謝大同

(福建商學院 信息管理工程系，福建 福州，350108)

基于自適應K階差分演化的多目標優(yōu)化算法

謝大同

(福建商學院 信息管理工程系，福建 福州，350108)

差分演化算法已經(jīng)被成功地用于解決單目標和多目標優(yōu)化問題，然而它的搜索能力受限于所使用的變異模式和控制參數(shù)。為此，提出一種新的變異模式——K階差分，并引入?yún)?shù)自適應機制，設計了一個基于自適應K階差分演化的多目標優(yōu)化算法。與NSGA-II、DEMO的仿真實驗比較結果表明，該算法在ZDT測試問題上能獲得較好的優(yōu)化效果。

差分演化；多目標優(yōu)化；參數(shù)自適應；K階差分

0 引言

差分演化算法(Differential Evolution，簡稱DE)是Storn和Price[1]提出的一種智能優(yōu)化方法，具有簡單、高效的特點，已經(jīng)被成功地用于解決單目標和多目標優(yōu)化問題。然而，差分演化算法對雜交概率和縮放因子這兩個參數(shù)比較敏感。一些研究者對算法參數(shù)的設置進行了探討，給出了一些指導性意見。譬如G?mperle[2]、Liu[3]等人建議縮放因子設為0.6，雜交概率在0.3到0.9之間選取。R?nkk?nen[4]等人認為，F(xiàn)最好設置在0.4到0.95之間，其中0.9是一個比較好的初始選擇，而對于CR，他們認為在0到0.2之間的值適合于可分離的函數(shù)，而在0.9到1.0之間的值適合于存在參數(shù)依賴的函數(shù)。類似的參數(shù)設置建議還有很多，但是它們一般都局限于部分問題，甚至有些建議相互矛盾。因此，由算法在演化過程中對參數(shù)進行自適應調(diào)節(jié)，已經(jīng)成為差分演化算法的一個研究熱點。在單目標優(yōu)化領域，人們提出了差分演化算法的一些參數(shù)自適應版本。實際上，這些參數(shù)自適應策略也可以用于多目標優(yōu)化問題。Abbass[5]提出一種參數(shù)自適應的多目標差分演化算法，在該算法中，雜交概率成為個體編碼的一部分，通過演化算子自適應地進行調(diào)整，而縮放因子則通過高斯分布N(0，1)產(chǎn)生。Qian和Li[6]提出ADEA算法，該算法使用個體的擁擠距離對參數(shù)進行自適應調(diào)整，使用Pareto非支配排名和修改的擁擠距離對個體進行選擇。此外，一些研究者對差分演化算法的變異模式進行了比較研究，發(fā)現(xiàn)各種變異模式在各類優(yōu)化問題上的表現(xiàn)互有優(yōu)劣，也設計了新的變異模式。Mezura-Montes[7]比較了8種不同的變異模式在13個測試問題上的性能。FAN和LAMPINEN[8]將所有可能的變異模式概括為四組，并提出一種對個體隨機分組或者按適應度分組后采用兩組的中心來產(chǎn)生差分向量的變異策略。

現(xiàn)有差分演化算法的變種基本上都按照基本差分演化算法中使用成對向量之差的方式來構造差分向量。本文從差分演化的這種操作特點聯(lián)想到數(shù)學上的差分概念，提出一種新的差分變異模式——K階差分變異；同時，在差分演化算法中自適應地調(diào)節(jié)縮放因子、雜交概率和變異模式；最終，設計出一個基于自適應K階差分演化的多目標優(yōu)化算法(SKDEMO，Self-adaptive K-order Differential Evolution Multi-objective Optimization)。

1 自適應K階差分演化

1.1 一種新的變異模式

圖1 K階差分演化算法的主體部分Fig.1 The main body of K-order differential evolution

如果按數(shù)學上K階差分(K≥2)的概念來構造差分向量，實際上是用三個或三個以上的解向量來產(chǎn)生一個差分向量，這種差分向量的構造方式將使得算法既可能獲得多樣性更好的解，也可能產(chǎn)生對目標向量進行局部搜索的效果。以2階差分變異為

圖2 階差分變異過程的示意圖Fig.2 Diagram of 2-order differential variation

