基于三種群演化策略的自適應(yīng)差分進(jìn)化算法

鄧峻 魏文紅* 張宇輝 李清霞

(1.東莞理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523808；2.東莞城市學(xué)院 計(jì)算機(jī)與信息學(xué)院，廣東東莞 523419)

演化算法是通過模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)的生物進(jìn)化過程，構(gòu)建出來(lái)的仿生算法。它可以通過模擬自然進(jìn)化的迭代過程，搜索評(píng)價(jià)函數(shù)的最優(yōu)解。而差分進(jìn)化算法(Differential Evolution，DE)[1]是進(jìn)化算法的一個(gè)重要分支，它采用實(shí)數(shù)編碼，適用于解決實(shí)數(shù)參數(shù)優(yōu)化問題，并成功應(yīng)用于現(xiàn)實(shí)世界的各種優(yōu)化問題[2-3]。如今，人們已經(jīng)對(duì)它做了許多改進(jìn)[4-6]。

一般情況下，優(yōu)化問題常常被定義為最小值優(yōu)化問題，最大值優(yōu)化問題則可以轉(zhuǎn)成最小值優(yōu)化問題。全局優(yōu)化問題的目標(biāo)是找到一個(gè)向量，使得目標(biāo)函數(shù)評(píng)價(jià)值最小。一般地，向量由D個(gè)變量組成，D是目標(biāo)函數(shù)的維度，每個(gè)變量由其下界和上界定義。

在單目標(biāo)優(yōu)化問題中，目標(biāo)函數(shù)可能有多個(gè)局部最優(yōu)，而一個(gè)好的優(yōu)化算法則需要找到全局最優(yōu)。如果算法陷入局部最優(yōu)，則有兩種可能。一是跳出局部最優(yōu)，尋求更優(yōu)解；另一種是淪陷于局部最優(yōu)，直到算法結(jié)束。其中，算法跳出局部的能力與算法的搜索路徑將一定程度上影響算法求解最優(yōu)值的計(jì)算時(shí)間。通常在一些復(fù)雜的優(yōu)化問題上，往往將會(huì)花費(fèi)大量的計(jì)算時(shí)間。

DE算法與其他優(yōu)化算法一樣容易陷入局部最優(yōu)，存在過早收斂的問題。為了提高DE算法的性能，許多DE的改進(jìn)算法被提出。具有最優(yōu)外部存檔的自適應(yīng)差分進(jìn)化算法(Adaptive Differential Evolution with Optional External Archive，JADE)[7]引入了額外存檔以及新的自適應(yīng)參數(shù)機(jī)制，增加了種群的多樣性，一定程度上緩解了過早收斂的問題。自適應(yīng)差分進(jìn)化算法(jDE)[8]雖然往往能較快的收斂到一個(gè)解，但可能會(huì)陷入局部最優(yōu)。而針對(duì)100位挑戰(zhàn)賽自適應(yīng)差分進(jìn)化算法(Self-adpative Differential Evolution Algorithm for 100-Digit ChallengejDE100)[9]是jDE算法的改進(jìn)算法，它加強(qiáng)了算法跳出局部的能力。它使用雙種群演化策略，大種群負(fù)責(zé)勘測(cè)，小種群負(fù)責(zé)探索，在一定條件下會(huì)重新初始化種群從而跳出局部陷阱。jDE100算法是CEC2019的100位挑戰(zhàn)賽[10]中唯一取得滿分的算法，但在部分函數(shù)上花費(fèi)了較多時(shí)間。jDE100算法雖然不易完全陷入局部，但它在一些優(yōu)化問題中有較大的時(shí)間開銷。

受jDE100算法思想的啟發(fā)，本文針對(duì)jDE100算法進(jìn)行了改進(jìn)，提出了一種具有三個(gè)種群進(jìn)行演化的自適應(yīng)差分進(jìn)化算法jDE-3，該算法在保障較強(qiáng)的全局搜索能力的前提下，縮短了計(jì)算時(shí)間。針對(duì)CEC2019的100位挑戰(zhàn)賽的實(shí)驗(yàn)測(cè)試，與其他采取差分進(jìn)化策略的算法進(jìn)行比較，該算法成功地通過了CEC2019的100位賽的挑戰(zhàn)。此外，還試著通過實(shí)驗(yàn)探討該算法面對(duì)高維問題下的參數(shù)調(diào)整。

