基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法①

李克文, 張永哲

(中國石油大學(華東) 計算機與通信工程學院, 青島 266580)

基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法①

李克文, 張永哲

(中國石油大學(華東) 計算機與通信工程學院, 青島 266580)

為了改善多目標粒子群優(yōu)化算法生成的最終Pareto前端的多樣性和收斂性, 提出了一種針對多目標粒子群算法進化狀態(tài)的檢測機制. 通過對外部Pareto解集的更新情況進行檢測, 進而評估算法的進化狀態(tài), 獲取反饋信息來動態(tài)調(diào)整進化策略, 使得算法在進化過程中兼顧近似Pareto前端的多樣性和收斂性. 最后, 在ZDT系列測試函數(shù)中,將本文算法與其他4種對等算法比較, 證明了本文算法生成的最終Pareto前端在多樣性和收斂性上均有顯著的優(yōu)勢.

多目標優(yōu)化; 粒子群算法; 反饋信息; 進化狀態(tài)

1 引言

粒子群算法(Particle swarm optimization, PSO)[1]最早由Kennedy和Eberhart在1995年提出. 自Coello等人[2]在2002年提出采用粒子群算法求解多目標優(yōu)化問題后, 多目標進化領(lǐng)域中的許多成功經(jīng)驗被借鑒到多目標粒子群優(yōu)化算法中, 并出現(xiàn)了大量的成果[3-8]. 文獻[9]提出的agMOPSO算法采用自適應網(wǎng)格的方法評估Pareto最優(yōu)解的個體密度, 進而剔除質(zhì)量較差的粒子; 文獻[10]提出的pdMOPSO算法采用ROUND、RANDOM以及PROB三種策略來選取全局最優(yōu)解, 這些策略有利于提高Pareto前端的多樣性, 但不易收斂到真實的Pareto前端. 文獻[11]提出的σMOPSO算法通過比較目標向量之間的σ值來選取全局最優(yōu)解, 這種策略會導致算法容易早熟, 陷入局部極值. 文獻此外, 還有小生境[12]、最大最小適應度[13]策略等. 這些多目標粒子群優(yōu)化算法忽略了一個問題: 如何平衡算法在進化過程中的開發(fā)和開采?過度的開發(fā)會影響最終的優(yōu)化精度, 過度的開采會陷入局部極值. 當前所存在的多目標粒子群優(yōu)化算法缺乏對進化狀態(tài)的動態(tài)檢測機制,難以獲取反饋信息來決定算法在何時采用何種進化策略. 基于此, 本文提出了一種基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法進化策略, 通過檢測外部檔案中解的更新情況評估算法的進化狀態(tài), 獲取反饋信息來動態(tài)調(diào)整算法的進化策略, 使得算法在進化過程中能夠平衡開發(fā)和開采, 兼顧到最終解集的多樣性和收斂性.

本文第二節(jié)介紹多目標優(yōu)化問題和粒子群優(yōu)化算法的基本概念, 第三節(jié)介紹通過檢測外部檔案的更新情況來評估算法進化狀態(tài)的方法, 第四節(jié)描述本文提出的動態(tài)調(diào)整策略和算法的完整流程, 第五節(jié)分析對比試驗結(jié)果, 第六節(jié)給出全文結(jié)論.

2 基本概念

2.1 多目標優(yōu)化問題

對于最小化無約束連續(xù)多目標優(yōu)化問題, 如公式(1)所示:

Pareto占優(yōu): 對于任意兩個向量稱u占優(yōu)v,或者v被u占優(yōu), 當且僅當:

Pareto最優(yōu)解: 一個解?被稱為Pareto最優(yōu)解或Pareto非占優(yōu)解, 當且僅當:

Pareto最優(yōu)解集: 所有Pareto最優(yōu)解的集合PS被稱作Pareto最優(yōu)解集.

2.2 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中, 個體i沒有質(zhì)量, 在進化過程中其位置和速度按照公式(5)更新.在公式(5)中, vi表示速度向量, xi表示位置向量, t表示迭代次數(shù), ω≥0表示慣性權(quán)重系數(shù), c1, c2≥0表示加速系數(shù),r1和r2是[0, 1]上均勻分布的隨機數(shù), pBesti表示第i個粒子的個體最優(yōu)解, gBest表示群體的全局最優(yōu)解.

3 進化狀態(tài)評估檢測

根據(jù)外部檔案的更新情形, 對算法的進化狀態(tài)做如下定義:

停滯狀態(tài): 在第t次迭代過程中, 算法產(chǎn)生的新解被拒絕進入外部集, 則稱算法在第t次迭代中處于停滯狀態(tài).

多樣化狀態(tài): 在第t次迭代過程中, 算法產(chǎn)生的新解替換了外部集中適應度較差的舊解, 則稱算法在第t次迭代中處于多樣化狀態(tài).

收斂狀態(tài): 在第t次迭代過程中, 如果算法產(chǎn)生的近似Pareto前端與真實的Pareto前端發(fā)生了目標空間上的距離逼近, 則稱算法在第t次迭代過程中處于收斂狀態(tài).

種群在一次的迭代過程中可產(chǎn)生N個新解, 不同性質(zhì)的新解可能使得算法處于不同的進化狀態(tài). 因此, 需要從宏觀上來判斷算法所處的進化狀態(tài). 下面舉例說明如何判斷算法的進化狀態(tài).

假設(shè)在第t次迭代中, 算法產(chǎn)生m個新解X1, X2,…Xm進入到外部集. 對于某一個新解Xi(1

稱算法在宏觀上朝著多樣化狀態(tài)發(fā)展, 當且僅當:

稱算法在宏觀上朝著收斂狀態(tài)發(fā)展, 當且僅當:

稱算法在宏觀上平衡發(fā)展, 當且僅當:

其中, v為閾值, v取值過大, 會使得算法在進化過程中陷入局部最優(yōu), v取值過小, 會使得算法在評估進化狀態(tài)時出現(xiàn)狀態(tài)抖動(在多樣化狀態(tài)和收斂狀態(tài)之間頻繁轉(zhuǎn)換). 在總結(jié)多次試驗中的閾值取值后, v的取值范圍宜為此次迭代過程中產(chǎn)生的新解個數(shù)的5%-10%.

4 基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法

4.1 全局最優(yōu)解選擇策略

為了使算法在進化過程中兼顧收斂性和多樣性,需要從外部檔案中選取代表收斂性和多樣性的Pareto最優(yōu)解作為全局最優(yōu)解, 引導算法種群平衡開采和開發(fā)過程. 通常, 收斂性和多樣性是相互沖突的, 因此, 需要選取不同的度量標準來評估外部檔案Pareto解集的收斂性和多樣性.

外部檔案中的Pareto最優(yōu)解的個體密度可以作為多樣性指標, 個體密度最小的Pareto解作為全局最優(yōu)解引導種群在目標空間的稀疏區(qū)域進行探索, 可增加Pareto前端的多樣性. 在自適應網(wǎng)格中, Pareto最優(yōu)解的個體密度den(Xi)定義為同Xi格坐標相同的的Pareto最優(yōu)解的個數(shù).在自適應網(wǎng)格中, 第k個Pareto最優(yōu)解的格坐標分量計算方式如公式(9)所示:

其中, pk,m表示第k個Pareto最優(yōu)解在第m個目標分量上的值, m=1, 2, …, M, M表示目標個數(shù), k=1, 2, …, K, K表示當前迭代過程中外部Pareto解集中的解個數(shù), fk,m表示該最優(yōu)解在第m個目標分量上的取值,表示目前第m個目標分量上的最小值和最大值. 為向上取整. 這里的目標維度分割數(shù)K不需要事先取值, 不依賴用戶對MOPSO問題的相關(guān)先驗知識, 將隨著外部Pareto解集中的解個數(shù)變化而變化.

為了選取合適的收斂性指標, 在這里借鑒參考文獻[14]提出的格占優(yōu)和格占優(yōu)強度并稍作修改, 提出G-占優(yōu)和G-占優(yōu)強度兩個定義.

G-占優(yōu): 假設(shè)Gx,m和Gy,m(m=1, 2, …M, M為目標個數(shù))是外部檔案中任意兩個解X, Y在自適應網(wǎng)格中的格坐標, 稱XG-占優(yōu)Y, 當且僅當:

記作.

G-占優(yōu)強度: 對于一個Pareto最優(yōu)解X, 其G-占優(yōu)強度是它在自適應網(wǎng)格中G-占優(yōu)外部檔案A中其它Pareto最優(yōu)解的數(shù)目, 即:

G-占優(yōu)強度反應了一個Pareto最優(yōu)解逼近真實Pareto前端的程度, 因此可以作為外部檔案的收斂性指標.

根據(jù)以上分析, 可得出全局最優(yōu)解選擇策略:

輸入: 1) 外部檔案A和目標個數(shù)M;

