改進的多目標粒子群優化算法

項鐵銘 王建成

(杭州電子科技大學天線與微波技術研究所 浙江 杭州 310018)

改進的多目標粒子群優化算法

項鐵銘 王建成*

(杭州電子科技大學天線與微波技術研究所 浙江 杭州 310018)

為提高解決多目標優化問題的能力，提出一種改進的多目標粒子群優化算法。該算法采用均勻隨機初始化方法初始種群，采用快速支配策略選取非支配解，生成外部檔案；通過比較粒子連續幾代的更新情況來判斷是否陷入局部最優并相應地采取不同的更新策略，同時引入變異因子對粒子進行擾動。實驗結果表明，在世代距離GD(Generational Distance)和空間評價方法SP(Spacing)性能指標上，改進之后的算法與另外幾種對等算法相比，具有顯著的整體優勢。

外部檔案 均勻初始化 快速支配策略 多目標粒子群優化算法 粒子信息檔案

0 引 言

與單目標問題不同，多目標之間相互關聯并且相互矛盾[1-2,9-10]。解決多目標問題就是要盡可能地找到一組能最大化均衡各個目標的較好的解的集合[3-5]。目前大多數多目標粒子群優化算法只是作用在算法的局部，如側重于非劣解的選取，或者外部檔案的維護等，并沒有對算法進行整體的協同改進，也不能改善算法的整體性能。而且存在著早熟收斂、陷入局部最優等問題，得到的結果集也很難令人滿意。為了解決這些問題，謝承旺等[6]提出了一種多策略融合的算法來改善上述問題，左一多[7]提出了一種快速支配策略來維護外部檔案，Xu等[8]融入了二分查找策略。這些改進后的算法都在某些程度上優化解決了上述提到的問題，但是對于陷入局部最優之后的操作以及多樣性的維護依然存在改進的空間。本文結合文獻[6-8]的優點，提出了一種改進的多目標粒子群優化算法(IMOPSO)。本文改進算法提出了一種全新的更新策略，旨在結合粒子信息檔案中粒子連續幾代的更新狀況，采用不同的更新策略，從而對粒子的更新作出更加高效的指導和優化，提高算法解決復雜MOP問題時的整體性能。

1 改進的多目標粒子群優化算法

1.1 種群初始化策略

為了保證初始化的多樣性，本文使用均勻隨機初始化方法，最大程度上保證初始群體的隨機性和多樣性。

1.2 檔案更新策略

對于超出檔案的解集，如果該解集大小超出檔案限定值，則根據限定值大小選取粒子保存到臨時檔案中用于下一次迭代的檔案更新；如果解集大小不足限定值，則將該解集全部存入臨時檔案中，參與下一次迭代時的檔案更新。這樣可以更好地實現粒子的均勻分布。

1.3 粒子更新策略

與現有大部分的MOPSO更新策略不同，本文提出了一種基于粒子個體表現的更新策略，策略如下：

1) 建立額外檔案用于保存粒子的每一代的位置及其適應度值信息。

2) 判斷當前粒子與前兩代相比兩個適應度值在每一代的變化。

3) 引用擾動概率P來平衡粒子的收斂速度與勘探開采能力。

本文采用的擾動概率P更新策略如下：

(1)

其中，r為當前迭代次數，Tmax為最大迭代次數，NN為外部檔案的定義規模，Nrep為當前迭代次數下外部檔案中的粒子數目，gen為達到外部檔案定義的規模時的迭代次數。

開始時，外部種群為空，擾動概率很高，高概率將導致高的探索能力，同時降低了粒子收斂于局部最優的可能性。隨著外部種群粒子數的增加，概率開始下降，當外部種群的實際大小達到其最大規模的一半時，擾動概率接近為0，使得粒子群有足夠的時間根據自身的知識和社會行為發現新的區域，更好地探索新的區域，再之后擾動概率又開始上升。當外部種群被充滿之后，擾動概率隨著迭代次數的增加逐漸降低，使粒子向真實地Pareto前端靠攏。

4) 若粒子迭代次數超過4次，則開始比較連續3代的適應度值，若其連續3代適應度值基本保持不變并且rand

xid=wvid+c1rand(gbest-Tn)

(2)

其中rand為0到1之間的隨機數，gbest為從全局最優解集的前20%中隨機挑選的解，Tn為粒子信息檔案,n=r%5,r為當前迭代次數。

5) 若不滿足4)中的條件則采用如下策略更新粒子的速度和位置(更新策略1)。

Vid=WVid+C1r1(pid-Xid)+C2r2(pgd-Xid)

(3)

Xid=Xid+Vid

(4)

其中W為慣性權重，c1和c2為學習因子。

1.4 算法流程

本文采用的多目標粒子群優化算法的步驟為：

1) 根據1.1節的策略，初始化種群。

2) 計算各粒子的適應度值并根據支配關系形成非支配解集。

3) 更新外部檔案集。

4) 按粒子間的擁擠距離對外部檔案中的粒子進行降序排列，根據1.2節的策略進行檔案維護。

5) 更新個體最優 ，若是第一代則直接將每個粒子初始位置設為，否則根據Pareto支配關系進行更新。

6) 從外部檔案的前20%個非支配解集中隨機選取一個全局最優位置。

7) 根據1.3節的策略來更新粒子的位置和速度。若粒子的速度vi>vmax則令vi=-vmax×rand；若粒子速度vi

8) 更新新一代的位置，若粒子的位置xi>xmax則令xi=xmax；若粒子位置xi

9) 根據當前迭代次數將各粒子存入不同的檔案Tn中。

10) 檢查是否達到最大迭代次數，如果達到，則終止程序；如果未達到，則繼續從第二步開始循環。

