一種改進的Memetic差分進化算法

甘肅政法學(xué)院 趙進龍?zhí)m州理工大學(xué) 霍明明

?

一種改進的Memetic差分進化算法

甘肅政法學(xué)院 趙進龍
蘭州理工大學(xué) 霍明明

【摘要】提出一種改進的自適應(yīng)memetic差分進化算法，通過引入正態(tài)分布的概念，在種群初始化和局部搜索方面對經(jīng)典差分進化算法進行改進，提高其尋優(yōu)精度。并通過引入自適應(yīng)算子，在增強算法全局收斂性的同時又保證算法具有較高的收斂速度。實驗仿真結(jié)果表明，改算法具有較好的全局收斂性并能有效避免早熟收斂。

【關(guān)鍵詞】差分進化算法；Memetic算法；自適應(yīng)

1　引言

遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機優(yōu)化算法，因其原理簡單，魯棒性強，適于并行計算等優(yōu)點，自1975 年J.Holland［1］教授提出之日起，對遺傳算法的研究如火如荼。但是遺傳算法采用二進制編碼，這種編碼方式的最大缺點就是長度較大，對很多優(yōu)化問題來說用其他的編碼方式可能更有利。差分進化算法（Differential Evolution algorithm）是1995年Storn等人［2］為解決切比雪夫多項式問題時提出的。差分進化算法是基于群體智能理論的優(yōu)化算法，相比于遺傳算法，DE繼承了基于種群的全局搜索策略，采用浮點數(shù)編碼和基于差分的簡單變異操作以及貪婪的競爭生存策略，降低了算法的復(fù)雜度。DE獨有的記憶功能使其可以根據(jù)當(dāng)前搜索情況，動態(tài)調(diào)整搜索策略，具有較強的魯棒性和全局搜索能力。

全局搜索和局部開發(fā)能力的平衡是提高差分進化算法搜索性能的關(guān)鍵性問題，而這在較大程度上依賴于算法中控制參數(shù)（NP，F(xiàn)，CR）的選取。陳巖等［3］通過個體間距離、個體適應(yīng)度等指標(biāo)來增強種群的多樣性。2006年，Brest J等［4］提出了一種JDE算法，對F，CR進行自適應(yīng)調(diào)整。針對DE易過早收斂和陷入局部最優(yōu)甚至停滯的現(xiàn)象［5-6］，郭義波等［7］提出了隨機選擇變異策略、自適應(yīng)調(diào)整交叉率和自適應(yīng)調(diào)整變異率的設(shè)想，達到了局部搜索和全局搜索的平衡。譚躍等［8］提出了一種混沌局部搜索策略的差分進化算法（CLSDE），在最優(yōu)個體附近利用混沌算法進行局部搜索，使算法跳出局部最優(yōu)。

Memetic算法［9］繼承了遺傳算法全局搜索能力強的特點，同時Memetic中的局部搜索策略又彌補了遺傳算法局部搜索能力差的缺點，達到了全局搜索和局部搜索的平衡。本文一改標(biāo)準差分進化算法隨機初始化種群帶來的弊端，對種群初始化算法進行改進，并加入自適應(yīng)算子對種群進行動態(tài)調(diào)節(jié)，引入memetic算法達到全局搜索和局部搜索的平衡。

2　經(jīng)典差分進化算法

經(jīng)典差分進化算法的數(shù)學(xué)描述如下：

圖1　差分進化算法的流程圖

3　改進的差分進化算法

差分進化算法最優(yōu)解的質(zhì)量取決于初始群體是否能包含解空間內(nèi)的全部可能的解，并且保證在進化過程中不失去其中的優(yōu)良個體。由此可見初始種群既不能粗略的隨機產(chǎn)生，也不能遍歷所有狀況，尤其對于多變量問題，只要將解空間中最具有代表性的個體作為初始種群，才能更好的反映解空間的內(nèi)在特征。

