一種加入局部搜索的雙子代差異演化算法

武志峰，劉爍，李耀輝

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津300222）

一種加入局部搜索的雙子代差異演化算法

武志峰，劉爍，李耀輝

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津300222）

針對差異演化算法存在收斂速度慢的問題，提出一種加入局部搜索算子的雙子代競爭差異演化算法。為了增加群體多樣性，對初始種群采用等間隔均勻分布。算法對每一代演化種群中的最優(yōu)個體以一定概率加入局部隨機(jī)擾動，在其附近搜索更優(yōu)秀的新個體，以加快發(fā)現(xiàn)最優(yōu)解的速度。在7個常用測試函數(shù)上的實(shí)驗結(jié)果表明：無論是在最優(yōu)解質(zhì)量、收斂速度，還是在平均評價次數(shù)等方面，本文算法都優(yōu)于文獻(xiàn)［5］的算法。

差異演化；局部搜索；全局優(yōu)化

1995年，Storn和Price［1］提出了一種新型的演化算法—差異演化（differential evolution，DE）算法。該算法的基本思想是利用種群中個體的差異進(jìn)行演化。與遺傳算法類似，該算法也是通過對種群的交叉、變異、選擇等操作生成下一代種群。與遺傳算法不同的是，差異演化算法的變異操作是基于群體差異性來修正各個體的值，即利用群體中個體的“差異”作為向最優(yōu)解搜索的主要動力源。對群體中的每個個體算法隨機(jī)選擇幾個不同的個體，并由它們的“差異”生成試驗向量，然后再以一定的交叉概率與該個體離散交叉生成新個體，最后通過“貪婪式”的選擇方法，保留原個體和新生成個體中的優(yōu)秀者。在首屆IEEE演化計算大賽中，差異演化算法是所有參賽算法中進(jìn)化速度最快的不確定搜索方法，表現(xiàn)出卓越的性能，隨后在各領(lǐng)域得到廣泛的應(yīng)用［2］。

雖然差異演化算法對于非凸、多峰等非線性的函數(shù)優(yōu)化問題具有不錯的性能，但基本差異演化算法對一些復(fù)雜的大規(guī)模優(yōu)化問題，其前期收斂速度較慢，后期由于種群趨于同化，算法易陷入局部最優(yōu)解，使算法的穩(wěn)定性、求解精度等不盡人意。目前，學(xué)界已提出許多方法來改進(jìn)差異演化算法的性能。文獻(xiàn)［3］利用個體向量的鄰域概念把變異算子分為鄰域內(nèi)的局部變異和群體內(nèi)的全局變異，以改進(jìn)算法的性能。文獻(xiàn)［4］提出一種雙種群差分進(jìn)化規(guī)劃算法。該算法將種群劃分為2個子群獨(dú)立進(jìn)化，分別采用DE/rand/1/bin和DE/best/2/bin版本生成變異個體。之后將2個子群合并為一個種群，再應(yīng)用混沌重組算子將之重新劃分，以實(shí)現(xiàn)子群間的信息交流。同時用非均勻變異算子對其最優(yōu)個體執(zhí)行進(jìn)化規(guī)劃操作，使算法具有較快的收斂速度和較強(qiáng)的全局尋優(yōu)能力。文獻(xiàn)［5］提出一種帶慣性變異與正交設(shè)計的差分進(jìn)化改進(jìn)算法。該算法利用正交設(shè)計方法在群體中最優(yōu)個體的局部鄰域內(nèi)進(jìn)行搜索，以提高最優(yōu)解的搜索速度。文獻(xiàn)［6］提出一種基于分工的差分進(jìn)化算法。在進(jìn)化過程中對個體進(jìn)行分工，優(yōu)秀個體選擇best/1策略承擔(dān)開發(fā)任務(wù)，一般或較差個體選擇rand/1變異策略承擔(dān)探索任務(wù)，通過個體分工負(fù)責(zé)提高算法性能。文獻(xiàn)［7］提出一種基于Boltzmann機(jī)制的雙子代競爭差異演化算法。與以往算法不同，該算法的交叉操作可以生成2個新個體，然后2個個體與父代個體一起競爭形成子代個體。同時引入Boltzmann機(jī)制，使算法可以跳出局部最優(yōu)解，從而找到全局最優(yōu)。文獻(xiàn)［8］提出了一種基于動態(tài)局部搜索的差分進(jìn)化算法，增加種群的多樣性，平衡算法的開發(fā)能力和探索能力。文獻(xiàn)［9］提出一種隨機(jī)變異差異演化算法，改進(jìn)了差異演化算法的變異操作。

