雙子群自適應變異多目標粒子群算法

摘 要：多目標粒子群優化算法因其強大的搜索能力和簡單的實現方式受到廣泛關注，然而它在收斂性和多樣性之間常常存在不平衡的問題。為了解決這一問題，作者提出了一種雙子群自適應變異多目標粒子群算法（BAMOPSO），旨在更好地平衡收斂性和多樣性。首先，采用一種新穎的雙子群初始化方法，使粒子在目標空間中分布更均勻，從而提高算法的多樣性。其次，設計了一種新的自適應變異策略，依據進化過程中目標函數值的變化來提升收斂性。最后，通過將BAMOPSO算法與六個經典多目標優化算法在十五個基準測試函數上進行比較實驗，驗證了該算法在平衡收斂性和多樣性方面的顯著提升。

關鍵詞：多目標粒子群優化算法；雙子群；自適應變異；

中圖分類號：TP18" " " " " " " " " " " " " " " " " " " " " " " " " " " 文獻標識碼：A文章編號：1009-3583（2024）-0086-08

Binary Group Adaptive Variation Multi-objective Particle Swarm Optimization Algorithm

CHEN Jian-jie1， LIU Yan-min2*， LUO Yi3

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

Abstract： Multi-objective particle swarm optimization has been widely concerned because of its powerful search ability and simple implementation， but it often has an imbalance between convergence and diversity. To solve this problem， a binary group adaptive variation multi-objective particle swarm optimization （BAMOPSO） algorithm is proposed to better balance convergence and diversity. Firstly， a novel binary group initialization method is used to make the particles more evenly distributed in the target space， thus improving the diversity of the algorithm. Secondly， a new adaptive variation strategy is designed to improve the convergence according to the change of the objective function value during evolution. Finally， by comparing BAMOPSO algorithm with six classical multi-objective optimization algorithms on 15 benchmark functions， it is verified that the algorithm has a significant improvement in balance convergence and diversity.

Keywords： multi-objective particle swarm optimization algorithm; binary group; adaptive variation

粒子群優化（Particle swarm optimization， PSO）[1]最早由Eberhart和Kennedy于1995年提出。PSO是一種基于群體智能的優化算法，它通過模仿鳥類等生物的社會行為來尋找最優解。與鳥一樣，PSO中的候選解（也稱為粒子）通常由兩個關鍵部分組成：飛行速度和當前位置，它們根據自身的飛行歷史信息和整個社會群體在進化過程中的飛行經驗進行動態調整。由于其結構和實現的簡單性，粒子群算法具有許多優點，不僅在目標函數優化、神經網絡訓練等各種數學優化領域表現出良好的性能，而且在工程優化中的制造控制、云計算中的多源調度等諸多實際優化問題中得到廣泛應用。然而，與其他經典群智能優化算法一樣，粒子群優化算法也存在收斂性和多樣性不平衡的問題，特別是在處理大規模復雜優化問題時。

現實生活中存在的問題往往和理想狀態下設想的問題相差很大，實際工程優化中的制造控制、云計算中的多源調度等諸多實際優化問題，多數都存在多個難以平衡相互沖突的目標，即多目標優化問題（Multi-objective Optimization Problems，MOPs）[2，3]。為了更好處理現實生活中遇到的諸多多目標問題，Coell和Lechuga等將原先的單目標優化問題（Particle swarm optimization， PSO）改進拓展為多目標粒子群算法（Multi-objective Particle Swarm Optimization ， MOPSO）[4]。從單目標到多目標的擴展雖然在很多方面大大優化了求解中的很多問題，然而這種擴展也不可避免地引出了新的MOPSO問題，即算法的解在收斂性和多樣性方面很容易失衡。為了得到更好的多目標優化算法，研究者們設計了很多不同的策略來解決收斂性和多樣性不平衡的問題，這也為多目標粒子群優化算法提供了新的研究方向。

