摘要：在多目標(biāo)粒子群優(yōu)化的設(shè)計中，收斂性和多樣性的正確管理是獲得接近真實帕累托前沿并分布良好的近似解的關(guān)鍵。為了更好地平衡收斂性和多樣性，防止算法過早收斂，提出了一種基于相似度的自適應(yīng)多目標(biāo)粒子群算法（SAMOPSO）。首先，算法利用存檔中每個解與其他解之間的相似度和適應(yīng)度值來維護存檔獲得高質(zhì)量的候選解。其次，引入了一種基于各粒子信息的自適應(yīng)飛行參數(shù)調(diào)整機制，進一步提高SAMOPSO算法的進化性能。最后，將SAMOPSO算法與六個經(jīng)典多目標(biāo)優(yōu)化算法在15個基準(zhǔn)測試函數(shù)上進行比較，結(jié)果證實了該算法的有效性。

關(guān)鍵詞：多目標(biāo)優(yōu)化；相似度；自適應(yīng)；收斂性；多樣性

中圖分類號：TP18文獻標(biāo)識碼：A文章編號：1009-3583（2024）-0094-07

Adaptive Multi-objective Particle Swarm Optimization Based on Similarity

SONG Qian1，LIU Yan-min2*，ZHANG xiao-yan3，ZHANG Yan-Song3

（1.School of Data Science and Information Engineering，GuizhouMinzuUniversity，Guiyang 550025，China;2.School of Mathematics，Zunyi Normal University，Zunyi 563006，China;3.School of Mathematics and Statistics，GuizhouUniversity，Guiyang 550025，China）

Abstract：In the design of multi-objective particle swarm optimization，the correct management of convergence and diversity is the key to obtain a well-distributed approximate solution close to the real Pareto Front.In order to better balance convergence and diversity and prevent premature convergence of algorithms，an adaptive multi-objective particle swarm optimization based on similarity（SAMOPSO）is proposed.Firstly，the algorithm uses the similarity and fitness values between each solution and other solutions in the archive to main-tain the archive and obtain high-quality candidate solutions.Secondly，an adaptive flight parameter adjustment mechanism based on par-ticle information is introduced to further improve the evolution performance of SAMOPSO algorithm.Finally，the SAMOPSO algorithm is compared with six classical multi-objective optimization algorithms on 15 benchmark functions，and the results confirm the effecti-veness of the algorithm.

keywords：multi-objectiveoptimization;similarity;self-adaptation;convergence;diversity

粒子群算法（Particle Swarm Optimizati-on，PSO）[1]是由Kennedy和Eberhart等人在1995年受到自然啟發(fā)提出的一種群智能范式，靈感來源于鳥類覓食的社會行為，由于其在確定搜索方向和步長方面的獨特性受到了廣泛研究。PSO依賴一群粒子在搜索空間中通過協(xié)作飛行來進行探索，向個體最優(yōu)經(jīng)驗（personal best，ptest）和種群最優(yōu)經(jīng)驗（global best，gbest）學(xué)習(xí)獲得最優(yōu)解。

在科學(xué)和工程領(lǐng)域中，許多需要同時優(yōu)化幾個可能相互沖突的目標(biāo)函數(shù)的現(xiàn)實應(yīng)用被稱為多目標(biāo)優(yōu)化問題（multi-objective optimization problems，MOPs）[2]。自2002年Coello Coello和Lechuga[3]將PSO的使用從單目標(biāo)優(yōu)化問題擴展到MOPs后，多目標(biāo)粒子群優(yōu)化算法（Multi-objective Particle Swar-m Optimization，MOPSO）[4]就被廣泛應(yīng)用于解決各種MOPs，例如交通信號控制問題[5]、路徑規(guī)劃問題[6]、車輛調(diào)度[7]等等。由于MOPs的目標(biāo)函數(shù)往往會彼此沖突，因此得到一個可以優(yōu)化所有目標(biāo)的單一解是困難的，相反，通常采用一組稱為帕累托最優(yōu)解（Pareto optimal）的平衡解來表示給定MOP的目標(biāo)之間可能得到的最佳妥協(xié)。

