廖雄鷹,李俊,羅陽坤,李波
1.武漢科技大學計算機科學與技術學院,武漢430065
2.智能信息處理與實時工業系統湖北省重點實驗室,武漢430065
基于自適應變異算子的差分進化算法
廖雄鷹1,2,李俊1,2,羅陽坤1,2,李波1,2
1.武漢科技大學計算機科學與技術學院,武漢430065
2.智能信息處理與實時工業系統湖北省重點實驗室,武漢430065
差分進化算法[1](Differential Evolution,DE)是一種簡單而又有效的用于解決函數優化問題的智能算法,具有原理簡單、控制參數少、魯棒性強和易于實現等特點。從1995年被Storn和Price提出至今,已在多個工程領域得到了成功應用,例如化工[2]、人工神經網絡[3]和機器人[4]等。
DE算法中提出了多種基本的變異策略,不同策略具有不同的性能。為適應更為復雜的優化問題和滿足更高的求解質量,研究人員不斷地挖掘不同策略的潛能,在基本變異策略的基礎上設計和改進出了一些新穎的變異算子。Fan和Lampinen[5]提出了一種三角變異算子,該算子利用隨機選擇的三個個體中最好個體的信息,引導實驗向量向其靠近;Price等[6]提出一種DE/rand/1/either-or算子,該算子將DE/rand/1和一個重組算子相混合,并通過參數來控制兩個算子的選擇;Das等[7]提出一種具有鄰域搜索能力的DE/target-to-best/1變異算子,為平衡算法的勘探能力和開采能力,與原有DE/target-tobest/1變異算子進行混合,提出了DEGL算法;受粒子群優化算法啟發,Zhang和Sanderson在JADE[8-9]中提出了一種DE/current-to-pbest/1算子,該算子不僅利用種群中最好個體的信息,還利用鄰域中較好的個體的信息;Wu等[10]結合DE/rand/1/bin、DE/best/rand/1/bin勘探和開采的優勢,提出一種自適應變異算子;Wang等[11]提出一種精英變異策略,該算法從種群中選擇20%的個體作為精英個體指導算法的搜索,在勘探和開采中找到一個較好的平衡。張錦華等[12]為平衡全局勘探能力和局部搜索能力,提出一種加權變異策略動態差分進化算法。這些研究工作對變異策略進行了改進,在一定程度上提高了DE的性能。
然而DE及諸多變種仍然存在收斂速度慢和易陷入局部最優等問題,特別是在進化后期,DE的種群多樣性降低,收斂速度下降,很容易導致算法陷入局部最優。為保持DE的種群多樣性,避免早熟,加快收斂速度,本文提出一種基于自適應變異算子的差分進化算法(A differential evolution algorithm based on adaptive mutation operator,AMODE)。算法提出一種基于種群聚集度自適應的變異算子,它依據種群個體的聚集度自適應地調整DE/best/1變異算子和加權異維學習變異算子的變異權重:在種群個體分散時,DE/best/1變異算子的權重占優,保證算法的收斂速度;隨著種群個體之間的差異性變小,種群愈發聚集時,加權異維學習變異算子的權重增大,從而可以有效增強種群的多樣性,避免算法陷入局部最優,進一步加快算法收斂速度,提高算法的求解精度。通過對20個典型的測試函數的實驗結果表明,與其他7種具有代表性的算法相比,本文提出的算法在收斂速度和求解精度上有很大提高。
差分進化算法(DE)主要操作有群體初始化、變異操作、交叉操作、選擇操作等。其主要思想是將同一群體中兩個互不相同的個體向量進行差分以及縮放,并與該群體中的第三個個體向量相加得到一個變異個體向量,然后變異個體向量與父代個體向量以一定概率進行雜交生成嘗試個體向量;最后,將嘗試個體向量與父代個體向量進行貪婪選擇,較優個體向量被保存到下一代群體當中。
其中,變異操作是DE產生后代個體的主要方式,它通過差分變換來產生新的變異個體,這種生成變異個體的方式即稱為變異算子。常見的變異算子如下所示:

