用于函数优化的小世界优化算法

第39卷第9期西安交通大学学报Vol.39 No92005年9月JOURNAL OF XI'AN JIAOTONG UNIVERSITYSep. 2005用于函数优化的小世界优化算法杜海峰，庄健， 张进华，王孙安(西安交通大学机械工程学院，710049, 西安)摘要:借鉴小世界现象的有关机理,构造了不同的小世界优化算子,主要包括局域短连接搜索算子和随机长连接搜索算子.将优化过程视为在搜索空间(网络)中从候选解向最优解的信息传递过程,利用小世界现象有效信息传递的有关机理实现了-种新的优化算法一小世界优化算法.通过对复杂函数的优化问题进行仿真试验,表明与相应遗传算法相比，新算法可以更好地保持解的多样性,能够有效地避免陷入局部极小值的问题，并在-定程度上克服了早熟和遗传算法欺骗问题,并且收敛速度快，因此具有解决复杂问题的潜力.关键词:小世界现象;优化算法;函数优化中图分类号: O224文献标识码: A文章编号: 0253-987X(2005)09-1011-05Small-World Phenomenon for Function OptimizationDu Haifeng，Zhuang Jian，Zhang J inhua，Wang Sun 'an .(School of Mechanical Engineering, Xi an Jiaotong University, Xi an 710049, China)Abstract: Inspired by the mechanism of small- world phenomenon，some small- world optimization opera-tors, mainly including the local short- range searching operator and random long range searching operator，were constructed. The optimization was considered as a process where information transmits from candi-date solution to optimal solution in search space ( networks). And a new optimization algorithm， smallworld optimization algorithm (SWOA)，was explored on the basis of the effective information transmissionmechanism of the small- world phenomenon. Compared with the corresponding genetic algorithms， thesimulated results of some complex functions optimization indicate that SWOA enables to enhance the diver-sity of the population with a higher convergence rate and avoid the prematurity and genetic algorithm de-ceptive problem to some extent.Keywords: small- world phenomenon; optimization algorithm; function optimization小世界现象源于社会心理学家Milgram在20问题，也迅速成为人工智能、复杂性理论探讨的热世纪60年代有关追踪美国社交网络中最短路径的点,其研究成果已经在互联网控制[3]、爱滋病传播预研究.相关结果表明，在社交网络中存在着短路测41和生物学蛋白质网络动力学研究[5]等许多领域径,即人们只要知道自己认识的人,就能很快地把信得到了成功的应用，但优化领域中有关小世界现象件转发到任何远方目标，这-现象也称为六度分离的讨论和成果还少见报道.问题. Watts和Strogatz1998年在Nature杂志.上发优化变量精度确定以后,优化空间就是优化变表的论文[2],使得小世界现象逐渐被计算机科学家量组成的网格(络)空间,因此本文将优化过程视为重视并被迅速上升为网络论,并有望成为继系统论、在搜中国煤化工解向最优解的信息传递信息论和控制论之后与计算机相关的重要理论.这过程YHCNMHQ信息传递的有关机理一涉及社会学、数学和计算科学问题的多学科交叉来构造新的优化搜索算法.本文首先介绍了小世界收稿日期: 2004-11-25.作者简介:杜海峰(1972~),男,副教授.基金项目:陕西省自然科学基金资助项目(2004F29)1012西安交通大学学报第39卷现象的一般原理,并基于小世界原理来重新描述优问题的求解精度,由x1-x2组成如图2所示的搜索化搜索过程,然后在构造小世界局域短连接搜索算空间,x、x2只在圆圈处取值.不失一般性,设点T子和随机长连接搜索算子的基础上,探讨了一种小是最优解,B是初始候选解,优化问题P的求解过世界优化算法(SWOA) ,最后以函数优化问题为例，程就是从B到T的搜索,可以视为图中虚线示意的对比了小世界优化算法和相应遗传算法的有关性从B到T的信息传递过程.上述优化搜索网络与能.Watts和Strogatz构造的带有多个随机连接的二维格点小世界网络[2]非常相似,因此如果在搜索过程1小世界网络与优化过程考虑小世界效应，即在局部搜索(局域短连接)的基小世界现象揭示了客观世界许多复杂网络(如础上,引入全局随机搜索(长距离随机连接),并强调社会网络)运动中最为有效的信息传递方式,即一个局部行为导致的全局性结果,即可以构造具有小世高度聚集的包含了局部连接节点的子网,连同一些界效应的优化搜索算法一小世 界优化算法.随机的有助于产生短路径的长距离随机连接就可以提高信息传递效率.小世界现象目前还没有精确的。候选解定义,一般认为,如果网络中两节点间的平均距离L随网络节点数目N成对数增长,即L∞lnN,则称该网络具有小世界现象.Watts和Strogatz的小世界网络是从规则网络向随机网络过渡的中间网络形态[2].图1以一维环状点阵为例来说明这一网络的构造方法. 在- -个有T:最优化解; B:初始侯选解N个节点环状的网络中,每个结点向与它最近邻的图2二维空间搜 索问题的节点网格K个结点连接出K条边(如图la所示),对图la中的每条边,以概率p改变它的目的节点来重新连2基于小世界原理的函数优化算法接,并保证没有重复的边出现.当p=0. 05时,上述网络的变化如图1b所示,当p=1时,如图1c所示.社会网络有关小世界效应的试验已经证明了在需要特别指出的是，上述构造过程需满足N》K》局部连接中加入随机长连接时,信息传递更加高效lnN》1,其中K>》InN是为了保证随机网络可以被和实用，因此构造小世界优化算法的要点应该是合连接.适的局部搜索策略和全局搜索方法.2.1基本定义考虑到算法的有效性和效率以及Milgram相关社会学试验的设计[1],算法中参与搜索或信息传递的起始点应该是一个候选解的集合而非单点. S称为传递节点集合,简称节点集,节点s=s...s.,s∈S,也是x的编码,记为s=e(x),而x称为s的解(a)规则网络(b)小世界网络(c)随机网络图1小世界模型的构造过程(N= 20,K=4)码,记为x=e -+(s),其中e和e -1分别表示编码和解码方式.一般将s位串分为m段,每段长为l,由图1可见，小世界网络是-个有局域聚集的l=2I,每段分别对应x;的编码.在实践中,常短连接子网连同一些由长距离随机连接构成的网络.Kleinberg认为,小世界问题是关于路由算法的用的节点编码形式有二进制和十进制，本文采用0-效率问题,可完全依靠本地信息来找到到达目的地中国煤化工-1-1-0-1-0-0 即表示的有效路径”.某节MHCNMHG考虑目标函数f(x) ,d≤x≤u的最小值优化问小世界搜索空间记为集I,即s∈I;S={s;,s2,题P,其中x=xz....ER”,d= (d,d,.，...为 s的n元组.对于P,定义信息传递的目标集dm }和u={u,u,,um }是对应自变量的可行解区T={s∈I:f(e+(s))=f*=间,即x;西酶数据,=,2,..,m.当m=2时,考虑min(f(x):d≤x≤u)}(1)第9期杜海峰,等:用于函数优化的小世界优化算法1013式中:f*是目标函数f的最优值.对于S,0(S)=|S与有效，本文借鉴进化计算中的倒位操作来构造r.∩T|表示S中包含的最优解个数.算法2设定全局长连接概率 p和e.定义d(s,s;)=lIs,-s,lI ,为s,,s;∈s间的距begin离,对于二进制编码-般采用海明距离,而十进制编码多采用欧式距离.把节点s;的e邻域节点集合定repeat义为s;(k)←-s;(k)ζ(s;)= {s,10< |s-s;|I≤l;s,∈S} (2)p←rand(0- 1)并记ζ(s;)|为ζ(s;)的元素数目;ζ(s;)为s;的非lif pe.ζ(S)= {s,|l< Is,-sll; s,∈S} (3)s,(k)←-s;(k)|",进-步地如果s;ET且e(ζ(s;))=|ζ(s)∩T|=0，end if那么一定有i←i计+10(ζ(s;)=| ζ(s)∩TI≥1(4)until i=n2.2主要算子end局域短连接搜索算子ψ的主要作用是将信息式中:rand(0一1)表示产生0到1之间均匀分布的从s;(k)传递给ζ(s;(k))中与T最靠近的节点s;(k随机数;s(k)|"表示颠倒s;(k)中μ位到r位之间的+1),且e比较小,记为s;(k+1)←Y(s;(k)). 实践字符顺序,例如中,由于Iζ(s;(k))|很大，例如对于20位二进制编s;(k) 1 0101100 1100-110011010100码的节点s;(k),Iζ (s;(k))|=19,而|ζ(s;(k))|=ζ (s;(k))|+C器,因此一般随机地从ζ(s;(k))中取r中的力相当于进化算法中倒位操作的倒位n(k)》2004年第9期目录选登1.悬浮轴承参数不确定控制的研究.... 刘淑琴,富志宏,陈大融(1009)2.基于广义密度函数的随机模糊结构广义可靠性分析胡太彬,陈建军,马芳,等(1022)3.基于角色的访问权限控制在ERP系统中的应用中国煤化工蔡宗琰,王宁生(1025)4.一种新的散乱数据边界点提取方法:MYHCNMH G尧宇,张树生,等(1037)5.大变形柔顺机构的驱动特性研究.............................. 李海燕,张宪民,彭惠青(1040)6.纳米氧化物/聚四氟乙烯复合材料的研究黄岳元,任杰(1051)7.制造系统智能前端的研究..............................陆宝春,张卫,孙宇(1057)8.间歇性弟屡赚眺机器人落地冲击及稳定性分析............... 刘壮志,朱剑英,吴洪涛,等(1068) .