基于動態平衡的多目標粒子群優化算法

張海波

摘 要： 傳統粒子群優化算法在求解動態優化問題時，種群將逐漸收斂，從而在問題變化后無法進一步尋優，針對上述問題，提出了一種基于動態平衡的多目標粒子群優化算法。采用雙種群策略以動態平衡算法的探索能力與開發強度，其中一個子種群在動態調整的網格中運行混沌搜索，確保種群多樣性符合要求的同時，能夠有效提升搜索的效率。利用快速收縮多目標粒子群算法，對另外的子種群進行計算，收斂到Pareto前沿。通過一組標準測試問題對所提方法進行了驗證，實驗結果顯示所提算法無論在收斂速度還是在優化精度上都優于其它典型多目標進化算法。

關鍵詞： 動態平衡; 混沌; 自適應網格; 多目標優化; 粒子群算法

中圖分類號： TP311

文獻標志碼： A

文章編號：1007-757X（2019）06-0150-04

Abstract： In the traditional particle swarm optimization algorithm for solving the dynamic optimization problem， the population will gradually converge， thus the algorithm may lose further optimization ability after the environment dynamically changes. In order to solve this problem， a dynamic adaptive grid is presented based on multi-objective particle swarm optimization. In the algorithm， a double-population strategy is designed to explore and develop intensity balance algorithm， one of the subpopulation runs for adaptive grid search， so as to ensure the population diversity and the adaptive mechanism to improve the search efficiency， another subpopulation uses multi-objective particle swarm algorithm for rapid contraction. The algorithm can rapidly converge to the Pareto front under environmental change. Through a set of standard test problems， the experimental results show that the proposed algorithm both in convergence speed and optimization accuracy are better than other typical multi-objective evolutionary algorithms.

Key words： Dynamic balance; Chaos; Adaptive grid; Multi-objective optimization; Particle swarm algorithm

0 引言

動態多目標優化問題集合了當前優化問題的兩個難點即需要優化的目標不僅為多個、相互沖突[1-3]，解決上述問題不僅需要算法能搜索到分布盡可能廣泛的Pareto最優解，而且還要快速適應環境變化，使優化結果能跟蹤Pareto最優前沿移動。

進化計算、粒子群優化算法等基于種群隨機搜索的自然啟發式算法被用來求解動態多目標優化問題[4]。這些算法與傳統算法之間的差異性總結為：第一，基于種群隨機搜索的目標優化算法能夠同時獲取多個Pareto最優解[5]。第二、這些算法對環境變化具有自適應能力，而不需要重新優化[6]。第三、不要求獲得模型信息，并且適用于求解計算復雜的優化問題[7]。

NSGA2是由Kalyanmoy Deb等人提出的多目標遺傳算法，其特點表現在三個方面，一是盡可能的減少用戶主觀決定的參數;二是非支配集排序時間復雜程度更低;三是維護精英個體，以便更加有效的提高多目標遺傳算法的效果。空間搜索是通過跟蹤當前最優粒子的方式來實現的，所以算法相對簡單、采用的參數少、算法計算速度較快[8]。Moore 和Chapman首次提出了粒子群優化算法在多目標問題求解方面的應用設想，并通過問題分析加以驗證[9]。傳統的進化算法、粒子群優化算法在求解動態優化問題時，在運算后期，種群慢慢收斂，無法獲取環境動態變化信息之后，就無法繼續尋優[10]。

本文針對上述問題，改進對多目標粒子群優化算法，提出MOEA-AR算法。采用雙種群策略以動態平衡算法的探索能力與開發強度，其中一個子種群在動態調整的網格中運行混沌搜索，確保種群多樣性符合要求并有效提升搜索的效率。利用快速收縮多目標粒子群算法，對另外的子種群進行計算，在環境變化后能快速收斂到Pareto前沿。通過一組標準測試問題對算法進行驗證，結果顯示所提算法在收斂速度和優化精度上都優于其它典型的多目標進化算法。

1 多目標優化概念

2 動態多目標粒子群優化算法

2.1 主程序

MOEA-AR算法不僅能夠保證種群多樣性，種群可以平展的擴散到Pareto前沿，提升算法收斂的效果，有效縮短最優結果尋找時間。MOEA-AR算法的流程和實施步驟如圖1所示。

第一步：算法初始化。在決策空間中，對種群之中的粒子位置嚴格給予隨機賦值，且粒子運動速度為零。粒子個體向導為其位置，檔案集為空。

第二步：種群的評價。判斷每個粒子在目標函數中的賦值情況，按照現有目標函數的取值將維度空間分為10個部分。

第三步：更新粒子個體向導。如果粒子運動目標值決定個體向導，那么粒子的當前位置就是該粒子的最新個體向導。如果目標值向量和個體向導之間不相互匹配，那么將個

體向導更新為當前位置，如果二者相互匹配，則不進行更新。

第四步：按照粒子的支配關系，選擇種群的非支配集，對檔案集進行更新。此處設計檔案集的規模為100，如果現有數量已經超出最大規模，那么沿著粒子密度從大到小的順序開始刪除密度大的檔案集粒子網格。

第五步：算法迭代的最高次數為300次，如果超出這個規模則停止繼續搜索，輸出運算后的檔案集。