其中F∈[0,1]為縮放因子,i,r1,r2,r3,r4,r5為[1,NP]上的隨機整數,且互不相等。各個算子各有其優劣:其中,“rand”變異方式的DE算法能有效保持整個種群的多樣性,從而具有良好的全局探索能力,但也存在收斂速度慢的問題;基于“best”變異方式的DE進化模式,以當前種群中適應度最好的個體作為基矢量,具有良好的局部開發能力和快速收斂的特性,但很容易陷入局部最優點而導致早熟。
為了更好描述AMODE算法,本文特提出了個體向量粒子、維度層、種群聚集度等定義。
定義1個體向量粒子。對于群體P中的第i個個體,令個體的個體維度為D,記為:

定義2維度層。如圖1所示,一層代表一個維度,表示群體P的所有個體在這一維度上的個體向量粒子的集合,將這個集合定義為一個維度層。

圖1 種群的維度層示意圖
由公式(1)~(3)可知,在傳統的差分進化算法中,對于一個變異向量而言,它在第j維上的個體向量粒子均來源于這一維度,即變異向量的個體向量粒子的變異來源維度層固定,則對于一個單獨的維度層而言,它的變異、交叉、選擇操作是獨立的、與其他維度層無關的,即各個維度層的進化過程是獨立且無關聯的。
定義3種群聚集度。設群體規模為NP,D表示群體個體的緯度,為種群在第k維度層上的個體向量粒子的平均值,Xik為個體Xi在第k維上的個體向量粒子,則種群聚集度C可以定義為:

定義3表明,種群聚集度C體現了種群個體的聚集程度:C越小,說明種群個體的差異性越小,聚集程度就越高;反之,說明種群個體分散,種群多樣性良好。因而,種群聚集度C可以很好地描述種群個體的聚集程度。
種群聚集度C越大,種群的多樣性就越差,算法就越容易陷入局部最優,從而導致早熟。
定義4異維學習(Different Dimensional Learning,DDL)[13-14]。在種群P的維度層中隨機選出第j,m維兩個維度層且m≠j,則異維學習定義為:

其中,i,a,b,c為[1,NP]上的隨機整數,且互不相等。個體在第j維維度層上的個體向量粒子變異來源于第m維維度層,因而被稱為異維學習。
異維學習概念由李冰等[13]在異維學習人工蜂群算法中被提出,因其搜索具有跳躍性的特點,可以很好地提高觀察蜂群跳出局部最優的概率。鑒于異維學習的優點,本文創新性地將異維學習策略引入差分演化算法中。
在差分演化算法中引入異維學習策略的依據為:若群體某一維度層或者某幾個維度層由于個體向量粒子聚集程度很高而使算法陷入局部最優,則單靠它自身維度層的探索開發很難或者不能跳出當前狀態。而對整個種群,其各個維度層的進化過程是獨立且無關聯的,這時就可以借助其他維度層上的優秀個體向量粒子對本維度層進行跳躍式地搜索,進而跳出早熟狀態。這樣就可以減少算法陷入局部最優的概率,加快算法的收斂速度。
但對于上述異維學習而言,它的異維維度m的選取是完全隨機的,這種不同維度層之間的隨機的異維學習具有很大盲目性和不確定性,可能導致算法早熟、收斂速度受到限制。為此,本文提出一種基于維度層加權的異維維度選擇策略:設Qk(k∈[1,D])為第k個維度層在第g代進化時被選擇參與變異的概率權重,初始值為1/D,更新公式如下:

其中,g(g>LP)為當前進化的代數(為保證進化信息統計的最新性和有效性,選擇最新的LP代作為樣本)。Sj,t為第j個維度層在第t代進化中參與變異且成功進入下一代群體的數目,而Ej,t為第j個維度層在第t代進化中參與變異但進入下一代群體失敗的數目。進化時,對各維度層的概率權重Qk(k∈[1,D])采取隨機廣義選擇的方式確定變異的異維維度K。基于這一異維維度選擇策略,提出一種加權異維學習變異算子:

其中i,r1,r2,r3為[1,NP]上的隨機整數,且互不相等;j,K∈[1,D]表示個體的維度,其中K是由公式(5)的Qk(k∈[1,D])采用隨機廣義選擇方式確定變異的異維維度。此變異算子的基矢量來源于不同于j維的其他維度層,可以引進其他維度層的優秀個體向量粒子對當前維度層進行跳躍式的優化搜索。
DE變異策略有多種不同的變化形式,每一種變化形式都有其自身的特點,對算法的側重點也不一樣,有的強調全局搜索能力,而有的強調收斂速度。如:基于“best”變異方式的DE算法,以當前種群中適應度最好的個體作為基矢量,具有良好的局部開發能力和加快收斂特性,但很容易陷入局部最優而導致早熟。
產生早熟的根本原因是隨著迭代次數的增加,個體之間的差異性減小,種群多樣性下降。為解決種群多樣性下降的問題,本文在“best”變異的基礎上引入加權異維變異的策略,依據種群聚集度(種群多樣性)自適應地調整DE/best/1變異算子和加權異維學習變異算子的變異權重:在進化的前期,種群個體分散,多樣性良好時,讓DE/best/1變異算子的權重占優,能充分地發揮DE/best/1變異策略快速收斂的特性;而隨著進化的不斷推進,種群個體之間的差異性變小,種群聚集愈發明顯,種群多樣性降低時,就要加大加權異維學習變異算子的變異權重,增加種群的多樣性,保證算法的收斂性能。由前面分析可知,各個維度層的進化過程是獨立且無關聯的,所以各維度層的個體向量粒子在進化后期仍然具有良好的差異性,這樣就可以借助其他維度層上的優秀個體向量粒子對本維度層進行跳躍式地搜索,從而增加種群的多樣性,避免早熟,同時也能保證算法的收斂速度和解的精度。
本文結合DE/best/1和加權異維學習兩種變異算子,綜合兩者的優勢,提出一種基于種群聚集度自適應的變異算子:

其中F∈[0,1]為縮放因子,i,r1,r2,r3,r4,r5為[1,NP]上的隨機整數,且互不相等;j,K∈[1,D]且K≠j表示個體的維度,K是對公式(5)中的Qk(k∈[1,D])采用隨機廣義選擇方式確定的變異的異維維度。C為種群聚集度,代表種群當前的聚集程度,當C?[0.05,0.95]時,將C截斷到[0.05,0.95]的區間內。
這種基于種群聚集度自適應的變異策略在保證快速收斂的同時,又能很好地解決因種群多樣性下降算法陷入局部最優而導致的早熟問題,大大提高了DE的收斂性能。
AMODE算法具體實現步驟如下:
(1)產生初始化群體X0
(2)評價群體X0中所有個體的適應值,并選出最優適應值個體Xtbest
(3)初始化種群聚集度C和群體各維度層的概率權重Qk
(4)While未滿足終止條件do
(5)

(6)隨機均勻選擇r1≠r2≠r3≠r4≠r5≠i
(7)隨機產生整數jrand∈[1,D]
(8)由Qk采用隨機廣義選擇方式確定變異的異維維度K

(21)依據式(4)計算種群Xt當前的種群聚集度C
(22)根據式(5)調整群體各維度層的概率權重Qk
(23)end while
AMODE算法流程圖,如圖2所示。
根據3.4節中AMODE算法步驟分析其時間復雜度,設其中種群規模為NP,問題維度為D,迭代次數為T。第(1)~(3)步群體初始化,第(2)步適應度函數評價和第(3)步參數初始化操作均為O(NP×D)。
第(10)步變異和交叉操作為O(D),則第(5)~(12)步每一次迭代計算為O(NP×D)。第(13)~(19)步的選擇操作、第(20)步的最優個體選擇操作、第(21)步的種群聚集度更新操作和第(22)步的群體各維度層的概率權重調整均為O(NP×D)。則(4)~(22)步總的時間復雜度為O(T×NP×D)。
綜上所述,AMODE算法總的時間復雜度為O(T×NP×D),僅與T、NP和D有關。AMODE算法與標準DE算法的時間復雜度一致,對算法的改進沒有增加過多的開銷。

