用于函數優(yōu)化的最大引力優(yōu)化算法

第23卷第5期模式識別與人工智能Vol.23 No.52010年10月.PR&AIOct 2010用于函數優(yōu)化的最大引力優(yōu)化算法*金林鵬李均利魏平陳剛(寧波大學(xué)信息科學(xué)與工程學(xué)院寧波315211)摘要提出一種基于牛頓萬(wàn) 有引力定理的函數優(yōu)化方法一最大引力優(yōu)化算法. 該算法通過(guò)“引力分組"和“引力淘汰”過(guò)程更新搜索體.文中給出4個(gè)引理來(lái)描述算法的數學(xué)基礎，同時(shí)也給出算法的收斂性證明.此外還對該算法進(jìn)行改進(jìn).最后與粒子群算法、差分算法、郭濤算法進(jìn)行比較,數值結果顯示該算法在解決連續函數優(yōu)化問(wèn)題具有較高的性能.關(guān)鍵詞函數優(yōu)化,最大引力優(yōu)化算法( MG0A) ,模擬進(jìn)化計算,萬(wàn)有引力中圖法分類(lèi)號TP311; TP 181Maximal Gravitation Optimization Algorithm for Function OptimizationJIN Lin-Peng, L Jun-Li, WEI Ping, CHEN Gang(College of Information Science and Enginering, Ningbo University, Ningbo 315211)ABSTRACTA global function optimization algorithm based on Newtons law of universal gravitation is proposed,namely maximal gravitation optimization algorithm ( MG0A). The search agents are updated through theprocesses of gravitational clustering and gravitational elimination, which are two main strategies inMG0A. Four lemmas are provided to describe the mathematical foundation, and the convergence ofMGOA is strictly proved. Furthermore, the proposed algorithm is improved. The experimental resultshows MGOA has good performance in solving continuous function optimization problems, compared withsome well-known heuristic search methods such as Particle Swarm Optimization, Differential Evolution,and Guo Tao algorithm.Key Words Function Optimization, Maximal Gravitation Optimization Algorithm ( MGOA) , SimulatedEvolution Computation, Universal Gravitation中國煤化工，*國家自然科學(xué)基金重點(diǎn)項目(No.60832003) 、浙江省自然科學(xué)基金項科學(xué)基金項目(No.2009 A610089)和寧大學(xué)王寬誠基金項目資助MYHCNMHG收稿日期:2009 -04 - 13;修回日期:2010-04 -09作者簡(jiǎn)介金林鵬,男,1984 年生，碩士研究生,主要研究方向為最優(yōu)化方法、演化計算. E-mail: kinis1984@ 163. com.李均利，男,1972年生，研究員，博士生導師，主要研究方向為演化計算、醫學(xué)圖像處理、視頻處理等.魏平，男,1978年生，博士,主要研究方向為演化計算醫學(xué)圖像處理等.陳剛,男,1963年生，博士,教授，主要研究方向為系統仿真非線(xiàn)性系統分析等。654模式識別與人工智能23卷1引言Kang等[I5]提出的基于引力的粒子群算法(ParticleSwarm Optimization Based on Gravitation Field Model,優(yōu)化是一個(gè)古老的問(wèn)題，追求最優(yōu)目標一直是CPSO) ,則是在原粒子群算法的基礎上加上由引力人類(lèi)的理想,長(cháng)期以來(lái).人們對最優(yōu)化問(wèn)題進(jìn)行不斷產(chǎn)生的加速度項.的探討和研究,發(fā)展了許多確定有效的優(yōu)化方法,如以上四種算法均是基于“位置+位移量”計算牛頓法、共軛梯度法、單純形法等.然而很多優(yōu)化問(wèn)模型(同粒子群算法類(lèi)似),受萬(wàn)有引力公式啟發(fā),題的函數性質(zhì)十分復雜,解析性質(zhì)不清晰,甚至可能模擬動(dòng)態(tài)的物理運動(dòng)過(guò)程.唯--不同的是他們的更沒(méi)有具體的函數表達式.傳統優(yōu)化算法在求解這些新公式,問(wèn)題,無(wú)論是在計算速度、收斂性、初值敏感性等方本文提出的最大引力優(yōu)化算法( Maximal Gravi-面都遠不能滿(mǎn)足要求.20世紀50年代中期出現仿tation Optimization Algorithm, MGOA)亦是基于牛頓生學(xué)學(xué)科,人們很快從生物進(jìn)化的機理和仿生學(xué)中引力公式,不同的是,1)該算法不是模擬一個(gè)動(dòng)態(tài).得到啟示,提出多種求解優(yōu)化問(wèn)題的模擬進(jìn)化方法,的物理運動(dòng)過(guò)程,而是模擬一個(gè)物理現象:在-一個(gè)有如遺傳算法"、模擬退火算法[2]、免疫算法']、蟻群很多物體的空間中,最大引力值存在于質(zhì)量最大物算法[4]、粒子群算法'5]、差分算法[°1等,并取得巨大體的附近;2)其計算所得的引力僅僅是一個(gè)測度,成功.并不是真正意義的引力,同時(shí)計算引力測度是為后對于引力模擬局部搜索( Gravitational Emulation來(lái)“引力分組過(guò)程”提供依據;3)其計算模型是基于Local Search, GELS)"的研究,最初概念性框架是“ 交叉變異"(同遺傳算法類(lèi)似),而不是基于“位置由Voudouris 和Tsang 于1995年提出，Webster[8])發(fā)+位移量”;4)該算法從確定交叉、變異的個(gè)體到確展了它.該算法可形象描述為一個(gè)在介質(zhì)上滾動(dòng)的定淘汰個(gè)體,均是基于萬(wàn)有引力現象,同遺傳算法球,介質(zhì)上有很多的坑,坑有深有淺球在滾動(dòng)過(guò)程“優(yōu)勝劣汰"思想有著(zhù)本質(zhì)的區別.中由于介質(zhì)摩擦力而逐漸失去動(dòng)力.如果該球正滾進(jìn)坑里,它就獲得了動(dòng)力;如果該球正滾出坑,它將2基于牛頓引力公式的最大引力失去動(dòng)力.算法的理念是由于引力的影響,球最終會(huì )優(yōu)化算法停留在某個(gè)坑里. Balachandar91 在Webster 的基礎上提出隨機引力模擬搜索( Randomized Gravitational2.1基本概念Emulation Search, RGES)算法,克服其收斂速度慢、解的質(zhì)量不高等問(wèn)題,使其求解能力大大提高.這3萬(wàn)有引力是兩個(gè)具有質(zhì)量的物體間相互吸引的種引力模擬搜索算法用于求解旅行商向題(Trave-作用,存在于任何有質(zhì)量的物體之間.兩個(gè)物體間的ling Salesman Problem, TSP)等組合優(yōu)化問(wèn)題,求解引力大小,跟它們之間質(zhì)量的乘積成正比，跟它們的機制基于離散的路徑信息，與本文提出的用于函數距離的平方成反比,用公式表示為優(yōu)化的最大引力算法關(guān)系不大,故這里不具體展開(kāi)F=G",(1)說(shuō)明.Hsiao[10]提出的空間引力優(yōu)化(SpaceGravita-其中,C = 6.672為引力常數,m,、m2分別為兩物體tional Optimization , SGO)是基于愛(ài)因斯坦相對論和的質(zhì)量,r是它們之間的距離.牛頓引力公式,模擬行星群在宇宙中漂移以找到最考慮求解無(wú)約束函數優(yōu)化問(wèn)題:Z = maxf(X),大質(zhì)量的行星個(gè)體,時(shí)空幾何的變化導致行星加速或減速,從而使行星漂移.Chuang["]提出的累積輻搜索空間D = {X|l≤x;≤u,i = 1,2,.*,n}，射優(yōu)化( Integrated Radiation Optimization , IRO),是X =(x,",x,)",4,u;(1≤i≤n)分別為每一基于“一個(gè)置身于引力場(chǎng)的行星的運動(dòng)是由空間中維取值的上下邊界f(X)為目標函數.將萬(wàn)有引力所有其他行星輻射引力波,共同作用的情況"這一用于函數優(yōu)化問(wèn)題，做法是將搜索空間D中的每個(gè)事實(shí)而設計的. Rashedil2-14)提出的引力搜索算法點(diǎn)看作中國煤化工i量m分別為(Gravitational Search Agorihm, GSA),通過(guò)計算每CNMHG(2)個(gè)粒子與其他所有粒子之間的引力值,并將所有這m' = nV(A)些引力值以隨機加權方式計算總和,求得該粒子所h(x)為-維尺度變換函數,滿(mǎn)足對Vx∈(-∞,受到的引力,進(jìn)而求得加速度,再更新速度和位置.+∞),h(x) > 0,并且嚴格單調遞增為了降低計算5期金林鵬等:用于 函數優(yōu)化的最大引力優(yōu)化算法655復雜度,將搜索空間D中任兩個(gè)點(diǎn)間的引力簡(jiǎn)化為成新物體C.顯然P;的個(gè)數決定新物體C的個(gè)數,Fr.2 =h(f(X)) . h((X2))3)故共生成n個(gè)新物體C.記新物體群ζ= {C, 1≤1.2 + K。i≤n},那么其中,X,X2 e D,r.2 為距離測度,Ko為很小的數,C=(U, {F.(P.)}) U(_ u{F_(P:)})防止式(3)中分母為零.雖然形式變了,但本質(zhì)上跟式(1)是一致的,因為我們需要的只是兩點(diǎn)間的引iter = iter + 1.力測度,而不是真正的引力值.step4對每個(gè)新物體C(1≤i≤n), 由于每為說(shuō)明方便,下面提到的物體適應值其實(shí)就是個(gè)浮動(dòng)物體與其所選擇的參考物體之間都有距離測物體的質(zhì)量,或者說(shuō)是目標函數值的某-尺度變換度,距離測度最小的一對物體中質(zhì)量小的物體即為函數值要淘汰的物體,記為E,其中2.2算法描述r咖= min(yj, 1≤j≤n2)在最大引力優(yōu)化算法(MC0A)中涉及到參考lhk = min({j|rqJ =喇，1≤j≤n})物體群R、浮動(dòng)物體群N(兩者統稱(chēng)為群體RNV)和新fRm，ifR(m) ≤Nu(m)物體群C,記R(X)和R(m)分別為參考物體R的E: =lNx，otherwise位置和質(zhì)量,N,(X)和N,(m)分別為浮動(dòng)物體N;的位置和質(zhì)量, C;(X)和C;(m)分別為新物體C;的位如果C(m) > E(m) ,C;就取代E,再用算法流程置和質(zhì)量,RN,(X)和RN,(m)分別為群體中物體中step2方法更新s;值;否則不變RN,的位置和質(zhì)量. MGOA的計算步驟如下.step5若連 續IterThreshold迭代次數內均沒(méi)step 1隨機產(chǎn)生參考物體群R和浮動(dòng)物體群有變異發(fā)生,則通過(guò)變異算子生成新物體C. ,更新,其中方法同step 4.R= {R,1≤i≤n}step6 若適應值最大的max{m,n2} +1個(gè)物W= {N,1≤j≤n}體,其平均適應值沒(méi)有增加,則令iter = iter -1.若滿(mǎn)足終止條件則停機，否則將這n + n2個(gè)物體重新令iter =0.step2計算每個(gè)參考物體R(1 ≤i≤mn)和隨機選定為參考物體和浮動(dòng)物體,轉step 2.每個(gè)浮動(dòng)物體N(1≤j≤n)之間的引力測度Fj2.3算 法說(shuō)明和距離測度r.s(距離測度可以是1-范數2-范數、F-2.3.1物理意義范數或模糊距離測度等):由式(1)可知,引力值較大的時(shí)候,要么有質(zhì)量τj= |R;(X) - N(X) I ,較大的物體,要么兩物體間的距離較小由于本算法R.(m) x N,(m)在每次迭代過(guò)程中淘汰引力相對較大并且距離測度rj+ Ko最小的一-對物體中質(zhì)量小的物體，這就保證在引力每個(gè)浮動(dòng)物體N,(1≤j≤n)選擇和其引力最大的相對較大的物體附近往往存在質(zhì)量大的物體.正是參考物體r,其中基于這一思想,構造出最大引力優(yōu)化算法從函數優(yōu)pF7 = max(Fij, 1≤i≤n)化角度來(lái)說(shuō),這樣--種淘汰策略有利用保持種群的ls, = min({i|Fj= F",1≤i≤n})多樣性.step3 記P= {P,1≤i≤n},其中P;為參2.3.2模型說(shuō)明考物體R,和所有選擇它的浮動(dòng)物體組成的集合,最大引力優(yōu)化算法同遺傳算法類(lèi)似，是通過(guò)交P: = {R} U {N|;j = i,1≤j≤n}.叉和變異來(lái)更新群體，而不是像粒子群算法通過(guò)位對于每個(gè)參考物體R,可能至少有一個(gè)浮動(dòng)物體選置和位移量、差分算法通過(guò)差向量,來(lái)更新群體.不擇它,也可能沒(méi)有浮動(dòng)物體選擇它這樣P:就分為過(guò)需要說(shuō)明的是,遺傳算法的設計理念是基于生物兩類(lèi),記p"和P"分別由這兩類(lèi)P;所組成的集合:進(jìn)化的“優(yōu)勝劣汰”思想,通過(guò)淘汰群體中差的個(gè): ,優(yōu)秀的個(gè)體通過(guò)P" ={R|{N|s =i,1≤j≤n}≠0,1≤i≤n}雜交YH中國煤化工個(gè)體遺傳算法的=P-p°這種讓CNMHG在數值實(shí)驗中也.設F。為鄰域交叉算子,F.為變異算子,對P"中的取得很大的成功不過(guò)遺傳算法也存在不足,如算法元素使用F.算子,對P"中的元素使用F算子,生不穩定、早熟等.而最大引力優(yōu)化算法的設計理念是656模式識別與人工智能23卷基于- -種萬(wàn)有引力現象,核心思想是“引力分組”和a個(gè)物體那么只要(),2.,"",入.) = (1,0,.",0)，“引力淘汰”機制,而這兩點(diǎn)均是通過(guò)萬(wàn)有引力這一λ;是RN。(X)的構造系數,就可再次搜索到最優(yōu)物普遍現象而導出的,跟遺傳算法的“優(yōu)勝劣汰”思想體不妨設浮點(diǎn)數編碼精度為e,Flim中(入1,λz,有著(zhù)質(zhì)的區別.應該這么說(shuō),遺傳算法和最大引力優(yōu)..,入.) 的取值有V.m種,那么V,ia必然小于化算法是設計理念的區別,至于交叉算子和變異算([(u"-l")/e])* ,因為Eλ= 1還制約著(zhù)(A，子,兩者可互相借鑒2.3.3鄰域交叉算子 F.的選取Az,.. ,入。)的取值,由此可知V,iwn是有限數.當RN。.根據最大引力優(yōu)化算法的構造思想,任何鄰域是參考物體時(shí),情況類(lèi)似，相應參數不妨設為V.,uw,交叉算子均可適用下面介紹一種鄰域交叉算子,最于是有早見(jiàn)于郭濤算法[06.。設Xx,X,.",X,∈R", \\z,p{r"(RN)≈麗uE...∈R,則2Pr.一+p, Pr,umn一>0, (4)[X'= 2\X其中∈E*.需要說(shuō)明的是，在實(shí)際演化計算中,由非最優(yōu)物體搜索到最優(yōu)物體的可能是存在l2λ:=1,l°≤λ;≤u° ,I" <0,u' >1的,故實(shí)際搜索到最優(yōu)物體的概率要比式(4)右邊.其中,I"、u"為λ;取值的上下界,我們將其記為的式子要大,而當z > 1或多最優(yōu)值問(wèn)題時(shí),其概率rLiner.就更大. Vj.V,urn P.iw是變量,每次迭代可能都不一樣,但不論怎么變換,式(4)總是成立的. 證畢3最大引力優(yōu)化算法的數學(xué)基礎注“[x]"表示對x向上取整.那么由引理1我們能不能得到結論:及收斂性證明p{T(RN)≈RN*t!} > 0.我們有如下引理.引理2對于單最優(yōu)值問(wèn)題而言 ,有定義1若群體RN 有z(z≥0)個(gè)物體是全局p{T(RN)→R++}最優(yōu)物體(這里X*和m*分別表示全局[>0，1≤z≤max{nj,n2|最優(yōu)物體的位置和質(zhì)量) ,則記為RN'(對多最優(yōu)值=0，z > max{n,n2} .問(wèn)題,X”不唯- -).證明對于單最優(yōu)值問(wèn)題而言,任意兩個(gè)最優(yōu)定義2記 T,為引力分組算子,對應算法流程物體之間的距離測度是最小的MGOA中每個(gè)浮動(dòng)中step 2,T。為構造算子,對應算法流程中step 3,T.物體與其所選擇的參考物體之間都有一個(gè)距離測為淘汰更新算子,對應算法流程中step 4.我們分別度,而淘汰更新算子T.淘汰的是距離測度最小的一記操作算子T和T'為T(mén)=ToTq°T,T"= Tp° T,對物體中質(zhì)量小的物體.若參考物體群和浮動(dòng)物體引理1 設最大引力優(yōu)化算法某- -次迭代,群群中都有最優(yōu)物體,由于最優(yōu)物體間引力測度最大，體為RN(z≥1),為全局最優(yōu)物體,則相互選擇,并且距離測度最小,故淘汰更新算子T,p{T'(RN)→RN uC*} >0,淘汰的是一一個(gè)最優(yōu)物體由于搜索到的新物體其適其中,∈C,"→"表示“演化得到”的應值不可能比最優(yōu)物體大,故這種情況下群體中就意思.不可能再增加最優(yōu)物體.證明對于RN(z≥ 1) ,不妨設物體RN。是最要證明p{T(RN)≈RN*#} > 0,首先要保證能優(yōu)物體,它成為浮動(dòng)物體的概率p; =n2/(n, +n2),搜索到最優(yōu)物體,其次淘汰物體能被最優(yōu)物體替換成為參考物體的概率p, = n/(n| + n2) ,并設它成掉(由前面分析可知,只要群體RN中最優(yōu)物體不同為參考物體后被浮動(dòng)物體選中的概率為P.,uan,則時(shí)出現在參考物體群和浮動(dòng)物體群,就能保證淘汰MGOA通過(guò)鄰域交叉算子在RN。附近搜索的概率為物體被替換).Ppr+p, xp.ur這里以Flunmr為例給出證明,其他F?？?概率,由引理1可類(lèi)似證明,因為任何鄰域交叉算子的一個(gè)共同特點(diǎn)知Pa中國煤化工浮動(dòng)物體群不同是在給定物體的附近搜索時(shí)有YHCNMHG當RN。是浮動(dòng)物體時(shí),必然選擇某-參考物體,p{T(RN)≈Ri'*} =Pandeu .pm.(5)而其它浮動(dòng)物體也可能選擇它,不妨設該組一共有當1≤z≤max{n,nz}時(shí),至少存在一種排列,金林鵬等:用于函數優(yōu)化的最大引力優(yōu)化算法657使參考物體群和浮動(dòng)物體群不同時(shí)出現最優(yōu)物體,群體RN通過(guò)多物體交叉方式和變異方式生成新物故Pm >0,式(5)大于0;當z> max{n,nri時(shí),不論體的概率這樣排列，參考物體和浮動(dòng)物體都至少有一一個(gè)是最引理4最大引力優(yōu)化算法的交叉概率p。 和變優(yōu)物體,故pm = 0,式(5)等于0.結論成立證畢異概率pm均大于0.相比單最優(yōu)值問(wèn)題而言,多最優(yōu)值問(wèn)題中“任證明由引理3可知,MGOA在-一次迭代中多意兩個(gè)最優(yōu)物體之間的距離測度是最小的”這一結物體交叉至少發(fā)生- -次,可知p。> 0.不過(guò)MGOA是論將不再成立.不過(guò)當1≤z≤max{n,n}時(shí),式不能保證變異- -定 發(fā)生的,但由于算法流程中step 5(5)大于零的;而當z > max{n,m}時(shí),若群體RN的存在,可知pm > 0.故結論成立.證畢中max{n,n2} + 1個(gè)物體都是同一位置的最優(yōu)物由文獻[17]可知變異算子可搜索到整個(gè)解空體,式(5)等于零(以上證明同單最優(yōu)值問(wèn)題,即引間D,而MGOA中pm>0,故MGOA能搜索到整個(gè)解理2).若不存在max{n,n2}{ + 1個(gè)物體均是同- -位空間.置的最優(yōu)物體,那么總可以找到一種排列使得同一定義4設有nm 個(gè)個(gè)體的群體RN ,其適應值最位置的最優(yōu)物體不同時(shí)出現在參考物體群和浮動(dòng)物大的n.個(gè)個(gè)體組成主群RN ,記W(RNx ).為1時(shí)刻體群,而這就給其他非最優(yōu)物體被替換提供了條件.主群中所有個(gè)體的平均適應值,Q為平均適應值的不過(guò)這些非最優(yōu)物體能不能更新為最優(yōu)物體,跟優(yōu)集合,若算法t時(shí)刻的W(RN%),滿(mǎn)足化問(wèn)題和迭代情況有關(guān)lim W(RN"), =f'，f'∈Q由以上分析可知,最大引力優(yōu)化算法求解多最優(yōu)值問(wèn)題時(shí),運行- -次可能只找到1個(gè),也可能是2則稱(chēng)算法收斂到f' .個(gè)或更多.另外,引理2及多最優(yōu)值問(wèn)題的分析也解定理1浮點(diǎn)編碼下 的最大引力優(yōu)化算法,所釋算法step 6中為什么是適應值最大的max{n; ,n2}有可能的RN所組成的集合是有限集,平均適應值集+1個(gè)物體的平均適應值,而不是整個(gè)群體的平均適合Q也是有限集.應值.我們記RN,(X) = (.xe2x.....)，,引理3不考 慮step 5,最大引力優(yōu)化算法在一k = 1 ,2,.",nm,則我們有1≤x≤u,1≤i≤n.次迭代中多物體交叉至少發(fā)生一次.當n =1時(shí),變采用浮點(diǎn)編碼,由于編碼精度總是有限的,不妨設為異不發(fā)生;當n > n2時(shí),在-一次迭代中變異至少發(fā)&,則%,的取值情況有[(4; - l,)/e] 種可能，生n-n次;當1 n2 時(shí),在一次迭代中至少有8(F5) =jO,n-n個(gè)參考物體沒(méi)有被浮動(dòng)物體所選擇,故變異l2M+1-5-石，了≠后至少發(fā)生-n次.當1 m中國煤化工≠f時(shí)，時(shí),變異的分量相對多-點(diǎn),n,》n近于隨機搜索8(當n≤n時(shí),多物體交叉的分量相對多一點(diǎn),幾=1TYHCNMH G(2M+1-萬(wàn)-萬(wàn))沒(méi)有變異發(fā)生.= (2M+1--f3) +(2M+1 -f一石)定義3交叉概率p。 和變異概率Pm分別表示= 8(fiJ5) +8(rJ5),658 .模式識別與人工智能23卷當凱=無(wú)或，=五時(shí)，顯然均是最優(yōu)物體.證畢8(元后) = 8(5) +8(2J5)，由此可知8是-一個(gè)度量.證畢4 n和n經(jīng)驗取值的研究定理3 (Q ,8)構成完備的度量空間.證明首先,平均適應值集合Q非空,由定理2最大引力優(yōu)化算法中n、m的取值直接影響其知δ是一個(gè)度量,因而(Q,8)構成度量空間.又由定理優(yōu)化性能,引理3已從理論上給出分析.下面我們以1知，集合Q是有限集,因而(Q,8)中的任意CauchyKowalik Problem( KL)函數為例,從實(shí)際計算性能序列都收斂,從而(Q ,8)構成完備的度量空間.證畢分析一下.Banach壓縮映射定理設(Q,8) 為完備度量fxa=(a.--x(1 + x26.)空間,g: Q→Q為一壓縮映射,則g有且僅有一個(gè)不(1 +xb, +xob)動(dòng)點(diǎn)f*∈Q,并且對于Vf∈Q滿(mǎn)足劃,在，x,如e [0,0.42], .[a;] = [0.1957 ,0. 1947 ,0. 1735 ,0. 1600 ,0. 0844,于= lim g'()，0.0627 ,0. 0456 ,0. 0342 ,0. 0323 ,0.0235,其中,g*(f%) =f,g'(f%) = g(g'(6)).0. 0246],定理4最大引力優(yōu)化算法依定 義.4收斂到全[b,] = [0.25 ,0.50,1 ,00,2. 00 ,4.00,6.00,8.00,局最優(yōu)10.0,12. 0,14. 0,16. 0],證明最大引力優(yōu)化算法將一個(gè)狀態(tài)的群體(x,z,x,x)≈(0. 192 ,0.190,0. 123 ,0.135),演化到另一個(gè)狀態(tài),如果定義群體狀態(tài)的某種測度，fuin≈0.000 307 48.并保證每一個(gè)狀態(tài)的群體測度的唯一性，那么我們用MGOA對該函數進(jìn)行優(yōu)化,停機準則MCOA可看作是測度空間到測度空間的映射.對于|f-f"|< 10-8 或函數評價(jià)次數超過(guò)150 030.由n個(gè)參考物體和n個(gè)浮動(dòng)物體組成的群體RN,MGOA的各參數設置如下:F. = FLum",l" =-0.45,定義群體t時(shí)刻的測度為W( RrN+q(a1.2)).因為u° = 1. 45 ,Fm為隨機搜索, lterThreshold = 5000,距MCOA中如果某-代該測度相對于上- -代沒(méi)有得到離測度為2-范數,Ko = 10-10,n,n2分別取1,2, ..增長(cháng),則不進(jìn)入下一代,而是反復使用T,I、T.算20,每-對n, ,n2做25次獨立隨機實(shí)驗.子,直到該測度得到增長(cháng),才進(jìn)入下一代這就保證由圖1可知,當n2/n大約大于2時(shí),平均函數每個(gè)狀態(tài)的群體該測度的唯一性, 于是MGOA可視評價(jià)次數少.這里要說(shuō)明的是,當n =1,n =8時(shí)，為一映射g: Q→Q,即平均函數評價(jià)次數是最少的,1 200左右然后隨著(zhù)n2的增大,評價(jià)次數逐步增加,這一-點(diǎn)跟n > 1的情對Vf∈Q,g(f)比f(wàn)至少增加- -個(gè)浮點(diǎn)編碼況不太- -樣(圖 1不太明顯).精度ε,于是有8(7后) - 8(g(7) ,g(2))=g(7) -f +g(3) -五≥e+ε =2ε戇x10→8(fJ)≥8(g(f),g(f)) +2e,20則必存在很接近于1的η(0 <η < 1),使得i58(g(f),g(f)) < n8(f f),A0可知g是一個(gè)壓縮映射.綜上所述,MGOA滿(mǎn)足nσo° nBanach壓縮映射定理的條件:(Q,8)是一個(gè)完備度圖1n和n對平均函數評價(jià)次數的影響量空間,g是-一個(gè)壓縮映射.所以MGOA必定收斂于Fig.1 Eft of n and n on average function evaluation唯一的不動(dòng)點(diǎn),即timeslimlW(N1w),. = lng(Nm2*)o) =F",中國煤化工且f"與初始群體的測度w(riq(p.n.2)2)無(wú)關(guān),顯CNMHG合事實(shí)上當η >n時(shí),x又僅承時(shí)萬(wàn)里們剛又些而當n > n2時(shí)，然f'就是全局最大值.那么由測度的定義可知,此變異搜索的分量相對多一些在數值實(shí)驗中我們采時(shí)群體RNV中適應值最大的max{n,nz} + 1個(gè)物體用隨機搜索作為變異算子,對MGOA優(yōu)化性能的貢5期金林鵬等:用于 函數優(yōu)化的最大引力優(yōu)化算法659獻不大,反而增加評價(jià)次數,只是為了保證能搜索到2) Shekelg Foxholes Function:整個(gè)解空間. n = 1時(shí)變異發(fā)生的次數很少.當nz≥8時(shí),由n + n個(gè)個(gè)體所組成的群體已能搜索到最fh =[k+2E(x-ay)°]優(yōu)解,故平均函數評價(jià)次數較低當然,n和n2對不同的函數有不同表現，但是勾右∈[-65.536,65.536],K =500, C =j,我們通過(guò)其他函數測試，得出如下經(jīng)驗結論.取n[anj] = 16[((j-1) mod5) -2],≈2n,n≠1;如果n; ,幾取小的值時(shí)不能計算的,[arj] = 16([(j-1)/5] -2),再將n,幾取大點(diǎn)試試;當n = 1時(shí)如果能計算,那(劃,x) = (-32, -32),fain = 0. 998 004.3)Two-dimensional Function:么其平均函數評價(jià)次數是最少的.fs =- [20 + xcoay + ysinx],x∈[0,10],y∈[- 10,0],5改進(jìn) 的最大引力優(yōu)化算法(x,y) = (10, - 6.337614),f.in =- 33. 432 987.4)Two dimensional Function:目前,在連續函數優(yōu)化研究領(lǐng)域,粒子群算法和f =- (21.5 + xsin(4mx) + ysin(20mry)),差分算法是高效的、主流的演化算法.粒子群算法主x∈[-3,12.1],y∈[4.1,5.8],要有慣性權重粒子群算法和帶收縮因子粒子群算法(x,y) = (11. 625 ,5.725),fmim =- 38.850 294.兩個(gè)版本,前者收斂速度相對要慢,但計算性能較穩5) Shubert Function:定;后者收斂速度較快,但計算性能不穩定差分算法的各個(gè)版本也都有類(lèi)似的問(wèn)題.{s= I2i.co[(i+1)x; +門(mén),jI如果我們能設計出一-種方案,其收斂速度相對劃,名∈[- 10,10],較快,并且計算性能也較穩定的話(huà),那就有很現實(shí)的f.. =- 186. 730 909,fm = 210.482 29.應用前景.為此我們對最大引力優(yōu)化算法進(jìn)行改進(jìn)，6)Two-dimensional Function:在原算法step 5和step 6之間插人-一個(gè)計算步:“從群體RN中選出適應值最好的ns個(gè)物體,對它們使fo=(b+(+) +(好+站)，用鄰域交叉算子F.產(chǎn)生新物體C.a ,設E為群體a =3,b =0.05,x,2∈[-5. 12,5.12],RN中適應值最差的物體,若Cem(m) > E..(m),(x,x) = (0,0),f. = 3600.Coen就取代Eom ;否則不變”.同時(shí)將原算法step 67)Trap Function:中“適應值最大的max{n,n2} +1個(gè)物體的平均適0≤x≤0.5應值”改為“整個(gè)群體RN的平均適應值".a-ax,0.50.5遺傳算法,這里就不具體展開(kāi)論證a >b,c> 1,x∈[0,c],x =0.5,fm = a/2.這是本文給出的一一個(gè)陷阱函數,a和b相差越數值仿真實(shí)驗小,c越大,優(yōu)化難度越大.數值實(shí)驗中我們取a =50,b =6,c = 6 000.實(shí)驗選用平臺是Pentium Dual E2200@8)De Jong F2 Function:2.2GHz,1CB內存,VC6環(huán)境，選取典型的f = 100(對-x2)* +(1 +x)',BenchMark測試函數,其中有些函數極難求得最劃,∈[-2.048,2.048], (x,x2) = (1,1),優(yōu)解.faim =0.1 )Two-dimensional Function:9)One-dimensional Function:f = 1 +xsin(4πx) - ysin(4mry +π) +fs =中國煤化工*) +6,sin(6 區+五%∈1. 257 305 4.6√x+y+10'5x,y∈[-1,1],YHCNMHG(x,y) = (土0.64096,士0.64096)，fo =-cosx,●cosx .exp(-(xn -π)°-(x一π)2),fa=2.118765..劃,∈[-100,100], (x,;x) =(π,π),fmin =-1.660模式識別與人工智能23卷.郭濤算法是一種改進(jìn)的遺傳算法,它去掉變異的原因是若迭代次數上限設定值相對于待求解的問(wèn)算子,并采用多父體雜交方式生成新個(gè)體,采用經(jīng)典題太小,則求不出解,而實(shí)際上郭濤算法能求.遺傳算法中的“優(yōu)勝劣汰”計算模型.而最大引力優(yōu)3)粒子群算法SPSO-2007.粒子群算法的各種參化算法是基于“萬(wàn)有引力”計算模型,但同樣采用多數設置如拓撲結構、更新模型等極大地影響著(zhù)算法的父體雜交方式生成新個(gè)體,并且在數值實(shí)驗中均選性能,從1995年開(kāi)始提出到現在,大量學(xué)者如Shi、用FLmeu交叉算子.故將郭濤算法和最大引力優(yōu)化算Clerc等進(jìn)行研究工作Particle Swarm Central (http:法作對比，就比較有意義,同時(shí)兩者的對比,其實(shí)質(zhì)//www. particleswarm. info/)提供的SPS0-2007, 是是遺傳算法“優(yōu)勝劣汰"計算模型和“萬(wàn)有引力”計性能不錯的版本這里采用該版本,設定種群規模為算模型的比較.30 ,停機條件同MG0A,其他參數保持不變引言中提到的SGO、IRO、GSA GPSO這四種算4)差分算法DE.種群規模NP = 30,其他參數法,雖冠以“引力算法”,但跟最大引力優(yōu)化算法是采用Yang等[18]提到的通常設置,CR = 0.9,F =從屬于完全不-樣的體系.它們均基于“位置+位0.5,目前差分算法有五個(gè)版本的變異策略,其中移量”計算模型,而這種計算模型最成功的案例莫DE/rand/1和DE/current to besU/2性能較好,這里過(guò)于粒子群算法.同時(shí)粒子群算法和差分算法是目采用DE/rand/1變異策略,停機條件同MGOA.前連續函數優(yōu)化領(lǐng)域的主流算法,故將他們同最大5)改進(jìn)的最大引力優(yōu)化算法MMGOA.ny = 8,引力優(yōu)化算法作對比其他參數同MGOA.每個(gè)測試函數做25次獨立隨機實(shí)驗,各優(yōu)化算標準差Std、成功率SR反映算法的穩健性以及法具體參數設置如下.跳出局部極值的能力,而平均函數評價(jià)次數FEs反1)最大引力優(yōu)化算法MGOA.參考物體n; =映算法的計算收斂速度.由表1可知,郭濤算法不能10,浮動(dòng)物體n2 =20,F。=Fu",I" =-0.45,u" =一直正確求解fs J,.對fo而言,GuoA沒(méi)有一次正確1.45,Fm為隨機搜索算子，距離測度為2-范數,求解.相對來(lái)說(shuō), MGOA優(yōu)化性能較穩定,基本上都IterThreshold = 5000,K。= 10-10. 停機準則為:設能正確求解,只不過(guò)fs( min)的最差解達不到給定fan是待優(yōu)化問(wèn)題的最優(yōu)解, fue為搜索到的最優(yōu)精度,即使這樣,所求得的最差解精度也已較高在解,若_Lfu-.f..|< 8o或超過(guò)最大函數評價(jià)次數計算速度方面,MGOA的平均函數評價(jià)次數均比150 030,則停機各函數eo設置不相同.GuoA要少,而且是少很多(當然fo除外,因為GuoA2)郭濤算法GuoA.種群規模為30,子空間維度無(wú)法計算,故沒(méi)有比較的意義). .為8,精度e = 10*(見(jiàn)文獻[ 16]).郭濤算法本身就具由表2可知,粒子群算法在25次獨立隨機實(shí)驗有停機準則,即當種群中最好解和最壞解相差在精度中,不能一直正確求解f fsSs fs(min) Sf,(max)、e之內就停機不過(guò)為公平比較,再額外加上MGOA的f。fif,這9個(gè)函數,其中f f的最好解和最壞解相停機準則但設定迭代次數上限為無(wú)窮大這么設置差較大.從標準差Std也可看出,粒子群算法在求解表1郭濤算法和最大引力優(yōu)化算 法優(yōu)化性能對比Table 1 Performance comparison between Guo Tao algoithm and MCOA測試CuoAMGOA函數Best/ WorstStdFEsSHtdSRf2. 118765/2.118764e-768485 25/252. 118765/2. 1187646412 25/250.9980030/0.998003e-1041076 25/250.998003/0.998003724725/25- 33.432987/ -31.175912 e+050963 12/25- 33. 43298/ - 33.43298 e-81261:- 38. 850309/ - 38. 850309 e-977680 25/25- 38. 850309/ - 38.850309 e-923346fs ( min)- 186.73090/- 186.73090 e-7 109739456 25/25 - 186.730908/ - 186. 730906 e-72288524/25f; (max)210. 48229/210. 48229 e-75407811 25/25210.48229/210. 48229:-6264593599. 99993599 99999 e-854497 25/252931224. 9906/24.90246e-2308143 25/25中國煤化工179994. 7280e-13/1. 8583e-9 e-1039513 25/25 2.TYHC NMH G 12536f,1. 257305/1. 33655772376 22/251.257305/1.257305e-12 5064 25/25fo-3.0e-16/0e-1732 0/25- 0.99999 -0.999999e-9183975期金林鵬等:用于 函數優(yōu)化的最大引力優(yōu)化算法661表23種優(yōu)化算法計算結果對比Table 2 Result comparison among 3 optimization algorithms測試SPS0-2007DIMMGOABes/WorstSudBest/WorstStdBesu/ Worststd_f2. 118765/2. 077148e-22. 118765/2.0771482. 118765/2. 1187640. 998003/0.998003e- 100. 998003/1. 992030e-1e-10-33. 432987/ -31.175912 e-1- 33.432987/ -31. 175912e+0-33. 43298/ -33.43298e-8- 38. 850309/ - 38.732330 e-2- 38.850309/ -38.850309 e-9 -38. 850309/-38. 632330 e-2fs (min) - 186. 73090/ - 186. 73080 e-5- 186.73090/ - 186.73090 e-7- 186.73090/ - 186. 73090fs ( max)210. 48229/ 210.48080e-4.210. 48229/210. 48229e-63599. 9999/529 43206e+23599. 9999/599 99993599. 9999399 999924. 99711/3.000000e+124. 9999/24 999924. 9906/24.902464. 5970e-11/1.8419e-9 e- 102.7911e -11/0. 0277e-3 6.4645e- 11/1.8376e-9 e-10f,1. 257305/1.3365571. 257305/1. 3365571. 257305/1.257305fro-0.99999/ -0.999999 e-90. 9999999999e-9-999999/ -0.9999999 e-9表3 3種優(yōu)化算法的平均函數評價(jià)次數和成功率對比分組”和“引力淘汰”機制的函數優(yōu)化方法一最大Table3 Comparison of average function evaluation times and引力優(yōu)化算法,同時(shí)給出其改進(jìn)算法.通過(guò)對典型測success rates among 3 optimization algorithms試函數求解,該算法的連續函數優(yōu)化能力是令人鼓測試_ SPS0-2007E舞的.函數FEsRSR95805 15/25 49279 17/25 2384 25/25不過(guò)最大引力優(yōu)化算法還需要做進(jìn)-步深人研3771 25/257689 24/252275 25/25究,比如鄰域交叉算子、變異算子距離測度、取值方24837 21/25 49506 17/25 2305 25/25面等,當然也可融人其他-些方法,更好地提高算法128150 4/252977 25/25 27239 21/25優(yōu)化性能.另一方面,也需要建立算法的離散模型,fs (min) 53569 21/25 4177 25/257398 25/25以適用于求解TSP、0/1背包等離散問(wèn)題.fs (max) 14115 24/25 3949 25/255898 25/2511538 24/252025 25/252605 25/25 .36379 23/25 38760 25/25 14175 25/25參考文獻7146 25/257472 24/251787 25/2534224 20/25 49164 17/25 2364 25/25[1] Holland J H. Adaptation in Natural and Artificial Sytems. Ann Ar2787 25/25187625/25 2706 25/25bor, USA: Univerity of Michigan Pres, 1975[2] Kirkpatrick s, Gelatt C D, Vecchi M P. Opinization by SimulatedAnnealing. Science, 1983, 220(<4598): 671 -680這9個(gè)函數時(shí)數值計算不穩定.而差分算法不能一-[3] Mori K, Tsukiyama M, Fukuda T. Immune Algorithm with Search-直正確求解f$f2 fs fs J,這5個(gè)函數.從標準差可看ing Divensity and Its Application to Resource Alloeation Problem.出差分算法在求解這5個(gè)函數時(shí)數值計算不穩定Trans of IEE Japan, 1993, 113(10); 872 -878相對來(lái)說(shuō),改進(jìn)最大引力優(yōu)化算法是最穩定的,除f4[4] Dorigo M, Maniceao v, Coloni A. Ant System: Optimizatioh by a不能- -直正確求解外,其他函數求解都很穩定,都達Colony of Cooperaling Agente. IEEE Trans on Sytens, Man and到所給精度.Cybemeice, 1996, 26(1): 29-41[5] Kennedy J, Eberhart R. Particle Swarm Opimization // Proc of the由表3可知,對于各優(yōu)化算法均能求解的函數IEEE Intenational Conference on Neural Networks. Perth, Austral-而言,總體來(lái)說(shuō),3種算法的平均函數評價(jià)次數各有in, 1995, IV: 1942 - 1948長(cháng)短.考慮到隨機性以及針對不同函數參數設置等[6] Stom R, Priee K. Minimizing the Real Functions of the ICEC 96因素可認為旗鼓相當.從成功率角度來(lái)說(shuō),改進(jìn)最大Contest by Differential Erolution /1 Proc of the IEEE International引力優(yōu)化算法相對來(lái)說(shuō)是最穩定的,跳出局部極值Conference on Evolutionary Computation. Nagoya, Japan, 1996:的能力也最強.中國煤化工Tehnirad Repn.7結束語(yǔ)Computer Science,' 1995:CHC N M H Gi Eeex. Depatment of8] Webster B L Solving Combintorial Opimization Problems Using a本文受萬(wàn)有引力現象啟發(fā),設計出基于“引力New Algorithm Based on Gravitational Atraction. Melbourme, USA:662模式識別與人工智能23卷Florida Institute of Technology, 2004itional Search Algorithm. Natunl Computing, 2010, 9: 727 -745[9] Balachandar s R, Kannan K. Randomized Gravitational Emulation[15] Kang Qi, Wang lei, Wu Qidi. A Novel Sl-Onganizing ParticleSearch Algorithm for Symmetric Traveling Saleaman Problem. Ap-Swarm Opimization Based on Gravitation Field Model // Proe of theplied Mathematics and Computation, 2007, 192(2): 413 -421American Control Conference.New York, USA, 2007; 528 -533[10] Hsiao Y T, Chuang C L, JjiangJ A, et al. A Novel Optimization[16] Guo Tao. Evolutionary Computation and Optimization. Ph. D Die-Algorithm: Space Grevitational Opimizaion// Proe of the IEEE Insertation. Wuhan, China: Wuhan University. School of Computer,temational Conference on Systems, Man and Cybemetics. Hawaii,1999 (in Chinese)USA, 2005,皿: 2323 -2328(郭海.演化計算與優(yōu)化博士學(xué)位論文.武漢:武漢大學(xué).計算[11] Chuang C L, Jiang J A. Integrated Radiation Opimization; In-機學(xué)院, 1999)spired by the Cravitational Radiation in the Curvature of Space-Time[17] Xu Zongben. Computational Itelligence - Simulated Evolutionary/1 Proe of the IEEE Congress on Evolutionary Computaion. SingaComputation. Beijing, China: Higher Educeaion Pres, 2003 (inpore, Singepore, 2007: 3157 -3164Chinese)[12] Rashedi E. Gravitational Search Algorihm. Kerman, lran: Shahid(徐宗本.計算智能一-模擬進(jìn)化計算. 北京:高等教育出版社，Bahonaer Unversity of Kerman, 20072003)[13] Raabedi E, Neamabadi-Pour H, Saryuadi s. CSA: A Graitaion- [18] Yang Zheny, Tang Ke, Yao Xin. Sll-Adaptive Diferential Evo-al Search Algorithm. Information Sciences: An Intemational Jourlution with Neighborhood Search /1 Proe of the IEEE Congress onnal, 2009, 179(13): 2232 -2248Evolutionary Computation. Washington, USA, 2008: 110-1116[14] Rashedi E, Neramabadi-Pour H, Saryadi s. BCSA: Binary Crav-第十三屆中國機器學(xué)習會(huì )議(CCML2011)征文通知由中國人工智能學(xué)會(huì )機器學(xué)習專(zhuān)業(yè)委員會(huì )和中國計算機學(xué)會(huì )人工智能與模式識別專(zhuān)業(yè)委員會(huì )聯(lián)合主辦,福建師范大學(xué)承辦,福建農林大學(xué)、武夷學(xué)院協(xié)辦的“第十三屆中國機器學(xué)習會(huì )議(CCML2011)”將于2011年8月6日至8日在福建武夷山召開(kāi)。該系列會(huì )議每?jì)赡昱e行- ~次 ,現已成為國內機器學(xué)習界最主要的學(xué)術(shù)活動(dòng)。根據中國人工智能學(xué)會(huì )要求,該會(huì )議從2011年起改為每逢奇數年舉行。此次會(huì )議將為機器學(xué)習及相關(guān)研究領(lǐng)域的學(xué)者交流最新研究成果、進(jìn)行廣泛的學(xué)術(shù)討論提供便利,并且將邀請國內機器學(xué)習領(lǐng)域的著(zhù)名學(xué)者做精彩報告。一征文范圍(但不限于)機器學(xué)習的新理論、新技術(shù)與新應用特征選擇人工生命人類(lèi)學(xué)習的計算模型流形學(xué)習與降維模糊集與粗糙集計算學(xué)習理論基于案例的推理多Agent系統中的學(xué)習監督學(xué)習增量學(xué)習與在線(xiàn)學(xué)習模式識別非監督學(xué)習對復雜結構數據的學(xué)習信息檢索半監督學(xué)習增強學(xué)習系統可理解性生物信息學(xué)強化學(xué)習數據挖掘與知識發(fā)現語(yǔ)音、圖像處理與理解多示例學(xué)習聚類(lèi)自然語(yǔ)言理解:神經(jīng)網(wǎng)絡(luò )生物特征識別中國煤化工集成學(xué)習進(jìn)化計算MHCNMHG多策略學(xué)習(下轉第714頁(yè))