分區引導種群進化的擬態物理學多目標優化算法

摘要：針對基本擬態物理學優化（artificialphysicsoptimization，APO）算法易陷入局部最優、分布性不佳等問題，提出一種分區引導種群進化的改進多目標擬態物理學優化（multi-objectiveAPOimprovedbypartition-guidedevolution，PEMOAPO）算法。首先，采用tent映射與反向學習相結合的策略進行種群的初始化，增強種群的多樣性；其次，提出分區引導個體進行進化的機制，對處于可行域與不可行域的個體，采取不同的質量函數及虛擬作用力計算規則進行迭代更新，增強算法的收斂性能。選取MW系列和C_DTLZ系列作為基準測試函數進行仿真實驗，通過綜合性能評價指標對比分析、統計學分析、收斂性分析及時間復雜度分析，表明改進算法具有良好的多樣性及收斂性，能快速收斂到Pareto前沿。

關鍵詞：擬態物理學；多目標；非支配排序；分區進化；質量函數；虛擬作用力

中圖分類號：TP301文獻標志碼：A文章編號：1001-3695（2023）05-015-1381-08doi：10.19734/j.issn.1001-3695.2022.10.0465

Abstract：ToaddresstheproblemsthatthebasicAPOalgorithmtendstofallintolocaloptimumandpoordistribution，thispaperproposedaPEMOAPOalgorithm.Firstly，thispaperusedthestrategyoftentmappingandreverselearningtoinitializethepopulationandenhancethepopulationdiversity.Secondly，itintroducedamechanismofpartition-guidedindividualsforevolution，anditadopteddifferentmassfunctionsandvirtualforcecalculationrulestoiterativelyupdatetheindividualsinthefeasibleandinfeasibledomainstoenhancetheconvergenceperformanceofthealgorithm.ChoosingMWseriesandC_DTLZseriesasthebenchmarktestfunctionsinsimulationexperiments，andthecomprehensiveperformanceevaluationindexcompa-risonanalysis，statisticalanalysis，convergenceanalysisandtimecomplexityanalysisshowthattheimprovedalgorithmhasgooddiversityandconvergence，andcanconvergetotheParetofrontquickly.

Keywords：artificialphysics;multi-objective;non-dominatedsorting;partitionevolution;massfunction;virtualforce

0引言

多目標優化問題存在于諸多領域之中，比如最優路徑規劃［1］、工程車輛懸架參數優化［2］和互聯網推送［3］等。實際應用中的優化問題往往涉及多個子目標函數和約束條件，且子目標函數之間相互沖突，無法同時達到最優，也沒有最優解，只能找到非劣解集合作為最終結果。多目標優化算法種類繁多，是解決多目標優化問題的有效手段，算法性能好壞又直接關系到多目標優化問題能否有效解決。基于此，對多目標優化算法展開具體研究，無論是在理論方面，還是在工程應用方面，都十分有意義。

國內外學者對多目標優化算法的研究已經取得了一定成效。典型的多目標算法有多目標粒子群算法［4］、多目標蟻群算法［5］、多目標遺傳算法［6］、多目標差分進化算法［7］等。對智能算法的研究大多遵循從單目標到多目標、從無約束到有約束、從低維到高維，從理論到應用的這樣一種規律，擬態物理學優化（APO）算法作為智能優化算法的一種，也不例外。Xie等人［8］最早提出APO算法，該算法受牛頓第二定律啟發，是一種隨機搜索算法。后續出現的有關APO算法的研究都是在文獻［8］基礎上的改進及應用。Xie等人［9］為提高傳統APO算法的全局搜索性能，引入PD控制器對個體進行動態控制，并提出一種可預測的擬態物理學優化算法。謝麗萍等人［10］對APO算法中的質量函數進行了不同設計，按曲線性質大致分為凸曲線質量函數、直線曲線質量函數和凹曲線質量函數，通過大量測試證明凹曲線質量函數性能較好。王黎等人［11］將APO算法與分布式估計算法相結合，并成功應用于復雜大規模組合優化問題配電網的重構；李盛興等人［12］將改進的APO算法用于交直流系統的無功優化問題；Zhan等人［13］將帶搜索向量的擬態物理學優化算法用于微電網脆弱性評估與重構問題。鑒于APO算法在解決單目標優化問題時的突出表現，許多學者嘗試將其改進，用于解決多目標優化問題。

