基于定期競爭學習的多目標粒子群優化算法

劉明 董明剛 敬超

摘 要：為提高種群的多樣性和算法的收斂性，提出一種基于定期競爭學習機制的多目標粒子群算法。該算法將多目標粒子群算法和競爭學習機制相結合，即每隔一定迭代代數便使用一次競爭學習機制，很好地保持了種群的多樣性;同時，該算法不需要全局最優粒子的外部存檔，而是從當前代種群中選取一部分優秀的粒子，再從這些優秀的粒子中隨機選取一個作為全局最優粒子，能夠有效提升算法的收斂性。將提出的算法與基于分解的多目標粒子群算法（MPSOD）、基于競爭機制且快速收斂的多目標粒子群（CMOPSO）算法、參考向量引導的多目標進化算法（RVEA）等8個算法在21個標準測試函數上進行了比較，結果表明，所提算法的帕累托（Pareto）前沿更加均勻，在世代距離（IGD）上會更加小。

關鍵詞：多目標優化;粒子群優化;定期競爭;競爭學習機制;全局最優選取策略

中圖分類號： TP183; TP301.6

文獻標志碼：A

Abstract： In order to improve the diversity of population and the convergence performance of algorithm， a Scheduled competition learning based Multi-Objective Particle Swarm Optimization （SMOPSO） algorithm was proposed. The multi-objective particle swarm optimization algorithm and the competition learning mechanism were combined and the competition learning mechanism was used in every certain iterations to maintain the diversity of the population. Meanwhile， to improve the convergence of algorithm without using the global best external archive， the elite particles were selected from the current swarm， and then a global best particle was randomly selected from these elite particles. The performance of the proposed algorithm was verified on 21 benchmarks and compared with 8 algorithms， such as Multi-objective Particle Swarm Optimization algorithm based on Decomposition （MPSOD）， Competitive Mechanism based multi-Objective Particle Swarm Optimizer （CMOPSO） and Reference Vector guided Evolutionary Algorithm （RVEA）. The experimental results prove that the proposed algorithm can get a more uniform Pareto front and a smaller Inverted Generational Distance （IGD）.

Key words： multi-objective optimization; Particle Swarm Optimization （PSO）; scheduled competition; competitive learning mechanism; global best selection strategy

0 引言

現實生活中普遍存在的優化問題都可以歸結為多目標優化問題，而解決多目標優化問題的一個有效途徑就是進化算法，常見的多目標進化算法有帶精英策略的快速非支配排序遺傳算法 （Non-dominated Sort Genetic Algorithm II， NSGAII）[1]、提升Pareto前沿的進化算法 （Strength Pareto Evolutionary Algorithm， SPEA2）[2]、基于分解的多目標進化算法（MultiObjective Evolutionary Algorithm based on Decomposition， MOEAD）[3]。粒子群優化（Particle Swarm Optimization， PSO）算法[4]也屬于進化算法之一，最初用來解決單目標優化問題，由于其具有實現簡單、計算成本低、效率高等優點，如今也被廣泛應用到多目標問題優化上，因此，大量的多目標粒子群算法被提出。

在多目標粒子群算法中，種群的多樣性和算法的收斂性是影響算法性能的兩個關鍵因素[5]。為了提高算法的收斂性，Hu等[5]提出了基于并行網格坐標系的自適應多目標粒子群算法，通過平行單元坐標系統反饋回來的信息來進行動態調整，很好地提升了算法的收斂性。Zhang等[6]提出了一種基于競爭機制[7]的多目標粒子群（Competitive Mechanism based multi-Objective Particle Swarm Optimizer， CMOPSO）算法，能夠很好地提升算法的收斂性，并且不需要外部存檔，而是在每一代種群中選取10個精英粒子作為全局最優粒子集合，再從10個精英粒子中隨機選取2個精英粒子，運用競爭機制對2個粒子進行比較，選取優勝的粒子作為全局最優粒子來引導種群的進化。韓敏等[8]提出了基于高斯混沌變異和精英學習的自適應多目標粒子群算法，提出了收斂性貢獻這一概念作為自適應參數的依據和精英學習方法，很好地提升了算法的收斂性。為了提升種群的多樣性，Cheng等[9]提出了一個有效的多目標粒子群教與學優化（Particle Swarm Optimization and Teaching-Learning-Based Optimization， PSO-TLBO）算法， 即將粒子群算法和教與學算法結合，主要應用粒子群算法來更新種群，同時每隔一定代數便運用一次教與學算法，能很好地保持種群的多樣性。Balling[10]提出了Maximin策略，該策略能夠自動地“獎勵”分散的解，“懲罰”聚集的解，整體偏向于分布分散的解，能很好地提升種群的多樣性。

綜上所述，學者們在針對多目標粒子群優化算法上取得了大量的優異成果，但多目標粒子群算法由于收斂速度快導致容易陷入局部最優或者早熟這一缺陷仍然沒有得到很好地解決，因此提升種群多樣性與算法收斂性仍然是一個值得研究的領域，故本文提出了一種基于定期競爭學習的多目標粒子群優化（Scheduled competition learning based Multi-Objective Particle Swarm Optimization， SMOPSO） 算法。

