基于混沌的動(dòng)力學(xué)演化算法

2006年6月安陽(yáng)工學(xué)院學(xué)報June. 2006第3期(總第21期)Journal of Anyang Institute of TechnologyNo, 3( Gen. No 21)基于混沌的動(dòng)力學(xué)演化算法李彥勤王侃(河南經(jīng)貿職業(yè)學(xué)院,河南鄭州45000)摘要:文章在現有動(dòng)力學(xué)演化算法的基礎上提出基于混沌的演化算子。除有效地防止過(guò)早收斂并且保持解的均勻分布外,新算法充分利用混沌對于初始值敏感性和遍歷性的特點(diǎn),還具有更快的收斂速度和更小的計算量。數值鮚聚顯示在解決多峰值問(wèn)題時(shí)新算法不僅有很好的性能和高可靠性,而且優(yōu)于作者已知的其他已出版的結果。關(guān)鍵詞:動(dòng)力學(xué)演化算法;過(guò)早收斂;混沌初始化;混沌變異;種群多樣性中圖分類(lèi)號:TP01文獻標識碼:A文章編號:1673-2928(2006)03-0052-030引言系統中的粒子x1,x2,…xN演化算法中的演化代數從20世紀90年代初期開(kāi)始,演化計算與生物在此記為時(shí)間t。學(xué)、計算機科學(xué)、數學(xué)、物理學(xué)以及其他學(xué)科的交義下面介紹一下動(dòng)力學(xué)演化算法中的相關(guān)概念。研究在理論和應用方面都取得了很大進(jìn)展134,粒子x,在t時(shí)刻的動(dòng)量p(t,x)被定義為但是仍然有一些問(wèn)題尚未解決,首先是過(guò)早收斂p(t, xi)=f(t, x: )-f(1.2)(在演化早期階段喪失種群的多樣性),以及缺乏合f(t,x1)是在t時(shí)刻示粒子x1的目標函數值適的停止準則的問(wèn)題。定義了一個(gè)活動(dòng)量a(t,x,),如果在t時(shí)刻x參考文獻[5]中提出了一種基于統計力學(xué)理論被選擇參加進(jìn)化操作,則粒子x1在t時(shí)刻的活動(dòng)量的動(dòng)力學(xué)演化算法。它把種群看作一個(gè)動(dòng)力學(xué)系被定義為,把種群中的個(gè)體看作是粒子,系統中每個(gè)粒子(t,x1)=a(t-1,x;)+1(1.3)有一個(gè)動(dòng)量p(k,x)和一個(gè)活動(dòng)量a(t,x1)以模擬否則保持不變分子運動(dòng),這兩個(gè)參數聯(lián)合控制選擇操作并驅使粒綜合這兩個(gè)參數我們定義了一個(gè)新的選擇策子在解空間內移動(dòng)搜尋,提出了基于最優(yōu)控制論的略。兩個(gè)停止準則來(lái)測試系統是否在統計力學(xué)意義上slet(t,x)=λ∑p(k,x)|+(1-λ)a(t,取得它的最低的能量或者最大的熵的狀態(tài))(k=0,1,…t)混沌是自然界里一種很常見(jiàn)的現象,它有隨機權重λ(∈(0,1))用來(lái)均衡兩條件的比重。在性,遍歷性和對起始條件的敏感性等特點(diǎn)。所有這迭代過(guò)程中,slet(t,x)(i=1,2…N)被按照從小到些使得混沌可以被用來(lái)解決優(yōu)化問(wèn)題6。利用它大的順序排序DEA的選擇策略是:一個(gè)粒子的動(dòng)量的積累變陷人局部最優(yōu)。本文中的新算法利用混沌的隨機化量越小,以往被選擇的次數越少,在本次迭代中性,遍歷性和對初始條件敏感性的特點(diǎn)克服了傳統它被選擇的可能性越大。因此在迭代的過(guò)程中,全的隨機初始化方法的不足。由于對交叉、變異概率部粒子都將可能被選擇,即DEA的選擇策略將驅動(dòng)等參數選擇的不精確性,傳統的隨機初始化方法難系統內的全部粒子運動(dòng)搜尋最優(yōu)解,正如粒子時(shí)刻以保證解集的范圍,引起重要基因的丟失,導致過(guò)到處移動(dòng)一樣。也正是因為這一點(diǎn),我們將新算法早的收斂。而基于混沌的演化算法使得種群具有稱(chēng)為動(dòng)力演化的算法。真正的隨機性,已有一系列的基于混沌的演化算法另外,DEA還根據動(dòng)量提出兩條新的停止準被提出,事實(shí)證明加入混沌思想的算法更高效。則。第一條準則是算法描述如果1.1動(dòng)力學(xué)演化算法的描述∑lp(t,x,)|<東(i=1,2,…N)(1.5)設有一個(gè)最小值優(yōu)化問(wèn)題演化停止,這里是一個(gè)事先給定的誤差準許min f(x)(1.1)值學(xué)四心味著(zhù)全部粒子移動(dòng)f(x)是目標函數,S是它的可行的解的集合和消中國煤化工能量最低狀態(tài)。在新算法中,將N個(gè)已編碼的解類(lèi)比為動(dòng)力學(xué)CNMHG收稿日期:2006-04-07作者簡(jiǎn)介:李彥勤(1981-)女,河南經(jīng)貿職業(yè)學(xué)院教師。如果Step 1:用新初始化策略初始化種群r,計算rMax∑lp(k,x)|>M(k=0,1,…t;x∈中粒子的函數值且設置p(t,x)=0,a(t,x)=0,(1.6)x∈r,計算sc(t)并按大小排序,保存最好的粒子,則算法停止。M是給定的一個(gè)適當大的數,例 Gennum=0;如,M可被取為最大的目標函數值和最小的目標函Step2:選擇排在slet( GenNum)最前部的a個(gè)數值的差。但在實(shí)際應用中要確定一個(gè)適當的M粒子;值是困難,必須經(jīng)過(guò)多次仔細的試驗。Step3:對這n個(gè)粒子實(shí)施新的進(jìn)化操作;1.2混沌操作和動(dòng)態(tài)變異概率Step4:修改這n個(gè)粒子的評價(jià)函數值,動(dòng)量和新箅法提出新的初始策略和新的變異算子來(lái)活動(dòng)量的;加快收斂。數字實(shí)驗顯示IDEA能保持種群多樣Step5:保存最好的粒子和它們的函數值,修改性,避免過(guò)早收斂,并且是快速可靠的slct( GenNum)并排序,1.2.1新初始化策略( GenNum)← Gen Num+1根據混沌的隨機性,遍歷性和對初始條件的敏Step6: P= Pm *(1-Gen Num *0. 01/maxGen)感性等特點(diǎn),我們利用 logistic方程引入新的初始化Step7:如果不停止,回到Step2策略根據新算法,產(chǎn)生分布均勻的初始種群,在迭1=μx1(1-x1)(H=4(17)代過(guò)程中全部粒子都將被選擇參加演化操作,選擇N個(gè)初始化值隨機產(chǎn)生算子和動(dòng)態(tài)變異算子Pn也使種群均勻分布且避免N∈[0陷入局部最優(yōu)k是優(yōu)化函數的自變量的個(gè)數,N是種群規模。2實(shí)驗結果然后利用(1.7)式產(chǎn)生作為演化的混沌種群。在這個(gè)部分里,我們利用IDEA解決一些典型比如,y可以通過(guò)將y作為混沌序列的初始的數值優(yōu)化問(wèn)題。這些例子經(jīng)常被用于測試演化值,由(1.7)式反復迭代得到(k代表迭代的次數)。的算法的性能。在本程序中,我們把種群大小N然后使用下面的映射函數得到一個(gè)均勻分布定為100,使用第一個(gè)停止準則。以下的3個(gè)函數被的種群:x,;=a1+(b-a,)y,x,;∈[馮,b];用驗證新算法的效率。1,2,…,N(1.8)(1)Six-hump Camel Back Function1.2.2基于混沌的變異算子minf(x1,x2)=(4-2.1x12+1/3x1)x12+變異操作在Gas中屬于輔助性操作,它起到保x1x2+(-4+4x2)x2持種群多樣性的作用。通常,低的變異率能防止演where-3≤x1≤3,umnd-2≤x2≤2化過(guò)程中單個(gè)基因的丟失;太高的變異率會(huì )把CAs這個(gè)函數有6個(gè)局部最優(yōu)解,并在兩個(gè)不同的變成純隨機檢索。通常,變異率P。是在0.001左點(diǎn)取得全局最優(yōu)解:(x,x2)=(-0.0898,0.7126)和(x1,x2)=(0.0898,-0.7126)?；镜淖儺惒龠^(guò)程如下最大迭代次數設置為200,0=10-3。在這些1)使用預先確定的變異率P決定是否執行變設置下,我們連續執行程序10次,結果如下表所異操作示2)將已確定執行變異操作的個(gè)體x;根據下式表映射到區間[0,1]上:F-min-valX,=(xa)(a1-b,),i=1,2,…k;j-]0316280.0899330712390019995.831833E4(1.9)然后用(7)式得到1,通過(guò)(18)式再映射10316280089930.71271021556321314E4回去得到新個(gè)體的x。比較x,和x,保留較優(yōu)1031628|00900712526121973370812E4103162900898420712647018474480823E51.2.3動(dòng)態(tài)的變異率P103162900898420471265522924258演化算法中,交叉操作是主要操作,但是它過(guò)1.03162200910380-071234425392.128796E5度的依賴(lài)于當前的種群情況,容易陷于局部最優(yōu)10316908407126540241869368E4變異操作能有效地擺脫局部最優(yōu)但是由于變異的101890912413913034官目性,它僅僅在演化的早期階段有效,當算法開(kāi)10124100910120181254始接近最優(yōu)解集時(shí),變異操作幾乎不起作用。為了1031638093012594212842116加快收斂速度我們需要動(dòng)態(tài)改變變異概率Pn。從表中可看出,兩個(gè)點(diǎn)以等概率取得且我們得利用下列公式來(lái)動(dòng)態(tài)改變變異概率到的最小值均小干-1.0316結果表明,新算法快P= P*(1-Gen Num *0.01/ maxGen速、準中國煤化工Gen Num是當前演化代數, maxGen是最大代CNMHG數0.3c09(3丌x1)1.24IDEA算法0.4cos(4x2)+0.753其中-50≤x1,x2≤50。這個(gè)函數在(0,0)有一3小結個(gè)全局最優(yōu)解0。結果如下表所示。本文根據動(dòng)力學(xué)理論和混沌理論提出新的算表2法?；煦缧蛄袑τ诔跏贾档拿舾行砸环矫媸沟盟鉌-min-va法很容易跳出局部最優(yōu),另一方面混沌本身的特點(diǎn)01.288464-1484388El1737使得算法克服了純隨機函數的局限性,使算法更接8.24822371544426E7973近于自然界中的進(jìn)化過(guò)程。新算法提出基于混沌2433083E111.71990E-11861理論的初始化策略和變異策略驅動(dòng)全體解向最優(yōu)5422493E12-1.251275E-11754解移動(dòng)。新的演化策略可以在演化過(guò)程中有效的1067623E-138405404E8128628E8避免陷入局部最優(yōu)。通過(guò)3個(gè)典型的數值優(yōu)化問(wèn)287683E144274502E8-8564709題證明了新算法的高效性。但是由于IDEA與傳統9860141E64412475E4458819E4675演化算法的區別,更多相關(guān)的收斂理論有待進(jìn)一步1.245244008190461E7251探討。557667E126091238E94.074859E75742140027E-117395142E12961參考文獻:[1]Mitchell,M.An(3)Press, Cambridge, Massachusetts, 1996min f(x,y)=-[x sin(9y)+y cos (25x)+ [2] Baeck, T, Fogel, D. and Michalewicz, Z. Handbook ofevolutionary computation, Volume 1. Oxford University其中x2+y2≤81,-10≤x,y≤10Press, Oxford, England, 1997這個(gè)函數在點(diǎn)(y,x)=(04400-6.02780)取得全局最小值-32.7179。結果如下and hyperplane- defined function, Evolutionary Computa-2000,8,p373-391表所示4] Michalewicz Z, Genetic algorithms +Data structures =E表3volution prograrns, Springer Verlag, Berlin, Germany327164462730475[5]Yuanxiang Li, xiufen Zou. Solving Global Optimal problem327179-6440-627803554by using a Dynamical Evolutionary Algorithm. Proceedings32686865200-6166855274of the Fifth International Conference on Algorithms and Ar-chitectures for Parallel Processing, the IEEE Press, 2002ppl70-173.7000-62000-650007561[6]Haijun Yang, Minqiang Li. Dynamical Behavior of Genetic32,7964001-627804283Algorithms with Finite Population. Acta Automatica sinica327179-64400627802964Nov.,2004,Vol.30,No,6327116440262795271327142-6,44006.2792The Dynamical Evolutionary Algorithm Based on the ChaoticLI Yan -gin WANG KanHenan Vocational College of Economy and Trade, Zhengzhou 45000, China)Abstract: This paper proposes an improved dynamical evolutionary algorithm (IDEA) based on the theory of statistical mechanics anovel chaotic operation. Besides preventing premature convergence effectively and keeping the population in good distribution, the newalgorithm makes full use of initial value sensitivity and track ergodicity of chaos, overcoming the disadvantage of big searching deadzone existed in conventional chaotic mutation model. The numerical results show IDEA not only has good performance and a high de-gree of reliability while dealing with various complex problems, but also is superior to any other published results known by the authorsKey Words: dynamical evolutionary algorithm; premature convergence; chaotic mutation; population diversity中國煤化工編輯郝安林CNMHG