王艷等人［14］借鑒聚集函數法思想，提出可用于對多目標優化問題中Pareto最優解集進行搜索的MOAPO算法。孫寶等人［15］將無約束MOAPO算法引入約束多目標優化領域中，提出一種基于序值與擁擠度的擬態物理學約束多目標優化（ICRMOAPO）算法，而后又融合R2指標，提出R2-ICRMOAPO算法［16］。張建新等人［17］引入濾子技術和平均熵初始化機制，提出一種可有效解決復雜多目標約束問題的濾子擬態物理學（FAPO）算法。FAPO算法未充分體現Pareto支配的概念，而ICRMOAPO算法雖然體現出Pareto支配的概念，但采用隨機初始化種群策略進行種群初始化，使得算法不具備良好的多樣性。

該算法對種群隨機初始化策略進行了改進，并且依據個體的不同分區，重新構造了個體質量函數和虛擬作用力計算規則，提出了一種分區引導進化的改進多目標擬態物理學優化（multi-objectiveAPOimprovedbypartition-guidedevolution，PEMOAPO）算法，通過tent映射產生混沌序列，再通過反向學習得到最終的初始化種群；針對可行域與不可行域的個體，設計不同質量函數，將其與個體序號建立起直接映射，并對虛擬力作用規則也進行修正。

3.2分區重構質量函數

傳統APO算法在求解多目標優化問題時，需知道群體中最優個體及最差個體的目標函數值，才能計算個體質量。但多目標優化問題具有多個目標函數，這時就需要通過一定策略將每個子目標函數通過一定手段組合為一個單目標函數，雖然這種方式所得質量函數也可以反映個體的優劣，但并沒有充分體現多目標優化的特點。

個體質量的大小是個體好壞的重要標志。好的個體質量較大，差的個體質量較小。在約束多目標優化問題中，質量依舊是評價個體好壞的重要指標。約束多目標優化問題中約束條件的存在將設計空間分成了可行域與不可行域兩個部分，可行域與不可行域內的個體又有著很大的區別，所以針對可行域與不可行域內的個體設計不同的進化策略就顯得尤為重要。對于可行域內的個體，個體的適應值大小可以反映個體優劣；對于不可行域內的個體而言，個體約束違反度的大小成為個體優劣的重要標志。所以對于約束多目標優化問題而言，質量函數要體現出如下特點：

a）可行域內個體的質量大于不可行域內個體的質量；

b）對于可行域內的個體，適應值優的個體質量較大，適應值差的個體質量較小；

c）對于不可行域內的個體，約束違反度較小的個體質量較大，約束違反度較大的個體質量較小。

當個體分區不同時，個體質量的計算方式也不同，箭頭表示個體的質量，箭頭越長，表示個體質量越大。可行域內的個體質量永遠比不可行域內個體的質量大。

3.3分區重構虛擬力計算規則

多目標約束優化問題中可行域內的個體與不可行域內的個體有很大區別，可行域內個體約束違反度為0，對于可行域內的個體，優化目標是使其朝著真實Pareto前沿運動；不可行域內的個體依據遠離可行域的程度計算其約束違反度值，對于不可行域內的個體，優化目標是使其朝著可行域方向運動。APO算法中適應值好的個體對適應值差的個體表現為引力，適應值差的個體對適應值好的個體表現為斥力。如果不對虛擬力作用規則進行修正，那么可能會出現當個體i在t時刻位于可行域，而在t+1時刻在其他虛擬力的作用下，運動至不可行域內，甚至遠離可行域。

4.3不同維度下算法對比分析

為檢驗提出的算法求解約束多目標優化問題的性能，將PEMOAPO與MOEA/D-AAP、CCMO、CMOAPO、ICRMOAPO在15個測試函數上進行對比分析，并且進行Wilcoxon秩和檢驗（在5%的顯著性水平上）來分析PEMOAPO算法是否在統計學意義上是最好的，+、=、-分別表示PEMOAPO性能優于、相近于、劣于對比算法。MW系列函數的維度為15，C1_DTLZ1的維度為7，C1_DTLZ3、C2_DTLZ2和C3_DTLZ4的維度為12。五種算法在固定維度的測試函數上的HV和IGD指標值的均值與標準差如表1和2所示，最好的結果已在表中加粗（M表示子目標函數個數，D表示維度）。