為了更好平衡收斂性和多樣性，提高粒子群算法的性能，人們提出了多種策略。最近興起了一種通過修改原始隨機初始化種群而選擇自定義初始化種群的方法來增加種群多樣性，研究者通過特定的方法產生一個或多個種群來達到增加種群多樣性的目的。Chao Wang[5]等提出了一種基于雙種群的進化算法，其中一個種群用于位置優化，另一個種群用于半徑優化。這兩個種群在進化過程中迭代交換從精英解中獲得的信息，協同搜索問題的最優解。Bui[6]等在所提算法DPP2中，試圖讓種群達到這兩個標準，但為這些標準設定的優先級有所不同。一個種群的重點是實現更好的收斂性（通過使用基于帕累托的排序方案），另一個種群的重點是確保種群的多樣性（通過使用基于分解的方法）。之后，通過合作機制將兩個種群進行融合，形成一個新的組合種群，希望使種群同時具有收斂和多樣性的特征。Li[7]等提出了一種基于雙種群的大規模多目標優化算法LSTPA。在該算法中，將解分為兩個子種群：收斂子種群（CP）和多樣性子種群（DP），分別以提高種群收斂和多樣性為目標。

可以看出，為了豐富和提升種群多樣性和收斂性，學者們對種群進行了不同的劃分和改進，通過這些操作很大程度上豐富和增強了種群的多樣性和收斂性。此外，另一批學者選擇另辟蹊徑，企圖通過操作變異手段來提升種群的多樣性和收斂性平衡。Tao[8]等提出了一種基于多尺度自適應協同突變策略的粒子群優化算法（MSCPSO）。在該方法中，采用不同標準差的多尺度高斯突變，以提高充分搜索整個解空間的能力。在采用的多尺度突變策略中，大尺度突變可以使種群在早期探索全局解空間，快速找到較優解區域，從而避免過早收斂，同時加快收斂速度，而小尺度突變可以使種群在后期更準確地挖掘局部最優解區域，從而提高最終解的準確性。Yang[9]等在改進的粒子群優化算法中引入自適應變異，提高了粒子群優化算法的收斂性和多樣性平衡。突變概率根據種群適應度的方差進行調整。采用非線性遞減策略調整慣性權值，增強搜索能力，使其能夠放棄局部最優解而找到全局最優解。

綜合前述改進策略，本文提出了一種雙子群自適應變異多目標粒子群算法（BAMOPSO），旨在提高種群的平衡收斂性和多樣性。首先，利用均勻采樣和拉丁超立方體采樣方法生成兩個子群。其次，根據種群進化中目標函數值標準差的變化情況，設計了一種自適應突變策略。最后，將提出算法BAMOPSO與六個經典多目標優化算法在十五個基準測試函數上進行實驗結果比較，驗證了所提出的算法對平衡收斂性和多樣性有明顯提升。

1" "基本概念

1.1" 多目標優化問題

通常多目標優化問題都是以最小化問題為例，對于最大化問題通過取相反數的形式化為最小化問題進行求解。由于多目標優化問題的多準則性質，解的“最優性”必須重新定義，從而產生了帕累托最優性的概念。與單目標優化情況相反，多目標優化問題的特點是權衡，因此，有大量的帕累托最優解。

1.2" 粒子群優化

2" "算法設計

2.1" 雙子群初始化

現有的大多數MOPS算法基本上初始化種群都采用隨機初始化，這會導致搜索空間中的粒子分散不均勻從而陷入局部最優。本文利用均勻采樣（Uniform Sampling，縮寫US）和拉丁超立方采樣（Latin Hypercube Sampling，縮寫為LHS）來分別生成兩個子群，然后將兩個子群合并為一個主種群來增加種群多樣性。

均勻采樣（US）能夠確保粒子在搜索空間的均勻覆蓋，避免了某些區域的過度集中，其實現簡單，易于操作和理解。通過均勻覆蓋整個搜索空間，減少陷入局部最優的可能性。假設有N個樣本，每個樣本有M個維度，則均勻采樣（US）公式為：xi，j～U（0，1），其中xi，j為樣本在目標空間中的每個維度j∈{1，2，…，M}上均勻分布生成的，i∈{1，2，…，M}為每個樣本的索引。將生成的樣本從單位區間[0，1]映射到目標空間的實際范圍[targetmin，targetmax]產生目標粒子：

