D3MOPSO：一種基于用戶偏好的元搜索排序聚合演化方法

湯小月 余 偉 李石君

1(武漢輕工大學數學與計算機學院 武漢 430023) 2 (武漢大學計算機學院 武漢 430079) (sharontang@whu.edu.cn)

D3MOPSO：一種基于用戶偏好的元搜索排序聚合演化方法

湯小月1余 偉2李石君2

1(武漢輕工大學數學與計算機學院 武漢 430023)2(武漢大學計算機學院 武漢 430079) (sharontang@whu.edu.cn)

隨著網絡數據的爆發式增長和用戶需求的多元化發展，現有元搜索排序聚合方法在精度和性能上面臨著巨大挑戰.以滿足用戶的多重需求和個性化偏好為目標，提出了一種新的元搜索排序聚合算法.通過重新定義多目標粒子群優化算法(multi-objective particle swarm optimization, MOPSO)中粒子的屬性，調整速度變化因子，改進種群初始化和演化機制，設計新的存檔與更新策略以及引導微粒選擇策略，提出了一個基于支配分解的離散多目標優化(D3MOPSO)算法，使其能根據用戶的質量需求偏好在大規模離散解空間中快速準確地找出最優解集.在多個數據集上的實驗結果表明：當數據規模較小時，D3MOPSO算法的精度和性能接近機器學習排序聚合方法；在大規模數據環境下，其精度和性能優于機器學習方法以及同類多目標優化方法.

排序聚合；元搜索；用戶偏好；多目標優化；離散粒子群優化

元搜索引擎[1-7]的用戶對檢索結果的質量要求通常包含著多重約束條件或意圖.不同的用戶對檢索結果的各項質量指標也會有不同的偏好與側重.為了更好地滿足用戶個性化的檢索需求，元搜索引擎應當將用戶對排序結果的質量偏好作為其排序聚合過程的重要參考.

現有的元搜索排序聚合算法大多是通過基于機器學習的方法來適應用戶的個性化偏好的，訓練一個合適的排序學習模型[8-17]，使其能輸出符合用戶期望的排序聚合結果.然而，隨著互聯網數據源的爆發式增長，基于學習模型的排序聚合算法在聚合與重排大規模數據源的檢索結果時，其排序效率和性能都受到了極大的挑戰.針對這一問題，有一種解決思路是將元搜索的排序融合視為一個尋找排序最優解的問題，然后采用學習效率更高、優化速度更快的演化算法來求解.然而，現有的基于演化的排序聚合算法[18-28]大都實現的是較為簡單的單目標優化，以單一的質量或效率度量值作為尋找最優解的依據，即使考慮了多個度量指標，也只是對其進行簡單的綜合，依然無法滿足用戶對排序結果的多元化、個性化的質量偏好.

為此，本文提出一種基于用戶自定義的質量偏好的元搜索排序聚合方法，在多目標粒子群優化算法的基礎框架上，通過重新定義其粒子狀態、更新策略與映射機制，實現對海量數據項的聚合與多維度排序問題的演化求解.本文的主要貢獻有3方面：

1) 提出了一種基于用戶自定義的質量偏好的檢索結果聚合模型，使聚合結果能夠在多個維度上滿足用戶的偏好；

2) 提出了一種適用于大規模數據項排序過程的全局最優解發現方法，通過引入用戶的質量偏好來提高解空間的搜索效率和改善優化效果；

3) 通過重新定義多目標粒子群算法中的映射機制，建立了粒子與實際數據項的關聯，進而提出一種新的基于演化的排序聚合算法D3MOPSO，該算法具有較強的收斂性，能夠快速地得到滿足用戶多重質量需求的排序聚合結果.

1 相關工作

從元搜索問世至今，已有大量的文獻記錄了對其進行的研究[1-7].對于其中決定檢索質量的關鍵問題——排序聚合問題，目前的研究重點集中在基于排序學習模型的方法上.在無監督的排序學習方法中，文獻[8]提出了一種基于位置得分的方法，通過檢查數據來動態地向每個位置分配權重；文獻[9]用基于Markov鏈的方法來實現排序聚合；文獻[10]提出根據平均Kendall-Tau距離或Kemeny距離來判斷排序聚合最優解；文獻[11]提出了Condorcet熔絲格式搜索方法；文獻[12]提出一種使用分數線性聚合的數據融合方法；文獻[13]用Mallows模型聚合來自領域專家的類型排名.在有監督的排序聚合學習方法中，文獻[14]提出了一種基于監督學習的排序聚合概率模型；文獻[15]提出了基于查詢相似性的監督排序聚合框架；文獻[16]討論了絕對和相對在線學習的概念，并比較了多種排名方法；文獻[17]將從特征值生成的額外中間特征用于排序函數的兩階段學習.然而，隨著互聯網數據的爆發式增長，無論是監督還是非監督算法都很難滿足海量數據源環境下的數據聚合與排序的性能和精度要求.于是，一類更易于實現、搜索速度更快的人工智能方法——演化方法——引起了學界的重視，如模擬退火算法[18]、遺傳算法[19]、蟻群優化算法[20]、禁忌搜索算法[21]和粒子群優化(PSO)算法[22].對元搜索而言，其排序聚合問題是一種離散優化，而對離散粒子群優化(DPSO)算法的研究已有不少先例.第1個DPSO算法是Kennedy和Eberhart在文獻[23]中提出的二進制粒子群優化算法(BPSO)算法；文獻[24]討論將連續空間映射到離散空間的方法并提出了若干以空間變換技術為特征的離散粒子群優化算法；文獻[25]通過分析粒子的飛行軌跡和引入廣義中心粒子和狹義中心粒子，提出一種雙中心粒子群優化；文獻[26]提出一種基于集合的粒子群優化算法(SPSO)，將候選解和速度分別定義為一個清晰集合和一個基于概率的模糊集合；文獻[27]提出了一種模糊粒子群優化算法；文獻[28]提出了一種基于加權和的離散粒子群優化算法；文獻[29]把遺傳算子引入粒子群優化算法中，提出了一種收斂精度較高的混合型智能優化算法.

盡管上述離散粒子群演化算法在許多排序應用中都獲得了良好的效果，但由于用戶需求多元化的發展特性，元搜索排序聚合問題不僅是一個離散演化問題，更是一個多目標粒子群優化問題，而由于缺乏充分的映射機制，目前也鮮有研究討論如何運用多目標粒子群的演化算法來滿足元搜索用戶的多維度需求.

本文提出的基于多目標粒子群的元搜索排序聚合演化算法將粒子與待排序數據項進行一一映射，通過粒子的運動在多維解空間中尋找排序最優解集合，并結合用戶對排序聚合結果質量的個性化偏好以縮小最優解的搜索范圍.不僅滿足了用戶對檢索結果多維度的質量需求，提高了解空間的搜索效率，還改善了粒子群演化算法在離散環境下的數據收斂性.同時，該方法也可以有效地彌補學習模型在大規模數據環境下排序聚合精度和性能上的退化.

2 基于用戶偏好的元搜索排序聚合表示法

本節介紹與元搜索排序聚合問題相關的定義與描述.

2.1基本定義

元搜索引擎的各類用戶由于職業、年齡、知識領域、專業背景等條件的不同，其對檢索結果的數據質量也有不同的偏好.例如對于同一檢索詞“奧巴馬”，有些用戶對排序結果的時效性要求較為嚴格，而另一些用戶則期望將更具權威性的結果排在前列.因此，本文將滿足用戶對數據的檢索需求和個性化偏好視為數據采集和整合過程中需要同時達成的雙重目標.用戶的檢索需求來源于用戶輸入的查詢限定條件，而用戶的個性化偏好(本文將重點研究用戶對數據質量各項指標的偏向性)則取決于用戶的歷史檢索行為.在詳細描述本文算法與排序聚合模型之前，首先需要對與“基于用戶偏好的排序聚合”問題相關的一些用語和符號進行定義和解釋.

