ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (8): 1665-1681.doi: 10.7544/issn1000-1239.2017.20170187

所属专题: 2017人工智能前沿进展专题

• 人工智能 • 上一篇    下一篇



  1. 1(武汉轻工大学数学与计算机学院 武汉 430023);2(武汉大学计算机学院 武汉 430079) (
  • 出版日期: 2017-08-01
  • 基金资助: 

D\+3MOPSO:An Evolutionary Method for Metasearch Rank Aggregation Based on User Preferences

Tang Xiaoyue1, Yu Wei2, Li Shijun2   

  1. 1(School of Mathematics and Computer Science, Wuhan Polytechnic University, Wuhan 430023);2(Computer School, Wuhan University, Wuhan 430079)
  • Online: 2017-08-01

摘要: 随着网络数据的爆发式增长和用户需求的多元化发展,现有元搜索排序聚合方法在精度和性能上面临着巨大挑战.以满足用户的多重需求和个性化偏好为目标,提出了一种新的元搜索排序聚合算法.通过重新定义多目标粒子群优化算法(multi-objective particle swarm optimization, MOPSO)中粒子的属性,调整速度变化因子,改进种群初始化和演化机制,设计新的存档与更新策略以及引导微粒选择策略,提出了一个基于支配分解的离散多目标优化(D\+3MOPSO)算法,使其能根据用户的质量需求偏好在大规模离散解空间中快速准确地找出最优解集.在多个数据集上的实验结果表明:当数据规模较小时,D\+3MOPSO算法的精度和性能接近机器学习排序聚合方法;在大规模数据环境下,其精度和性能优于机器学习方法以及同类多目标优化方法.

关键词: 排序聚合, 元搜索, 用户偏好, 多目标优化, 离散粒子群优化

Abstract: Much work has been done to implement metasearch engines with different rank aggregation methods. However, those methods do not have the ability to deal with the exploding data from huge amount of Web sources as well as the multiplying requirements of metasearch users. In this paper, we take the view that the rank aggregation problem can be solved with a multi-objective optimizer if the quality requirements of a user are considered along with the queries, and we find that the user’s preferences among those quality requirements can help reduce the solution space. Accordingly, we propose an evolutionary rank aggregation algorithm based on user preferences. We bring a new encoding scheme for MOPSO, leverage new definitions of position and velocity, modify initialization methods of the particle swarms, improve the turbulence operator, and adjust strategies of external archive updating and leader selection, aiming at building a discrete multi-objective optimizer based on decomposition and dominance (D\+3MOPSO) to map out the best aggregated ranking quickly and accurately from a large-scale discrete solution space. We have the proposed algorithm along with several state-of-the-art rank aggregation methods tested on 4 datasets of different sizes: the LETOR MQ2008-agg dataset, a Web dataset, a synthetically simulated dataset and an extended Web dataset. The experiment results demonstrate that our method outperforms machine-learning-based algorithms and other multi-objective evolutionary algorithms by convergence, performance and efficiency especially when dealing with the large-scale metasearch rank aggregation tasks.

Key words: rank aggregation, metasearch, user preference, multi-objective optimization, discrete particle swarm optimization