多種群協(xié)同進(jìn)化的差分進(jìn)化算法＊

章猛，鄒德旋，徐福強(qiáng)，羅鴻赟

(江蘇師范大學(xué)電氣工程及自動化學(xué)院，江蘇 徐州 221116)

0 引言

差分進(jìn)化算法（Differential Evolution，DE）在1997年Storn和Price發(fā)表的文章[1]中正式提出，是一種基于群體的進(jìn)化算法。它借助種群個(gè)體之間的差分信息來影響個(gè)體的進(jìn)化方向，并通過貪婪選擇的方式將適應(yīng)度更優(yōu)的個(gè)體保留，經(jīng)過不斷的進(jìn)化得到最優(yōu)解。但在面對復(fù)雜的全局優(yōu)化問題時(shí)，DE 算法容易出現(xiàn)收斂精度低、陷入局部最優(yōu)等問題。針對這些問題，國內(nèi)外的學(xué)者提出來許多的改進(jìn)方案，以提高DE算法的優(yōu)化性能。

從變異策略的研究來看，文獻(xiàn)[2]中提出一種“Top-bottom”策略：根據(jù)適應(yīng)度進(jìn)行排序，將種群的前75%個(gè)體和后75%個(gè)體構(gòu)成檔案庫，從中選擇個(gè)體構(gòu)成差分向量以一定的概率來維持種群多樣性，將大部分個(gè)體導(dǎo)向潛在的更有希望的區(qū)域；文獻(xiàn)[3]提出一種新的變異策略DE/Alopex/1，根據(jù)適應(yīng)度值計(jì)算兩個(gè)個(gè)體相關(guān)性和特殊參數(shù)“溫度”，進(jìn)一步來計(jì)算不同的移動方向的概率，引導(dǎo)個(gè)體向優(yōu)質(zhì)區(qū)域移動。文獻(xiàn)[4]提出DE/neighbor/1 策略，以N 個(gè)個(gè)體構(gòu)成的鄰域內(nèi)選擇最優(yōu)個(gè)體作為基向量，從剩余個(gè)體隨機(jī)選擇個(gè)體構(gòu)成差分向量，平衡DE的全局探索和局部開發(fā)能力。

從控制參數(shù)調(diào)整方面來看，文獻(xiàn)[5]使用正態(tài)分布隨機(jī)數(shù)和柯西分布隨機(jī)數(shù)來進(jìn)行控制參數(shù)的自適應(yīng)調(diào)整，并使用權(quán)重萊默均值的方式來控制均值，提高“精英”信息對參數(shù)更新的作用。文獻(xiàn)[6]提出新的參數(shù)AF 代表種群的分散程度，根據(jù)分散程度判斷控制參數(shù)F和CR是在原來的程度上增加或減少，配合不同的變異策略平衡全局探索和局部開發(fā)。

從引入優(yōu)良機(jī)制方面來看，文獻(xiàn)[7]使用了外部存檔的方法，可以選擇該外部存檔中的一些高質(zhì)量解決方案作為候選解決方案。文獻(xiàn)[8]中設(shè)計(jì)局部搜索半徑，在最優(yōu)個(gè)體附近搜索四個(gè)節(jié)點(diǎn)運(yùn)用牛頓三次插值進(jìn)行局部搜索，提高算法收斂性能。

基于以上學(xué)者的研究，本文提出多種群協(xié)同進(jìn)化的差分進(jìn)化算法（Multi-population Coevolution Differential Dvolution，MCDE）。本算法提出雙序法進(jìn)行種群劃分：同時(shí)使用適應(yīng)度值排序和距離系數(shù)排序?qū)⒎N群分為三個(gè)子種群：優(yōu)秀種群、次優(yōu)種群和普通種群；針對不同種群的特點(diǎn)，使用不同的變異策略和控制參數(shù)；同時(shí)針對普通種群采用概率判定的方式確定個(gè)體的變異策略來加快收斂速度。為了驗(yàn)證本文算法的性能，采用CEC2017[9]標(biāo)準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果證明本算法與其他算法相比性能更好。

