2006年6月安陽工學(xué)院學(xué)報(bào)June. 2006第3期(總第21期)Journal of Anyang Institute of TechnologyNo, 3( Gen. No 21)基于混沌的動(dòng)力學(xué)演化算法李彥勤王侃(河南經(jīng)貿(mào)職業(yè)學(xué)院,河南鄭州45000)摘要:文章在現(xiàn)有動(dòng)力學(xué)演化算法的基礎(chǔ)上提出基于混沌的演化算子。除有效地防止過早收斂并且保持解的均勻分布外,新算法充分利用混沌對(duì)于初始值敏感性和遍歷性的特點(diǎn),還具有更快的收斂速度和更小的計(jì)算量。數(shù)值鮚聚顯示在解決多峰值問題時(shí)新算法不僅有很好的性能和高可靠性,而且優(yōu)于作者已知的其他已出版的結(jié)果。關(guān)鍵詞:動(dòng)力學(xué)演化算法;過早收斂;混沌初始化;混沌變異;種群多樣性中圖分類號(hào):TP01文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1673-2928(2006)03-0052-030引言系統(tǒng)中的粒子x1,x2,…xN演化算法中的演化代數(shù)從20世紀(jì)90年代初期開始,演化計(jì)算與生物在此記為時(shí)間t。學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、物理學(xué)以及其他學(xué)科的交義下面介紹一下動(dòng)力學(xué)演化算法中的相關(guān)概念。研究在理論和應(yīng)用方面都取得了很大進(jìn)展134,粒子x,在t時(shí)刻的動(dòng)量p(t,x)被定義為但是仍然有一些問題尚未解決,首先是過早收斂p(t, xi)=f(t, x: )-f(1.2)(在演化早期階段喪失種群的多樣性),以及缺乏合f(t,x1)是在t時(shí)刻示粒子x1的目標(biāo)函數(shù)值適的停止準(zhǔn)則的問題。定義了一個(gè)活動(dòng)量a(t,x,),如果在t時(shí)刻x參考文獻(xiàn)[5]中提出了一種基于統(tǒng)計(jì)力學(xué)理論被選擇參加進(jìn)化操作,則粒子x1在t時(shí)刻的活動(dòng)量的動(dòng)力學(xué)演化算法。它把種群看作一個(gè)動(dòng)力學(xué)系被定義為,把種群中的個(gè)體看作是粒子,系統(tǒng)中每個(gè)粒子(t,x1)=a(t-1,x;)+1(1.3)有一個(gè)動(dòng)量p(k,x)和一個(gè)活動(dòng)量a(t,x1)以模擬否則保持不變分子運(yùn)動(dòng),這兩個(gè)參數(shù)聯(lián)合控制選擇操作并驅(qū)使粒綜合這兩個(gè)參數(shù)我們定義了一個(gè)新的選擇策子在解空間內(nèi)移動(dòng)搜尋,提出了基于最優(yōu)控制論的略。兩個(gè)停止準(zhǔn)則來測(cè)試系統(tǒng)是否在統(tǒng)計(jì)力學(xué)意義上slet(t,x)=λ∑p(k,x)|+(1-λ)a(t,取得它的最低的能量或者最大的熵的狀態(tài))(k=0,1,…t)混沌是自然界里一種很常見的現(xiàn)象,它有隨機(jī)權(quán)重λ(∈(0,1))用來均衡兩條件的比重。在性,遍歷性和對(duì)起始條件的敏感性等特點(diǎn)。所有這迭代過程中,slet(t,x)(i=1,2…N)被按照從小到些使得混沌可以被用來解決優(yōu)化問題6。利用它大的順序排序DEA的選擇策略是:一個(gè)粒子的動(dòng)量的積累變陷人局部最優(yōu)。本文中的新算法利用混沌的隨機(jī)化量越小,以往被選擇的次數(shù)越少,在本次迭代中性,遍歷性和對(duì)初始條件敏感性的特點(diǎn)克服了傳統(tǒng)它被選擇的可能性越大。因此在迭代的過程中,全的隨機(jī)初始化方法的不足。由于對(duì)交叉、變異概率部粒子都將可能被選擇,即DEA的選擇策略將驅(qū)動(dòng)等參數(shù)選擇的不精確性,傳統(tǒng)的隨機(jī)初始化方法難系統(tǒng)內(nèi)的全部粒子運(yùn)動(dòng)搜尋最優(yōu)解,正如粒子時(shí)刻以保證解集的范圍,引起重要基因的丟失,導(dǎo)致過到處移動(dòng)一樣。也正是因?yàn)檫@一點(diǎn),我們將新算法早的收斂。而基于混沌的演化算法使得種群具有稱為動(dòng)力演化的算法。真正的隨機(jī)性,已有一系列的基于混沌的演化算法另外,DEA還根據(jù)動(dòng)量提出兩條新的停止準(zhǔn)被提出,事實(shí)證明加入混沌思想的算法更高效。則。第一條準(zhǔn)則是算法描述如果1.1動(dòng)力學(xué)演化算法的描述∑lp(t,x,)|<東(i=1,2,…N)(1.5)設(shè)有一個(gè)最小值優(yōu)化問題演化停止,這里是一個(gè)事先給定的誤差準(zhǔn)許min f(x)(1.1)值學(xué)四心味著全部粒子移動(dòng)f(x)是目標(biāo)函數(shù),S是它的可行的解的集合和消中國(guó)煤化工能量最低狀態(tài)。在新算法中,將N個(gè)已編碼的解類比為動(dòng)力學(xué)CNMHG收稿日期:2006-04-07作者簡(jiǎn)介:李彥勤(1981-)女,河南經(jīng)貿(mào)職業(yè)學(xué)院教師。如果Step 1:用新初始化策略初始化種群r,計(jì)算rMax∑lp(k,x)|>M(k=0,1,…t;x∈中粒子的函數(shù)值且設(shè)置p(t,x)=0,a(t,x)=0,(1.6)x∈r,計(jì)算sc(t)并按大小排序,保存最好的粒子,則算法停止。M是給定的一個(gè)適當(dāng)大的數(shù),例 Gennum=0;如,M可被取為最大的目標(biāo)函數(shù)值和最小的目標(biāo)函Step2:選擇排在slet( GenNum)最前部的a個(gè)數(shù)值的差。但在實(shí)際應(yīng)用中要確定一個(gè)適當(dāng)?shù)腗粒子;值是困難,必須經(jīng)過多次仔細(xì)的試驗(yàn)。Step3:對(duì)這n個(gè)粒子實(shí)施新的進(jìn)化操作;1.2混沌操作和動(dòng)態(tài)變異概率Step4:修改這n個(gè)粒子的評(píng)價(jià)函數(shù)值,動(dòng)量和新箅法提出新的初始策略和新的變異算子來活動(dòng)量的;加快收斂。數(shù)字實(shí)驗(yàn)顯示IDEA能保持種群多樣Step5:保存最好的粒子和它們的函數(shù)值,修改性,避免過早收斂,并且是快速可靠的slct( GenNum)并排序,1.2.1新初始化策略( GenNum)← Gen Num+1根據(jù)混沌的隨機(jī)性,遍歷性和對(duì)初始條件的敏Step6: P= Pm *(1-Gen Num *0. 01/maxGen)感性等特點(diǎn),我們利用 logistic方程引入新的初始化Step7:如果不停止,回到Step2策略根據(jù)新算法,產(chǎn)生分布均勻的初始種群,在迭1=μx1(1-x1)(H=4(17)代過程中全部粒子都將被選擇參加演化操作,選擇N個(gè)初始化值隨機(jī)產(chǎn)生算子和動(dòng)態(tài)變異算子Pn也使種群均勻分布且避免N∈[0陷入局部最優(yōu)k是優(yōu)化函數(shù)的自變量的個(gè)數(shù),N是種群規(guī)模。2實(shí)驗(yàn)結(jié)果然后利用(1.7)式產(chǎn)生作為演化的混沌種群。在這個(gè)部分里,我們利用IDEA解決一些典型比如,y可以通過將y作為混沌序列的初始的數(shù)值優(yōu)化問題。這些例子經(jīng)常被用于測(cè)試演化值,由(1.7)式反復(fù)迭代得到(k代表迭代的次數(shù))。的算法的性能。在本程序中,我們把種群大小N然后使用下面的映射函數(shù)得到一個(gè)均勻分布定為100,使用第一個(gè)停止準(zhǔn)則。以下的3個(gè)函數(shù)被的種群:x,;=a1+(b-a,)y,x,;∈[馮,b];用驗(yàn)證新算法的效率。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化過程中單個(gè)基因的丟失;太高的變異率會(huì)把CAs這個(gè)函數(shù)有6個(gè)局部最優(yōu)解,并在兩個(gè)不同的變成純隨機(jī)檢索。通常,變異率P。是在0.001左點(diǎn)取得全局最優(yōu)解:(x,x2)=(-0.0898,0.7126)和(x1,x2)=(0.0898,-0.7126)?；镜淖儺惒龠^程如下最大迭代次數(shù)設(shè)置為200,0=10-3。在這些1)使用預(yù)先確定的變異率P決定是否執(zhí)行變?cè)O(shè)置下,我們連續(xù)執(zhí)行程序10次,結(jié)果如下表所異操作示2)將已確定執(zhí)行變異操作的個(gè)體x;根據(jù)下式表映射到區(qū)間[0,1]上:F-min-valX,=(xa)(a1-b,),i=1,2,…k;j-]0316280.0899330712390019995.831833E4(1.9)然后用(7)式得到1,通過(18)式再映射10316280089930.71271021556321314E4回去得到新個(gè)體的x。比較x,和x,保留較優(yōu)1031628|00900712526121973370812E4103162900898420712647018474480823E51.2.3動(dòng)態(tài)的變異率P103162900898420471265522924258演化算法中,交叉操作是主要操作,但是它過1.03162200910380-071234425392.128796E5度的依賴于當(dāng)前的種群情況,容易陷于局部最優(yōu)10316908407126540241869368E4變異操作能有效地?cái)[脫局部最優(yōu)但是由于變異的101890912413913034官目性,它僅僅在演化的早期階段有效,當(dāng)算法開10124100910120181254始接近最優(yōu)解集時(shí),變異操作幾乎不起作用。為了1031638093012594212842116加快收斂速度我們需要?jiǎng)討B(tài)改變變異概率Pn。從表中可看出,兩個(gè)點(diǎn)以等概率取得且我們得利用下列公式來動(dòng)態(tài)改變變異概率到的最小值均小干-1.0316結(jié)果表明,新算法快P= P*(1-Gen Num *0.01/ maxGen速、準(zhǔn)中國(guó)煤化工Gen Num是當(dāng)前演化代數(shù), maxGen是最大代CNMHG數(shù)0.3c09(3丌x1)1.24IDEA算法0.4cos(4x2)+0.753其中-50≤x1,x2≤50。這個(gè)函數(shù)在(0,0)有一3小結(jié)個(gè)全局最優(yōu)解0。結(jié)果如下表所示。本文根據(jù)動(dòng)力學(xué)理論和混沌理論提出新的算表2法?；煦缧蛄袑?duì)于初始值的敏感性一方面使得算F-min-va法很容易跳出局部最優(yōu),另一方面混沌本身的特點(diǎn)01.288464-1484388El1737使得算法克服了純隨機(jī)函數(shù)的局限性,使算法更接8.24822371544426E7973近于自然界中的進(jìn)化過程。新算法提出基于混沌2433083E111.71990E-11861理論的初始化策略和變異策略驅(qū)動(dòng)全體解向最優(yōu)5422493E12-1.251275E-11754解移動(dòng)。新的演化策略可以在演化過程中有效的1067623E-138405404E8128628E8避免陷入局部最優(yōu)。通過3個(gè)典型的數(shù)值優(yōu)化問287683E144274502E8-8564709題證明了新算法的高效性。但是由于IDEA與傳統(tǒng)9860141E64412475E4458819E4675演化算法的區(qū)別,更多相關(guān)的收斂理論有待進(jìn)一步1.245244008190461E7251探討。557667E126091238E94.074859E75742140027E-117395142E12961參考文獻(xiàn):[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è)函數(shù)在點(diǎn)(y,x)=(04400-6.02780)取得全局最小值-32.7179。結(jié)果如下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中國(guó)煤化工編輯郝安林CNMHG