定義1. 帶質量標簽的數據源.對于元搜索引擎的任意一個數據源(即獨立搜索引擎)，可用集合DS={ID,UR,OD,DQ}對其進行描述，其中，ID表示數據源名稱，UR表示用戶輸入的檢索詞集合，OD={d1,d2,…,dN}為當前數據源中的全部待排序數據項(即文檔，為保持術語的通用性本文統稱為數據項)的集合，N為數據項總數，該集合中任意一個數據項可表示為d=(w1,w2,…,wL)，wi表示長度為L的詞表中第i個詞匯在數據項d中對應的度量值.DQ為數據源的質量標簽向量，通常可表示為DQ=(v1,v2,…,vM)，其中vi為該標簽中第i個質量指標的值，M表示考察的質量指標的個數.

根據元搜索的通用質量標準，本文選取準確性、可靠性、時效性、訪問速度、領域相關性這5個指標對數據源質量進行考察.假設某數據源的質量標簽為(0.2,0.3,0.1,0.6,0.1)，這表示該數據源的準確性權值為0.2，可靠性權值為0.3，時效性權值為0.1，訪問速度權值為0.6，而領域相關性權值為0.1.對于元搜索采用的所有數據源，可采用文獻[30]中的評估方法對其質量標簽進行計算.

定義3.Y項-支配(PY-占優).假設存在函數F，可對任意數據源中的任意數據項d計算其質量標簽向量，即F(d)=(f1(d),f2(d),…,fM(d))，其中M為質量指標數.當2個數據項d1和d2的質量標簽向量F(d1)和F(d2)的各分量滿足以下2個條件時，可稱數據項d1“Y項-支配(PY-占優)”數據項d2，記為d1?PYd2：

1) ?i∈{1,2,…,M}:fi(d1)≥fi(d2)；

其中，Y為集合Set的大小.當Y=1時，Y項-支配即為Pareto支配.需要注意的是，當Y≤[M/2]時，Y項-支配是一種非劣支配關系.

結合上述定義，可以正式給出本文所研究的基于用戶偏好的元搜索排序聚合問題的描述.

2.2基于用戶偏好的元搜索排序聚合問題描述

Fig.1 Searching grid of particles on objective dimension z圖1 質量目標維度z上的最優解集搜索網格示意圖

第2.1節提到，為了在關鍵詞匹配檢索的前提下滿足不同用戶對檢索結果質量的個性化偏好，可以將用戶對數據的檢索需求和個性化偏好視為元搜索數據采集和整合過程中需要同時達成的多重目標.因此，基于用戶偏好的元搜索排序問題可看作是一個根據用戶對數據的偏好而指定目標權重的多目標優化問題.假設用戶輸入的查詢限定條件集合為UR，從用戶的歷史檢索行為中可以得知用戶偏好向量為UP，那么將多個數據源DS1,DS2,…,DSn中的海量數據項根據用戶偏好UP進行元搜索排序聚合就是要從滿足查詢條件UR的數據項集合中找出以用戶偏好UP為優化目標的全局Y項-支配(PY占優)最優解集合SPY={d*|?SPY:d?PYd*}以及該集合元素的Top-K排序結果LPY=(d1,d2,…,dK)，使得在用戶較為偏重的質量指標上占優的數據項排序靠前，而在用戶不夠偏重的質量指標上占優的數據項排序靠后，即?di∈LPY,1≤i≤K,?1≤j≤M，有或且同時滿足:

(1)

由于互聯網上的數據源數目龐大，若先按查詢條件對多個數據源的海量數據項進行篩選，再從符合條件的數據項中挑選符合用戶多元化、個性化的質量偏好的集合進行排序，其運算規模是巨大的，現有的排序聚合技術在效率上難以應對此類高維度、大數據量的問題.為此，本文提出一種基于支配分解的多目標離散粒子群優化方法(discrete multi-objective particle swarm optimizer based on decom-position and dominance, D3MOPSO)來解決這一問題.

3 D3MOPSO：一種改進的離散多目標粒子群算法

本節詳細介紹如何改進多目標粒子群優化算法，以適應求解元搜索排序聚合問題的需要,將從數據項與粒子的映射方法、粒子群初始化方法、粒子的位置與速度定義、粒子狀態更新規則、迭代存檔策略等方面深入介紹本文提出的D3MOPSO算法.

3.1多方向的目標搜索策略

傳統的離散多目標粒子群優化方法需要將所有的離散點在某個維度上以線性方式按一定方向排序，以保證搜索在前后2個方向上的隨機游走.然而對于規模極大的互聯網數據來說，由于離散點數量驟增，這種搜索方法效率不佳.本文根據數據源和元搜索結果的特性，對數據源集合中符合用戶輸入條件UR的全部數據項取其質量標簽向量DQ某一特定分量的值，按其大小將數據源排列成網格.由此可以定義排序優化搜索網格的結構如圖1所示:

(2)

(3)

(4)

(5)

由于I，J兩個方向的有序，這種分布方式能使每個粒子第z個質量維度上的目標值都在一個小領域內保持相對平滑，有利于粒子在局部搜索中找到的極值.更重要的是，粒子在該搜索網格中能夠多方向游走，從而提高搜索效率.算法1描述了針對M個目標分別生成對應的搜索網格的過程.

算法1. 最優解集搜索網格生成算法.

輸入:n個數據源DS1,DS2,…,DSn、用戶查詢詞集合UR、各數據源質量標簽向量DQ形如(v1,v2,…,vM)；

輸出:對應于M個質量偏好排序目標的搜索網格(矩陣).

③ParticleGraph(z)=newmatrix(Maxitem,n)； /*z=1,2,…,M*/

④SortIndex(z)=newmatrix(1,n)； /*存儲按數據源的特征z降序排列后的數據源索引值*/

⑤ forz=1:M

⑥SortIndex(z)=SORT(DS1,DS2,…,DSn) byDQ.vz；

⑦ParticleGraph(z)=(DSSortIndex(z)(1),DSSortIndex(z)(2),…). /*重新排序各數據源的結果*/

⑧ end for

3.2種群的初始化策略

傳統的排序聚合算法更多地考慮高質量的數據源和數據項的排名，因而很容易丟失更多的候選數據.而一般的粒子群算法采用隨機初始化策略，也容易造成收斂困難.本文提出一種加權隨機初始化方法，原理是結合數據源的質量標簽和數據項位置的分布規律隨機進行概率分配.

算法2. 粒子群初始化算法.

輸入:z/*生成初始粒子群的質量目標維度編號*/；

輸出:搜索第z個質量目標網格矩陣的粒子群.

①rand1=random()； /*生成[0,1)上的隨機數*/

②SortIndex=SORT(DS1,DS2,…,DSn) byDQ.vz； /*向量用來存儲按數據源的特征z降序排列后的數據源索引值*/

④si=0； /*存儲隨機選擇的數據源編號(排序后的編號)*/

⑤ fori=1:n

ifrand1

si=i；break；

elserand1-=DSSortIndex(i).DQ.vz/TotalScore；

end if

end for

⑥ti=0； /*存儲隨機選擇的數據編號*/

⑧rand2=random()； /*生成[0,1)上的隨機數*/

⑨ fori=1:DataNumber

ifrand2

ti=i；break；

elserand2-=hi-beta；

end if

end for

⑩ returnd(si,ti). /*選中第si個數據源的查詢結果中的第ti個數據作為粒子*/

