求解函數優化的新型差異演化算法

摘 要：針對差異演化算法存在早熟收斂和后期求解效率低的缺點，提出一種新型差異演化算法。該算法基于單種群，在演化過程中直接對當前種群進行變異、交叉和選擇操作，無須差異演化算法中的中間過渡種群。此外，新型差異演化算法的變異與交叉概率是時變的，其中變異概率隨著迭代次數的增加而減小；交叉概率隨著迭代次數的增加而增加。對幾個典型的測試函數進行仿真實驗表明，該算法能夠有效避免早熟收斂，改善了差異演化算法的優化性能。

關鍵詞：函數優化；差異演化；單種群；時變變異；時變交叉

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2009)06-2047-03

doi:10.3969/j.issn.1001-3695.2009.06.014

Novel differential evolution algorithm for function optimization

DENG Chang-shou1，2，LIANG Chang-yong1

(1.Institute of Computer Network System， Hefei University of Technology， Hefei 230009， China；2.School of Information Science Technology， Jiujiang University， Jiujiang Jiangxi 332005， China)

Abstract:This paper proposed a novel differential evolution algorithm to overcome the premature convergence and slow convergent speed during the late evolution in differential evolution algorithm.The new algorithm was based on single population without intermediate population， in which mutation operation， crossover operation and selection operation were used on the current population. In addition， the parameters of mutation and crossover in the new DE were time-varying. The probability of mutation decreased with the evolution， while the probability of crossover was increasing. Results of several typical benchmark functions show the algorithm can avoid premature convergence and improve the performance of differential evolution algorithm in optimization.

Key words:function optimization; differential evolution; single population; time varying mutation; time varying crossover

0 引言

差異演化(differential evolution， DE)是一種實數編碼的基于種群演化的全局優化算法^[1]。DE原理簡單，控制參數少，實施隨機、并行、直接的全局搜索，易于理解和實現。目前已經成為演化算法的一個重要分支，在約束優化計算、模糊控制器優化設計、神經網絡優化和濾波器設計等方面得到了廣泛應用^[2~5]。

DE算法根據父代個體間的差異向量進行變異、交叉和選擇操作，與其他演化算法一樣易陷入局部最優，存在早熟收斂和迭代后期搜索效率低等現象。常見的解決方法主要是增加種群的規模，但這樣會增加計算量，而且也不能從根本上克服早熟收斂的問題。為了提高DE算法的性能，目前已有學者提出了一些改進方法。例如文獻[6]在DE算法中加入了遷移算子和加速算子，提高了算法的種群多樣性和收斂速率，然而它需要計算目標函數的梯度信息，實現較為麻煩且缺乏通用性，推廣應用受到限制。文獻[7]針對DE算法中的變異概率F和交叉概率CR兩參數對算法的影響，提出了一種模糊自適應DE算法，但是需要選擇模糊隸屬函數，實現較為困難。文獻[8]提出了與粒子群相混合的方法來提高DE算法的性能，然而由于粒子群算法的引入，增加了DE算法控制參數的復雜性和計算量。

與大多數的演化算法一樣，DE算法中當前種群中個體的優秀染色體只能在下一代有可能參與變異、交叉和選擇操作，這是影響DE算法收斂速度的一個重要原因。此外，產生早熟收斂的根本原因是隨著迭代次數的增加，種群多樣性快速下降。為了提高DE算法的收斂速度，克服早熟收斂，本文提出一種新型DE(novel DE，NDE)算法。該算法無須產生中間過渡種群，直接對當前種群進行變異、交叉和選擇操作，提高了DE算法的收斂速度。此外，該算法中的變異和交叉概率是時變的，隨著迭代次數的增加而變化，增加了種群的多樣性，克服了早熟收斂。仿真結果表明，與DE算法以及標準遺傳算法相比，NDE 算法能取得較好的優化性能，收斂速率得到明顯提高。

1 DE算法

DE算法首先在問題的可行解空間隨機產生初始種群，然后對當前種群進行變異和交叉操作，產生一個過渡種群；接著基于貪婪的思想，對當前種群和過渡種群中的對應個體進行一對一的選擇，產生新一代群體。DE算法根據變異和交叉操作的不同，形成了不同的模式，常見的有DE/rand/1/bin和DE/best/1/bin^[1]。DE/rand/1/bin的算法流程如圖1所示。設DE算法種群規模為NP，每個個體是D維向量，則第G代中的個體可表示為Xi，G（i=1，2，…，NP）。DE算法的主要操作包括產生初始種群、變異、交叉和選擇。

產生初始種群比較簡單，即在D維空間中，隨機產生均勻分布的滿足上下界約束的NP個個體的種群Xi，0(i=1，2，…，NP)。