本文在文獻(xiàn)［7］的基礎(chǔ)上，采用rand/1變異策略，在交叉生成雙子代競爭個體的同時，對每一代中的最優(yōu)個體加入局部搜索方法，承擔(dān)開發(fā)任務(wù)，加快最優(yōu)解搜索。同時，為保證種群的多樣性，在種群初始化時實(shí)行均勻分布，即在自變量的可行域內(nèi)按照種群規(guī)模均勻設(shè)置每個個體。在7個常用基準(zhǔn)測試函數(shù)上的實(shí)驗結(jié)果表明，該算法在最優(yōu)解質(zhì)量和收斂速度上都具有很好的效果。

1　差異演化算法

差異演化算法是一種類似遺傳算法的以實(shí)數(shù)編碼的演化算法。與遺傳算法的主要區(qū)別是其變異操作基于個體的差異向量進(jìn)行。差異演化算法實(shí)質(zhì)上是一種自適應(yīng)的迭代尋優(yōu)隨機(jī)搜索算法。其基本思想是從初始種群開始，把任意2個個體的向量差加權(quán)后與第3個個體求和形成變異個體，再將變異個體與當(dāng)前種群中的某一指定個體進(jìn)行交叉操作生成試驗個體，然后在指定個體和試驗個體之間選擇適應(yīng)值較優(yōu)的個體作為新一代的個體。通過不斷地迭代，算法使種群中優(yōu)良個體得以保留，劣質(zhì)個體逐漸淘汰，從而引導(dǎo)搜索過程向最優(yōu)解逼近。

令xi（t）是第t代的第i個染色體，則xi（t）=（xi1（t），xi2（t），…，xin（t））（i=1，2，…，M；t=1，2，…，tmax）。其中：n為染色體的長度，即變量的個數(shù)；M為種群規(guī)模；tmax為最大的進(jìn)化代數(shù)。

基本差異演化算法框架描述如下：

步驟1設(shè)置算法相關(guān)參數(shù)。參數(shù)包括種群規(guī)模M，縮放因子F和交叉因子CR等。

步驟2生成初始種群。隨機(jī)生成滿足約束條件的M個個體構(gòu)成初始種群。

步驟3變異操作。從種群中隨機(jī)選擇3個個體xp1、xp2、xp3且i≠p1≠p2≠p3，則

步驟4交叉操作。把變異操作生成的個體與指定目標(biāo)個體做如下交叉操作：

式中：rand1ij為隨機(jī)數(shù)，rand1ij∈［0，1］；CR為交叉概率，CR∈［0，1］；rand（i）為在［1，n］之間的隨機(jī)整數(shù)。這種交叉策略可確保vi（t+1）中至少有一個分量由hi（t）的相應(yīng)分量貢獻(xiàn)。

步驟5選擇操作。對新個體vi（t+1）和目標(biāo)個體xi（t）進(jìn)行評價，擇優(yōu)生成下一代個體：

步驟6反復(fù)執(zhí)行步驟3至步驟5操作，直至達(dá)到最大進(jìn)化代數(shù)。

2　加入局部搜索的雙子代差異演化算法

2.1算法基本思想

