用于函数优化的最大引力优化算法

第23卷第5期模式识别与人工智能Vol.23 No.52010年10月.PR&AIOct 2010用于函数优化的最大引力优化算法*金林鹏李均利魏平陈刚(宁波大学信息科学与工程学院宁波315211)摘要提出一种基于牛顿万 有引力定理的函数优化方法一最大引力优化算法. 该算法通过“引力分组"和“引力淘汰”过程更新搜索体.文中给出4个引理来描述算法的数学基础，同时也给出算法的收敛性证明.此外还对该算法进行改进.最后与粒子群算法、差分算法、郭涛算法进行比较,数值结果显示该算法在解决连续函数优化问题具有较高的性能.关键词函数优化,最大引力优化算法( MG0A) ,模拟进化计算,万有引力中图法分类号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中国煤化工，*国家自然科学基金重点项目(No.60832003) 、浙江省自然科学基金项科学基金项目(No.2009 A610089)和宁大学王宽诚基金项目资助MYHCNMHG收稿日期:2009 -04 - 13;修回日期:2010-04 -09作者简介金林鹏,男,1984 年生，硕士研究生,主要研究方向为最优化方法、演化计算. E-mail: kinis1984@ 163. com.李均利，男,1972年生，研究员，博士生导师，主要研究方向为演化计算、医学图像处理、视频处理等.魏平，男,1978年生，博士,主要研究方向为演化计算医学图像处理等.陈刚,男,1963年生，博士,教授，主要研究方向为系统仿真非线性系统分析等。654模式识别与人工智能23卷1引言Kang等[I5]提出的基于引力的粒子群算法(ParticleSwarm Optimization Based on Gravitation Field Model,优化是一个古老的问题，追求最优目标一直是CPSO) ,则是在原粒子群算法的基础上加上由引力人类的理想,长期以来.人们对最优化问题进行不断产生的加速度项.的探讨和研究,发展了许多确定有效的优化方法,如以上四种算法均是基于“位置+位移量”计算牛顿法、共轭梯度法、单纯形法等.然而很多优化问模型(同粒子群算法类似),受万有引力公式启发,题的函数性质十分复杂,解析性质不清晰,甚至可能模拟动态的物理运动过程.唯--不同的是他们的更没有具体的函数表达式.传统优化算法在求解这些新公式,问题,无论是在计算速度、收敛性、初值敏感性等方本文提出的最大引力优化算法( Maximal Gravi-面都远不能满足要求.20世纪50年代中期出现仿tation Optimization Algorithm, MGOA)亦是基于牛顿生学学科,人们很快从生物进化的机理和仿生学中引力公式,不同的是,1)该算法不是模拟一个动态.得到启示,提出多种求解优化问题的模拟进化方法,的物理运动过程,而是模拟一个物理现象:在-一个有如遗传算法"、模拟退火算法[2]、免疫算法']、蚁群很多物体的空间中,最大引力值存在于质量最大物算法[4]、粒子群算法'5]、差分算法[°1等,并取得巨大体的附近;2)其计算所得的引力仅仅是一个测度,成功.并不是真正意义的引力,同时计算引力测度是为后对于引力模拟局部搜索( Gravitational Emulation来“引力分组过程”提供依据;3)其计算模型是基于Local Search, GELS)"的研究,最初概念性框架是“ 交叉变异"(同遗传算法类似),而不是基于“位置由Voudouris 和Tsang 于1995年提出，Webster[8])发+位移量”;4)该算法从确定交叉、变异的个体到确展了它.该算法可形象描述为一个在介质上滚动的定淘汰个体,均是基于万有引力现象,同遗传算法球,介质上有很多的坑,坑有深有浅球在滚动过程“优胜劣汰"思想有着本质的区别.中由于介质摩擦力而逐渐失去动力.如果该球正滚进坑里,它就获得了动力;如果该球正滚出坑,它将2基于牛顿引力公式的最大引力失去动力.算法的理念是由于引力的影响,球最终会优化算法停留在某个坑里. Balachandar91 在Webster 的基础上提出随机引力模拟搜索( Randomized Gravitational2.1基本概念Emulation Search, RGES)算法,克服其收敛速度慢、解的质量不高等问题,使其求解能力大大提高.这3万有引力是两个具有质量的物体间相互吸引的种引力模拟搜索算法用于求解旅行商向题(Trave-作用,存在于任何有质量的物体之间.两个物体间的ling Salesman Problem, TSP)等组合优化问题,求解引力大小,跟它们之间质量的乘积成正比，跟它们的机制基于离散的路径信息，与本文提出的用于函数距离的平方成反比,用公式表示为优化的最大引力算法关系不大,故这里不具体展开F=G",(1)说明.Hsiao[10]提出的空间引力优化(SpaceGravita-其中,C = 6.672为引力常数,m,、m2分别为两物体tional Optimization , SGO)是基于爱因斯坦相对论和的质量,r是它们之间的距离.牛顿引力公式,模拟行星群在宇宙中漂移以找到最考虑求解无约束函数优化问题:Z = maxf(X),大质量的行星个体,时空几何的变化导致行星加速或减速,从而使行星漂移.Chuang["]提出的累积辐搜索空间D = {X|l≤x;≤u,i = 1,2,.*,n}，射优化( Integrated Radiation Optimization , IRO),是X =(x,",x,)",4,u;(1≤i≤n)分别为每一基于“一个置身于引力场的行星的运动是由空间中维取值的上下边界f(X)为目标函数.将万有引力所有其他行星辐射引力波,共同作用的情况"这一用于函数优化问题，做法是将搜索空间D中的每个事实而设计的. Rashedil2-14)提出的引力搜索算法点看作中国煤化工i量m分别为(Gravitational Search Agorihm, GSA),通过计算每CNMHG(2)个粒子与其他所有粒子之间的引力值,并将所有这m' = nV(A)些引力值以随机加权方式计算总和,求得该粒子所h(x)为-维尺度变换函数,满足对Vx∈(-∞,受到的引力,进而求得加速度,再更新速度和位置.+∞),h(x) > 0,并且严格单调递增为了降低计算5期金林鹏等:用于 函数优化的最大引力优化算法655复杂度,将搜索空间D中任两个点间的引力简化为成新物体C.显然P;的个数决定新物体C的个数,Fr.2 =h(f(X)) . h((X2))3)故共生成n个新物体C.记新物体群ζ= {C, 1≤1.2 + K。i≤n},那么其中,X,X2 e D,r.2 为距离测度,Ko为很小的数,C=(U, {F.(P.)}) U(_ u{F_(P:)})防止式(3)中分母为零.虽然形式变了,但本质上跟式(1)是一致的,因为我们需要的只是两点间的引iter = iter + 1.力测度,而不是真正的引力值.step4对每个新物体C(1≤i≤n), 由于每为说明方便,下面提到的物体适应值其实就是个浮动物体与其所选择的参考物体之间都有距离测物体的质量,或者说是目标函数值的某-尺度变换度,距离测度最小的一对物体中质量小的物体即为函数值要淘汰的物体,记为E,其中2.2算法描述r咖= min(yj, 1≤j≤n2)在最大引力优化算法(MC0A)中涉及到参考lhk = min({j|rqJ =喇，1≤j≤n})物体群R、浮动物体群N(两者统称为群体RNV)和新fRm，ifR(m) ≤Nu(m)物体群C,记R(X)和R(m)分别为参考物体R的E: =lNx，otherwise位置和质量,N,(X)和N,(m)分别为浮动物体N;的位置和质量, C;(X)和C;(m)分别为新物体C;的位如果C(m) > E(m) ,C;就取代E,再用算法流程置和质量,RN,(X)和RN,(m)分别为群体中物体中step2方法更新s;值;否则不变RN,的位置和质量. MGOA的计算步骤如下.step5若连 续IterThreshold迭代次数内均没step 1随机产生参考物体群R和浮动物体群有变异发生,则通过变异算子生成新物体C. ,更新,其中方法同step 4.R= {R,1≤i≤n}step6 若适应值最大的max{m,n2} +1个物W= {N,1≤j≤n}体,其平均适应值没有增加,则令iter = iter -1.若满足终止条件则停机，否则将这n + n2个物体重新令iter =0.step2计算每个参考物体R(1 ≤i≤mn)和随机选定为参考物体和浮动物体,转step 2.每个浮动物体N(1≤j≤n)之间的引力测度Fj2.3算 法说明和距离测度r.s(距离测度可以是1-范数2-范数、F-2.3.1物理意义范数或模糊距离测度等):由式(1)可知,引力值较大的时候,要么有质量τj= |R;(X) - N(X) I ,较大的物体,要么两物体间的距离较小由于本算法R.(m) x N,(m)在每次迭代过程中淘汰引力相对较大并且距离测度rj+ Ko最小的一-对物体中质量小的物体，这就保证在引力每个浮动物体N,(1≤j≤n)选择和其引力最大的相对较大的物体附近往往存在质量大的物体.正是参考物体r,其中基于这一思想,构造出最大引力优化算法从函数优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,和所有选择它的浮动物体组成的集合,最大引力优化算法同遗传算法类似，是通过交P: = {R} U {N|;j = i,1≤j≤n}.叉和变异来更新群体，而不是像粒子群算法通过位对于每个参考物体R,可能至少有一个浮动物体选置和位移量、差分算法通过差向量,来更新群体.不择它,也可能没有浮动物体选择它这样P:就分为过需要说明的是,遗传算法的设计理念是基于生物两类,记p"和P"分别由这两类P;所组成的集合:进化的“优胜劣汰”思想,通过淘汰群体中差的个: ,优秀的个体通过P" ={R|{N|s =i,1≤j≤n}≠0,1≤i≤n}杂交YH中国煤化工个体遗传算法的=P-p°这种让CNMHG在数值实验中也.设F。为邻域交叉算子,F.为变异算子,对P"中的取得很大的成功不过遗传算法也存在不足,如算法元素使用F.算子,对P"中的元素使用F算子,生不稳定、早熟等.而最大引力优化算法的设计理念是656模式识别与人工智能23卷基于- -种万有引力现象,核心思想是“引力分组”和a个物体那么只要(),2.,"",入.) = (1,0,.",0)，“引力淘汰”机制,而这两点均是通过万有引力这一λ;是RN。(X)的构造系数,就可再次搜索到最优物普遍现象而导出的,跟遗传算法的“优胜劣汰”思想体不妨设浮点数编码精度为e,Flim中(入1,λz,有着质的区别.应该这么说,遗传算法和最大引力优..,入.) 的取值有V.m种,那么V,ia必然小于化算法是设计理念的区别,至于交叉算子和变异算([(u"-l")/e])* ,因为Eλ= 1还制约着(A，子,两者可互相借鉴2.3.3邻域交叉算子 F.的选取Az,.. ,入。)的取值,由此可知V,iwn是有限数.当RN。.根据最大引力优化算法的构造思想,任何邻域是参考物体时,情况类似，相应参数不妨设为V.,uw,交叉算子均可适用下面介绍一种邻域交叉算子,最于是有早见于郭涛算法[06.。设Xx,X,.",X,∈R", \\z,p{r"(RN)≈丽uE...∈R,则2Pr.一+p, Pr,umn一>0, (4)[X'= 2\X其中∈E*.需要说明的是，在实际演化计算中,由非最优物体搜索到最优物体的可能是存在l2λ:=1,l°≤λ;≤u° ,I" <0,u' >1的,故实际搜索到最优物体的概率要比式(4)右边.其中,I"、u"为λ;取值的上下界,我们将其记为的式子要大,而当z > 1或多最优值问题时,其概率rLiner.就更大. Vj.V,urn P.iw是变量,每次迭代可能都不一样,但不论怎么变换,式(4)总是成立的. 证毕3最大引力优化算法的数学基础注“[x]"表示对x向上取整.那么由引理1我们能不能得到结论:及收敛性证明p{T(RN)≈RN*t!} > 0.我们有如下引理.引理2对于单最优值问题而言 ,有定义1若群体RN 有z(z≥0)个物体是全局p{T(RN)→R++}最优物体(这里X*和m*分别表示全局[>0，1≤z≤max{nj,n2|最优物体的位置和质量) ,则记为RN'(对多最优值=0，z > max{n,n2} .问题,X”不唯- -).证明对于单最优值问题而言,任意两个最优定义2记 T,为引力分组算子,对应算法流程物体之间的距离测度是最小的MGOA中每个浮动中step 2,T。为构造算子,对应算法流程中step 3,T.物体与其所选择的参考物体之间都有一个距离测为淘汰更新算子,对应算法流程中step 4.我们分别度,而淘汰更新算子T.淘汰的是距离测度最小的一记操作算子T和T'为T=ToTq°T,T"= Tp° T,对物体中质量小的物体.若参考物体群和浮动物体引理1 设最大引力优化算法某- -次迭代,群群中都有最优物体,由于最优物体间引力测度最大，体为RN(z≥1),为全局最优物体,则相互选择,并且距离测度最小,故淘汰更新算子T,p{T'(RN)→RN uC*} >0,淘汰的是一一个最优物体由于搜索到的新物体其适其中,∈C,"→"表示“演化得到”的应值不可能比最优物体大,故这种情况下群体中就意思.不可能再增加最优物体.证明对于RN(z≥ 1) ,不妨设物体RN。是最要证明p{T(RN)≈RN*#} > 0,首先要保证能优物体,它成为浮动物体的概率p; =n2/(n, +n2),搜索到最优物体,其次淘汰物体能被最优物体替换成为参考物体的概率p, = n/(n| + n2) ,并设它成掉(由前面分析可知,只要群体RN中最优物体不同为参考物体后被浮动物体选中的概率为P.,uan,则时出现在参考物体群和浮动物体群,就能保证淘汰MGOA通过邻域交叉算子在RN。附近搜索的概率为物体被替换).Ppr+p, xp.ur这里以Flunmr为例给出证明,其他F。可2概率,由引理1可类似证明,因为任何邻域交叉算子的一个共同特点知Pa中国煤化工浮动物体群不同是在给定物体的附近搜索时有YHCNMHG当RN。是浮动物体时,必然选择某-参考物体,p{T(RN)≈Ri'*} =Pandeu .pm.(5)而其它浮动物体也可能选择它,不妨设该组一共有当1≤z≤max{n,nz}时,至少存在一种排列,金林鹏等:用于函数优化的最大引力优化算法657使参考物体群和浮动物体群不同时出现最优物体,群体RN通过多物体交叉方式和变异方式生成新物故Pm >0,式(5)大于0;当z> max{n,nri时,不论体的概率这样排列，参考物体和浮动物体都至少有一一个是最引理4最大引力优化算法的交叉概率p。 和变优物体,故pm = 0,式(5)等于0.结论成立证毕异概率pm均大于0.相比单最优值问题而言,多最优值问题中“任证明由引理3可知,MGOA在-一次迭代中多意两个最优物体之间的距离测度是最小的”这一结物体交叉至少发生- -次,可知p。> 0.不过MGOA是论将不再成立.不过当1≤z≤max{n,n}时,式不能保证变异- -定 发生的,但由于算法流程中step 5(5)大于零的;而当z > max{n,m}时,若群体RN的存在,可知pm > 0.故结论成立.证毕中max{n,n2} + 1个物体都是同一位置的最优物由文献[17]可知变异算子可搜索到整个解空体,式(5)等于零(以上证明同单最优值问题,即引间D,而MGOA中pm>0,故MGOA能搜索到整个解理2).若不存在max{n,n2}{ + 1个物体均是同- -位空间.置的最优物体,那么总可以找到一种排列使得同一定义4设有nm 个个体的群体RN ,其适应值最位置的最优物体不同时出现在参考物体群和浮动物大的n.个个体组成主群RN ,记W(RNx ).为1时刻体群,而这就给其他非最优物体被替换提供了条件.主群中所有个体的平均适应值,Q为平均适应值的不过这些非最优物体能不能更新为最优物体,跟优集合,若算法t时刻的W(RN%),满足化问题和迭代情况有关lim W(RN"), =f'，f'∈Q由以上分析可知,最大引力优化算法求解多最优值问题时,运行- -次可能只找到1个,也可能是2则称算法收敛到f' .个或更多.另外,引理2及多最优值问题的分析也解定理1浮点编码下 的最大引力优化算法,所释算法step 6中为什么是适应值最大的max{n; ,n2}有可能的RN所组成的集合是有限集,平均适应值集+1个物体的平均适应值,而不是整个群体的平均适合Q也是有限集.应值.我们记RN,(X) = (.xe2x.....)，,引理3不考 虑step 5,最大引力优化算法在一k = 1 ,2,.",nm,则我们有1≤x≤u,1≤i≤n.次迭代中多物体交叉至少发生一次.当n =1时,变采用浮点编码,由于编码精度总是有限的,不妨设为异不发生;当n > n2时,在-一次迭代中变异至少发&,则%,的取值情况有[(4; - l,)/e] 种可能，生n-n次;当1 n2 时,在一次迭代中至少有8(F5) =jO,n-n个参考物体没有被浮动物体所选择,故变异l2M+1-5-石，了≠后至少发生-n次.当1 m中国煤化工≠f时，时,变异的分量相对多-点,n,》n近于随机搜索8(当n≤n时,多物体交叉的分量相对多一点,几=1TYHCNMH G(2M+1-万-万)没有变异发生.= (2M+1--f3) +(2M+1 -f一石)定义3交叉概率p。 和变异概率Pm分别表示= 8(fiJ5) +8(rJ5),658 .模式识别与人工智能23卷当凯=无或，=五时，显然均是最优物体.证毕8(元后) = 8(5) +8(2J5)，由此可知8是-一个度量.证毕4 n和n经验取值的研究定理3 (Q ,8)构成完备的度量空间.证明首先,平均适应值集合Q非空,由定理2最大引力优化算法中n、m的取值直接影响其知δ是一个度量,因而(Q,8)构成度量空间.又由定理优化性能,引理3已从理论上给出分析.下面我们以1知，集合Q是有限集,因而(Q,8)中的任意CauchyKowalik Problem( KL)函数为例,从实际计算性能序列都收敛,从而(Q ,8)构成完备的度量空间.证毕分析一下.Banach压缩映射定理设(Q,8) 为完备度量fxa=(a.--x(1 + x26.)空间,g: Q→Q为一压缩映射,则g有且仅有一个不(1 +xb, +xob)动点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最大引力优化算法依定 义.4收敛到全[b,] = [0.25 ,0.50,1 ,00,2. 00 ,4.00,6.00,8.00,局最优10.0,12. 0,14. 0,16. 0],证明最大引力优化算法将一个状态的群体(x,z,x,x)≈(0. 192 ,0.190,0. 123 ,0.135),演化到另一个状态,如果定义群体状态的某种测度，fuin≈0.000 307 48.并保证每一个状态的群体测度的唯一性，那么我们用MGOA对该函数进行优化,停机准则MCOA可看作是测度空间到测度空间的映射.对于|f-f"|< 10-8 或函数评价次数超过150 030.由n个参考物体和n个浮动物体组成的群体RN,MGOA的各参数设置如下:F. = FLum",l" =-0.45,定义群体t时刻的测度为W( RrN+q(a1.2)).因为u° = 1. 45 ,Fm为随机搜索, lterThreshold = 5000,距MCOA中如果某-代该测度相对于上- -代没有得到离测度为2-范数,Ko = 10-10,n,n2分别取1,2, ..增长,则不进入下一代,而是反复使用T,I、T.算20,每-对n, ,n2做25次独立随机实验.子,直到该测度得到增长,才进入下一代这就保证由图1可知,当n2/n大约大于2时,平均函数每个状态的群体该测度的唯一性, 于是MGOA可视评价次数少.这里要说明的是,当n =1,n =8时，为一映射g: Q→Q,即平均函数评价次数是最少的,1 200左右然后随着n2的增大,评价次数逐步增加,这一-点跟n > 1的情对Vf∈Q,g(f)比f至少增加- -个浮点编码况不太- -样(图 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对平均函数评价次数的影响量空间,g是-一个压缩映射.所以MGOA必定收敛于Fig.1 Eft of n and n on average function evaluation唯一的不动点,即timeslimlW(N1w),. = lng(Nm2*)o) =F",中国煤化工且f"与初始群体的测度w(riq(p.n.2)2)无关,显CNMHG合事实上当η >n时,x又仅承时万里们刚又些而当n > n2时，然f'就是全局最大值.那么由测度的定义可知,此变异搜索的分量相对多一些在数值实验中我们采时群体RNV中适应值最大的max{n,nz} + 1个物体用随机搜索作为变异算子,对MGOA优化性能的贡5期金林鹏等:用于 函数优化的最大引力优化算法659献不大,反而增加评价次数,只是为了保证能搜索到2) Shekelg Foxholes Function:整个解空间. n = 1时变异发生的次数很少.当nz≥8时,由n + n个个体所组成的群体已能搜索到最fh =[k+2E(x-ay)°]优解,故平均函数评价次数较低当然,n和n2对不同的函数有不同表现，但是勾右∈[-65.536,65.536],K =500, C =j,我们通过其他函数测试，得出如下经验结论.取n[anj] = 16[((j-1) mod5) -2],≈2n,n≠1;如果n; ,几取小的值时不能计算的,[arj] = 16([(j-1)/5] -2),再将n,几取大点试试;当n = 1时如果能计算,那(划,x) = (-32, -32),fain = 0. 998 004.3)Two-dimensional Function:么其平均函数评价次数是最少的.fs =- [20 + xcoay + ysinx],x∈[0,10],y∈[- 10,0],5改进 的最大引力优化算法(x,y) = (10, - 6.337614),f.in =- 33. 432 987.4)Two dimensional Function:目前,在连续函数优化研究领域,粒子群算法和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.两个版本,前者收敛速度相对要慢,但计算性能较稳5) Shubert Function:定;后者收敛速度较快,但计算性能不稳定差分算法的各个版本也都有类似的问题.{s= I2i.co[(i+1)x; +门,jI如果我们能设计出一-种方案,其收敛速度相对划,名∈[- 10,10],较快,并且计算性能也较稳定的话,那就有很现实的f.. =- 186. 730 909,fm = 210.482 29.应用前景.为此我们对最大引力优化算法进行改进，6)Two-dimensional Function:在原算法step 5和step 6之间插人-一个计算步:“从群体RN中选出适应值最好的ns个物体,对它们使fo=(b+(+) +(好+站)，用邻域交叉算子F.产生新物体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 ;否则不变”.同时将原算法step 67)Trap Function:中“适应值最大的max{n,n2} +1个物体的平均适0≤x≤0.5应值”改为“整个群体RN的平均适应值".a-ax,0.50.5遗传算法,这里就不具体展开论证a >b,c> 1,x∈[0,c],x =0.5,fm = a/2.这是本文给出的一一个陷阱函数,a和b相差越数值仿真实验小,c越大,优化难度越大.数值实验中我们取a =50,b =6,c = 6 000.实验选用平台是Pentium Dual E2200@8)De Jong F2 Function:2.2GHz,1CB内存,VC6环境，选取典型的f = 100(对-x2)* +(1 +x)',BenchMark测试函数,其中有些函数极难求得最划,∈[-2.048,2.048], (x,x2) = (1,1),优解.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卷.郭涛算法是一种改进的遗传算法,它去掉变异的原因是若迭代次数上限设定值相对于待求解的问算子,并采用多父体杂交方式生成新个体,采用经典题太小,则求不出解,而实际上郭涛算法能求.遗传算法中的“优胜劣汰”计算模型.而最大引力优3)粒子群算法SPSO-2007.粒子群算法的各种参化算法是基于“万有引力”计算模型,但同样采用多数设置如拓扑结构、更新模型等极大地影响着算法的父体杂交方式生成新个体,并且在数值实验中均选性能,从1995年开始提出到现在,大量学者如Shi、用FLmeu交叉算子.故将郭涛算法和最大引力优化算Clerc等进行研究工作Particle Swarm Central (http:法作对比，就比较有意义,同时两者的对比,其实质//www. particleswarm. info/)提供的SPS0-2007, 是是遗传算法“优胜劣汰"计算模型和“万有引力”计性能不错的版本这里采用该版本,设定种群规模为算模型的比较.30 ,停机条件同MG0A,其他参数保持不变引言中提到的SGO、IRO、GSA GPSO这四种算4)差分算法DE.种群规模NP = 30,其他参数法,虽冠以“引力算法”,但跟最大引力优化算法是采用Yang等[18]提到的通常设置,CR = 0.9,F =从属于完全不-样的体系.它们均基于“位置+位0.5,目前差分算法有五个版本的变异策略,其中移量”计算模型,而这种计算模型最成功的案例莫DE/rand/1和DE/current to besU/2性能较好,这里过于粒子群算法.同时粒子群算法和差分算法是目采用DE/rand/1变异策略,停机条件同MGOA.前连续函数优化领域的主流算法,故将他们同最大5)改进的最大引力优化算法MMGOA.ny = 8,引力优化算法作对比其他参数同MGOA.每个测试函数做25次独立随机实验,各优化算标准差Std、成功率SR反映算法的稳健性以及法具体参数设置如下.跳出局部极值的能力,而平均函数评价次数FEs反1)最大引力优化算法MGOA.参考物体n; =映算法的计算收敛速度.由表1可知,郭涛算法不能10,浮动物体n2 =20,F。=Fu",I" =-0.45,u" =一直正确求解fs J,.对fo而言,GuoA没有一次正确1.45,Fm为随机搜索算子，距离测度为2-范数,求解.相对来说, MGOA优化性能较稳定,基本上都IterThreshold = 5000,K。= 10-10. 停机准则为:设能正确求解,只不过fs( min)的最差解达不到给定fan是待优化问题的最优解, fue为搜索到的最优精度,即使这样,所求得的最差解精度也已较高在解,若_Lfu-.f..|< 8o或超过最大函数评价次数计算速度方面,MGOA的平均函数评价次数均比150 030,则停机各函数eo设置不相同.GuoA要少,而且是少很多(当然fo除外,因为GuoA2)郭涛算法GuoA.种群规模为30,子空间维度无法计算,故没有比较的意义). .为8,精度e = 10*(见文献[ 16]).郭涛算法本身就具由表2可知,粒子群算法在25次独立随机实验有停机准则,即当种群中最好解和最坏解相差在精度中,不能一直正确求解f fsSs fs(min) Sf,(max)、e之内就停机不过为公平比较,再额外加上MGOA的f。fif,这9个函数,其中f f的最好解和最坏解相停机准则但设定迭代次数上限为无穷大这么设置差较大.从标准差Std也可看出,粒子群算法在求解表1郭涛算法和最大引力优化算 法优化性能对比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期金林鹏等:用于 函数优化的最大引力优化算法661表23种优化算法计算结果对比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种优化算法的平均函数评价次数和成功率对比分组”和“引力淘汰”机制的函数优化方法一最大Table3 Comparison of average function evaluation times and引力优化算法,同时给出其改进算法.通过对典型测success rates among 3 optimization algorithms试函数求解,该算法的连续函数优化能力是令人鼓测试_ SPS0-2007E舞的.函数FEsRSR95805 15/25 49279 17/25 2384 25/25不过最大引力优化算法还需要做进-步深人研3771 25/257689 24/252275 25/25究,比如邻域交叉算子、变异算子距离测度、取值方24837 21/25 49506 17/25 2305 25/25面等,当然也可融人其他-些方法,更好地提高算法128150 4/252977 25/25 27239 21/25优化性能.另一方面,也需要建立算法的离散模型,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参考文献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个函数时数值计算不稳定.而差分算法不能一-[3] Mori K, Tsukiyama M, Fukuda T. Immune Algorithm with Search-直正确求解f$f2 fs fs J,这5个函数.从标准差可看ing Divensity and Its Application to Resource Alloeation Problem.出差分算法在求解这5个函数时数值计算不稳定Trans of IEE Japan, 1993, 113(10); 872 -878相对来说,改进最大引力优化算法是最稳定的,除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可知,对于各优化算法均能求解的函数IEEE Intenational Conference on Neural Networks. Perth, Austral-而言,总体来说,3种算法的平均函数评价次数各有in, 1995, IV: 1942 - 1948长短.考虑到随机性以及针对不同函数参数设置等[6] Stom R, Priee K. Minimizing the Real Functions of the ICEC 96因素可认为旗鼓相当.从成功率角度来说,改进最大Contest by Differential Erolution /1 Proc of the IEEE International引力优化算法相对来说是最稳定的,跳出局部极值Conference on Evolutionary Computation. Nagoya, Japan, 1996:的能力也最强.中国煤化工Tehnirad Repn.7结束语Computer Science,' 1995:CHC N M H Gi Eeex. Depatment of8] Webster B L Solving Combintorial Opimization Problems Using a本文受万有引力现象启发,设计出基于“引力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(郭海.演化计算与优化博士学位论文.武汉:武汉大学.计算[11] Chuang C L, Jiang J A. Integrated Radiation Opimization; In-机学院, 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(徐宗本.计算智能一-模拟进化计算. 北京:高等教育出版社，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-第十三届中国机器学习会议(CCML2011)征文通知由中国人工智能学会机器学习专业委员会和中国计算机学会人工智能与模式识别专业委员会联合主办,福建师范大学承办,福建农林大学、武夷学院协办的“第十三届中国机器学习会议(CCML2011)”将于2011年8月6日至8日在福建武夷山召开。该系列会议每两年举行- ~次 ,现已成为国内机器学习界最主要的学术活动。根据中国人工智能学会要求,该会议从2011年起改为每逢奇数年举行。此次会议将为机器学习及相关研究领域的学者交流最新研究成果、进行广泛的学术讨论提供便利,并且将邀请国内机器学习领域的著名学者做精彩报告。一征文范围(但不限于)机器学习的新理论、新技术与新应用特征选择人工生命人类学习的计算模型流形学习与降维模糊集与粗糙集计算学习理论基于案例的推理多Agent系统中的学习监督学习增量学习与在线学习模式识别非监督学习对复杂结构数据的学习信息检索半监督学习增强学习系统可理解性生物信息学强化学习数据挖掘与知识发现语音、图像处理与理解多示例学习聚类自然语言理解:神经网络生物特征识别中国煤化工集成学习进化计算MHCNMHG多策略学习(下转第714页)