基于參考點的多模態多目標粒子群算法

李國森 閆 李* 郭倩倩 周同馳 王永林 岳彩通

1(中原工學院電子信息學院 河南 鄭州 450007) 2(鄭州大學電氣工程學院 河南 鄭州 450001) 3(鄭州大學產業技術研究院 河南 鄭州 450001)

0 引 言

在實際工程應用中，往往存在多個目標相互沖突的多目標優化問題[1]。由于目標之間的沖突性，這類問題不存在多個目標同時最優的唯一解，而是存在一組互不占優的折衷解，稱為Pareto最優解集(Pareto-optimal Set,PS)[2]。近年來，許多解決多目標問題的優化算法被相繼提出[3]，如NSGA-II[4]、PESA-II[5]、SPEA2[6]和MOEA/D[7]等。這些算法得到的Pareto最優解集在目標空間映射后得到的Pareto前沿(Pareto Front,PF)分布均勻且收斂[8-9]。

在多目標優化問題中，存在一類問題具有多模態的特性，如路徑規劃問題[10]、背包問題[11]、火箭發動機設計問題[12]和作業車間調度問題[13]。這些問題存在著多個不同的Pareto解集，對應著目標空間中的同一個Pareto前沿[14]，被稱為多模態多目標優化問題。如何設計多模態多目標算法使其能夠獲得多個不同的Pareto解集是解決這類問題的關鍵。多個Pareto解集有利于決策者根據自己的喜好選擇合適的解決方案。

多模態多目標優化問題在提出之后，逐漸獲得研究學者的關注。Deb等[14]提出了Omni-optimizer算法，將決策空間中擁擠距離的概念引入到非支配排序方法中以提高解在決策空間中的多樣性。Liang等[16]提出了DN-NSGAII算法，采用基于決策空間的非支配排序算法以改善解在決策空間中的分布。Yue等[10]采用基于環形拓撲的小生境方法，并將特殊擁擠距離嵌入到非支配排序方法中以獲得更多的Pareto解。Liu等[11]利用雙檔案機制和重組策略指導種群進化，提高種群的多樣性和收斂性。Liang等[17]采用自組織映射網絡在決策空間中建立鄰域關系，并采用精英學習策略避免算法收斂過快。

但是上述研究在解決多模態多目標問題時仍然存在Pareto解集不完整、收斂性較差等問題，本文以多目標粒子群算法(Multi-objective Particle Swarm Optimization, MOPSO)[18]為框架，提出了一種基于參考點的多模態多目標粒子群算法(RPMOPSO)。通過引入參考點策略以提高種群多樣性，并采用擴散機制找到更多的Pareto解。利用十二個測試函數，將RPMOPSO與其他六種算法進行性能比較，結果表明RPMOPSO在尋優性能和收斂性上表現良好。

1 基本概念

1.1 多模態多目標優化問題

如果多目標問題在決策空間中存在多個Pareto解集，且這些解集映射到目標空間中同一Pareto前沿，則稱為多模態多目標優化問題(multimodal multi-objective optimization problems,MMOPs)[10]。該優化問題如圖1所示，決策空間中Pareto解集PS1、PS2對應著目標空間中相同的PF。例如，A1和A2在決策空間中的位置不同，但對應目標空間中相同的點A′。找到A1和A2這兩個解，可以給決策者不同的選擇方案。

圖1 多模態多目標優化問題

1.2 粒子群算法描述

設種群規模為N的種群，在一個D維的決策空間中進行尋優。在t時刻，第i個粒子在其個體最優位置pi(t)和全局最優位置gi(t)的引導下從當前位置xi(t)以速度vi(t)飛行[19-20]，則該粒子在(t+1)時刻的速度vi(t+1)和位置xi(t+1)可表示為：

vi(t+1)=wvi(t)+c1r1(pi(t)-xi(t))+

c2r2(gi(t)-xi(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

式中：w為慣性權重；c1和c2為學習因子；r1和r2為區間[0,1]上的隨機數。

隨后為了進一步控制粒子的飛行速度，將壓縮因子χ引入粒子的速度公式[21]，表示如下：

vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+

c2r2(gi(t)-xi(t)))

(3)

(4)

2 算法設計

2.1 參考點策略

在傳統粒子群算法中，每個粒子采用共享的全局最優信息更新自身的位置，以促使種群快速收斂，但在一定程度上降低了解的多樣性。

圖2 參考點策略示意圖

因此，在粒子進行速度更新時，式(3)重新定義為：

vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+

c2r2(o*-xi(t)))

(5)

2.2 擴散機制

