基于耗散結構理論的差分進化算法

摘 要:差分進化算法是一種新的進化計算技術，為解決其早熟問題，提出了一種基于耗散結構理論的改進差分進化算法。在變異成功的個體數和交叉算子之間建立聯系，使變異成功的個體影響交叉算子，提高全局收斂能力。仿真實驗表明，通過對三個標準測試函數的測試，并與標準遺傳算法和差分進化算法相比，所提出的改進差分進化算法是一種收斂速度快、求解精度高、魯棒性較強的全局優化算法。

關鍵詞:差分進化算法; 耗散結構; 海明距離; 測試函數

中圖分類號:TP301.6

文獻標志碼:A

文章編號:1001-3695(2010)02-0503-03

doi:10.3969/j.issn.1001-3695.2010.02.027

Differential evolution based on dissipative structure theory

NIU Xue-li， LIU Xi-yu， WEI Xin

(School of Management Economics， Shandong Normal University， Jinan 250014， China)

Abstract:Differential evolution algorithm is a new evolutionary computation technology. In order to avoid the premature convergence problem， this paper proposed a modified differential evolution algorithm with the dissipative structure theory. Established the relationship between the number of the successfully mutated individuals and the cross operator. So the number of the successfully mutated individuals could affect the cross operator， improved the global search. In test， used three benchmark functions， and compared the performance of the proposed modified differential evolution algorithm with GA and DE. The result demonstrates that it’s a powerful global optimization algorithm with rapid convergence rate， high solution quality and robustness.

Key words:differential evolution; dissipative structure: Hamming distance; benchmark function

差分進化(differential evolution， DE)算法[1，2]是由R.Storn和K.Price于1995提出的一種采用浮點矢量編碼，在連續空間中進行隨機搜索的優化算法，其原理簡單，受控參數少。DE算法作為一種性能卓越的優化算法正受到日益關注，其應用領域也越來越廣[3~6]。

DE算法是根據父代個體間的差分矢量進行變異、交叉和選擇操作，與其他進化算法(如遺傳算法)一樣易陷入局部最優，存在早熟收斂現象。為提高DE算法的性能，很多學者提出了改進方法。文獻[7]針對差分矢量的縮放因子F和交叉概率CR兩參數對算法的影響，提出了一種模糊自適應差分進化算法;文獻[8]將縮放因子F由固定數值設計為隨機函數，減少了需調整的參數，實現了一個簡化的DE版本;文獻[9]提出了一種雙群體偽并行差分進化算法，該算法采用雙種群結構提高了DE算法的全局搜索能力和收斂速率。

DE算法的性能與其變異、交叉操作密切相關。針對DE算法中過早收斂于目標函數的局部最優解的問題，本文在對耗散結構理論研究的基礎上，提出了基于耗散結構的自適應差分進化算法。

1 基本差分進化算法

DE算法同遺傳算法(GA)一樣，也包括交叉、變異和選擇等進化算子，但與其他進化算法不同的是，DE算法在隨機選擇的父代個體間差分矢量的基礎上生成變異個體;接著按一定的概率對父代個體與生成的變異個體進行交叉操作，生成實驗個體;最后采用貪婪策略在父代個體與實驗個體之間進行選擇操作，選擇具有更佳適應度的個體作為子代個體。

1.1 變異操作

對于每個目標向量xi，G，i=1，2，…，NP，基本DE算法的變異向量如式(1)所示:

mi，G+1=xr1，G+F#8226;(xr2，G-xr3，G)(1)

其中，隨機選擇的序號r1、r2和r3互不相同。變異算子F∈[0，2]是一個實常數因數，控制偏差變量的放大作用。

1.2 交叉操作

DE算法利用交叉操作來保持種群多樣性，則實驗向量變為式(2)所示。

uij，G+1=mij，G+1 rand(j)≤CR or j=rand n(i)

xij，G+1 rand(j)≤CR or j≠rand n(i)(2)

其中:rand(j)∈[0，1]為均勻分布的隨機數，j表示第j個變量;CR為交叉概率常數，其大小預先確定;rand n(i)∈[1，2，…，D]為隨機選擇的維數變量索引，以保證實驗矢量至少有一維變量由變異矢量貢獻。

1.3 選擇操作

DE算法采用“貪婪”選擇策略產生子代個體。將試驗向量與當前種群中的目標向量xi，G進行比較，若目標函數要被最小化，那么具有較小目標函數值的向量將被選為子代個體。

2 基于耗散結構理論的改進DE

2.1 耗散結構理論