1 標(biāo)準(zhǔn)差分進(jìn)化算法

1.1 種群初始化

初始化階段主要是確定各種初始參數(shù)：種群數(shù)量NP、變量維度D、可行域、變異因子F、交叉因子CR；以及使用均勻隨機(jī)數(shù)的方式產(chǎn)生初代種群，具體公式如下：

其中，xi,j表示第i個(gè)粒子的第j維；i=1,2,…,NP，j=1,2,…,D。rand()表示[0,1]內(nèi)的均勻隨機(jī)數(shù)。xmax，xmin表示可行域的最大值和最小值。

1.2 變異

變異部分主要是通過差分向量和基向量進(jìn)行加權(quán)求和得到下一代個(gè)體，從而實(shí)現(xiàn)個(gè)體變異。常見的變異策略如下：

1.3 交叉

1.4 選擇

通過貪婪選擇的方式在實(shí)驗(yàn)個(gè)體與父代個(gè)體之間選出更優(yōu)秀的個(gè)體做為子代個(gè)體。具體公式如下：

2 多種群協(xié)同進(jìn)化的差分進(jìn)化算法

2.1 基于適應(yīng)度值和歐氏距離的種群劃分

在本文使用雙序法將種群劃分為優(yōu)秀種群X1、次優(yōu)種群X2、普通種群X3。首先將種群個(gè)體按照適應(yīng)度函數(shù)值進(jìn)行排序得到種群Y1，然后按照公式⑻計(jì)算每個(gè)個(gè)體與最優(yōu)個(gè)體的距離系數(shù)di，并按距離排序得到種群Y2：

di代表第i個(gè)粒子與全局最優(yōu)粒子之間的距離系數(shù)，di越小，該粒子離最優(yōu)粒子越近。

本文基于二八法則[10]，將種群Y1和種群Y2的前20%提出來構(gòu)成種群Y3和種群Y4。若個(gè)體xi在Y3內(nèi)卻不在Y4內(nèi)，則其屬于種群X2。以種群Y2剩余個(gè)體內(nèi)離全局最優(yōu)粒子最近的粒子為邊界，距離更近的粒子劃入種群X1，距離較遠(yuǎn)的粒子劃入種群X3。同時(shí)種群X1內(nèi)的個(gè)體數(shù)量上限為0.5*NP。

采用該劃分方式將由公式⑴得到的50 個(gè)個(gè)體放置函數(shù)的等值線圖中具體分類如圖1 所示，其中三角形代表種群X1，圓代表種群X3，五角星代表種群X2。

圖1 子種群分布圖

2.2 種群的策略選取

對于種群X1的個(gè)體來說，它們存在于以xbest為圓心的圓形區(qū)域內(nèi)，適合使用搜索能力強(qiáng)且搜索精度高的變異策略。因此選用DE/current-to-best/1 策略，其中K=0.1。種群X2的個(gè)體所處位置是全局最優(yōu)個(gè)體的候選位置，選取的是DE/rand/1 策略，有利于快速篩選確定全局最優(yōu)位置。

本文根據(jù)在ESCDE[11]中提出DE/rand assemble/1策略得到思路提出了一種變異策略稱作DE/rand*3/1如式⑼所示：

根據(jù)種群X3的特點(diǎn)，個(gè)體的適應(yīng)度值差且與xbest的距離不理想。因此通過調(diào)整基向量的方式來促使個(gè)體向更優(yōu)的個(gè)體學(xué)習(xí)。采用概率判定法來決定變異策略的選擇來保證種群多樣性。具體的策略選擇如下：

其中，參數(shù)W是根據(jù)sigmoid 函數(shù)提出，一種新的參數(shù)，表達(dá)式如下：