1 算法背景

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

差分進(jìn)化算法[1]是一種依賴于種群的進(jìn)化算法，它的種群由NP個(gè)個(gè)體組成，每個(gè)個(gè)體擁有D個(gè)變量，隨著迭代數(shù)的改變，種群也隨之變化，最終算法會(huì)在最大迭代數(shù)下終止。

(1)

Pg表示第g代的種群，表示第g代種群中第I個(gè)個(gè)體的基因向量。

每一個(gè)個(gè)體向量由D個(gè)變量構(gòu)成：

(2)

D是每一個(gè)個(gè)體向量的維度，每一個(gè)個(gè)體由D個(gè)變量組成，表示第g代種群下第I個(gè)個(gè)體中的第j個(gè)變量。

差分進(jìn)化算法的流程如下：

1)初始化：在迭代開始之前，種群會(huì)被隨機(jī)初始化，每個(gè)個(gè)體向量中的變量，會(huì)對(duì)應(yīng)其值的上下界隨機(jī)生成均勻分布的值。xj_low，xj_upp分別代表變量在維度j下取值的下界與上界，具體如式(3)：

xi,j=xj_low+rand()*(xj_upp-xj_low)，

(3)

2)變異：一個(gè)變異向量將會(huì)通過DE的變異策略產(chǎn)生。例如‘DE/rand/1’策略：

(4)

3)交叉：種群中的每一個(gè)個(gè)體將會(huì)與對(duì)應(yīng)的變異向量進(jìn)行交叉操作。

(5)

4)選擇：在第g次迭代中，經(jīng)歷變異，交叉操作后，種群產(chǎn)生了NP個(gè)，稱為嘗試個(gè)體。這些嘗試個(gè)體將會(huì)與種群的原本個(gè)體進(jìn)行評(píng)價(jià)值比較，擁有更優(yōu)秀的評(píng)價(jià)值者會(huì)被保留。這些保留者會(huì)組成新的種群，進(jìn)行下一次迭代。

(6)

1.2 jDE算法

jDE算法[7]繼承了DE算法的基本策略，但對(duì)兩個(gè)控制參數(shù)，即縮放因子F和交叉率CR采用自適應(yīng)機(jī)制。每個(gè)個(gè)體都有屬于自己的控制參數(shù)值F和CR。新增控制參數(shù)Fl和Fu，表示F的上下界；控制參數(shù)CRl和CRu，表示CR的上下界。

(7)

(8)

1.3 JADE算法

與jDE算法相似，JADE算法[10]，除了控制參數(shù)自適應(yīng)機(jī)制有所改變，還增加了新的存檔機(jī)制以及變異策略。每個(gè)個(gè)體都有屬于自己的控制參數(shù)值F和CR，其變化與uCR和uF相關(guān)。uCR和uF一定程度上代表整個(gè)種群在某一迭代中，控制參數(shù)CR和F較為合適的中間值。而存檔機(jī)制是在選擇階段，存儲(chǔ)評(píng)估值交叉的個(gè)體基因向量，在變異階段中，有機(jī)會(huì)采用存檔中的基因向量，以達(dá)到基因多樣性的目的。

1.4 jDE100算法

jDE100算法[6]是jDE算法的改進(jìn)算法。與jDE算法不同的是，它有兩個(gè)演化種群，一個(gè)大的種群Pb負(fù)責(zé)全局探索，一個(gè)小的種群Ps負(fù)責(zé)局部開發(fā)。兩個(gè)種群都采用jDE的基本策略，大的種群在變異階段有概率獲取小種群的基因向量，若在大的種群發(fā)現(xiàn)了當(dāng)代全局最佳，則小種群的某個(gè)個(gè)體會(huì)被取代，以達(dá)到大小種群基因交流的目的。其中若種群收斂到一定程度，則會(huì)觸發(fā)種群重新初始化的機(jī)制，重新搜索。jDE100算法流程圖如圖1所示。

圖1 jDE100 算法流程圖

2 jDE-3算法描述

2.1 算法思想與改進(jìn)

