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