基于小生境中適應(yīng)度共享的改進(jìn)DE算法

湯愷祥 許峰

摘 要：將小生境技術(shù)和適應(yīng)度共享思想引入DE算法中，用于改進(jìn)種群替代中子代選擇的優(yōu)化問題，具體做法是：首先根據(jù)DE算法中的變異、交叉及選擇操作得到子代種群，其次將這些子代種群通過小生境技術(shù)劃分為若干個(gè)小種群，并在每個(gè)小種群中利用適應(yīng)度共享方法選擇或剔除個(gè)體，最后將得到的子代和原父代合并作為下輪算法的父代種群。通過測試函數(shù)對改進(jìn)算法進(jìn)行了數(shù)值試驗(yàn)與性能測試，并與其他算法進(jìn)行了比較。結(jié)果顯示，改進(jìn)算法可在一定程度上提高最優(yōu)解的分布性。

關(guān)鍵詞：多目標(biāo)優(yōu)化;DE;小生境;適應(yīng)度共享;分布性

中圖分類號：O224;TP301.6? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2021）02-0001-05

2006年，Deb[1]和Brockhoff[2]指出，現(xiàn)實(shí)中的許多優(yōu)化問題是多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem， MOP），而其中的高維多目標(biāo)優(yōu)化問題（Many-dimensional Multi-objective Optimization Problem， MOP）的比重越來越高。由于實(shí)際操作表明MOEA在處理MOP時(shí)的能力不足，其表現(xiàn)在處理問題時(shí)性能的低下，對真實(shí)的Pareto前沿表示不準(zhǔn)確，結(jié)果分布性不均勻和穩(wěn)定性不理想等問題。

差分進(jìn)化算法（DE Algorithm）[3]，在解決多目標(biāo)問題時(shí)表現(xiàn)良好，有著效率高、全局搜索強(qiáng)和PF表現(xiàn)良好等[4]。但大量的實(shí)驗(yàn)DE算法在處理更為復(fù)雜的問題時(shí)，仍存在局部最優(yōu)、對PF表示不準(zhǔn)確以及解集分布不均勻等問題。

2005年，Rainer Storm[5]和Kenneth Price[5]在他們提出差分進(jìn)化算法的基礎(chǔ)上進(jìn)一步改進(jìn)了DE算法;2016年，Blasco[6]在進(jìn)行高維Pareto前沿分析時(shí)引入了相似距離;2017年，Bi[7]將小生境方法引入進(jìn)MOEA中;2018年，Monalisa[8]將聚類思想引入進(jìn)DE算法中;2019年，許峰[9]等提出了通過聚類操作約減DE算法的目標(biāo)函數(shù)。

在DE算法中并沒有考慮到：擇優(yōu)選擇操作后對得到的個(gè)體進(jìn)行進(jìn)一步優(yōu)化，剔除相似個(gè)體。本文將小生境技術(shù)與適應(yīng)度共享方法引入進(jìn)DE算法中，是為了優(yōu)化子代種群，以達(dá)到分布性改進(jìn)。

1 DE算法

DE算法可以解決連續(xù)變量的全體優(yōu)化問題，主要包含突變、交叉、選擇三種操作。當(dāng)使用DE算法求解最小化問題時(shí)，問題可以表述為：minf（x），XL≤X≤XU，其中XL，XU為變量X取值上的上限和下限。之后其主要概念及關(guān)鍵步驟如下：

1.1 種群初始化

設(shè)進(jìn)化代數(shù)G=（0，1，2，…，Gmax），其中Gmax為最大代數(shù)，當(dāng)前代種群中第i個(gè)體為：

Xi，f=（X1i，G，X2i，G，…，XDi，G）? （1）

其中，D為個(gè)體向量的維數(shù)，Xi，G為目標(biāo)向量。其初始化公式如下：

Xi（0）=XiL+rand（）·（XiU-XiL）? （2）

其中rand是[0，1]上的隨機(jī)數(shù)，之后Xi（0）表示為第0代群體上的第i個(gè)的個(gè)體。

1.2 變異操作

DE算法的變異操作基本流程為：在當(dāng)前種群中，隨機(jī)選取三個(gè)目標(biāo)向量，差分得到新的個(gè)體向量，稱之為變異向量。具體方法如下：

Xi，G=X+F·（X-X）? （3）

其中，F(xiàn)∈[0，2]稱之為變異尺度因數(shù)，作用是對變異向量進(jìn)行縮減操作，以此達(dá)到限制探索步長。通常情況下，F(xiàn)=0.5。

公式（3）被稱為DE/rand/1策略，其他的常用策略還包括以下內(nèi)容：