本文采用擴散機制，以幫助粒子跳出局部最優。一方面，傳統粒子群算法存在早熟停滯或者陷入局部最優的問題；另一方面，如果過多的粒子在某一次迭代中選擇同一參考點，將導致這些粒子聚集在同一最優解附近，從而過度開發某一區域，而難以找到更多最優解。因此，擴散機制的基本思想是改變這些粒子的飛行軌跡，將其擴散到更大的區域，使其有機會選擇新的參考點。

(pi(t)-xi(t))

(6)

式中：Levy(λ)是服從參數λ(1<λ≤3)的Levy分布的隨機數；‖pi(t)-xi(t)‖表示pi(t)和xi(t)之間的距離。在式(6)中，一方面，Levy分布具有長距離和短距離跳躍相間的特性[24-25]。其長跳躍的搜索方式有利于全局探索，且不容易陷入局部停滯；另一方面，粒子根據歷史最優位置和當前位置的距離動態調整搜索范圍，以提高算法的全局勘探能力。當pi(t)和xi(t)距離很近時，粒子的搜索范圍將變得很大，以搜索到更多的解；反之，粒子不會立即收斂到最優解，避免陷入局部最優。

2.3 算法步驟

步驟1設置算法的種群大小N、學習因子(c1、c2)、最大迭代次數MaxIter，根據佳點集原理初始化種群P，外部檔案EXA=P，參考點RP=P，參考點用于保留最優解的檔案RPA=P。

步驟2計算第j個(j=1,2,…,N)參考點被所有粒子選擇的次數為φj。

步驟3對于第i個(i=1,2,…,N)粒子P{i}，計算該粒子離參考點最近的點(記為RP{j})，則參考點RP{j}所保留的最優信息o*為RPA{j}。根據式(5)計算粒子的速度，然后根據式(2)計算粒子的位置。

步驟5對于第j個參考點RP{j}，計算種群中離其最近的粒子，將該粒子與該參考點保留的最優解RPA{j}進行比較，保留一個非支配解進入檔案RPA{j}。

步驟6更新外部檔案EXA=[P;EXA]，對外部檔案進行非支配排序，選擇占優性強且稀疏的前N個解存入EXA。

步驟7若迭代次數達到最大迭代次數MaxIter，輸出外部檔案；否則，返回步驟2。

3 實 驗

3.1 測試函數

本文采用12個經典的多模態多目標測試函數[10]，包括MMF1-MMF8、SYM-PART simple、SYM-PART rotate、SYM-PART rot.+ trans. 和Omni-test函數(D=3)。其中，Omni-test函數在決策空間中的Pareto解集個數最多，用來測試算法在目標空間的尋優能力。

3.2 實驗設置

使用六種優化算法與RPMOPSO進行比較，包括三種多模態多目標算法(MO_Ring_PSO_SCD[10]、Omni-optimizer[9]和DN-NSGAII[16])和三種多目標算法(NSGA-II、PESA-II和MOEA/D)。其中，RPMOPSO參數如下：c1=c2=2.05。其他算法的參數值與相應文獻中的參數值相同。所有算法的種群大小N和最大迭代次數MaxIter分別設置為800和100[10]，外部歸檔大小設置為800，獨立運行25次。采用MATLAB R2014b進行仿真，運行環境為Intel? CoreTMI7-4790處理器，內存為16 GB。

3.3 評價指標

本文采用Pareto解集近似性(PSP)[10]和超體積(Hv)[26]指標衡量算法性能。PSP用于度量所獲得PS的收斂性和分布性。Hv用于評價所獲得PF的收斂性和分布性。PSP值越大意味著在決策空間中獲得的PS的收斂性和多樣性越好。Hv值越大意味著在目標空間中獲得的PF越接近真實的PF。

3.4 實驗結果

3.4.1策略性能對比

為了驗證所提策略在解決多模態多目標問題時的有效性，將RPMOPSO算法和MOPSO[10]、RPMOPSO-I(采用參考點策略的MOPSO算法)和RPMOPSO-II(采用擴散機制的MOPSO算法)進行比較。表1所示為結合不同策略的算法的PSP的均值、標準差，以及Wilcoxon秩和檢驗的h值。

表1 各策略PSP指標統計

可以看出，RPMOPSO-I的性能優于MOPSO，而RPMOPSO-II的性能略優于MOPSO。因此，參考點策略和擴散機制能有效地改善基本MOPSO的性能。此外，秩和檢驗的結果表明，兩種策略的結合能夠使算法性能得到顯著的提升。其原因在于參考點策略使RPMOPSO能夠找到更多的Pareto最優解。參考點策略可以在決策空間中產生穩定的小生境，每個粒子在自己的小生境鄰域內進化，且不會受其他鄰域的影響，以提高種群的多樣性。擴散機制能夠使粒子向更大的范圍內尋優，因此陷入局部最優的粒子不僅可以跳出當前的最優解，而且可以捕捉到更多的最優解。