由式（1）可知，在rand/1變異策略中，新的變異個體由3個完全不同的隨機(jī)個體組成，因而有利于保持種群的多樣性。這使算法的全局搜索能力較強(qiáng)，但同時也會導(dǎo)致算法收斂速度慢、精度低、搜索效率低下。此外，傳統(tǒng)的差異演化算法在生成初始種群時多使用隨機(jī)初始化的方法，從而導(dǎo)致初始種群在問題的解空間中不能均勻分布，進(jìn)而影響到種群對問題解空間的全面搜索。文獻(xiàn)［7］通過改進(jìn)交叉和選擇操作，提出一種基于Boltzmann生存機(jī)制的雙子代競爭差異演化算法，增加了群體的多樣性，從而使算法性能得到提高。但這種算法忽略了對種群中每個個體局部鄰域的搜索，同樣存在算法的收斂速度慢等問題，特別是在當(dāng)前最好解非常接近最優(yōu)解的時候，可能需要多次操作才能找到真正的最優(yōu)解。而局部搜索算法是一種簡單有效的尋找最優(yōu)解的方法，可以在當(dāng)前解的周圍快速找到更好的解。本文提出一種加入局部搜索策略的改進(jìn)算法，首先對種群在解空間內(nèi)進(jìn)行均勻初始化，保證種群在解空間中均勻分布；然后利用雙子代策略生成新一代種群，并對其中的最優(yōu)個體加入一定的局部搜索策略，在其周圍進(jìn)行局部開發(fā)，以期搜索到更好的解，從而使算法盡快收斂；同時為避免陷入局部極小值，算法并不是對每一代種群中的最優(yōu)個體都進(jìn)行局部搜索，而是以一定的概率，對其執(zhí)行局部搜索算子，且隨著演化代數(shù)的增加，其執(zhí)行局部搜索算子的概率也不斷加強(qiáng)。

2.2均勻初始化種群

為保證初始種群在問題解空間的均勻分布，算法沒有采用隨機(jī)生成初始種群的方法，而是根據(jù)種群規(guī)模把自變量的取值范圍均勻分為若干段，然后在每一段區(qū)間上隨機(jī)生成一個個體，從而保證了初始種群中每個個體在求解空間上分布的均勻性。例如，自變量X的取值范圍為［a，b］，算法種群規(guī)模為popsize，則均勻初始化種群可描述如下：

輸入：種群規(guī)模popsize，自變量下界a，自變量上界b；

輸出：均勻初始化的種群population；

Function initPop（popsize，a，b）

｛

interval=（b-a）/popsize；

for（i=0；i＜popsize；i++）

｛

ai=a+i×interval；

bi=ai+interval；

for（j=0；j＜col；j++）|

population［i］［j］=random（）×（bi-ai）+ai；

｝

｝

2.3局部搜索算子

在經(jīng)典的差異演化算法中，rand/1的變異策略使差異演化算法具有較強(qiáng)的全局搜索能力，但同時也會導(dǎo)致算法收斂速度變慢。特別是當(dāng)問題的全局最優(yōu)解就在當(dāng)前最優(yōu)解附近時，算法卻可能還需要搜索多次才能得到全局最優(yōu)解。為加快算法的收斂速度，本文算法對每一代種群中的最優(yōu)個體以一定概率加入隨機(jī)擾動的局部搜索算子，以便使其在當(dāng)前最優(yōu)個體附近快速尋找更好的個體。若發(fā)現(xiàn)更優(yōu)的新個體，則再次對新個體進(jìn)行局部搜索，直到新個體停止改進(jìn)或概率條件不滿足為止。之所以不采用確定性的加入，主要是為了保證種群的多樣性，從而避免算法陷入局部最優(yōu)。局部搜索算子公式定義如下：

式中：xbestj（t）表示第t代最優(yōu)個體Xbest（t）的第j個分量；σ為局部搜索算子的一個參數(shù)，它決定了對最優(yōu)個體Xbest（t）加入的局部隨機(jī)擾動的大小，即決定了Xbest（t）后代的變化范圍?？梢妳?shù)σ對算法收斂有重要的作用。

自然界在演化過程中，通常都遵循這樣的演化規(guī)律，隨著演化代數(shù)的增加，種群會逐漸向最優(yōu)解靠近，即最優(yōu)解的發(fā)現(xiàn)是一個連續(xù)漸變的過程，很少會以突變的形式得到最優(yōu)解。因此，在本文提出的算法中，隨著演化代數(shù)的增加，局部搜索算子也以一種連續(xù)漸變的方式逐步縮減其隨機(jī)擾動的幅度，即參數(shù)σ逐步縮小，從而實(shí)現(xiàn)算法的穩(wěn)定收斂。