jDE-3算法是針對(duì)jDE100的改進(jìn)算法。相較于jDE100算法，jDE-3算法采用三個(gè)種群進(jìn)行演化。前期先用單個(gè)種群Pt按照jDE策略進(jìn)行探索，探索后如果條件未滿足，則大種群Pb將繼承Pt探索的基因向量。這樣設(shè)計(jì)的目的是為了提高算法前期的探索效率，由于Pt種群遠(yuǎn)小于Pb，不會(huì)過于影響Pb的多樣性，這樣既加快了探索效率，又不會(huì)過于影響探索精度。大種群Pb以及小種群Ps將繼續(xù)探索。其中小種群重新初始化的條件和大種群一樣增加了生命周期作為限制，以防止小種群陷入若干個(gè)局部最優(yōu)，無(wú)法繼續(xù)探索。

2.2 算法步驟

根據(jù)算法思想，jDE-3的算法具體步驟如下：

準(zhǔn)備:Pt試探種群，tNP試探種群的個(gè)體數(shù)

準(zhǔn)備:Pb大種群，bNP大種群的個(gè)體數(shù)

準(zhǔn)備:Ps小種群，sNP小種群的個(gè)體數(shù):bNP=m×sNP, m ∈ 1, 2, …

1: 初始化種群，隨機(jī)產(chǎn)生Pt={x1,x2,…,xtNP}

2: 初始化種群，隨機(jī)產(chǎn)生Pb={x1,x2,…,xbNP}

3: 初始化種群，隨機(jī)產(chǎn)生Ps={x1,x2,…,xsNP}

4: 初始化Fi= 0.5;CRi= 0.9; (i∈ {1,tNP+bNP+sNP})

5: while 當(dāng)終止條件1未滿足

6: for each i ∈Ptdo

7: 執(zhí)行 jDE 變異策略

8: 執(zhí)行 jDE 交叉策略

9: 執(zhí)行 jDE 選擇策略

10: end for

11: end while

12:Pt覆蓋Ps前tNP個(gè)個(gè)體

12: while 當(dāng)終止條件2未滿足

13: 檢查種群Pb

14: 檢查種群Ps

15: for each i ∈Pbdo

16: 執(zhí)行 jDE 變異策略

17: 執(zhí)行 jDE 交叉策略

18: 執(zhí)行 jDE 選擇策略

21: end if

22: for k ∈ 1, 2, …, m do . repeat m-times

23: for each i ∈Psdo

24: 執(zhí)行 jDE 變異策略

25: 執(zhí)行 jDE 交叉策略

26: 執(zhí)行 jDE 選擇策略

27: end for

28: end for

29: end while

在算法中，有以下幾個(gè)方面是需要值得注意的：

1)終止條件1：當(dāng)最優(yōu)解達(dá)到10位正確精度或者評(píng)價(jià)次數(shù)超過1e5；

2)終止條件2：當(dāng)最優(yōu)解達(dá)到10位正確精度后或者評(píng)價(jià)次數(shù)超過1e10則跳出；

3)檢查種群Pb指的是如果種群中最佳個(gè)體與種群種個(gè)體相似數(shù)在種群種占比大于等于myEqs%(最佳個(gè)體評(píng)價(jià)值與種群個(gè)體評(píng)價(jià)值的差值小于等于EPS=1e-16為相似)，則種群會(huì)被重新初始化?；蛘呷绻N群評(píng)價(jià)次數(shù)超過生命周期(大種群生命周期age1=1e9)，則同樣會(huì)重新初始化；

4)檢查種群Ps指的是如果種群中最佳個(gè)體與種群種個(gè)體相似數(shù)在種群種占比大于等于myEqs%(最佳個(gè)體評(píng)價(jià)值與種群個(gè)體評(píng)價(jià)值的差值小于等于EPS=1e-16為相似)，則種群會(huì)被重新初始化。或者如果種群評(píng)價(jià)次數(shù)超過生命周期(小種群生命周期age2=1e8)，則同樣會(huì)重新初始化。但會(huì)保留種群Ps的最佳個(gè)體。

5)Pb種群的jDE變異策略與原本略有不同，它額外增加了Ps的第一個(gè)成員作為可選擇成員，讓Ps的基因向量能在Pb中流通。

6)復(fù)制策略是當(dāng)Pb探索種群搜索到當(dāng)前最優(yōu)解的時(shí)候，將該成員覆蓋Ps的第一個(gè)成員，讓種群Ps開發(fā)這一個(gè)優(yōu)質(zhì)解。