當(dāng)應(yīng)用PSO解決MOPs時，需要面臨的挑戰(zhàn)之一是為粒子選擇pbest和gbest，pbest和gbest的選擇策略決定了粒子飛行的潛在方向，對MOPSO的性能有重要影響。第二個挑戰(zhàn)是整個進化過程中種群的收斂性和多樣性之間的平衡，在進化過程的早期階段，快速收斂導(dǎo)致多樣性損失，這可能會導(dǎo)致算法過早陷于局部最優(yōu)。針對這兩個挑戰(zhàn)，Wu等[8]基于外部存檔中的解到原點的最小距離的改變提出了進化狀態(tài)檢測機制，檢測種群狀態(tài)是探索狀態(tài)還是開發(fā)狀態(tài)？以及基于預(yù)定義參考點的存檔維護策略，從而選擇相應(yīng)的優(yōu)質(zhì)領(lǐng)導(dǎo)者更好地促進收斂性和多樣性之間的平衡。Han等[9]提出一種為不同子群選擇不同領(lǐng)導(dǎo)者的多群方法，基于非支配解的分布和優(yōu)勢信息設(shè)計了進化狀態(tài)檢測機制，利用候選解的進化狀態(tài)信息和空間特征，提出了一種自適應(yīng)多選擇策略并引入一種基于各粒子優(yōu)勢關(guān)系的自適應(yīng)參數(shù)調(diào)整機制，進一步提高算法的性能。Wang等[10]提出了一種平行單元坐標(biāo)系方法（Parallel Cell Coordinate System，PCCS），基于粒子在單元格中的分布來評估粒子，將選擇全局最優(yōu)和個體最優(yōu)、維護存檔、調(diào)整飛行參數(shù)和干擾停滯的策略集成到算法中。Cai等[11]利用一組方向向量將目標(biāo)空間劃分為多個子區(qū)域，使每個子區(qū)域保留一個多樣性解并利用擁擠距離計算保留解的適應(yīng)度值來更好地執(zhí)行選擇操作。Bai等[12]根據(jù)非支配解當(dāng)前和歷史的分布信息，提出一種分布知識導(dǎo)向評估策略，提高了分布信息的準(zhǔn)確性，為gbest的選擇提供更準(zhǔn)確有效的信息，改進算法的搜索性能。

雖然上述改進策略使得MOPSO的有效性得到了提升，但仍然存在改進的空間。進化過程中，為了使粒子跳出收斂性較差的區(qū)域，自適應(yīng)調(diào)整機制可以調(diào)整參數(shù)，提高粒子的探索能力。同時，當(dāng)粒子搜索收斂性較好的最優(yōu)區(qū)域時，較低的速度可以幫助粒子獲得良好的最優(yōu)解。因此本文提出了一種基于相似度的自適應(yīng)多目標(biāo)粒子群算法（SA-MOPSO）。首先，算法評估存檔中每個解與其他解之間的接近程度，在最接近的兩個粒子之間進行選擇，其次，為了充分利用每個粒子攜帶的信息，更好地管理收斂性和多樣性之間的平衡，對飛行參數(shù)進行了自適應(yīng)調(diào)整，使算法的性能得到提升。

1定義和概念

1.1多目標(biāo)優(yōu)化問題

以最小化為例，一個多目標(biāo)優(yōu)化問題可以定義為：

minF（x）=[f（x），f3（x）…fm（x）]，x=Ω（1）

其中是n維決策變量，是決策空間，f（x）是m維目標(biāo)函數(shù)，m＞1，fm（x）表示第m個目標(biāo)函數(shù)。通常情況下，利用Pareto支配關(guān)系比較解，一個解x Pareto支配另一個解y（xp y），即

在MOPs中，不被任何其他解支配的解稱為非支配解或Pareto最優(yōu)解，Pareto最優(yōu)解集合在目標(biāo)空間中的映射稱為帕累托前沿（Pareto Front，PF）。1.2粒子群算法

種群中的每個粒子有兩個特性：