在種群均勻初始化過程中，每個個體都被均勻分布在自變量的一個區(qū)段內(nèi)。在添加局部擾動時，設(shè)定對其擾動的范圍不能超過這一區(qū)段的1/2，即σ≤interval/2，其中interval是種群中個體間的間隔距離。在算法演化過程中，對每一代種群都要根據(jù)當(dāng)前種群中自變量的分布情況重新計算個體間的間隔。隨著演化的進(jìn)行，種群會逐漸向最優(yōu)解靠攏，種群內(nèi)個體間的間隔距離也會逐漸縮小，因此也就保證了局部搜索算子以連續(xù)漸變的方式逐漸縮減擾動幅度。

2.4算法描述

步驟1初始化算法參數(shù)。設(shè)置種群規(guī)模M，縮放因子F，交叉因子CR，最大進(jìn)化代數(shù)T，執(zhí)行局部搜索算子的概率P1等相關(guān)參數(shù)。

步驟2初始化種群。按2.2節(jié)中的方法對種群進(jìn)行初始化，得到在自變量取值范圍內(nèi)均勻分布的初始種群，設(shè)置初始進(jìn)化代數(shù)t=0。

步驟3變異操作。采用經(jīng)典DE算法的rand/1變異策略對種群實(shí)行變異。

步驟4交叉、選擇操作。采用文獻(xiàn)［7］中的方法對種群進(jìn)行交叉生成2個子代個體，然后再選擇一個個體進(jìn)入下一代種群。

步驟5設(shè)置擾動參數(shù)。重新計算當(dāng)前種群中的個體間隔，以設(shè)置擾動參數(shù)σ。

步驟6局部搜索。對當(dāng)前種群中的最優(yōu)個體以概率P1執(zhí)行局部搜索，直到新個體不再改進(jìn)為止。

步驟7終止條件檢驗。若進(jìn)化代數(shù)t已達(dá)最大迭代次數(shù)T或達(dá)到預(yù)設(shè)精度，則輸出最優(yōu)個體xbest（t）的結(jié)果f（xbest（t））并停止；否則，置t=t+1，轉(zhuǎn)步驟3。

3　實(shí)驗測試及結(jié)果分析

為驗證本文算法的性能，將其與文獻(xiàn)［5］中的算法進(jìn)行對比測試。測試函數(shù)取文獻(xiàn)［5］中給出的7個常用測試函數(shù)。其中，n為函數(shù)自變量的維數(shù)，n=30；S為自變量的取值范圍，其中f1（x）～f3（x）以及f5（x）的取值范圍為［-100，100］；f4（x）的取值范圍為［-600，600］，f6（x）和f7（x）的取值范圍為［-50，50］。

這些函數(shù)中，f1為單峰函數(shù)；f2為Rosenbrock函數(shù)，是一個非凸、病態(tài)單峰函數(shù)；其他函數(shù)為多峰函數(shù)；f2和f7在（1，1，…，1）處取最小值0，f6在（－1，－1，…，－1）處取最小值0，其他函數(shù)均在（0，0，…，0）處取最小值0。

為使結(jié)果具有可比性，所有測試函數(shù)取值范圍、維數(shù)均與相應(yīng)文獻(xiàn)中取值相同。本文算法中交叉因子CR取0.9，縮放因子F取0.5，局部搜索概率P1動態(tài)取值并隨演化代數(shù)逐漸增加。本文算法與文獻(xiàn)［5］算法在7個測試函數(shù)上的對比實(shí)驗結(jié)果如表1所示。

由表1可知，在函數(shù)f2、f3和f4上，本文算法和文獻(xiàn)［5］算法一樣每次都能找到全局最優(yōu)解，算法表現(xiàn)十

表1　30維函數(shù)獨(dú)立優(yōu)化50次的實(shí)驗結(jié)果