3.3粒子的位置與速度變化規律

為了提高從大規模數據項集合中選取多目標最優解的效率，本文重新定義了傳統粒子群優化算法中的粒子位置與速度.

2) 粒子速度.粒子的運動速度規定了粒子的運動方向和位移，是決定粒子能否快速有效地收斂于最佳目的地的關鍵因素.用速度向量Vx=(vxI,vxJ)來定義粒子群中任一粒子px，1≤x≤s的運動速度，其中vxI,vxJ分別是粒子在搜索網格中I和J方向上的速度分量，其值都是整數.如果vxI為正值，則按di,j→Inext的方向移動vxI次，如果為負值，則按di,j→Iprior的方向移動vxI次；如果vxJ為正值，則按di,j→Jnext的方向移動vxJ次，如果為負值，則按di,j→Jprior的方向移動vxJ次.

3.4離散粒子的狀態更新過程

粒子群優化算法通過更新粒子的速度來改變粒子的移動距離.由于本文算法中粒子的位置和速度均為整數向量，因此本文也相應地重新定義了離散化的粒子速度變化規則，以適應離散化的元搜索排序聚合問題的需要.假設粒子px的速度Vx在I和J方向上的分量分別為vxI和vxJ，則每次粒子發生移動后速度就更新為式(6)所示形式.

(6)

在式(6)中，Pbx是粒子px的個體歷史最優位置，Obx是粒子群在當前質量維度上的局部最優位置，Gbx則是粒子群在全部質量維度上的全局歷史最優位置(描述參見3.6節)；ωI和ωJ為[0,1]區間內的隨機數，分別表示粒子在I和J方向上的慣性系數；cI1，cI2和cI3為I方向上的關系系數，表示粒子的自身歷史軌跡與群體運動規律對其速度的影響，類似的還有J方向上的關系系數cJ1，cJ2和cJ3，其值可通過訓練調優獲得；系數rI1，rI2，rI3以及rJ1，rJ2，rJ3是2組[0,1]區間內的隨機數.DI和DJ分別為方向I和方向J上的距離函數，其計算方法如例所示：設粒子px的當前位置對應數據項d15,32，其Pbx對應數據項d23,17，則可以計算得到函數值DI(Pbx-px)=8，DJ(Pbx-px)=-15.

根據上述粒子速度的變化規則，將粒子位置更新規則重新定義的離散形式為

(7)

式(7)中的運算符⊙表示對粒子位置狀態的更新運算，其值域范圍決定了粒子移動的方向和位移大小，因此該運算也是決定算法性能的關鍵.一個成功的位置更新策略必須保證粒子的每次移動都能更加靠近目的地.據此本文對粒子位置的更新運算⊙進行重新定義.假設粒子px更新前的起始位置對應于數據項dk,l，經過更新操作后粒子將移動到數據項dk′,l′對應的目標位置.則運算符⊙對應下列計算：

(8)

(9)

Fig.2 Searching directions of a particle圖2 搜索過程中的粒子運動方向示意圖

3.5保留多樣性與用戶偏好的存檔策略

現有的粒子群優化算法通常借助外部存檔(external archive, EA)來存儲搜索過程中產生的Pareto解[31]，其基本思路是通過對算法當前迭代過程中產生的最優解與EA中的元素進行Pareto支配的比較來獲得Pareto最優解，即：當EA中的元素數目尚未達到最大容量MAXP時，直接將新生的非被支配解插入；而當EA已滿時，隨機決定是否用新生的非被支配解來優化EA中的某個隨機元素.但隨著優化目標增多，在迭代優化的過程中會形成大量的非被支配解(相互不滿足Pareto支配關系)，使得EA容易被迅速填滿，導致EA更新頻繁.在連續的優化問題中，這個問題可以通過使最優解匹配優化目標的平均期望來避免.解決方法包括基于KL散度(Kullback-Leibler divergence)的均衡性度量[32]和基于自適應網格法的最優點選擇[33]等方法.

在離散多目標最優化問題中，多樣性具有不同的涵義和意義.在大規模元搜索排序聚合問題中，保留解的多樣性主要是指減少最優解集中的相似解.有別于連續最優化問題中的Pareto最優前沿，離散最優化問題中的距離不一定能反映相似程度.因此，在本文提出的D3MOPSO算法中，檔案保存策略考慮了多樣性和用戶偏好等特征，避免了最優解集過大的情況.本文主要從3方面對檔案保存策略進行改進：

1) 用定義3中的Y項-支配(PY占優)代替Pareto支配機制，以保證存檔結果的領先性.Y的取值在實驗中將會進行訓練調優.

2) 定義粒子相似度時綜合考慮粒子的文本特征、質量特征和位置特征3方面的相似度，保留粒子的多樣性，以避免存檔的粒子過于集中.每個檔案(粒子)px實際上對應搜索網格中的一個數據項d，由于數據項d同時具有文本特征、質量特征和位置特征，因此，粒子px也同樣具有這3類特征：

①W(px)=(w1,w2,…,wL)表示px的文本特征；

②F(px)=(f1(d),f2(d),…,fM(d))表示px在質量標簽多個維度上的匹配度，是粒子的質量特征；

綜合上述3類特征，2個粒子pA和pB的相似度計算為

S(pA,pB)=S1(W(pA),W(pB))+
S2(F(pA),F(pB))+S3(P(pA),P(pB))，

(10)

其中，S1為2個粒子的文本特征相似度計算函數，度量方法已有許多[34]，本文采用的是向量余弦值.為了避免最優解都集中在適應某個單一目標的局部最優解附近，需計算粒子的質量特征相似度，其計算函數為

位置特征相似度計算函數S3(P(pA),P(pB))=e-|kA-kB|計算兩粒子的位置相似度.

Fig.3 Two pointers traversing through EA圖3 EA更新過程中的雙指針遍歷

3.6引導微粒的選取

選取合適的引導微粒可以有效提高粒子的多樣性和算法的收斂性.在傳統的粒子群優化算法中，存檔集合EA中的解兩兩不相互支配，因此必須從中選擇一個檔案成員作為全局最優目標位置Gb.通常的選擇策略有隨機選擇法和就近選擇法等[35-36].

在本文提出的D3MOPSO算法中，根據3.5節得到的存檔EA滿足相對有序性，即粒子在EA中的順序必然在某些目標質量維度上滿足一定的優劣支配關系.在這一存檔策略的基礎上，本文提出一種帶生命周期的全局最優位置淘汰機制，結合加權初始生存期賦值，進而有效地選出檔案成員得到引導微粒.

本文為存檔中的非劣個體設置生存期屬性，生存期是檔案成員充當全局最優位置角色并引導粒子尋找最優解的活動周期，其長度可以用歷經的迭代次數來表示，即生存期值.帶生存期的全局最優位置的淘汰機制的基本思路是：如果粒子群中某粒子px隨機選中檔案中某個非支配個體Ej作為全局最優解，則賦予檔案成員Ej一個初始的生存期值Lj=10j-αL0，其中j表示Ej在EA中的位置，α為該成員的位置系數，表示Ej的生存期長度與EA中當前存檔的最優解總數Num有關，本文取α=lnNum.L0為全局初始生存期，Li表示初始生存期會隨著EA中位置逐漸遞減，一旦當檔案成員Ej的生存期值L減至預設的最小閾值Lmin，甚至更小時，檔案成員Ej的活動期結束，進而從檔案中重新為粒子px隨機選擇一個非劣解作為它的全局最優位置并引導粒子px繼續飛行.此處生存期的值需要根據粒子之間的支配關系進行調整.對于檔案成員Ej，其生存期值按照3種情況進行調整：

