孫欣 于慧 王宇嘉 林煒星 梁海娜 陳萬芬

摘 要：針對粒子群算法在處理復(fù)雜優(yōu)化問題時，出現(xiàn)多樣性較差、收斂精度低等問題，提出了基于局部協(xié)同與競爭變異的動態(tài)多種群粒子群算法（Dynamic Multi-population Particle Swarm Optimization Based on Local Cooperative and Competitive Mutation，LC-DMPPSO）。LC-DMPPSO算法設(shè)計了一種局部協(xié)同的方法，該方法劃分種群成多個子種群，劃分后的子種群再通過非支配排序、差分變異的方法選擇出一對領(lǐng)導(dǎo)粒子。同時，對粒子的更新方法進行改進，讓各個目標優(yōu)化更加均衡，增強LC-DMPPSO算法的局部搜索能力，提高收斂精度。在LC-DMPPSO算法中，為了防止出現(xiàn)“早熟”收斂的情況，引入競爭變異來增加種群多樣性。最后，通過選擇一系列標準測試函數(shù)將LC-DMPPSO算法與3種進化算法進行比較，驗證所提算法的有效性。實驗結(jié)果顯示，所提算法的多樣性和收斂性比其他3種進化算法更好，優(yōu)化效果更佳。

關(guān)鍵詞：多目標優(yōu)化問題;粒子群算法;多種群;局部協(xié)同;競爭變異

Abstract：In view of the poor diversity and low convergence accuracy of particle swarm algorithm when dealing with complex optimization problems， a dynamic multi-population particle swarm optimization based on local coordination and competitive mutation （Dynamic Multi-population Particle Swarm Optimization Based on Local Cooperative and Competitive Mutation， LC-DMPPSO）. LC-DMPPSO designed a local coordination method， which divides the population into multiple sub-populations， and then the divided sub-populations select a pair of leader particles through the method of non-dominated sorting and differential mutation. At the same time， the particle update method is improved to make the optimization of each target more balanced， enhance the local search ability of LC-DMPPSO， and improve the accuracy of convergence. In LC-DMPPSO， in order to prevent "premature" convergence， competitive mutation is introduced to increase population diversity. Finally， a series of standard test functions are selected to compare LC-DMPPSO with three evolutionary algorithms to verify the effectiveness of the proposed algorithm. The experimental results show that the diversity and convergence of the proposed algorithm are better than the other three evolutionary algorithms， and the optimization effect is better.

Key words：multi-objective optimization problem （MOP）; particle swarm optimization （PSO）; multi-population; local cooperative; Competition mutation

在現(xiàn)代工程領(lǐng)域中，很多情況下會遇到復(fù)雜的多目標問題[1-3]，這些問題中的目標相互沖突，其中一個目標的最佳解決方案可能是另一個目標的最壞解決方案。因此，MOP只能用一組稱為帕累托最優(yōu)解[4] 來描述。在求解MOP中，不難發(fā)現(xiàn)的是如何平衡各目標之間的沖突，才是求解的關(guān)鍵。文獻[5]中提出一種通過最近鄰方法的歸檔更新機制，減少計算量。文獻[6]中使用神經(jīng)模糊系統(tǒng)確定遺傳交叉和變異算子，提高算法性能。文獻[7]中將改進的螢火蟲算法與粒子群優(yōu)化算法相結(jié)合，解決了自動數(shù)據(jù)聚類問題。文獻[8]中將整個進化過程分為前階段和后階段，既保持種群的多樣性又能提高種群整體的收斂精度。文獻[9]中將加權(quán)期望后的貝葉斯優(yōu)化方法處理電路模塊劃分問題，并將該方法擴展到MOP上，該方法能夠在更少的迭代中，取得最好的優(yōu)化結(jié)果。文獻[10]中采用動態(tài)分解的參考向量動態(tài)劃分分解空間的方法尋找最優(yōu)解。文獻[11]中在處理計算昂貴的適應(yīng)度函數(shù)時，提出具有主動學(xué)習(xí)的代理輔助粒子群算法。然而，該算法犧牲種群多樣性為代價提高局部搜索能力。

為了使PSO算法在解決多目標優(yōu)化問題中的收斂性與種群多樣性之間取得平衡，現(xiàn)提出LC-DMPPSO算法。LC-DMPPSO算法通過與其它3種算法，在一系列的標準測試函數(shù)進行對比實驗，驗證其求解復(fù)雜優(yōu)化問題的有效性。

1 MOP模型與PSO

1.1 MOP模型

MOP極小化模型[12]定義如下：

2 算法介紹

2.1 局部協(xié)同

