（基础心理学专业论文）粒子群算法的动态拓朴结构研究.pdf

西南大学博十学位论文 粒子群算法的动态拓扑结构研究 基础心理学专业博士研究生：王雪飞 指导教师：邱玉辉教授 摘要 最优化问题在计算机科学、人工智能、运筹学和其它相关领域中有着重要的 地位，是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问题， 很多应用领域中都面临困难的非线性优化问题，如：结构设计要在满足强度要求 等条件下使所用材料的总重量最轻；资源分配要使各用户利用有限资源产生的总 效益最大；安排运输方案要在满足物质需求和装载条件下使运输总费用最低；编 制生产计划要按照产品工艺流程和顾客需求，尽量降低人力、设备、原材料的成 本使总利润达到最大等等。在2 l 世纪的信息时代，其理论和技术必将在社会的 各个方面起着越来越大的作用。 由于优化问题存在的普遍性，多年以来有数不清的优化技术被提出和研究。 但工业和科学领域的大多数实际问题的复杂程度也正日益增加，出现了大量根本 无法在可接受的时间内找至d 解的问题。传统的规划技术已经无法满足求解复杂问 题的需求，因此更高效更实用的优化算法总是需要的。 作为一种新的群体智能方法，粒子群算法p s o 是一个非常有前景的工具， 在处理高维的以及缺乏领域知识的问题时尤其有用。该算法的灵感来源子社会心 理学和人工生命，致力于模拟个体间的社会交互，具有收敛速度快、通用性强等 优势，自1 9 9 5 年被提出之后得到了数值优化领域的广泛关注。 如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者 关注的重点。克服早熟收敛的措施主要是设法保持种群的多样性，或引入跳出局 部最优点的机制。在加快收敛速度方面，主要的工作集中在如何选择最优的算法 参数，以及从其他智能优化算法中借鉴一些思想对p s o 算法的主要框架加以修 两南大学衅士学位论文 正。但这些研究者多数属于纯科学计算或工程应用领域，他们只专注于结果而不 探究原因，更少有人深入考虑粒子群算法的社会心理学渊源。 本文在研究过程中，注重算法的理论分析和实验验证相结合。从信息传播效 率入手，详细研究了粒子群算法种群的一种动态拓扑结构，实现了基于小世界网 络模型的新颖粒子群算法。论文的主要工作和创新点包括： ( 1 ) 总结了目前群体智能的发展背景，介绍了群体智能的三种主要方法论： 蚁群算法、粒子群优化算法和人工鱼群算法，通过与还原论、人工生命、自组织 系统等相关论题的关系，分析了群体智能技术的内在特征和共性。 ( 2 ) 通过大量实验，研究了p s o 中关键参数对算法性能的影响，并由此得出 规范p s o 的参数设置。 ( 3 ) 从线性定常系统的角度对p s o 的收敛性加以分析，得出粒子轨迹最终收 敛到全局最优粒子所在的位置。从随机系统的角度对算法的收敛性进行了理论分 析，增强了线性定常条件下结论的有效性，给出了系统均方稳定的一个充分条件。 ( 4 ) 提出了基于边重构和边增加小世界网络模型的两种改进p s o 算法，实现 了p s o 算法的动态邻域结构，并对改进算法引入的新参数做了详尽的实验研究。 ( 5 ) 在选定的b e n c h 蛐咄问题和性能衡量标准上，对比研究了提出的小世界 p s o 算法与其他经典p s o 算法。这些咖c h m a r k 问题具有挑战优化算法的困难 性：高维、多峰、具有欺骗性的梯度信息等。本研究尤其重视比较算法在困难多 峰函数上的表现，以多次试验的统计结果给出算法在收敛速度、收敛成功率、目 标函数计算次数以及获得解的质量等几个衡量指标上的表现。仿真实验的结果显 示，本论文提出的具有动态拓扑机构的小世界p s o 算法能明显改善经典p s o 的 性能。 关键词：群体智能，粒子群优化算法，小世界网络，动态拓扑收敛性 西南大学博十学位论文 r e s e a r c ho nd y n a m i c n d p o i o g yo f p a r t i c l es w a r m a l g o r i t h m s r e s e a r c hd i r e c t i o n ：a m 他a ，f n 把f g e 门c e s u p e r “s o r ：p r o fy 肭u ，q ，u p h d c a n m d a t e ：) ( u e 角f 呐仃g a b s t r a c t 0 p t i i i l i z a t i o np r o b i e 脚a r eo fv i t a li m p o 衄c ei nf i e l d s o fc o i n p u t e rs c i e n c e a r t i f i c i a li n _ t e l l i g e n c e ，o p e r a t i 伽_ a 1r e s e a r c ha n do m e rr e l a t i v ef i e l 出m 姐yp r o b l e r l l s e n c 咖t e r e d 证e 1 1 9 i 1 1 e e f i n gt e c h i l o l o g y ，s c i 即矗f i cr e s e a r c ha n de c o n 删c 舢g 咖e n t c 蛆b c 订e a l e da s 俯a t i 咄o f c h a i i e r i g e a b l en o n l i n c 盯o p t i 商z a 曲np r o b i e n l ，锄c h 弱： c 伽血g l l r a t i o nd e s i 弘i n g e dt 0i i l j i i l i z et o t a lw e i g h to fi n a t e r i a i s u s e dw h i l e 谢s 蜘n gt 1 1 ei n t c n s 时r e q u 船t ；r e s o u r c ea l l o t t i n g e dt om a x i i n i z et 刚b e n e m 嘶l i z i n gl i i l l i 谢r c s o u r c e s ；t r a n s p o 泡t i o ns c h e 蜥n gn e e dt ol i l 主蛐t o t a 王c x p s e o nc 栅m s t a n c eo fa p p o i m c dn l a t e r i a l 髓dl o a dc 印a b i m y ；i n 删f a 咖r es c h e l i l e 匝觚g 堍n e e dt om a x i l i z e t o t a lb e 矗tb yc o n 廿o l l i n gm ec o s t so fm a n p o w 盯； d e v i c e s ，锄dr a w8 n dp r o s s e dm a t e r i a l sa c c o i 血g 幻幽ef l o wo ft e c h n i q u e sa n d d e m a 士i do fc l i e n t o p t i i l l i z a t i o nt h e o r y 蛆d “st e c l l n i q u e sw i l ls u r e l yt a ：k em o r ca n d m o r ei m p o n a n tp a ni nt h ei n f 细a t i o n 唧o f 2 1c e n t i l ：哆 n 嘲e r i c a lo p 血证翻t i o nm e t h o d sw e r ep r o p o s e dt h e s ey e a r sd u et om e 倒v e r s a l i t yo fo p t 醯妇a 石o np r o b l e m s m 卸yh a r do p 协n i z a t i o np r o b l 锄e m e 唱e d w l l i c hc 锄o tb es 0 1 v e di i la c c 印t a b l e 缸e ，丽t l lt t l ei i l c r e a s i n gc o 唧l e x i t yo fr e a l t a s l 【si nm ef i e l do fi i l d u s 虹ya n ds c i e n d f i cr e s e a r c h m o r ee 抒b c t i v e 锄dp r a c t i c a b l e a l g o r i t h r 璐a r en e e d e df b rt h et r a d “i o n a lp r o 掣a m m i n gm e t h o d sc a n 芏1 0 tm e 烈c o m p l e x i 两南大学博士学位论文 p r o b l e m sn o w a d a y s a san e w l yd e v e l 叩e ds w 釉i n t e l l i g e ep 啪d i g 芏n p a r t i c l es w 锄a 1 9 0 r i m mi sa v e i yp m l i l i s i n g0 p t i m i z a t i o nt o o l ，w i 也m a n ya d v 锄妞g e s i nh i g h 一幽e i l s i o n a l p r o b l e m s0 rt a s i 【s 也a t1 kp r i o rl m o w l e d g e i t sb a s i ci d i so r i g i n a t e df 如ms o c i a l p s y c h o i o 盱a n d 川f i c i a ll i f ea sas i i i m l a t i o o fs o c i o - c o g n i t i v cp r o c e s s e s b e c a u s e o f 垴h i g hc a n v e 玛e n c er a t e 趾de x c e l l e mg e n e r a l i z a t i o n ，p a r t i c l es w a ma l g o r i t h i n h a sa t t t a c t e d 删l c ha t t e n t i o ns i n c ei t 、抛sf i r s tp r o p o s e di i l1 9 9 5 mt h i si i t e r a 啦，m o s tr e s e a r c h e 巧h a v ef 砸u s e dm e 打e f r b r 姆o nh o wt 0p m m o t c 也ec o n v 既窘c er a t ea n da v o i d 也ep r e m 咖ec o n v e r g e n c ep m b l e m h 仃o d u c i n gn e w m e c h a n i s 螂t oe n 吼e ( h ed i v e r s 蚵o fs 舢p o p u l a d o no re s c a p e 劬ml o c di l l i n i i l l a m a y b eu f i l lo nr c l i e v i n gp r 即：l a t i l r ec o n v e r g e n c eo f t h ea 1 9 0 r i t l l m a st oi m p m v i i l g c o m 旧唱e n c em t e ，m c hw o r kf 如u so nt i 】n i n gs n a t e g yp 趾a m e t e 璐，o rm o d i 驰gt h e o r i 酉n a t 岔m l e w o r k w i t hi d e 鹞i n s p 砌劬mo t i l e rm e t a h 吼血s d c s a sm o s t r c s e a r c h e r so f t h i sf i e l da 砖w i 也p u r es c i e m i f l cc o m p 埘n go re n g i n e e r i n ga p p l i c a t i 咄 b a d 唱r 0 吼d ，t h e yc a 咒m o 咒a b o u tt h er e s i l l t st l l a np r o b ei n t 0t h e 训c a l l s e ，n o tt 0 m 酬c 咄i d 盯c i a lp s y c h o i o 盱硎g i n so f t h ea i g 州t h i n i no 盯r e a r c kw ea 呦c h i i n p o r t 锄c c t ob a t h 山踟帐疵c a i a n a l y s i sa n d e x p 幽e n t a ld 锄o n s 仃a t i o n f r o mt h ea s p e c to fi n f o 皿a d o ns p a de 艇c i e n c y ，a d ”l 棚ct 叩o l o g yo f p a m c l es w a 瑚a l g o r i t h mi st h o r o u g l l yi n v e s t i g a t e d 柚dan a v e l 叫i c l es w a n na 培嘣t h mb a s e do n 锄a uw o r l dn 酣v o r km o d e l i sp r o p o s c d t h em a j o r c o 吐i b i n i o n so f t l l ed i s s e r 诅t i o na r e ： ( 1 ) w bs m m i l a r i z e t h ed e v e l o p i n gb a c k g r o u n do fs w 蝴i n t e n j g e n c e ，吼d i n h o d u c et h r e em e t l l o d o l o 西e so fs w a n ni i l t c n i g e n c e ：a n tc 0 1 0 n yo p d m i 删o n ( a c 0 胁i c l es w a 皿c l p d m i z a 石o n ( p s o ) a n da i t i 矗d 8 lf j s h s w a 册a j g o d 妇 ( a f s a ) 髓ei n 乜_ i n s i c 册dg e i l e r a lc h 啪c t e ro f s w a n ni t c l l i g e n c ei sa n a l y z c dt h r o u 曲 r e l e v a n c yo f r e d u c 幽n i 锄，a n i f i c i a ll 主f e ，s e l 细玛孤i z a d o ns y s t e i n ，龃do 吐l c rt o p i c s ( 2 ) w bi n v e s t i g a t et h ei n n u e n c eo f p a r a m e t c 巧b y1 a 玛ee x p e 曲e n t s 托dv e f i 母也e p a r a m e t e r l e c 石n go f c a n o n i c a lp s o ( 3 ) w e 觋a l y c o n v e 唱印c eo f 仃a d i d 伽a lp s oa l g o r i 吐瑚f 如mt h ev i e wo fl i n e 盯 c o n s 劬ts y s t c l ，趿de l i c i tt h a tt h ct r a c ko fa n yp a n i d ew i l lc o n v e r g et ot h ep o s i t i 叽 i v 3 1 3 2 3 3 3 ，4 3 5 表格 测试集中的函数， 同步异步更新， 认知部分的系数，。， 。与k 。， 不同参数组的比较 6 1 本章采用的b e i l e h m a r k 函数列表。，。， 6 ，2 本章采用的b e n c h m a r k 函数的参数， 6 3 在b e n c h m 盯k 函数上的性能比较：函数调用次数平均值 6 4 在b e c h a r k 函数上的性能比较：函数调用次数标准差， 6 5 在b e n c h m a r k 函数上的性能比较：最好解 6 6 在b e n d l m 缸k 函数上的性能比较：平均迭代次数 6 ，7 在b e n c h m 盯k 函数上的性能比较：成功率， 6 8 在b e n 吐m 缸k 函数上的性能比较：平均c p u 耗费时间， 6 9 在b e n c h m a r k 函数上的性能比较：函数调用次数平均值 6 1 0 在b e n c h m a r k 函数上的性能比较：函数调用次数标准差 6 1 1 在b e n c h m a r k 函数上的性能比较：最好解。 6 ，1 2 在b e n c h m a 血函数上的性能比较：平均迭代次数， 6 1 3 在b e c h m a r k 函数上的性能比较：成功率 6 ，1 4 在b 钮c h m 盯k 函数上的性能比较：平均c p u 耗费时间 2 4 2 6 2 7 2 9 3 0 铸以乳雅雅踮88盯黯宕8蹭 第一章前言 1 1 研究背景 随着人们对生命本质的不断了解，生命科学正以前所未有的速度迅猛发 展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典 计算途径。在这种背景下，社会性动物( 如蚁群、蜂群、鸟群等) 的自组织行为 引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其 进行仿真，这就产生了群体智能( s w a r mi n t e u i g e c e ，s i ) ，群体智能中的群体 指的是“一组相互之间可以进行直接通信或间接通信( 通过改变局部环境) 的 主体( a 鼬n t ) ，这组主体能够合作进行分布式的问题求解”，而群体智能则是 指“无智能的主体通过合作表现出智能行为的特性”。群体智能在没有集中控制 且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。 群体智能主要受启发于社会性动物的行为模式，社会性动物的奇妙之处在 于：个体的行为都很简单，但当它们作为一个群体协同工作时，却能涌现出非常 复杂的智能行为特征。例如，单只蚂蚁的能力非常有限，但当这些简单的蚂蚁 组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫蚁巢等复杂行为；一群行为显 得盲目的蜂群能造出糟美的蜂窝；鸟群在没有集中控制的情况下能够同步飞行 等。 作为行为主义学派的最新技术，群体智能方法自2 0 世纪9 0 年代中期提出以 来一直受到广泛的关注1 1 。群体智能方法易于实现，算法中仅涉及各种基本的 数学操作，其数据处理过程对c p u 和内存的要求都不高。且这种方法只需目标 函数的输出值，而无需其梯度信息。已完成的群体智能理论和应用方法研究都 证明：群体智能是一种能够有效解决大多出全局优化问题的新方法。更重要的 是，群体智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数 据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群体智能理 论及应用研究都是具有重要学术意义和现实意义的。 目前，群体智能的典型技术包括蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，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 ) ，主要特征是多智能体、 非中心控制、自组织和涌现行为 2 ，3 卜蚁群算法由意大利学者d o r i g o 于1 9 9 1 年 2 粒子群算法的动态拓扑结构研究 在他的博士论文中提出，该方法受启发于蚂蚁个体之间能通过简单的信息素传 递进行相互协作，从而完成寻找从蚁穴到食物源的最短路径这一复杂任务【4 】口 粒子群算法由社会心理学家k e n i 剧y 和e b e r h 口t 博士于1 9 9 5 年首次提出【5 】，该 方法从鸟群的觅食行为和鱼群的聚集行为中获得灵感。k e n n e d y 和e b e r h a r t 修 改了生物学家n a n kh 印p n e r 的鸟群觅食模型【6 】，发展出用于解决优化问题的粒 子群算法。 群体智能已成为国际上的研究热点之一。目前国际上有大量的杂志 和会议发表群体智能理论研究及应用的相关成果，其中国际顶级杂志包 括： i e e en a n s a c t i o no ne v 0 i u t i o n a r yc o m p u t a t i o n ( i e e e ) ，e v 0 1 u t i o n a r y c 0 玎1 p u t a t i o n ( m i tp r 髑s ) ，n a t u r a lc 锄p u t i l l g ( s p r i g e r ) 等；国际项级学 术会议主要有：i e e es w 姗i n t e u i g e n c es y m p o s i u m ，s p e c i a ls e s 8 i o no 踟m m i n t e u i g e n c eo fc o n f e s so e v 0 1 u t i o n a r yc o m p u t a t i o n ，a n tc o l o n yo p t i 1 i z a t i o n 柚ds w a r m 工n t e l l i g e 。e 等。 许多国家的著名大学也设立了研究群体智能的实验室或课题组，如：h d i a n a u n i v e r 8 i t y - p u r ( 1 u eu n i v e r 8 i t y ( u s a ) ，h l l 】1 t i n 异d o c o l l e g e ( u k ) ，u i v e r s i t y0 f p 8 t r 锄( g r 盹c e ) ，r e 8 e 盯c hp s y c l l o l o 西s tb l l r e a uo fl 曲o rs t a t i s t i c s ( u s a ) ，i d w _ a s t a t eu n i r s i t = i r ( u s a ) ，u i l i v e r 8 i t yo f p r e t o r i a ( s o u t ha 甜c a ) ，s y r a c l l s eu 瞎 v 耵s i t y ( i t a l y ) ：国内部分高校也有实验室和研究人员开展群体智能方面的理论 研究和应用工作，主要有：南京大学人工智能实验室，复旦大学智能信息处理开 放实验室，北京大学系统与控制研究中心中科院计算所智能信息处理开放实 验室，中科院自动化所复杂系统与智能科学实验室，浙江大学智能人机交互与 虚拟现实实验室，西安电子科技大学神经网络研究中心，西南大学智能软件与 软件工程实验室等。 1 2 研究动机 优化在计算机科学、人工智能、运筹学和其它相关领域中有着重要的地位。 许多科学的、社会的、经济的和工程的问题都具有需要调节的参数，以得到更 满意的结果7 1 。传统的规划技术和基于梯度的优化方法已经不能满足日盏复杂 的现实优化问题的需求因此研究者们一直致力于发展更高效更实用的优化技 术。 经过十年以来的发展，群体智能理论凭借其简单的算法结构和优异的问题 第一章前言3 求解能力。吸引了众多研究者的兴趣，并取得了令人注目的成果。已有的理论 和应用研究显示，群体智能方法为解决困难的优化问题提供了新的途径，与梯 度方法及传统的进化算法相比，具有明显的优势： 1 无集中控制机制，不会因某些个体的失效影响整个问题的求解，系统具有 更强的鲁棒性； 2 采用间接的信息交流方式，确保系统具有良好的可扩展性 3 具有潜在的并行性和分布式特点，易于开发分布式并行算法模型 4 对问题定义的连续性及梯度信息无特殊要求，适用范围广： 5 算法中仅涉及各种基本数学操作，易于实现，且数据处理过程对c p u 和内 存的要求也不高。 群体智能技术的应用领域已扩展到多目标优化、数据分类、数据聚类、模 式识别、电信q o s 管理、生物系统建模、流程规划、信号处理、机器人控制、决 策支持以及仿真和系统辩识等方面 8 ，9 ，1 0 ，1 l ，1 2 1 由此可见，作为一类现代启发式优化算法，群体智能理论及其应用研究都 具有相当重要的学术意义和现实价值。 粒子群算法是最新的群体智能技术，属于基于种群的随机全局优化算法类， 其主要思想起源于社会心理学和人工生命。该算法模仿生物群体的社会认知过 程( 社会规范的涌现) ，将该过程建模成为简单个体问的交互与协作，用于发现 适应度空间中的全局最优点。 p s o 算法自1 9 9 5 年被提出之后，得到了数值优化领域的广泛关注，吸引了 大量研究者的工作【1 3 ，1 4 卜但算法的数学理论基础相对薄弱，缺乏具备普遍意 义的理论性分析，如收敛性分析等。我们在他人工作的基础上，从描述粒子轨 迹的显式公式出发，对一个粒子的轨迹进行分析，进而给出保证粒子轨迹收敛 的参数c l ，c 2 和w 取值。从随机系统的角度，对p s o 的动力学模型加以分析研究， 并最终给出了系统依概率收敛的一个充分条件。 另一方面，如何加快算法的收敛速度和避免早熟收敛问题，一直是大多 数研究者关注的重点，也 法共同面临的两个主要难题。标 第一章前言 5 通过分析还原论的局限，探讨与人工生命、复杂系统等相关论题的关系， 提出了群体智能技术的内在特征和共性，对深入理解各种群体智能方法的 内部机理和发展方向具有重要的作用。 从线性定常系统的角度对p s o 的收敛性加以分析，得出粒子轨迹收敛的结 论。从随机系统的角度对p s o 的动力学模型进行研究，给出了系统依概率 收敛的一个充分条件。在目前粒子群算法缺乏理论研究的背景下，这方面 的努力意义重大。 实现了p s 0 算法的动态邻域结构，提出了两种基于小世界网络模型 的p s o 算法，明显改善了经典p s o 算法的搜索效率。 论文的内容安排如下： 1 4 论文内容介绍 第二章介绍群体智能的发展历史、主要方法及研究应用现状，并讨论了几个重 要的相关论题。 第三章首先给出粒子群优化算法的发展历史、参数设置，并总结分析了其研究 及应用现状。 第四章给出算法的理论分析与粒子轨迹收敛性的研究。 第五章分析了p s o 算法性能与粒子邻域结构的关系，提出具有动态邻域思想的 小世界p s 0 算法。 第六章描述实验所用的标准测试函数和环境设置，说明实验结果中使用的衡量 指标，并显示引入的参数对算法性链影响的实验结果。以多种方式呈现小 世界p s o 算法的基本表现，并给出各种p s o 算法在困难b e n c h m k 问题上 的性能比较实验结果。 第七章总结及未来工作计划。 第二章群体智畿 随着计算机和他们解决的问题越来越复杂，研究者们开始向大自然寻求灵 感。自然界的生物系统具有趋向于非集中性、自适应性和环境意识，这使得他 们具有适应环境的生存能力，具有很强的可量测性和灵活性，这些属性远远优 于现有最好的人机系统。探讨如何将从生物学中的安全性、适应环境和优化过 程中获取的灵感用于计算任务，对人工智能的新原理、新方法的发展具有极大 的推动作用。 在我们生存的大自然中，存在着形形色色的生物，它们看似无目的的活动、 觅食，但经历了漫长的自然界的优胜劣汰之后，依然作为一个种群生存至今。它 们所形成的觅食和生存方式为人类解决问题的思路带来了不少启发和鼓舞。动 物一般不具有人类所具有的复杂逻辑推理能力和综合判断能力的高级智能，它 们的目标是在个体的简单行为中通过群体的表现而涌现出来的。 研究发现，很多动物的行为都具有以下几个特点： 1 适应性：动物通过感觉器官来感知外界环境，并应激性地做出各种反应， 从而影响环境，表现出与环境交互的能力； 2 自治性：动物有其特有的某些行为，在不同的时刻和不同的环境中能够自 主地选取某种行为，而不是通过外界的控制或指导： 3 盲目性：不像传统的基于知识的智能系统，有着明确的目标，单个个体的 行为是独立的，与总目标之间没有直接的关系； 4 涌现性：总目标盼完成是在个体行为的运动过程中涌现现出来的； 5 并行性：各个体的行为是实时的、并行进行的。 动物自治体是一种从底层来研究生物的适应性行为，或者说是生物的智能 行为的模型。与传统的基于知识的顺序结构的智能系统相比较，它是一种基于 行为的多并行通路的并行结构。 动物自治体具有以下特点： 8 粒子群算法的动态拓扑结构研究 1 - 并行性：自治体的各行为是并行处理的 2 自下而上的设计方法：它从分析自治体的底层行为出发，来实现整体的设 计； 3 任务分解：对于自治体的某一种行为仅限于执行某一任务； 4 分散：智能自治体不需要一个总体的完善的知识库和推理库。而是由一系 列分散的、简单的适应性反应行为表现出来： 5 涌现性：自治体的单一行为与总体目标之间有时候没有必然的逻辑关系， 总体目标的实现往往是在自治体内部各行为间、自治体与其所处环境的相 互作用中涌现出来的。 随着生命科学和多学科交叉融合方法的迅猛发展，具有自治特性的社会性 动物( 如蚁群、蜂群、鸟群等) 引起了人们的广泛关注，计算机科学家们对社 会性动物的自组织行为进行数学建模并用计算机对其进行仿真提出了许多用 于解决复杂问题的新方法，如遗传算法、进化规划、进化策略等。群体智能算 法( s w a 衄i n t e l l i g e n c e ，s i ) 作为一种新兴的演化计算技术己成为越来越多研究 者的关注焦点。 群体智能中的群体指的是“一组相互之间可以进行直接通信或间接通 信( 通过改变局部环境) 的主体( a g e n t ) ，这组主体能够合作进行分布式的问题 求解”，而群体智能则是指“无智能的主体通过合作表现出智能行为的特性”。 群体智能在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问 题求解方案提供了基础。 与大多数基于梯度应用优化算法不同，群体智能依靠的是概率搜索算法。 虽然概率搜索算法通常采用较多评价函数，但与梯度方法及传统的演化算法相 比，其优点还是显著的： 1 无集中控制约束，不会因个别个体的故障影响整个问题的求解，系统具有 更强的鲁棒性； 2 以非直接的信息交流方式确保系统具有良好的可扩展性，由于系统中个体 的增加而产生的通信开销增加很少； 1 0 粒子群算法的动态拓扑结构研究 位置来产生下组解；而鱼群算法是通过觅食行为、追尾行为、聚群行为和随 机行为产生下组解。2 1 1蚁群算法a c o 2 1 群体智能方法蚂蚁之所以被称为社会性昆虫，是因为它具备组成社会的三个要素：除有 组织、有分工外，还有相互通信和信息的传递。生物学家和仿生学家发现，蚁群 有着奇妙的信息系统。寻找食物时，蚂蚁倾向于跟随信息素浓度高的轨迹。这 些轨迹是由觅食的个体在行进过程中留下的，以指导其他个体朝相同食物源方 向前进。被访问得越多的地方，其信息素的浓度就越高。由于蚂蚁在寻找食物 源和返回巢穴时的访问，邻近巢穴的道路上聚集了浓度更高的信息素【24，25。 从蚂蚁群体寻找最短路径的觅食行为中受到启发。意大利学者dorigo等 人1 9 9 1 年提出了一种模拟自然界蚁群行为的优化算法一人工蚁群算法，简称 蚁群算法a c o 。a c o 使用人工信息素轨迹作为群体中简单a g e n t s 之间的通信方 式。信息素轨迹作为蚂蚁使用的分布式的数值信息，以概率构造问题的解。模 拟蚂蚁的搜索经验，问题的潜在解依照信息素更新规则和概率转换规则被不断修改【2 6 卜蚁群算法的基本思想如下： 用图表示问题可行解的构造。假定一只蚂蚁必须在些边e中做出选择，对 于每一个边ee，表示信息素的量，表示边的满意性，选择边目约概率为：即，= 毫 其中，a 和卢是两个可调参数控制路径集中性和满意性的相对权值。 如果缺乏信息素的衰减机制，算法的性能不会很好。路径上信息素的衰减是通过引入衰减因子0 s p 6 x ，则表明邻域中心有较多食物，并且不太拥挤，人工鱼五朝邻域中心位 置方向前进步；否则，执行觅食行为。 3 第三步：追尾 设人工鱼x 当前邻域内巧为最大的伙伴玛，如果巧“， 6 k ，则表明伙 伴玛的状态具有较高的食物浓度，且其周围不太拥挤，人工鱼x 朝伙伴玛 的方向前进一步；否则，执行觅食行为。 第二章群体智能 1 7 此外，还要根据所要解决的具体问题，对人工鱼当前所处的环境进行评价， 从而选择一种行为。对于求解最大值问题，最简单的评估方法可以用试探法，即 模拟执行聚群、追尾等行为。然后评价行动后的值，选择其中的最大者来实际 执行，缺省的行为方式为觅食行为。 2 2与群体智麓相关的几个论题 2 2 1 还原论的局限 作为近代科学思想的奠基人之一的笛卡尔，在他那篇关于正确运用推理的 著名论著中对科学研究提出如下建议：“如果一个问题过于复杂以至于一下子难 以解决，那么就将原问题分解成一些足够小的问题，然后再分别解决。”这被称 为“笛卡尔方法”，该方法至今仍有效地被用于自然科学的若干研究领域。 笛卡尔方法隐含了一个假定：当所有分解出的子问题都得到解决后，系统 还可以恢复原状或重新组合起来，也就是说，分解出的各个子问题的解答之总 和就给出了一个原问题的答案。还原论的这一假定和其“自上而下”的设计方 法对于简单系统也许成立，但对于生命系统和其他复杂系统而言，情况并非如 此：整体总是大于部分之和，对系统的关键分解可能是不可逆的。生命结构显 得非常复杂，它们由许多部分以非常特定的方式结合，一般难以分析它们的结 构，功能关系，因此我们必须借助整体哲学及方法论4 8 1 。 在现有的群体智能方法中，个体的行为都很简单，但当它们作为一个群体 协同工作时，却能涌现出非常复杂的智能行为特征。例如，单只蚂蚁的能力非 常有限，但当这些简单的蚂蚁组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫 蚁巢等复杂行为；一群行为显得盲目的蜂群能造出精美的蜂窝；鸟群在没有集 中控制的情况下能够同步飞行等。因此，群体智能方法都采用“自下而上”的设 计方法，即定义每个独立个体的行为，以及个体之间的交互方式，仅由筒单个体 的协作就能涌现出复杂的高层行为。 2 2 2 自组织现象、涌现与复杂系统 自组织现象是指自然界中自发形成的宏观有序现象【4 9 卜在自然界中大量 存在自组织现象，系统的一些参数往往表现出与尺度无关的特性，例如代谢网 络、物种问的协同进化过程以及i n t e r n e t 中的b b si d n e 押o r k 8 等【4 8 ，5 0 ，5 1 。自 粒子群算法的动态拓扑结构研究 组织现象中理论研究较多的典型实例有：贝纳德流体的对流花纹；贝洛索夫扎 鲍廷斯基化学振荡花纹与化学波；激光器中的自激振荡等。 自组织理论除耗散结构理论外，还包括协同学、超循环理论等，它们力 图沟通物理学与生物学甚至社会科学，对时间本质问题等的研究有突破性进 展【5 2 ，5 3 】，在相当程度上说明了生物及社会领域的有序现象5 4 1 。 由伊里亚普里戈金教授于1 9 6 9 年创立的耗散结构理论是自组织理论中的 重要部分。耗散结构理论可概括为：一个远离平衡态的非线性的开放系统通过 不断地与外界交换物质和能量，在系统内部某个参量的变化达到一定的阈值时， 通过涨落，系统可能发生突变即非平衡相变，由原来的混沌无序状态转变为一 种在时间上、空间上或功能上的有序状态。这种在远离平衡的非线性区形成的 新的稳定的宏观有序结构，由于需要不断与外界交换物质或能量才能维持，因 此称之为“耗散结构”。 根据自组织理论，从无序向有序转化，必须具备下列条件【5 5 1 1 开放性 产生有序结构的系统必须是一个开放系统，能不断与外界进行交互作用， 从而使外部输入负熵大于内部熵增，使系统熵减，至少熵不变，这样才能 维持自身的有序结构，或者更趋向复杂化。 2 非平衡 系统从无序走向有序，必须处于远离热平衡态。在热平衡态附近，不会出 现新的有序结构。系统中的交互作用只发生在远离均衡态的时候，这种情 况下才有可能从杂乱无序的初态，跃迁到新的有序状态。 3 非线性 形成有序结构的系统内部各要素之间要有非线性的相互作用。这种相互作 用使系统内各要素间产生相干效应与协同动作，从而变无序为有序。非线 性相互作用，导致系统有序化的多方向性。 4 随机涨落 一个系统从无序向有序转化的过程中，偶然性、随机涨落起着十分重要的 作用，即通过涨落才能导致有序。 粒子群算法的动态拓扑结构研究 实验结果表明，使用惯性权重在大量的应用中改善了性能。最大速度因 素p 名。；可以简单地设为每个变量在每一维上的动态范围值x 。，这一限制是为 了防止粒子在最优解可能存在的区域振荡过大，导致未对该区域进行充分的探 索【6 8 】。 在s h i 和e b e r h 盯t 的研究中，惯性权重在算法运行时从0 9 线性减少至o 4 ，提 供了广度搜索( 开始时步长较大) 和深度搜索( 随着搜索过程逐渐减小，趋向于 精调) 之间的种平衡。参数作为惯性因子，能随时间动态调整粒子速度6 9 1 ， 使粒子逐渐趋向于局部搜索，使用惯性权重的结果是能以更少的平均迭代次数 获得更满意的解。 惯性权重因子的版本通常被称为标准的p s 0 算法。有不少研究者针对惯性 权重对算法的影响展开了工作，最近有研究将惯性权重设置为0 5 附近的随机 值，还有研究采用模糊控制器动态修改惯性权重。另外，其他的惯性权重自适 应调整策略也是一个主要的研究论题。 3 1 3 带收缩因子的p s o c l e r c 仔细研究了一个通用的粒子群系统，能控制速度的急速增长 7 0 】。为保 证粒子轨迹的收敛性条件成立，c l e r c 引入收缩因子x 修改了通用的粒子群模型， 其中一个简化的系统为： 譬：2 翌哗三三7 i 饿一z ：) + c 2 r ；雠一z ：) ) ( 3 3 ) iz 1 = z + 妒1 7 收缩因子由下式计算： x 。f 石褊其中眶【0 ，1 】，妒2 c 1 + c 2 ，妒 4 ( 3 4 ) 大多数采用收缩因子方法黔研究者将妒设为4 1 ( 即有：c i = 句= 2 。0 5 ) ， 并设k = 1 ，由此得出x 0 7 2 9 。这在数学上等价于使用惯性权重方法设 = 0 7 2 9 ，且o l = 臼= 1 4 9 “5 。 收缩因子方法会随时间收敛：粒子振荡轨迹的幅度随时间不断减小。 当，c = l 时，收敛速度小得足以在搜索收敛前开展彻底的广度搜索。 使用收缩因子的优点在于不再需要使用。也无需推测影响收敛性和防 止急速增长的其他参数的值1 7 1 】。 2 4 粒子群算法的动态拓扑结掏研究 表3 1 ：测试集中的函数 r 丑s t r i g r i n，( z ) = 竺l 一1 0 c 0 8 2 w q + l o 3 05 1 2 1 0 0 s c h 如r f 6 m ) = o 5 + 蔷描蓑群 21 0 0o 0 0 0 0 1 3 2 1 实验设计 为了测试不同的参数设置，最初的p s o 设置来源于s h i 和e b e 抽a r t 在f 8 8 1 中 使用的参数，在文献中他们将所使用的惯性权值叫和c l e r c 所采用的收缩因 子x 进行了比较。s h i 和e b e r h ”t 采用的种群大小是3 0 ，c l 和c 2 均设为2 ，0 5 ，v k 。值 设为五一，并引入了c l e r c 的收缩因子。他们并未详细说明，可以假定邻域是 全局的，粒子的更新是同步的( 即：在两次迭代之间确定) 。他们选用的函 数集：s p h e r e 函数( d ej o n g 的f 1 ) ，r _ 0 s e n b r o c l 【函数，一般r a s t r i 斟i n 函数，一 般g r i e w a n k 函数，以及s c h a r 的f 6 函数。 表3 1 列出函数的公式和每个函数采用的参数。 3 2 2 实验实现 在每个实验中，每个函数重复运行2 0 次，每次最多迭代1 0 0 0 0 0 次。对于每个 函数的重复运行结果，统计其成功率、成功运行的平均迭代次数和中值迭代次 数、函数调用的平均次数和中值次数。最后一项衡量的是运行集中算法实际完 成的工作量。通常。可以通过迭代次数与种群大小相乘得出函数调用次数，因 为每个粒子的位置在一次迭代中被计算一次。然而，由于发现解之后一次运行 就终止，实际函数调用次数要比乘数少。 3 2 2 1 实验一：种群大小 第一个实验研究了种群大小改变的影响。在【6 9 】中，s h i 和e b e r h 甜t 指 第三章粒子群优化算法 出”p s o 算法对种群大小不敏感”。对性能来讲确实如此，但是考虑成本却 不一样。采用s h i 和e b e r h a r t 在文f 7 1 1 中提到的最佳参数在5 个函数上运行p s o ， 即使用c 1 e r c 的收缩因子x ，其中计算用妒= 4 0 l ( 社会学习率和