位置（）=[，），2（）……（），

速度，

，其中N表示種群的規(guī)模，種群中第i個粒子的速度和位置更新公式為：

（2）（3）

其中t為迭代次數(shù)，c1為自我認知學(xué)習(xí)因子，c2為社會認知學(xué)習(xí)因子，為慣性權(quán)重，r1，r2是［0，1］內(nèi)的隨機數(shù)。pbesti（t）的計算公式為

pbest（+1）=（4）

2算法設(shè)計

2.1自適應(yīng)參數(shù)調(diào)整機制

在MOPSO中，飛行參數(shù)慣性權(quán)重和加速度系數(shù)c1、c2對于實現(xiàn)全局探索和局部開發(fā)之間的平衡非常重要，其中，慣性權(quán)重決定下一代速度更新會受到粒子當(dāng)前速度的影響程度，學(xué)習(xí)因子c1、c2分別決定了粒子向個體歷史最優(yōu)位置和全局歷史最優(yōu)位置的學(xué)習(xí)程度。因此飛行參數(shù)會導(dǎo)致算法進化過程走向不同的飛行方向，相應(yīng)地，使用較小的和c1，以及較大的c2可以促進算法的收斂，將有利于將近似帕累托前沿向前推進，相反，在多樣性狀態(tài)下，和c1越大，c2越小會增加近似帕累托前沿的多樣性。算法的尋優(yōu)過程是復(fù)雜的，固定調(diào)節(jié)速度的參數(shù)控制方法可能會與優(yōu)化過程不匹配[13]，因此，為了減少算法陷入“早熟”收斂的可能性，本文對，c1、c2進行了改進，使得飛行參數(shù)在進化過程中可以根據(jù)進化信息進行自適應(yīng)調(diào)整。慣性權(quán)重的更新方式如下：

其中，omin為慣性權(quán)重最小值，取值為0.1；max為慣性權(quán)重最大值，取值為0.8；N是種群的大小，|A（t）|表示第t次迭代存檔中解的數(shù)目。進化過程的早期階段非支配解數(shù)目較少，此時應(yīng)該調(diào)大擴大搜索范圍，當(dāng)存檔逐漸變滿，值逐漸變小，使得粒子盡可能地開發(fā)有希望的區(qū)域。

種群每一次的迭代更新，所有粒子位置都會根據(jù)速度矢量改變，每個粒子都可能攜帶有用的信息。適應(yīng)度值較好的粒子能夠引導(dǎo)其他粒子探索有希望的區(qū)域，適應(yīng)度值較差的粒子能夠指示避開無望的區(qū)域。為了充分利用每個粒子攜帶的信息，本文根據(jù)每個粒子的個體最優(yōu)經(jīng)驗來調(diào)整不同粒子的學(xué)習(xí)因子。學(xué)習(xí)因子的更新方式如下：

（6）

（7）

其中，cmin為學(xué)習(xí)因子最小值，取值為0.5；cmax為學(xué)習(xí)因子最大值，取值為2；pfit（·）為個體最優(yōu)經(jīng)驗的適應(yīng)度值之和，當(dāng)個體最優(yōu)經(jīng)驗的適應(yīng)度值越小，說明個體pbest周圍的區(qū)域希望越大，此時，調(diào)大c1，調(diào)小c2使得粒子更多地向pbest學(xué)習(xí)；個體pbest的適應(yīng)度值越大，說明個體pbest周圍的區(qū)域應(yīng)該盡可能避開，此時，調(diào)小c1，調(diào)大c2使得粒子更多地向全局最優(yōu)粒子學(xué)習(xí)。

2.2存檔的維護策略

MOPSO采用外部存檔存儲每次迭代更新產(chǎn)生的非支配解，以保存精英解。當(dāng)一個新的解插入到外部存檔中，如果這個新的解被存檔中的某個解支配它將被丟棄，否則，此解進入外部存檔并刪除存檔中被它支配的解。由于領(lǐng)導(dǎo)者的選擇是基于外部存檔完成的，因此存檔的正確管理對算法的性能影響至關(guān)重要。一般來說，存檔的大小是有限的，而非支配解的數(shù)量會隨著群體的迭代而迅速增加，如果不對存檔進行修剪，計算成本將增大。因此，為了獲得高質(zhì)量的存檔，本文首先利用相似度計算等式計算外部存檔中每個非支配解與其他非支配解之間的相似度系數(shù)I（g），保留最大的相似度系數(shù)作為非支配解的多樣性度量，之后，對具有最大相似度系數(shù)的非支配解進行刪除。當(dāng)一個解的相似度系數(shù)越小，表明它與其他解之間接近程度越小，存檔中，當(dāng)兩個非支配解的相似度系數(shù)最大并且一樣，說明搜索空間中這兩個解彼此最接近，此時計算解的適應(yīng)度值之和fit（g），刪除具有更大和的解。重復(fù)此步驟，直到存檔的大小達到閾值。I（g）和fit（g）的定義如下：

其中，A（t）表示種群第t次迭代的外部存檔，|A（t）|表示存檔中現(xiàn)存解的數(shù)目。

2.3算法步驟

SAMOPSO算法的步驟如下：

Step1：初始化每個粒子的位置和速度；

Step2：對種群進行突變操作；

Step3：評估種群；

Step4：建立外部存檔存儲非支配解并根據(jù)2.2維護存檔；

Step5：為每個粒子選擇ghest，并用公式（4）選擇pbest;

Step6：根據(jù)公式（2）、（3）和2.1更新種群；

Step7：判斷是否達到最大迭代次數(shù)？是則輸出，否則轉(zhuǎn)到Step2繼續(xù)迭代。

3仿真實驗與結(jié)果分析

3.1性能指標(biāo)

實驗中，使用反世代距離（inverted gen-erationaldistance，IGD）[14]和超體積（hyper-volume，HV）[14]來說明SAMOPSO算法的有效性。

（1）IGD：IGD指標(biāo)被用于反映不同進化算法的多樣性和收斂性。

F*是一組從真實Pareto最優(yōu)前沿上選擇的均勻分布的解，F(xiàn)是算法獲得的非支配解集，x是屬于F*的最優(yōu)解，mindis（x，F(xiàn)）是x與F中的非支配解之間的最小歐氏距離。IGD值越小，算法得到的解集質(zhì)量越好。

（2）HV：HV指標(biāo)被用于描述所得到的非支配解的收斂性和多樣性，HV可以反映不同進化算法的綜合性能。

其中為勒貝格測度，Q是非支配解的數(shù)目，V是第Y個非支配解與預(yù)先設(shè)置的參考點構(gòu)造的超體積，HV值越大，說明收斂性和多樣性越好。

3.2實驗設(shè)計

在本節(jié)中，使用5個ZDT[15]基準(zhǔn)測試函數(shù)和10個UF[16]基準(zhǔn)測試函數(shù)評估算法的性能。采用六種經(jīng)典算法與SAMOPSO算法進行比較驗證其性能，對比算法可分為兩類：多目標(biāo)PSO算法，包含NMPSO[17]，MPSOD[11]，SMPSO[18]，和多目標(biāo)進化算法，包含NSGAⅢ[19]，MOEADD[20]，SPEAR[21]。

3.3實驗參數(shù)設(shè)置

測試問題包含ZDT系列和UF系列，ZDT系列、UF1-UF7是雙目標(biāo)測試問題，UF8-UF10是三目標(biāo)測試問題，ZDT1-ZDT3、UF系列測試問題的決策空間都為30維，ZDT4和ZDT6的決策空間為10維。

為了進行公平地對比實驗分析，所有比較算法的所有參數(shù)都按照其原始論文中的建議進行設(shè)置，種群大小均設(shè)置為N＝200，外部存檔的閾值與N一致，最大評估次數(shù)為10000，在每個測試實例上，每個算法進行30次獨立運行。所有的實驗結(jié)果都是在Intel（R）Core（TM）i7-8750H CP-U@2.20GHz 2.20 GHz，Windows 10操作系統(tǒng)，MATLAB R2020b上獲得。對比算法的源代碼由PlatEMO[22]提供。

3.4實驗結(jié)果分析

表1和表2顯示了6種對比算法NMPSO、MPSOD、SMPSO、NSGAⅢ、MOEADD、SPEAR和所提出的SAMOPSO算法在ZDT、UF問題上的IGD、HV指標(biāo)的平均值和標(biāo)準(zhǔn)差，每個測試實例的最佳值以粗體表示。從表一最后一行的總結(jié)結(jié)果可以觀察到SAMOPSO算法在15個基準(zhǔn)測試?yán)又谐鲆话氲膶嵗螴GD指標(biāo)獲得了最好的結(jié)果，其次是NSGAⅢ、MOEADD，它們分別在3個測試實例上表現(xiàn)最好，NMPSO在UF4上得到的效果最好。在表二SAMOPSO算法和其他6種算法的HV指標(biāo)的比較結(jié)果中，SAMOPSO算法在9個基準(zhǔn)測試問題中表現(xiàn)最好，優(yōu)于其他比較算法。在ZDT系列測試問題中，SAMOPSO算法在ZDT4上的表現(xiàn)略差于MOEADD，在UF系列測試問題中有5個表現(xiàn)較好。根據(jù)實驗結(jié)果可以得出結(jié)論，在所提出的SAMOP-SO算法和所有選擇的競爭算法的比較中，SAMOP-SO算法可以在求解MOPs時，表現(xiàn)出更好的綜合性能。

