第32卷第3期.渤海大學(xué)學(xué)報(自然科學(xué)版)Vol.32，No.32011年9月Joumal of Bohai University( Natural Science Edition)Sep. 2011中心引力優(yōu)化算法楊淋淋,錢偉懿,張琪.(渤海大學(xué)數(shù)理學(xué)院,遼寧錦州121013)摘要:中心引力最優(yōu)化是一種以物理運動學(xué)理論為基礎(chǔ)的新的確定性群體搜索優(yōu)化算法。在重力場中,物體的移動是由物體間的受力和加速度來制定，并把這種物體間的作用運用于粒子運動中。在中心引力優(yōu)化算法中,通過加速度的更新來實現(xiàn)目標(biāo)函數(shù)適應(yīng)值的更新?；谶@種思想,給出一種改進(jìn)中心引力優(yōu)化算法,并用幾個典型的例子對算法進(jìn)行了驗證,結(jié)果表明算法是有效的。關(guān)鍵詞:中心引力最優(yōu)化;萬有引力定律;粒子;最優(yōu)解中圖分類號:0224文獻(xiàn)標(biāo)識碼:A文章編號:1673 - 0569 (2011)03 -0203 -040引言近年來,針對全局優(yōu)化問題的求解出現(xiàn)了許多算法,其中群體智能算法起到極其重要作用,目前群體智能優(yōu)化算法大部分是模擬自然界的一- 些生物的群體行為來構(gòu)造隨機(jī)優(yōu)化算法,比如,模擬生物的進(jìn)化過程而產(chǎn)生的遺傳算法“,螞蟻的尋徑行為提出的蟻群算法(2)(AntcolonyOptimization,ACO),模擬鳥群覓食行為提出的粒子群優(yōu)化算法(3) ( Particle Swarm Optimization, PSO)等。最近, Formato提出了以重力場中的物體間的相互作用為模型的一種新的優(yōu)化算法(4) ,中心引力算法( Central Force Optimization, CFO)。中心引力算法與其它智能優(yōu)化算法不同的是它根據(jù)物理運動學(xué)的模型建立的--個新型的優(yōu)化算法。本文將對中心引力算法進(jìn)行改進(jìn),改進(jìn)的算法主要是把運動的時間看成一- 個隨機(jī)數(shù),這樣改進(jìn)了收斂速度,并用幾個典型的例子對算法進(jìn)行了驗證,結(jié)果表明算法是有效的。1 CFO算法CFO算法由Formato在2007年提出來的,是基于物理運動學(xué)原理構(gòu)造的一種新型優(yōu)化算法,通過初始化若干隨機(jī)質(zhì)點,進(jìn)行迭代，直至找到最優(yōu)解。具體過程如下:在- -個D維搜索空間內(nèi),經(jīng)過j-1次迭代產(chǎn)生的N,個質(zhì)點,- ,,當(dāng)根據(jù)萬有引力定律構(gòu)造加速度公式:a,_.=G ZU(M];. -M,;1) . (M;. -M_.)"-(第一x藝)(1)臺其中:M_-=f(xj),U(z)=.[1,:≥0,,C是一個常數(shù)。新的質(zhì)點產(chǎn)生公式:l0,z<0 .劃=x1+91.101+2041(0中國煤化工(2)MYHCNMHG收稿日期:2011 -01 - 10.基金項目:遼寧省自然科學(xué)基金資助項目( No:20102003 )作者簡介:楊淋淋( 1985 - ),女,渤海大學(xué)碩士研究生,從事智能優(yōu)化算法.最優(yōu)化理論與應(yīng)用研究.204渤海大學(xué)學(xué)報(自然科學(xué)版)第32卷其中:一是質(zhì)點。在j-1次迭代后的速度,取值以=-11, Ot是運動的時間。Formato取司=0,Ol=1。2改進(jìn)的 CFO算法2.1重力 的計算假設(shè)種群有Np個點:x,x,x,.xv,我們把每個點看做是有質(zhì)量的點,每-一點x的質(zhì)量m,定義如下:、. f(x:)-f(xu)m; =expL -nx總(x) -f(xm)J ,i=1,2,,Np,(3)其中:x = argmin{f(x,) |li=1 ,2,3,,N,1是當(dāng)前最好的點，從式(3)中可以看出目標(biāo)函數(shù)值較小的x;質(zhì)量較大;反之,目標(biāo)函數(shù)值較大時,質(zhì)量較小。2.2加速 度的計算我們由物理學(xué)中的運動等式模仿建立加速度公式，物體m;給物體m;的加速度可由下面的公式確定:G(x,-x)-mr,m,>m,. |x-x, |I 2a(i,j) =(4)G(x;-x)||x-x;r,m,≤m,其中:G為重力參數(shù),x;,x;為種群中的點,m; ,m;為點x;,x,對應(yīng)的質(zhì)量。而它們之間的萬有引力可以以物體的各個等效質(zhì)點所受萬有引力之和來計算。所以,點名的加速度:A,= 2 a(i,j)。(5)2.3質(zhì)點位置的更新每一個質(zhì)點都有自己的位置和速度,在重力場中，宇宙中每個天體在其他天體的合力作用下,就有了向某一方運動的趨勢。而移動的位移就由物理學(xué)中的運動學(xué)公式來計算,我們用x:表示當(dāng)前的位置,模擬重力場中的位移公式得到了中心優(yōu)化算法的位移更新公式:x'=x+→Aλ,(6)其中:x表示k代時點x;的位置,入∈(0,1)的隨機(jī)數(shù)。2.4算法流程改進(jìn)的中心引力算法的步驟描述:步驟一:產(chǎn)生初始質(zhì)點群P= {x ,x,x ,計算每個質(zhì)點x;的目標(biāo)函數(shù)值f(x,),i=1,2,-- ,Np,k=0步驟二:確定質(zhì)點群p中的最好點Xxne ,對應(yīng)的函數(shù)值為(xn)。步驟三:利用公式(3)得到各質(zhì)點對應(yīng)的質(zhì)量m。再利用公式(4)和式(5)得到各質(zhì)點的加速度。步驟四:利用公式(6)更新質(zhì)點,并計算更新后質(zhì)點的函數(shù)值。步驟五:是否滿足終止條件,若滿足,則停止迭代,輸出最優(yōu)中國煤化工TYHCNMH G3改進(jìn)的CFO算法結(jié)果分析通過下面例子驗證算法的有效性第3期楊淋淋,錢偉懿,張琪:中心引 力優(yōu)化算法205例1()]Goldstein - Price( GP)f(x,x2)=(1 +(x, +x2+1)2)(19-14(x, +x2)) +3(好+x右) +6x.x2x(30+(2x, -3x2)2)(18 -32x +12x折+48x2 -36x.2 +27名)，其中:-2≤x,x≤2,理論結(jié)果為:xm=(0,-1),f0=3。例2[5) Branin( BR)(x,x2)=(x2-2-xi+5x.-6)2 +10(1-2-)cos(x) +10,4π2π8其中:-5≤x,≤10,0