武志峰，劉爍，李耀輝

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

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

武志峰，劉爍，李耀輝

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

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

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

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

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

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

1　差異演化算法

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

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

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

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

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

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

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

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

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

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

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

2.1算法基本思想

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

2.2均勻初始化種群

為保證初始種群在問題解空間的均勻分布，算法沒有采用隨機(jī)生成初始種群的方法，而是根據(jù)種群規(guī)模把自變量的取值范圍均勻分為若干段，然后在每一段區(qū)間上隨機(jī)生成一個(gè)個(gè)體，從而保證了初始種群中每個(gè)個(gè)體在求解空間上分布的均勻性。例如，自變量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)的全局搜索能力，但同時(shí)也會(huì)導(dǎo)致算法收斂速度變慢。特別是當(dāng)問題的全局最優(yōu)解就在當(dāng)前最優(yōu)解附近時(shí)，算法卻可能還需要搜索多次才能得到全局最優(yōu)解。為加快算法的收斂速度，本文算法對(duì)每一代種群中的最優(yōu)個(gè)體以一定概率加入隨機(jī)擾動(dòng)的局部搜索算子，以便使其在當(dāng)前最優(yōu)個(gè)體附近快速尋找更好的個(gè)體。若發(fā)現(xiàn)更優(yōu)的新個(gè)體，則再次對(duì)新個(gè)體進(jìn)行局部搜索，直到新個(gè)體停止改進(jìn)或概率條件不滿足為止。之所以不采用確定性的加入，主要是為了保證種群的多樣性，從而避免算法陷入局部最優(yōu)。局部搜索算子公式定義如下：

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

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

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

2.4算法描述

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

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

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

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

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

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

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

3　實(shí)驗(yàn)測(cè)試及結(jié)果分析

為驗(yàn)證本文算法的性能，將其與文獻(xiàn)［5］中的算法進(jìn)行對(duì)比測(cè)試。測(cè)試函數(shù)取文獻(xiàn)［5］中給出的7個(gè)常用測(cè)試函數(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ù)，是一個(gè)非凸、病態(tài)單峰函數(shù)；其他函數(shù)為多峰函數(shù)；f2和f7在（1，1，…，1）處取最小值0，f6在（－1，－1，…，－1）處取最小值0，其他函數(shù)均在（0，0，…，0）處取最小值0。

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

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

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

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

4　結(jié)束語

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

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

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

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

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

［9］歐陽海濱，高立群，孔祥勇．隨機(jī)變異差分進(jìn)化算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(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ù)研究計(jì)劃（14JCYBJC15400）；天津職業(yè)技術(shù)師范大學(xué)人才計(jì)劃資助項(xiàng)目（RC14-51）.

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