為了觀察SAMOPSO算法所得到的非支配解集的分布，圖2圖3給出了六個對比算法與所提出的SAMOPSO算法在ZDT1、ZDT3測試問題上的PF圖。從圖中可以看出，一些對比算法在測試問題上明顯缺乏收斂性或者多樣性。NMPSO算法可以接近真實的PF，卻觀察到不足的多樣性，其非支配解的分布是不均勻的，其余對比算法相對NMPSO算法有較好的多樣性，卻有差的收斂性。而本文提出的SAMOPSO算法得到的非支配解集不僅可以接近真實PF，而且可以均勻分布。

圖4給出了不同算法在ZDT1和UF9上關(guān)于IGD值的收斂軌跡，可以觀察到SAMOPSO算法有較快的收斂速度。為了進一步探究實驗結(jié)果，不同算法在ZDT系列測試問題上關(guān)于IGD度量的箱形圖如圖5所示，圖中的1、2、3、4、5、6、7分別代表SAMOPSO、NMPSO、MPSOD、SMPSO、NSGAⅢ、MOEADD、SPEAR。與比較算法相比，SAMOPSO算法在解決大多數(shù)測試問題方面具有顯著的性能，結(jié)果可以穩(wěn)定在一個較小的波動范圍內(nèi)，實驗結(jié)果表明，該算法在收斂精度和穩(wěn)定性方面相對比較算法具有較明顯的優(yōu)勢。

