一種帶有三重選擇機制的多種群多策略差分進化算法

摘 要：針對差分進化算法（differential evolution，DE）在尋優過程中易陷入局部最優以及求解精度不高的問題，提出一種帶有三重選擇機制的多種群多策略差分進化算法（TSMDE）。該算法采用分層種群結構，利用適應度值將種群劃分為三個子種群，且子種群的大小隨迭代動態調整。同時，采用五個改進的突變策略以及不同的參數自適應方式，以滿足個體在不同進化階段的開發與探索需求。為了充分發揮多種群的優勢，提出一種高效的信息共享機制——三重選擇機制。各子種群先根據不同模式選擇執行突變的個體，然后該個體根據自身進化狀態選擇合適的突變策略，最后判斷出該個體處于停滯狀態后從兩個外部存檔中選擇一個候選解進行替換，最終通過三重選擇機制引導整個種群的進化進程。最后，將TSMDE與13個先進的差分進化（DE）變體進行對比，以驗證TSMDE的有效性。在CEC2014測試集中的30個基準函數上的實驗結果表明，該算法在求解精度、避免陷入局部最優等方面的能力優于或比得上這13個先進算法。

關鍵詞：差分進化；分層種群；多策略；三重選擇機制；參數自適應

中圖分類號：TP301.6"" 文獻標志碼：A"" 文章編號：1001-3695（2025）03-020-0795-09

doi：10.19734/j.issn.1001-3695.2024.09.0316

Multi-population multi-strategy differential evolution algorithm with triple selection mechanism

Song Xiaoyu，Li Min，Zhao Ming

（School of Computer Science amp; Engineering，Shenyang Jianzhu University，Shenyang 110168，China）

Abstract：To address the issue of the differential evolution（DE）algorithm falling into local optima and achieving low solution accuracy during the optimization process，this paper introduced a multi-population multi-strategy differential evolution algorithm（TSMDE）with a triple selection mechanism.The algorithm adopted a hierarchical population structure，dividing it into three sub-populations based on fitness values，and dynamically adjusted the size of each sub-population as iterations progress.Meanwhile，it applied five improved mutation strategies as well as different parameter adaptive approaches to balance exploitation and exploration for individuals at different evolutionary stages.In order to fully utilize the advantages of multiple populations，it implemented an efficient information-sharing process via the triple selection mechanism.In this mechanism，each sub-population first selected an individual to mutate using different modes.Then，the individual chose a suitable mutation strategy based on its evolutionary state，and finally，it selected a candidate solution from two external archives to replace the target vector when stagnation was detected.This guided the evolutionary process of the entire population.Finally，it compared TSMDE with 13 advanced DE variants to validate its effectiveness.Experimental results on 30 benchmark functions from the CEC2014 test set demonstrate that the proposed algorithm achieves better or comparable performance in both solution accuracy and avoiding local optima compared to the 13 advanced algorithms.

Key words：differential evolution;stratified populations;multiple strategies;triple selection mechanism;adaptive parameters

0 引言

受自然界生命優化以及某群體行為活動的啟發，一些研究人員提出了一系列非導數求解的優化方法，如文獻［1］提出的差分進化算法。DE因其結構簡單、性能優良等特點，在很多實際優化問題中得到了應用，如圖像處理、衛星通信等領域［2］。雖然差分進化算法在許多問題領域都表現出色，但它也存在一些不足之處，比如在進行復雜問題優化時易陷入局部最優，出現過早收斂等現象［2，3］。針對如何改善算法性能，國內外研究人員提出了許多不同的解決方法。

通過改進突變策略以及策略選擇方式來引入更多隨機變化，可以增強算法探索能力。Meng等人［4］提出了一種新的基于歷史種群的突變策略，從歷史信息中獲得信息以指導種群的進化。Mallipeddi等人［5］提出了一種集成突變策略和控制參數的算法。其中，不同的突變策略池和控制參數池在整個進化過程中共存，并競爭產生后代。

為了在進化過程中自適應調整種群多樣性，Tanabe等人［6］提出了一種種群大小線性縮減方式，種群規模按照線性函數不斷減小。Meng等人［7］提出了一種先進的參數自適應學習機制，將控制參數F和CR劃分為不同的組，避免好的F匹配到不好的CR，從而避免進化過程中的錯誤相互作用。

通過改良某操作階段或設計一種強化優化的機制，能夠提高算法性能。Zeng等人［8］提出了一種新的選擇操作，若新生成的實驗向量比目標向量差且個體處于停滯狀態時，從三個候選向量中選擇一個替換目標向量。