改進的多目標粒子群優化算法流程圖如圖1所示。

圖1 算法流程圖

2 實驗結果分析

本文選取了幾種對等的優化算法進行比較,本文采用世代距離GD來評價算法的收斂性，采用空間評價方法SP來評價解集的分布性。定義公式如下：

(5)

(6)

GD值越小，說明算法的收斂性越好,SP值越小，說明得到的解的分布性越好。

本文測試函數為ZDT系列。該系列測試函數為雙目標函數，ZDT1～4的Pareto前沿特征分別為二維連續凸函數，二維連續凹函數，不連續函數，凸函數。

各算法的種群規模均設為N=100，全局外部檔案的最大容量均設為NN=100，所有算法的最大迭代次數Tmax=500，每種算法在所有的測試函數上均獨立運行30次。

圖2-圖5為IMOPSO、CMOPSO、NSGA-II三種算法在四個測試函數上的仿真結果。

圖2 三種算法對ZDT1函數求解的Pareto分布

圖3 三種算法對ZDT2函數求解的Pareto分布

圖4 三種算法對ZDT3函數求解的Pareto分布

圖5 三種算法對ZDT4函數求解的Pareto分布

從圖2-圖5來看，IMOPSO算法與其他算法相比，無論是在求解數量、解集的逼近性以及分布性上都有較大的優越性。

表1列出了4個對等比較算法在4個測試問題上的GD性能指標, 這些值是同一算法在同一測試問題上獨立運行30次的統計結果。其中比較算法結果數據來源于文獻[6]。

表1 4種對等算法在4個測試實例上的GD性能對比結果

從表1可以看出，IMOPSO在4個測試問題中獲得了3個最優的GD值，MOED/A算法獲得一個最優的GD值。GD性能能夠反映算法的收斂性，因此，從收斂角度來看，IMOPSO的表現較為突出。

表2給出了4種對等比較算法在4個多目標測試問題上的SP性能的對比結果。

表2 4種對等算法在4個測試實例上的SP性能對比結果

從表3可以看出，IMOPSO在4個測試函數上獲得了4個最優的SP值。總體上來說，本文算法具有不錯的SP性能。

綜上所述，IMOPSO算法在所有測試函數中獲得了最好的收斂性和多樣性的折中效果，表明了本文改進之后的方法能夠很好地均衡算法的進化過程，并在復雜多目標優化測試問題中取得了明顯的效果。

3 結 語

本文通過結合文獻[6-7]的優點，完善粒子的更新策略，提出了一種改進的多目標優化算法，并與一些算法進行了比較分析。通過對實驗結果的分析可以看出，在求解多目標的問題上，改進后的算法相對于其他算法，能夠更精確地收斂到標準測試函數的真實Pareto前端。并且，也能夠維持好的解的分布性。

[1] 江勛林,郭堅毅,唐建,等.一種基于模糊學習子群的多目標粒子群算法[J].計算機應用研究,2011,28(12):4492-4494.

[2] Agrawal S,Dashora Y,Tiwari M K,et al.Interactive Particle Swarm:A Pareto-Adaptive Metaheuristic to Multiobjective Optimization[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2008,38(2):258-277.

[3] Lin Q,Li J,Du Z,et al.A novel multi-objective particle swarm optimization with multiple search strategies[J].European Journal of Operational Research,2015,247(3):732-744.

[4] Srivastava L,Singh H.Hybrid multi-swarm particle swarm optimisation based multi-objective reactive power dispatch[J].Generation Transmission & Distribution Iet,2015,9(8):727-739.

[5] Zhang Y,Gong D W,Zhang W Q.Feature selection of unreliable data using an improved multi-objective PSO algorithm[J].Neurocomputing,2016,171(C):1281-1290.

[6] 謝承旺,鄒秀芬,夏學文,等.一種多策略融合的多目標粒子群優化算法[J].電子學報,2015,43(8):1538-1544.

[7] 左一多.多目標優化問題的粒子群算法及其性能分析[D].北京:中國地質大學,2013.

[8] Xu G,Yang Y Q,Liu B B,et al.An efficient hybrid multi-objective particle swarm optimization with a multi-objective dichotomy line search[J].Journal of Computational & Applied Mathematics,2015,280(C):310-326.

[9] Clarke J,Jr M L.Multi-objective particle swarm optimization of binary geothermal power plants[J].Applied Energy,2015,138:302-314.

[10] Liu H L,Gu F,Zhang Q.Decomposition of a Multiobjective Optimization Problem Into a Number of Simple Multiobjective Subproblems[J].IEEE Transactions on Evolutionary Computation,2014,18(3):450-455.

ANIMPROVEDMULTI-OBJECTIVEPARTICLESWARMOPTIMIZATIONALGORITHM

Xiang Tieming Wang Jiancheng*

(InstituteofAntennaandMicrowaves,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

In order to improve the ability to solve the problem of multi-objective optimization (MOPSO), an improved multi-objective particle swarm optimization algorithm (IMOPSO) is proposed. Using IMSPSO, initial population was produced by a uniformly random initialization approach, and non-dominated solutions were selected by fast control strategy to generate the external archive. By comparing the successive generations of particles, we could judge whether they felled into local optima and adopted different updating strategies. At the same time, a disturbance item was added to the particle’s updating. The experimental results show that the proposed algorithm significantly surpasses other algorithms in terms of GD(Generational Distance), SP(Spacing).

External archive Uniform and random initialization Fast control strategy MOPSO Particle information archive

TP181

A

10.3969/j.issn.1000-386x.2017.09.059

2016-11-09。項鐵銘，副教授，主研領域：智能優化算法，多目標優化，現代天線設計。王建成，碩士生。