分穩(wěn)定。除在f3上平均評價次數(shù)稍大些外，本文算法在f2和f4上的平均評價次數(shù)都遠(yuǎn)小于文獻(xiàn)［5］中的算法，說明本文算法具有很好的收斂性能。對于函數(shù)f1，本文算法的求解精度也遠(yuǎn)高于文獻(xiàn)［5］，且最優(yōu)解的方差達(dá)到10-97，說明算法相當(dāng)穩(wěn)定；算法平均評價次數(shù)相對較小，也說明算法收斂較快。對于函數(shù)f5，本文算法雖然未能找到全局最優(yōu)解，但從平均最優(yōu)解質(zhì)量來看仍然優(yōu)于文獻(xiàn)［5］，平均評價次數(shù)也略少于文獻(xiàn)［5］。對于函數(shù)f6和f7，2種算法都未能找到全局最優(yōu)解，但在得到相同最優(yōu)結(jié)果的情況下，本文算法的平均評價次數(shù)遠(yuǎn)少于文獻(xiàn)［5］的算法。綜合來看，本文算法在測試函數(shù)上的表現(xiàn)要優(yōu)于文獻(xiàn)［5］，特別是在平均評價次數(shù)即收斂速度上是令人滿意的。

4　結(jié)束語

本文算法在雙子代競爭差異演化算法的基礎(chǔ)上加入了局部搜索算子，并采用一定策略保證了初始種群在求解空間中的均勻分布，這使算法具有較強(qiáng)的搜索能力和較好的收斂性能。對7個經(jīng)典benchmark函數(shù)的測試結(jié)果表明：該算法在最優(yōu)解質(zhì)量、平均進(jìn)化代數(shù)和平均評價次數(shù)上都優(yōu)于或至少不輸于文獻(xiàn)［5］的算法，同時該算法也具有很好的穩(wěn)定性。

［1］STORN R，PRICE K.Differential evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces［C］//International Computer Science Institute，California：Berkely，1995.

［2］PLAGIANAKOS V P，VRAHATIS M N.Parallel evolutionary training algorithms for“hardware friendly”neural networks［J］.Natural Computing，2002（1）：307-322.

［3］CHAKRABORTY U K，DAS S，KONAR A.Differential evolution with local neighborhood［C］//IEEE Congress on Evolutionary Computation CEC2006.Vancouver：IEEE Press，2006：2042-2049.

［4］何兵，車林仙，劉初升.雙種群差分進(jìn)化規(guī)劃算法［J］.計算機(jī)工程與應(yīng)用，2012，48（26）：25-31.

［5］劉進(jìn)，覃潔萍.帶慣性變異與正交設(shè)計的差分進(jìn)化改進(jìn)算法［J］.計算機(jī)工程與應(yīng)用，2011，47（34）：34-38.

［6］姜立強(qiáng)，劉光斌，郭錚.分工差分進(jìn)化算法［J］.小型微型計算機(jī)系統(tǒng)，2009，30（7）：1302-1304.

［7］武志峰，黃厚寬，張瑩.基于Boltzmann機(jī)制的雙子代競爭差異演化算法［J］.南京大學(xué)學(xué)報，2008，44（2）：195-203.

［8］張偉，劉三陽.動態(tài)局部搜索差分進(jìn)化算法［J］.西南大學(xué)學(xué)報：自然科學(xué)版，2015，37（3）：93-98.

［9］歐陽海濱，高立群，孔祥勇．隨機(jī)變異差分進(jìn)化算法［J］.東北大學(xué)學(xué)報：自然科學(xué)版，2013，34（3）：330-334.

An improved differential evolution algorithm with local search operator

WU Zhi-feng，LIU Shuo，LI Yao-hui
（School of Information Technology and Engineering，Tianjin University of Technology and Education，Tianjin 300222，China）

As a particular instance of EA，although differential evolution algorithm is simple and powerful for optimizing continuous functions，it is still faced with premature convergence and easy getting in local optimization problems.In order to solve these problems，an improved differential evolution algorithm with local search operator is presented in this paper.For increasing colony diversity，the population is initialized by an uniform distribution.A local stochastic disturbance term is taken to the best individual of the population in each iteration with a probability.It can search a new individual with better fitness nearby the current individual and speed up the convergence.The experiments on seven common test functions show that this proposed algorithm is superior to the other algorithm on the quality of solution，average evaluation number and convergence speed.

differential evolution algorithm；local search；global optimization

TP301.6

A

2095－0926（2015）04－0001－04

2015-07-16

天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計劃（14JCYBJC15400）；天津職業(yè)技術(shù)師范大學(xué)人才計劃資助項目（RC14-51）.

武志峰（1974—），男，教授，博士，碩士生導(dǎo)師，研究方向為演化計算、數(shù)據(jù)挖掘與知識發(fā)現(xiàn).