謝大同

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

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

謝大同

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

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

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

0 引言

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

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

1 自適應(yīng)K階差分演化

1.1 一種新的變異模式

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

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

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

2.2參數(shù)自適應(yīng)

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

差分演化的參數(shù)自適應(yīng)調(diào)節(jié)機(jī)制采用統(tǒng)計(jì)建模的方法實(shí)現(xiàn)。首先，將F、CR、K作為個(gè)體編碼的一部分。從而，種群中的第i個(gè)個(gè)體可表示為(Xi,Fi,CRi,Ki)。然后，采用(0.1, 1)和(0.01, 1)之間產(chǎn)生的均勻分布隨機(jī)數(shù)分別對(duì)F和CR這兩個(gè)參數(shù)進(jìn)行初始化，K則隨機(jī)設(shè)置1或2(當(dāng)K值為1時(shí)表示執(zhí)行1階差分變異，為2時(shí)執(zhí)行2階差分變異)。在差分演化算法執(zhí)行過程中，記錄下被改善個(gè)體所使用的F、CR和K，并分別記錄下每種變異模式下被改善個(gè)體的數(shù)量。每20代期間，若沒有個(gè)體被改善，則分別采用(0.1，1)和(0.01，1)之間產(chǎn)生的均勻分布隨機(jī)數(shù)重新初始化個(gè)體的F和CR，否則若被改善個(gè)體的參數(shù)值之間的最大差距超過0.1，則從被改善個(gè)體中隨機(jī)選取參數(shù)賦予未改善的個(gè)體，未超過0.1則根據(jù)被改善個(gè)體的參數(shù)值分別計(jì)算F和CR的均值Fmean和Cmean，并以正態(tài)分布N(Fmean，0.052)和N(Cmean，0.022)為未改善的個(gè)體產(chǎn)生新的F和CR值。未改善個(gè)體的變異模式按兩種變異模式下改善個(gè)體的概率采用輪盤賭策略進(jìn)行設(shè)置。參數(shù)自適應(yīng)的K階差分演化多目標(biāo)優(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停機(jī)條件不滿足do4 Fori=1toNPDo5 Selectrandomlyr0≠r1≠…≠rk+1≠i6 jrand=randint(1，D)7 Forj=1toDDo8 If(randj(0，1)=0 1then31 從被改善個(gè)體中隨機(jī)選取參數(shù)賦予未改善的個(gè)體32 采用輪盤賭策略為未改善個(gè)體設(shè)置K值33 Else34 計(jì)算被改善個(gè)體中縮放因子和雜交概率的均值Fmean、CRmean35 用N(Fmean，0 052)和N(CRmean，0 022)為未改善的個(gè)體生成參數(shù)

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

2 數(shù)值實(shí)驗(yàn)

2.1實(shí)驗(yàn)設(shè)置

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

表1 四個(gè)算法在ZDT測(cè)試問題集上的收斂性能指標(biāo)IGD的均值和標(biāo)準(zhǔn)差

表2 四個(gè)算法在ZDT測(cè)試問題集上的分布性能指標(biāo)Spacing的均值和標(biāo)準(zhǔn)差

表3 四個(gè)算法在ZDT測(cè)試問題集上的性能指標(biāo)超體積的均值和標(biāo)準(zhǔn)差

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

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

表4 在5個(gè)ZDT測(cè)試問題上分別執(zhí)行KDEMO和SKDEMO各50次所得超體積指標(biāo)值的Kruskal-Wallis檢驗(yàn)結(jié)果

——續(xù)表4

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

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

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

3 結(jié)束語

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

(責(zé)任編輯：楊成平)

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

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

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

TP311

A

2096-3300(2017)03-0091-10