（1）DE/best/1策略

i，G=best，G+F·（-）? （4）

（2）DE/rand/1策略

i，G=+F·（-）+F·（-）? （5）

（3）DE/best/2策略

i，G=+F·（-）+F·（-）? （6）

（4）DE/current-to-best/1策略

i，G=+F·（-）+F·（-）? （7）

其中，為當(dāng)前種群中的最優(yōu)個(gè)體。

根據(jù)不同問題選擇適合的策略，可以得到變異個(gè)體。由于是隨機(jī)選擇三個(gè)個(gè)體，這保證了父代種群組成豐富，更能保證種群的多樣性。群成員個(gè)體之間：隨著迭代次數(shù)的增加，變化程度減小，DE算法效率得以提升。

1.3 交叉操作

個(gè)體間的交叉操作定義：個(gè)體Vi（t+1），對此個(gè)體進(jìn)行交叉操作，得到的個(gè)體稱之為實(shí)驗(yàn)個(gè)體，記為Ui（t+1）。在交叉操作中，至少保證有一組變異因子的維度，而其余維度則由交叉因子決定。交叉方式如下：

Uij（t+1）=Vi，j（t+1），rand（j）≤CR或j=kxij（t），其他? （8）

其中，xij（t）表示目標(biāo)個(gè)體Xi（t）中第j維向量，Ui，j（t+1）為突變個(gè)體且j=1，2，…，D，rand（j）∈[0，1]為隨機(jī)數(shù)，CR∈[0，1]表示交叉概率因子，K∈[1，2，…，D]代表第i個(gè)體對應(yīng)的系數(shù)。交叉操作可以通過控制參數(shù)來控制實(shí)驗(yàn)中個(gè)體自變異的更新內(nèi)容，由此控制種群個(gè)體的進(jìn)化程度。綜合上述操作，變異和交叉操作對DE算法的一些性質(zhì)如：收斂速率等的改變方向是一致的。

1.4 選擇操作

DE算法類似于其他進(jìn)化算法，都是通過“優(yōu)勝劣汰”法則對個(gè)體進(jìn)行選取。其過程如下：首先對目標(biāo)個(gè)體與實(shí)驗(yàn)個(gè)體進(jìn)行適應(yīng)度評價(jià)，其次對不同個(gè)體的適應(yīng)度值進(jìn)行區(qū)分，最后根據(jù)目標(biāo)優(yōu)化問題擇優(yōu)選取。其公式如下：

Xi（t+1）=Ui（t+1），f（Ui（t+1））

DE算法求解優(yōu)化問題時(shí)需要設(shè)定參數(shù)：

（1）種群規(guī)模NP，就是群體中所包含個(gè)體的總個(gè)數(shù)，一般由用戶根據(jù)實(shí)際問題的需要設(shè)定，NP越大，種群的多樣性越高，就有更高的概率獲得最優(yōu)解，但所需計(jì)算時(shí)間也越長;

（2）變異因子F。選取范圍0～2，一般初始值取 0.5;

（3）交叉概率CR，選取范圍0～1，設(shè)定初始值為0.4。

2 表現(xiàn)型適應(yīng)度共享方法

適應(yīng)度共享策略[10]的提出，為了解決解集分布不均勻的問題，提高種群多樣性。從啟發(fā)上來看這種方法，可以理解為：在一個(gè)資源有限的目標(biāo)空間中，如果生物個(gè)體眾多的話，會(huì)導(dǎo)致生物個(gè)體由于競爭資源而難以生存。對應(yīng)算法的表現(xiàn)為：種群分布性和多樣性變差以及進(jìn)化的效率變緩慢。這時(shí)我們可以將種群個(gè)體的適應(yīng)度按如下調(diào)整：

fi*=fi/sharing（dij）? （10）

其中：fi代表為未修正種群個(gè)體與修正后種群個(gè)體的親密度，n為種群個(gè)體數(shù)目，其中dij為抗體i與j之間的距離，共享函數(shù)的定義如下：

sharing（dij）=1-di，j/？滓share，dij<？滓share0，其他，? （11）

其中？滓share代表著和共享參數(shù)，即種群個(gè)體之間保持距離的期望值。

在距離方面，Goldberg[11]指出表現(xiàn)型適應(yīng)度共享策略要優(yōu)于基因型適應(yīng)度共享策略。這代表著，個(gè)體i與個(gè)體j之間親密度的歐式距離要優(yōu)于個(gè)體間的距離，也就是個(gè)體i，j在目標(biāo)空間里的距離。如圖1所示。

