混合多種群自適應Memetic差分進化算法

摘 要：基本差分進化算法（Differential Evolution，DE）是一種實用性強、簡單高效的群智能優化算法，但DE算法同樣可能存在著其他群智能優化算法共同存在的缺點，如早熟收斂、易陷入局部最優解等。針對以上問題，文章提出一種Memetic算法，通過改進種群初始化方法和引入鄰域搜索算子來增強種群的多樣性，通過多種群間的信息交互，保證算法有效跳出局部極值點。通過引入自適應算子，對交叉概率因子和縮放因子進行自適應調整，保證算法具有較高的收斂速度。仿真實驗結果表明，HMADE算法可解決標準差分進化算法后期收斂停滯的問題。

關鍵詞：差分進化算法；Memetic算法；自適應算子；鄰域搜索；多種群

1 概述

隨著信息技術的快速發展以及人們對生命本質的不斷探索，越來越多的復雜優化問題得以解決。但對于具有多極值、非線性等特點的組合優化問題及復雜函數而言，經典優化算法往往顯得無能為力。

1995年，美國學者R.Storn和K.Price提出了一種基于群體差異的群智能算法——差分進化算法[1]。DE算法模擬生物學中隨機進化模型，通過種群初始化，交叉、變異、選擇等使優勢個體得以保留和遺傳下去。DE算法是一種具有全局搜索的群智能優化算法，編解碼簡單，易建模，具有較強的魯棒性和全局搜索能力。

目前DE算法是計算智能領域的一個研究熱點，畢曉君等[2]將具有穩定傾向性的云模型運用到改善DE算法易早熟和陷入局部極值的缺點。云模型對DE算法受控參數的自適應調節，提高了約束多目標算法的收斂速度。通過對外部種群不可行解和可行解建立不同的存儲，有效提高了可行解的分布性。新的變異策略的提出有效提高了算法的全局探索能力。張雪霞等[3]將種群中個體動態隨機的分成多個子群體，通過采用自適應機制對縮放因子F和交叉概率因子CR的調整，實現全局搜索和局部搜索的平衡。實驗表明改進算法具有較高的收斂速度和求解精度。何大闊等[4]將DE算法較強的全局開發能力與多智能體的優點有機結合，并引入差分算子提高智能體的更新速度，從而保證了種群具有較高的種群多樣性。實驗表明改進算法不僅具有較強的全局開發能力，同時具有較高的尋優精度。任雪婷等[5]提出了一種改進的自適應混沌粒子群算法與自適應差分進化算法的混合算法，并通過與基本的粒子群算法和DE算法對比，驗證了新算法的有效性。符純明等人[6]提出了一種基于隔代映射算子的差分進化算法以求解優化問題，并通過對11個單峰、多峰測試函數和兩個工程實例進行實驗，驗證了改進算法的有效性。何延年等[7]人利用α核心集對種群進行聚類，并選用貪婪的差分變異算子進行深度搜索，通過對多峰值、大空間的全局性參數的實驗中，其收斂速度和精度由于混合量子進化算法、改進粒子群優化算法和DE/best/2算法。

Memetic Algorithm（MA）[8]是即文化基因算法，它是模擬文化進化過程的優化算法。Memetic算法是一種基于個體的局部搜索和基于種群的全局搜索的結合體。它因此被稱為混合遺傳算法或拉馬克式算法。Memetic算法提出的僅僅是一種框架、是一個概念，這種框架下，局部搜索可以是貪婪算法、模擬退火、爬山搜索等，全局搜索可以是進化規劃、遺傳算法等。

2 算法描述

2.1 經典DE算法

DE算法主要應用于求解連續變量的全局優化問題，其主要步驟與其他群智能優化算法相似。算法的基本思想：隨機產生種群，種群個數NP，從種群中隨機選擇兩個個體經過變異操作產生變異向量。變異向量與某個預先決定的目標個體進行交叉操作，產生實驗個體。采用貪婪的選擇方式，并以適應度值為參照，對個體進行選擇操作，從而產生具有優勢目標個體的下一代種群。

2.2 自適應算子

變異算子F用來對差分向量進行縮放，產生變異向量。較小的變異算子F有利于對解空間的探索，但往往多樣性較差，易出現早熟現象；較大的變異算子F有利于維持種群多樣性，便于搜索解空間中的最優解。交叉概率因子CR決定了變異向量在試驗向量中所占的比重，這往往會影響算法時收斂速度。較大的CR有利于算法的收斂，但易出現早熟和局部極值的現象。較小的CR增大了變異向量被選擇的概率，從而增加種群多樣性，但易出現算法停滯，大大降低了算法的收斂速度。文章提出的自適應算子如下：

2.3 種群初始化

初始群體中是否能包含解空間內的全部可能的解決定了DE算法求解最優解的質量。對于多變量問題初始種群既不能粗略的隨機產生，也不能遍歷所有情況，如何將解空間中最具有代表性的種群個體作為初始種群，是種群初始化的關鍵。

基本的DE算法隨機產生初始種群，這在一定程度上對算法的收斂速度和尋優能力起到了制約作用，而采用服從正態分布的方法創建初始種群，這種方法增加了最優解被選擇的可能性，提高了算法的尋優能力。其公式如下：