其中的ΔL=(L1-Lmin)/l，ΔL為生存期L的調整步長，L0，Lmin和l為ΔL的計算參數.

4 D3MOPSO算法框架與復雜度分析

本文提出的D3MOPSO算法沿用了傳統粒子群優化算法的框架和交叉、變異的演化思想，同時在解空間搜索模式、種群初始化方法、粒子位置與速度變化規則、排序聚合規則以及外部存檔更新策略、全局最優解位置選擇策略等方面進行了較大改進，以適應元搜索排序聚合問題.

4.1算法描述

綜合各項步驟，可以得到本文提出的D3MOPSO模型的整體框架.

算法3. D3MOPSO算法框架.

輸入:n個數據源DS1,DS2,…,DSn，用戶檢索詞集合UR，各數據源質量標簽向量DQ形如(v1,v2,…,vM)；

輸出:有序的Top-K排序聚合最優解.

② 根據算法2初始化M個大小為SwarmSize的粒子群；

③ 根據3.3節定義粒子的結構體并初始化粒子群中個體的位置和速度；

④ 初始化粒子群中的每個個體最優位置矩陣PbMatrix、粒子群在每個質量目標維度上的局部最優位置矩陣ObMatrix；

⑤ 根據3.6節初始化計算全局最優位置矩陣GbMatrix的函數；

⑥ 開始迭代，根據3.3～3.6節，為粒子群中的每個個體生成新的位置值與速度值并更新PbMatrix,ObMatrix和GbMatrix矩陣；

⑦ 如果迭代中產生的任何一個粒子可以Y項-支配全局最優位置Gb，則根據3.5節判斷并將其加入到存檔EA中；

⑧ 每次迭代后，根據3.6節更新全局最優位置Gb及其生存期，根據具體情況進行變化；

⑨ 返回步驟⑥，直至達到最大迭代次數，結束算法并輸出存檔EA.

4.2復雜度分析

本文提出的D3MOPSO運行時有2個過程需要占用存儲空間:1)解搜索空間搜索網格的初始化，需要占用M×n×Maxitem≈M×N大小的存儲空間，空間復雜度為O(M×N);2)粒子群搜索最優解的迭代過程，假設粒子群規模為SwarmSize，則空間復雜度為3SwarmSize×M，即O(SwarmSize×M).因此，算法總的空間復雜度不超過O(M×N).

從算法3可以看出，由于初始化過程可以在常數時間內完成，D3MOPSO算法的最大時間耗費發生在迭代搜索最優解的過程中.考慮到在每次迭代中，粒子群更新粒子位置與速度的時間開銷為O(SwarmSize×M)，存檔最優解的時間開銷為O(MAXP)(假設檔案最大容量為MAXP)，更新全局最優位置矩陣的時間開銷也是O(SwarmSize×M)，可以推算出D3MOPSO算法在最壞情況下的時間復雜度為O(maxgen×SwarmSize×M)，其中maxgen為迭代次數.由于粒子群的大小和迭代次數與海量的待排序數據項規模相比起來非常小，因此，與線性多目標優化算法的復雜度O(NM)相比，D3MOPSO可以看作是一種快速的多目標排序算法.

5 實驗與結果

由于本文提出的D3MOPSO算法采用了改進的離散多目標優化思想來解決由用戶自定義質量偏好的元搜索排序聚合問題，為了方便比較，本文選取基于ANN網絡的ListNet排序算法[37]和基于蒙特卡羅模型的WT-INDEG算法[38]作為元搜索排序聚合的基線算法，同時選用NPDA[39]算法和BHTPSO算法[40]作為離散多目標優化基線算法，通過在排序學習數據集、真實網絡數據集、綜合仿真數據集和擴展真實數據集4種數據集上進行對比實驗來檢測D3MOPSO算法的有效性和性能.

5.1度量標準

1) Kullback-Tau距離(Kendall Tau distance, KTD)

為了衡量檢索結果和期望結果真值的偏差，采用KTD來評價排序聚合結果與期望結果的距離.假設用戶對輸入查詢詞集合UR后元搜索的排序結果存在有期望真值，則此次檢索結果的KTD[41]可表示為

K(τ1,τ2)=|{(i,j):i(τ2(i)>τ2(j))∨(τ1(i)>τ1(j))∧
(τ2(i)<τ2(j))}|，

(11)

其中,τ1(i)和τ2(i)分別表示數據項i在實際排序結果與期望排序結果中的序號.KTD的值越小，實際排序結果越符合用戶的期望.

2) 歸一化折損積累增益(normalized discounted cumulative gain, NDCG)

為了給網絡數據源中的每個檢索結果數據項找到聚合排序結果的最佳可能排名，可以采用歸一化折損累積增益(NDCG)指標來評估排序結果的準確度[42].假設有k個待排序的數據項，那么排序結果的NDCG@k指標計算為

(12)

其中,函數ref計算數據項i與檢索詞的相關性，σ是i的理想排名,歸一化參數Nk使得最優排序的NDCG@k始終等于1.

3) 多樣性指標(diversity metric, DM)

由于離散數據和排序聚合問題的特殊性，傳統的間距指標(spacing metric)[43]無法有效的描述近似最優解集EA中的解與解之間的距離.考慮到解之間的位置距離、語義距離和順序距離，假設L為排序算法得到的近似最優解向量，針對本文的數據項排序聚合過程定義一個專門的多樣性指標DM如下：

(13)

其中,pi和pj都是排序聚合結果最優解L中的粒子，與之對應的是相應位置上的待排序數據項.距離函數C計算粒子pi和pj所在位置之間的Chebyshev距離，差異性函數D計算粒子pi和pj對應的數據項之間的語義距離，即文檔內容的差異性.M則是用戶的質量偏好向量的秩，函數f的含義參見定義2.因此，DM值越大，排序聚合結果的多樣性就越好.

4) 收斂性指標(convergency metric, CM)

(14)

由此，本文考察的收斂性指標CM可以被定義為D3MOPSO算法近似最優解向量中所有項的歸一化距離的平均值：

(15)

收斂性指標代表算法得到的近似最優解集和支配最優解全集.因此，該指標值越低就表明算法得到的解的收斂性越好，越接近理想結果.

5) 收斂迭代次數(iteration converging generation metric, ICGM)

使用多目標進化算法來求解問題時，達到收斂所需的迭代次數直接反映了算法的收斂速度，ICi表示第i次迭代結束后檔案EA中被更新的存檔粒子數，則每次進化算法執行過程中開始收斂的迭代次數ICGM為滿足約束條件?i>Gen,ICi<φ的迭代數Gen的最小值.其中φ為檔案EA更新存檔數的最小閾值，即在經過了ICGM次迭代之后的迭代過程中，如果每一次更新的存檔數少于φ個，則認為本算法在第ICGM次迭代后達到收斂.本文通過參數試驗設置φ=2.ICGM越小，說明收斂速度越快.如果迭代次數達到maxgen時EA更新的存檔粒子數仍不小于φ，則說明整個迭代周期都沒有收斂.值得注意的是，如果ICGM比較小，而收斂性指標CM不理想，則說明該算法陷入早熟收斂.

6) 執行時間(Time)

為了比較各方法的效率，在同樣的數據集情況下，直接使用執行時間來進行比較.執行時間越小，說明算法效率越高.

5.2數據集

本文將在排序學習公共數據集、真實網絡數據集、綜合仿真數據集和擴展真實數據集這4種類型的數據集上測試本文所提出的方法.下面從數據集大小和數據特點等方面分別介紹這4類數據集.

1) 排序學習公共數據集(LETOR dataset)