3.4.2算法性能對比

本節將RPMOPSO與三種多模態多目標算法和三種多目標算法進行比較。首先，比較不同算法在決策空間獲得PS的能力，不同算法的PSP值如表2所示。結果表明RPMOPSO在所有測試函數中具有較好的表現，其性能優于其他六種算法。MO_Ring_PSO_SCD排第二名，因其使用環形拓撲能夠形成小生境，能夠找到更多Pareto解。DN-NSGAII和Omni-optimizer的表現緊隨其后，兩者采用決策空間的擁擠距離作為環境選擇提高了算法的性能。NSGA-II、MOEA/D和PESA-II表現較差，其原因在于這三種多目標算法沒有考慮決策空間中解的分布。其次，評價算法在目標空間中獲得的PF的性能，不同算法的Hv值如表3所示。可以看出RPMOPSO在Hv性能指標上表現不是最好的。實際上，所有算法在同一個測試函數上的Hv值是很接近的。原因是所有的算法都考慮了最優解在目標空間中的分布。

表2 不同算法PSP指標統計

表3 不同算法Hv指標統計

為了進一步比較算法的性能，將所有算法在Omni-test測試函數上獲得的PS和PF分別在圖3、圖4進行展示。Omni-test測試函數有27個PS。從圖3可以看出，RPMOPSO獲得的Pareto最優解能夠比較全面地覆蓋真正的PS。MO_Ring_PSO_SCD、DN-NSGAII和Omni-optimizer獲得的PS并不完整。NSGA-II、PESA-II和MOEA/D搜索到的PS更少。其中，MOEA/D僅獲得一個PS。這說明沒有小生境技術很難維持多個PS。從圖4可以看出，所有算法在Omni-test測試函數上都能夠較好的覆蓋整個真實的PF，且能夠逼近真正的PF。

圖3 各算法所獲得的PS對比

圖4 各算法所獲得的PF對比

綜上，在獲得近似PF的前提下，RPMOPSO在決策空間中獲得的PS分布性良好。

3.4.3算法收斂性比較

為了比較算法的收斂性[10]，將四個多模態多目標算法(RPMOPSO，MO_Ring_PSO_SCD，Omni-optimizer和DN-NSGAII)在測試函數MMF4上進行比較。MMF4在決策空間上有4個PS，如圖5所示，其PS的分布將決策空間劃分為4個子區域，分別為區域1、區域2、區域3和區域4。這樣每個子區域面積相等，且每個子區域均有一個PS。算法的收斂性可以定義為每一代種群分布在每個子區域中解的比例[10]。在理想的情況下，如果算法在測試函數MMF4上收斂性很好，那么每個子區域中解的比例應等于25%。

圖5 測試函數MMF4的PS分布

圖6為算法迭代過程中，在每個子區域中解的比例變化曲線。從圖6(a)中可以看出，本文算法中的區域1、區域2所在的曲線隨迭代次數增加而逐漸上升，而區域3、區域4所在的曲線呈下降趨勢。在迭代次數接近50時，四個區域的解的比例趨于25%。在第80代至第100代時，每個區域的解的比例基本上接近25%。這說明RPMOPSO具有良好的收斂性。對于MO_Ring_PSO_SCD，圖6(b)中每個區域的解的比例最終能夠收斂到25%左右，但是區域1、區域2的解的比例略大于區域3、區域4的解的比例，這說明其收斂性略差于RPMOPSO。對于DN-NSGAII，在第30代以后，區域1、區域4的解的比例遠低于區域2、區域3的解的比例。對于Omni-optimizer，在第45代以后，區域2、區域3的解的比例低于區域1、區域4的解的比例。在圖6(c)、(d)中，每個區域曲線的變化趨勢為頻繁震蕩，并不穩定。這說明DN-NSGAII和Omni-optimizer算法表現出很差的收斂性。

圖6 算法的收斂性對比

可以看出，RPMOPSO在收斂性上具有良好的性能。

4 結 語

本文提出了一種基于參考點的多模態多目標粒子群算法(RPMOPSO)。采用了參考點策略和擴散機制，參考點策略的引入促使種群形成若干小生境，每個粒子在它的小生境鄰域內獨立進化，以提高種群的多樣性。擴散機制能夠改變粒子的飛行軌跡，擴散粒子到更大的搜索區域，極大地提高了粒子捕捉到更多Pareto解的可能性。通過和多模態多目標算法及多目標優化算法的比較，證明了RPMOPSO能夠找到更多的Pareto解，且具有很好的收斂性。未來將嘗試把算法應用于求解實際中的多模態多目標問題。