4實驗結(jié)論

本文提出了一種基于相似度的自適應(yīng)多目標(biāo)粒子群算法（SAMOPSO），改進了存檔的維護策略，引入了自適應(yīng)參數(shù)策略。通過利用存檔中不同解之間的相似度，刪除性能不好的解提高候選解的質(zhì)量，為了增加進化信息的利用程度，從而使得參數(shù)自適應(yīng)改變，算法在一定的程度上獲得了較好的收斂性和多樣性。通過仿真實驗驗證了SAMOP-SO算法的性能，并與幾種經(jīng)典算法在ZDT和UF系列測試問題上進行了比較，實驗結(jié)果表明，該SAMOPSO算法在收斂性、多樣性方面更具有競爭性。

參考文獻：

[1]KennedyJ，EberhartR.Particle swarm optimization[C]//Pro-ceedings of ICNN'95-international conference on neural net-wo-rks.IEEE，1995（4）：1942-1948.

[2]ZhouH，QiaoJ.Multiobjective optimal control for waste-water treatment proces-s using adaptive MOeA/D[J].Applied I-ntelligence，2019（49）：1098-1126.

[3]Coello C A C，Lechuga M S.MOPSO：A proposal for mul-tiple objective parti-cle swarm optimization[C]//Proceedings of the 2002 Congress on evolutionary Computation.CeC'02 Cat.No.02TH8600.Ieee，2002（2）：1051-1056.

[4]Coello C A C，Pulido G T，LechugaMS.Handling multiple objectives with particle swarm optimization[J].IEEE Tr-an-sactions on evolutionary computation，2004，8（3）：256-279.