我們利用均勻采樣（US）生成的第一個子群PA和拉丁超立方體采樣（LHS）生成的第二個子群PB合并后得到主種群P，種群P綜合兩子群的優點，均勻采樣提供了廣泛且均勻的搜索空間覆蓋，而拉丁超立方體采樣確保每個維度的樣本分布均勻。這種組合方法提高了搜索的全面性，增強全局探索能力，減少局部最優的影響，從而提升優化算法的性能。

2.2" 自適應變異策略

目前普遍使用的變異方式大多是無規律隨機變異，這種變異無法根據搜索環境控制變異程度，往往會把一個優的粒子變異為一個劣的粒子導致算法性能變差。本文提出了一種根據粒子群在搜索過程中的目標函數值標準差變化情況自適應改變變異率，從而提升了算法的收斂性。

如圖 1函數值對應圖中我們可以看出雖然函數值均值最貼合收斂距離，但由于迭代后期均值基本保持不變這違背我們需要的變異期望（我們希望迭代后期對粒子進行擾動）。因此，函數值的標準差是最優反映了收斂到真實帕累托前沿變化情況，我們可以利用函數值的標準差來動態調整變異過程的變異率。

當檢測到當前代種群位于優的位置時，下一次迭代就減小這個粒子的變異率。反之，當種群在當前代位于劣的位置則在下一次迭代中增加變異率。而判斷種群位置的優劣則通過計算目標函數值的標準差衡量，將當前代目標函數的標準差與上一代目標函數標準差進行比較來調節適合的變異率。首先，將第一次種群初始化后的目標函數值計算其標準差記為S0，再把種群第一次迭代的目標函數值記為S1，計算絕對值標準差：€%]=€HLS1-S0€HL。其次，根據€%]的變化情況設置相應的變異率，計算公式如下：

2.3 算法步驟

3" "仿真實驗與結果分析

3.1" 性能指標

3.2" 實驗設計

本文將五個ZDT[13]基準測試函數和十個UF[14]基準測試函數用于評估本文提出的BAMOPSO算法的性能。這些測試問題都具有不同的復雜特征和形狀，能夠更為全面評估算法的性能。為了驗證提出算法的性能，使用了擁有較強競爭力的NMPSO[15]、MPSOD[16]、MOEADD[17]、NSGAIII[18]、SPEAR[19]、MOPSO[4]六個經典的多目標優化算法進行比較。

3.3" 實驗參數設置

本文使用了雙目標測試函數ZDT系列、UF系列以及三目標測試函數UF8-UF-10來驗證算法的綜合性能，本文通過將所有對比算法的參數都與原算法保持一致來保證各個算法之間更具有可比性和公平性。設置種群規模為200，外部存檔的閾值也為200，最大評估次數設置為10000，每個算法在每個測試函數上獨立運行30次。此外所有算法實驗數據都是在AMD Ryzen 7 4800U with Radeon Graphics 1.80 GHz、windows 11系統，MATLAB R2022b條件下實現的。對比算法的原代碼均由 PlatEMO[20]提供。

3.4" 實驗結果與分析

為了更好地驗證改進算法的綜合性能，本次實驗選擇了ZDT 系列和 UF 系列中的 15個基準測試函數進行測試。這些函數用于評估算法在不同條件下的表現，并通過表1、表2詳細分析實驗結果，以全面了解改進算法的實際效果和優越性。表1和表2顯示了算法NMOPSO、MPSOD、MOEADD、NSGAIII、SPEA、MOPSO和BAMOPSO在 ZDT和UF系列基準問題上獨立運行 30 次的IGD和HV的平均值及標準差結果。這些結果作為算法評估的標準，以平均值（mean）和標準差（std）形式表示，并且在IGD和HV上的最佳結果已加粗標出。