HV值越大，說明算法的綜合性能越好。從表1可以看出，與對比算法相比，PEMOAPO算法在大部分測試函數上獲得了較大的HV值，綜合性能良好。具體來說，在兩目標測試函數上，PEMOAPO算法與MOEA/D-AAP在測試函數MW2，MW10上無顯著性差異，與CCMO算法在測試函數MW1、MW5、MW7和MW9上無顯著性差異；在三目標測試函數上，PEMOAPO算法在測試函數C1_DTLZ1和C2_DTLZ2上與CCMO算法的HV值無顯著差異。PEMOAPO算法在所有測試函數上所得HV值均優于CMOAPO和ICRMOAPO算法。

IGD值越小，說明算法的綜合性能越好。從表2可以看出，PEMOAPO算法在大部分測試函數上都取得了較小的IGD值，綜合性能良好。具體來說，在兩目標測試函數上，PEMOAPO算法在測試函數MW1、MW5、MW7和MW9上與CCMO算法無顯著性差異，在測試函數MW2、MW10上與MOEA/D-AAP算法無明顯差異；在三目標測試函數上，PEMOAPO算法在所選C-DTLZ系列測試函數上IGD指標值的顯著性統計結果均優于對比算法。

在15個測試函數中，絕大部分的p值均小于5%，反映了PEMOAPO算法在固定維數的實驗中總體上與對比算法具有顯著差異，并且求解性能優于對比算法。

為直觀觀察改進PEMOAPO算法的尋優能力，圖5給出由五種算法所得的MW系列部分測試函數的前沿圖。圖6給出PEMOAPO算法在C-DTLZ系列測試函數上的前沿圖。

從圖5和6可以看出，PEMOAPO算法在大部分測試函數上所得解集多樣性良好，種群個體既沒有明顯較大的空隙，又沒有相互緊貼甚至重疊，而對比算法中種群個體或多或少出現了不同程度的聚集現象，設計變量平面內出現了明顯的空白，種群個體的分布不均勻。在MOEA/D-AAP、CCMO、CMOAPO和ICRMOAPO四種對比算法中，CMOAPO和ICRMOAPO算法由于其易陷入局部收斂，所以在大部分測試函數上尋優能力和分布性欠佳，對比分析可知，該算法所提出的質量函數與虛擬力的分區計算規則是有效的，可以提升算法在測試函數上的尋優能力。

為檢驗PEMOAPO算法在不同維度下的求解優勢，將PEMOAPO算法與MOEA/D-AAP、CCMO、CMOAPO和ICRMOAPO算法在測試函數MW1～13的2目標問題上進行對比分析，其中測試函數維度為D=20，50，80，100，每次運行的最大評價次數為maxFE=1000D，五種算法在測試問題為MW1～13的2目標問題上獲得的IGD值統計結果如表3所示。

由表3可知，在不同維度的測試函數上，PEMOAPO算法的求解性能優于對比算法。在20維條件下，PEMOAPO在MW1、MW2、MW3、MW5、MW6、MW9，MW10、MW12和MW13的IGD指標值均取得了最優結果，說明該算法具有優異的收斂精度及穩定性。對于測試函數MW7，PEMOAPO的IGD指標值雖沒有達到最小，但仍強于對比算法MOEA/D-AAP，對于測試函數MW11，PEMOAPO算法較CMOAPO取得1個數量級的優勢。在20維條件下對比實驗反映了PEMOAPO中混合策略初始化和分區引導進化的手段可有效促使算法跳出局部最優，并取得更好的收斂和分布性能。在50維條件下，PEMOAPO在除MW1和MW11的其他測試函數上取得了最小的IGD值，PEMOAPO受維度升高的影響較小，與對比算法相比，IGD值優勢依然存在。在80維和100維條件下，五種算法的IGD指標值均發生了不同程度的變化，雖然PEMOAPO在MW2、MW3、MW5、MW7、MW10、MW13上相較對比算法仍有優勢，但其IGD指標均值明顯隨維度升高而出現倒退情形，所以PEMOAPO算法在決策規模較大的多目標優化問題的求解性能還有待進一步提升。

