基于動態(tài)平衡的多目標粒子群優(yōu)化算法

張海波

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

關(guān)鍵詞： 動態(tài)平衡; 混沌; 自適應(yīng)網(wǎng)格; 多目標優(yōu)化; 粒子群算法

中圖分類號： 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 引言

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

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

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

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

1 多目標優(yōu)化概念

2 動態(tài)多目標粒子群優(yōu)化算法

2.1 主程序

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

第一步：算法初始化。在決策空間中，對種群之中的粒子位置嚴格給予隨機賦值，且粒子運動速度為零。粒子個體向?qū)槠湮恢茫瑱n案集為空。

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

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

體向?qū)Ц聻楫斍拔恢茫绻呦嗷テヅ?，則不進行更新。

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

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

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

第七步：全部向?qū)нx擇網(wǎng)格密度最小的例子，如果多個例子同時符合條件，則隨機選擇。然后按照自適應(yīng)網(wǎng)格粒子群優(yōu)化算法對粒子群的位置和速度進行計算更新。

2.2 自適應(yīng)網(wǎng)格粒子群優(yōu)化算法

在自適應(yīng)網(wǎng)格例子群優(yōu)化算法的設(shè)計過程中，包含兩個子種群，其中一個執(zhí)行自適應(yīng)網(wǎng)格搜索算子，另外一個執(zhí)行收縮的PSO搜索算子，獲得種群最優(yōu)解，根據(jù)反饋結(jié)果調(diào)整種群的網(wǎng)格或者向?qū)?。自適應(yīng)網(wǎng)格粒子群算法流程如圖2所示。

第五步：調(diào)整網(wǎng)格

按照gbest粒子所在的位置調(diào)整其運動搜索的范圍。網(wǎng)格的調(diào)整案例如圖3所示。

為了簡化表達，假設(shè)每一個維度的決策變量能夠均分為3段，形成一個兩維的空間，gbest處于第五區(qū)間。調(diào)整之前，粒子在網(wǎng)格1范圍內(nèi)搜索，調(diào)整之后，粒子要在1、2、4、5的網(wǎng)格內(nèi)搜索。調(diào)整之前，粒子2在網(wǎng)格2的范圍內(nèi)搜索，調(diào)整后要在網(wǎng)格2和網(wǎng)格5構(gòu)成的范圍內(nèi)搜索。

上式中，Ω2q表示的是第q個空間粒子的網(wǎng)格搜索范圍，rand（Ω2q）表示的是在Ω2q的區(qū)間內(nèi)隨機生成的點。

2.3 混沌映射算子

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

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

3 仿真實驗

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

3.1 標準的測試函數(shù)

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

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

3.2 性能評價方案

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

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

3.3 實驗結(jié)果

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

4 總結(jié)

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

參考文獻

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

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

[2] Pareto檔案多目標粒子群優(yōu)化[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] 陳民鈾， 張聰譽， 羅辭勇. 自適應(yīng)進化多目標粒子群優(yōu)化算法[J]. 控制與決策， 2009， 24（12）：1851-1855.

[5] 趙宏偉.云計算環(huán)境下基于改進粒子群優(yōu)化算法的多目標資源調(diào)度策略研究[C]//大數(shù)據(jù)學術(shù)會議. 2014：.

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

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

[8] 楊培宏， 劉連光， 劉春明，等. 基于粒子群優(yōu)化算法的電網(wǎng)GIC-Q多目標優(yōu)化策略[J]. 電力自動化設(shè)備， 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] 韓紅桂， 盧薇， 喬俊飛. 一種基于多樣性信息和收斂度的多目標粒子群優(yōu)化算法[J]. 電子學報， 2018， 46（2）：315-324.

（收稿日期： 2019.02.28）