本文選取微軟的LETOR排序聚合數據集MQ2008-agg進行公共數據集上的算法測試.該數據集包含了在25個匿名數據源對800次查詢請求進行響應的結果.由于LETOR數據集對每條查詢結果數據項均給出了46個特征值，根據這些特征值可以計算出各數據項的多個質量特征值和各數據源的質量標簽向量，從而構造本文提出的D3MOPSO算法所需的實驗數據集.

2) 真實網絡數據集(real-world dataset)

本文選取的真實網絡數據集是從20個真實Web搜索引擎數據源的檢索結果中采集得到的，數據項來自于30次不同的檢索請求，平均每次檢索對每個數據源抓取約200條數據項.實驗中針對每個數據源、每條有效檢索結果數據項計算其文本特征向量、數據源質量標簽向量等特征值的方法來自于文獻[30].

3) 綜合仿真數據集(synthetic simulation dataset)

本文選取的另一個數據集是根據真實數據源的分布特征所生成的模擬數據集合.綜合了來自于1 000個仿真數據源的檢索結果數據，每個數據源的平均記錄條數約為150條，共計進行了100次模擬檢索請求，累計生成15 837 493條記錄.每條記錄都需要進行數值化處理，即將每條記錄都表示為在M個質量目標維度上的取值，即如(v1,v2,…,vM)的形式.

4) 擴展真實數據集

為了比較不同規模的真實數據集對算法效率的影響，本文抓取了更大規模的真實數據作為擴展真實數據集進行實驗.該數據集采納了135個數據源(55個Web搜索引擎和80個在線電子圖書館)的搜索數據，共提交查詢請求30次(查詢詞與真實數據集相同)，對每次查詢均從135個數據源返回的結果中抓取前50條數據項，獲取數據項共計173 279條.

結合上述4類數據集各自的數據規模與特點，本文對各數據集進行以下劃分.考慮到排序學習數據集LETOR MQ2008-agg和綜合仿真數據集2個數據集中包含標準排序結果，適用于基于機器學習排序聚合算法的訓練和參數調整過程，因此，本文選取這2個數據集中的60%作為訓練集，20%作為交叉確認集，20%作為測試集.各項算法在上述2個數據集上的測試結果可以用以比較排序效果指標.對于缺乏標準排序結果的真實數據集和擴展真實數據集，直接取其全部數據項作為測試集，僅計算排序結果的性能指標.

另一方面，為了方便控制數據規模，對4個數據集中的數據源和數據項也要進行篩選.對于包含800查詢詞的LETOR數據集，取其中60%查詢詞(480個)的對應結果作為訓練集，另取20%查詢詞(160個)的對應結果作為交叉確認集，余下20%查詢詞(160個)的搜索結果作為測試數據集.每條查詢均涉及25個數據源，對每個數據源取其前15條檢索結果.對于包含30個查詢詞的真實數據集，對其涉及到的20個數據源，各取前50條檢索結果.對于包含100個查詢詞的仿真數據集，按同樣比例進行劃分，取其中60查詢詞的對應結果作為訓練集，另取20查詢詞的對應結果作為交叉確認集，余下20個查詢詞的檢索結果作為測試集.每條查詢涉及1 000個數據源，各取前15條查詢結果.對于包含30個查詢詞的擴展真實數據集，對其涉及的135個數據源各取前50條檢索結果.

5.3實驗參數設置

在本文提出的D3MOPSO算法中，有一些參數需要通過訓練實驗來獲取最佳的取值.例如定義3“Y項-支配”中的Y值將直接影響到最優解的判定，通過對綜合仿真數據集在Y∈{1,2,3,4,5}中的各個可能取值上進行訓練實驗，得知Y=3時的優化效果最好.實驗發現，Y=1會導致大量的粒子相互支配，而Y=5時，滿足“5項-支配”關系的粒子又太少.只有當Y=3時，最優解集合的大小適中.

根據3.2節，某數據源檢索結果數據項中最后一名的最小概率a反映了遞減函數的最小值，通過訓練實驗發現，a≈1/(3mi)≈0.001 67為其最佳取值.而在粒子速度的變化規則中(見3.4節)，I方向上的關系系數最佳取值為：cI1=n/100，cI2=n/80以及cI3=n/50，J方向上的關系系數的最佳取值為：cJ1=1.08，cJ2=1.49以及cJ3=2，其中n為數據源的數量.外部存檔EA的最大容量取值MAXP=200時效果最好，如果檔案容量繼續增大則會影響算法收斂速度.3.5節中介紹的目標維度上的容錯誤差θ=0.01，表示當2個粒子在某個目標維度上的值的距離小于θ，則可認為其值相同.粒子相似閾值λ=0.7，表示當2個粒子的相似度很接近時，需進行篩選操作.最后，對于3.6節所述的引導微粒生存期的計算參數，通過多次試驗調整，最終設置為L0=1,Lmin=1,l=20.

5.4實驗與結果

本文基于5個維度的質量目標(準確性、可靠性、時效性、訪問速度和領域相關性)對用戶偏好和數據源質量標簽進行定義和計算，在上述4類數據集上均構建D3MOPSO算法、基于ANN的ListNet算法、基于蒙特卡羅模型的WT-INDEG算法、基于多目標優化的NPDA算法、BHTPSO算法這5種算法的排序模型，進行對比實驗.

采用基于listwise的ANN算法ListNet實現排序聚合的基本思路是將各數據源中的所有非重復數據項看作待排序數據項，采用選取各數據項的5維質量特征，以LETOR公共數據集和仿真數據集中提供的帶標準排序結果的訓練集為基礎對ListNet中的神經網絡進行訓練，最后用訓練好的網絡模型對各個數據集中的全部待排序數據項進行綜合排序.為了避免計算量過大，本文選取層數為1的線性神經網絡，使用交叉熵表示損失函數，學習步長設為0.3，最大迭代次數maxgen=1 000，采用梯度下降法來對排序函數的梯度ω進行訓練，進而計算各排序序列的Top-3概率.

基于蒙特卡羅模型的WT-INDEG算法的基本思路ANN方法類似，對所有數據源中的非重復數據項進行整體排序從而實現排序聚合.將數據項的5個維度的質量特征值結合用戶偏好程度作為權重，以KTD距離最小化為學習目標，每輪生成樣本數量1 000個，變異分位數rho設為0.1，更新概率設為0.25，最大迭代次數maxgen=1 000，停止閾值為30次，即當中間結果在30次內KTD沒有改進時停止學習.

基于多目標優化的NPDA算法和BHTPSO算法無法從目標的優先順序角度實現用戶對各個質量目標的偏好，因此需要以結果中的數據項的質量特征向量與用戶提供的質量偏好向量在各維度上的差異最小為目標來實現對多個數據項的重新排序與聚合.為了便于比較，在本文的實驗中，D3MOPSO，NPDA和BHTPSO這3種基于多目標優化的算法的最大迭代次數均設為200次，即maxgen=200，優化目標均為5個.其中BHTPSO算法中的慣性系數取[0.2,0.6]區間內的隨機數，而加速系統分別從區間[0.5,2.0]，[1.0,2.0]和[0.5,1.5]中隨機生成和調整.

根據5.1節，本文選取的性能指標主要包括KTD，NDCG，DM，CM這4項指標.針對4類數據集，各排序聚合算法對每個數據集的測試子集中的所有查詢詞逐一完成排序聚合實驗，對多次實驗結果的KTD，NDCG，DM，CM指標值取平均值和標準差，以比較各算法的排序聚合表現.

1) 在排序學習數據集上的表現

LETOR MQ2008-agg數據集是一個公共數據集，每個查詢詞都有對應的標準排序列表.表1展示了在該數據集上各算法的排序聚合指標的比較結果.

Table 1 Performance of Algorithms on LETOR Dataset表1 排序學習數據集上各算法的排序聚合效果指標