圖2 AMODE算法流程圖
為驗證AMODE算法的高效性和魯棒性,選擇在20個典型的測試函數[15-16]上進行實驗,其中,f1~f7為單模態函數;f8~f13為多模態函數;f14~f20為偏移函數[16]。對所有的測試函數分別選取維數D=30和D=100進行仿真實驗,測試函數的具體相關信息如表1所示。
實驗中的算法由MATLAB語言實現,軟件為MATLAB 2012b。運行環境為:Windows 7、雙核3.2 GHz CPU、4 GB內存。
為驗證AMODE算法性能,選取了DE/best/1、DE/current-to-best/1、DE/rand/1/either-or[6]、DEGL[8]、JADE[9,17]等變異策略的進化算法,以及與基本粒子群算法PSO[18]、基本遺傳算法GA[19]等經典算法作比較,對測試函數進行尋優仿真。
AMODE算法參數設置為縮放因子F=0.5,交叉概率Cr=0.9。為了比較的公平,種群規模NP均為40,最大進化代數為5 000代,文中涉及“best”變異策略的算法參數設置為:縮放因子F=0.5,交叉概率Cr=0.9;使用“rand”變異策略的算法參數設置為:縮放因子F=0.5,交叉概率Cr=0.1;PSO算法加速因子設置為c1=c2=2,其慣性權重w=0.712;GA算法交叉概率設置為0.5,交叉概率為0.1;其他參數與其參考文獻中的保持一致。為消除在運行過程中隨機因素的影響,每個測試函數獨立運行30次。

表120 個典型測試函數

表2 D=30時AMODE算法與其他算法的實驗結果及統計
實驗分為兩組,一組的測試函數為D=30;另一組的測試函數為D=100。實驗記錄各個算法運行得到的最優適應度值的平均值(Mean)與標準差(Std Dev),表2為函數為30維的實驗結果,表3為函數為100維時的測試結果。為客觀地評價AMODE算法與對比算法在測試函數上的性能差異程度,采用Wilcoxon秩和檢驗方法對實驗結果進行了統計分析,其中“+”、“-”、“≈”分別表示對比算法的性能要優于、劣于、相當于AMODE算法。
當D=30時,從表2最后三行可以看出,AMODE算法在大部分函數上的求解精度要優于其他幾種算法,且在15個函數上的求解標準差均為0,穩定性要遠遠高于其他算法。相比于DE/best/1、DE/current-to-best/1和DEGL算法,AMODE算法在10個函數上求解的精度更優;相比于DE/rand/1/either-or和JADE算法,AMODE算法在9個函數上求解的精度更優;較之PSO算法和GA算法,AMODE分別在19個、18個函數上求解的精度更優。雖然在函數f5、f8和f9上,AMODE算法取得的效果一般,但在大部分函數上都取得了極好的最優值,在一些函數上收斂到了全局最優值。且AMODE算法求解穩定性最好,在15個函數上的求解標準差均為0,占總測試函數的75%,高于DE/best/1算法的50%和JADE算法的40%。
當D=100時,各算法的實驗結果如表3所示,從中可以看出隨著維數的增加,DE/best/1、DE/current-tobest/1、DE/rand/1/either-or、DEGL、JADE等算法的性能均大幅度下降,但是同比于D=30時,AMODE算法仍保持良好的收斂性能,甚至在個別函數如f12、f19上有了小幅度的提高,收斂性能受維度的影響很小,具有非常好的魯棒性。AMODE算法在大部分函數上的求解精度要遠遠優于其他幾種算法,從表3的最后三行可以看出,AMODE算法的求解精度在18個函數上比DE/best/1、DE/current-to-best/1、DE/rand/1/either-or、DEGL算法和GA算法更優,在17個函數上比JADE算法更優,在19個函數上較之PSO算法更優。在其他算法收斂精度大幅度下降的情況下,AMODE算法在大部分函數上仍然取得了極好的最優值,并且AMODE算法仍然在14個函數上的求解標準差為0,穩定性要遠遠高于其他算法。
從表2和表3可以看出,無論是D=30或D=100時,在大部分函數上,AMODE算法的收斂精度以及穩定性較之其他算法更優。
為了進一步研究AMODE算法在不同函數上的收斂速度,特意選取一個較高的維度(D=100)時,在20個測試函數上進行實驗。實驗結果表明:在其他算法的收斂速度受到高緯度的限制時,AMODE算法在大多數函數上的收斂速度較之其他算法更快,仍具有較高的收斂性能。圖3給出了D=100時各算法在測試函數上的收斂曲線,其中lg表示以10為底色的對數(限于篇幅,只給出具有代表性的6個函數)。
從圖3可以看出,在Sphere函數上,AMODE算法的收斂速度要顯著地快于其他對比算法;而對于Quartic函數而言,因其是一個帶噪聲的函數,求解比較困難,但從圖3的求解圖像可以看出,AMODE算法對減輕噪聲有效果,且收斂速度更快;在Ackley函數上,雖然AMODE算法在求解精度上的改進相對較小,但表現出了更快的收斂速度;在偏移函數f15上,AMODE算法表現出了極快的收斂速度;f15加上噪聲因素時即變f16為偏移函數,在函數f16上的收斂曲線再次表明AMODE算法具有消除噪聲效果,且收斂速度更快。AMODE算法在多數測試函數上都取得了良好的收斂速度,效果顯著,然而,對于一些具有特殊性質的測試函數來說,比如f8(Schwefel 2.26)和f9(Rastrigin),它們的適應度函數地貌非常具有欺騙性,在搜索范圍內存在非常多的局部最小值點,且全局最優點所處位置特殊,使得AMODE算法效果一般。

