混合多種群自適應(yīng)Memetic差分進(jìn)化算法

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

關(guān)鍵詞：差分進(jìn)化算法；Memetic算法；自適應(yīng)算子；鄰域搜索；多種群

1 概述

隨著信息技術(shù)的快速發(fā)展以及人們對(duì)生命本質(zhì)的不斷探索，越來(lái)越多的復(fù)雜優(yōu)化問(wèn)題得以解決。但對(duì)于具有多極值、非線性等特點(diǎn)的組合優(yōu)化問(wèn)題及復(fù)雜函數(shù)而言，經(jīng)典優(yōu)化算法往往顯得無(wú)能為力。

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

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

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

2 算法描述

2.1 經(jīng)典DE算法

DE算法主要應(yīng)用于求解連續(xù)變量的全局優(yōu)化問(wèn)題，其主要步驟與其他群智能優(yōu)化算法相似。算法的基本思想：隨機(jī)產(chǎn)生種群，種群個(gè)數(shù)NP，從種群中隨機(jī)選擇兩個(gè)個(gè)體經(jīng)過(guò)變異操作產(chǎn)生變異向量。變異向量與某個(gè)預(yù)先決定的目標(biāo)個(gè)體進(jìn)行交叉操作，產(chǎn)生實(shí)驗(yàn)個(gè)體。采用貪婪的選擇方式，并以適應(yīng)度值為參照，對(duì)個(gè)體進(jìn)行選擇操作，從而產(chǎn)生具有優(yōu)勢(shì)目標(biāo)個(gè)體的下一代種群。

2.2 自適應(yīng)算子

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

2.3 種群初始化

初始群體中是否能包含解空間內(nèi)的全部可能的解決定了DE算法求解最優(yōu)解的質(zhì)量。對(duì)于多變量問(wèn)題初始種群既不能粗略的隨機(jī)產(chǎn)生，也不能遍歷所有情況，如何將解空間中最具有代表性的種群個(gè)體作為初始種群，是種群初始化的關(guān)鍵。

基本的DE算法隨機(jī)產(chǎn)生初始種群，這在一定程度上對(duì)算法的收斂速度和尋優(yōu)能力起到了制約作用，而采用服從正態(tài)分布的方法創(chuàng)建初始種群，這種方法增加了最優(yōu)解被選擇的可能性，提高了算法的尋優(yōu)能力。其公式如下：

其中，randn（1）產(chǎn)生服從N（0，1）的隨機(jī)數(shù)。運(yùn)用公式（1）得到如下種群初始化圖像。

3 雙種群進(jìn)化策略

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

Step1：初始化兩個(gè)種群規(guī)模為NP的種群1和2。兩種群的最大進(jìn)化代數(shù)均為Gmax，雙方信息交流間隔代數(shù)為n。

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

Step3：統(tǒng)計(jì)種群1和2中每次進(jìn)化后的最優(yōu)值 和 ，

Step4：重復(fù)Step2～3，直至滿足進(jìn)化結(jié)束條件。

4 鄰域搜索策略

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

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

式中，A∈（0，1），f（G）表示第G代種群的平均適應(yīng)度值；f（xb（G））表示第G代的最佳適應(yīng)度值。A值在一定程度上代表著種群個(gè)體的聚集程度，A值越小個(gè)體的聚集程度越低，種群多樣性越高，越易避免早熟現(xiàn)象。當(dāng)種群中連續(xù)3代f（xb（G））不變，且A超過(guò)了預(yù)先設(shè)定的閾值T時(shí)，對(duì)種群重新初始化。

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

5 數(shù)值試驗(yàn)

5.1 典型Benchmarks測(cè)試函數(shù)

本實(shí)驗(yàn)選取三個(gè)典型的Benchmarks函數(shù)來(lái)驗(yàn)證改進(jìn)Memetic算法的有效性。測(cè)試環(huán)境：Dell Vostro 1088 matlab R2010b。

Benchmarks測(cè)試函數(shù)的數(shù)學(xué)模型如下：

實(shí)驗(yàn)參數(shù)設(shè)置為種群規(guī)模100，局部搜索次數(shù)20次，優(yōu)化次數(shù)20，最大迭代次數(shù)2000，交換次數(shù)10：.ADE算法中縮放因子為F=0.6得到如表1所示結(jié)果。

5.2 HMADE算法實(shí)驗(yàn)分析

從表1中可以看出，HMADE算法可以找到f3的全局最優(yōu)值。對(duì)于大部分測(cè)試函數(shù)，文章提出的HMADE算法優(yōu)于標(biāo)準(zhǔn)的DE算法和ADE算法。

為比較HMADE與DE、ADE的性能，對(duì)算法的尋優(yōu)結(jié)果進(jìn)行降序排列，并對(duì)結(jié)果取對(duì)數(shù)，進(jìn)行仿真實(shí)驗(yàn)得到如圖2-4所示的尋優(yōu)曲線。圖中，橫坐標(biāo)代表進(jìn)化代數(shù)，縱坐標(biāo)代表最優(yōu)值的對(duì)數(shù)，實(shí)線方塊、實(shí)線星號(hào)和虛線圓圈分別代表ADE、HMADE、DE的尋優(yōu)曲線。

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

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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ìn)人工蜂群算法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2012，33（8）：1022-1031.

[3]張雪霞，陳維榮，戴朝華.帶局部搜索的動(dòng)態(tài)多群體自適應(yīng)差分進(jìn)化算法及函數(shù)優(yōu)化[J].電子學(xué)報(bào)，2010，38（8）：1825-1830.

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

[5]任雪婷，賀興時(shí).一種改進(jìn)的粒子群與差分進(jìn)化混合算法[J].西安工程大學(xué)學(xué)報(bào)，2016，30（3）：380-387.

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

[7]何延年，李曉紅，蔣蕓.改進(jìn)多種群差分進(jìn)化算法的混沌系統(tǒng)參數(shù)估計(jì)[J].計(jì)算機(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.