在與排序效果相關的KTD和NDCG指標上，D3MOPSO算法與ANN和WT-INDEG算法接近，這是因為ANN和WT-INDEG方法采用的排序算法具有良好的排序結果比較特性；另一方面，D3MOPSO算法的KTD和NDCG指標均值要遠優于NPDA和BHTPSO方法，這是因為NPDA和BHTPSO方法得到的最優解是一個無序的集合，在排序上表現不佳.在反映多樣性的DM指標上，D3MOPSO算法要略差于NPDA和BHTPSO方法，這是因為NPDA和BHTPSO方法在多樣性選擇時的主要依據就是粒子位置，因而導致了最優解集在粒子位置上的差異很大，導致DM指標值更高；同時，在DM指標上D3MOPSO算法又優于ANN和WT-INDEG方法，這是因為ANN和WT-INDEG方法對排序結果的多樣性考慮不足.最后，在體現排序結果收斂性的CM指標上，D3MOPSO算法表現接近NPDA和BHTPSO方法，并且5個方法在CM指標上都表現良好，說明各方法得到的結果都能有效地接近最優解集合.因此，在針對LETOR公共數據集的實驗中可以發現，D3MOPSO算法的排序效果比較理想，能夠有效地接近最佳的聚合排序結果.

2) 在真實網絡數據集上的表現

由于真實網絡數據集不便獲得最佳期望排序結果作為排序效果參照值，因此，在該數據集上主要分析各個算法在DM和CM兩個指標上的表現.表2展示了在真實網絡數據集上各算法的多樣性和收斂性指標的比較結果.

可以看出，在數據規模較小的真實網絡數據集的實驗中，D3MOPSO和BHTPSO，NPDA在收斂速度上表現十分接近，并未明顯體現出優勢，甚至不及BHTPSO算法收斂速度快，這是因為D3MOPSO算法與BHTPSO相比，在迭代過程中需要多一步計算歷史最優位置，而歷史最優位置只有在數據規模較大、迭代次數較多時才能顯著地加速搜索最優解的過程，抵消計算帶來的時間開銷.

Table 2 Performance of Algorithms on Real-world Dataset表2 真實網絡數據集上各算法的排序聚合效果指標

3) 在綜合仿真數據集上的表現

綜合仿真數據集中每個查詢詞對應的標準排列順序來自于數據項自動生成后的特征值比較結果.表3展示了在綜合仿真數據集上各算法排序聚合指標的比較結果.

表3中的數據表明，在大規模的多數據源數據項的排序聚合中，ANN和WT-INDEG方法在體現排序效果的KTD和NDCG指標上表現不佳，其收斂性指標CM的值更是表明其排序結果嚴重偏離最優解集.而NPDA和BHTPSO方法雖然在多樣性指標DM上表現良好，但是以降低了收斂性指標CM的值為代價的.由于解空間過大，NPDA和BHTPSO算法為了遍歷解空間搜索最優解需要擴大粒子的運動幅度，容易使粒子跳躍過快，從而導致難以收斂.通過在綜合仿真數據集上的實驗發現，在解空間規模驟增的情況下，只有D3MOPSO算法可以在各項排序指標上能保持較為均衡而平穩的表現，其排序聚合的結果也遠遠優于其他方法.

Table 3 Performance of Algorithms on Synthetic Simulated Dataset表3 綜合仿真數據集上各算法的排序聚合效果指標

4) 在擴展真實數據集上的表現

與真實網絡數據集類似，在擴展真實數據集上僅分析各個算法在DM和CM兩個指標上的表現.表4展示了在擴展真實網絡數據集上各算法的多樣性和收斂性指標的比較結果.實驗結果表明：在規模較大的擴展真實網絡數據集上，D3MOPSO算法在多樣性與收斂性方面與基于排序學習的ANN和WT-INDEG算法相比具有明顯優勢，在多樣性上雖略遜于同為基于多目標優化的NPDA和BHTPSO算法，但在收斂性上比這2個算法稍好.

Table 4 Performance of Algorithms on ExtendedReal Dataset表4 擴展真實數據集上各算法的排序聚合效果指標

上述實驗結果表明，在有監督的學習環境下，即在LETOR公共數據集和綜合仿真數據集的實驗中，基于機器學習的排序聚合方法排序效果指標的均值較高并且標準差較小，表現較為穩定，但一旦脫離了學習目標，基于機器學習的排序聚合方法排序效果下降明顯，穩定性也降低.基于演化的方法在各種環境之下的排序表現差異不大，就排序性能的穩定性而言，基于粒子群優化的D3MOPSO算法和BHTPSO算法要優于NPDA算法.而綜合表現上，D3MOPSO算法在對大規模數據進行排序聚合時性能最為穩定.

值得注意的是，D3MOPSO算法在多樣性指標上表現不及BHTPSO，NPDA算法.這是因為以窮盡式搜索為主導思想的多目標優化算法(包括BHTPSO和NPDA算法)會保留盡可能多的非劣解，以提高最終得到的最優解集的多樣性.這樣做的弊端是導致算法收斂的效率往往不高.為此，BHTPSO,NPDA兩種算法分別采取了有效的策略來避免收斂速度慢的問題[39-40].多方面的實驗結果表明，在適度數據規模下，BHTPSO和NPDA算法在收斂速度上具備現有的多目標優化算法中的較高水平，如表1、表2所示.

針對元搜索排序融合這一特定問題，由于其用戶對檢索結果的各項質量指標的重視程度存在差異，具有偏向性.這就意味著在這個特殊的多目標優化問題中可以通過降低對多樣性的要求來“補償”算法的收斂性.通過引入用戶偏好，一方面可以根據子目標的優先順序有效地縮小多目標優化的解空間，加快迭代速度；另一方面還能結合全局最優、局部最優以及歷史最優的位置信息來優化粒子的搜索路徑，進一步提升收斂性.D3MOPSO算法綜合采納了上述2種思路，雖然在存檔最優解時將多樣性納入了考慮，避免了出現過多相似解，但由于采用了基于用戶偏好設置的雙窗口滑動有序比較來縮減最優解的存檔大小，保留的非劣解相較BHTPSO,NPDA兩種算法更少，因此多樣性表現不及這2種算法(表2)，但在收斂性的提升效果上卻比BHTPSO,NPDA兩種算法更有優勢，并在數據規模較大時體現得較為明顯(表3、表4).

5.5原因分析

本文提出的D3MOPSO算法的最大優勢是在大規模數據環境下的時間性能要明顯優于基于排序學習模型的ANN算法、WT-INDEG算法以及同樣基于演化的NPDA算法、BHTPSO算法.

Fig.4 Execution time comparison of algorithms on 4 datasets圖4 4類數據集上各算法的排序聚合執行時間對比圖