在基于與環境進行能量交換的開放系統中，存在著復雜性不斷增長的結構，比利時科學家I. Prigogine將其發展為常規的熱力學概念——耗散結構[10](dissipative structure)。一個遠離平衡的開放體系，通過不斷地與外界交換物質和能量，可能從原來的無序狀態變為一種時間、空間或功能有序的狀態，在這種非平衡狀態下的非線性區形成的有序結構就成為耗散結構。這種結構是由于進行不可逆過程時，體系發生能量耗散所導致的。

可以將耗散結構理論引入到差分進化算法中進行分析。系統初始條件為隨機選取的個體，即系統處于遠離平衡態。通過變異算子，選擇的作用使種群向適應度高的方向發展，變異算子為種群的這種發展提供了隨機擾動。初始個體和變異算子、交叉算子、選擇的作用造就了種群的向前發展，因而形成了一種耗散結構。但是隨著進化的不斷進行，系統中的不同個體在交叉算子、變異算子、選擇的作用下逐漸趨于相同，種群的多樣性漸趨于零。隨著進化代數的增大，適應值并沒有得到改善，使得耗散結構逐漸消失，即缺乏“持續發展”的能力，相當于陷入局部最優。變異和交叉算子對差分進化算法的收斂性起著決定作用，所以可以通過對交叉算子的操作改善上述缺點。當系統耗散結構逐漸消失時，在原來基礎上增大交叉概率，相當于與外界進行更多的物質和能量的交換，以促進系統繼續向前發展。

2.2 變異算子

在本算法中變異算子F取0.5，根據兩個被選中進行差運算的父代個體的海明距離來決定是否執行變異操作。其中，個體xr2，G隨機選擇，xr3，G個體選擇與xr2，G海明距離最大的個體。當海明距離大于某個閾值Pr時進行差運算，否則不進行。因為當海明距離較小時，兩個個體相似程度太高，變異起不到很好的作用。在初始階段，Pr可取較小的值，防止收斂到局部極值，隨著進化的進行應逐漸增大，以便在最優值附近進行微調。通過計算成功進行變異操作的個體數在所有根據海明距離選擇出來的個體數中所占的比例大小，從而與交叉算子建立聯系。定義表示閾值的函數為

Pr=0.5L+0.5(L+1)(1-e-3GGsum)

其中:L為個體向量的長度;Gsum為總的進化代數;G為當前的進化代數。

2.3 交叉算子

本算法在對耗散結構理論分析的基礎上，將非平衡系統從無序到有序的發展思想應用于差分進化算法，將種群的交叉行為認為是系統與環境進行能量交換的方式，即構成了一個耗散系統結構。將第i代的n個個體存儲在N×L的矩陣A(i)中，fj表示矩陣第j行的個體的適應度。用CR=1-f′(j)+Rm/(10×Rt)來表示第j行的交叉概率。其中f′(j)是適應度不大于fj的個體數在個體總數n中所占的比例;Rt為所有根據海明距離選擇出來的個體數;Rm為Rt中海明距離小于閾值Pr的個體數，即不成功變異的個體數。

可以看出，上述交叉概率與成功變異的個體數相關。成功變異的個體數較少時，CR增大，說明這一代中相似個體過多，無法滿足系統有序的要求，系統的耗散結構逐漸消失。為了使系統繼續向前發展，所以增大交叉概率。成功變異的次數較多時，CR減少，說明這一代中相似個體少，此時對應于當前的系統狀態，已經存在足夠的“波動”，系統基本可以通過自組織繼續向前發展，此時的交叉概率就在原來自適應算法的基礎上加上一個較小的值。若計算出來的CR大于1，則定義CR=1。

2.4 改進DE的算法(DADE)過程

a)初始化種群規模NP、變異算子F，最大進化代數Gmax，按如下公式隨機初始化每一個個體:xij=rand[0，1](xuj-xlj)+xlj。其中，i=1，2，…，NP;j=1，2，…，D;xuj為第j維變量的上限;xlj為下限，并將隨機生成的n個個體保存在矩陣A中。

b)對初始種群進行評價，即計算初始種群中每個個體的目標函數值。

c)判斷是否達到終止條件或進化代數達到Gmax，若是，則進化終止，將此時的最佳個體作為解輸出;若否則繼續。

d)變異操作。首先按fj的大小對A中個體進行排序，并隨機選擇第一個個體xr1，G;其次將A中剩余個體生成海明距離矩陣H并隨機選擇第二個個體xr2，G，在H中找出與之海明距離最大的個體xr3，G。如果xr2，G，xr3，G的海明距離大于閾值Pr，則進行差運算，并與個體xr1，G進行變異操作，否則不變異，并將變異后的個體放在矩陣B中。若未成功變異，Rm增1然后在矩陣A和B中選出n個適應度最好的個體，存入矩陣A中。