3 基于小生境中適應(yīng)度共享的改進(jìn)DE算法

DE算法從變異和交叉的方向分析，該算法的優(yōu)點(diǎn)是個(gè)體都是隨意選取的，這保證了父代有多種組織方式，使得能確保算法中種群的多樣性。群成員中的個(gè)體之間隨著迭代次數(shù)的增加程度減小，這使得DE算法收斂速度增加。DE算法可以在PF復(fù)雜（如不連續(xù)的PF或具有尖峰的PF）的情況下，很大程度上保證實(shí)驗(yàn)種群的均勻性和確保解集均勻分布在PF上。

但是從種群個(gè)體擇優(yōu)選擇的方向分析，該算法中，交叉變異產(chǎn)生一個(gè)好子代可以取代大部分差的子代，并且在選擇操作中好的子代被選擇的概率大大增加，這就導(dǎo)致種群多樣性變差，即種群替換方向存在缺陷。因此，在利用該算法時(shí)，要確保算法在變異交叉的步驟不變的情況下，改進(jìn)選擇操作后的步驟以達(dá)到合理的互補(bǔ)。所以，本文提出了一種基于小生境中適應(yīng)度共享的改進(jìn)DE算法，這使得滿足原優(yōu)點(diǎn)的同時(shí)，盡可能確保種群多樣性和解的分布性。具體定義及流程如下：

定義清除算法（小生境）相關(guān)距離：

D（A，B）=1- （12）

其中A=（a1，a2，…，an）T，B=（b1，b2，…，bn）T為n維向量，且D（A，B）∈[0，2]。

個(gè)體i=（x1，x2，…，xn）與個(gè)體j=（y1，y2，…，yn）的距離公式為：

d（i，j）=? （13）

（14）

小生境中心點(diǎn)為X1，X2，…，Xm，其余個(gè)體為Y1，Y2，…，YM，D（Xm，YM）表示中心點(diǎn)與個(gè)體間的相關(guān)距離。相關(guān)距離越大，個(gè)體與中心點(diǎn)越近。

基于小生境中適應(yīng)度共享的改進(jìn)DE算法步驟如下：

步驟1 初始化，得到初始種群P，設(shè)置變異因子和交叉因子;

步驟2 根據(jù)DE算法流程更新操作;

2.1 對父代種群Pt，根據(jù)DE算法流程變異交叉擇優(yōu)選擇的操作得到U;

2.2 對U采取清除算法（小生境）操作，即首先對U中個(gè)體根據(jù)適應(yīng)度值進(jìn)行降序排列，將第一個(gè)個(gè)體作為第一個(gè)小生境中心。其次利用上述相關(guān)距離方法判斷當(dāng)前個(gè)體到所有小生境中心的最短距離是否大于自定義數(shù)值，是則形成新的小生境，不是則加入最近的小生境中。最后小生境生成完畢，多出的個(gè)體降低其適應(yīng)值;

2.3 將生成的每個(gè)小生境進(jìn)行適應(yīng)度共享操作，即首先，將每個(gè)小生境中的個(gè)體根據(jù)先前得出的適應(yīng)度優(yōu)劣排序;其次，設(shè)置共享函數(shù)中期望值的范圍（即兩個(gè)個(gè)體之間親和度的歐拉距離），如果兩個(gè)個(gè)體之間期望值越大，則親和度越近，即兩個(gè)體相似，將這兩個(gè)個(gè)體保留較好的，舍棄較差的;最后重復(fù)上述操作直到遍歷完所有的點(diǎn);

2.4 將每個(gè)小生境中剩余的個(gè)體合并得到子代種群Qt;

2.5 將Pt和Qt合并且根據(jù)聚合函數(shù)更新父代種群Pt+1;

步驟3 若滿足終止條件，則輸出最終的解，否則重復(fù)步驟2。

4 數(shù)值實(shí)驗(yàn)與算法性能評測

4.1 算法性能評測指標(biāo)

MOEA性能評測指標(biāo)分為四種，具體為容量指標(biāo)、收斂性指標(biāo)、多樣性指標(biāo)、收斂性和多樣性綜合指標(biāo)[12]。根據(jù)本文新算法的優(yōu)化點(diǎn)為分布性的改進(jìn)，考慮采用分布性指標(biāo)（S）與綜合指標(biāo)（IGD）。定義如下：

S（A）=? （15）

其中dx=|fi（x）-fi（x*）|，=dx，|A|表示集合A個(gè)體總數(shù)，k表示目標(biāo)函數(shù)個(gè)數(shù)。S指標(biāo)越小，空間內(nèi)解集分布越均勻，即算法分布性越好。