其中，T=30·(g/G-0.5)，g為當(dāng)前迭代次數(shù)，G為最大迭代次數(shù)。當(dāng)種群X2的種群數(shù)量未超過種群數(shù)量的1%時(shí)，認(rèn)為已經(jīng)找到了全局最優(yōu)解的位置，此時(shí)，若g/G＜1/2，則T=30·g/G,以加強(qiáng)局部探索能力。

2.3 參數(shù)自適應(yīng)機(jī)制

在DE算法中變異率F決定變異個(gè)體的移動步長，交叉率CR決定實(shí)驗(yàn)個(gè)體從變異個(gè)體繼承基因的概率。固定的控制參數(shù)不能適應(yīng)各種問題，還容易影響優(yōu)化進(jìn)度。因此本文采用自適應(yīng)的方式獲得種群X1控制參數(shù)，公式如下：

由上式可獲得在[μF-0.1,μF+0.1]和[μCR-0.1,μCR+0.1]內(nèi)的正態(tài)分布隨機(jī)數(shù)，參數(shù)μF和μCR按式⒁和式⒂進(jìn)行更新。

其中，F(xiàn)max=0.9，F(xiàn)min=0.2;，CRmax=0.9，CRmin=0.5。由此可得種群X1在其范圍內(nèi)同時(shí)兼具很強(qiáng)的局部探索能力和全局探索能力。種群X2和種群X3要保持種群多樣性，因此，參數(shù)F選擇[0,1]內(nèi)的均勻隨機(jī)數(shù)，參數(shù)CR的選取如下：

2.4 MCDE算法流程圖

MCDE算法的流程圖如圖2所示。

圖2 MCDE算法流程圖

3 函數(shù)仿真與分析

3.1 測試函數(shù)

為了評估本文所提出的MCDE 算法，將在CEC2017 測試函數(shù)集的30 個(gè)測試函數(shù)上進(jìn)行仿真實(shí)驗(yàn)。其中中F1～F3 為單峰函數(shù)，F(xiàn)4～F10 為多峰函數(shù)，F(xiàn)11～F20為混合函數(shù)，F(xiàn)21～F30為復(fù)合函數(shù)。

3.2 參數(shù)設(shè)置

另外選擇四種近年優(yōu)秀的算法MDE[7]、DE-BMS[12]、DE/Alopex/1[3]、HSDE[13]與MCDE 算法相對比。各算法在30 維的情況下，NP=100、G=3000；在100 維時(shí)，NP=200、G=5000。各算法的參數(shù)設(shè)置遵循原文獻(xiàn)。為了避免隨機(jī)因素對算法的影響，每個(gè)算法獨(dú)立運(yùn)行30 次。實(shí)驗(yàn)環(huán)境為：處理器Intel(R) Core(TM) i5-8265U CPU@ 1.60GHz 1.80 GHz，RAM 12GB，Win10 64位操作系統(tǒng)，MATLAB R2019a。

3.3 仿真實(shí)驗(yàn)結(jié)果

表1 和表2 表示MCDE 算法和其他比較算法在低維（D=30）和高維（D=100）時(shí)的平均值和方差比較，其中最好的數(shù)據(jù)結(jié)果以加粗字體表示。

表1 MCDE與其他算法結(jié)果對比（D=30）

圖3～圖8 是低維時(shí)函數(shù)F1，F(xiàn)10，F(xiàn)21 和高維時(shí)函數(shù)F5，F(xiàn)20，F(xiàn)22的收斂曲線圖。

3.4 算法收斂精度分析

表1 是各算法在30 維時(shí)的實(shí)驗(yàn)數(shù)據(jù)對比結(jié)果，從表中數(shù)據(jù)可已看出，在平均值指標(biāo)方面，MCDE算法在30 個(gè)測試函數(shù)中取得了20 個(gè)第一和四個(gè)第二的成績，其余測試函數(shù)除F22 和F30 以外都與比較算法中得到的最優(yōu)結(jié)果相差不大，說明MCDE 算法具有很強(qiáng)的收斂精度。從方差值指標(biāo)來看，MCDE 算法取得了六個(gè)第一、七個(gè)第二，在算法穩(wěn)定性上也有一定的保障。綜上所述，MCDE 算法在低維（D=30）的情況下，在單峰函數(shù)，多峰函數(shù)和復(fù)合函數(shù)上較其他算法有明顯的優(yōu)勢，在混合函數(shù)上也能取得較好的表現(xiàn)。

