第23卷第5期模式識別與人工智能Vol.23 No.52010年10月.PR&AIOct 2010用于函數(shù)優(yōu)化的最大引力優(yōu)化算法*金林鵬李均利魏平陳剛(寧波大學(xué)信息科學(xué)與工程學(xué)院寧波315211)摘要提出一種基于牛頓萬 有引力定理的函數(shù)優(yōu)化方法一最大引力優(yōu)化算法. 該算法通過“引力分組"和“引力淘汰”過程更新搜索體.文中給出4個引理來描述算法的數(shù)學(xué)基礎(chǔ)，同時也給出算法的收斂性證明.此外還對該算法進(jìn)行改進(jìn).最后與粒子群算法、差分算法、郭濤算法進(jìn)行比較,數(shù)值結(jié)果顯示該算法在解決連續(xù)函數(shù)優(yōu)化問題具有較高的性能.關(guān)鍵詞函數(shù)優(yōu)化,最大引力優(yōu)化算法( MG0A) ,模擬進(jìn)化計(jì)算,萬有引力中圖法分類號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)項(xiàng)目(No.60832003) 、浙江省自然科學(xué)基金項(xiàng)科學(xué)基金項(xiàng)目(No.2009 A610089)和寧大學(xué)王寬誠基金項(xiàng)目資助MYHCNMHG收稿日期:2009 -04 - 13;修回日期:2010-04 -09作者簡介金林鵬,男,1984 年生，碩士研究生,主要研究方向?yàn)樽顑?yōu)化方法、演化計(jì)算. E-mail: kinis1984@ 163. com.李均利，男,1972年生，研究員，博士生導(dǎo)師，主要研究方向?yàn)檠莼?jì)算、醫(yī)學(xué)圖像處理、視頻處理等.魏平，男,1978年生，博士,主要研究方向?yàn)檠莼?jì)算醫(yī)學(xué)圖像處理等.陳剛,男,1963年生，博士,教授，主要研究方向?yàn)橄到y(tǒng)仿真非線性系統(tǒng)分析等。654模式識別與人工智能23卷1引言Kang等[I5]提出的基于引力的粒子群算法(ParticleSwarm Optimization Based on Gravitation Field Model,優(yōu)化是一個古老的問題，追求最優(yōu)目標(biāo)一直是CPSO) ,則是在原粒子群算法的基礎(chǔ)上加上由引力人類的理想,長期以來.人們對最優(yōu)化問題進(jìn)行不斷產(chǎn)生的加速度項(xiàng).的探討和研究,發(fā)展了許多確定有效的優(yōu)化方法,如以上四種算法均是基于“位置+位移量”計(jì)算牛頓法、共軛梯度法、單純形法等.然而很多優(yōu)化問模型(同粒子群算法類似),受萬有引力公式啟發(fā),題的函數(shù)性質(zhì)十分復(fù)雜,解析性質(zhì)不清晰,甚至可能模擬動態(tài)的物理運(yùn)動過程.唯--不同的是他們的更沒有具體的函數(shù)表達(dá)式.傳統(tǒng)優(yōu)化算法在求解這些新公式,問題,無論是在計(jì)算速度、收斂性、初值敏感性等方本文提出的最大引力優(yōu)化算法( Maximal Gravi-面都遠(yuǎn)不能滿足要求.20世紀(jì)50年代中期出現(xiàn)仿tation Optimization Algorithm, MGOA)亦是基于牛頓生學(xué)學(xué)科,人們很快從生物進(jìn)化的機(jī)理和仿生學(xué)中引力公式,不同的是,1)該算法不是模擬一個動態(tài).得到啟示,提出多種求解優(yōu)化問題的模擬進(jìn)化方法,的物理運(yùn)動過程,而是模擬一個物理現(xiàn)象:在-一個有如遺傳算法"、模擬退火算法[2]、免疫算法']、蟻群很多物體的空間中,最大引力值存在于質(zhì)量最大物算法[4]、粒子群算法'5]、差分算法[°1等,并取得巨大體的附近;2)其計(jì)算所得的引力僅僅是一個測度,成功.并不是真正意義的引力,同時計(jì)算引力測度是為后對于引力模擬局部搜索( Gravitational Emulation來“引力分組過程”提供依據(jù);3)其計(jì)算模型是基于Local Search, GELS)"的研究,最初概念性框架是“ 交叉變異"(同遺傳算法類似),而不是基于“位置由Voudouris 和Tsang 于1995年提出，Webster[8])發(fā)+位移量”;4)該算法從確定交叉、變異的個體到確展了它.該算法可形象描述為一個在介質(zhì)上滾動的定淘汰個體,均是基于萬有引力現(xiàn)象,同遺傳算法球,介質(zhì)上有很多的坑,坑有深有淺球在滾動過程“優(yōu)勝劣汰"思想有著本質(zhì)的區(qū)別.中由于介質(zhì)摩擦力而逐漸失去動力.如果該球正滾進(jìn)坑里,它就獲得了動力;如果該球正滾出坑,它將2基于牛頓引力公式的最大引力失去動力.算法的理念是由于引力的影響,球最終會優(yōu)化算法停留在某個坑里. Balachandar91 在Webster 的基礎(chǔ)上提出隨機(jī)引力模擬搜索( Randomized Gravitational2.1基本概念Emulation Search, RGES)算法,克服其收斂速度慢、解的質(zhì)量不高等問題,使其求解能力大大提高.這3萬有引力是兩個具有質(zhì)量的物體間相互吸引的種引力模擬搜索算法用于求解旅行商向題(Trave-作用,存在于任何有質(zhì)量的物體之間.兩個物體間的ling Salesman Problem, TSP)等組合優(yōu)化問題,求解引力大小,跟它們之間質(zhì)量的乘積成正比，跟它們的機(jī)制基于離散的路徑信息，與本文提出的用于函數(shù)距離的平方成反比,用公式表示為優(yōu)化的最大引力算法關(guān)系不大,故這里不具體展開F=G",(1)說明.Hsiao[10]提出的空間引力優(yōu)化(SpaceGravita-其中,C = 6.672為引力常數(shù),m,、m2分別為兩物體tional Optimization , SGO)是基于愛因斯坦相對論和的質(zhì)量,r是它們之間的距離.牛頓引力公式,模擬行星群在宇宙中漂移以找到最考慮求解無約束函數(shù)優(yōu)化問題:Z = maxf(X),大質(zhì)量的行星個體,時空幾何的變化導(dǎo)致行星加速或減速,從而使行星漂移.Chuang["]提出的累積輻搜索空間D = {X|l≤x;≤u,i = 1,2,.*,n}，射優(yōu)化( Integrated Radiation Optimization , IRO),是X =(x,",x,)",4,u;(1≤i≤n)分別為每一基于“一個置身于引力場的行星的運(yùn)動是由空間中維取值的上下邊界f(X)為目標(biāo)函數(shù).將萬有引力所有其他行星輻射引力波,共同作用的情況"這一用于函數(shù)優(yōu)化問題，做法是將搜索空間D中的每個事實(shí)而設(shè)計(jì)的. Rashedil2-14)提出的引力搜索算法點(diǎn)看作中國煤化工i量m分別為(Gravitational Search Agorihm, GSA),通過計(jì)算每CNMHG(2)個粒子與其他所有粒子之間的引力值,并將所有這m' = nV(A)些引力值以隨機(jī)加權(quán)方式計(jì)算總和,求得該粒子所h(x)為-維尺度變換函數(shù),滿足對Vx∈(-∞,受到的引力,進(jìn)而求得加速度,再更新速度和位置.+∞),h(x) > 0,并且嚴(yán)格單調(diào)遞增為了降低計(jì)算5期金林鵬等:用于 函數(shù)優(yōu)化的最大引力優(yōu)化算法655復(fù)雜度,將搜索空間D中任兩個點(diǎn)間的引力簡化為成新物體C.顯然P;的個數(shù)決定新物體C的個數(shù),Fr.2 =h(f(X)) . h((X2))3)故共生成n個新物體C.記新物體群ζ= {C, 1≤1.2 + K。i≤n},那么其中,X,X2 e D,r.2 為距離測度,Ko為很小的數(shù),C=(U, {F.(P.)}) U(_ u{F_(P:)})防止式(3)中分母為零.雖然形式變了,但本質(zhì)上跟式(1)是一致的,因?yàn)槲覀冃枰闹皇莾牲c(diǎn)間的引iter = iter + 1.力測度,而不是真正的引力值.step4對每個新物體C(1≤i≤n), 由于每為說明方便,下面提到的物體適應(yīng)值其實(shí)就是個浮動物體與其所選擇的參考物體之間都有距離測物體的質(zhì)量,或者說是目標(biāo)函數(shù)值的某-尺度變換度,距離測度最小的一對物體中質(zhì)量小的物體即為函數(shù)值要淘汰的物體,記為E,其中2.2算法描述r咖= min(yj, 1≤j≤n2)在最大引力優(yōu)化算法(MC0A)中涉及到參考lhk = min({j|rqJ =喇，1≤j≤n})物體群R、浮動物體群N(兩者統(tǒng)稱為群體RNV)和新fRm，ifR(m) ≤Nu(m)物體群C,記R(X)和R(m)分別為參考物體R的E: =lNx，otherwise位置和質(zhì)量,N,(X)和N,(m)分別為浮動物體N;的位置和質(zhì)量, C;(X)和C;(m)分別為新物體C;的位如果C(m) > E(m) ,C;就取代E,再用算法流程置和質(zhì)量,RN,(X)和RN,(m)分別為群體中物體中step2方法更新s;值;否則不變RN,的位置和質(zhì)量. MGOA的計(jì)算步驟如下.step5若連 續(xù)IterThreshold迭代次數(shù)內(nèi)均沒step 1隨機(jī)產(chǎn)生參考物體群R和浮動物體群有變異發(fā)生,則通過變異算子生成新物體C. ,更新,其中方法同step 4.R= {R,1≤i≤n}step6 若適應(yīng)值最大的max{m,n2} +1個物W= {N,1≤j≤n}體,其平均適應(yīng)值沒有增加,則令iter = iter -1.若滿足終止條件則停機(jī)，否則將這n + n2個物體重新令iter =0.step2計(jì)算每個參考物體R(1 ≤i≤mn)和隨機(jī)選定為參考物體和浮動物體,轉(zhuǎn)step 2.每個浮動物體N(1≤j≤n)之間的引力測度Fj2.3算 法說明和距離測度r.s(距離測度可以是1-范數(shù)2-范數(shù)、F-2.3.1物理意義范數(shù)或模糊距離測度等):由式(1)可知,引力值較大的時候,要么有質(zhì)量τj= |R;(X) - N(X) I ,較大的物體,要么兩物體間的距離較小由于本算法R.(m) x N,(m)在每次迭代過程中淘汰引力相對較大并且距離測度rj+ Ko最小的一-對物體中質(zhì)量小的物體，這就保證在引力每個浮動物體N,(1≤j≤n)選擇和其引力最大的相對較大的物體附近往往存在質(zhì)量大的物體.正是參考物體r,其中基于這一思想,構(gòu)造出最大引力優(yōu)化算法從函數(shù)優(yōu)pF7 = max(Fij, 1≤i≤n)化角度來說,這樣--種淘汰策略有利用保持種群的ls, = min({i|Fj= F",1≤i≤n})多樣性.step3 記P= {P,1≤i≤n},其中P;為參2.3.2模型說明考物體R,和所有選擇它的浮動物體組成的集合,最大引力優(yōu)化算法同遺傳算法類似，是通過交P: = {R} U {N|;j = i,1≤j≤n}.叉和變異來更新群體，而不是像粒子群算法通過位對于每個參考物體R,可能至少有一個浮動物體選置和位移量、差分算法通過差向量,來更新群體.不擇它,也可能沒有浮動物體選擇它這樣P:就分為過需要說明的是,遺傳算法的設(shè)計(jì)理念是基于生物兩類,記p"和P"分別由這兩類P;所組成的集合:進(jìn)化的“優(yōu)勝劣汰”思想,通過淘汰群體中差的個: ,優(yōu)秀的個體通過P" ={R|{N|s =i,1≤j≤n}≠0,1≤i≤n}雜交YH中國煤化工個體遺傳算法的=P-p°這種讓CNMHG在數(shù)值實(shí)驗(yàn)中也.設(shè)F。為鄰域交叉算子,F.為變異算子,對P"中的取得很大的成功不過遺傳算法也存在不足,如算法元素使用F.算子,對P"中的元素使用F算子,生不穩(wěn)定、早熟等.而最大引力優(yōu)化算法的設(shè)計(jì)理念是656模式識別與人工智能23卷基于- -種萬有引力現(xiàn)象,核心思想是“引力分組”和a個物體那么只要(),2.,"",入.) = (1,0,.",0)，“引力淘汰”機(jī)制,而這兩點(diǎn)均是通過萬有引力這一λ;是RN。(X)的構(gòu)造系數(shù),就可再次搜索到最優(yōu)物普遍現(xiàn)象而導(dǎo)出的,跟遺傳算法的“優(yōu)勝劣汰”思想體不妨設(shè)浮點(diǎn)數(shù)編碼精度為e,Flim中(入1,λz,有著質(zhì)的區(qū)別.應(yīng)該這么說,遺傳算法和最大引力優(yōu)..,入.) 的取值有V.m種,那么V,ia必然小于化算法是設(shè)計(jì)理念的區(qū)別,至于交叉算子和變異算([(u"-l")/e])* ,因?yàn)镋λ= 1還制約著(A，子,兩者可互相借鑒2.3.3鄰域交叉算子 F.的選取Az,.. ,入。)的取值,由此可知V,iwn是有限數(shù).當(dāng)RN。.根據(jù)最大引力優(yōu)化算法的構(gòu)造思想,任何鄰域是參考物體時,情況類似，相應(yīng)參數(shù)不妨設(shè)為V.,uw,交叉算子均可適用下面介紹一種鄰域交叉算子,最于是有早見于郭濤算法[06.。設(shè)Xx,X,.",X,∈R", \\z,p{r"(RN)≈麗uE...∈R,則2Pr.一+p, Pr,umn一>0, (4)[X'= 2\X其中∈E*.需要說明的是，在實(shí)際演化計(jì)算中,由非最優(yōu)物體搜索到最優(yōu)物體的可能是存在l2λ:=1,l°≤λ;≤u° ,I" <0,u' >1的,故實(shí)際搜索到最優(yōu)物體的概率要比式(4)右邊.其中,I"、u"為λ;取值的上下界,我們將其記為的式子要大,而當(dāng)z > 1或多最優(yōu)值問題時,其概率rLiner.就更大. Vj.V,urn P.iw是變量,每次迭代可能都不一樣,但不論怎么變換,式(4)總是成立的. 證畢3最大引力優(yōu)化算法的數(shù)學(xué)基礎(chǔ)注“[x]"表示對x向上取整.那么由引理1我們能不能得到結(jié)論:及收斂性證明p{T(RN)≈RN*t!} > 0.我們有如下引理.引理2對于單最優(yōu)值問題而言 ,有定義1若群體RN 有z(z≥0)個物體是全局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} .問題,X”不唯- -).證明對于單最優(yōu)值問題而言,任意兩個最優(yōu)定義2記 T,為引力分組算子,對應(yīng)算法流程物體之間的距離測度是最小的MGOA中每個浮動中step 2,T。為構(gòu)造算子,對應(yīng)算法流程中step 3,T.物體與其所選擇的參考物體之間都有一個距離測為淘汰更新算子,對應(yīng)算法流程中step 4.我們分別度,而淘汰更新算子T.淘汰的是距離測度最小的一記操作算子T和T'為T=ToTq°T,T"= Tp° T,對物體中質(zhì)量小的物體.若參考物體群和浮動物體引理1 設(shè)最大引力優(yōu)化算法某- -次迭代,群群中都有最優(yōu)物體,由于最優(yōu)物體間引力測度最大，體為RN(z≥1),為全局最優(yōu)物體,則相互選擇,并且距離測度最小,故淘汰更新算子T,p{T'(RN)→RN uC*} >0,淘汰的是一一個最優(yōu)物體由于搜索到的新物體其適其中,∈C,"→"表示“演化得到”的應(yīng)值不可能比最優(yōu)物體大,故這種情況下群體中就意思.不可能再增加最優(yōu)物體.證明對于RN(z≥ 1) ,不妨設(shè)物體RN。是最要證明p{T(RN)≈RN*#} > 0,首先要保證能優(yōu)物體,它成為浮動物體的概率p; =n2/(n, +n2),搜索到最優(yōu)物體,其次淘汰物體能被最優(yōu)物體替換成為參考物體的概率p, = n/(n| + n2) ,并設(shè)它成掉(由前面分析可知,只要群體RN中最優(yōu)物體不同為參考物體后被浮動物體選中的概率為P.,uan,則時出現(xiàn)在參考物體群和浮動物體群,就能保證淘汰MGOA通過鄰域交叉算子在RN。附近搜索的概率為物體被替換).Ppr+p, xp.ur這里以Flunmr為例給出證明,其他F?？?概率,由引理1可類似證明,因?yàn)槿魏梧徲蚪徊嫠阕拥囊粋€共同特點(diǎn)知Pa中國煤化工浮動物體群不同是在給定物體的附近搜索時有YHCNMHG當(dāng)RN。是浮動物體時,必然選擇某-參考物體,p{T(RN)≈Ri'*} =Pandeu .pm.(5)而其它浮動物體也可能選擇它,不妨設(shè)該組一共有當(dāng)1≤z≤max{n,nz}時,至少存在一種排列,金林鵬等:用于函數(shù)優(yōu)化的最大引力優(yōu)化算法657使參考物體群和浮動物體群不同時出現(xiàn)最優(yōu)物體,群體RN通過多物體交叉方式和變異方式生成新物故Pm >0,式(5)大于0;當(dāng)z> max{n,nri時,不論體的概率這樣排列，參考物體和浮動物體都至少有一一個是最引理4最大引力優(yōu)化算法的交叉概率p。 和變優(yōu)物體,故pm = 0,式(5)等于0.結(jié)論成立證畢異概率pm均大于0.相比單最優(yōu)值問題而言,多最優(yōu)值問題中“任證明由引理3可知,MGOA在-一次迭代中多意兩個最優(yōu)物體之間的距離測度是最小的”這一結(jié)物體交叉至少發(fā)生- -次,可知p。> 0.不過MGOA是論將不再成立.不過當(dāng)1≤z≤max{n,n}時,式不能保證變異- -定 發(fā)生的,但由于算法流程中step 5(5)大于零的;而當(dāng)z > max{n,m}時,若群體RN的存在,可知pm > 0.故結(jié)論成立.證畢中max{n,n2} + 1個物體都是同一位置的最優(yōu)物由文獻(xiàn)[17]可知變異算子可搜索到整個解空體,式(5)等于零(以上證明同單最優(yōu)值問題,即引間D,而MGOA中pm>0,故MGOA能搜索到整個解理2).若不存在max{n,n2}{ + 1個物體均是同- -位空間.置的最優(yōu)物體,那么總可以找到一種排列使得同一定義4設(shè)有nm 個個體的群體RN ,其適應(yīng)值最位置的最優(yōu)物體不同時出現(xiàn)在參考物體群和浮動物大的n.個個體組成主群RN ,記W(RNx ).為1時刻體群,而這就給其他非最優(yōu)物體被替換提供了條件.主群中所有個體的平均適應(yīng)值,Q為平均適應(yīng)值的不過這些非最優(yōu)物體能不能更新為最優(yōu)物體,跟優(yōu)集合,若算法t時刻的W(RN%),滿足化問題和迭代情況有關(guān)lim W(RN"), =f'，f'∈Q由以上分析可知,最大引力優(yōu)化算法求解多最優(yōu)值問題時,運(yùn)行- -次可能只找到1個,也可能是2則稱算法收斂到f' .個或更多.另外,引理2及多最優(yōu)值問題的分析也解定理1浮點(diǎn)編碼下 的最大引力優(yōu)化算法,所釋算法step 6中為什么是適應(yīng)值最大的max{n; ,n2}有可能的RN所組成的集合是有限集,平均適應(yīng)值集+1個物體的平均適應(yīng)值,而不是整個群體的平均適合Q也是有限集.應(yīng)值.我們記RN,(X) = (.xe2x.....)，,引理3不考 慮step 5,最大引力優(yōu)化算法在一k = 1 ,2,.",nm,則我們有1≤x≤u,1≤i≤n.次迭代中多物體交叉至少發(fā)生一次.當(dāng)n =1時,變采用浮點(diǎn)編碼,由于編碼精度總是有限的,不妨設(shè)為異不發(fā)生;當(dāng)n > n2時,在-一次迭代中變異至少發(fā)&,則%,的取值情況有[(4; - l,)/e] 種可能，生n-n次;當(dāng)1 n2 時,在一次迭代中至少有8(F5) =jO,n-n個參考物體沒有被浮動物體所選擇,故變異l2M+1-5-石，了≠后至少發(fā)生-n次.當(dāng)1 m中國煤化工≠f時，時,變異的分量相對多-點(diǎn),n,》n近于隨機(jī)搜索8(當(dāng)n≤n時,多物體交叉的分量相對多一點(diǎn),幾=1TYHCNMH G(2M+1-萬-萬)沒有變異發(fā)生.= (2M+1--f3) +(2M+1 -f一石)定義3交叉概率p。 和變異概率Pm分別表示= 8(fiJ5) +8(rJ5),658 .模式識別與人工智能23卷當(dāng)凱=無或，=五時，顯然均是最優(yōu)物體.證畢8(元后) = 8(5) +8(2J5)，由此可知8是-一個度量.證畢4 n和n經(jīng)驗(yàn)取值的研究定理3 (Q ,8)構(gòu)成完備的度量空間.證明首先,平均適應(yīng)值集合Q非空,由定理2最大引力優(yōu)化算法中n、m的取值直接影響其知δ是一個度量,因而(Q,8)構(gòu)成度量空間.又由定理優(yōu)化性能,引理3已從理論上給出分析.下面我們以1知，集合Q是有限集,因而(Q,8)中的任意CauchyKowalik Problem( KL)函數(shù)為例,從實(shí)際計(jì)算性能序列都收斂,從而(Q ,8)構(gòu)成完備的度量空間.證畢分析一下.Banach壓縮映射定理設(shè)(Q,8) 為完備度量fxa=(a.--x(1 + x26.)空間,g: Q→Q為一壓縮映射,則g有且僅有一個不(1 +xb, +xob)動點(diǎn)f*∈Q,并且對于Vf∈Q滿足劃,在，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)化算法將一個狀態(tài)的群體(x,z,x,x)≈(0. 192 ,0.190,0. 123 ,0.135),演化到另一個狀態(tài),如果定義群體狀態(tài)的某種測度，fuin≈0.000 307 48.并保證每一個狀態(tài)的群體測度的唯一性，那么我們用MGOA對該函數(shù)進(jìn)行優(yōu)化,停機(jī)準(zhǔn)則MCOA可看作是測度空間到測度空間的映射.對于|f-f"|< 10-8 或函數(shù)評價次數(shù)超過150 030.由n個參考物體和n個浮動物體組成的群體RN,MGOA的各參數(shù)設(shè)置如下:F. = FLum",l" =-0.45,定義群體t時刻的測度為W( RrN+q(a1.2)).因?yàn)閡° = 1. 45 ,Fm為隨機(jī)搜索, lterThreshold = 5000,距MCOA中如果某-代該測度相對于上- -代沒有得到離測度為2-范數(shù),Ko = 10-10,n,n2分別取1,2, ..增長,則不進(jìn)入下一代,而是反復(fù)使用T,I、T.算20,每-對n, ,n2做25次獨(dú)立隨機(jī)實(shí)驗(yàn).子,直到該測度得到增長,才進(jìn)入下一代這就保證由圖1可知,當(dāng)n2/n大約大于2時,平均函數(shù)每個狀態(tài)的群體該測度的唯一性, 于是MGOA可視評價次數(shù)少.這里要說明的是,當(dāng)n =1,n =8時，為一映射g: Q→Q,即平均函數(shù)評價次數(shù)是最少的,1 200左右然后隨著n2的增大,評價次數(shù)逐步增加,這一-點(diǎn)跟n > 1的情對Vf∈Q,g(f)比f至少增加- -個浮點(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是一個壓縮映射.綜上所述,MGOA滿足nσo° nBanach壓縮映射定理的條件:(Q,8)是一個完備度圖1n和n對平均函數(shù)評價次數(shù)的影響量空間,g是-一個壓縮映射.所以MGOA必定收斂于Fig.1 Eft of n and n on average function evaluation唯一的不動點(diǎn),即timeslimlW(N1w),. = lng(Nm2*)o) =F",中國煤化工且f"與初始群體的測度w(riq(p.n.2)2)無關(guān),顯CNMHG合事實(shí)上當(dāng)η >n時,x又僅承時萬里們剛又些而當(dāng)n > n2時，然f'就是全局最大值.那么由測度的定義可知,此變異搜索的分量相對多一些在數(shù)值實(shí)驗(yàn)中我們采時群體RNV中適應(yīng)值最大的max{n,nz} + 1個物體用隨機(jī)搜索作為變異算子,對MGOA優(yōu)化性能的貢5期金林鵬等:用于 函數(shù)優(yōu)化的最大引力優(yōu)化算法659獻(xiàn)不大,反而增加評價次數(shù),只是為了保證能搜索到2) Shekelg Foxholes Function:整個解空間. n = 1時變異發(fā)生的次數(shù)很少.當(dāng)nz≥8時,由n + n個個體所組成的群體已能搜索到最fh =[k+2E(x-ay)°]優(yōu)解,故平均函數(shù)評價次數(shù)較低當(dāng)然,n和n2對不同的函數(shù)有不同表現(xiàn)，但是勾右∈[-65.536,65.536],K =500, C =j,我們通過其他函數(shù)測試，得出如下經(jīng)驗(yàn)結(jié)論.取n[anj] = 16[((j-1) mod5) -2],≈2n,n≠1;如果n; ,幾取小的值時不能計(jì)算的,[arj] = 16([(j-1)/5] -2),再將n,幾取大點(diǎn)試試;當(dāng)n = 1時如果能計(jì)算,那(劃,x) = (-32, -32),fain = 0. 998 004.3)Two-dimensional Function:么其平均函數(shù)評價次數(shù)是最少的.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:目前,在連續(xù)函數(shù)優(yōu)化研究領(lǐng)域,粒子群算法和f =- (21.5 + xsin(4mx) + ysin(20mry)),差分算法是高效的、主流的演化算法.粒子群算法主x∈[-3,12.1],y∈[4.1,5.8],要有慣性權(quán)重粒子群算法和帶收縮因子粒子群算法(x,y) = (11. 625 ,5.725),fmim =- 38.850 294.兩個版本,前者收斂速度相對要慢,但計(jì)算性能較穩(wěn)5) Shubert Function:定;后者收斂速度較快,但計(jì)算性能不穩(wěn)定差分算法的各個版本也都有類似的問題.{s= I2i.co[(i+1)x; +門,jI如果我們能設(shè)計(jì)出一-種方案,其收斂速度相對劃,名∈[- 10,10],較快,并且計(jì)算性能也較穩(wěn)定的話,那就有很現(xiàn)實(shí)的f.. =- 186. 730 909,fm = 210.482 29.應(yīng)用前景.為此我們對最大引力優(yōu)化算法進(jìn)行改進(jìn)，6)Two-dimensional Function:在原算法step 5和step 6之間插人-一個計(jì)算步:“從群體RN中選出適應(yīng)值最好的ns個物體,對它們使fo=(b+(+) +(好+站)，用鄰域交叉算子F.產(chǎn)生新物體C.a ,設(shè)E為群體a =3,b =0.05,x,2∈[-5. 12,5.12],RN中適應(yīng)值最差的物體,若Cem(m) > E..(m),(x,x) = (0,0),f. = 3600.Coen就取代Eom ;否則不變”.同時將原算法step 67)Trap Function:中“適應(yīng)值最大的max{n,n2} +1個物體的平均適0≤x≤0.5應(yīng)值”改為“整個群體RN的平均適應(yīng)值".a-ax,0.50.5遺傳算法,這里就不具體展開論證a >b,c> 1,x∈[0,c],x =0.5,fm = a/2.這是本文給出的一一個陷阱函數(shù),a和b相差越數(shù)值仿真實(shí)驗(yàn)小,c越大,優(yōu)化難度越大.數(shù)值實(shí)驗(yàn)中我們?nèi) =50,b =6,c = 6 000.實(shí)驗(yàn)選用平臺是Pentium Dual E2200@8)De Jong F2 Function:2.2GHz,1CB內(nèi)存,VC6環(huán)境，選取典型的f = 100(對-x2)* +(1 +x)',BenchMark測試函數(shù),其中有些函數(shù)極難求得最劃,∈[-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 區(qū)+五%∈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)的遺傳算法,它去掉變異的原因是若迭代次數(shù)上限設(shè)定值相對于待求解的問算子,并采用多父體雜交方式生成新個體,采用經(jīng)典題太小,則求不出解,而實(shí)際上郭濤算法能求.遺傳算法中的“優(yōu)勝劣汰”計(jì)算模型.而最大引力優(yōu)3)粒子群算法SPSO-2007.粒子群算法的各種參化算法是基于“萬有引力”計(jì)算模型,但同樣采用多數(shù)設(shè)置如拓?fù)浣Y(jié)構(gòu)、更新模型等極大地影響著算法的父體雜交方式生成新個體,并且在數(shù)值實(shí)驗(yàn)中均選性能,從1995年開始提出到現(xiàn)在,大量學(xué)者如Shi、用FLmeu交叉算子.故將郭濤算法和最大引力優(yōu)化算Clerc等進(jìn)行研究工作Particle Swarm Central (http:法作對比，就比較有意義,同時兩者的對比,其實(shí)質(zhì)//www. particleswarm. info/)提供的SPS0-2007, 是是遺傳算法“優(yōu)勝劣汰"計(jì)算模型和“萬有引力”計(jì)性能不錯的版本這里采用該版本,設(shè)定種群規(guī)模為算模型的比較.30 ,停機(jī)條件同MG0A,其他參數(shù)保持不變引言中提到的SGO、IRO、GSA GPSO這四種算4)差分算法DE.種群規(guī)模NP = 30,其他參數(shù)法,雖冠以“引力算法”,但跟最大引力優(yōu)化算法是采用Yang等[18]提到的通常設(shè)置,CR = 0.9,F =從屬于完全不-樣的體系.它們均基于“位置+位0.5,目前差分算法有五個版本的變異策略,其中移量”計(jì)算模型,而這種計(jì)算模型最成功的案例莫DE/rand/1和DE/current to besU/2性能較好,這里過于粒子群算法.同時粒子群算法和差分算法是目采用DE/rand/1變異策略,停機(jī)條件同MGOA.前連續(xù)函數(shù)優(yōu)化領(lǐng)域的主流算法,故將他們同最大5)改進(jìn)的最大引力優(yōu)化算法MMGOA.ny = 8,引力優(yōu)化算法作對比其他參數(shù)同MGOA.每個測試函數(shù)做25次獨(dú)立隨機(jī)實(shí)驗(yàn),各優(yōu)化算標(biāo)準(zhǔn)差Std、成功率SR反映算法的穩(wěn)健性以及法具體參數(shù)設(shè)置如下.跳出局部極值的能力,而平均函數(shù)評價次數(shù)FEs反1)最大引力優(yōu)化算法MGOA.參考物體n; =映算法的計(jì)算收斂速度.由表1可知,郭濤算法不能10,浮動物體n2 =20,F。=Fu",I" =-0.45,u" =一直正確求解fs J,.對fo而言,GuoA沒有一次正確1.45,Fm為隨機(jī)搜索算子，距離測度為2-范數(shù),求解.相對來說, MGOA優(yōu)化性能較穩(wěn)定,基本上都IterThreshold = 5000,K。= 10-10. 停機(jī)準(zhǔn)則為:設(shè)能正確求解,只不過fs( min)的最差解達(dá)不到給定fan是待優(yōu)化問題的最優(yōu)解, fue為搜索到的最優(yōu)精度,即使這樣,所求得的最差解精度也已較高在解,若_Lfu-.f..|< 8o或超過最大函數(shù)評價次數(shù)計(jì)算速度方面,MGOA的平均函數(shù)評價次數(shù)均比150 030,則停機(jī)各函數(shù)eo設(shè)置不相同.GuoA要少,而且是少很多(當(dāng)然fo除外,因?yàn)镚uoA2)郭濤算法GuoA.種群規(guī)模為30,子空間維度無法計(jì)算,故沒有比較的意義). .為8,精度e = 10*(見文獻(xiàn)[ 16]).郭濤算法本身就具由表2可知,粒子群算法在25次獨(dú)立隨機(jī)實(shí)驗(yàn)有停機(jī)準(zhǔn)則,即當(dāng)種群中最好解和最壞解相差在精度中,不能一直正確求解f fsSs fs(min) Sf,(max)、e之內(nèi)就停機(jī)不過為公平比較,再額外加上MGOA的f。fif,這9個函數(shù),其中f f的最好解和最壞解相停機(jī)準(zhǔn)則但設(shè)定迭代次數(shù)上限為無窮大這么設(shè)置差較大.從標(biāo)準(zhǔn)差Std也可看出,粒子群算法在求解表1郭濤算法和最大引力優(yōu)化算 法優(yōu)化性能對比Table 1 Performance comparison between Guo Tao algoithm and MCOA測試CuoAMGOA函數(shù)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期金林鵬等:用于 函數(shù)優(yōu)化的最大引力優(yōu)化算法661表23種優(yōu)化算法計(jì)算結(jié)果對比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)化算法的平均函數(shù)評價次數(shù)和成功率對比分組”和“引力淘汰”機(jī)制的函數(shù)優(yōu)化方法一最大Table3 Comparison of average function evaluation times and引力優(yōu)化算法,同時給出其改進(jìn)算法.通過對典型測success rates among 3 optimization algorithms試函數(shù)求解,該算法的連續(xù)函數(shù)優(yōu)化能力是令人鼓測試_ SPS0-2007E舞的.函數(shù)FEsRSR95805 15/25 49279 17/25 2384 25/25不過最大引力優(yōu)化算法還需要做進(jìn)-步深人研3771 25/257689 24/252275 25/25究,比如鄰域交叉算子、變異算子距離測度、取值方24837 21/25 49506 17/25 2305 25/25面等,當(dāng)然也可融人其他-些方法,更好地提高算法128150 4/252977 25/25 27239 21/25優(yōu)化性能.另一方面,也需要建立算法的離散模型,fs (min) 53569 21/25 4177 25/257398 25/25以適用于求解TSP、0/1背包等離散問題.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參考文獻(xiàn)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個函數(shù)時數(shù)值計(jì)算不穩(wěn)定.而差分算法不能一-[3] Mori K, Tsukiyama M, Fukuda T. Immune Algorithm with Search-直正確求解f$f2 fs fs J,這5個函數(shù).從標(biāo)準(zhǔn)差可看ing Divensity and Its Application to Resource Alloeation Problem.出差分算法在求解這5個函數(shù)時數(shù)值計(jì)算不穩(wěn)定Trans of IEE Japan, 1993, 113(10); 872 -878相對來說,改進(jìn)最大引力優(yōu)化算法是最穩(wěn)定的,除f4[4] Dorigo M, Maniceao v, Coloni A. Ant System: Optimizatioh by a不能- -直正確求解外,其他函數(shù)求解都很穩(wěn)定,都達(dá)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)化算法均能求解的函數(shù)IEEE Intenational Conference on Neural Networks. Perth, Austral-而言,總體來說,3種算法的平均函數(shù)評價次數(shù)各有in, 1995, IV: 1942 - 1948長短.考慮到隨機(jī)性以及針對不同函數(shù)參數(shù)設(shè)置等[6] Stom R, Priee K. Minimizing the Real Functions of the ICEC 96因素可認(rèn)為旗鼓相當(dāng).從成功率角度來說,改進(jìn)最大Contest by Differential Erolution /1 Proc of the IEEE International引力優(yōu)化算法相對來說是最穩(wěn)定的,跳出局部極值Conference on Evolutionary Computation. Nagoya, Japan, 1996:的能力也最強(qiáng).中國煤化工Tehnirad Repn.7結(jié)束語Computer Science,' 1995:CHC N M H Gi Eeex. Depatment of8] Webster B L Solving Combintorial Opimization Problems Using a本文受萬有引力現(xiàn)象啟發(fā),設(shè)計(jì)出基于“引力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(郭海.演化計(jì)算與優(yōu)化博士學(xué)位論文.武漢:武漢大學(xué).計(jì)算[11] Chuang C L, Jiang J A. Integrated Radiation Opimization; In-機(jī)學(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ì)算智能一-模擬進(jìn)化計(jì)算. 北京:高等教育出版社，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-第十三屆中國機(jī)器學(xué)習(xí)會議(CCML2011)征文通知由中國人工智能學(xué)會機(jī)器學(xué)習(xí)專業(yè)委員會和中國計(jì)算機(jī)學(xué)會人工智能與模式識別專業(yè)委員會聯(lián)合主辦,福建師范大學(xué)承辦,福建農(nóng)林大學(xué)、武夷學(xué)院協(xié)辦的“第十三屆中國機(jī)器學(xué)習(xí)會議(CCML2011)”將于2011年8月6日至8日在福建武夷山召開。該系列會議每兩年舉行- ~次 ,現(xiàn)已成為國內(nèi)機(jī)器學(xué)習(xí)界最主要的學(xué)術(shù)活動。根據(jù)中國人工智能學(xué)會要求,該會議從2011年起改為每逢奇數(shù)年舉行。此次會議將為機(jī)器學(xué)習(xí)及相關(guān)研究領(lǐng)域的學(xué)者交流最新研究成果、進(jìn)行廣泛的學(xué)術(shù)討論提供便利,并且將邀請國內(nèi)機(jī)器學(xué)習(xí)領(lǐng)域的著名學(xué)者做精彩報(bào)告。一征文范圍(但不限于)機(jī)器學(xué)習(xí)的新理論、新技術(shù)與新應(yīng)用特征選擇人工生命人類學(xué)習(xí)的計(jì)算模型流形學(xué)習(xí)與降維模糊集與粗糙集計(jì)算學(xué)習(xí)理論基于案例的推理多Agent系統(tǒng)中的學(xué)習(xí)監(jiān)督學(xué)習(xí)增量學(xué)習(xí)與在線學(xué)習(xí)模式識別非監(jiān)督學(xué)習(xí)對復(fù)雜結(jié)構(gòu)數(shù)據(jù)的學(xué)習(xí)信息檢索半監(jiān)督學(xué)習(xí)增強(qiáng)學(xué)習(xí)系統(tǒng)可理解性生物信息學(xué)強(qiáng)化學(xué)習(xí)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)語音、圖像處理與理解多示例學(xué)習(xí)聚類自然語言理解:神經(jīng)網(wǎng)絡(luò)生物特征識別中國煤化工集成學(xué)習(xí)進(jìn)化計(jì)算MHCNMHG多策略學(xué)習(xí)(下轉(zhuǎn)第714頁)