假設N為輸入的待聚合排序結果個數.基于機器學習的排序聚合算法的實現思路是將所有的非重復的數據項進行重新排序得到最終結果.基于ANN網絡的ListNet算法通過訓練神經網絡為所有可能的排序序列計算其成為最終排序序列的概率，WT-INDEG算法通過計算每種可能排序序列的交叉熵得到最優的排序結果.由于上述方法計算開銷巨大，實際中通常采用以前K項排序序列代替完整排序序列的方式來減少計算量，基于神經網絡的ListNet算法僅計算Top-K概率，WT-INDEG算法僅計算Top-K序列的交叉熵.這一過程通常需要N!/(N-K)!次計算，因此當K>2時，基于神經網絡的ListNet算法和WT-INDEG算法的時間復雜度可近似表示為O(N3).在基于多目標優化的演化排序聚合算法中，NPDA算法為了得到在M個優化目標上的最優解，每確定一個最優解的分量都需要對一張M維的增益表進行更新，確定N個數據項的排序信息共需要更新N(N+1)/2次，所以該算法的時間復雜度為O(M×N2)；BHTPSO算法和本文的D3MOPSO算法都是基于粒子群搜索的演化算法，但BHTPSO在每輪迭代的存檔過程中，為了保持解的多樣性，存檔的非支配解數目遠超外部檔案EA的容量(導致EA頻繁更新)，在數量級上接近輸入總量，因此，其時間復雜度為O(M×maxgen×N)，其中maxgen為迭代次數；對本文提出的D3MOPSO算法而言，正如4.2節所分析，在最壞情況下的時間復雜度為O(maxgen×SwarmSize×M)，其中SwarmSize為粒子群大小.在大規模數據環境下，粒子群的大小和迭代次數與海量的待排序數據項規模相比非常小，因此，從時間復雜度的表示來看，D3MOPSO算法要優于上述基于排序學習的算法以及基于多目標優化的NPDA，BHTPSO算法.本文的實驗結果也證實了上述分析結論.圖4展現了各排序聚合算法在4個不同數據集上的執行效率比較結果.

容易看出，在數據源數目較少的排序學習數據集和真實網絡數據集上，基于無監督學習的ANN和WT-INDEG算法的耗時都非常少，執行效率總體上高于基于演化的D3MOPSO，NPDA和BHTPSO算法.這是由于2方面原因造成的：1)基于機器學習模型的排序聚合方法單次迭代處理排序向量的能力強、耗時少，相比多目標優化方法具有天然優勢，因而總的執行效率更高.2)基于排序學習的模型的訓練過程的開銷與輸入的數據量正相關，當輸入的數據規模較小時，訓練過程可以在較短的時間內完成，能迅速使模型適應對當前規模數據項集合重新排序的問題，而基于多目標優化的演化方法則無法從同類型問題的訓練過程中獲得性能優勢.綜合看來，當涉及的數據源較少時，基于演化的排序聚合算法在執行效率上普遍不及排序學習模型.其中，D3MOPSO算法的執行時間要略優于NPDA和BHTPSO這2種同樣基于演化的方法，處于中等水平.

當排序聚合涉及到數據源數量明顯增多時，如在本實驗中的綜合仿真數據集和擴展真實數據集上，增加的數據源和增多的數據項使得輸入規模增加，基于排序學習的ANN和WT-INDEG算法所需的訓練時間急劇增長，導致運行時間開銷驟增.但基于多目標優化的D3MOPSO，NPDA和BHTPSO等演化算法由于其搜索解空間的方法的靈活性和敏捷性，排序聚合速度相對較快，算法的執行時間增長幅度與其數據規模的增長相比較為平緩，所以比排序學習方法的運行時間明顯更短.

在基于演化的3種方法之中，D3MOPSO算法的運行效率高于NPDA和BHTPSO算法，且在數據源數目多、規模大時較為明顯，如圖5所示.圖5中n表示數據源數量，m表示數據源規模.

Fig.5 Convergence time comparison of evolutionary algorithms on datasets of different sizes圖5 基于演化的算法在不同規模數據集上收斂時間對比

可以看出，在排序聚合規模較大的綜合仿真數據集和擴展真實數據集上，D3MOPSO算法的收斂速度最快，明顯耗時更短.這是由于D3MOPSO算法在迭代步長上比一般演化算法有所改進，同時也優化了迭代過程中粒子速度的變化策略和迭代結束時的存檔策略，因此，單次迭代的效率較高，存檔更新速度加快，整個算法的收斂性得以提升.

綜上所述，當排序聚合涉及到的數據源規模極大時，D3MOPSO算法是一種效率較為穩定的快速搜索最優解的方法.

6 總 結

用戶對元搜索結果的多維度需求和個性化質量偏好使得元搜索排序聚合成為一個多目標優化問題，然而，傳統的離散多目標優化算法缺乏從數據項到粒子的映射方法，導致其無法直接應用于排序聚合過程中.為此，本文提出了一種名為D3MOPSO的多策略演化算法，通過重新定義粒子的位置、速度與支配關系，引入速度變化因子，優化粒子群的初始化、演化和融合機制，設計新的種群更新、存檔更新策略和引導微粒選取策略，改進了傳統的離散多目標粒子群優化算法，并結合用戶自定義的對元搜索結果的質量偏好縮小了解空間，優化了粒子群的搜索路徑，使元搜索引擎能夠快速地從海量數據源中的數據項中聚合得到符合用戶質量偏好的最佳排序結果.實驗結果表明:當數據規模極大時，D3MOPSO算法的排序效率要遠遠高于其他排序聚合算法，是一種穩定、高效的大規模元搜索排序聚合演化算法.

[1] Desarkar M S, Sarkar S, Mitra P. Preference relations based unsupervised rank aggregation for metasearch[J]. Expert Systems with Applications, 2016, 49(C): 86-98

[2] Ozdemiray A M, Altingovde I S. Explicit search result diversification using score and rank aggregation methods[J]. Journal of the Association for Information Science and Technology, 2015, 66(6): 1212-1228

[3] Ali R, Naim I. User feedback based metasearching using neural network[J]. International Journal of Machine Learning and Cybernetics, 2015, 6(2): 265-275

[4] Li Lin, Xu Guangdong, Zhang Yanchun, et al. Random walk based rank aggregation to improving Web search[J]. Knowledge-Based Systems, 2011, 24(7): 943-951

[5] Keyhanipour A H, Moshiri B, Kazemian M, et al. Aggregation of Web search engines based on users’ preferences in Web Fusion[J]. Knowledge-Based Systems, 2007, 20(4): 321-328

[6] Amin G R, Sadeghi A E H. Metasearch information fusion using linear programming[J]. RAIRO-Operations Research, 2012, 46(4): 289-303[7]Meng Weiyi, Wu Zonghuan, Yu C, et al. A highly scalable and effective method for metasearch[J]. ACM Trans on Information Systems, 2001, 19(3): 310-335

[8] Amin G R, Emrouznejad A. Optimizing search engines results using linear programming[J]. Expert Systems with Applications, 2011, 38(9): 11534-11537

[9] Dwork C, Kumar R, Naor M, et al. Rank aggregation methods for the Web[C] //Proc of the 10th Int Conf on World Wide Web. New York: ACM, 2001: 613-622

[10] Coppersmith D, Fleischer L K, Rurda A. Ordering by weighted number of wins gives a good ranking for weighted tournaments[C] //Proc of the 17th Annual ACM-SIAM Symp on Discrete Algorithm. New York: ACM, 2006: 776-782

[11] Montague M, Aslam J A. Condorcet fusion for improved retrieval[C] //Proc of the 11th Int Conf on Information and Knowledge Management. New York: ACM, 2002: 538-548

[12] Wu Shengli, Li Jieyu, Zeng Xiaoqin, et al. Adaptive data fusion methods in information retrieval[J]. Journal of the Association for Information Science and Technology, 2014, 65(10): 2048-2061

[13] Klementiev A, Roth D, Small K, et al. Unsupervised rank aggregation with domain-specific expertise[C] //Proc of the 21st Int Joint Conf on Artificial Intelligence. New York: ACM, 2009: 1101-1106

[14] Qin Tao, Geng Xiubo, Liu Tieyan. A new probabilistic model for rank aggregation[J]. Advances in Neural Information Processing Systems, 2010, 23(1): 1948-1956

[15] Wang Yang, Huang Yalou, Pang Xiaodong, et al. Supervised rank aggregation based on query similarity for document retrieval[J]. Soft Computing, 2013, 17(3): 421-429