不同的優化策略在不同問題或搜索空間的不同區域可能表現各異，一些善于探索，一些善于開發［9］。通過劃分種群可實現多策略集成［10］，綜合利用各個策略的優點。不同種群采用不同的策略，使算法可以更有效地探索搜索空間，即使某些策略在某些情況下失效，其他策略仍然可能找到滿意的解，從而提高收斂速度和尋優效率。比如，Deng等人［10］基于區域約束階躍劃分機制，將親本種群劃分為三個重點不同的子種群，根據個體的適應度值以及進化過程來確定每個子種群的大小，以滿足不同進化階段的探索和開發需求。

盡管現有的研究成果在解決某些優化問題時表現出色，但在面對多模態或復雜約束問題時，可能面臨過早收斂或易陷入局部最優的困境［11］。鑒于此，探索一種具有更強穩定性和魯棒性的差分進化算法變得尤為迫切。通過分析相關文獻［5，10，11］，可以發現單一突變策略的優化算法在處理復雜搜索空間時往往效率不足。為此可以引入多種群機制，通過不同種群執行多樣化的突變策略，增加解的多樣性，降低早熟收斂的風險。此外，不同突變策略在不同問題或搜索空間的不同區域表現各異，可以組合多種策略，綜合利用各個策略的優點，從而提高搜索效率。為進一步提升算法的開發能力，對于精英子種群，可通過集中資源在有潛力的優質個體上，進行局部區域的深度搜索。最后，可以利用外部存檔中的個體替換處于停滯狀態的個體來維持種群多樣性。通過這些機制的引入，預計改進后的算法能夠更好地應對復雜優化問題中的早熟和局部最優問題，能夠更好地平衡探索與開發。

綜合上述討論，本文提出了一種基于適應度分組的帶有三重選擇機制的多種群多策略差分進化算法。在本算法中，將種群基于適應度值劃分為三個子種群，根據所處進化過程，動態調整各子種群的大小，以充分利用計算資源、增強算法的穩定性。同時，不同子種群采用不同的突變策略并為每個子種群匹配不同的參數自適應方式，來動態調整不同子種群中個體的控制參數值，以滿足不同個體在不同進化階段的開發與探索需求。為了充分發揮多子種群的優勢，本文提出一種高效的信息共享機制——三重選擇機制。通過突變個體選擇機制、突變策略選擇機制以及停滯個體替換向量選擇機制來引導整個種群的進化進程，提高算法求解精度、避免陷入局部最優。

3 實驗分析

本章為了評估提出算法TSMDE的性能，將TSMDE與七個種群規模固定的算法、六個種群規模動態調整的算法進行比較。使用CEC2014測試集評估算法在各種不同類型函數上的尋優能力。其中：f1～f3屬于單峰函數；f4～f16是簡單的多模態函數；f17～f22屬于混合函數；f23～f30屬于組合函數。

3.1 實驗設置

為了更好地評估本文算法的性能，本文選擇兩組算法進行比較，一組種群規模固定的七個DE變體（JADE［16］、EPSDE［5］、CIPDE［17］、PALMDE［7］、TPDE［10］、RNEGDE［18］和SHADE［14］）和一組種群規模動態調整的六個DE變體（LSHADE［6］、jSO［19］、EBLSHADE［20］、LPALMDE［7］、APSDE［21］和Hip-DE［4］）。

為了減少單次運行的隨機性影響，對于每個測試問題，各算法均獨立運行51次，每次的終止條件是評估次數達到最大值（maxFEs=10 000D，D=30、50、100）時停止運行，記錄51次運行結果的均值和方差作為該算法在該測試問題上的實驗結果。然后采用兩種非參數統計檢驗方法（即Friedman和Wilcoxon符號秩檢驗）對實驗結果進行統計比較分析，并繪制函數收斂曲線圖展示各算法找到最優解的速度。

3.2 比較與討論

3.2.1 均值和方差

在本部分中，將TSMDE與十三種DE變體進行比較。各算法參數設置與原始文獻推薦參數一致。本文種群大小設置為200，歷史存檔H為30，更新失敗、成功次數上限分別為48、5。

1）與七個種群規模固定的DE變體比較