在面對復(fù)雜的多目標問題時，利用多個種群可以取得更好的優(yōu)化結(jié)果，基于這種思想，LC-DMPPSO采用一種協(xié)同策略，即局部協(xié)同。其是將初始種群劃分為M+1個子種群。M個待優(yōu)化的目標分別對應(yīng)M個子種群。接下來，劃分后得到的M個子種群在選擇領(lǐng)導(dǎo)粒子時，通過非支配排序的方式進行篩選，每個子種群最終得到一對領(lǐng)導(dǎo)粒子，該方法為粒子提供更多向優(yōu)秀個體學(xué)習(xí)的機會，引導(dǎo)種群向更好的方向進化。在第M+1的子種群中，利用差分變異方式（Differential Mutation，DM）選擇領(lǐng)導(dǎo)粒子，充分利用DM的全局搜索優(yōu)勢，能夠保障LC-DMPPSO的收斂性。具體步驟如下：

（1） 將整個初始種群按照M個待優(yōu)化目標隨機劃分為M+1子種群;

（2） M個子種群針對M個目標進行優(yōu)化，計算粒子的適應(yīng)度值以及擁擠距離，得到該粒子的非支配等級。然后，依據(jù)非支配等級選擇出一對領(lǐng)導(dǎo)粒子。最后，更新粒子信息;

（3） 另一個子種群依照DM的方法從自身最優(yōu)粒子中選擇領(lǐng)導(dǎo)粒子，每個子種群通過領(lǐng)導(dǎo)粒子完成更新操作;

（4） 完成上述工作，將M+1個子種群合并。

2.2 領(lǐng)導(dǎo)粒子選擇

在LC-DMPPSO中，會根據(jù)種群中的每個粒子的特點去決定領(lǐng)導(dǎo)粒子。被選擇作為領(lǐng)導(dǎo)粒子的一對粒子，引導(dǎo)其向更好的方向發(fā)展。假設(shè)M個子種群中的第k（k=1，2，…，M）個子種群針對目標fk進行優(yōu)化。此時，第i個粒子選擇領(lǐng)導(dǎo)粒子時，需要判斷粒子i的非支配等級，預(yù)選的領(lǐng)導(dǎo)粒子的非支配等級必須在粒子i之上。接下來，預(yù)選的領(lǐng)導(dǎo)粒子被確定后，可以在其中任意選擇一個非支配等級。然后，對排列在相同等級下的粒子進行進一步的篩選，通過計算粒子在目標fk上的適應(yīng)度值，選擇表現(xiàn)最好的粒子作為領(lǐng)導(dǎo)粒子lbest1。

但是，若在該非支配等級上存在兩個及以上的粒子，那么就會按照擁擠距離作為評判標準，選擇其中較大的那個粒子成為領(lǐng)導(dǎo)粒子，記為lbest1。然后，依據(jù)領(lǐng)導(dǎo)粒子lbest1進行排序后，選擇距離lbest1最近且擁擠距離最大的粒子作為另一個領(lǐng)導(dǎo)粒子，記為lbest2，構(gòu)成的一對領(lǐng)導(dǎo)粒子lbest1，lbest2將引導(dǎo)整個種群的進化方向。

領(lǐng)導(dǎo)粒子的具體選擇操作如下：首先，建立一個臨時檔案用來存儲所有粒子，臨時檔案中有6個粒子，編號為1～6。此時，假設(shè)子種群針對目標fk進行優(yōu)化，6個粒子在臨時檔案中進行非支配排序后的等級排序結(jié)果如表1所示，表1中共有三個等級。假設(shè)子種群的第i個粒子選擇領(lǐng)導(dǎo)粒子時，第i個粒子的非支配等級為一級，此時的預(yù)選領(lǐng)導(dǎo)粒子分別為1﹑5。若隨機選擇種群的第i個粒子的等級為二級，領(lǐng)導(dǎo)粒子lbest1應(yīng)是粒子1、5、3、6中在目標fk上表現(xiàn)最好的粒子，假設(shè)粒子3是fk上表現(xiàn)最好，那么粒子3就被選為領(lǐng)導(dǎo)粒子lbest1。然后，再根據(jù)粒子3的位置，在剩余的5個粒子中選擇非支配排序離它最近且擁擠距離最大的粒子作為領(lǐng)導(dǎo)粒子lbest2。LC-DMPPSO算法中選擇兩個領(lǐng)導(dǎo)粒子，讓其余所有粒子有機會向鄰近粒子學(xué)習(xí)，增強局部搜索能力，同時，設(shè)計多個子種群可以動態(tài)地針對單個目標進行優(yōu)化，能夠有效地提高LC-DMPPSO算法的收斂精度。

同時，為了更直觀地驗證LC-DMPPSO有效性，4種算法在3個目標上得到的pareto前沿的實驗仿真結(jié)果如圖3～圖5所示。從圖3中可以看出，LC-DMPPSO在3個目標測試函數(shù)DTLZ4上能夠得到更多的非支配解，MOPSO-SDCD和MMOPSO明顯沒有很好的收斂在pareto前沿上，沒有達到很好的優(yōu)化效果。同樣，在3個目標DTLZ4上，LC-DMPPSO的pareto分布最好。最后，在3個目標WFG9上，LC-DMPPSO分布依然是4個算法中優(yōu)化效果最佳，證明所提算法的種群多樣性最好。

