基于局部協(xié)同與競爭變異的動(dòng)態(tài)多種群粒子群算法

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

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

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

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

1 MOP模型與PSO

1.1 MOP模型

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

2 算法介紹

2.1 局部協(xié)同

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)

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

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

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

[4] 鄭夏，馬良.應(yīng)急物資儲(chǔ)備中心多目標(biāo)優(yōu)化選址的仿真研究[J].計(jì)算機(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]何愛華，張曉青，趙克全.多目標(biāo)優(yōu)化問題近似解的組合標(biāo)量化[J].重慶師范大學(xué)學(xué)報(bào)（自然科學(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.