[16] Chen Yiwei, Hofmann K. Online learning to rank: Absolute vs relative[C] //Proc of the 24th Int Conf on World Wide Web. New York: ACM, 2015: 19-20

[17] Keyhanipour A H, Moshiri B, Rahgozar M. CF-Rank: Learning to rank by classifier fusion on click-through data[J]. Expert Systems with Applications, 2015, 42(22): 8597-8608

[18] Attiya G, Hamam Y. Task allocation for maximizing reliability of distributed systems: A simulated annealing approach[J]. Journal of Parallel & Distributed Computing, 2006, 66(10): 1259-1266

[19] Falzon G, Li Maozhen. Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments[J]. The Journal of Supercomputing, 2012, 59(1): 104-130

[20] Moradi P, Rostami M. Integration of graph clustering with ant colony optimization for feature selection[J]. Knowledge-Based Systems, 2015, 84(C): 144-161

[21] Carrasco R, Trinh A P, Gallego M, et al. Tabu search for the Max-Mean dispersion problem[J]. Knowledge-Based Systems, 2015, 85(C): 256-264

[22] Wang Lizhe, Geng Hao, Liu Peng, et al. Particle swarm optimization based dictionary learning for remote sensing big data[J]. Knowledge-Based Systems, 2015, 79(C): 43-50

[23] Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm[C] //Proc of the 27th IEEE Int Conf on Systems, Man and Cybernetics. Piscataway, NJ: IEEE, 1997: 4104-4108

[24] Sha D Y, Hsu C Y. A hybrid particle swarm optimization for job shop scheduling problem[J]. Computers and Industrial Engineering, 2006, 51(4): 791-808

[25] Tang Kezong, Liu Bingxiang, Yang Jingyu, et al. Double center particle swarm optimization algorithm[J]. Journal of Computer Research and Development, 2012, 49(5): 1086-1094 (in Chinese)(湯可宗, 柳炳祥, 楊靜宇, 等. 雙中心粒子群優化算法[J]. 計算機研究與發展, 2012, 49(5): 1086-1094)

[26] Chen Weineng, Zhang Jun, Chung H S H, et al. A novel set-based particle swarm optimization method for discrete optimization problems[J]. IEEE Trans on Evolutionary Computation, 2010, 14(2): 278-300

[27] Abraham A, Liu Hongbo, Zhang Weishi, et al. Scheduling jobs on computational grids using fuzzy particle swarm algorithm[C] //Proc of the 10th Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer, 2006: 500-507

[28] Izakian H, Ladani B T, Zamanifar K, et al. A novel particle swarm optimization approach for grid job scheduling[J]. Communications in Computer & Information Science, 2010, 31(9): 100-109

[29] Ma Chao, Deng Chao, Xiong Yao, et al. An intelligent optimization algorithm based on hybrid of GA and PSO[J]. Journal of Computer Research and Development, 2013, 50(11): 2278-2286 (in Chinese)(馬超, 鄧超, 熊堯, 等. 一種基于混合遺傳和粒子群的智能優化算法[J]. 計算機研究與發展, 2013, 50(11): 2278-2286)

[30] Yu Wei, Li Shijun, Yang Sha, et al. Automatically discovering of inconsistency among cross-source data based on Web big data[J]. Journal of Computer Research and Development, 2015, 52(2): 295-308 (in Chinese)(余偉, 李石君, 楊莎, 等. Web大數據環境下的不一致跨源數據發現[J]. 計算機研究與發展, 2015, 52(2): 295-308)

[31] Nejat A, Mirzabeygi P, Panahi M S. Airfoil shape optimization using improved multi-objective territorial particle swarm algorithm with the objective of improving stall characteristics[J]. Structural & Multidisciplinary Optimization, 2013, 49(6): 1-15

[32] De-La-Torre M, Granger E, Sabourin R, et al. An adaptive ensemble-based system for face recognition in person re-identification[J]. Machine Vision and Applications, 2015, 26(6): 741-773

[33] Ahmadi A. Memory-based adaptive partitioning (MAP) of search space for the enhancement of convergence in Pareto-based multi-objective evolutionary algorithms[J]. Applied Soft Computing, 2016, 41: 400-417

[34] Zhang Xianchao, Xu Wen, Gao Liang, et al. Combining content and link analysis for local Web community extraction[J]. Journal of Computer Research and Development, 2012, 49(11): 2352-2358 (in Chinese)(張憲超, 徐雯, 高亮, 等. 一種結合文本和鏈接分析的局部Web社區識別技術[J]. 計算機研究與發展, 2012, 49(11): 2352-2358)

[35] Mostaghim S, Teich J. Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO)[C] //Proc of the 2003 Swarm Intelligence Symp. Piscataway, NJ: IEEE, 2003: 26-33

[36] Villalobos-Arias M A, Pulido G T, Coello C A C. A proposal to use stripes to maintain diversity in a multi-objective particle swarm optimizer[C] //Proc of the 2005 Swarm Intelligence Symp. Piscataway, NJ: IEEE, 2005: 22-29

[37] Ali R, Naim I. User feedback based metasearching using neural network[J]. International Journal of Machine Learning and Cybernetics, 2015, 6(2): 265-275

[38] Desarkar M S, Sarkar S, Mitra P. Preference relations based unsupervised rank aggregation for metasearch[J]. Expert Systems with Applications: An International Journal, 2016, 49(C): 86-98

[39] Kirlik G, Sayn S. Computing the nadir point for multi-objective discrete optimization problems[J]. Journal of Global Optimization, 2015, 62(1): 79-99

[40] Beheshti Z, Shamsuddin S M, Hasan S. Memetic binary particle swarm optimization for discrete optimization problems[J]. Information Sciences, 2015, 299(C): 58-84

[41] Buzaglo S, Etzion T. Bounds on the size of permutation codes with the kendall tau-metric[J]. IEEE Trans on Information Theory, 2015, 61(6): 3241-3250

[42] Clémencon S, Jakubowicz J. Kantorovich distances between rankings with applications to rank aggregation[C] //Proc of the 2010 European Conf on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2010: 248-263

[43] Tavana M, Li Zhaojun, Mobin M, et al. Multi-objective control chart design optimization using NSGA-III and MOPSO enhanced with DEA and TOPSIS[J]. Expert Systems with Applications, 2016, 50: 17-39

[44] Zitzler E, Thiele L. Multi-objective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Trans on Evolutionary Computation, 1999, 3(4): 257-271

D3MOPSO：AnEvolutionaryMethodforMetasearchRankAggregationBasedonUserPreferences

Tang Xiaoyue1, Yu Wei2, and Li Shijun2

1(SchoolofMathematicsandComputerScience,WuhanPolytechnicUniversity,Wuhan430023)2(ComputerSchool,WuhanUniversity,Wuhan430079)

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 (D3MOPSO) 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.

rank aggregation; metasearch; user preference; multi-objective optimization; discrete particle swarm optimization

Tang Xiaoyue, born in 1983. PhD of Wuhan University. Lecturer of Wuhan Polytechnic University. Member of CCF. Her main research interests include Web mining, information retrieval, and artificial intelligence.

Yu Wei, born in 1987. PhD. Lecturer in Computer School of Wuhan University. Member of CCF. His main research interests include Web data ming.

Li Shijun, born in 1964. Professor and PhD supervisor in Computer School of Wuhan University. Member of CCF. His main research interests include data ming (shjli@whu.edu.cn).

2017-03-20；

：2017-06-07

國家自然科學基金項目(61502350)；湖北省教育廳科研計劃項目(Q-20161702) This work was supported by the National Natural Science Foundation of China (61502350) and the Research Program of Hubei Provincial Department of Education (Q-20161702).

余偉(yuwei@whu.edu.cn)

TP391