表1、2分別給出了本文算法與七個種群規模固定的DE算法在30和100維時的Wilcoxon符號秩驗和Friedman檢驗的比較結果，以及在各函數上獲得的適應度值的均值與標準差。由于篇幅有限，50維的實驗數據將不進行展示。其中，加粗數據表示最優。R+、R-表示TSMDE優于、差于被比較算法的測試問題的排名之和。+、=、-分別表示TSMDE表現優于、相似于和差于被比較算法的函數個數。F_ave和rank分別表示各算法在30個函數上的平均排名值和算法的最終排名。

從表1中可以看出，對于30維函數，TSMDE的尋優精度和穩定性在23、22、15、18、18、22和21個函數上分別優于JADE、EPSDE、RNEGDE、SHADE、CIPDE、PALMDE和TPDE。從統計結果看出，對于JADE、EPSDE、PALMDE和TPDE，秩和檢驗的p值均小于0.05，且R+值遠大于R-值，因而，TSMDE顯著優于這些算法。各算法的平均排名分別為5.366 7、6.05、3.60、3.816 7、4.616 7、4.983 3、4.616 7和2.82。本文算法排名第一。

在100維時，從表2可以看出，TSMDE的尋優精度和穩定性在22、27、20、19、18、19和25個函數上分別優于JADE、EPSDE、RNEGDE、SHADE、CIPDE、PALMDE和TPDE。對于JADE、EPSDE和TPDE，秩和檢驗的p值均小于0.05，且R+值遠大于R-值，因而，TSMDE顯著優于這些算法。各算法的平均排名分別為4.166 7、7.066 7、4.116 7、3.95、4.55、4.983 3、4.42、2.75。本文算法排名第一。

2）與6個種群規模動態調整DE變體比較

表3給出了本文算法與六個種群規模動態調整算法在50維時的實驗結果。由于篇幅有限，30維和100維的實驗數據將不進行展示。對于50維優化，各算法（LSHADE、jSO、APSEDE、LPALMDE、EBLSHADE、Hip-DE和TSMDE）在30個基準函數上的平均排名分別是4.20、3.82、4.10、4.68、4.08、3.37和3.72。本文提出的算法排名第二，僅次于Hip-DE。

雖然Friedman檢測結果顯示本文算法落后于Hip-DE，但從表3中的Wilcoxon符號秩檢驗結果來看，對于50維問題，與Hipde相比，TSMDE得到的R+（174）大于R-值（126）。并且在30個基準函數中分別在19、17、14、22、20和18個函數上優于或相似于LSHADE、jSO、APSDE、LPALMDE、EBLSHADE和Hip-DE。

此外，由Wilcoxon檢驗結果可知，對于兩個不同維的優化問題，TSMDE和六個被比較算法相比，p值并無明顯差異，TSMDE與它們相比具有很強的競爭力。主要因為TSMDE采用三重選擇機制，通過將資源集中在少數高質量個體上來提高算法開發能力，通過選用不同外部存檔個體替換停滯個體來增強算法避免陷入局部最優的能力。

3.2.2 收斂圖

本實驗中，繪制了本文算法與七個種群規模固定算法在CEC2014測試集的4個基準函數上的適應度均值的收斂曲線圖（30D），如圖3所示。其中f3屬于單峰函數，f11屬于簡單多模函數，f17屬于混合函數，f30屬于組合函數，選取有代表性的函數可以反映算法在不同類型函數上的收斂性。

由圖3可以看出，在f3上TSMDE在早期的整體收斂速度比SHADE、CIPDE、EPSDE、RNEGDE和PALMDE慢，但比TPDE和JADE快。在f11上在前期收斂速度比CIPDE收斂慢。在f17、f30上在前期TSMDE僅比TPDE收斂速度快。主要原因如下，TSMDE采用子種群規模動態調整策略。在早期NPA數量少，NPB和NPC數量多，有助于維持種群多樣性，因而在一定程度上削弱早期的搜索速度。但相同評估次數內，在這些不同類型的函數上，與對比算法相比，TSMDE能收斂到更好的值。

3.2.3 參數敏感性分析

本節對算法的核心參數進行敏感性分析，比較不同參數設置下的均值和標準差。

a）將種群規模分別設置為100、150、200和250進行實驗驗證，實驗結果表明當NP為200時，算法性能最好。記錄個體連續更新失敗的次數T來判斷處于停滯個體并進行替換，有助于維持種群多樣性并減少資源浪費。將更新失敗限制次數T分別設置為30、48、70和100進行實驗，結果表明當T為48時，算法性能最好。