標(biāo)準的差分進化算法采用隨機方法產(chǎn)生初始種群，這種方法在一定程度上影響了算法的尋優(yōu)能力和收斂速度，而利用服從正態(tài)分布的方法產(chǎn)生初始種群，且每次產(chǎn)生一個個體，這種方法在一定程度上增加了最優(yōu)解被選擇的可能性，提高了算法的尋優(yōu)能力。其公式如下：

其中，randn（1）產(chǎn)生服從N（0，1）的隨機數(shù)。

服從N（0，1）分布的種群個體分布圖如圖2所示：

圖2　服從正態(tài)分布的初始種群分布圖

3.2自適應(yīng)算子

縮放因子F在一定程度上控制了種群進化的方向，對算法的全局搜索和局部搜索能力起到了一定的程度的調(diào)節(jié)作用。F較小，有利于提高收斂速度和增強局部搜索能力，但種群多樣性較低，容易出現(xiàn)早熟和局部最優(yōu)；F較大，有利于算法的全局搜索和保持種群的多樣性，但局部搜索能力較低。高岳林等［10］認為F的值既不能太大，也不能小于某一特定值，建議之間時，算法能得到較好的結(jié)果。

Amin Nobakhti等［11］認為CR越大，試驗矢量每一維選擇變異矢量的概率越大，從而使試驗矢量相對于目標(biāo)矢量受到更大的擾動（perturbation），降低了算法的收斂速度；反之，小的CR將快速失去種群的多樣性（rapid loss of diversity）。

圖5(a)、5(b)和5(c)分別為旋流器內(nèi)x=0平面三條特征線Z-1、Z-2和Z-3上的切向速度分布圖。

綜上，本文提出了如下自適應(yīng)的縮放因子和交叉概率因子：

其中，G表示迭代次數(shù)，Gmax代表最大迭代次數(shù)。

3.3局部搜索策略

局部搜索是Memetic算法中一個最重要的環(huán)節(jié)，同時也是差分進化算法能否得到最優(yōu)解的決定因素之一。對于一個較好的算法，要能在算法的前期具有較強的全局搜索能力，使算法最終能收斂到解空間中的最優(yōu)解；算法后期具有較強的局部搜索能力，以提高算法的收斂速度和搜索精度。

局部搜索策略是一種近似算法，一般能給出一個可以接受的較好的解，但有可能陷入局部峰值，算法就在該點結(jié)束，此時得到的結(jié)果有可能就是一個較不理想的結(jié)果。本文采用在每次迭代結(jié)束后，以概率P從鄰域中隨機選擇一個個體，并在該個體附近進行k局部搜索，得到最優(yōu)解xbest，若xbest優(yōu)于xbest，則用xbest的值取代xbest的值，并xbest隨機取代種群中的一個個體，結(jié)束本次搜索，否則繼續(xù)DE的基本操作。局部搜索公式如下：

xbest=xrand+Normalrand（0，1） （5）

其中，Normalrand（0，1）服從期望為0，方差為1的標(biāo)準正態(tài)分布。

隨著迭代次數(shù)的增加，種群多樣性的降低是導(dǎo)致種群出現(xiàn)早熟的根本原因。為判斷種群是否出現(xiàn)停滯或達到最優(yōu)解，本文引入聚集度因子（aggregation degree factor）A。

4　數(shù)值試驗

為驗證本文提出的改進算法IMDE的有效性，選擇四個benchmarks函數(shù)中經(jīng)典的4個測試函數(shù)：Griewank、Schwefel、Rosenbrock、Rastrigin。測試函數(shù)的相關(guān)描述見表1。對于上述4個測試函數(shù)，文中選用DE / rand / 1 / bin進行尋優(yōu)測試，以比較DE和IMDE的性能。測試環(huán)境：matlab R2010b。