本文的主要工作如下：

1） 提出一種定期競爭學習機制，可以很好地提升種群的多樣性。該機制將多目標粒子群算法和競爭學習機制相結合，每隔一定迭代次數[10]便運用競爭學習機制進行一次種群更新，即把種群中的粒子隨機兩兩配對進行比較，失敗的粒子將向優勝的粒子學習，優勝的粒子則向其保存的個體歷史最優粒子學習，這使得每個粒子都有可能成為全局最優粒子，能很好地提升種群的多樣性。

2） 提出一種新的全局最優粒子的選擇方式，可以很好地提升算法的收斂性。它采用了基于非支配解排序[17]和擁擠距離[1]的共同排序，選取前10個粒子作為精英粒子[9]，然后采取隨機法從精英粒子中隨機選取一個作為全局最優粒子來引導其他粒子的更新。此外，該方法不需要存儲全局最優粒子的外部存檔，能極大地降低算法的時間復雜度。

1 相關工作

1.1 PSO算法

4 結語

為提升種群多樣性和算法的收斂性，本文提出了一種基于定期競爭機制的多目標粒子群算法，它將多目標粒子群算法與競爭學習機制相結合，既考慮到了種群的多樣性，又能兼顧收斂性。首先，利用本文提出的多目標粒子群優化策略，可以很好地提升算法的收斂性，再定期使用競爭學習機制，提升種群的多樣性。并且，該算法不需要存儲全局最優粒子的外部存檔，極大地降低了算法的時間復雜度。經實驗驗證，本文算法能夠在收斂性和多樣性之間取得良好的平衡，很好地提升了算法的性能。

SMOPSO算法的未來研究方向如下：1）隨著社會的發展，多目標優化問題會變得越來越復雜，將該算法向更多目標方向發展是一個很值得研究的領域;2）可以試著引入局部搜索策略，提高算法的收斂精度，以期獲得更好的收斂性，從而進一步提升算法的性能。

致謝：本文算法的實現應用了安徽大學BIMK團隊開發的多目標進化算法PlatEMO開源平臺。對BIMK團隊提供的幫助，在此致以衷心的感謝！

參考文獻：

[1] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multi-objective genetic algorithm： NSGA-II [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）：182-197.

[2] LAUMANNS M. SPEA2： improving the strength Pareto evolutionary algorithm， Technical Report Gloriastrasse 35 [R/OL]. [2018-03-09]. https：//ci.nii.ac.jp/naid/10017663175.

https：//ci.nii.ac.jp/naid/10017663175

[3] ZHANG Q， LI H. MOEA/D： a multiobjective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712-731.

[4] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conferenceon Neural Networks. Piscataway： IEEE， 1995： 1942-1948.

[5] HU W， YEN G G. Adaptive multiobjective particle swarm optimization based on parallel cell coordinate system [J]. IEEE Transactions on Evolutionary Computation， 2015， 19（1）： 1-18.

[6] ZHANG X， ZHENG X， CHENG R， et al. A competitive mechanism based multi-objective particle swarm optimizer with fast convergence [J]. Information Sciences， 2018， 427： 63-76.

[7] CHENG R， JIN Y. A competitive swarm optimizer for large scale optimization [J]. IEEE Transactions on Cybernetics， 2015， 45（2）： 191-204.

[8] 韓敏，何泳.基于高斯混沌變異和精英學習的自適應多目標粒子群算法[J].控制與決策，2016，31（8）：1372-1378. （HAN M， HE Y. Adaptive multi-objective particle swarm optimization with Gaussian chaotic mutation and elite learning [J]. Control and Decision，2016，31（8）：1372-1378.）

[9] CHENG T， CHEN M， FLEMING P J， et al. An effective PSO-TLBO algorithm for multi-objective optimization [C]// Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2016： 3977-3982.

[10] BALLING R. The maximin fitness function， multi-objective city and regional planning [C]// EMO 2003： Proceedings of the 2003 International Conference on Evolutionary Multi-Criterion Optimization， LNCS 2632. Berlin： Springer， 2003： 1-15.

[11] ZHANG X， TIAN Y， CHENG R， et al. An efficient approach to nondominated sorting for evolutionary multiobjective optimization [J]. IEEE Transactions on Evolutionary Computation， 2015， 19（2）： 201-213.

[12] 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.

[13] TIAN Y， CHENG R， ZHANG X， et al. PlatEMO： a Matlab platform for evolutionary multi-objective optimization [Educational Forum][J]. IEEE Computational Intelligence Magazine， 2017， 12（4）： 73-87.

[14] DAI C， WANG Y， YE M. A new multi-objective particle swarm optimization algorithm based on decomposition [J]. Information Sciences — Informatics and Computer Science， Intelligent Systems， Applications： An International Journal， 2015， 325（C）： 541-557.

[15] LIN Q， LIU S， ZHU Q， et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2018， 22（1）： 32-46.

[16] LI M， YANG S， LIU X. Bi-goal evolution for many-objective optimization problems [J]. Artificial Intelligence， 2015， 228： 45-65.

[17] CHENG R， JIN Y， OLHOFER M， et al. A reference vector guided evolutionary algorithm for many-objective optimization [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（5）： 773-791.