表3 D=100時AMODE算法與其他算法的實驗結果及統計
綜上以上實驗分析可以發現,雖然AMODE算法在極少數函數上的性能不佳,但對于絕大多數函數而言,基于種群聚集度自適應的變異策略較大地提高了DE算法的收斂速度和收斂精度,同其他7種對比算法相比,AMODE算法的優化性能仍具有很大的優勢,且穩定性更佳。

圖3 D=100時各算法的收斂曲線
為保持DE的種群多樣性,避免早熟,加快收斂速度,本文算法提出一種基于種群聚集度自適應的變異算子,該算子依據種群個體當前的的種群聚集度自適應地調整DE/best/1算子和加權異維學習變異算子的變異權重,充分發揮DE/best/1算子快速收斂和加權異維學習變異算子增強種群的多樣性、避免算法陷入局部最優的特點。通過一系列對比實驗表明,本文提出的算法在求解精度和收斂速度上取得了很大進步,且具有良好的穩定性。但也在個別函數,如f8、f9上性能不佳,針對這些特殊函數,如何進一步提高它們的性能,需要進行更加深入的研究。
[1] Storn R,Price K.Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[2] Liu C,Song X,Xu T,et al.An operation optimization method based on improved EDA for BOF end-point control[C]//IEEE Congress on Evolutionary Computation,2016:1077-1084.
[3] Leema N,Nehemiah H K,Kannan A.Neural network classifier optimization using differential evolution with global information and back propagation algorithm for clinical datasets[J].Applied Soft Computing,2016,49:834-844.
[4] Jiang L,Qiu H,Wu Z,et al.Active disturbance rejection control based on adaptive differential evolution for twowheeled self-balancing robot[C]//Chinese Control and Decision Conference,2016.
[5] Fan H Y,Lampinen J.A trigonometric mutation operation to differential evolution[J].Journal of Global Optimization,2003,27(1):105-129.
[6] Price K,Storn R,Lampinen J.Differential evolution:A practical approach for global optimization[M].Berlin:Springer Verlag,2005.
[7] Das S,Abraham A,Chakraborty U K,et al.Differential evolution using a neighborhood-based mutation operator[J].IEEE Transactions on Evolutionary Computation,2009,13(3):526-553.
[8] Zhang J,Sanderson A C.JADE:Adaptive differential evolutionwithoptionalexternalarchive[J].IEEETransactions on Evolutionary Computation,2009,13(5):945-958.
[9] Zhang J,Sanderson A C.JADE:Self-adaptive differential evolutionwithfastandreliableconvergenceperformance[J].Soft Computing,2011,15(8):1581-1599.
[10] Wu Lianghong,Wang Yaonan,Yuan Xiaofang.Design of 2-D recursive filters using self-adaptive mutation differentialevolutionalgorithm[J].InternationalJournal of Computational Intelligence Systems,2012,4(4):644-654.
[11] Wang S W,Duan Y M,Shu W N,et al.Differential evolution with elite mutation strategy[J].Journal of Computational Information Systems,2013,9(3):855-862.
[12] 張錦華,宋來鎖,張元華,等.加權變異策略動態差分進化算法[J].計算機工程與應用,2017,53(4):156-162.
[13] 李冰,孫輝,趙嘉,等.異維學習人工蜂群算法[J].計算機應用研究,2016,33(4):1028-1033.
[14] Banharnsakun A,Achalakul T,Sirinaovakul B.The bestso-far selection in artificial bee colony algorithm[J].Applied Soft Computing,2011,11(2):2888-2901.
[15] Yao Xin,Liu Yong,Lin Guangming.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.
[16] Wang H,Wu Z,Liu Y,et al.Space transformation search:A newevolutionarytechnique[C]//Proceedingsofthe First ACM/SIGEVO Summit on Genetic and Evolutionary Computation,Shanghai,China,June 2009:537-544.
[17] 周新宇,吳志健,王暉.一種精英反向學習的差分演化算法[J].小型微型計算機系統,2013,34(9):1647-1652.
[18] Jong K A D.Analysis of the behavior of a class of genetic adaptive systems[D].University of Michigan,1975.
[19] Kennedy J.Particle swarm optimization[M]//Encyclopedia of Machine Learning.US:Springer,2010:760-766.
LIAO Xiongying,LI Jun,LUO Yangkun,et al.Differential evolution algorithm based on adaptive mutation operator.Computer Engineering andApplications,2018,54(6):128-134.
LIAO Xiongying1,2,LI Jun1,2,LUO Yangkun1,2,LI Bo1,2
1.College of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China
2.Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China
In order to solve the problem of differential evolution algorithm,such as premature convergence,slow convergence speed and low convergence precision,a differential evolution algorithm based on adaptive mutation operator is proposed.In this paper,the definition of individual vector particle and dimensional layer is presented.Based on the different dimension’s selection strategy for weighted dimensional layer,the weighted different dimensional learning is introduced into differential evolution algorithm for the first time,which can effectively improve the diversity of the population.According to the degree of populational aggregation,and an adaptive mutation operator based on degree of populational aggregation is proposed.The operator can adaptively adjust the variation weight of DE/best/1 mutation operator and the different dimensional learning mutation operator according to the degree of populational aggregation currently.It accelerates the convergence speed,improves the convergence precision of the algorithm.20 typical test functions are tested,the results show that compared with the 7 representative algorithms,the algorithm proposed in this paper has great advantages in solving accuracy and convergence speed,and it shows very good robustness.
differential evolution;dimensional layer;weighted different dimensional learning;degree of populational aggregation;adaptive mutation operator
針對差分演化算法易于早熟、收斂速度慢和收斂精度低等問題,提出一種基于自適應變異算子的差分進化算法。給出個體向量粒子及維度層定義,并提出了基于維度層加權的異維維度選擇策略,首次將加權異維學習策略引入差分演化算法中,有效地提高了種群的多樣性;根據種群聚集度的思想,提出一種基于種群聚集度自適應的變異算子,該算子能依據種群個體當前的種群聚集度自適應地調整DE/best/1變異算子和加權異維學習變異算子的變異權重,加快算法收斂速度、提高其收斂精度。通過在20個典型的測試函數上進行測試,與7種具有代表性的算法相比,結果表明提出的算法在求解精度和收斂速度上具有很大優勢,并顯示出了非常好的魯棒性。
差分進化;維度層;加權異維學習;種群聚集度;自適應變異
2017-09-04
2017-10-27
1002-8331(2018)06-0128-07
A
TP301.6
10.3778/j.issn.1002-8331.1709-0023
國家自然科學基金(No.61572381)。
廖雄鷹(1991—),男,碩士研究生,主要研究方向:智能計算;李俊(1978—),男,博士,副教授,主要研究方向:智能計算,E-mail:250581376@qq.com;羅陽坤(1992—),男,碩士研究生,主要研究方向:智能計算;李波(1975—),男,博士,教授,主要研究方向:智能計算、機器學習。