4.4統計結果分析

箱線圖可以直觀反映數據的分散程度和總體分布情況。為合理分析五種算法在測試函數上30次獨立運行的結果，圖7給出固定維度的IGD指標值統計結果箱線圖，其中橫坐標標簽1、2、3、4和5分別對應MOEA/D-AAP、CCMO、CMOAPAO、ICRMOAPO和PEMOAPO算法。

從圖7可知，相較其他對比算法，PEMOAPO算法在測試函數MW1、MW6、MW11、MW12、MW13上的IGD統計結果具有優勢，同時也說明改進算法具有良好的收斂性和分布性。同時，通過與傳統MOAPO算法的IGD統計結果的比較，進一步說明了改進策略的有效性，將質量函數與個體序號建立起直接映射，將虛擬力計算規則根據區域不同進行重構，可顯著提升改進MOAPO算法的性能。從IGD指標的統計結果看，MOEA/D-AAP、CCMO、CMOAPO和ICRMOAPO四種對比算法中均存在一定的異常值，改進算法的異常值雖然明顯減少，但仍存在，改進算法的魯棒性還有待進一步提高。

4.5收斂性評價

為對PEMOAPO算法的收斂精度和收斂速度進行分析，在搜索維度D=15的條件下，圖8給出MOEA/D-AAP、CCMO、CMOAPO、ICRMOAPO和PEMOAPO算法在MW系列測試函數上IGD值隨著評估次數變化的迭代尋優過程。

從圖8可以看出，PEMOAPO算法在大部分測試函數上的迭代趨勢明顯優于對比算法，在除MW9以外的測試函數上當迭代次數到達最大迭代次數的一半時，IGD指標值就基本已達到最優精度，保證收斂速度的同時獲得了最高的收斂精度。具體來說：除MW9外，在其余測試函數上改進算法PEMOAPO的IGD值最小，在測試函數MW1、MW2、MW6、MW11、MW12和MW13上PEMOAPO算法IGD值收斂速度較快，在評估次數達到4000次左右時趨于穩定。傳統CMOAPO算法在測試函數MW6、MW7、NW9、MW11、MW12上的IGD值在達到最大評估次數時IGD值最大，將改進PEMOAPO算法與傳統CMOAPO算法進行對比分析，充分說明所提改進策略的有效性。同時在迭代初期，PEMOAPO算法可以很快跳出局部最優區域，在測試函數MW2、MW3、MW7、MW11、MW12，上迭代初期PEMOAPO算法便以很快的速度避免陷入局部收斂，最后獲得的IGD值收斂精度均優于對比算法，說明對于種群初始化方式采用tent映射和反向學習相結合的策略是有效的，增加了種群多樣性，避免算法在迭代初期陷入局部搜索。綜上所述，PEMOAPO算法在大部分測試函數上表現出良好的分布性和收斂性，且有較快的收斂速度，故提出的改進策略是可行且有效的。

4.6算法運算時間對比

時間復雜度是衡量算法優劣的重要指標之一，為對其進行量化分析，在仿真環境相同的情況下，將各算法在15個測試函數上分別獨立運行30次，記錄算法的平均運行時間。表4給出五種算法在所有測試函數上運行30次后每次尋優的平均時間，單位為s。

從表4可以看出，由于具有高質量的分區進行質量和虛擬力計算的規則，在所有測試函數上，PEMOAPO算法所花費的運行時間僅比ICRMOAPO算法長，與MOEA/D-AAP、CCMO、和CMOAPO算法相比，PEMOAPO算法的耗費時間有所減少。在雙目標測試函數MW2、MW5、MW6上，PEMOAPO算法取得了最短的運行時間，在三目標測試函數C1_DTLZ1、C1_DTLZ3、C2_DTLZ2和C3_DTLZ4上，PEMOAPO算法也獲得了最短的運行時間，MOEA/D-AAP是最耗時的算法，其次，CMOAPO和CCMO算法也比較耗時，最后，ICRMOAPO算法耗時最少，但它的綜合性能不佳。由于PEMOAPO算法在質量函數和虛擬力計算時需要耗費一定的時間，所以在大部分測試函數上沒有表現出最快的收斂速度。但考慮到分布性、收斂性方面出色的表現，這些少量的時間耗費是可以接受的。