第六步：利用混沌算子，其初始值隨機，迭代后的種群具有分布均勻、種類多樣的特征，可以由其替代原始的例子種群。

第七步：全部向導選擇網格密度最小的例子，如果多個例子同時符合條件，則隨機選擇。然后按照自適應網格粒子群優化算法對粒子群的位置和速度進行計算更新。

2.2 自適應網格粒子群優化算法

在自適應網格例子群優化算法的設計過程中，包含兩個子種群，其中一個執行自適應網格搜索算子，另外一個執行收縮的PSO搜索算子，獲得種群最優解，根據反饋結果調整種群的網格或者向導。自適應網格粒子群算法流程如圖2所示。

第五步：調整網格

按照gbest粒子所在的位置調整其運動搜索的范圍。網格的調整案例如圖3所示。

為了簡化表達，假設每一個維度的決策變量能夠均分為3段，形成一個兩維的空間，gbest處于第五區間。調整之前，粒子在網格1范圍內搜索，調整之后，粒子要在1、2、4、5的網格內搜索。調整之前，粒子2在網格2的范圍內搜索，調整后要在網格2和網格5構成的范圍內搜索。

上式中，Ω2q表示的是第q個空間粒子的網格搜索范圍，rand（Ω2q）表示的是在Ω2q的區間內隨機生成的點。

2.3 混沌映射算子

引入混沌映射算子，可以獲取偽隨機的遍歷非重復迭代結果，所以對于初始化種群的求解來說是非常適用的。Logistic映射的應用是最為廣泛的，在[0， 1]的區間內不存在穩定的周期點或者是不動的點，所以一直處于一種非常理想的混沌運動中。但是，Logistic映射的點在[0， 1]的區間內是符合雪夫分布的。Tent映射完全映射在[0， 1]的區間內，但計算時小數部分的二進制數會左移，受到字長限制，迭代之后分布會趨于零。因此，Logistic映射和Tent映射都不適合種群初始化。

本文提出一種混沌映射算子模型，利用Logistic擾動來有效消除Tent混沌映射后的不動點?？梢詫⑸鲜鏊惴ū硎緸槭剑?0）。

3 仿真實驗

按照標準的仿真測試手段來比較分析NSGA2和MOEA-AR算法之間的差異，驗證算法性能。

3.1 標準的測試函數

用DTLZ2問題來測試算法的運算性能，并將其數學模型表示如下式（12）。

上式中，n表示的是決策變量的個數，M表示的是目標的個數，XM是第n-M+1個變量。

3.2 性能評價方案

在判斷多目標粒子群優化算法的求解效果時，可以將搜索空間Pareto最優解作為評價指標。收斂距離定義為真實的Pareto的最優前沿和Pareto之間的歐氏距離如式（13）

（m，n）表示的是m和n之間的歐氏距離，Ω表示的是優化的真實Pareto最優前沿，Ψ表示的是近似Pareto最優解集，L（ψ）表示的是獲得最優解的收斂距離。f表示的是以綜合單目標排序優化算法計算得出的最優解，L（f）表示其收斂距離。

3.3 實驗結果

實驗中選擇三組參數，一組：n=10，M=2、4、5、6、8;二組：n=15，M=10、12;三組：n=20，M=15，分析目標不斷增加時的算法優化下過，各組分別運行10次，取平均值，消除隨機因素影響。結果如圖4—圖7所示。

4 總結

由實驗結果可以發現，在優化問題較簡單即具有兩個目標時，兩種方法都具有較好的優化效果，然而隨著優化問題復雜度增大，NSGA2優化效果越來越差，而本文所提算法能夠始終保持較好的收斂精度，因此本文所提方法好于經典的NSGA2算法。

參考文獻

[1] 安偉剛， 李為吉. 單純形-多目標粒子群優化方法的

混合算法[J]. 西北工業大學學報， 2004， 22（5）：563-566.

[2] Pareto檔案多目標粒子群優化[J]. 模式識別與人工智能， 2006， 19（4）：475-480.

[3] Sebastian E. Feedback control for optimal process operation[J]. Journal of Process Control， 2007， 17（3）： 203-219.

[4] 陳民鈾， 張聰譽， 羅辭勇. 自適應進化多目標粒子群優化算法[J]. 控制與決策， 2009， 24（12）：1851-1855.

[5] 趙宏偉.云計算環境下基于改進粒子群優化算法的多目標資源調度策略研究[C]//大數據學術會議. 2014：.

[6] 胡旺， Gary G YEN，張鑫.基于Pareto熵的多目標粒子群優化算法[J].軟件學報， 2014（5）：1025-1050.

[7] 耿煥同， 陳正鵬， 陳哲，等.基于平衡搜索策略的多目標粒子群優化算法[J].模式識別與人工智能， 2017， 30（3）：224-234.

[8] 楊培宏， 劉連光， 劉春明，等. 基于粒子群優化算法的電網GIC-Q多目標優化策略[J]. 電力自動化設備， 2017， 37（3）：93-99.

[9] Moore J， Chapman R. Application of particle swarm to multiobjective optimization[R]. Department of Computer Science and Software Engineering， Auburn University， 1999.

[10] 韓紅桂， 盧薇， 喬俊飛. 一種基于多樣性信息和收斂度的多目標粒子群優化算法[J]. 電子學報， 2018， 46（2）：315-324.

（收稿日期： 2019.02.28）