表2 是各算法在100 維情況下的平均值，方差的數(shù)據(jù)對比結(jié)果，從平均值指標(biāo)上來看，MCDE 算法在F2、F5、F7、F8、F10、F16、F17、F20、F21、F22、F23、F24、F26、F29 等14 個(gè)測試函數(shù)上的收斂精度優(yōu)于其他比較算法，且在其他測試函數(shù)上的優(yōu)化結(jié)果與比較算法的最優(yōu)結(jié)果接近。綜和表1 和表2 來看，無論是在低維（D=30）還是在高維（D=100）的情況下，MCDE 算法較其他對比算法，均具有明顯的優(yōu)勢，這說明MCDE算法的種群劃分方法、概率判定機(jī)制及變異策略能夠有效的提高算法的尋優(yōu)能力和收斂精度。

3.5 算法收斂曲線分析

圖3～圖8表示的是各算法在不同的測試函數(shù)上的收斂曲線圖，圖3～圖5是低維的情況下的函數(shù)收斂圖。從圖3 中可以看出，MCDE 算法在函數(shù)F1 上的收斂速度略慢于MDE算法，比其他算法均快，并且和MDE算法同時(shí)得到全局最優(yōu)值。從圖4 和圖5 中可以看出MCDE 算法在函數(shù)F10 和F21 上的收斂速度不是最快的，但卻是最穩(wěn)的，精度最高的，盡管收斂速度出現(xiàn)波動，但沒有陷入局部最優(yōu)值，這也表明了本文的雙序法種群劃分的效果。圖6～圖8是高維的情況下的函數(shù)收斂圖。從圖8 可以看出MCDE 算法在函數(shù)F22 上收斂速度存在一個(gè)劇烈變化的過程，但沒有陷入局部最優(yōu)，收斂精度是所有算法中最高的。從圖6、圖7 可以看出，MCDE 算法在函數(shù)F5 和函數(shù)F20 上能以最快的速度得到最好的結(jié)果，且全程收斂曲線平緩，未陷入局部最優(yōu)。

圖3 F1函數(shù)測試結(jié)果（D=30）

圖4 F10函數(shù)測試結(jié)果（D=30）

圖5 F21函數(shù)測試結(jié)果（D=30）

圖6 F5函數(shù)測試結(jié)果（D=100）

圖7 F20函數(shù)測試結(jié)果（D=100）

圖8 F22函數(shù)測試結(jié)果（D=100）

4 總結(jié)

本文提出來一種多種群協(xié)作的差分進(jìn)化算法（MCDE），首先提出雙序法，同時(shí)使用距離系數(shù)排序和適應(yīng)度排序，將全局最優(yōu)粒子的侯選位置劃分出來；同時(shí)根據(jù)不同子種群的特點(diǎn)來選擇合適的變異策略，并對普通種群選用概率判定法選擇變異策略更好的平衡全局探索能力和局部搜索能力，避免陷入局部最優(yōu)。通過MCDE 算法和近年來先進(jìn)算法在CEC2017測試函數(shù)集上的實(shí)驗(yàn)結(jié)果看，無論是在低維還是在高維情況下，MCDE 算法的收斂精度和收斂能力整體上優(yōu)于其他比較算法，且在進(jìn)化過程中沒有發(fā)生陷入局部最優(yōu)的情況。但也存在收斂速度波動較大的缺點(diǎn)，接下來將針對該問題進(jìn)行深入研究。綜上所述，MCDE算法是一種有效可靠的全局優(yōu)化算法。