·2·(總796)利用 Alopex改進(jìn)的動(dòng)力學(xué)演化算法2007年文章編號(hào):1003-5850(2007)11-000204利用 Alopex改進(jìn)的動(dòng)力學(xué)演化算法An Dynamical Evolutionary Algorithm Improved by alopex姜欹1樂慶玲(武漢科技大學(xué)計(jì)算機(jī)學(xué)院武漢430081)(2湖北大學(xué)武漢430062)摘要】通過將動(dòng)力學(xué)演化算法( Dynamical Evolutionary Algorithm,DEA)與一種隨機(jī)優(yōu)化方法—— Alopex算法相結(jié)合,提出一種改進(jìn)的動(dòng)力學(xué)演化算法。改進(jìn)的算法改善了動(dòng)力學(xué)演化算法擺脫局部極小點(diǎn)的能力,對典型函數(shù)的測試表明:改進(jìn)算法的全局搜索能力有了顯著提高,特別是對多峰函數(shù)能鈔有效地避免早熟收斂問題【關(guān)鍵詞】動(dòng)力學(xué)演化算法, Alopex,進(jìn)化計(jì)算中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:AABSTRACT A stochastic optimization algorithm is proposed by combining dynamical evolutionary algorithm (DEA)with Alopexalgorithm that is a stochastic optimization method. The proposed algorithm improves the ability of breaking away from localminima. The experiment results demonstrate that the proposed algorithm is superior to the original dynamical evolutionaryKEYWORDS dynamical evolutionary algorithm, Alopex, evolutionary computation從20世紀(jì)90年代初期開始,演化計(jì)算與生物學(xué);群描述成一個(gè)動(dòng)力系統(tǒng),種群中的所有個(gè)體被看成是計(jì)算機(jī)科學(xué)數(shù)學(xué)物理學(xué)以及其他學(xué)科的交叉研究在動(dòng)力學(xué)中相互作用的粒子,它們的宏觀行為可描述成理論和應(yīng)用方面都取得了很大進(jìn)展,但是仍然有一些一個(gè)微分方程系統(tǒng)將這個(gè)系統(tǒng)和算法策略合并在問題尚未解決,首先是過早收斂(在演化早期階段喪失起,定義了演化算法的一個(gè)最優(yōu)控制問題。利用最優(yōu)控種群的多樣性),以及缺乏合適的停止準(zhǔn)則的問題。參制理論中的 Pontryagin最大值原理,對演化算法進(jìn)考文獻(xiàn)[5]中提出了一種基于統(tǒng)計(jì)力學(xué)理論的動(dòng)力學(xué)行了最優(yōu)軌線分析,提出了演化算法的最優(yōu)軌線理論,演化算法(DEA)。它把種群看作一個(gè)動(dòng)力學(xué)系統(tǒng),把定義了一個(gè)起核心作用的 Hamilton函數(shù)。種群中的個(gè)體看作是粒子,系統(tǒng)中每個(gè)粒子有一個(gè)動(dòng)設(shè)有一個(gè)最小值優(yōu)化問題量P(,x)和一個(gè)活動(dòng)量a(t,xi)以模擬分子運(yùn)動(dòng)這ninf(x)(x∈s)兩個(gè)參數(shù)聯(lián)合控制選擇操作并驅(qū)使粒子在解空間內(nèi)移f(x)是目標(biāo)函數(shù),S是它的可行的解的集合動(dòng)搜尋,提出了基于最優(yōu)控制論的兩個(gè)停止準(zhǔn)則來測在DEA中,將N個(gè)已編碼的解類比為動(dòng)力學(xué)系試系統(tǒng)是否在統(tǒng)計(jì)力學(xué)意義上取得它的最低的能量或統(tǒng)中的粒子x1,x2,x3,…,x。演化算法中的演化代數(shù)者最大的熵的狀態(tài)。在此記為時(shí)間L。下面介紹一下動(dòng)力學(xué)演化算法中的盡管DEA已被成功地應(yīng)用于各種優(yōu)化問題及實(shí)相關(guān)概念際工程領(lǐng)域但是當(dāng)面對復(fù)雜的優(yōu)化問題,尤其是多粒子x在t時(shí)刻的動(dòng)量p(t,x)被定義為峰、多極值的多模態(tài)函數(shù)優(yōu)化問題時(shí),由于目標(biāo)問題存p(, ti)=f(u,xi)-f(t-1,x在著眾多的局部極值因此不可避免地存在著早熟、收∫(t,x)是在t時(shí)刻時(shí)粒子x的目標(biāo)函數(shù)值斂速度慢等缺陷。為提高動(dòng)力學(xué)演化算法對復(fù)雜問題定義了一個(gè)活動(dòng)量a(t,x),如果在t時(shí)刻x被選全面最優(yōu)解的探測能力,本文提出了將DEA與擇參加進(jìn)化操作,則粒子x在t時(shí)刻的活動(dòng)量被定義Alopex相結(jié)合的思想,并設(shè)計(jì)和實(shí)現(xiàn)了算法。通過實(shí)為a(,x)=a(-1,xz)+1驗(yàn)證明,這一方法能夠提高DEA的全局收斂性能否則保持不變綜合這兩個(gè)參數(shù)我們定義了一個(gè)新的選擇策略1動(dòng)力學(xué)演化算法(DEA)sla(t,x)=λ∑|p(k,x)1+(1-x)a(,x)動(dòng)力學(xué)演化算法(DEA)最初是由武漢大學(xué)李元(k=0,1,…,t)(4香教授于2002年提出,其基本思想是將演化算法的種中國煤化工條件的比重。在選代CNMHG2007-08-27收到,2007-09-25改回·基金項(xiàng)目:武漢科技大學(xué)青年基金資助項(xiàng)目(No.2006XY22)“作者簡介:姜毅,男1978年生,講師在讀博士,研究方向:智能計(jì)算。第20卷第11期電腦開發(fā)與應(yīng)用總797)·3·過程中,slct(t,x)(=1,2,…,N)被按照從小到大的P: (n)順序排序。DEA的選擇策略是:一個(gè)粒子的動(dòng)量的積1+e+4, 7T累變化量越小,以往被選擇的次數(shù)越少,在本次迭代中△(n)=[x;(n-1)-x(n-2)]它被選擇的可能性越大因此在選代的過程中,全部粒[f(n-1)-f(n-2)]子都將可能被選擇,即DEA的選擇策略將驅(qū)動(dòng)系統(tǒng)式中:f(n)—一目標(biāo)函數(shù)在第n次的取值;x內(nèi)的全部粒子運(yùn)動(dòng)搜尋最優(yōu)解,正如粒子時(shí)刻到處移(n)—目標(biāo)函數(shù)的第個(gè)自變量在第n次迭代中的動(dòng)一樣。也正是因?yàn)檫@一點(diǎn)我們將這種新算法稱為動(dòng)取值;3(n)和內(nèi)1(n)—第n次迭代中的自變量x隨力演化的算法。另外,DEA還根據(jù)動(dòng)量提出兩條新的機(jī)行走的步長和向增加方向行走的概率n1—隨停止準(zhǔn)則。第一條準(zhǔn)則是如果機(jī)數(shù);戶(n)和p(n)—正向變化概率和反向變化概∑p(,x)|<∈(i=1,2率。式(9)中正負(fù)號(hào)的選取與實(shí)際問題有關(guān),正號(hào)使問題極小化,負(fù)號(hào)使問題極大化。實(shí)驗(yàn)表明,為保證算法演化停止,這里是一個(gè)事先給定的誤差準(zhǔn)許值。從統(tǒng)計(jì)力學(xué)的觀點(diǎn)看它意味著全部粒子移動(dòng)和消散的收斂速度,需合理選擇步長和控制參數(shù),一般b初能量使動(dòng)態(tài)系統(tǒng)取得它的能量最低狀態(tài)。始值的大小根據(jù)變量變化的范圍來確定,通常取變量變化范圍的幾百分之一或更小,改進(jìn)的 Alopex算法第二個(gè)準(zhǔn)則是如果的收斂速度對初始值的依賴性有所降低Max∑|p(k,x)|>M(k=0.1,…,t,x∈S)(6)則算法停止,M是給定的—個(gè)適當(dāng)大的數(shù),例如,3基于 Alopex改進(jìn)的動(dòng)力學(xué)演化算法M可被取為最大的目標(biāo)函數(shù)值和最小的目標(biāo)函數(shù)值為解決大規(guī)模優(yōu)化問題,充分利用動(dòng)力學(xué)演化算的差但在實(shí)際應(yīng)用中要確定一個(gè)適當(dāng)?shù)腗值是困難法與 Alopex算法的優(yōu)越性,本文提出了將改進(jìn)的的,必須經(jīng)過多次試驗(yàn)。Alopex算法加人動(dòng)力學(xué)演化算法的改進(jìn)算法,其基本2改進(jìn)的 Alopex算法思想是:按照動(dòng)力學(xué)演化算法對粒子迭代一次后,計(jì)算粒子適應(yīng)度值(目標(biāo)函數(shù))的變化,根據(jù)變量的變化和Alopex算法是一種啟發(fā)式與隨機(jī)優(yōu)化相結(jié)合的目標(biāo)函數(shù)的變化,確定粒子是否繼續(xù)按此改變方向進(jìn)算法,它從前次自變量變化對目標(biāo)函數(shù)產(chǎn)生的影響中行進(jìn)化。進(jìn)行改進(jìn)的 Alopex操作,即給予新個(gè)體一定得到啟發(fā),用過程控制參數(shù)控制行走方向的概率,利用的“噪聲”使其具有一定的爬坡能力,有利于動(dòng)力學(xué)算噪聲”來擺脫局部最優(yōu)解使算法具有一定的爬坡能法在搜索中跳出局部極值同時(shí)又能根據(jù)目標(biāo)函數(shù)的力在一定程度上既克服了傳統(tǒng)啟發(fā)式算法易陷入局變化加速算法的收斂。在動(dòng)力學(xué)演化算法進(jìn)行到一定部最優(yōu)的缺陷又克服了模擬退火算法從完全隨機(jī)搜代數(shù)后,種群中近似最優(yōu)解占據(jù)絕大部分,使得粒子的索到梯度搜索極為緩慢的不足。它不要求目標(biāo)函數(shù)可更新很難跳出局部最優(yōu),致使收斂過程放慢計(jì)算速度微且能保證求出的解滿足一定的精度特點(diǎn)是具有快低。為了保證算法的全局收斂性,需要維持解群中個(gè)體速的搜索能力。 Alopex算法在選代過程中,各個(gè)自變的多樣性避免有效信息的丟失。另一方面,為了加快量不僅可以向正向變化,而且能以一定的概率向反向收斂速度,就要使解群較快地向最優(yōu)狀態(tài)轉(zhuǎn)移,容易陷變化,其目的是使算法跳出局部最優(yōu)值。從實(shí)驗(yàn)得知,入局部極值點(diǎn)。在動(dòng)力學(xué)演化算法中引進(jìn)改進(jìn)的為得到全局最優(yōu)解,自變量正向變化的步長應(yīng)小一些, Alopex算法后,由于它在產(chǎn)生子代時(shí)可根據(jù)粒子的信避免由于步長過大錯(cuò)過全局最優(yōu)值;而反向變化步長息產(chǎn)生一定的“噪音”,使子代與父代粒子間有一定的應(yīng)大一些,因?yàn)榉聪蜃兓哪康氖鞘鼓繕?biāo)函數(shù)擺脫局差異,這樣會(huì)使粒子群具有一定的多樣性使算法有部最優(yōu)值;若反向步長過小,目標(biāo)函數(shù)跳出局部最優(yōu)的的爬坡能力,收斂到全局最優(yōu)。另外, Alopex算法在搜概率不大,由此可能會(huì)導(dǎo)致目標(biāo)函數(shù)在某個(gè)局部最優(yōu)索過程中利用前次自變量及其函數(shù)值的變化信息將有解的一側(cè)來回?cái)[動(dòng),不能跳出局部最優(yōu)。改進(jìn)的模型利于縮短搜索時(shí)間,其“噪聲”也隨著收斂過程的進(jìn)行為逐漸減小,有科干篁法血全局最優(yōu)前進(jìn)x(n)=x(n-1)+6,(n)(7)中國煤化工b,p(n)=p(n)∩p(n)≥rCNMHG2,…,x};②粒子的8,1-p(n)=p(n)∩p(n)<(8)適應(yīng)值,并保留最好的粒子③設(shè)置初始動(dòng)量,活動(dòng)量(n)-,p(n)=p(n)∩p(n)≥r1為:p(t,x)=0,a(t,x)=0,x∈X;④令t=計(jì)+1⑤按r0;,1-p(n)=p',(n)∩p(n)