陳學(xué)志,李垣江,張?zhí)炝?高 婧,田雨波

(江蘇科技大學(xué) 電子信息學(xué)院, 鎮(zhèn)江 212100)

差分進化算法[1](differential evolution, DE)與遺傳算法[2]、人工蜂群算法[3]一樣,都是通過模擬生物進化過程設(shè)計的一種智能優(yōu)化算法,它采用浮點矢量編碼方式,通過種群的并行演化來搜索空間中的最優(yōu)適應(yīng)值．由于算法具有結(jié)構(gòu)簡單易于執(zhí)行,且擁有較少的控制參數(shù),整體優(yōu)化性能較好,近年來受到了越來越多學(xué)者的關(guān)注與研究[4-5]．研究表明,差分進化算法對一些大規(guī)模、高位數(shù)、非線性和不可微的函數(shù)進行優(yōu)化時擁有很強的實用性[6-7]．然而,普通的差分進化算法與其他很多智能優(yōu)化算法一樣,也存在著收斂慢、易于陷入局部最優(yōu)等問題[8]．

為了改良差分進化算法的性能,提出很多改進方法:文獻[9]提出一種變異因子F滿足正態(tài)分布N(0.5,0.3)的自適應(yīng)差分進化(self-adaptive differential evolution,SaDE)算法;文獻[10]通過一種使用模糊邏輯控制器來調(diào)節(jié)控制參數(shù)的模糊自適應(yīng)差分進化(fuzzy adaptive differential evolution,FADE)算法,使得算法控制參數(shù)具有了自適應(yīng)調(diào)節(jié)能力;文獻[11]提出了以進化代數(shù)為函數(shù)的選擇策略,平衡了算法的搜索能力與開發(fā)能力;文獻[12]提出一種基于多種群協(xié)方差學(xué)習(xí)的差分進化算法,通過多種群結(jié)構(gòu)來保證種群進化時的多樣性;文獻[13]提出一種基于混沌自適應(yīng)差分進化算法,并將其應(yīng)用于艦船電力系統(tǒng)網(wǎng)絡(luò)重構(gòu)之中．文中提出了一種基于種群競爭的自適應(yīng)差分進化算法(population-competition-based self-adaption differential evolution,PCSADE),通過對不同種群劃分不同的變異策略以及變異因子的自適應(yīng)控制來提高演化種群的多樣性與對最優(yōu)適應(yīng)值的搜索能力．通過6種不同的測試函數(shù)進行數(shù)值仿真,實驗結(jié)果驗證了PCSADE算法在收斂速度、搜索能力上相比于原有的算法有了很大提高．

1 種群競爭自適應(yīng)差分進化算法

1.1 差分進化算法

差分進化算法采用浮點矢量編碼生成種群,算法包括初始化、變異、交叉、選擇4個步驟．通過對初始種群的變異來獲得變異個體,將待變異個體按照交叉策略與初始種群進行元素互換得到交叉后的個體,將越接近求解目標(biāo)的個體賦予越小的適應(yīng)值,選擇適應(yīng)值較小的個體作為新的子代個體，通過不斷更新種群來實現(xiàn)對于最優(yōu)適應(yīng)值的搜索．

1.1.1 種群初始化

在m維空間中隨機產(chǎn)生NP個初始個體,產(chǎn)生方式如下:

(1)

1.1.2 種群變異

從當(dāng)前種群隨機選擇3個個體xr1、xr2、xr3,取出其中兩個作差,再乘上放縮因子與剩下的那個個體相加得到變異個體,在每一步的迭代中對每個個體執(zhí)行如下操作:

vi=xr1+F(xr2-xr3)

(2)

式中：vi為第i個個體的變異結(jié)果；xr1、xr2、xr3都是從NP中抽取出來的3個不同的個體;F為放縮因子．

1.1.3 交叉操作

將變異后得到的個體與其對應(yīng)的原種群中的個體按照一定的概率進行特性元素交叉．使用rand函數(shù)產(chǎn)生一個隨機數(shù),當(dāng)這個隨機數(shù)的大小滿足一定條件的時候則輸出變異后個體內(nèi)的元素,否則輸出原種群個體中的元素．交叉操作可以增加種群個體的多樣性,對每個個體執(zhí)行如下操作:

(3)

式中：uij(g)為第g代中第i個個體中第j個位置處特性元素的交叉結(jié)果,其值來自于上一步的變異所得個體或者是原始個體對應(yīng)位置上的特性元素；CR為交叉率；jrand為1～m的隨機整數(shù),這樣可以保證交叉后的個體中至少有一個特性來自于變異結(jié)果vi．

1.1.4 選擇操作

在完成變異交叉的步驟后,算法會比較交叉所得到個體ui與待進化個體xi的適應(yīng)值．將所需要求解的問題轉(zhuǎn)換成適應(yīng)值函數(shù),越是接近求解目標(biāo)的個體,適應(yīng)值越小．選擇擁有較小適應(yīng)值的個體作為子代個體留下,公式如下:

(4)

式中：f(·)為適應(yīng)值函數(shù),其具體函數(shù)形式由求解問題得到;ui(g)為第g代中個體完成交叉操作后所得到的結(jié)果；xi(g)為第g代中原始個體,xi(g+1)為所得到的子代個體．

1.2 種群競爭自適應(yīng)差分進化算法

文中提出一種基于種群競爭的自適應(yīng)差分進化策略(PCSADE),將種群競爭機制與自適應(yīng)策略引入到了DE算法中,可以有效地解決DE算法收斂速度慢、在進化過程中種群多樣性減少、易于陷入局部最優(yōu)等問題．

PCSADE算法將種群按照適應(yīng)值優(yōu)劣分成3個子種群,對于不同的種群采用不同的變異策略．對于優(yōu)勢種群采用較小的變異因子結(jié)合促進進化的變異策略使得優(yōu)勢種群的個體可以產(chǎn)生更多的候選個體;對于中間種群使用線性自適應(yīng)變異因子結(jié)合常規(guī)的變異策略,保證中間種群中的個體能夠按照自己的適應(yīng)度特征來進化;對于劣勢種群的個體采用較大的變異因子結(jié)合抑制變異的策略,使得劣勢種群中的個體可以保證自己擁有足夠的多樣性．從整體來看,完整種群中的個體多樣性得到保證,同時也增加了尋找全局最優(yōu)個體的速度．

1.2.1 子代種群的劃分

假設(shè)整體種群中有NP個個體,對種群中所有個體求取適應(yīng)值,按照種群內(nèi)所有個體按照適應(yīng)值大小排序．將序號處在前1/N0的個體劃分為優(yōu)勢種群,序號處在后1/N0的個體劃分為劣勢種群,剩余(1-2/N0)的個體劃分為中間種群．經(jīng)過實驗與理論分析N0取值要大于等于4,這樣可以保證中間種群的數(shù)量超過整體種群的一半,當(dāng)中間種群數(shù)量較多時既可以充分發(fā)揮自適應(yīng)變異因子的作用．公式如下:

(5)

式中：index為個體在整體種群中的排列序號；在實驗中N0取值為4；xindex整體種群中第index個個體；X1為優(yōu)勢種群；X2為中間種群；X3為劣勢種群．

1.2.2 變異因子的自適應(yīng)調(diào)整

對于優(yōu)勢種群,由于其結(jié)果比較好,所以需要使用較小的變異因子,FL=0.1．這樣使得優(yōu)勢種群的個體在變異過程中能夠較好的保持自身的優(yōu)勢,種群個體在變異中朝著最優(yōu)的方向搜索．

對于中間種群,由于數(shù)量較多,個體特性較為復(fù)雜,中間種群中較優(yōu)的個體與較差的個體之間適應(yīng)值差別較大,所以采用了線性自適應(yīng)調(diào)整策略．對于適應(yīng)值較小的個體采用較小的變異因子,適應(yīng)值較大的個體采用較大的變異因子，公式如下:

(6)

式中：Fi為中間種群中的第i個個體的變異因子；FL、FU分別為優(yōu)勢種群與劣勢種群的變異因子；fi為中間種群第i個個體的適應(yīng)值；X2為中間種群的進化個體；max(fX2)、min(fX2)分別為中間種群最大適應(yīng)值與最小適應(yīng)值．

對于劣勢種群,由于其結(jié)果較差,所以使用較大的變異因子,FU=0.9，從而保持種群內(nèi)部的差異性,防止算法收斂到局部最優(yōu)．