2.2參數(shù)自適應

由于差分演化存在對參數(shù)敏感的問題，我們?yōu)椴罘盅莼惴ǖ目s放因子F、雜交概率CR、變異模式K設計了自適應調(diào)節(jié)策略。

差分演化的參數(shù)自適應調(diào)節(jié)機制采用統(tǒng)計建模的方法實現(xiàn)。首先，將F、CR、K作為個體編碼的一部分。從而，種群中的第i個個體可表示為(Xi,Fi,CRi,Ki)。然后，采用(0.1, 1)和(0.01, 1)之間產(chǎn)生的均勻分布隨機數(shù)分別對F和CR這兩個參數(shù)進行初始化，K則隨機設置1或2(當K值為1時表示執(zhí)行1階差分變異，為2時執(zhí)行2階差分變異)。在差分演化算法執(zhí)行過程中，記錄下被改善個體所使用的F、CR和K，并分別記錄下每種變異模式下被改善個體的數(shù)量。每20代期間，若沒有個體被改善，則分別采用(0.1，1)和(0.01，1)之間產(chǎn)生的均勻分布隨機數(shù)重新初始化個體的F和CR，否則若被改善個體的參數(shù)值之間的最大差距超過0.1，則從被改善個體中隨機選取參數(shù)賦予未改善的個體，未超過0.1則根據(jù)被改善個體的參數(shù)值分別計算F和CR的均值Fmean和Cmean，并以正態(tài)分布N(Fmean，0.052)和N(Cmean，0.022)為未改善的個體產(chǎn)生新的F和CR值。未改善個體的變異模式按兩種變異模式下改善個體的概率采用輪盤賭策略進行設置。參數(shù)自適應的K階差分演化多目標優(yōu)化算法SKDEMO的步驟如下：