關(guān)于實驗參數(shù)設(shè)置，除f1函數(shù)的最大迭代次數(shù)為1000，種群規(guī)模為NP=60，f4的閾值為100外，其他函數(shù)參數(shù)設(shè)置為：局部搜索次數(shù)k=20，種群規(guī)模NP=100，最大迭代次數(shù)ITER=2000，閾值=0.15，選擇概率P=0.75。得到如表2所示結(jié)果。

表1　典型Benchmarks函數(shù)描述

表2　Benchmarks函數(shù)測試尋優(yōu)結(jié)果

從表2和圖3中可以看出，本文提出的IMDE算法對f1～f4的尋優(yōu)結(jié)果都優(yōu)于標(biāo)準DE算法，其中對于f1函數(shù)，本文提出的IMDE算法可以找到其全局最優(yōu)值（注：圖3中f1函數(shù)尋優(yōu)對比圖像中未出現(xiàn)紅線，說明在算法的第一次迭代中就找到了最優(yōu)解）。

圖3　f1～f4的尋優(yōu)對比曲線

從以上仿真對比結(jié)果可以看出，IMDE的尋優(yōu)能力要優(yōu)于標(biāo)準DE，證明本文提出的IMDE算法對求解優(yōu)化問題更有效。

5　結(jié)論

本文在分析了標(biāo)準差分進化算法存在的優(yōu)點和缺點的基礎(chǔ)上，提出了一種服從標(biāo)準正態(tài)分布的初始化方法，提高了算法尋優(yōu)效率和尋優(yōu)精度。利用Memetic算法強大的局部搜索能力，將Memetic算法和DE算法相結(jié)合，實現(xiàn)了IMDE算法全局搜索和局部搜索的平衡，并加入自適應(yīng)算子對種群進行自適應(yīng)調(diào)整，提高了算法的收斂速度。實驗表明，本文提出的IMDE算法對求解優(yōu)化問題的有效性。

參考文獻

［1］Holland J H.Adaption in natural and artificial systems［M］.The University of Michigan Press，975：1-50.

［2］Storn R，Price K.Differential evolution：a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of G local Optimization，1997，11（4）：341-359.

［3］陳巖，王宗憲.基于多準則尋優(yōu)策略的差分進化算法研究法［J］.山東科技大學(xué)學(xué)報（自然科學(xué)版），2016，35（1）：102-108.

［4］Brest J，Greiner S，Boskovic B，et al.S elf adapting control parameters in diff- erential evolution：a comparative study on numerical benchmark problems［J］.Journal of IEEE Trans Evolutionary Computation ，2006，10（6）：646-657.

［5］Holland J H.Adaptation in natural and artificial systems［M］.Ann Arbor：Michigan Press，1975：1-50.

［6］Yang Q W，Jiang J P，Qu Z X，et al.Improving genetic algorithms by using logic operation［J］.Control and Decision，2002，15（4）：520-512.

［7］郭義波，程際云，李芹，楊平.隨機選擇變異及自適應(yīng)差分進化算法的研究［J］.上海電力學(xué)院學(xué)報，2016，32（2）：162-174.

［8］譚躍，譚冠政.混沌局部搜索策略的差分進化算法［J］.重慶工學(xué)院學(xué)報，2009，23（5）：64-70.

［9］Peter Merz，Bernd Freisleben.Memetic Algorithms and the Fitness Landscape of the Graph Bi Partitioning Problem.PPSN VLNCS 1998：765-774.

［10］高岳林，劉軍民.差分進化算法的參數(shù)研究［J］.黑龍江大學(xué)自然科學(xué)學(xué)報，2009，26（1）：81-85.

［11］Amin Nobakhti，Hong Wang.A simple self-adaptive differential evolution algorithm with application on the ALSTOM gasifier［J］.Applied Soft Computing，2008，8：350-370.

作者簡介：

趙進龍（1985—），河北石家莊人，碩士，助教，主要研究方向：算法設(shè)計與分析。

霍明明（1986—），河南開封人，碩士，助教，主要研究方向：算法設(shè)計與分析。