1.2.3 種群競爭策略

種群競爭策略是將算法每步迭代后的種群個體按照其自身的適應(yīng)值劃分成3個子種群,并且每個種群都擁有著不同的變異策略．處于優(yōu)勢種群內(nèi)的個體擁有較好的種群進化機制,相比于劣勢種群擁有更大的進化幾率,可以促進優(yōu)勢種群個體更好的進化,同時也能加快算法的收斂速度．處于中間種群中的個體,除了自適應(yīng)變異因子外對于個體的變異策略保持不變．對于劣勢種群中的個體,采用抑制其進化的策略，在該種群中,由于擁有較大的變異因子,其個體之間的差異也相對較大,通過使其個體以較小的概率進化、大概率停滯的策略可以使得該種群擁有很強的大差異性,有效地緩解了普通差分進化算法在進化過程中種群個體的差異性會逐漸減小的難題,這對于解決算法局部最優(yōu)的問題有著非常重要的意義．

優(yōu)勢種群變異策略如下:

(7)

劣勢種群變異策略如下:

(8)

式中：randn為一個服從均值為0,方差為1的正態(tài)分布的隨機數(shù)；xbest為當(dāng)前代內(nèi)最優(yōu)個體；rand(0,1)為0～1均勻分布的隨機數(shù)．

1.2.4 PCSADE算法流程

Step1:使用式(1)初始化種群,初始化算法相關(guān)參數(shù),設(shè)置最大迭代次數(shù);

Step2:計算初始個體的適應(yīng)值,并且找出初代的最優(yōu)個體xbest;

Step3:按照適應(yīng)值大小將種群排序,按照每個個體的序號將整體種群分為優(yōu)勢種群,中間種群,劣勢種群;

Step4:計算中間種群的自適應(yīng)變異因子,具體方法如式(6),將不同種群的個體按照各自的變異策略進行變異,其中優(yōu)勢種群使用式(7),劣勢種群使用式(8);

Step5:按照式(3)對當(dāng)前種群進行交叉操作;

Step6:按照式(4)對變異后的個體與當(dāng)前種群中的個體進行選擇操作;

Step7:判斷是否達到輸出結(jié)果的條件(精度達到要求或者到達最大迭代次數(shù)),若達到要求就輸出最優(yōu)解,若達不到要求就返回Step2．

2 實驗結(jié)果與分析

2.1 測試函數(shù)

文中通過6個測試函數(shù)對PCSADE算法進行性能測試,如表1．

表1 測試函數(shù)基本信息Table 1 Basic information of test functions

對于表中的6個經(jīng)典測試函數(shù),當(dāng)自變量x在每個特征維度上都為0時,會取到自己的谷值0．其中,Sphere函數(shù)、Schwefel函數(shù)和Zakharov函數(shù)為單峰函數(shù),用來檢驗算法的收斂精度和速度,可以通過這兩個指標(biāo)來衡量算法的執(zhí)行能力．Rastrigin函數(shù)、Ackley函數(shù)和Griewank函數(shù)為多峰函數(shù),用來檢測算法跳出局部最優(yōu)的能力．

2.2 實驗設(shè)計與分析

文中為了驗證PCSADE算法的性能,通過使用6個經(jīng)典測試函數(shù)將PCSADE、差分進化算法(differential evolution,DE)、粒子群算法(particle swam optimization，PSO)、協(xié)方差矩陣自適應(yīng)進化算法(cavariance Matrix adaptation evolution stratege,CMA-ES)[14]進行對比實驗．將6個測試函數(shù)分別作為優(yōu)化算法的適應(yīng)值函數(shù),并且按照它們各自的邏輯規(guī)則進行迭代尋優(yōu)．PCSADE算法的實驗參數(shù)設(shè)計如下:種群規(guī)模NP=100,個體維數(shù)dim=30,優(yōu)勢種群變異因子F1=0.1,劣勢種群變異因子F2=0.9,優(yōu)勢種群最優(yōu)個體指導(dǎo)變異的概率P=0.9,種群個體每個維度上特性最大值Xmax=1.28,最小值Xmin=-1.28,交叉率CR=0.9;DE算法參數(shù)設(shè)計如下:種群規(guī)模NP=100,個體維數(shù)dim=30,種群個體每個維度上特性最大值Xmax=1.28,最小值Xmin=-1.28,變異因子F=0.9,交叉率CR=0.9．PSO算法參數(shù)設(shè)計如下:種群規(guī)模NP=100,粒子維數(shù)dim=30,粒子在每個特性維度上的最大最小值分別為Xmax=1.28、Xmin=-1.28,粒子飛行速度的最大最小值分別為Vmax=1、Vmin=-1,學(xué)習(xí)因子c1=2、c2=2,速度更新權(quán)重w從0.9到0.4線性遞減;CMA-ES算法的參數(shù)設(shè)計如下:種群規(guī)模λ=10×(4+3logn),初始步長σ0=0.3(Varmax-Varmin),其中未知變量個數(shù)n設(shè)置為10,變量上下邊界Varmax、Varmin分別設(shè)置為10、-10．

