一種改進(jìn)的極值動(dòng)力學(xué)優(yōu)化算法

信息技術(shù)農業(yè)閿絡(luò )信息2014年第11期A(yíng)GRICULTURE NETWORK INFORMATION種改進(jìn)的極值動(dòng)力學(xué)優(yōu)化算法張千(重慶交通大學(xué)管理學(xué)院,重慶400074)摘要:針對基本的極值動(dòng)力學(xué)優(yōu)化算法容易陷入局部最優(yōu)解、數值尋優(yōu)能力較差甚至不能尋優(yōu)等缺點(diǎn),提出一種帶柯變異的基于種群的極值動(dòng)力學(xué)優(yōu)化算法。改進(jìn)后的算法不僅具有局部搜索能力還具有全局搜索能力,同時(shí)提高了收斂速度和精確度。鍵詞:極值動(dòng)力學(xué)優(yōu)化算法;種群;柯西變異中圖分類(lèi)號:TP315文獻標識碼:A文章編碼:1672-6251(2014)11-0044-04An Improved OptimizationAlgorithmwith Extremal DynamicsZHANG QianSchool of Management, Chongqing Jiaotong University, Chongqing 400074Abstract: Aization algorithm with extremal dynamics was proposed based on the shortcomings and thinsufficiency of classical extremal optimization algorithm, which was easy to fall into local optimal solution, and had poor ability ofnumerical optimization, sometimes even had no optimal solution. The algorithm was called population-basedextremal optimizationalgorithm with Cauchy mutation. The improved algorithm not onlyhas the local search ability, but also has the global search abilityand the convergence speed and accuracy were improvedKey words: extremal dynamics optimization algorithm; population; Cauchy mutation極值動(dòng)力學(xué)優(yōu)化(EO算法是從統計物理學(xué)基礎本文在實(shí)現基本EO算法的基礎上,針對基本EO上發(fā)展而來(lái)的一種新穎的啟發(fā)式優(yōu)化方法,能有效地算法存在的不足,提出相應的改進(jìn)措施,以提高算法解決復雜的組合優(yōu)化問(wèn)題,近年來(lái)受到了國內外研究的性能;同時(shí)針對典型的復雜測試函數,研究改進(jìn)算學(xué)者越來(lái)越多的關(guān)注。該算法具有易于實(shí)現、局部搜法尋優(yōu)性能,并通過(guò)多次仿真實(shí)驗比較原算法和改進(jìn)索能力強、無(wú)可調參數或可調節參數少等特點(diǎn)。EO算法的結果,證實(shí)算法的有效性和可行性。算法源于復雜系統自組織臨界的思想,算法從優(yōu)化問(wèn)基本極值動(dòng)力學(xué)優(yōu)化算法(EO)的實(shí)現題內部變量之間的聯(lián)系出發(fā),將問(wèn)題本身作為一個(gè)演1.1EO算法的機理化的復雜系統,變量之間的相似性構成了變量之間比EO算法是從BS模型發(fā)展而來(lái),其研究對象為較、競爭、交流的條件、變量在局部尋優(yōu)的過(guò)程中,單一個(gè)體,個(gè)體由組員構成,各個(gè)內部組元之間有著(zhù)驅動(dòng)整個(gè)系統向最優(yōu)解運動(dòng),EO算法具有獨特的視直接或間接的相互作用或關(guān)聯(lián),故由多個(gè)組元構成的角,為算法的研究提供了新的思路。個(gè)體就可以被看作成一個(gè)復雜系統。本文EO算法的EO算法實(shí)現簡(jiǎn)單,算法效率高,應用前景廣闊。研究對象均稱(chēng)為“個(gè)體”,其內部組成元素均稱(chēng)為目前EO算法和其改進(jìn)算法已經(jīng)被成功地應用于求解“組元”。些組合優(yōu)化問(wèn)題,如圖的二分問(wèn)題、圖著(zhù)色、自旋般地,EO算法根據個(gè)體內部組元對個(gè)體目標玻璃問(wèn)題、旅行商問(wèn)題、可滿(mǎn)足問(wèn)題,以及一些工程函數值的貢獻大小來(lái)賦予每個(gè)組元的適應度,適應度優(yōu)化問(wèn)題,與其他智能優(yōu)化算法的比較研究表明,EO最小的組員就是最差組元。在每次迭代中,EO總是算法是解決NP組合優(yōu)化難題的一種有效方法選擇適應度最差的組元及其鄰居來(lái)進(jìn)行隨機的變異,作者簡(jiǎn)介:張千(1987-),男,碩士,研究方向:物流系統分析方法和技術(shù)中國煤化工收稿日期:2014-09-25CNMHG《農業(yè)網(wǎng)絡(luò )信息》2014年第11期信息技術(shù)從而使得所有組元都能協(xié)同進(jìn)化,個(gè)體的適應度不斷1.23適應度函數地得到改善,從而實(shí)現個(gè)體的自我完善。不管個(gè)體初對于只有邊界約束(不含等式約束和不等式約始狀態(tài)如何,在只給定組員總數N的情況下,系統會(huì )束)的問(wèn)題,當前個(gè)體中組元x的適應度入定義為其演化到一種臨界狀態(tài),最終可以找到近似最優(yōu)解或最變異后對整體目標函數值的貢獻大小,即A=OBJ(S優(yōu)解。OBJ(Sbes,其中S是只對x進(jìn)行變異而保持其它組1.2EO算法條件的選擇元不變時(shí)產(chǎn)生的子個(gè)體,OBJS)是S的目標函數值基本EO算法的條件選取有幾個(gè)方面,包括測試OBJ(hest是迄今為止找到的近似最優(yōu)解 Shest所對應函數、乘法函數、適應度函數的選取,針對極小化問(wèn)的目標函數值。對于含有等式約束和不等式約束的問(wèn)題,具體條件選取如下3方面題,所有違背約束條件的懲罰函數值之和,即Q(S)1.2.1測試函數∑□1P(S)應該加入到組元x的適應度函數中去。因從文獻[2]中選擇1個(gè) Benchmark問(wèn)題(g09)作為測試函數。這些試函數對于一般的進(jìn)化算法都是此,當前個(gè)體中組x的適應度函數如下非常難解的。該函數的數學(xué)表達如下A;=OBJ(S)-OBJ(Sbest)+Q(;)(7)測試函數g091.3EO算法的實(shí)現f(x)=(x1-10)2+5(x2-12)2-x24+10x”+7x62+x不是一般性,對于一個(gè)極小化問(wèn)題,基本EO算法流程如下約束條件(1)隨機產(chǎn)生一個(gè)個(gè)體(向量)S=(x1,x…x)g1(x)=-127+2x12+3x24+x3+4x42+5x5≤0設迄今為止找到的最優(yōu)解為S,其目標函數值為CS),則初始S=S,CS)=CS);g2(x)=-282+7x1+3x2+10x32+x4-x5≤0(2)對于當前的個(gè)體S,進(jìn)行如下操作:①分別g2(x)=-196+23x1+x2+6x62-8x7≤0對S中的各個(gè)組員進(jìn)行非均勻算子變異,在對各個(gè)組g4(x)=4x12+x2+3x1x2+2x2+5x-11x員進(jìn)行變異的時(shí)候,保持其他組員不變。②對生成的其中:-10≤x≤10(i=1,2,…7)最優(yōu)解為x*=n個(gè)向量的適應度λ,i∈{1,2…,n}進(jìn)行計算,找出適(23304,19513,-047754.3657,-062441.0381,1.5942)應度最小的那個(gè)向量S。③無(wú)條件接收無(wú)條件地接受最小值為f(x*)=680.6300S=S;④如果當前的目標函數CS)小于迄今為止找到22懲罰函數的最優(yōu)目標函數值C(S)并且懲罰函數的值為0,則令般的,一個(gè)約束連續優(yōu)化問(wèn)題可以如下定S'=S,C(S)=C(S)(3)重復執行步驟(2),直到滿(mǎn)足終止條件(即Optimize f(X),X=(x(2)當前代數達到最大迭代次數,或近似解滿(mǎn)足精度要其中,f(X)為尋優(yōu)函數,X∈S∩F,X∈R"是n維求)決策變量空間,該空間的所有變量都有以下約束(4)返回最優(yōu)解S和最優(yōu)目標函數值CS)。le≤xe≤ue,c=1,…,n基本EO算法的流程見(jiàn)圖1。其中,1和u分別是x的上界和下界。集合F∈由上述基本EO算法的實(shí)現流程可以看出,基本R"定義了可行域,由以下rr≥0個(gè)約束條件來(lái)決定:的EO算法尋優(yōu)時(shí)不需要調節任何參數,而且只有g(shù)(X)≤0.i=1,…,q(4)個(gè)變異算子,沒(méi)有交叉算子,因此,基本的EO算法h1(X=0.i=q+1.…,r(5)操作簡(jiǎn)單,容易實(shí)現,免去了調節參數的麻煩很顯然F∈S;2基于種群的帶柯西變異的極值動(dòng)力學(xué)優(yōu)化通常采用懲罰函數法來(lái)處理約束連續優(yōu)化問(wèn)題。(PEO)算法對于最小化問(wèn)題,當決策向量Ⅹ不滿(mǎn)足第i個(gè)約束條由于基本EO算法總是選擇最差組元來(lái)進(jìn)行變異,件時(shí),其對應的懲罰函P(X)為基本的EO算法較易陷人局部極值點(diǎn)。對基本EO算PO=/max0.g(X),1≤i≤q法進(jìn)行改進(jìn),提中國煤化工題的新算hiOX2,q+l≤i≤r(6)法-帶柯西變異HaCNMHGPopulation《農業(yè)網(wǎng)絡(luò )信息》2014年第11期信息技術(shù)開(kāi)始Gaussian(0, 1)0.35隨機產(chǎn)生一個(gè)向量S=(x1,x2,…,xn),令其為迄今為止的0.30最優(yōu)解即s’=S,C(S)=C(S)025Cauchy(o, 1)0.20分別對S中的各個(gè)組員進(jìn)行非均勻算子變異,變異時(shí)保持其他組員不變,得到n個(gè)向量,計算n個(gè)向量的適應度,找出適應度最小的那個(gè)向量S圖2柯西和高斯分布概率密度函數杏令S=S,若目標函數值C(S)小于迄今為止找到的最優(yōu)目標函數值C(S)并且懲罰函數值為0,則令向上越接近水平軸,變得越緩慢,柯西分布可以看作S=S, C(S)=C(S)是無(wú)限的,這樣基于高斯分布的鄰域函數產(chǎn)生小波動(dòng)的概率較大而產(chǎn)生大波動(dòng)的概率幾乎為零,基于柯西是否滿(mǎn)足終止條件(迭代次數達到最大或滿(mǎn)足精度要求)分別的領(lǐng)域產(chǎn)生小波動(dòng)的能力相對高斯分布有所下降而產(chǎn)生大波動(dòng)的能力增強,這樣經(jīng)過(guò)柯西變異就更有可能跳出局部最小值,從而增強了算法的全局搜索能返回最優(yōu)解S·和最優(yōu)目標函數值C(S')力。因此雖然柯西變異的局部搜索能力不如高斯變異,但柯西變異適合于粗調而且當搜索點(diǎn)離全局最優(yōu)結束點(diǎn)很遠時(shí),采用柯西變異可以獲得更好的結果。綜上圖1基本EO算法流程圖所述:柯西變異算子與高斯變異算子不同之處在于based External Optimization,PEO)。由基本EO算法的柯西變異算子適合全局搜索,高斯變異算子更適合局實(shí)現過(guò)程起我們可以看出,基本EO算法在演化過(guò)程部搜索。因此本章采用引入種群的概念和柯西變異以中只有一個(gè)個(gè)體,沒(méi)有種群。而PEO引人了種群的概使搜索點(diǎn)快速地向全局最優(yōu)點(diǎn)靠攏,從而加快了收斂念即引人較大數量的個(gè)體同時(shí)進(jìn)行演變。另外,本章過(guò)程并且跳出局部最優(yōu)的PEO算法還采用了柯西變異算子以增加其全局搜索般的柯西變異算子的思想是:對于個(gè)體S=(x1能力,使得改進(jìn)后的算法不僅具有局部搜索能力還具ⅹ3…x),對該個(gè)體的柯西變異是根據以下公式進(jìn)行操有全局搜索能力。通過(guò)分別利用基本EO算法和帶柯作西變異的PEO算法求解一個(gè)經(jīng)典的約束連續優(yōu)化問(wèn)S=S+αC(0,1)題,來(lái)證實(shí)其有效性其中:α為控制變異步長(cháng)的常數,C(O,1)是由2.1帶柯西變異的PEO算法條件的選擇t=1的柯西分布函數產(chǎn)生的隨機數。為方便同基本EO算法相比較,本章所介紹的2.2帶柯西變異的PEO算法的實(shí)現PEO算法條件選取除增加了基于種群的柯西變異之外不失一般性,對于一個(gè)約束最小化問(wèn)題,帶柯西與前章所述基本EO算法條件相同變異的PEO算法的具體流程如下維柯西密度函數集中在原點(diǎn)附近,其定義為(1)隨機生成一個(gè)均勻分布的初始種群,種群大小0為比例參數,相應的分布函數定義為F(x)(2對于種群中每一個(gè)個(gè)體S,執行以下操作:①對每個(gè)組員X,j∈{1,…m},實(shí)施柯西變異操作,同由圖2可見(jiàn),柯西分布概率密度函數f(x)類(lèi)似于時(shí)保持其他組元不變,就可以得到n個(gè)子個(gè)體S,j∈高斯分布概率密度函數,其差異主要表現為:柯西分{1,…川;②給每布在垂直方向略小于高斯分布,而柯西分布在水平方A=入=OBJ(S)-OEH中國煤化工試予適應度CNMHG個(gè)體的適應《農業(yè)網(wǎng)絡(luò )信息》2014年第11期信息技術(shù)度進(jìn)行排序,找出具有最差適應度的個(gè)體S,w∈{1,行30次。};④S取代當前個(gè)體S,即S=S,同時(shí),令OBJ3.2實(shí)驗仿真和結果分析(S)=OBJ(S);⑤如果OBJ(S)