DE 算法的變異操作是利用隨機兩個個體間的偏差擾動產生新個體。變異操作后得到中間個體記為vi，G+1，即

vi，G+1=Xr1，G+F×(Xr2，G-Xr3，G)(1)

交叉操作是將當前所得到的中間個體vi，G+1與個體Xi，G進行雜交，如式(2)所示。交叉操作得到當前個體的候選個體ui，G+1=(u1i，G+1，u2i，G+1，…，uDi，G+1)。

uij，G+1=vij，G+1 if (rand＜CR) or j=R(i)

Xij，Gelse(2)

其中:i=1，2，…，NP；j=1，2，…，D；rand∈[0，1]是一個均勻分布的隨機數；R（i）∈[1，D]之間的隨機整數；CR∈[0，1]為交叉概率。采用這種交叉策略，可以確保下一代個體中至少有一個染色體來源于中間個體。

選擇操作時首先評價候選個體的函數適應值，然后根據式(3)決定哪個個體進入下一代種群。

以上描述表明，DE算法中當前種群經變異、交叉操作所產生的優秀染色體，在本次的迭代過程中不能發揮其作用，而只有其進入下一代群體之后才能夠發揮優勢，因此在一定程度上影響了DE算法的收斂速度。其次，DE算法中間個體與初始種群需要占用同樣多的存儲資源，尤其是對于高維和大種群問題，需要占用大量的內存。最后，DE 算法核心思想是利用其他隨機個體間的向量之差產生新的中間個體，這種方式決定了DE 算法在許多問題上都有很好的收斂表現。然而，隨著迭代次數的增加，個體之間的差異逐漸減小，就會出現搜索速度相對緩慢，局部搜索能力下降，逼近全局最優解時仍需要經過很多次迭代才能獲得最優值。

2 新型DE算法

2.1 單種群

為了提高DE算法的收斂速度，使當代種群中經變異、交叉操作之后產生的優秀染色體可以參與當代群體中其他個體的變異與交叉操作，節約內存資源，本文修改了DE算法的框架，省略了DE算法中的中間過渡種群，經交叉與變異操作之后形成的新個體，經選擇操作之后，直接參與當代種群的演化操作，而無須等待進入下一代之后才參與演化操作。

2.2 時變變異與時變交叉

DE算法的搜索性能與變異操作以及交叉操作密切相關。變異概率F太大，DE算法在尋優過程中最優解容易遭到破壞，算法搜索效率低下，求得全局最優解的概率低；變異概率F太小，搜索過程中種群的多樣性低，容易陷入局部最優解，出現早熟現象。

交叉概率CR越大，中間個體vi，G+1對候選個體ui，G+1的貢獻越多，有利于局部搜索和加速收斂速度；反之當前個體Xi，G對該候選個體的貢獻越多，有利于保持種群的多樣性和全局搜索。良好的搜索策略應該是在搜索的初始階段保持種群多樣性進行全局搜索，而在搜索的后期應加強局部搜索能力，提高算法的精度。

為此，在NDE算法中，本文提出時變變異概率和時變交叉概率。它能根據算法的搜索進展情況，自適應地確定變異率和交叉率，使算法在初期有較大的變異率和較小的交叉概率；在后期逐步降低變異率和提高交叉概率，保留優良信息， 避免最優解遭到破壞，增加了搜索到全局最優解的概率。時變變異如式(4)，時變交叉如式(5)。

F=F0×2e(1-iter max/(iter max-iter+1)) (4)

其中:F0是常數；iter max為最大迭代次數；iter為當前迭代次數。

CR=CRMIN+iter/iter/iter max×(CRMAX-CRMIN)(5)

其中:CRMIN、CRMAX為常數；iter max為最大迭代次數；iter為當前迭代次數。

2.3 新型DE算法流程圖

本文提出的新型DE算法流程如圖2所示。

3 算法測試

為了驗證NDE算法的性能，選取文獻[9]測試新的種群自適應遺傳算法NGAAPS的四個標準測試函數對NDE算法進行測試，并與標準DE算法、標準遺傳算法SGA以及NGAAPS算法進行了比較。測試函數如下：

a)測試函數1(Sphere)

f1(x)=3i=1x2i，-5.12≤x≤5.12

b)測試函數2(Rosenbrock)

f2(x)=100(x2-x21)2+(x1-1)2-2.048≤x1，x2≤2.408

c)測試函數3(Rastrigin)

f3(x)=20+2i[x2i-10 cos (2πxi)]，-5.12≤xi≤5.12

d)測試函數4(Schaffer)