5結束語

多目標優化問題廣泛存在于實際工程應用領域，同時，多目標問題的求解也面臨著很多挑戰，例如如何選擇合適的策略來降低算法的時間復雜度，如何提高解集的多樣性和收斂性。本文提出了一種分區引導種群進化的多目標擬態物理學優化算法，其中包括混沌映射和反向學習的種群初始化策略、質量函數修正規則和基于可行域和非可行域劃分的虛擬力修正規則。與其他APO算法相比，引入tent映射與反向學習相結合的策略進行種群的初始化，增強了種群的多樣性；個體質量的計算與個體的排序與約束違反度建立起直接關系，充分體現了多目標優化的特點；同時質量函數和虛擬力修正規則根據可行解和不可行解區分約束搜索和無約束搜索，加快了收斂速度，增強了種群的多樣性，能夠有效地解決多目標優化問題。

對提出的PEMOAPO算法從綜合性能評價指標以及統計結果等方面進行了較為全面的分析。當測試函數的維度固定時，PEMOAPO算法性能良好；當維度變化時，尤其是高維時，PEMOAPO算法的指標值隨維度升高而出現倒退情形。PEMOAPO算法在決策規模較大的多目標優化問題的求解性能還有待進一步提升，這是未來要解決的問題。

參考文獻：

［1］KumarS，ParhiDR，MuniMK，etal.Optimalpathsearchandcontrolofmobilerobotusinghybridizedsine-cosinealgorithmandantcolonyoptimizationtechnique［J］.IndustrialRobot，2020，47（4）：535-545.

［2］PrasadV，PawaskarDN，SeshuP.Controllerdesignandmulti-objectiveoptimizationofheavygoodsvehiclesuspensionsystembygeometry-inspiredGA［J］.StructuralandMulti-disciplinaryOptimization，2021，64（1）：89-111.

［3］WangPingquan，LiuXun，HanZheng.Multi-parameteronlineoptimizationalgorithmofBPneuralnetworkalgorithmininternetofthingsservice［J］.NeuralComputingandApplications，2021，33（2）：505-515.

［4］HanFei，ChenWentao，LingQinghua，etal.Multi-objectiveparticleswarmoptimizationwithadaptivestrategiesforfeatureselection［J］.SwarmandEvolutionaryComputation，2021，62（6）：100847.

［5］SoheiliS，ZokaH，AbachizadehM.Tunedmassdampersforthedriftreductionofstructureswithsoileffectsusingantcolonyoptimization［J］.AdvancesinStructuralEngineering，2021，24（4）：771-783.

［6］WangMingming，LiXiaoping，ChenLong.Anenhancemultimodalmultiobjectiveoptimizationgeneticalgorithmwithspecialcrowdingdistanceforpulmonaryhypertensionfeatureselection［J］.Compu-tersinBiologyandMedicine，2022，146：105536.

［7］SunJianyong，LiuXin，BackT，etal.Learningadaptivedifferentialevolutionalgorithmfromoptimizationexperiencesbypolicygradient［J］.IEEETransonEvolutionaryComputation，2021，25（4）：666-680.

［8］XieLiping，ZengJianchao，FormatoRA.Convergenceanalysisandperformanceoftheextendedartificialphysicsoptimizationalgorithm［J］.AppliedMathematicsamp;Computation，2011，218（8）：4000-4011.

［9］XieLiping，ZengJianchao，YangQiongqiong.Apredictableartificialphysicsoptimizationalgorithm［J］.InternationalJournalofComputingScienceandMathematics，2015，6（5）：459-470.

［10］謝麗萍，曾建潮.受擬態物理學啟發的全局優化算法［J］.系統工程理論與實踐，2010，30（12）：2276-2282.（XieLiping，ZengJianchao.Physicomimetics-inspiredglobaloptimizationalgorithm［J］.SystemsEngineering-Theoryamp;Practice，2010，30（12）：2276-2282.）

［11］王黎，蘇丹，王興偉.基于EDAPO優化算法的配電網重構［J］.東北電力大學學報，2012，32（3）：49-53.（WangLi，SuDan，WangXingwei.Adiscreteartificialphysicsoptimizationalgorithmbasedonestimationofdistributionappliestodistributionnetworkreconfiguration［J］.JournalofNortheastDianliUniversity，2012，32（3）：49-53.）