2) 算法所處的進化狀態(tài)Status∈{停滯狀態(tài), 多樣化狀態(tài), 收斂狀態(tài)}.

輸出: 全局最優(yōu)解gBest.

步1: 遍歷A中的所有Pareto最優(yōu)解, 分別計算其個體密度和G-占優(yōu)強度;

步2: 個體密度集合D中升序存放Pareto最優(yōu)解, G-占優(yōu)強度集合G中降序存放Pareto最優(yōu)解, 全局最優(yōu)解候選集合C置空;

步3: 如果進化狀態(tài)為停滯狀態(tài)或平衡進化,C=TOP(D, |C|/2)∪TOP(G, |C|/2);

步4: 如果進化狀態(tài)為多樣化狀態(tài), C=TOP(D,|C|/2--)∪TOP(G, |C|/2++);

步5: 如果進化狀態(tài)為收斂狀態(tài), C=TOP(D,|C|/2++)∪TOP(G, |C|/2--);

步6: gBest=Random(C).

注釋: (1) TOP(P, n)表示從有序集合P中返回最前面n個成員;

(2) n++(或n--)表示每次迭代中n加1(減1);

(3) Random(Q)表示從集合Q中隨機選擇一個成員.

4.2 個體最優(yōu)解選擇策略

在個體最優(yōu)解選擇策略方面, 為了使算法在選擇個體最優(yōu)解時最大化地保留個體最優(yōu)解選擇的多樣性,本文提出的算法將為個體最優(yōu)解維護一個外部檔案來存儲個體最優(yōu)解, 同時為了降低算法的復雜度, 將其大小設(shè)為全局最優(yōu)解外部檔案的1/6, 為了保證個體最優(yōu)解的變化能夠跟蹤全局最優(yōu)解的快速變化, 在個體選擇最優(yōu)解時將選擇距離全局最優(yōu)解最近(已經(jīng)通過公式(9)確定)的粒子作為個體最優(yōu)解.

4.3 局部極值擾動策略

為了改善粒子群算法在多目標優(yōu)化中易陷入局部最優(yōu)的不足, 本文將采用文獻[15]提出的精英學習策略(Elitism Learning Strategy, ELS)來輔助算法跳出局部極值. 當算法陷入停滯狀態(tài)的時候在全局最優(yōu)解候選集合C中隨機選擇某個成員作為參與學習的精英粒子, 學習率lp的計算方法如公式(12)所示:

在公式(12)中, Stepl表示精英學習率的步長, 其大小為最大學習率和最小學習率的區(qū)間長度除以迭代次數(shù), 在本文算法中, 最大學習率和最小學習率分別為0.5和0, 算法開始時設(shè)定精英學習率為最大值, 擾動幅度參考文獻[15], 如公式(13)所示:

在公式(13)中, Xd表示精英學習粒子被隨機選中的第d個決策變量,分別為第d個決策變量的最大值和最小值, r為[0, 1]上的隨機數(shù), Gaussian(0, r2)是均值為0、方差為r的高斯函數(shù).

4.4 算法整體流程

輸入: 1) 多目標待優(yōu)化問題;

2) 具有D個決策變量的搜索空間;

3) 初始化相關(guān)參數(shù): 外部檔案的最容量K, 最大迭代次數(shù)Tmax, 種群數(shù)量N.

輸出: 外部檔案中的近似Pareto最優(yōu)解集.

步1: 初始化種群

(1) 迭代次數(shù)設(shè)置為0;

(2) 在搜索空間中均勻隨機生成N個粒子;

(3) 根據(jù)多目標問題計算每個粒子的第m個目標函數(shù)值;

(4) 判斷哪些粒子可以進入外部檔案.

步2: 迭代次數(shù)加1

步3: 評估進化環(huán)境

(1) 根據(jù)公式(6)(7)(8)判定算法的進化狀態(tài);

(2) 根據(jù)公式(9)和公式(11)計算外部檔案中每個解的個體密度和G-占優(yōu)強度.

步4: 調(diào)整算法的運動參數(shù): 算法的學習因子設(shè)定為2.05, 慣性權(quán)重隨著迭代次數(shù)從0.9線性下降到0.4.

步5: 更新種群

(1) 根據(jù)全局最優(yōu)解選擇策略和個體最優(yōu)解選擇策略選擇選擇全局最優(yōu)解gBesti和個體最優(yōu)解pBesti.