IGD（P*，P）=? （16）

其中P*表示理想PF，P表示算法求得的近似PF，d（v，P）表示個(gè)體v到P中個(gè)體的最小歐幾里德距離。IGD指標(biāo)越小，算法分布性越好。

4.2 數(shù)值實(shí)驗(yàn)結(jié)果

為了評測本文提出的基于小生境適應(yīng)度共享的DE算法分布性，用此算法對兩個(gè)標(biāo)準(zhǔn)測試函數(shù)Osyczka2和Viennet4進(jìn)行數(shù)值實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與經(jīng)典的DE多目標(biāo)進(jìn)化算法[12]的優(yōu)化結(jié)果進(jìn)行了比較。

（1）Osyczka2函數(shù)

F（x）=（f1（x），f2（x））f1（x）=-25（x1-2）2+（x2-1）2+（x3-1）2? ?+（x4-4）2+（x5-1）2f2（x）=x12+x22+x32+x42+x52+x620≤x1，x2，x6≤103≤x3，x5≤51≤x4≤60≤x1+x2-20≤6-x1-x20≤2+x1-x20≤2-x1+3x20≤4-（x3-3）2-x40≤（x5-3）2-x6-4

（2）Viennet4函數(shù)

F（x）=（f1（x），f2（x），f3（x））f1（x）=++3f2（x）=+-13f3（x）=++15-4≤x1，x2≤4x2<-4x1+4x1>-1x2>x1-2

為了更準(zhǔn)確、定量地衡量本文算法的性能，下面給出本文算法和常規(guī)DE算法的S和IGD的對比數(shù)據(jù)。由于計(jì)算結(jié)果有隨機(jī)性，下列數(shù)據(jù)為10次計(jì)算結(jié)果的平均值。

5 結(jié)論

圖4～圖5直觀顯示，基于小生境適應(yīng)度共享的DE算法在解的分布性和均勻性方面均明顯優(yōu)于常規(guī)DE多目標(biāo)進(jìn)化算法。表1和表2中的指標(biāo)很清楚地進(jìn)一步表明，本文改進(jìn)算法的S指標(biāo)和IGD指標(biāo)均明顯占優(yōu)。

綜上，可以得出明確的結(jié)論：基于小生境適應(yīng)度共享的DE多目標(biāo)進(jìn)化算法較常規(guī)DE多目標(biāo)進(jìn)化算法在分布性和均勻性方面有了明顯的提高。

——————————

參考文獻(xiàn)：

〔1〕DEB K， SAXENA D. Searching for Pareto-optimal Solutions through Dimensionality Reduction for Certain Large-dimensional Multi-objective Optimization Problems [C] // Proceedings of the World Congress on Computational Intelligence （WCCI-2006）， 2006， 3352–3360.

〔2〕BROCKHOFF D， ZITZLER E. Are All Objectives Necessary？ On Dimensionality Reduction in Evolutionary Multi-objective Optimization [C] // Parallel Problem Solving from Nature PPSN IX， Springer， 2006， 533-542.

〔3〕STOM R，PRICE K，LAMPINEN J. Differential evolution： a practical approach to global optimization[M]. Berlin： Springer-Verlag， 2005.

〔4〕STOM R，PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Global optimization， 1997， 11（04）：341-359.

〔5〕SUN J，ZHANG Q. DE/EDA： a new evolutionary algorithm for global optimization[J]. Information science，2004，169（3-4）：249-262.

〔6〕BLASCO X， REYNOSO-MEZA G. Asymmetric Distances to Improve n-dimensional Pareto Fronts Graphical Analysis [J]. Information Sciences，2016， 340： 228-249.

〔7〕Xiaojun Bi， Chao Wang.A niche-elimination operation based NSGA-III algorithm for many-objective optimization [J]. Applied Intelligence， 2017， 48：118-141.

〔8〕MONALISA P， SRIPARNA S， SANGHAMITRA B. DECOR： Differential Evolution Using Clustering Based Objective Reduction for Many-objective Optimization [J]. Information Sciences，2018， 423： 200-218.

〔9〕車旭，許峰.基于聚類的目標(biāo)約簡高維多目標(biāo)差分進(jìn)化算法[J].安徽理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，40（01）.

〔10〕GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization[C] //Proceedings of the 2nd International Conference on Genetic Algorithms. Hillsdale： L. Lawrence Erlbaum Associates， 1987： 41-49.

〔11〕DEB K， GOLDBERG D E. An investigation of niche and species formation in genetic function optimization[C] //Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco， California： Morgan Kaufmann Publishers， 1989： 42-50.

〔12〕鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2007.