多種群協同進化的差分進化算法＊

章猛，鄒德旋，徐福強，羅鴻赟

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

0 引言

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

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

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

從引入優良機制方面來看，文獻[7]使用了外部存檔的方法，可以選擇該外部存檔中的一些高質量解決方案作為候選解決方案。文獻[8]中設計局部搜索半徑，在最優個體附近搜索四個節點運用牛頓三次插值進行局部搜索，提高算法收斂性能。

基于以上學者的研究，本文提出多種群協同進化的差分進化算法（Multi-population Coevolution Differential Dvolution，MCDE）。本算法提出雙序法進行種群劃分：同時使用適應度值排序和距離系數排序將種群分為三個子種群：優秀種群、次優種群和普通種群；針對不同種群的特點，使用不同的變異策略和控制參數；同時針對普通種群采用概率判定的方式確定個體的變異策略來加快收斂速度。為了驗證本文算法的性能，采用CEC2017[9]標準測試函數進行仿真實驗，結果證明本算法與其他算法相比性能更好。

1 標準差分進化算法

1.1 種群初始化

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

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

1.2 變異

變異部分主要是通過差分向量和基向量進行加權求和得到下一代個體，從而實現個體變異。常見的變異策略如下：

1.3 交叉

1.4 選擇

通過貪婪選擇的方式在實驗個體與父代個體之間選出更優秀的個體做為子代個體。具體公式如下：

2 多種群協同進化的差分進化算法

2.1 基于適應度值和歐氏距離的種群劃分

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

di代表第i個粒子與全局最優粒子之間的距離系數，di越小，該粒子離最優粒子越近。

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

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

圖1 子種群分布圖

2.2 種群的策略選取

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

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

根據種群X3的特點，個體的適應度值差且與xbest的距離不理想。因此通過調整基向量的方式來促使個體向更優的個體學習。采用概率判定法來決定變異策略的選擇來保證種群多樣性。具體的策略選擇如下：

其中，參數W是根據sigmoid 函數提出，一種新的參數，表達式如下：

其中，T=30·(g/G-0.5)，g為當前迭代次數，G為最大迭代次數。當種群X2的種群數量未超過種群數量的1%時，認為已經找到了全局最優解的位置，此時，若g/G＜1/2，則T=30·g/G,以加強局部探索能力。

2.3 參數自適應機制

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

由上式可獲得在[μF-0.1,μF+0.1]和[μCR-0.1,μCR+0.1]內的正態分布隨機數，參數μF和μCR按式⒁和式⒂進行更新。

其中，Fmax=0.9，Fmin=0.2;，CRmax=0.9，CRmin=0.5。由此可得種群X1在其范圍內同時兼具很強的局部探索能力和全局探索能力。種群X2和種群X3要保持種群多樣性，因此，參數F選擇[0,1]內的均勻隨機數，參數CR的選取如下：

2.4 MCDE算法流程圖

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

圖2 MCDE算法流程圖

3 函數仿真與分析

3.1 測試函數

為了評估本文所提出的MCDE 算法，將在CEC2017 測試函數集的30 個測試函數上進行仿真實驗。其中中F1～F3 為單峰函數，F4～F10 為多峰函數，F11～F20為混合函數，F21～F30為復合函數。

3.2 參數設置

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

3.3 仿真實驗結果

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

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

圖3～圖8 是低維時函數F1，F10，F21 和高維時函數F5，F20，F22的收斂曲線圖。

3.4 算法收斂精度分析

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

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

3.5 算法收斂曲線分析

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

圖3 F1函數測試結果（D=30）

圖4 F10函數測試結果（D=30）

圖5 F21函數測試結果（D=30）

圖6 F5函數測試結果（D=100）

圖7 F20函數測試結果（D=100）

圖8 F22函數測試結果（D=100）

4 總結

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