(2) 根據(jù)運動方程以及運動參數(shù)更新粒子的位置和速度;

(3) 如果算法陷入停滯狀態(tài), 將根據(jù)公式(12)所確定的學習率lp按照公式(13)對粒子進行局部極值擾動.

(4) 評估粒子的目標函數(shù)值;

(5) 根據(jù)全局最優(yōu)解選擇策略和個體最優(yōu)解選擇策略更新種群的個體最優(yōu)解候選集和全局最優(yōu)解候選集;

步6: 迭代終止條件(如果迭代次數(shù)大于預設(shè)定次數(shù), 結(jié)束; 否則轉(zhuǎn)步2).

5 實驗及結(jié)果分析

為了驗證本文提出的算法(daMOPSO), 本文在實驗中選取了4種常用于比較多目標優(yōu)化的對等算法, 包括agMOPSO[9], pdMOPSO[10], σMOPSO[11]及MOEA/D[16], 在對比實驗中, 將選取各對比算法的種群大小均設(shè)定為N=100, 外部檔案規(guī)模均設(shè)定為K=100,算法的迭代次數(shù)均設(shè)定為T=300. 各對比算法的參數(shù)都按照各自的參考文獻設(shè)置. daMOPSO的學習因子設(shè)置為2.05, 慣性權(quán)重隨迭代次數(shù)從0.9線性下降到0.4, 閾值v取各迭代過程中產(chǎn)生的新解個數(shù)的6%. 各對比算法在所有的測試函數(shù)上都獨立運行30次以降低隨機影響.

為了評估本文提出的算法生成的近似Pareto前端的多樣性和收斂性, 本文將采用反轉(zhuǎn)世代距離(Inverted Generational Distance, IGD)[16]作為評估指標. 其計算方法如公式(14)所示:

本文選擇ZDT1、ZDT2、ZDT3、ZDT4和ZDT6這組測試函數(shù)來測試各個算法的性能, ZDT5作為布爾函數(shù), 需要二進制編碼, 本文略去該測試函數(shù). 獲得的近似Pareto前端如圖1至圖5所示. σMOPSO在ZDT4測試中獲得的Pareto前端和agMOPSO、σMOPSO、pdMOPSO在ZDT6測試中獲得的Pareto前端質(zhì)量太差, 在圖中未表示.

圖1 ZDT1的測試結(jié)果

圖2 ZDT2的測試結(jié)果

圖3 ZDT3的測試結(jié)果

圖4 ZDT4的測試結(jié)果

表1給出了各個算法在獨立運行30次后獲得的IGD的平均值(mean)和方差值(std).

通過表1可以看出, daMOPSO在測試函數(shù)中取得的整體效果非常理想, 僅在ZDT4的測試中結(jié)果不如MOEA/D, ZDT4函數(shù)具有219個不同的局部Pareto最優(yōu)前沿, 其中只有一個對應全局最優(yōu)前沿, 這說明daMOPSO在在跳出局部最優(yōu)時與MOEA/D相比略顯不足.

圖5 ZDT6的測試結(jié)果

表1 各個算法在5種測試函數(shù)中獲得的IGD對比

與其它幾種對等算法相比, 由于daMPSO在維護全局外部檔案集的同時維護了一個個體外部檔案集, 因此空間復雜度要大于其它幾種對等算法, daMOPSO在每一次迭代中都會計算每一個最優(yōu)解的個體密度和G-占優(yōu)強度, 因此時間復雜度也略高于其它幾種算法.

下一步筆者將會對daMOPSO的跳出局部最優(yōu)能力以及降低時空復雜度進行探索提升. 總體來看, daMOPSO在處理這類優(yōu)化問題時的能力要優(yōu)于其它幾種對比算法.

6 總結(jié)

基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法(daMOPSO)通過檢測外部檔案的更新情況確認算法的進化狀態(tài),通過個體密度和G-占優(yōu)強度來評價個體適應度, 并根據(jù)不同的進化狀態(tài)動態(tài)調(diào)整算法的進化策略, 保證算法在進化過程中能夠兼顧Pareto前端的多樣性和收斂性. 選擇了ZDT系列測試函數(shù)對daMOPSO算法進行了測試, 結(jié)果表明該算法在處理不同類型的Pareto前端時都表現(xiàn)出了比較優(yōu)秀的性能.

1Kennedy J, Eberhart R. Particle swarm optimization. Proc. of IEEE International Conference on Neural Networks. Perth,WA, Australia. 1995. 1942–1948.