1 G=0，初始化種群PG={(X1，F(xiàn)1，CR1，K1)，(X2，F(xiàn)2，CR2，K2)，…，(XNP，F(xiàn)NP，CRNP，KNP)}2 將PG中的非支配解放入檔案集AG3 While停機條件不滿足do4 Fori=1toNPDo5 Selectrandomlyr0≠r1≠…≠rk+1≠i6 jrand=randint(1，D)7 Forj=1toDDo8 If(randj(0，1)=0 1then31 從被改善個體中隨機選取參數(shù)賦予未改善的個體32 采用輪盤賭策略為未改善個體設置K值33 Else34 計算被改善個體中縮放因子和雜交概率的均值Fmean、CRmean35 用N(Fmean，0 052)和N(CRmean，0 022)為未改善的個體生成參數(shù)

36 采用輪盤賭策略為未改善個體設置K值37 Endif38 EndIf39 G=G+140 EndWhile41 輸出結果

2 數(shù)值實驗

2.1實驗設置

為了驗證算法的性能，在ZDT1、ZDT2、ZDT3、ZDT4和ZDT6這5個測試問題上對NSGAII、DEMO、未使用參數(shù)自適應機制的K階差分演化算法(記為KDEMO)和使用參數(shù)自適應機制的K階差分演化算法(記為SKDEMO)進行比較實驗。四個算法共同的參數(shù)設置為：檔案集規(guī)模為200，運行次數(shù)為50，停機條件為評價次數(shù)達到100000；NSGA-II和DEMO的種群規(guī)模設為200；其它兩個算法的種群規(guī)模設為50。此外，按照文獻[9]，將NSGA-II的雜交概率設為0.9，變異概率為1/n (n是決策變量的數(shù)目)，雜交和變異算子的分布指數(shù)均為20。對于DEMO，使用文獻[10]給出的三種算法中總體表現(xiàn)最好的DEMO/parent算法，且雜交概率和縮放因子也分別設為0.3和0.5。KDEMO采用2階差分變異模式，其雜交概率和縮放因子取值與DEMO一致。

3.2 實驗結果及分析

表1、表2和表3分別列出了NSGA-II、DEMO、KDEMO和SKDEMO在5個測試問題上得到的IGD、Spacing、超體積這三個指標的均值和標準差(記為“均值(標準差)”的形式)。

表1 四個算法在ZDT測試問題集上的收斂性能指標IGD的均值和標準差

表2 四個算法在ZDT測試問題集上的分布性能指標Spacing的均值和標準差

表3 四個算法在ZDT測試問題集上的性能指標超體積的均值和標準差

三個表中的數(shù)據(jù)表明，KDEMO和SKDEMO在5個ZDT測試問題上與NSGA-II和DEMO相比具有明顯的性能優(yōu)勢(粗體文字標明了四種算法中最好的平均性能指標值)，而KDEMO算法與SKDEMO算法的性能幾乎不分伯仲。單純從收斂性能來看，SKDEMO的效果更好，而從分布性能來看KDEMO更優(yōu)。另外，盡管KDEMO在ZDT2上表現(xiàn)出IGD和Spacing指標值都優(yōu)于SKDEMO，但按照超體積指標，SKDEMO優(yōu)于KDEMO。在ZDT3上，SKDEMO的IGD和Spacing指標均優(yōu)于KDEMO，但在超體積指標上卻劣于KDEMO。這一現(xiàn)象與一些文獻中提到的IGD和Spacing指標不能準確反映算法性能優(yōu)劣的結論吻合。

為了更準確地區(qū)分KDEMO和SKDEMO在不同問題上的性能，將兩個算法在各問題上運行50次的超體積性能指標值使用Kruskal-wallis檢驗方法進行統(tǒng)計比較，統(tǒng)計檢驗結果如表4所示。表中數(shù)值表示由行對應的算法A和列對應的算法B配對在單尾檢驗下得到的p值，零假設為“A的結果不優(yōu)于B的結果”，備擇假設為“A的結果優(yōu)于B的結果”，顯著性水平α設為0.05。根據(jù)表4的數(shù)據(jù)可知，SKDEMO在5個ZDT測試問題上的超體積指標均優(yōu)于KDEMO。

表4 在5個ZDT測試問題上分別執(zhí)行KDEMO和SKDEMO各50次所得超體積指標值的Kruskal-Wallis檢驗結果

——續(xù)表4

ZDT6KDEMOSKDEMOKDEMO———1 00E+00SKDEMO1 82E-28———

上述實驗結果表明，SKDEMO所采用的自適應機制是有效的。為了幫助進一步理解SKDEMO的參數(shù)自適應機制，用圖3～圖7來描述演化過程中優(yōu)秀參數(shù)的均值和個體被改善數(shù)量的均值的變化趨勢。

圖3 SKDEMO 在ZDT1上執(zhí)行時優(yōu)秀參數(shù)均值和個體被改善數(shù)量均值的變化趨勢Fig.3 Variation tendencies of the mean values about perfect parameter values and the count of improved individuals with SKDEMO executed on ZDT1

圖4 SKDEMO 在ZDT2上執(zhí)行時優(yōu)秀參數(shù)均值和個體被改善數(shù)量均值的變化趨勢Fig.4 Variation tendency of the mean values about perfect parameter values and the count of improved individuals with SKDEMO executed on ZDT2

圖5 SKDEMO 在ZDT3上執(zhí)行時優(yōu)秀參數(shù)均值和個體被改善數(shù)量均值的變化趨勢Fig.5 Variation tendency of the mean values about perfect parameter values and the count of improved individuals with SKDEMO executed on ZDT3

圖6 SKDEMO 在ZDT4上執(zhí)行時優(yōu)秀參數(shù)均值和個體被改善數(shù)量均值的變化趨勢Fig.6 Variation tendency of the mean values about perfect parameter values and the count of improved individuals with SKDEMO executed on ZDT4

圖7 SKDEMO 在ZDT6上執(zhí)行時優(yōu)秀參數(shù)均值和個體被改善數(shù)量均值的變化趨勢Fig.7 Variation tendency of the mean values about perfect parameter values and the count of improved individuals with SKDEMO executed on ZDT6

圖3～圖7表明，在演化前期，被改善的個體較多時，F(xiàn)的取值在0.5附近，CR的取值在0.3附近，接近文獻[10]中所建議的參數(shù)。而后期被改善的個體變少，主要原因在于演化后期算法開始收斂，種群中趨同的個體也越來越多。此時算法主要對優(yōu)秀個體進行精細搜索，因此縮放因子值會變小，而雜交概率也變小，即個體執(zhí)行差分變異的概率降低。從圖3～圖6可看出，前500代縮放因子基本上在0.5附近，而雜交概率波動比較明顯，個體改善的數(shù)量變化趨勢陡峭，說明此段時間算法性能受雜交概率的影響較大。從圖6可知，在500代時，個體改善的數(shù)量最大，此時雜交概率較小，而在1000代時雜交概率值較大，個體改善的數(shù)量幾乎為0，因此可以認為，對于ZDT4而言，雜交概率在0.1附近時更容易改善個體。圖7表明，ZDT6使用0.4附近的值作為雜交概率時，更容易改善個體。

3 結束語

利用基本差分演化算法中構造差分向量的特點，結合數(shù)學上的差分概念，設計了一種K階差分變異模式，對差分演化的變異方式進行了延伸。實驗結果表明，基于2階差分變異模式的多目標演化算法KDEMO在ZDT測試問題上的尋優(yōu)能力比NSGA-II和DEMO更強，而在KDEMO算法基礎上加入?yún)?shù)自適應調(diào)節(jié)機制構造的算法SKDEMO的性能比KDEMO更好。在種群規(guī)模允許的范圍內(nèi)，可將差分向量的構造方式拓展為使用3階、4階甚至更高階的差分變異模式。下一步的工作將探究差分演化算法采用不同階的差分變異模式在各種問題上的優(yōu)化效果。同時，也有必要從理論上分析K階差分變異模式的收斂性。