b）為了在迭代初期更好維持種群多樣性，精英種群的個體數量NPA不宜過大且不應大于NPC，而NPC不宜過小。將k1、k2和k3分別設置不同值，［k2×NP，k1×NP］和［k1×NP，k3×NP］對應NPA和NPC的不同數量區間［Amin，Amax］和［Cmin，Cmax］（即［16NP，14NP］和［14NP，310NP］、［15NP，720NP］和［720NP，25NP］、［14NP，920NP］和［920NP，12NP］、［13NP，920NP］和［920NP，35NP］），并比較實驗結果。從表4可以看出，第Ⅰ組k2設置偏小，第Ⅲ、Ⅳ組k2和k3偏大，計算資源分配不均，不能更好平衡開發與探索，因此僅在f1、f6和f27上表現最優。對于幾種不同類型函數，第Ⅱ組綜合表現最好。故而本文算法中k1、k2和k3分別為720、15和25。

c）將γ分別設置為3、4、5、6和7進行實驗。當γ設置較大，個體因連續多次突變更容易被增強，在局部搜索中更容到更優解，使算法在f13、f16和f29上表現較好，但也增加陷入局部最優的可能性。當γ設置較小，由于計算資源分散到更多個體，局部搜索深度不足，使得算法對f1、f6和f8的求解精度下降。考慮到隨著問題維數的增加，算法應適度減小γ以便更多個體有機會執行搜索，以此增加搜索空間覆蓋率。因此，綜合考慮本文算法中γ取值為5。

3.2.4 策略有效性分析

不同種群結構適用的問題類型不同，為了驗證子種群劃分及其動態調整策略的有效性和對TSMDE整體性能的影響，定義了其他三個版本的TSMDE與其進行對比實驗。其中：TSMDE-Ⅰ采用固定子種群（三子種群大小一樣，即NP/3）；TSMDE-Ⅱ中A、C兩組個體數量均線性增加，使用式（5）更新；而TSMDE-Ⅲ中A、C的大小均線性減少，使用式（6）更新。實驗結果如表5所示，相同結果未展示。相比于另外三個版本，TSMDE算法在多峰、混合甚至組合函數上都有良好表現，求解精度和穩定性均表現更優，充分說明TSMDE的調整策略與函數特性匹配度更高，能更好地適應這些函數不同階段的優化需求。

3.2.5 算法時間復雜度

對于時間復雜性，遵循2014年進化計算大會測試套件的指導。使用三個變量T0、T1和T m2進行評估［3］。其中T0表示在CEC2014測試套件中基本算術表達式的耗時，T1表示在CEC2014測試套件中對基準函數f18進行30D優化在20萬評估次數內的耗時，T2表示算法在30D下在20萬評估次數內優化f18的總成本。使用Tc=（T m2-T1）/T0評估各算法的復雜度，T m2分別表示獨立運行5次的T2的均值。TSMDE與各算法的時間復雜度比較如表6所示。可以看到，TSMDE算法消耗時間比JADE、SHADE、PALMDE和TPDE多，但這是必要的，因為整體性能有很大提高。

以上實驗表明，TSMDE在求解精度等方面的能力優于或比得上七個種群規模固定DE變體（即JADE、EPSDE、RNEGDE、SHADE、CIPDE、PALMDE和TPDE）以及六個種群規模動態變化DE變體（即LSHADE、jSO、APSDE、LPALMDE、EBLSHADE和Hip-DE），這是因為在TSMDE中不同子種群采用不同的突變策略和參數自適應方式，可更有效地探索搜索空間，從而提高算法找到全局最優解的概率。三重選擇機制的應用不僅提高了算法求解精度，而且提升了算法避免陷入局部最優的能力。

4 結束語

本文提出了一種新的TSMDE算法，該算法通過子群劃分及其動態調整機制，使算法既能在早期保持種群多樣性，又能在后期提高開發能力。該算法中不同子種群使用不同突變策略和參數自適應方式，使算法能夠更好地滿足不同進化階段的探索與開發需求。該算法還提出三重選擇機制，其中的個體選擇機制使精英種群將更多的計算資源集中到有潛力的個體上，從而促使算法在局部區域進行深入搜索。其中的停滯個體的替換個體選擇機制——選用不同外部存檔中的個體替換處于停滯狀態的個體，提高了算法跳出局部最優的能力。本文算法在提高算法探索能力的同時保持較強的開發能力，使算法的優化效率明顯提升。未來的研究工作將嘗試引入種群動態調整機制，以進一步提高算法的性能。本文算法在實驗環境下表現出了較好的尋優性能，因此，在未來工作中，筆者還計劃將該算法應用到實際的車間調度問題中，進一步驗證其在實際工程中的適用性與效果。為此，筆者正在收集和整理車間調度相關數據，以構建真實的優化場景。通過將改進算法應用于實際問題，希望能進一步提升調度系統的優化效率，為工程應用提供可行的解決方案。

