基于種群競(jìng)爭(zhēng)的自適應(yīng)差分進(jìn)化算法

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

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

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

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

1 種群競(jìng)爭(zhēng)自適應(yīng)差分進(jìn)化算法

1.1 差分進(jìn)化算法

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

1.1.1 種群初始化

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

(1)

1.1.2 種群變異

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

vi=xr1+F(xr2-xr3)

(2)

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

1.1.3 交叉操作

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

(3)

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

1.1.4 選擇操作

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

(4)

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

1.2 種群競(jìng)爭(zhēng)自適應(yīng)差分進(jìn)化算法

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

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

1.2.1 子代種群的劃分

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

(5)

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

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

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

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

(6)

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

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

1.2.3 種群競(jìng)爭(zhēng)策略

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

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

(7)

劣勢(shì)種群變異策略如下:

(8)

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

1.2.4 PCSADE算法流程

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

2.1 測(cè)試函數(shù)

文中通過(guò)6個(gè)測(cè)試函數(shù)對(duì)PCSADE算法進(jìn)行性能測(cè)試,如表1．

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

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

2.2 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

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

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

3 結(jié)論

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