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