［12］李盛興，羅滇生，李一泉，等.改進擬態物理學算法在交直流系統無功優化中的應用［J］.電力系統保護與控制，2016，44（18）：115-119.（LiShengxing，LuoDiansheng，LIYiquan，etal.ReactiveoptimizationofhybridAC-DCpowersystembasedonimprovedAPO［J］.PowerSystemProtectionandControl，2016，44（18）：115-119.）

［13］ZhanXin，XiangTieyuan，ChenHongkun，etal.Vulnerabilityassessmentandreconfigurationofmicrogridthroughsearchvectorartificialphysicsoptimizationalgorithm［J］.InternationalJournalofElectricalPowerandEnergySystems，2014，62：679-688.

［14］王艷，曾建潮.一種基于擬態物理學優化的多目標優化算法［J］.控制與決策，2010，25（7）：1040-1044.（WangYan，ZengJianchao.Multi-objectiveoptimizationalgorithmbasedonartificialphysicsoptimization［J］.ControlandDecision，2010，25（7）：1040-1044.）

［15］孫寶，孫大剛，李占龍，等.基于序值與擁擠度的擬態物理學多目標算法［J］.系統工程與電子技術，2014，36（12）：2442-2448.（SunBao，SunDagang，LiZhanlong，etal.Artificialphysicsmulti-objectivealgorithmbasedonsequencevalueandcrowdingdegree［J］.SystemsEngineeringandElectronics，2014，36（12）：2442-2448.）

［16］孫寶，郭娜，李占龍，等.基于R2指標的擬態物理學約束多目標優化算法［J］.兵器裝備工程學報，2022，43（8）：186-192.（SunBao，GuoNa，LiZhanlong，etal.Artificialphysicsconstrainedmulti-objectiveoptimizationalgorithmbasedonR2indicator［J］.JournalofOrdnanceEquipmentEngineering，2022，43（8）：186-192.）

［17］張建新，李昆.基于濾子擬態物理學算法的多目標優化［J］.計算機仿真，2019，36（5）：295-299.（ZhangJianxin，LiKun.Physicomimeticsmethodformultiobjectiveoptimizationbasedonfiltermethod［J］.ComputerSimulation，2019，36（5）：295-299.）

［18］王艷.多目標擬態物理學優化算法及其應用研究［D］.蘭州：蘭州理工大學，2011.（WangYan.Researchonmulti-objectivemimicryphysicsoptimizationalgorithmanditsapplication［D］.Lanzhou：LanzhouUniversityofTechnology，2011.）

［19］王艷，張嘉琳，趙洪山.基于tent映射NSGA-Ⅱ算法的微電網多目標優化方法［J］.科學技術與工程，2022，22（14）：5643-5652.（WangYan，ZhangJialin，ZhaoHongshan.Multi-objectiveoptimizationmethodofmicrogridbasedontentmappingNSGA-Ⅱalgorithm［J］.ScienceTechnologyandEngineering，2022，22（14）：5643-5652.）

［20］FanQian，ChenZhenjian，LiZhao，etal.Anewimprovedwhaleoptimizationalgorithmwithjointsearchmechanismsforhigh-dimensionalglobaloptimizationproblems［J］.EngineeringwithComputers，2021，37（3）：1851-1878.

［21］OuyangChengtian，ZhuDonglin，QiuYaxian.Lenslearningsparrowsearchalgorithm［J］.MathematicalProblemsinEngineering，2021，2021（2）：9935090.

［22］MaZhongwei，WangYong.Evolutionaryconstrainedmultiobjectiveoptimization：testsuiteconstructionandperformancecomparisons［J］.IEEETransonEvolutionaryComputation，2019，23（6）：972-986.

［23］QiaoJunfei，ZhouHongbiao，YangCuili，etal.Adecomposition-basedmultiobjectiveevolutionaryalgorithmwithangle-basedadaptivepenalty［J］.AppliedSoftComputing，2019，74：190-205.

［24］TianYe，ZhangTao，XiaoJianhua，etal.Acoevolutionaryframeworkforconstrainedmulti-objectiveoptimizationproblems［J］.IEEETransonEvolutionaryComputation，2021，25（1）：102-116.