為了能清晰地觀察這4種智能優(yōu)化算法分別在6個函數(shù)上的優(yōu)化結(jié)果,圖1為在這6個測試函數(shù)上的迭代曲線對比圖．

觀察圖1可以發(fā)現(xiàn),PSO算法在這6個測試函數(shù)中迭代少量步數(shù)之后曲線就趨于平緩,即PSO算法在這6個測試函數(shù)中很容易就陷入局部最優(yōu),最容易出現(xiàn)收斂早熟的現(xiàn)象．CMA-ES算法在f2和f6上經(jīng)過一定次數(shù)的迭代也陷入了局部最優(yōu)的情況;在f1和f4上經(jīng)過500次迭代還未到收斂點；在f5上經(jīng)過170次迭代后適應(yīng)度取對數(shù)值到達-16,依舊呈下降趨勢,并且在這些函數(shù)上曲線的下降速度優(yōu)于DE和PSO算法而劣于PCSADE算法;在f3上經(jīng)過大約330次迭代,CMA-ES算法可以找到全局最優(yōu)解,但它的收斂速度依然落后于PCSADE算法．DE算法在f2上經(jīng)過大約100次迭代的演化逐漸趨于平緩;在f1、f4和f6上經(jīng)過500次迭代依然未到達收斂點；在f5上經(jīng)過215次迭代最優(yōu)適應(yīng)值取對數(shù)到達-16,并且依舊保持下降趨勢,而在這4個函數(shù)上優(yōu)化結(jié)果曲線的下降速度都要小于PCSADE算法,甚至在f1、f4和f5的收斂速度還不如CMA-ES算法;在f3上函數(shù)經(jīng)過400次迭代到達收斂值,然而卻未到達最優(yōu)解．通過觀察發(fā)現(xiàn)PCSADE算法在上述6個函數(shù)中的性能表現(xiàn)都非常優(yōu)異:對于單峰值函數(shù)f1、f4和f6,PCSADE算法可以通過不同子種群間的競爭策略使得算法找到全局最優(yōu)，迭代次數(shù)大幅度減少;對于多峰值函數(shù)f2、f3和f5,PCSADE由于其對于適應(yīng)值較大的個體使用大變異因子F，使得適應(yīng)值大的個體一旦發(fā)生變異將會產(chǎn)生較大變化,從而增強算法在多峰值函數(shù)的情況下跳出局部最優(yōu)的能力．

圖1 數(shù)值仿真結(jié)果對比Fig.1 Comparison of numerical simulation results

3 結(jié)論

PCSADE算法是一種基于種群競爭,并使用自適應(yīng)變異因子策略來提高進化效果的優(yōu)化算法.通過種群競爭的方法可以提高算法的搜索效率,保證了種群個體在變異迭代中彼此之間的差異性,有效地解決了傳統(tǒng)差分進化算法多樣性隨著迭代次數(shù)增加而減少的這一難題．相比于現(xiàn)有的很多智能優(yōu)化算法,PCSADE算法體現(xiàn)出了優(yōu)異的性能,實用性也得到很大的提升．基于PCSADE算法的特點,未來可以進一步探索其在新領(lǐng)域中的應(yīng)用,擴展適用范圍,并且將其應(yīng)用解決具體工業(yè)實際問題．