（计算机应用技术专业论文）微粒群优化算法（pso）的改进研究.pdf

摘要 摘要 微粒群优化算法( p a r t i c l es w a m no p t i m i z a t i o n ，p s o 算法) 源于鸟群和鱼群群体运 动行为的研究，是一种新的群体智能优化算法，是演化计算领域中的一个新的分支。它 的主要特点是原理简单、参数少、收敛速度较快，所需领域知识少。该算法的出现引起 了学者们极大的关注，已在函数优化、神经网络训练、组合优化、机器人路径规划等领 域获得了广泛应用，并取得了较好的效果。尽管粒子群优化算法发展近十年，但无论是 理论分析还是实践应用都尚未成熟，有大量的问题值得研究。 针对小生境微粒群算法在处理复杂多峰函数优化问题中存在的一些缺陷，本文提出 一种改进的小生境s n p s o ( s t r e t c h i n g n i c h e p s 0 ) 算法。s n p s o 算法将顺序小生境的思想 引入其中，首先在主群体中应用s t r e t c h i n g 技术，其次对子群体采用解散机制，即当 在子群体中找到一个极值点后把该子群体解散回归主群体，最后设置子群体创建时的半 径阈值，避免子群体半径过大。该算法解决了标准的n i c h e p s o 算法在处理多峰函数时， 极值点的个数依赖于子群体个数及极值点容易出现重复、遗漏等问题。对3 个常用的基 本测试函数的实验表明，新算法( s n p s o ) 在多峰函数寻优中解的稳定性、收敛性和覆 盖率均优于标准n i c h e p s o 。 随后，本文分析了海豚的群智能规则，并且定义“核心 作为团队最好位置的预测， 从而提出了一种海豚伙伴算法，这是一种启发式算法，通过伙伴选择，角色定位和信息 交流确定每个海豚在自己所处团队中的位置，然后团队的领导者要执行对“核心一的探 索，而普通的团队成员要仅仅跟随以加快团队搜索的收敛速度。多个测试函数展现了d p o 的搜索性能，算法在前期能够以很快的收敛速度找到较好的适应度值，并且具有比g a 算法更好的跳出局部极值点的能力。另外，d p o 算法具有小生境思想，因此也具有良好 的寻找多个极值点的能力，测试函数同时良好的展现了算法搜索多个极值点的有效性和 准确性。 关键词：微粒群；小生境；海豚；伙伴；核心；海豚伙伴算法 a b s t r a c t a b s t r a c t p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) i sa ne v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u ed e v e l o p e d b yd r e b e r h a r ta n dd r k e n n e d y i n19 9 5 ，i n s p i r e db ys o c i a lb e h a v i o ro fb i r df l o c k i n go rf i s h s c h o o l i n g r e c e n t l y , p s oa l g o r i t h mh a sb e e ng r a d u a l l ya t t r a c t e dm o r ea t t e n t i o no v e ra n o t h e r i n t e l l i g e n ta l g o r i t h m p s o i s s i m p l e i nc o n c e p t , f e wi n p a r a m e t e r s ，a n de a s y i n i m p l e m e n t a t i o n i tw a sp r o v e dt ob ea ne f f i c i e n tm e t h o dt os o l v eo p t i m i z a t i o np r o b l e m s ，a n d h a ss u c c e s s f u l l yb e e na p p l i e di nt h ea r e ao ff u n c t i o no p t i m i z a t i o n , n e u r a ln e t w o r kt r a i n i n ga n d f u z z yc o n t r o ls y s t e m s ，e t c h o w e v e r , b o t ht h e o r ya n da p p l i c a t i o no fp s o a r es t i l lf a rf r o m m a t u r e am o d i f i e dn i c h ep s oa l g o r i t h mi sc o n s t r u c t e dw h i c ha l l o w su n i m o d a lf u n c t i o n o p t i m i z a t i o nm e t h o d st 0e 倚c i e n f l yl o c a t ea l lo p t i m ao fm u l t i m o d a lp r o b l e m st h a tt h en i c h e p s oi su n r e a c h e d i nt h en e wa l g o r i t h m , t h es e q u e n t i a ln i c h et e c h n i q u ei si n t r o d u c e d f i r s t l y , as t r e t c h i n gt e c h n i q u ei sa d o p t e di nm a i ns w a r m s e c o n d l y , t h ed i s m i s s e dm e c h a n i s mi su s e d i ns u b - s w a r m sn a m e l yw h e nal o c a lb e s to fv a l u ei sf o u n di ns u b - s w a r m s ，t h es u b s w a r m s w o u l db ed i s m i s s e da n dr e g r e s s e dt ot h em a i ns w a t l n a tl a s t , t h er a d i u so fc r e a t e d s u b s w a r m si sc o n f i n e di no r d e rt oa v o i dt h ee x c e s s i v eo fr a d i u s t h en e w s t r e t c h i n g - n i c h e p s oa l g o r i t h mr e s o l v e st h ed i s a d v a n t a g eo fs t a n d a r dn i c h ep s ot h a tt h e l o c a lb e s to fv a l u ed e p e n d i n go nt h en u m b e ro fs u b - s w a r m sa n de a s i l yh a v et h ep r o b l e mo f i t e r a t i o na n dp r e t e r m i s s i o n t e s t i n go ft h ea l g o r i t h mb yu s i n gt h r e eb e n c h m a r kf u n c t i o n s i n d i c a t et h a tt h em o d i f i e dn i c h ep s oh a sh i g h e rp e r f o r m a n c et h a ns t a n d a r dn i c h ep s oi na b e t t o rv a l u ef o u n da n das t e a d yc o n v e r g e n c e b a s e do nt h eb i o n i cs t u d yo nd o l p h i n , p h i l o s o p h yo fd o l p h i np a r t n e ro p t i m i z a t i o n ( d p o ) i sf o r m u l a t e da n das o - c a l l e d n u c l e u s i si n t r o d u c e dt op r e d i c tt h eb e s tp o s i t i o na c c o r d i n gt o t h ep o s i t i o n sa n df i t n e s so ft h et e a mm e m b e r s d p oi sah e u r i s t i cm e t h o dw h i c hp e r f o r m s w i n lp a r t n e rs e l e c t i o n , r o l e si d e n t i f ya n dc o m m u n i c a t i o nt od e t e r m i n a t et h e r o l e so fe a c h d o l p h i ni nh i sv i r t u a lt e a m , t h e nt h el e a d e ro f t h et e a mn e e dd om o r ee x p l o r e rt ot h e ”n u c l e u s 竹 a n dt h ec o m m o nm e m b e rw i l lj u s tf o l l o w i n gt h ep i o n e e r t e s to ns e v e r a lb e n c h m a r kf u n c t i o n s s h o w st h a td p oc a na c h i e v ef a i r l yb e t t e rv a l u ei nt h eb e g i n n i n gs t e p sw i n lr a p i ds p e e d a n d c a no f t e nb r e a k t h r o u g ht h el o c a lm i n i l t l mt h a tg aa l w a y sl o s ti n m e a n w h i l e ，t h ed p oh a s n i c h ec a p a b i l i t yt of i n dm a n ym i n i m u mf o rm u l t i m o d a lf u n c t i o n s b e n c h m a r kf u n c t i o ns h o w s i t sa c c u r a c y k e y w o r d s ：p s o ； n i c h e ；d o l p h i n ；p a r t n e r , n u c l e u s ；d p o 图表索零l 鞫复l 麓形臻构 图表索引 1 4 1 4 1 4 1 5 1 7 2 7 图2 - 2 环形结构。 图2 - 3 鳃面体结梅 图2 菇冯诺菝受结构 图3 1 多峰的单变量多极德点函数 图令l 大体上的凹函数 嚣每2 一维蛹数的n u c l e u s 说明 图夸3 一维函数的同心镧n u c l e u s 说明 图4 0 = 维函数的同心恻n u c l e u s 说明。 翻5 - 11 0 维s p h e r e 函数 2 7 2 9 2 9 霾5 - 2l 维r o s e n b r o c k 趱羧 3 5 3 5 图5 - 310 维r a s t r i g i n 函数3 6 图5 4l o 维g r i e w a a k 函数 餮5 巧l 缍d e j o n g 基数 巨5 舔3 0 维s p h e r e 函数 图5 73 0 维r o s e n b r o c k 函数。 整5 - 83 0 维r a s t r i g i n 蘧数。 圈5 - 9 3 0 维g r i e w a n k 丞数 图5 - 1 03 0 维d e j o n g 函数。 图5 11b r a n i n 缀数粒子分雍 3 7 3 8 3 嚣 3 9 表3 1 预瓣强标避数的极髓点个数2 2 表3 l e v yn o 5 踵数最小燕解院较一2 3 表3 3r a s t r i g i n 函数的极值点个数的准确度比较2 3 表3 4g r i e w a n k 函数的极傻点个数的准确度比较2 3 表5 1 测试蘧数戆平筠最好蹙。辩 表5 - 2 伙伴个数相关的溯试函数最好值。4 l l i s to ff i g u r e sa n dt a b l e s l i s to ff i g u r e sa n dt a b l e s f i g2 - 1s t a rt o p o l o g y 1 4 f i g2 - 2r i n gt o p o l o g y 1 4 f i g2 - 3t e t r a h e d r o nt o p o l o g y 1 4 f i g2 - 4v o nn e u m a nt o p o l o g y 1 5 f i g3 - 1s i n g l ev a r i a b l em u l t i m o d a lf u n c t i o no f v a r i o u sl o c a lb e s to f v a l u e 1 7 f i g4 - 1c o n c a v ef u n c t i o na tl a r g e 2 7 f i g4 - 2o n ed i m e n s i o n a lf u n c t i o n 2 7 f i g4 - 3o n ed i m e n s i o n a lf u n c t i o n 2 9 f i g4 - 4o n ed i m e n s i o n a lf u n c t i o n 2 9 f i g5 1s p h e r ef u n c t i o n 、i t l l10 - d i m e n s i o n 3 5 f i g5 - 2r o s e n b r o c kf u n c t i o nw i t h1o - d i m e n s i o n 3 5 f i g5 - 3r a s t r g i i lf u n c t i o n 、以t l l10 - d i m e n s i o n 3 6 f i g5 4g r i e w a n kf u n c t i o nw i t h10 - d i m e n s i o n 3 6 f i g5 - 5d ej o n gf u n c t i o n 、i m10 - d i m e n s i o n 3 7 f i g5 - 6s p h e r ef u n c t i o n 、i n l3 0 一d i m e n s i o n 3 7 f i g5 - 7r o s e n b r o c kf u n c t i o n 诵也3 0 - d i m e n s i o n 3 8 f i g5 - 8r a s t r g i nf u n c t i o n 、加n l3 0 - d i m e n s i o n 3 8 f i g5 - 9g r i e w a n kf u n c t i o n 谢也3 0 - d i m e n s i o n 3 9 f i g5 一10d ej o n gf u n c t i o n 、历t l l3 0 - d i m e n s i o n 3 9 f i g5 - 11i t e r a t i o n so nb r a n i nf u n c t i o n 4 0 t a b 3 - 1t h es u p p o s e dm i n i m u mn u m b e ro f t e s tf u n c t i o n s 2 2 t a b 3 - 2c o m p a r i s o no nb e s tf i t n e s sv a l u eo fl e v yn o 5 2 3 t a b 3 - 3t h ea c c u r a c yc o m p a r i s o no ft h ei h s t r i g i l lf u n c t i o n sm i n i m u mn u m b e r 。2 3 t a b 3 - 4t h ea c c u r a c yc o m p a r i s o no ft h eg r i e w a n kf u n c t i o n sm i n i m u mn u m b e r 2 3 i ；l b 5 1b e s t v a l u eo b t a i n e do n7 i 。瓿tf u n c t i o n s 3 4 t l i b 5 ：! b e s tf i t n e s so np a r t n e rn u m b e r 41 i v 独创 生声明 本人声明所呈交的学位论文是拳人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 申不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名： 桶匿坠 日 期： 型壁：墨： 2 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印，缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 导师签名：畿 第一章绪论 第一章绪论 1 1 课题研究的背景内容及意义 所谓优化问题，就是在满足一定的约束条件下，寻找一组参数值，使系统的某些性 能指标达到最大或最小。优化是科学研究，工程技术和经济管理领域中的一种常见问题。 例如，工程设计中怎样选择参数，使设计方案既满足使用要求又能降低成本资源分配中， 怎样分配有限资源，使分配方案既满足各方面的基本需求，又能获得好的经济效益在人 类活动的各个领域中，诸如此类，不胜枚举。 优化问题是个古老的课题。长期以来，人们对优化问题进行了不懈地探讨和研究。 早在上个世纪，在英国科学家发明微积分的时代，已经提出极值问题，后来又提出约束 优化问题并对此问题提出了乘数法。苏联数学家为解决生产组织中的问题，发表了生 产组织与计划中的数学方法等论文，这是世界上最早研究线性规划的文章。法国数学 家研究了函数值沿什么方向下降最快的问题，提出最速下降法。后来针对约束优化问题 又提出了l a g r n a g e 乘数法。 自从优化问题提出后，人们对优化问题的求解研究从未间断，对优化问题的求解提 出了各种方法。在数值算法中，近些年出现以自然界生物群体所表现出的智能现象为基 础而设计的数值算法，这些算法虽然不能够保证一定能得到问题的最优解，但这些算法 的特点是，算法步骤简单、易于理解，同时算法的适用对目标函数没有特殊的要求，能 在可接受的时间范围内给出问题的一个满意的解，因此对此类算法的研究是现在的热 点。 随着对优化问题的不断研究，对优化问题的性质的认识也有了很大的发展，以基于 这些性质为基础的解析法也得到了很大的改进。被优化函数的中的导数、梯度的性质是 解析法的基础，随着问题的不断复杂，学者们又开始研究在更广泛的基础上的导数与微 分，即泛函中的微分，微分和导数，这些都是进一步更深层次地研究优化问题理论的基 础。解析法最根本的优点是在于它通过严格的数学证明与推导，从而在被优化问题满足 了一定条件下能得到问题准确的解。然而这些条件一般都是比较苛刻，在实际中是比较 难满足的。因此近似的数值方法在实际中具有现实的应用意义。 对于复杂的优化问题，用解析法求解一般比较困难，而且有些问题根本就不满足解 析法所需要假设条件。随着科技与社会的发展，在求解优化问题的数值解法中出现了模 拟生物群体行为特性、事物的发展与结构特性等而设计的优化算法，这类算法基本迭代 式简单，但一般迭代次数比较大可是随着数字计算机出现，为简单而重复的运算提供了 保证使这类算法得到迅速的发展。这类算法一般称为进化算法。这类算法目前主要有人 工神经网络，其在一定程度上模拟人脑的组织结构；模拟退火算法，是源于物理学中固 体物质的退火过程事件；禁忌搜索算法是模拟人类有记忆过程；遗传算法( g e n e tic a 】g o r j t h m s ，g a ) ，借鉴了自然界优胜劣汰的进化思想；蚁群算法( a n tc o o n y 江南大学硕士学位论文 o p t i m i z a t i o na l g o r i t h m , a c o ) ，受启发于自然界蚂蚁的寻径方式；微粒群优化算法 ( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) ，是模拟鸟类的觅食行为。 以优化性质的基本理论为基础而设计的解析法，在目标函数满足一定的条件时，例 如被优化遐标函数连续、可导、可徽等时，都能在理论上给感算法的收敛性，德这些条 件对实际的优化对象很难满足，这就决定了这类算法在应用上的局限性。进化算法是不 依赖于问题的一类数值算法，该算法的基本式子简单，易于编程。实现的缺点是一般需 要迭代步数比较多，而且易陷入局部极值，多数进化算法都未能从理论上给予严格的数 学证明，所以现在提出的很多进化算法都未能以百分百的概率求出优化问题的解。对所 提出的进化算法进行适当机理分析，荐结合一些优化性质对冀法进行改进，以提高算法 解决实际问题的能力，是现今的一个研究方向。对算法改进的一个目的是使改进后的算 法能在更广泛的范围内使算法收敛或使算法在相同的计算量的条 牛下更快地收敛。关于 进化算法的收敛性的证明也是一个研究热点，遗传算法的模式定理是遗传算法的理论基 础。 进化算法的发展已有较悠久的历史，早期发展起来的符号主义、联结主义、进化计 算可作为经典进化算法的主要研究学派。进化算法是一种以人类、生物的行为方式或物 质的运动形态为背景，经过数学抽象建立起来的算法模型。此类算法自提出以来，由予 其对优化问题的求解具有普遍性，不需要目标优化函数的任何信息甚至被优化对象明确 的表达式，只需要知道被优化闻题的输入输出鼯可，从焉避免了以被优化函数的性质为 基础的算法的计算复杂性与不易操作性，因此得到了快速发展、广泛j 陂用与普遍重视。 每年很多有关进化算法的国际会议的召开，为推动进化算法的发展提供有利的平台同时 每年发表的有关进化算法的文章也是不可胜计。至今，新的进化算法不断的涌现，每一 种新的算法都经历着最初的提出、不断的合理改进以提高算法优化性能或以适应不同的 优化闯题的求解。如蚁群算法非常适合求解离教优曩二阍题，但不适合求解连续优化闷题， 所以将蚁群算法用于连续优化就是个有意义的研究课题，到对算法的收敛性证明，最 终达到成熟。微粒群优化算法是由美国社会心理学家j a m e sk e n n e d y 和电气工程师 r u s s e l le b e r h a r t 于1 9 9 5 年提出，其基本思想是受他们早期对鸟类群体行为研究结果 的启发，并利用了生物学家f r a n kh e p p e r 的生物群体模型。翻微粒群算法提出以来， 由于它的计算快速性和算法本身的易实现性，引起了国际上相关领域众多学者的关注， 其研究和发展受到国际学术界的广泛重视。在国外，短短地几年问，对算法的分析、改 进以及应用的文章大量涌现。例如p s o 算法广泛应用予神经网络训练秘h 粕3 。如fv a nd e n b e r g h 等分别将标准p s o 、协同进化p s o ( c p s o ) h 鄙和自适应p s o ( a p s o ) 旧分别应用于 神经网络的权值训练，使网络训练精度和训练时闻有很大改善。e b e r h a r t 等又提出了 p s o 的二进制版本强1 ，来解决工程实际中的优化问题。dkag r a f i o t i s 等汹将二进制 p s o ( b p s o ) 与b p 算法相结合( b p s o _ b p 算法) ，利用b p s o 优化前向网络的结构和b p 算 法训练阚络权值。对算法的研究作出贡献的主要人物，除了原创者k e n n e d y 和e b e r h a r t 之外，还有s h iy u h u i ，a c a r i s l e ，a n dg d o z i e r ，m e 1 e r e , e 0 z c a n 等。 2 第一章绪论 在国内，从事微粒群算法研究和应用的学者还不多，对微粒群算法的研究还处于起 步阶段，在一段时期内仍将会成为研究的热点问题阳1 。 1 2 本文的主要研究内容 首先在分析了p s o 算法的产生和改进其算法的有效性的基础上，着重分析了拓扑 结构和粒子邻域结构对p s o 算法的影响。 p s o 的拓扑结构是指整个群体中所有粒子之间相互连接的方式，而的邻域结构是指 单个粒子如何与其它粒子相连的方式。邻域结构是决定微粒群优化算法效果的一个很重 要的因素，邻域结构的改进是微粒群优化算法研究的一个很重要的方面。后文所提出的 海豚伙伴算法也考虑了邻域粒子的影响。 其次研究分析了基本的p s o 算法在典型的单峰函数和多峰函数求解中的稳定性、 收敛性、覆盖性等存在的一些问题。 针对基本的p s o 算法对单峰函数和多峰函数求解过程中遇到的问题，通过引入一 些解决问题的思想和机制，取得了一定的优化效果。 最后，在对标准p s o 的分析基础上，考虑了高智能动物的生态行为特征，加入了 小生境思想和启发式搜索原理，提出了一种新的优化算法一海豚伙伴算法。 本文分析了海豚的群智能规则，给出了他们在合作寻觅过程中的几个基本原则，并 且定义“核心 作为团队最好位置的预测。通过伙伴选择，角色定位和信息交流确定每 个海豚在自己所处团队中的位置，团队的领导者要执行对“核心 的探索，而普通的团 队成员要紧紧跟随以加快团队搜索的收敛速度。 本文采用了国际上通用的多个基准测试函数良好的展现了d p o 的搜索性能，算法 在前期能够以很快的收敛速度找到较好的适应度值，并且具有比g a 算法更好的跳出局 部极值点的能力。d p o 算法具有小生境思想，故具有良好的寻找多个极值点的能力，测 试函数也同时良好的展现了算法搜索多个极值点的有效性和准确性。 3 涯南丈学硕士学位论文 第二章微粒群优化算法研究 本章将在群体智能进化计算理论基础上着重分析一种快速的群体智能优化算 法一一微粒群算法，并且分析拓扑结构对性能的影响。 2 1 进化计算 2 1 1 优化问题概述 在实际的日常生活中或在处理工程问题的过程中，人们经常遇到在某个问题有多个 解决方案可供选择的情况下，如何根据自身所提出的某些性能的要求，从多个可选择的 方案中选择一个可行方案，使所要求的性能指标达到最大或最小，这就是优化问题。如 王程设计巾怎样选择参数，使得设计既满足要求又能降低成本资源分配孛，怎样的分配 方案既能满足各个方面的基本要求，又能获得好的经济效益等。优化问题是一个古老的 润题，早在上个世纪就己提趣了极值问题。刘本世纪年代以来，由于生产和科学研究突 飞猛迸发展，特别是电子计算机日益广泛应用，使优化问题的求解不仅成为一种迫切的 需要，而且有了有力的求解工具。在微积分出现以前，己有许多人开始研究用数学方法 解决最优化问题。例如欧洲古代城堡几乎都楚圆形的，因为阿基米德已经证骧，给定周 长，圆所包围的面积最大，数学上称为等周问题。 自优化阉题提患履，人们为求解优化闷题作了不懈的努力，提崽了各种不同的优化 算法，一般针对不同的优化问题，有各种不同的算法。二十世纪五十年代以前，对非线 性规划问题的数学方法只限予古典求导方法和变分法求无约束极值，或是拉格朗旦乘子 法解决等式约束下的条件极值。由于科学技术和生产的迅速发展，实践中许多优化问题 已经无法用经典方法求解，但由于电子计算机的发展，自上个世纪五十年代末以来出现 了许多数值算法可用于求解优化闻题。在基磷理论研究方面，其中有代表性的是库恩和 图克两人推导了关于不等式约束条件下的非线性最优必要条件，称为库恩一图克定理， 贝尔曼的最优纯原理和动态规划理论，庞特晕亚金的极大值原理，以及卡尔曼关于随枧 控制系统最优滤波器，这些构成了现代最优化技术及最优控制的理论基础。至今，对优 化阉题求解算法的研究仍然是一个热点研究领域。 2 1 2 优化问题的数学模型 求解优化阔题必须要渍楚需要优化的目标，对此目标有影响的各翻交量，蠢变量和 优化目标间的定量关系。一个优化问题的组成必需要包括需优化的目标，自变量包括可 调的与不可调的，以及自变量对目标的定量关系可以包括的还有约束条件和可行域。优 化的目标可以是函数也可以不是函数，若优化的目标是一个函数，通常就称为霞标函数， 用厂x ) = 。厂( 毛，恐，吒) 。表示。优化问题有可能是对目标函数的最小化也有可能是最 4 第二章微粒群优化算法研究 大化，但由于函数的最大化等价于一厂( x ) 的最小化，所以最小化和最大化问题并没有本 质区别。 约束条件是求目标函数极值时，对于自变量的某些限制，例如在整数规划中要求变 量全部是整数，在某些资源规划问题中，要求作为资源数量的变量全部是正数。此外有 些问题中自变量还必须满足物理系统的基本方程和性能方程。通常这些约束条件用等式 或不等式来表示。 等式约束： 蜀( x ) = 0 , x e 4 ，j = 1 ，2 ，m ，m 1 2 时，算法则较多的陷入局部极值。惯性权重w ( f ) 表明微粒的原先的速度能在多 大的程度上得到保留，较大的坝f ) 值有较好的全局搜索能力，而较小的w 【f j 则由较强的 局部搜索能力。凶此，随着迭代次数的增加，线性的减小惯性权重坝f j ，就可以使得微 江南大学硕+ 学位论文 粒群算法在初期具有较强的全局收敛能力，而在晚期具有较强的局部收敛能力。当惯性 权重氓 满足： 。w ( f ) = m - m - n ) 三_ 。 m a x c i r c l e t i m e s ( 2 16 ) 即w ( f ) 随着迭代线性地从聊递减到刀( 通常所= 1 2 , n = 0 4 ) 时，从几个测试函数 的测试结果来看，效果很好。等式( 2 1 6 ) 中的m 似删e f l m 嚣为最大截止代数，对于 惯性权重m f j 来说，由于不同的问题，其每一代所需的比例关系并不相同，这样，线性 的递减关系并不是对所有的问题都会最佳。又有学者提出了基于模糊系统的惯性权重的 动态调整。 c l e r c 在他的研究中，提出了收缩因子的概念。该方法描述了一种选择以f ) 、q ，c ： 的值的方法，以确保算法收敛。文献2 8 引入了具有明显选择机制的改进的微粒群算法， 文献2 6 引入了遗传变异操作，虽然降低了在单峰值函数的收敛效率，但在拥有多个局 部最优解的函数中，却表现良好。文献2 9 采用简化粒子群优化方程和添加极值扰动算 子两种策略对p s o 加以改进，提出了简化粒子群优化( e x t r e m u md i s t u r b e da n ds i m p l e p a r t i c l es w a r mo p t i m i z a t i o n ，简称t s p s o ) 算法。f v a n d e nb e r g h 提出了具有局部 收敛性能的改进微粒群算法g c p s o ( g u a r a n t e e dc o n v e r g e n c ep a r t i c l es w a r m o p t i m i z e r ) 。在深入分析粒子行为的基础上啪1 口，其他的改进包括动态改变邻域结构 嘲，增加粒子多样性3 3 瑚3 等。 2 3 拓扑和邻域结构 p s o 的拓扑结构是指整个群体中所有粒子之间相互连接的方式，而的邻域结构是指 单个粒子如何与其它粒子相连的方式。前者是整体性质，后者是局部性质，邻域结构决 定了拓扑结构。邻域结构是决定微粒群优化算法效果的一个很重要的因素，不同邻域结 构的微粒群优化算法，效果会有很大的差别啪1 。邻域结构的改进是微粒群优化算法研究 的一个很重要的方面，当多个粒子在待优化函数上运行时，迭代的每一步，都在检测每 个粒子处函数值的大小，这些信息在不同的粒子之间传递。通过这种方式，粒子之间分 享关于待优化函数的全局信息，使得每个粒子在下一步迭代时依据这些信息调整它们搜 索的方向和幅度。而邻域结构决定了信息在不同粒子之间传递的方式，包括在每一步迭 代中粒子可以直接得到哪些其它粒子传递的信息，这些信息在粒子之间传递的强度如 何，等等。如果信息在粒子之间传递强度太强，那么很容易使整个系统出现早熟，也即 是粒子很快聚集到某一个局部极值点上。反之，如果信息强度太弱，则因为单个粒子很 难迅速得到相距较远的粒子的信息，使得算法收敛速度变慢，影响计算的效率。 1 2 第二章微粒群优化算法研究 2 3 1 拓扑因素 确定拓扑结构的因素比较多，但是有两个最重要的特征可以量化，一是与单个粒子 直接相连的粒子的个数k ，k 的大小决定了单个粒子的邻域大小，从而影响信息在粒子 间传递的速度，通常k 值比较大的群体收敛比较快，反之比较慢。第二个确定因素是整 个群体中类的个数c ，一个类定义为互为邻域的粒子的集合，每个类中的粒子之间相互 连接数为k 。类的个数与信息在粒子之间的传递通常是减函数关系。 根据w a t t s 的研究结果，信息在粒子构成的网络中流动时，决定它的传递速度的一 个很重要的因素是从一个粒子到另一个相邻粒子的平均最短距离，而平均最短距离和k 以及c 有高度的相关性。 考虑拓扑因素的情况下，式( 2 1 4 ) 转换为 吩( f + 1 ) = w ( f ) 吩( f ) + c 1 木，i ，( f ) 宰( 弓( f ) 一西( f ) ) + q 岛( f ) 木( ( f ) 一嘞( f ) ) ( 2 1 7 ) 其中最，( t ) 为粒子所在的拓扑结构组成的群的最好值。 2 3 2 邻域结构和迭代式之问的对应关系 邻域结构和微粒群的迭代式之间存在着对应关系，不同的邻域结构影响中的磊， 其中气定义随着邻域( 一) 大小的改变而改变，整个系统的最后输出解为所有中的 最优值，当邻域是整个微粒群时，当前最优解就是名，否则，如果整个群分为j | 个类， 则输出的最优解为所有七个的最优值。 2 3 3 几种典型的拓扑结构 邻域结构来源于数学的研究，不过亦可从社会结构学角度来看邻域结构。社会结构 定义为人与人之间的连接关系，小世界理论( s m a l lw o r l d ) 认为，此类关系分为两种基 本类型，一是强连接关系，一是弱连接。前者是指个人之间产生的紧密的、稳定的连接， 后者是指偶然产生的、不稳定的连接。强连接关系基本决定了群体的结构，而弱连接关 系则非常显著的改变群体间信息流动的快慢。在一个具有稳定结构的群体中，随机的加 上几个弱连接关系，将大大的提高群体间信息流动和传递的速度，从而也将加快收敛的 速度。目前研究得比较多的几种基本的结构类型为： 星型连接也即是全局类型的连接，每一个个体与群体中的所有其它成员连接，如图 所示，这种类型的连接中，信息传递的速度比较快，所以收敛速度也比较快，但是也较 容易陷入到局部极小点。 江南大学硕士学位论文 图2 - 1 星形结构 f i g2 - 1s t a rt o p o l o g y 环形连接即所有粒子排成一个环状结构，这种结构信息传递得比较慢，收敛速度较 慢，但是也较不容易陷入局部极值点。 图2 - 2 环形结构 f i g2 - 2r i n gt o p o l o g y 金字塔型结构即四面体结构，粒子分布在四面体的四个顶点上，然后所有这样的四 面体相互连接起来。 图2 - 3 四面体结构 f i g2 - 3t e t r a h e a r o nt o p o l o g y 冯诺依曼( v o nn e u m a n ) 结构即每个粒子与上下左右四个最邻近的粒子相互连接， 形成一种网状的结构。 1 4 第二章微粒群优化算法研究 图2 _ 4 冯诺依曼结构 f i g2 - 4v o nn e u m a nt o p o l o g y k e n n e d y 在文献3 6 - 3 8 中继续研究了各种不同的邻域结构和效果的关系，得出 的结论是没有那一种邻域结构是适合于所有类型的测试函数。所有算法中，根据成功概 率性能最好的近邻结构是局部模型，根据比例等级和性能等级两项指标则冯诺以曼模 型最优。后者是一个全面较优的算法，应当考虑替换当前采用较多的其它模型。全局模 型是一个较差的模型，无论p s o n 还是p s a l n 究其原因，如果每个个体都被整个种群所 影响，则由种群所导出的信息是相同的，都在种群的重心，从而由于缺少多样性阻碍了 探测的进行。如果每个个体的近邻粒子较少，则每个个体将有不同的搜索空间，故可保 持良好的性能。 2 4 本章小结 本章给出了优化问题的基本数学模型，分析了求最优解或近似最优解的三种主要算 法：枚举法、启发式算法和搜索算法。阐述了没有免费午餐定理( n f l 定理) 对研究与应 用优化算法时的观念性启示作用。介绍了遗传算法( g e n e t i ca l g o r i t h m ，g a 算法) 、进 化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g e p ) 等 进化类算法在理论和应用两方面的迅速发展。 本章着重研究了群智能的有关理论，对微粒群算法这一新的群体智能算法进行了深 入的分析，p s o 算法目前存在的问题是：精度较低，易发散，若加速系数、最大速度等 参数太大，微粒群可能错过最优解，算法不能收敛；而在收敛的情况下，由于所有的粒子 都同时向最优解的方向飞去，所以粒子趋向同一化( 失去了多样性) ，这样就使算法容易 陷入局部最优解，即算法收敛到一定精度时，无法继续优化。 p s o 的邻域结构是指单个粒子如何与其它粒子相连的方式。邻域结构决定了拓扑结 构。邻域结构是决定微粒群优化算法效果的一个很重要的因素，邻域结构的改进是微粒 群优化算法研究的一个很重要的方面，在后续章节的d p o 算法中就着重进行了邻域结构 的改进研究。 1 5 第三章小生境p s o 及其改进 第三章小生境p s o 及其改进 3 i 小生境思想 在自然界，“人以群分，物以类聚 是一个司空见惯的现象。生物总是倾向于与自 己的特征、性状相类似的生物( 同类) 生活在一起。生物学上，小生境是指在特定环境中 一种组织的功能，而把有共同特性的组织称作物种。 图3 i 多峰的单变晕多极值点函数 f i g3 - is i n g l ev a r i a b l em