表1展示了包括經典算法MOPSO、MPSOD、NSGAIII、MOEADD 、SPEAR、NMPSO以及提出算法BAEMOPSO在ZDT和UF系列測試函數上的IGD指標的平均值和標準差。通過對這些數據的分析，可以看出改進算法BAEMOPSO在大多數測試函數中都取得了最佳的結果。盡管BAEMOPSO在ZDT6和UF1、2、4、5、6上的表現并不是絕對最優，但其最優結果個數依然多于其他六種經典算法。此外，BAEMOPSO在ZDT系列的測試函數中表現出顯著的優勢，得益于其使用了雙子群初始化種群和自適應變異策略。這兩種策略有效地提高了算法的收斂性和種群多樣性，從而在整體性能上取得了提升。結合表 1中的數據，我們可以得出結論：改進算法BAEMOPSO在所有15個測試函數中表現最為出色，相較于其他經典算法，具有明顯的優勢。這一結果不僅證明了BAEMOPSO算法的有效性，也展示了其在多目標優化問題中的良好性能。

表2展示了六種經典算法MOPSO、MPSOD、NSGAIII、MOEADD 、SPEAR、NMPSO，以及提出算法BAEMOPS在ZDT和UF系列測試函數（包括ZDT和UF系列）上的HV指標的平均值和標準差。從表2中可以直觀看出與其他六種經典算法相比，BAEMOPSO在十五個測試函數中有超過一半多的測試函數結果比其他算法優。總體而言， BAEMOPSO在所有15個測試函數上表現最佳，驗證了提出算法的優越性能，展示了其在多目標優化問題中的強大優化性能。

為了更直觀地展示算法性能差異，圖3展示了七個算法在ZDT1測試問題中收斂情況結果。這些圖表明了Pareto最優解在理想解附近的分布情況。具體來看，在ZDT1問題中，NMPSO 算法的Pareto最優解雖然接近理想解，但分布較為集中在中間區域，表現出多樣性較差的分布特征。與其相比，BAMOPSO算法的Pareto最優解不僅接近理想解，而且在理想解附近的分布較為均勻，明顯多樣性更好。相比于其他六個算法BAMOPSO的收斂性遠遠優于它們，這直觀展示了提出的算法具有較強競爭力。

圖4 展示了七個算法在ZDT3測試問題上的PF圖，與在ZDT1測試函數上情況一樣，雖然NMPSO在收斂到真實Pareto時表現很好，但也顯示了它的收斂都是局部最優的缺點，與之相比，本文所提出的算法BAMOPSO不僅能收斂到真實Pareto前沿而且分布更加均勻。此外，相比其他六種算法所提出的算法無論收斂性還是多樣性都表現出更優，這說明BAMOPSO算法的收斂性能和多樣性能都有更好的競爭力。

圖5展示了對比算法與提出的BAMOPSO算法在ZDT1和ZDT3問題上的IGD值收斂軌跡。通過圖中的信息，可以觀察到所有算法IGD值的變化趨勢，同時明顯可以看出，BAMOPSO算法的收斂速度相比對比算法更為迅速。

圖6展示了七種算法在ZDT系列問題上的IGD值箱型圖，其中1至7分別代表算法MOPSO、MPSOD、NSGAIII、MOEADD、SPEAR、NMPSO和BAMOPSO。從圖中可以觀察到各算法數據的離散分布情況，可以看出BAMOPSO算法的數據波動相對較小。

4" "結語

本文提出了一種新型的雙子群自適應變異算法，簡稱BAMOPSO算法，該算法采用不同的種群初始化方法和自適應變異技術。具體來說，BAMOPSO算法通過兩種特定的初始化方法來生成兩個不同的子種群，從而有效增加了整體種群的多樣性。另外，根據目標函數值的變化情況動態調整變異率，以提升算法的收斂性。為了驗證算法的有效性，將BAMOPSO與其他六種現有算法進行了標準測試基準問題的對比實驗。實驗結果表明，相較于其他算法，BAMOPSO在解決ZDT和UF系列測試問題時展現出了顯著的優勢，顯示出其在處理多目標優化問題方面的強大競爭力。

參考文獻：

[1]Kennedy J， Eberhart R. Particle swarm optimization[C]Pro- ceedings of the 1995 IEEE international conference on neural networks. ieee， 1995（4）： 1942-1948.