參考文獻：

［1］Storn R，Price K.Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces［D］.［S.l.］：International Computer Science Institute，1995.

［2］丁青鋒，尹曉宇.差分進化算法綜述［J］.智能系統學報，2017，12（4）：431-442.（Ding Qingfeng，Yin Xiaoyu.Research survey of diffe-rential evolution algorithms［J］.CAAI Trans on Intelligent Systems，2017，12（4）：431-442.）

［3］左汶鷺，高岳林.基于隨機鄰域變異和趨優反向學習的差分進化算法［J］.計算機應用研究，2023，40（7）：2003-2012.（Zuo Wenlu，Gao Yuelin.Differential evolution algorithm based on random neighborhood mutation and optimal opposition-based learning［J］.Application Research of Computers，2023，40（7）：2003-2012.）

［4］Meng Zhenyu，Yang Cheng.Hip-DE：historical population based mutation strategy in differential evolution with parameter adaptive mechanism［J］.Information Sciences，2021，562：44-77.

［5］Mallipeddi R，Suganthan P N，Pan Q K，et al.Differential evolution algorithm with ensemble of parameters and mutation strategies［J］.Applied Soft Computing，2011，11（2）：1679-1696.

［6］Tanabe R，Fukunaga A S.Improving the search performance of SHADE using linear population size reduction［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2014：1658-1665.

［7］Meng Zhenyu，Pan J S，Kong Lingping.Parameters with adaptive learning mechanism（PALM）for the enhancement of differential evolution［J］.Knowledge-Based Systems，2018，141：92-112.

［8］Zeng Zhiqiang，Zhang Min，Chen Tao，et al.A new selection operator for differential evolution algorithm［J］.Knowledge-Based Systems，2021，226：107150.

［9］Adam S P，Alexandropoulos S N，Pardalos P M，et al.No free lunch theorem：a review［M］//Approximation and Optimization.Cham：Springer International Publishing，2019：57-82.

［10］Deng Libao，Li Chunlei，Han Rongqing，et al.TPDE：a tri-population differential evolution based on zonal-constraint stepped division me-chanism and multiple adaptive guided mutation strategies［J］.Information Sciences，2021，575：22-40.

［11］Li Yuzhen，Wang Shihao，Yang Hongyu，et al.Enhancing differential evolution algorithm using leader-adjoint populations［J］.Information Sciences，2023，622：235-268.

［12］Liu Dong，He Hao，Yang Qiang，et al.Function value ranking aware differential evolution for global numerical optimization［J］.Swarm and Evolutionary Computation，2023，78：101282.

［13］Cui Laizhong，Li Genghui，Lin Qiuzhen，et al.A novel artificial bee colony algorithm with depth-first search framework and elite-guided search equation［J］.Information Sciences，2016，367：1012-1044.

［14］Tanabe R，Fukunaga A.Evaluating the performance of SHADE on CEC 2013 benchmark problems［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2013：1952-1959.

［15］Draa A，Bouzoubia S，Boukhalfa I.A sinusoidal differential evolution algorithm for numerical optimisation［J］.Applied Soft Computing，2015，27：99-126.

［16］Zhang Jingqiao，Sanderson A C.JADE：adaptive differential evolution with optional external archive［J］.IEEE Trans on Evolutionary Computation，2009，13（5）：945-958.

［17］Zheng Liming，Zhang Shengxin，Tang K S，et al.Differential evolution powered by collective information［J］.Information Sciences，2017，399：13-29.

［18］Yang Qiang，Yan Jiaqi，Gao Xudong，et al.Random neighbor elite guided differential evolution for global numerical optimization［J］.Information Sciences：an International Journal，2022，607：1408-1438.

［19］Brest J，Maucˇec M S，Bokovicˇ B.Single objective real-parameter optimization：algorithm jSO［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2017：1311-1318.

［20］Mohamed A W，Hadi A A，Jambi K M.Novel mutation strategy for enhancing SHADE and LSHADE algorithms for global numerical optimization［J］.Swarm and Evolutionary Computation，2019，50：100455.

［21］Wang Minghao，Ma Yongjie，Wang Peidi.Parameter and strategy adaptive differential evolution algorithm based on accompanying evolution［J］.Information Sciences，2022，607：1136-1157.