一種基于多種群協作進化的自適應差分進化算法研究?

周 頔

（四川文理學院智能制造產業技術研究院 達州 635000）

1 引言

差分進化（Differential Evolution，DE）是1995年提出的一種啟發式隨機搜索的智能優化算法［1］。由于DE算法通過群體內個體之間的合作與競爭產生的群體智能指導優化搜索，其原理簡單，可對在連續空間內進行隨機、并行、有效的全局搜索，具有較強的魯棒性、穩健性以及強大的全局尋優能力，所以該算法越來越受到學術界和工程界的廣泛關注，在約束優化計算、信號處理、環境保護和運籌學以及NP問題等多個領域得到廣泛的應用。

然而由于DE算法是通個體之間的差分矢量進行變異、交叉和選擇來實現尋優，所以它存在著早熟收斂、易陷入局部最優和尋優效率不高等缺陷。近年來，許研究者針對這些存在的缺陷，提出了很多的改進 DE 算法［2～12］。Lee等［2］采用適應性步長局部搜索策略來確定DE 算法合適的縮放比例因子，目的是為了加速算法搜索。方強等［3］將單純形尋優操作引入DE 算法，以提高算法的搜索精度。張雪霞等［4］基于二次規劃法，提出一種改進的DE 算法。Brest 等［5］提出一種改進的 DE 算法，以自適應調節算法的參數縮放因子和交叉概率。吳亮紅等［6］提出一種基于雙種群結構的偽并行DE 算法，以提高DE算法的收斂速率和全局搜索能力。Gong等［7］利用正交設計法來改進DE 算法的收斂速度，提高其綜合尋優性能。Ali等［8］將懲罰函數加入DE算法，用于較好地求解約束條件問題。賈東立等［9］將混沌變異和高斯變異用作局部搜索策略，基于混沌理論和高斯局部優化方法，提出一種新的混合DE算法。葛延峰等［10］通過改進個體差異信息和適度值取值范圍，提出一種改進自適應DE 算法。曲福恒等［11］利用并行多個策略與參數組合來提高個體多樣性，提出了一種改進的差分進化算法。陳華等［12］提出一種可自動調節縮放因子和交叉概率因子的自適應DE算法。

這些改進的DE 算法能夠較好地服了DE 算法的陷入局部最優和早熟收斂性問題，但算法的局部搜索能力、收斂速度和尋優精度還有待進一步加強。本文為了充分利用局部搜索策略，協同進化機制以及多種群進化等優點，提出一種改進的多種群協作自適應差分進化（MSDPIDE）算法，通過函數優化驗證MSDPIDE算法的有效性。

2 基本差分進化算法

DE 算法采用了遺傳算法的基本框架，同時借鑒了Nelder-Mead 單純形方法，設計了獨特的差分變異算子［5］。DE 算法包括變異操作、交叉操作和選擇操作［13～14］。

2.1 初始化

其中xjmin和xjmax分別表示種群中個體的下界和上界。rand 是［0，1］區間上的均勻隨機數發生器。

2.2 變異操作

變異操作是DE 算法與遺傳算法的不同之處。在DE算法中，主要是對父代的差分矢量進行變異，不同的兩個個體（）構成矢量對。不同的DE算法方法如下:

1）DE/rand/1/bin

2）DE/rand/2/bin

3）DE/best/1/bin

4）DE/rand/2/bin

5）DE/current-to-best/1

2.3 交叉操作

均勻交叉變異產生的個體xk和種群中的第i個個體，用來補償上一步的變異搜索，進而產生試驗向量xG。本文采用二項式交叉方法。具體交叉操作的方程為

其中，jrand?{1,2,…,D}是一個隨機整數，用來保證目標個體至少有一個分量進行了交叉操作。交叉概率CR ∈［0，1］。

2.4 選擇操作

DE算法選擇個體xG和適應度更好的個體，作為子代個體。選擇的的標準如下:

3 多種群協作自適應差分進化（MSDPIDE）算法

3.1 局部搜索策略

為了提高DE 算法個體產生策略的多樣性，避免DE 算法早熟收斂問題，本文采用局部搜索策略來調整自適應DE 算法搜索。假設當前DE 算法種群規模為 NP ，最優解為。隨機選擇個體x=(x1,x2,…,xD)，采用下列等式對最優解xtgbest 進行局部搜索，產生新的個體。