[2]Ali S， Ullah K， Hafeez G， et al. Solving day-ahead scheduling problem with multi-objective energy optimization for demand side management in smart grid[J]. Engineering Science and Technology， an International Journal， 2022（36）： 101135.

[3]XIONG G， SHUAI M， HU X. Combined heat and power economic emission dispatch using improved bare-bone multi- objective particle swarm optimization[J]. Energy， 2022， 244 （1）： 123108.

[4]COELLO C， LECHUGA S. MOPSO： a proposal for multiple objective particle swarm optimization [C].Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 （Cat. No. 02TH8600）. IEEE， 2002（ 2）： 1051-1056.

[5]Wang C， Wang Z， Tian Y， et al. A dual-population based evol- utionary algorithm for multi-objective location problem under uncertainty of facilities[J]. IEEE Transactions on Intelligent Transportation Systems， 2021， 23（7）： 7692-7707.

[6]Bui L T， Nguyen T T. A modified dual-population approach for solving multi-objective problems[C]. 21st Asia Pacific Symposium on Intelligent and Evolutionary Systems（IES）. IEEE， 2017： 89-94.

[7]Li B， Zhang Y， Yang P， et al. A two-population algorithm for large-scale multi-objective optimization based on fitness- aware operator and adaptive environmental selection[J]. IEEE Transactions on Evolutionary Computation， 2023.

[8]Tao X， Guo W， Li Q， et al. Multiple scale self-adaptive coop- eration mutation strategy-based particle swarm optimization[J]. Applied Soft Computing， 2020， 89： 106124.

[9]Yang H， Yang Z， Tian A， et al. Particle swarm optimization based on adaptive mutation and diminishing inerita weights[C]. 2013 Ninth International Conference on Natural Computa- tion （ICNC）. IEEE， 2013： 549-553.

[10]HAN H， LU W，QIAO J. An adaptive multiobjective particle " "swarm optimization based on multiple adaptive methods[J]. " IEEE Transactions on Cybernetics， 2017， 47（9）： 2754-2767.

[11]COELLO C A C， CORTES N C. Solving multiobjective op " "timization problems using an artificial immune system[J]. " Genetic Programming and Evolvable Machines，2005，6（2）： " "163-190.

[12]ZITZLER E， THIELE L. Multiobjective evolutionary algor- " ithms： a comparative case study and the strength Pareto ap- " proach[J]. IEEE Transactions on Evolutionary Computation， " 1999， 3（4）： 257-271.

[13]ZITZLER E， DEB K， THIELE L. Comparison of multi ob- " jective evolutionary algorithms： Empirical results[J]. Evol- " utionary Computation， 2000， 8（2）： 173-195.

[14]ZHANG Q， ZHOU A， ZHAO S， et al. Multiobjective optimi- " zation test instances for the CEC 2009 special session and " competition[J]. Mechanical engineering， 2008（264）： 1-30.

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

[16]DAI C， WANG Y， YE M. A new multi-objective particle " swarm optimization algorithm based on decomposition[J]. " Information Sciences， 2015（325）： 541-557.

[17]LI K， DEB K， ZHANG Q， et al. An evolutionary many-ob- " jective optimization algorithm based on dominance and de- " composition[J]. IEEE Transactions on Evolutionary Compu- " tation， 2014， 19（5）： 694-716.

[18]DEB K， JAIN H. An evolutionary many-objective optimiza- " tion algorithm using reference-point-based nondominated " sorting approach， part I： solving problems with box constra- " ints[J]. IEEE Transactions on Evolutionary Computation， " 2013， 18（4）： 577-601.

[19]JIANG，YANG S. A strength Pareto evolutionary algorithm " based on reference direction for multiobjective and many-ob- " jective optimization[J]. IEEE Transactions on Evolutionary " Computation， 2017， 21（3）： 329-346.

[20]TIAN Y， CHENG R， ZHANG X， et al. PlatEMO： A MATLAB " "platform for evolutionary multi-objective optimization [edu- " cational forum][J]. IEEE Computational Intelligence Maga- " zine， 2017， 12（4）： 73-87.

（責任編輯：羅東升）