e)交叉操作。對A中的個體按適應度大小進行排序，并對矩陣A(i)逐行計算。計算每一行的CR，對于每一行j產生一個隨機數x，如果x≤CR，就在這一行上進行交叉，否則這一行保持不變，進行下一步的計算。

f)按貪婪準則進行選擇操作，得到新種群。

g)進化代數k=k+1，執行步驟c)~f)，直到滿足終止條件。

其算法流程如圖1所示。

3 仿真實驗

為了測試DADE的性能，本文通過三個典型的基準測試函數進行測試，并與遺傳算法和差分進化算法進行了比較。

1)Rastrigrin函數

f1=∑30i=1(xi2-10 cos(2πxi)+10)

xi取值范圍為(-5.12，5.12)

全局最優點:xi=0， f(x)=0

2)Rosenbrock函數

f2=∑30i=1(100(xi+1-xi2)2+(xi-1)2)

xi取值范圍為(-30，30)

全局最優點:xi=0，f(x)=0

3)Griewank函數

f3=14000∑30i=1xi2-∏30i=1cos(xii)+1

xi取值范圍為(-50，50)

全局最優點:xi=0， f(x)=0

這三個基準函數具有不同的特點，可以充分考慮新型算法對不同類型問題的優化性能。f1為多峰函數，在S={xi∈(-5.12，5.12)，i=1，2，…，n}范圍內有大約10n個局部極小點;f2為非凸，病態的函數;f3是一種典型的多模態函數，具有大量局部極值。

表1列出了每個函數的參數設置，三種算法的參數初始化如下:種群規模NP均為100，DADE變異算子F取0.5，初始交叉率CR0取0.3，最大進化代數Gmax為1 000。GA采用實數編碼方式，其中交叉率wc取0.8，變異率wm取0.02。

表1 測試函數的參數設置

函數 n搜索區域

RastigrinRosenbrockGriewank303030[-5.12，5.12]n[-30，30]n[-50，50]n

圖2~4是上述三種算法求解各測試函數運行20次最優解平均值的進化曲線，縱坐標為最優解的對數值。從圖中可以看出，對于這三個高維多峰函數，GA均提前收斂，出現早熟現象;DE的求解精度雖然好于GA，但在計算過程中仍早熟收斂，得不到令人滿意的優化結果;而DADE的求解精度比以上兩種方法高很多，具有很強的尋優能力。因此，DADE在性能上較DE算法有明顯的改善，能有效避免早熟，具有很強的全局收斂性。

4 結束語

本文在含有變異和交叉的自適應算法的基礎上，引入耗散結構理論，提出一種基于耗散結構理論的自適應差分進化算法。該算法不但保留了DE實現簡單、并行搜索的特點，并且通過海明距離調整變異率，使變異成功的個體影響交叉算子。通過對測試函數的測試表明，該算法全局收斂性強、穩定性好、求解精度高。

參考文獻:

[1]STORN R， PRICE K. Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces， TR-95-102[R]. Berkeley:International Computer

Science Institute， 1995.

[2]PRICE K. Differential evolution: a fast and simple numerical optimizer[C]//Proc of Biennial Conferencnce of the North American Fuzzy Information Processing Society. New York: [s. n.]， 1996:524-527.

[3]CHEONG F， LAI R. Designing a hierarchical fuzzy logic controller using differential evolution[C]//Proc of IEEE International Fuzzy Systems Conference. 1999:277-282.

[4]MOALLA S， ALIMI A M， DERBEL N. Design of beta neural systems using differential evolution[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics. 2002:6-9.

[5]URSEM R K， VADSTRUP P. Parameter identification of induction motors using differential evolution[C]//Proc of the 5th Congress on Evolutionary Computation. Canberra: [s.n.]， 2003:790-796.

[6]VESTERSTROM J， THOMSEN R. A comparative study of differential evolution， particle swarm optimization， and evolutionary algorithms on numerical benchmark problems[C]//Proc of Congress on Evolutionary Computation. Piscataway:IEEE Press， 2004:1980-1987.

[7]LIU Jun-hong， LAMPINEN J. A fuzzy adaptive differential evolution algorithm[C]//Proc of IEEE Region 10 Conference on Computers， Communications， Control and Power Engineering. Berlin:Springer， 2002:606-611.

[8]謝曉峰，張文俊，張國瑞，等.差異演化的實驗研究[J].控制與決策，2004，19(1):49-52.

[9]吳亮紅，王耀南，袁小芳，等.雙群體偽并行差分進化算法研究及其應用[J].控制理論與應用，2007， 24(3): 453-458.

[10]常青，鐘民先.基于耗散結構的改進遺傳算法求取紅外圖像二維閾[J].華東理工大學學報:自然科學版，2005，31(5):639-643.