[1]STORN R，PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization，1997 (11): 341-359.

[2]GAMPERLE R，MULLER S D，KOUMOUTSAKOS P. A parameter study for differential evolution[J]. Advances in intelligent systems，fuzzy systems，evolutionary computation，2002 (10): 293-298.

[3]L J. On setting the control parameter of the differential evolution algorithm[C]. Brno：The 8th international Mendel conference on soft computing，2002.

[4]RONKKONEN J，KUKKONEN S，PRICE K V. Real-parameter optimization with differential evolution[C]. Edinburgh：IEEE Congress on Evolutionary Computation 2005， 2005.

[5]ABBASSH A. The self-adaptive pareto differential evolution algorithm[C]. New Jersey：IEEE Congress on Evolutionary Computation 2002，2002.

[6]QIAN W. Adaptive differential evolution algorithm for multiobjective optimization problems[J]. Applied Mathematics and Computation，2008 (201): 431-440.

[7]MEZURA M E，VELAZQUEZ J，COELLO C A. A comparative study of differential evolution variants for global optimization[C]. Seattle：The 8th annual conference on Genetic and evolutionary computation，2006.

[8]FAN H，LAMPINEN J. A trigonometric mutation operation to differential evolution[J]. Journal of Global Optimization，2003 (27): 105-129.

[9]KALYANMOY D，AMRIT P，SAMEER A，et al. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation，2002 (6): 182-197.

[10]TEA R，BOGDAN F. DEMO: differential evolution for multiobjective optimization [C]. Guanajuato: The third international conference on evolutionary multi-criterion optimization，2005.

(責任編輯：楊成平)

Multi-objective Optimization Algorithm Based on Self Adaptive K-order Differential Evolution

XIE Da-tong

(Department of Information Management and Engineering,Fujian Commercial College, Fuzhou 350108, China)

Differential evolution has been successfully employed to solve single-objective and multi-objective problems. However, its search ability is significantly influenced by its variation patterns and control parameters. Therefore, a new variation pattern named K-order difference is proposed in this paper. Then, a multi-objective optimization algorithm, SKDEMO, which is based on K-order differential evolution and self adaptive parameter adjustment mechanism, is designed to solve multi-objective problems. The experiments on five ZDT benchmark problems show that SKDEMO exhibits better performance than NSGA-II and DEMO.

differential evolution; multi-objective optimization; parameter self-adaptation; K-order difference

2017-04-20

福建省中青年教師教育科研項目(科技類)“多目標優(yōu)化問題的K階差分演化算法研究”(JA13400)。

謝大同(1977-)，湖南雙峰人，副教授，博士。研究方向：智能計算、軟件工程。

TP311

A

2096-3300(2017)03-0091-10