f4(x)=0.5-(sin2x21+x22-0.5)/[1+0.001(x21+x22)]2-100≤x1，x2≤100

其中： f1為三參數、單極值的二次函數，在(0，0，0)處有最小值0，容易搜索到最優解； f2為二參數、單極值的非二次函數，但它是病態的，有一狹長深谷，且極難極小化，尋優中可能陷入局部解，其在(1，1)處有全局最小值0； f3是一個具有多個局部最優點的多峰函數，局部極小點成正弦坡度分布，其在(0，0)處有全局最小值為0； f4在(0， 0)處有最大值為1，該函數最大值峰周圍有一圈脊，其取值均為0.990 283，因此很容易陷入在此的局部最大點。實驗時，NDE算法的參數，NP=30，F0=0.3，CRMAX=0.9，CRMIN=0.6，最大迭代次數為500；DE算法中F=0.6，CR=0.6，其他參數與NDE算法中的參數相同。當搜索得到的最優解的函數值與理想極值的誤差小于10-6時，則認為算法收斂并停止進化。每個測試函數用NDE和DE算法分別運行100次，記錄算法停止搜索時找到最優解的平均進化代數(AvgGN)和最優解函數值與理想極值的平均誤差(AvgfE)，以及100次求解的成功率，與文獻[9]中的SGA以及NGAAPS求解結果的對比情況如表1所示。SGA與NGAAPS采用輪盤賭選擇和單點交叉，交叉率為0.7，變異概率為0.01。種群數為30，最大進化代數為1 000，當搜索得到的最優解的函數值與理想極值的誤差小于10-3時，則認為算法收斂并停止進化。

表1的實驗結果表明，對于四個標準測試函數，NDE與DE算法的求解成功率均為100%，NDE算法收斂速度不僅比DE算法快，而且求解結果的精度高。此外，對于四個標準測試函數，NDE算法在求解成功率、收斂速度以及求解精度等方面都顯著優于標準遺傳算法SGA。對于函數f1和f3， NDE算法除平均收斂速度稍遜于NGAAPS算法之外，兩者的成功率均為100%，而且NDE算法求解精度高于NGAAPS算法；對于函數f2和f4，NDE算法的平均收斂速度快于NGAAPS算法，而且求解精度高于它；對于函數f4，NDE算法的成功率為100%，而NGAAPS算法的成功率僅為65%，因此NDE比NGAAPS算法具有更好的魯棒性。

4 結束語

本文提出一種新型DE算法，有效克服了基本DE算法早熟收斂和后期求解效率不高的問題。新型DE算法僅使用單個種群進行演化，無須過渡種群，直接對當代種群進行變異和交叉操作，使得當代種群中產生的優秀染色體在當代種群中可以發揮作用。另外，新型DE算法中的變異概率和交叉概率是時變的，提高了其優化性能。實例仿真實驗表明，與DE算法和標準GA算法相比，NDE不論在尋優性能還是在收斂性能上，均有極大的提高，是一種求解函數優化的有效方法。

參考文獻：

［1］STORN R，PRICE K.Minimizing the real functions of the ICEC’96 contest by differential evolution[C]//Proc of IEEE Conference on Evolutionary Computation.[S.l.]:IEEE Press，1996:842-844.

［2］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.

［3］STORN R.Designing nonstandard filters with differential evolution[J].IEEE Signal Processing Magazine，2005，22(1):103-106.

［4］CHEN Chong-wei，CHEN De-zhao，CAO Guang-zhi.An improved differential evolution algorithm in training and encoding prior knowledge into feedforward networks with application in chemistry [J].Chemo Metrics and Intelligent Laboratory Systems，2002，64(1):27-43.

［5］PATERLINIA S，KRINK T.Differential evolution and particle swarm optimization in partitional clustering[J].Computational Statistics Data Analysis，2006，50(5):1220-1247.

［6］CHIOU J P，WANG Feng-sheng.A hybrid method of differential evolution with application to optimal control problems of a bioprocess system[C]//Proc of International Conference on Evolutionary Computation.1998:627-632.

［7］LIU Jun-hong，LAMPINEN J.A fuzzy adaptive differential evolution algorithm[C]//Proc of the 10th IEEE Region Conference on Compu-ters，Communications， Control and Power Engineering.2002:606-611.

［8］HENDTLASS T.A combined swarm differential evolution algorithm for optimization problems[C]//Proc of the 14thInternational Conference on Industrial and Engineering Applications of Artificial Intelligence andExpert Systems:Engineering of Intelligent Systems.London:Springer-Verlag，2001:11-18.

［9］何宏，錢鋒.一種新的種群自適應遺傳算法[J].計算機應用研究，2006，23(10):30-32.