其中，j=1,2,3…,D ，U(-1,1)表示-1～1 之間均勻分布的隨機數。

3.2 多種群協作進化

將種群個體分成N 個子群體，用于代替單一種群在可行解空間中進行搜索，促進個體間的交換信息。在算法迭代中，為了增加算法的搜索速度，降低算法的復雜度，首先基于不同策略，協同進化各個子種群，然后按子種群中個體適應度值排序，獲得每個子種群的最優個體，更新每個子群體的最差個體，并評價適應度值。接著重新合并N個子種群為一個種群，再隨機分為N 個子群體，再得每個子種群的最優個體。并進行最優個體的比較，把優秀個體保留下來，實現不同群體間動態交換信息。這樣能促進各個種群并行進化，保持優秀個體進化的穩定性，避免過早收斂現象。

3.3 MSDPIDE算法思想與描述

由于自適應DE算法存在不能及時更新進化策略，所以基于局部搜索策略，改進自適應DE 算法。針對求解問題，動態產生獨立進化的子種群，增強子種群個體間的信息交換，保持種群的多樣性；通過利用群體之間的對等的相互移民策略均衡全局探索能力和收斂速度之間的矛盾，使得算法在合理的計算復雜度下具有較高的全局收斂率。

MSDPIDE算法的具體步驟如下:

第一步:初始化算法各參數:這些參數包括種群大小N 、迭代次數Tmax、交叉概率CR、縮放因子F 、自變量的下界和上界、初始衰減率α 以及初始增長率 β 等。

第二步:隨機生成初始種群，t=1。

第三步:評價每個個體得適應度值，找出最優個體。

第四步:判斷最優解是否滿足要求。若是輸出最優解；否則，執行第五步。

第五步:按照式（2）～（6），進行變異操作。

第六步:按照式（7），進行交叉操作。

第七步:按照式（8），對進行選擇操作。

第八步:對最優個體根據式（9），進行局部搜索。

第九步:新的種群生成后，令t =t +1，轉第三步繼續進行。

4 數值實驗研究

4.1 測試函數

為了驗證MSDPIDE 算法在高維復雜優化函數中的性能，Benchmarks 函數被選作對算法進行測試。本文選用的9 個經典測試函數和變量范圍，如表1 所示，其全局最優值均為0。同時MSDPIDE 算法與DE 算法和CADE算法［16］進行比較。

表1 Benchmarks測試函數集

4.2 運行環境與參數設置

實驗開發環境如下:Matlab 2012a，運行于I5 CPU 2.20GHz，4.0GB 內存臺式電腦。實驗參數設置如下:種群規模NP=100，函數維數為1000，群個數n=3，縮放因子 F =0.60，交叉概率CR=0.80，最大進化代數為Tmax=500，每個算法獨立運行20次。

4.3 實驗結果與分析

DE 算法、CADE 算法和 MSDPIDE 算法運行 20次的求解Benchmarks 測試函數，測試結果的最大最優值、最小最優值和平均最優值，如表2所示。

表2 連續20次的運行結果

從表2 中可以看出，根據MSDPIDE 算法和DE算法求解這9 個函數的結果，除DE 算法求解 f9函數獲得較好的結果外，MSDPIDE 求解 f1、f2、f3、f4、f5、f6、f7、f8函數均比DE 算法的求解效果好。MSDPIDE 算法與 ACDE 比較，ACDE 算法能夠較好地求解 f3和 f5函數，MSDPIDE 能夠較好地求解 f1、f2、f4、f6、f7、f8和 f9函數，且性能比ACDE算法好。綜上可知，本文提出的MSDPIDE算法在1000 維的高維復雜基準函數測試中表現得更為穩定，求解精度更高，能夠解決高維多極函數的復雜優化問題。

5 結語

針對實際工程應用中的高維復雜函數優化問題，提出了利用局部搜索策略提高個體多樣性，成功地避免了算法的早熟收斂，提高了全局尋優能力，保證個體之間能夠進行充分高效的信息交換。利用自適應調節機制，以平衡局部搜索與全局搜索。通過對9個典型benchmark函數進行測試結果表明，該MSDPIDE 算法比DE 和CADE 算法總體性能優。MSDPIDE 算法尋優能力強，搜索精度高，穩定性好，更適于處理高維函數優化問題。