7)種群Ps在每一輪迭代中，重復(fù)執(zhí)行了m次。這里設(shè)定，它的jDE策略和原始jDE策略一致。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)描述

實(shí)驗(yàn)主要圍繞不同算法在CEC2019特別會(huì)議上10個(gè)基準(zhǔn)函數(shù)的測(cè)試表現(xiàn)。在表1中，描述了這10個(gè)函數(shù)的基本信息。函數(shù)的維數(shù)從9維到18維不等，但大多數(shù)函數(shù)都是10維。在這個(gè)挑戰(zhàn)賽中，所有基準(zhǔn)函數(shù)的最優(yōu)解值都為1，但需要達(dá)到十位精度，即1.000 000 000。在以往的競(jìng)賽中，目標(biāo)功能評(píng)價(jià)的最大數(shù)量是有限的，但這一挑戰(zhàn)賽對(duì)時(shí)間或功能評(píng)價(jià)的最大數(shù)量都沒有限制。

在100位數(shù)字挑戰(zhàn)賽中[9]有10個(gè)問題，目標(biāo)是在不受時(shí)間限制的情況下計(jì)算每個(gè)函數(shù)的最小值到10位的精度。該挑戰(zhàn)賽要求參賽者用一種算法解決十個(gè)問題，允許對(duì)每個(gè)函數(shù)進(jìn)行有限的控制參數(shù)調(diào)優(yōu)。對(duì)于每個(gè)函數(shù)，需要50次連續(xù)測(cè)試，且每個(gè)算法具有不同的初始種群。在50次的實(shí)驗(yàn)測(cè)試中，我們最優(yōu)的25次結(jié)果，則該函數(shù)的分?jǐn)?shù)是最優(yōu)的25個(gè)試驗(yàn)中正確數(shù)字的平均數(shù)目。如果超過一半或一半以上的試驗(yàn)找到所有正確的10位數(shù)，那么該函數(shù)的得分是10分，10個(gè)函數(shù)的總分最高為100分。

由于100位數(shù)字挑戰(zhàn)賽中沒有高維測(cè)試函數(shù)，為了探討jDE-3在高維問題下的參數(shù)選擇，將測(cè)試集中第四個(gè)測(cè)試函數(shù)Rastrigin’s Function進(jìn)行擴(kuò)展(無(wú)偏移和旋轉(zhuǎn))：

(9)

分別測(cè)試jDE-3在該測(cè)試函數(shù)30維、50維、80維和100維下達(dá)到10位正確精度，即1.000 000 000所花費(fèi)的評(píng)價(jià)次數(shù)。對(duì)每一種情況進(jìn)行30次測(cè)試。

表1 CEC2019 100-digit函數(shù)介紹

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

在該挑戰(zhàn)賽中，DE算法獲得43.72分，jDE算法獲得68.08分，JADE算法獲得46分，jDE100算法獲得100分，jDE-3算法獲得100分。表2至表6分別為DE算法、jDE算法、JADE算法、jDE100算法和jDE-3算法針對(duì)各函數(shù)挑戰(zhàn)所得的詳細(xì)分?jǐn)?shù)。其中DE算法的參數(shù)CR和F默認(rèn)為0.9和0.5；jDE算法的參數(shù)CRinit=0.9，F(xiàn)init=0.5，tau1=0.1，tau2=0.1；JADE算法的參數(shù)uF=0.5，uCR=0.5，c=0.1，p=0.1；jDE100算法的參數(shù)與文獻(xiàn)[8]中的一致；jDE-3算法的參數(shù)與jDE100算法基本一致。所有種群大小Pt為80，調(diào)整的參數(shù)CRl與Fl詳見表9。

表2 DE算法詳細(xì)得分

jDE-3不同參數(shù)下優(yōu)化高維問題見表7，其中CRl取值為0。

表3 jDE算法詳細(xì)得分

表4 JADE算法詳細(xì)得分

表5 jDE100算法詳細(xì)得分

表6 jDE-3算法詳細(xì)得分

表7 jDE-3算法在不同參數(shù)下優(yōu)化高維問題所花費(fèi)的評(píng)價(jià)次數(shù)

3.3 實(shí)驗(yàn)對(duì)比與分析