其中，randn（1）產生服從N（0，1）的隨機數。運用公式（1）得到如下種群初始化圖像。

3 雙種群進化策略

DE/current-to-best/2/bin的變異策略使得變異向量能夠具有較大概率的進入下一代，有利于算法的收斂，從而提高收斂速度。DE/rand/1/bin種群多樣性較好，有利搜索到最優解。Qin等[9]提出了SaDE算法，每個個體根據進化過程中的學習經驗在每次迭代中自適應選擇DE/rand/1/bin和DE/current-to-best/2/bin中的一種變異策略，并根據該策略在上一代中的成功概率來確定本策略的選擇概率。文章采用的雙種群進化策略流程如下：

Step1：初始化兩個種群規模為NP的種群1和2。兩種群的最大進化代數均為Gmax，雙方信息交流間隔代數為n。

Step2：種群1固定縮放因子F進化，種群2按照固定的交叉概率因子進化。

Step3：統計種群1和2中每次進化后的最優值 和 ，

Step4：重復Step2～3，直至滿足進化結束條件。

4 鄰域搜索策略

為了提高算法的局部開發能力，文中采用具有柯西分布的鄰域搜索策略。即在每一次迭代結束后采用具有柯西分布的鄰域搜索策略進行局部搜索，搜索k次，并從中取最優解取代種群中的隨機一個個體，直至找到最優解。

由于在每一代個體進化后采用局部搜索操作，使得算法的收斂速度過快，有可能會陷入局部極值，隨著迭代次數的增加，種群多樣性的降低是導致種群出現早熟的根本原因。為判斷種群是否出現停滯或達到最優解，文章引入聚集度因子A。

式中，A∈（0，1），f（G）表示第G代種群的平均適應度值；f（xb（G））表示第G代的最佳適應度值。A值在一定程度上代表著種群個體的聚集程度，A值越小個體的聚集程度越低，種群多樣性越高，越易避免早熟現象。當種群中連續3代f（xb（G））不變，且A超過了預先設定的閾值T時，對種群重新初始化。

在文章中加入了如下鄰域搜索：

5 數值試驗

5.1 典型Benchmarks測試函數

本實驗選取三個典型的Benchmarks函數來驗證改進Memetic算法的有效性。測試環境：Dell Vostro 1088 matlab R2010b。

Benchmarks測試函數的數學模型如下：

實驗參數設置為種群規模100，局部搜索次數20次，優化次數20，最大迭代次數2000，交換次數10：.ADE算法中縮放因子為F=0.6得到如表1所示結果。

5.2 HMADE算法實驗分析

從表1中可以看出，HMADE算法可以找到f3的全局最優值。對于大部分測試函數，文章提出的HMADE算法優于標準的DE算法和ADE算法。

為比較HMADE與DE、ADE的性能，對算法的尋優結果進行降序排列，并對結果取對數，進行仿真實驗得到如圖2-4所示的尋優曲線。圖中，橫坐標代表進化代數，縱坐標代表最優值的對數，實線方塊、實線星號和虛線圓圈分別代表ADE、HMADE、DE的尋優曲線。

從以上仿真結果分析可以看出，HMADE算法具有較好的尋優能力和收斂速度。

6 結束語

文章以帶有自適應算子的差分進化算法進行全局搜索，以帶有柯西分布的鄰域搜索進行局部搜索，新的種群初始化方法和多種群信息交互算法，增加了種群多樣性，同時Memetic中鄰域搜索策略的引入，增強了算法跳出局部最優解的能力。通過與DE算法和ADE算法進行實驗比較，文章提出的HMADE算法具有較強的尋優能力和較快的收斂速度。

參考文獻

[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]畢曉君，王艷較.改進人工蜂群算法[J].哈爾濱工程大學學報，2012，33（8）：1022-1031.

[3]張雪霞，陳維榮，戴朝華.帶局部搜索的動態多群體自適應差分進化算法及函數優化[J].電子學報，2010，38（8）：1825-1830.

[4]何大闊，高廣宇，王福利，等.多智能體差分進化算法[J].控制與決策，2011，26（7）：961-966.

[5]任雪婷，賀興時.一種改進的粒子群與差分進化混合算法[J].西安工程大學學報，2016，30（3）：380-387.

[6]符純明，姜潮，陳光宋，等.基于隔代映射算子的差分進化算法[J].中國機械工程，2016：1523-1545.

[7]何延年，李曉紅，蔣蕓.改進多種群差分進化算法的混沌系統參數估計[J].計算機工程，2015，41（2）：178-188.

[8]Moscato P. On evolution， search， optimization， genetic algorithms and martial arts： toward mimetic algorithms. Tech. Rep. Caltech Concurrent Computation Program， Rep. 826， Pasadena， CA： California Inst. Technol， 1989.

[9]A.K.Qin and P.N. Suganthan. Self-adaptive differential evolution algorithm for numerical optimization [A].In： IEEE Congress on Evolutionary Computation （CEC 2005）[C].Edinburgh， Scotland，Sep 02-05，2005.