[5]ShaikhPW，el-AbdM，KhanaferM，etal.A review on swarm intelligence and evolutionary algorithms for solving the traffic signal control problem[J].Ieee tr-ansactions on intelligenttransportation s-ystems，2020（231）：48-63.

[6]ChenZ，WuH，ChenY，etal.Patrol robot path planning in nu-clear power pl-ant using an interval multi-objective par-ticle swarm optimization algorithm[J].Applied soft computing，2022（116）：108192.

[7]QiR，LiJ，WangJ，etal.Qmoea：A q-learning-based multi-objective evolutiona-ry algorithm for solving time-dependent green vehicle routing problems with tim-e windows[J].Infor-mation Sciences，2022（608）：178-201.

[8]WuB，HuW，HuJ，etal.Adaptive m-ultiobjective particle swarm optimization based on evolutionary state estimation[J].Ieee Transactions on Cybernetics，2019（517）：3738-3751.

[9]HanH，LiuY，HouY，etal.Multi-mo-dal multi-objective par-ticle swarm optim-ization with self-adjusting strategy[J].In-formation Sciences，2023（629）：580-598.

[10]HuW，YenGG.Adaptivemultiobject-ive particle swarm op-timization based on parallel cell coordinate system[J].Ieee Transactions on evolutionary Computatio-n，2013（191）：1-18.

[11]DaiC，WangY，Ye M.A new multi-objective particle swarm

optimization al-gorithm based on decomposition[J].Info-rmation Sciences，2015（325）：541-557.

[12]BaiX，HanH，ZhangL，etal.Adist-ribution-knowledge-guided assessment str-ategy for multiobjective particle swarm optimization[J].Information Sciences，2023（648）：119603.

[13]LiuQ，LiJ，RenH，etal.Allparticl-es driving particle swarm optimization：Superior particles pulling plus inferior p-artic-les pushing[J].Knowledge-Based Sy-stems，2022（249）108849.

[14]HanH，ZhangL，YingaA，etal.Ada-ptive multiple selection strategy for mul-ti-objective particle swarm optimization[J].Information Sciences，2023（624）：235-251.

[15]Zitzlere，DebK，ThieleL.Comparis-on of multiobjective evolutionary algorit-hms：empirical results[J].evolutionary c-omputation，2000（82）：173-195.

[16]ZhangQ，ZhouA，ZhaoS，etal.Mul-tiobjectiveoptimiza-tion test instances f-or the CeC 2009 special session and co-mpetition[J].Mechanical Engineering，2008（1）：1-31.

[17]LinQ，LiuS，ZhuQ，etal.Particle swarm optimization with a balanceable fitness estimation for many-objective opt-im-ization problems[J].Ieee Transactions on evolutionary Com-putation，2016（221）：32-46.

[18]Nebro A J，Durillo J J，Garcia-Nieto J，etal.SMPSO：A new PSO-based meta-heuristic for multi-objective optimization[C].//2009 Ieee Symposium on computati-onal intelligence in multi-criteria decisio-n-making MCDM.Ieee，2009：66-73.

[19]DebK，JainH.An evolutionary many-objective optimiza-tion algorithm using r-eference-point-based nondominated sortin-g approach，part I：solving problems wi-th box con-straints[J].Ieee transactions on evolutionary computation，2013（184）：577-601.

[20]LiK，DebK，ZhangQ，etal.Anev-olutionary many-objec-tive optimization a-lgorithm based on dominance and deco-mposition[J].Ieee transactions on evolut-ionary computation，2014（195）：694-716.

[21]JiangS，Yang S.A strength Pareto ev-olutionary algorithm based on reference direction for multiobjective and many-o-bjective optimization[J].Ieee Transactions on evolutionary Computation，2017，21（3）：329-346.

[22]TianY，ChengR，ZhangX，etal.Pla-tEMO：A MATLAB platform for evoluti-onary multi-objective optimization[educ-ational forum][J].IEEE Computational I-ntelligence Magazine，2017，12（4）：73-87.

（責(zé)任編輯：羅東升）