從實驗結(jié)果可以明顯看出，在優(yōu)化5個目標測試函數(shù)時，LC-DMPPSO在GD、SP、IGD評價指標上全部取得了不錯的優(yōu)化效果，且在3個目標的測試函數(shù)上生成的Pareto前沿分布性要明顯優(yōu)于另外三種算法，具有最好的競爭力。結(jié)合所有實驗分析驗證了所提算法LC-DMPPSO在解決復(fù)雜的多目標優(yōu)化問題上的有效性。

4 結(jié) 論

針對多目標優(yōu)化問題中多樣性與收斂性之間的不平衡問題，提出了LC-DMPPSO算法。該算法通過引入局部協(xié)同的思想，將種群劃分為多個子種群共同完成進化，并為子種群選擇一對領(lǐng)導(dǎo)粒子的操作方式，大大提高了LC-DMPPSO算法的局部搜索能力，實現(xiàn)了各目標之間的多樣性與收斂性的平衡，利用競爭變異策略保證了種群的多樣性。實驗結(jié)果表明，LC-DMPPSO算法能有效平衡各個目標之間的關(guān)系，優(yōu)化結(jié)果最佳。

參考文獻

[1] 史文欣，毛劍琳.基于五行環(huán)優(yōu)化算法的多目標柔性車間調(diào)度問題研究[J].電子測量技術(shù)， 2020， 43（20）：63-68.

[2] 隗寒冰，賀少川.基于深度強化學(xué)習(xí)的插電式柴電混合動力汽車多目標優(yōu)化控制策略[J].重慶交通大學(xué)學(xué)報（自然科學(xué)版）， 2021， 40（1）：44-52.

[3] 周天沛，孫偉.基于充電設(shè)備利用率的電動汽車充電路徑多目標優(yōu)化調(diào)度[J].電力系統(tǒng)保護與控制， 2019， 47（4）：115-123.

[4] 鄭夏，馬良.應(yīng)急物資儲備中心多目標優(yōu)化選址的仿真研究[J].計算機仿真， 2019， 36（9）：473-478.

[5] ALKEBSI K， DU Wen-li. A fast multi-objectiveparticle swarm optimization algorithm based on a new archive updating mechanism[J]. IEEE Access， 2020， 8： 124734-124754.

[6] DZIWINSKI P， BARTCZUK L. A new hybrid particle swarm optimization and genetic algorithm method controlled by fuzzy logic[J]. IEEE Transactions on Fuzzy Systems， 2020， 28（6）：1140-1154.

[7] AGBAJE M B， EZUGWU A E， ELS R. Automatic data clustering using hybrid firefly particle swarm optimization algorithm[J]. IEEE Access， 2019， 7： 184963-184984.

[8] FENG Qian， LI Qing， WANG Heng， et al. Two-stage adaptive constrained particle swarm optimization based on bi-objective method[J]. IEEE Access， 2020， 8： 150647-150664.

[9] LYU Wen-long， XUE Pan， YANG Fan， et al. An efficient bayesian optimization approach for automated optimization of analog circuits[J]. IEEE Transactions on Circuits and Systems， 2018， 65（6）：1954-1967.

[10]GAO Tiao-kang， CAO Bin， ZHANG Meng-xuan. Multi-objective complex network clustering based on dynamical decomposition particle swarm optimization[J].IEEE Access， 2020， 8：32341-32352.

[11]LV Zhi-ming， WANG Lin-qing， HAN Zhong-yang， et al. Surrogate-assisted particle swarm optimization algorithm with pareto active learning for expensive multi-objective optimization[J]. IEEE/CAA Journal of Automatica Sinica， 2019， 6（3）：838-849.

[12]何愛華，張曉青，趙克全.多目標優(yōu)化問題近似解的組合標量化[J].重慶師范大學(xué)學(xué)報（自然科學(xué)版）， 2019，36（3）：7-10.

[13]高云龍，閆鵬.基于多種群粒子群算法和布谷鳥搜索的聯(lián)合尋優(yōu)算法[J].控制與決策， 2016， 31（4）：601-608.

[14]CHEN Yong-gang， LI Li-xiang， PENG Hai-peng， et al. Particle swarm optimizer with two differential mutation[J]. Applied Soft Computing， 2017， 61：314-330.

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

[16]LIN Qiu-zhen， LI Jian-qiang， DU Zhi-hua， et al. A novel multi-objective particle swarm optimization with multiple search strategies[J]. European Journal of Operational Research， 2015， 247（3）：732-744.

[17]PENG Guang， FANG Yang-wang， PENG Wei-shi， et al. Multi-objective particle optimization algorithm based on sharing-learning and dynamic crowding distance[J]. Optik， 2016， 127：5013-5020.

[18]DEB K， JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach， part i： solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation， 2014， 18（4）：577-601.