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

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

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

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

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

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]雖然往往能較快的收斂到一個解，但可能會陷入局部最優(yōu)。而針對100位挑戰(zhàn)賽自適應(yīng)差分進(jìn)化算法(Self-adpative Differential Evolution Algorithm for 100-Digit ChallengejDE100)[9]是jDE算法的改進(jìn)算法，它加強(qiáng)了算法跳出局部的能力。它使用雙種群演化策略，大種群負(fù)責(zé)勘測，小種群負(fù)責(zé)探索，在一定條件下會重新初始化種群從而跳出局部陷阱。jDE100算法是CEC2019的100位挑戰(zhàn)賽[10]中唯一取得滿分的算法，但在部分函數(shù)上花費(fèi)了較多時間。jDE100算法雖然不易完全陷入局部，但它在一些優(yōu)化問題中有較大的時間開銷。

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

1 算法背景

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

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

(1)

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

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

(2)

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

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

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

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

(3)

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

(4)

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

(5)

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

(6)

1.2 jDE算法

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

(7)

(8)

1.3 JADE算法

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

1.4 jDE100算法

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

圖1 jDE100 算法流程圖

2 jDE-3算法描述

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

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

2.2 算法步驟

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

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

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

準(zhǔn)備:Ps小種群，sNP小種群的個體數(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個個體

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

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

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

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

3)檢查種群Pb指的是如果種群中最佳個體與種群種個體相似數(shù)在種群種占比大于等于myEqs%(最佳個體評價值與種群個體評價值的差值小于等于EPS=1e-16為相似)，則種群會被重新初始化。或者如果種群評價次數(shù)超過生命周期(大種群生命周期age1=1e9)，則同樣會重新初始化；

4)檢查種群Ps指的是如果種群中最佳個體與種群種個體相似數(shù)在種群種占比大于等于myEqs%(最佳個體評價值與種群個體評價值的差值小于等于EPS=1e-16為相似)，則種群會被重新初始化?；蛘呷绻N群評價次數(shù)超過生命周期(小種群生命周期age2=1e8)，則同樣會重新初始化。但會保留種群Ps的最佳個體。

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

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

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

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

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

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

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

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

(9)

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

表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算法針對各函數(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)的評價次數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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