2Coello Coello CA, Lechuga MS. MOPSO: A proposal for multiple objective particle swarm optimization. Proc. of the 2002 Congress on Evolutionary Computation. Honolulu, HI,USA. 2002. 1051–1056.

3Maltese J, Ombuki-Berman B, Engelbrecht A. Co-operative vector-evaluated particle swarm optimization for multiobjective optimization. Proc. 2015 IEEE Symposium Series on Computational Intelligence. Cape Town, South Africa.2015. 1294–1301.

4Padhye N, Branke J, Mostaghim S. Empirical comparison of MOPSO methods—guide selection and diversity preservation. Proc. of IEEE Congress on Evolutionary Computation. Trondheim. 2009. 2516–2523.

5Dai C, Wang YP, Ye M. A new multi-objective particle swarm optimization algorithm based on decomposition.Information Sciences, 2015, 325: 541–557. [doi: 10.1016/j.ins.2015.07.018]

6Coelho LDS, Guerra FA, Leite JV. Multiobjective exponential particle swarm optimization approach applied to hysteresis parameters estimation. IEEE Trans. on Magnetics,2012, 48(2): 283–286. [doi: 10.1109/TMAG.2011.2172581]

7Moubayed NA, Petrovski A, McCall J. Clustering-based leaders’ selection in multi-objective particle swarm optimisation. Yin H, Wang W, Rayward-Smith V. Intelligent Data Engineering and Automated Learning-IDEAL 2011.Berlin, Heidelberg, Germany. 2011. 100–107.

8Zhou AM, Qu BY, Li H, et al. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 2011, 1(1): 32–49. [doi: 10.1016/j.swevo.2011.03.001]

9Coello CCA, Pulido GT, Lechuga MS. Handling multiple objectives with particle swarm optimization. IEEE Trans. on Evolutionary Computation, 2004, 8(3): 256–279. [doi:10.1109/TEVC.2004.826067]

10Alvarez-Benitez JE, Everson RM, Fieldsend JE. A MOPSO algorithm based exclusively on Pareto dominance concepts.Coello Coello CA, Hernández AA, Zitzler E. Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg, Germany.2005. 459–473.

11Mostaghim S, Teich J. Strategies for finding good local guides in multi-objective particle swarm optimization(MOPSO). Proc. of the 2003 IEEE Swarm Intelligence Symposium. Indianapolis, IN, USA. 2003. 26–33.

12Zhao QL. The Research of the Niche particle swarm optimization based on self-adaptive radius technology. Proc.of Asia-Pacific Conference on Information Processing.Shenzhen, China. 2009. 97–100.

13徐佳, 李紹軍, 王惠, 等. 基于最大最小適應度函數(shù)的多目標粒子群算法. 計算機與數(shù)字工程, 2006, 34(8): 31–34.

14胡旺, Yen GG, 張鑫. 基于Pareto熵的多目標粒子群優(yōu)化算法. 軟件學報, 2014, 25(5): 1025–1050.

15Zhan ZH, Zhang J, Li Y, et al. Adaptive particle swarm optimization. IEEE Trans. on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(6): 1362–1381.[doi: 10.1109/TSMCB.2009.2015956]

16Zhang QF, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007, 11(6): 712–731. [doi: 10.1109/TEVC.2007.892759]

Multi Objective Particle Swarm Optimization Based on Dynamic Adjustment

LI Ke-Wen, ZHANG Yong-Zhe
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China)

To improve the diversity and convergence of Pareto front generated by multi objective particle swarm optimization, a detection mechanism for evolutionary state of multi objective particle swarm optimization is presented in this paper. The evolutionary state of the algorithm is assumed by detecting the updating situation of the external Pareto set to get the feedback information to adjust the evolutionary strategy of the algorithm dynamically. It enables the algorithm to take the diversity and convergence of the approximate Pareto front into account in the process of the evolution. Finally,the proposed algorithm shows a good performance compared with other four kinds of equivalence algorithms in the ZDT series test function.

multi objective optimization; particle swarm optimization; feedback information; evolutionary state

張永哲, E-mail: 864238735@qq.com

李克文,張永哲.基于動態(tài)調(diào)整的多目標粒子群優(yōu)化算法.計算機系統(tǒng)應用,2017,26(7):161–166. http://www.c-s-a.org.cn/1003-3254/5820.html

山東省自然科學基金(ZR2013FL034)

2016-10-20; 收到修改稿時間: 2016-11-14