在所有比較的算法之中，只有jDE100算法和jDE-3算法取得了100分。下面將比較這兩個(gè)算法直接花費(fèi)的評(píng)價(jià)次數(shù)。表10為jDE-3算法的在各函數(shù)中所花費(fèi)的評(píng)估數(shù)分析，其中取50次連續(xù)運(yùn)行中最好的25次作為統(tǒng)計(jì)數(shù)據(jù)。表8為jDE-3算法與jDE100算法的評(píng)估數(shù)比較，比較方式為jDE100算法的評(píng)估數(shù)與jDE-3算法的評(píng)估數(shù)差值除以jDE算法的評(píng)估數(shù)，+50%表示jDE-3算法比jDE100算法花費(fèi)的評(píng)價(jià)次數(shù)要少50%。由表可以看出，如果通過迭代次數(shù)的中值進(jìn)行比較，jDE-3算法在函數(shù)F1、F2、F3、F5、F7、F8和F10花費(fèi)的評(píng)價(jià)次數(shù)更少；如果通過迭代次數(shù)的平均值進(jìn)行比較，jDE-3算法在函數(shù)F1、F2、F3、F7、F8和F10花費(fèi)的評(píng)價(jià)次數(shù)更少。表9為jDE-3算法的參數(shù)設(shè)置，只允許調(diào)整Fl和CRl兩個(gè)參數(shù)。圖6至圖7分為各算法在函數(shù)F1、F2、F3、F7、F8、F10收斂圖對(duì)比，其中橫軸代表評(píng)估數(shù)，縱軸代表達(dá)到的精度位數(shù)。

在jDE-3算法中，主要調(diào)整的參數(shù)為Fl和CRl，分別為縮放因子和交換概率的下限，在一般情況下，F(xiàn)l的取值影響較大。由于采取jDE策略，每個(gè)個(gè)體對(duì)應(yīng)的參數(shù)F和CR將根據(jù)演化過程自適應(yīng)。當(dāng)Fl取值過小，種群的個(gè)體可能因?yàn)閖DE中的貪婪策略，使個(gè)體對(duì)應(yīng)的F長(zhǎng)期保持較小值，影響種群的全局搜索，陷入局部；當(dāng)Fl取值過大，F(xiàn)的取值受限，不能取到較小值，種群可能難以較快收斂到足夠的精度。

由表7可以看到，當(dāng)Fl取值過低，jde-3在面對(duì)高維多局部值的優(yōu)化問題中容易多次陷入局部，需要花費(fèi)更多的額外代價(jià)跳出局部尋求全局最優(yōu)。而Fl也不是越大越好，應(yīng)是一個(gè)適中的值。

表8 jDE-3算法和jDE100算法在評(píng)價(jià)次數(shù)比較 %

表9 jDE-3算法的參數(shù)設(shè)置

表10 jDE-3算法在所有50次運(yùn)行中的25次最佳記錄，包含函數(shù)評(píng)估數(shù)(FES)的最佳、最差、中位數(shù)、均值和標(biāo)準(zhǔn)差值

圖2 函數(shù)F1收斂圖對(duì)比

圖3 函數(shù)F2收斂圖對(duì)比

圖4 函數(shù)F3收斂圖對(duì)比

圖5 函數(shù)F7收斂圖對(duì)比

圖6 函數(shù)F8收斂圖對(duì)比

圖7 函數(shù)F10收斂圖對(duì)比

4 結(jié)語(yǔ)

為了在保證單目標(biāo)優(yōu)化問題中精度的前提下減少時(shí)間代價(jià)，受jDE100算法啟發(fā)，提出了一種基于三種群演化策略的自適應(yīng)差分進(jìn)化算法jDE-3來(lái)解決CEC2019中100位挑戰(zhàn)的問題。jDE-3算法采用自適應(yīng)控制參數(shù)F和CR，利用三個(gè)種群進(jìn)行演化，第一個(gè)種群在前期進(jìn)行快速勘測(cè)，后兩個(gè)種群負(fù)責(zé)長(zhǎng)期的探索與開采。在整個(gè)算法的進(jìn)化過程中，小種群的重新初始化機(jī)制被修改，使其更容易跳出局部最優(yōu)。最后經(jīng)過實(shí)驗(yàn)證明，jDE-3算法不僅能精確地求解CEC2019中函數(shù)F1-F10的全部問題，還在絕大部分函數(shù)上比其他DE算法及其變種節(jié)約了求解時(shí)間。