（通信与信息系统专业论文）改进的生物群智能优化算法及在滤波器设计中的应用.pdf

兰州大学研究生学位论文 摘要 优化是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问 题。对优化策略及算法的研究成为近年来备受科学工作者关注的研究目标之一。 受到具有社会性的动物，如蚁群、蜂群、鸟群、鱼群等的自组织行为的启发，不 少学者对这种行为进行数学建模并用计算机对其进行仿真，随之产生了“群智能” ( s w a r mi n t e l l i g e n c e ，s i ) ，或称“群集智能”，主要包括遗传算法、蚁群算法、 粒子群算法和人工鱼群算法等。本文在对现有的群智能理论领域主要算法的基本 理论、系统模型、参数设置和实验仿真进行分析研究的基础上，提出了一种粒子 群与蚁群及遗传和模拟退火算法相混合的算法，并将其应用于i i r 数字滤波器、 陷波器的设计应用上，从实验分析上看，取得了一定的效果，通过仿真实验表明， 该方法设计的滤波器在通带和阻带内具有较好的特性，较好地防止了算法易陷入 局部最优等问题，且计算简单、计算量小，有较好的应用前景，进而验证了该混 合算法的适用性和有效性。 关键词：群智能、蚁群算法、粒子群算法、数字滤波器 i l l 兰州大学研究生学位论文 a b s t r a c t m a n ys c i e n t i f i cr e s e a r c h ，e n g i n e e r i n ga n de c o n o m i c a lm a n a g e m e n tp r o b l e m sn e e d t h eo p t i m i z a t i o no fas e to fp a r a m e t e r sw i t ht h ea i mo fm i n i m i z i n go rm a x i m i z i n gt h e o b j e c t i v ef u n e t i o mt oo p t i m i z et h es t r a t e g ya n dt h ea l g o r i t h l nr e s e a r c hi n t or e c e n t y e a r sp r e p a r e so n eo fr e s e a r c ha i m sw h i c hi sp a i da t t e n t i o nt h es c i e n t i f i cw o r k e r s t h es o c i a la n i m a l ( s u c ha sa n tc o l o n y , s w a r m ，b i r dg r o u p ，s c h o o io ff i s he t o ) h a s a r o u s e dp e o p l e su n i v e r s a li n t e r e s tf r o mt h eo r g a n i z a t i o nb e h a v i o ri n s p i r a t i o n , m a n y s c h o l a r sc a r r yo nm a t h e m a t i c sm o d e l i n ga n dt ot h i sb e h a v i o rc a r r yo nt h es i m u l a t i o n w i t ht h ec o m p m e rt oi t f r o mt h e no n , i th a sb u i l tal l e wr e s e a r c hf i e l d s w a r m i n t e l l i g e n c e ( s d ，m a i n l yi n c l u d e st h eg e n e t i ca l g o r i t h m ，t h ea n tc o l o n yo p t i m i z a t i o n , p a r t i c l es w a r l l lo p t i m i z a t i o na n da r t i f i c i a lf i s hs w a l t i la l g o r i t h ma n d s oo n t h i sa r t i c l ei nt ot h ee x i s t i n gs w a r mi n t e l l i g e n c et h e o r yd o m a i nm a i na l g o r i t l u n e l e m e n t a r yt h e o r y , t h es y s t e mm o d e l ，t h ep a r a m e t e r e s t a b l i s h m e n ta n dt h e e x p e r i m e n t a ls i m u l a t i o nc o n d u c t st h ea n a l y s i sr e s e a r c hi nt h ef o u n d a t i o n ，p r o p o s e da a l g o r i t h mw h i c hc o m b i n e dp a r t i c l es w a r mo p t i m i z a t i o n ，t h ea n tc o l o n yo p t i m i z a t i o n ， t h eg e n e t i ca l g o r i t h ma n dt h es i m u l a t i o na n n e a l i n ga l g o r i t h m , a n da p p l i e si ti nt h ei i r d i g i t a lf i l t e ra n da d a p t i v en o t c hf i l t e rd e s i g na p p l i c a t i o n ，a n a l y z e sf r o mt h e e x p e r i m e n t o nl o o k e d ，h a so b t a i n e dc e r t a i ne f f e c t , t h e ni n d i c a t e dt h r o u g ht h e s i m u l a t i o ne x p e r i m e n t ，t h i sm e t h o d sd e s i g nf i l t e rh a v et h e9 0 0 dc h a r a c t e r i s t i ci nt h e p a s s b a n da n dt h es t o p - b a n d ，h a dp m v e n t e dw e l lt h ea l g o r i t h me a s yt of a l li n t o p a r t i a l l yt h em o s te x c e l l e n tq u e s t i o n , a l s ot h ec o m p u t a t i o ns i m p l e ，t h ec o m p u t a t i o n l o a di ss m a l l ，h a sc o m p a r e st h eg o o da p p l i c a t i o np r o s p e c t , t h e nh a sc o n f i r m e dt h i s c o m b i n e da l g o r i t h ms e r v i c e a b i l i t ya n dt h ev a l i d i t y k e y w o r d ：s w a r mi n t e l l i g e n c e ( s i ) ，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 e s w a r mo p t i m i z a t i o n ( p s o ) ，d i g i t a lf i l t e rd e s i g n 兰州大学研究生学位论文 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：王一日期：矿刀s ? f 兰州大学研究生学位论文 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 n 论文作者签名：皇二导师签名： i l 兰州大学研究生学位论文 1前言 从生物进化的机理中受到启发，人们研究并提出了许多用以解决复杂优化问 题的新方法，如遗传算法、进化规划、进化策略等。群智能算法作为种新兴的 演化计算技术已成为越来越多的研究者的关注焦点，它与人工生命，特别是进化 策略以及遗传算法有着极为特殊的联系。群智能中的群体指的是“一组相互之问 可以进行直接或间接通信( 通过改变局部环境) 的主体( a g e m ) ，这组主体能够 合作进行分布式的问题求解”，而群智能则是指“无智能的主体通过合作表现出 智能行为的特性”。群智能在没有集中控制且不提供全局模型的前提下，为寻找 复杂的分布式问题求解方案提供了基础。目前，群智能理论研究领域主要有四种 算法：遗传算法g a ( g e n e t i ca l g o r i t h m ) 、蚁群算法a c o ( a n tc o l o n y o p t i m i z a t i o n ) 、粒子群优化算法p s o ( p a r t i c l es w a r mo p t i m i z a t i o n ) 和人工鱼群 算法a f s a ( a r t i f i c i a lf i s hs w a r ma l g o r i t h m ) 。其中，蚁群算法是对蚂蚁群落食 物采集过程的模拟，已成功应用于许多离散优化问题。粒子群优化算法也是起源 于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很 好的优化工具。我国学者李晓磊提出的人工鱼群算法，是一种模拟鱼的觅食、聚 群和追尾行为的随机搜索算法，目前这些算法在理论研究方面还需进一步加强。 1 1群智能算法的研究与现状 所谓群智能( s w a r mi n t e l l i g e n c e ) 指的是众多无智能的简单个体组成的群体， 通过相互间简单合作表现出智能行为的特性。自然界中动物、昆虫常以集体的力 量进行觅食生存，在这些群落中单个个体所表现的行为是简单且缺乏智能的：而 且各个个体之间的行为是相同的，但由个体组成的群体则表现出了一种有效的复 杂的智能行为。群智能可以在适当的进化机制引导下通过个体交互以某种突现形 式发挥作用，这是个体以及可能的个体智能难以达到的。群智能以群体为主要载 体，通过它们之间的间接或直接通信进行并行式问题求解【旧。 b o n a b e a u 等人认为群智能是受群居性昆虫群体和其它动物群体的集体行为 启发而设计的算法和分布式问题解决装置【3 1 。群智能的特点是最小智能但自治的 个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组 织、可扩展性、健壮性等特性。 目前，研究群智能的方法多是从多a g e n t 系统的观点来进行的。该观点假定 多a g e n t 系统中的每个个体能够感知环境，包括自身和其它a g e n t 对环境的改变， 兰州大学研究生学位论文 a g e n t 问通过环境变化进行相互的间接通信。而且在一些研究中将人类社会中的 一些性能移植到群智能中去，比如假定每个a g e n t 都具有“意志”、“信念”，各 a g e n t 之间既有合作又有竞争，而且遵守各种协议等。文献 4 ，5 ，6 】等从多a g e n t 系统的观点研究讨论了群智能的性能特点，认为群智能是一组可相互通信，互相 影响的主动和可移动的a g e n t 组成，每个a g e n t 只能存取局部信息，而没有中心 控制和具有全局观点的个体，是一种分布式的计算环境。 张铃等1 7 j 人从进化观点的角度探讨了群智能的现象并采用一种特殊的人工 神经网络来模拟该“离散的脑袋”，建立了随机( 连接) 神经网络的群智能模型。 具体地说，( 以蚂蚁筑巢为例) 就是将每个蚂蚁看成是一个神经元，它们之间的 通信联络可看成是各神经元之间的连接，但是连接是随机的而不是固定的。即用 一个随机连接的神经网络来描述一个群体。这种神经网络所具有的性质就是群体 的智能。 在群智能的研究和发展基础上，人们先后提出了多种群智能优化算法，最典 型的有遗传算法、蚁群算法、粒子群算法及鱼群算法，为解决优化问题提供了丰 富多彩的解决方法。 1 1 1 遗传算法( g a ) 遗传算法是由美国m i c h i g a n 大学的j o h nh o l l a n d 于2 0 世纪6 0 年代末提出 并创立。g a 作为一种解决复杂问题的有效的优化方法，近年来在国内外得到较 为广泛的应用，并产生了很多分支，如进化程序、遗传编程、进化策略、分类器 系统和人工生命。遗传算法的思想基于达尔文的进化论与孟德尔的遗传学原理。 它模拟了自然选择和遗传过程中发生的繁殖、交配和变异现象，根据适者生存、 优胜劣汰的自然法则，利用遗传算子选择、交叉和变异逐代产生优秀个体，即候 选解，最终搜索到较优的个体 8 , 9 , 1 0 l 。 1 9 7 5 年，h o l l a n d 出版了自然与人工系统中的适应性行为，该书系统地 阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理模式定理， 从而奠定了遗传算法的理论基础。 7 0 年代，d ed o n g 把遗传算法应用于函数优化问题，对遗传算法的机理与参 数进行了较为系统地研究，并建立了著名的5 函数测试平台，定义了性能评价标 准。 8 0 年代初，d a v i d g o l d b e r g 出版了搜索、优化和机器学习中的遗传算法， 该书全面系统地总结了当时关于遗传算法的研究成果，结合大量实例，完整地论 述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础。 9 0 年代，j o h nr k o z a 出版了专著遗传编程，提出了遗传编程的概念， 2 兰州大学研究生学位论文 并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面，随着 遗传算法的不断深入发展，关于遗传算法的学术研究活动频繁，遗传算法已成为 一个多学科、多领域的重要研究方向。 1 1 2 蚁群算法理论( a c o ) 蚁群算法是在2 0 世纪9 0 年代提出的一种新型模拟进化算法，它是由意大利 学者d o r i g o ，m a h i e z z o ，c o l o r n i 等人由前人关于自然界中真实蚁群智能行为的 研究结果得到启发，从而提出的一种新型算法，并称之为蚁群系统a s ( a n t s y s t e m ) 1 1 1 a 2 1 。它充分利用了蚁群搜索食物的过程与著名的货郎担问题t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 之间的相似性，通过人工模拟蚂蚁搜索食物的过 程( 即通过个体之间的信息交流与相互协作最终找到从蚁巢到食物源的最短路 径) 来求解t s p 问题 1 3 , 1 4 1 。随后，蚁群算法被用来求解i o b - s h o p 调度问题 1 t , i 4 1 、 指派问题i j 5 垮经典优化问题，得到了较好的效果。显示出蚁群算法在求解复杂 优化问题( 特别是离散优化问题) 方面的优越性，证明它是一种具有广阔发展前 景的优化算法。 由于基本蚁群算法进化收敛速度慢，且易陷入局部最优或出现停滞现象等缺 陷，学者相继对蚁群算法进行改进，提出了改进的蚁群算法。具有代表性的主要 有：1 9 9 6 年g a m b a r d e l l a 和d o r i g o 提出的自适应蚁群算法( a a s ) 1 1 6 a 7 1 ，该算 法采用伪随机选择机制对a s 的蚂蚁选择策略进行了改进，将确定随机选择策略 有机结合在一起：随后，s t u t z l e 等人提出了最大最小蚁群算法( m m a s ) 1 s l ，该 算法就信息素更新机制进行了改进，只增加最佳路径的信息素浓度，且将各路径 可能的信息素浓度限制在【t 嘶，t 。d ，从而更好地利用历史加快收敛速度，避 免较早出现停滞现象。m m a s 是到目前为止解决t s p 、q a p 等问题最好的a c o 类算法。 1 9 9 8 年a c o 的第一届学术会议( a n t 9 8 ) 召开，引起了研究者的广泛关 注。改进方案不断涌现并逐步完善蚁群算法的性能，如将蚁群算法与遗传算法结 合【1 9 1 ：给蚁群系统加入变异特征 2 0 1 等，而g b i l c h e v 与1 c p a r m e e 研究的求解连 续空间优化问题的a c s l 2 1 1 模型，则拓宽了蚁群算法应用研究范围，将蚁群算法 引入到求解连续空间优化问题中。应当指出。现阶段对蚁群算法的研究还只是停 留在仿真阶段，尚未能提出十分完善的理论分析，对它的有效性也没有给出严格 的数学解释。 兰州大学研究生学位论文 1 1 3 粒子群算法( p s o ) 受到人工生命研究结果的启发，粒子群算法c p s o ) 的基本概念源于对鸟群 和鱼群捕食行为的简化社会模型的模拟，1 9 9 5 年由社会心理学家j a m e s k e n n e d y 和电子工程师r u s s e l le b e r h a r t 等人提出t 2 2 乃，。由于p s o 算法概念简单，实现容 易，短短几年时间，p s o 算法便获得了很大发展，出现了许多改进p s o 算法， 并且已经应用于众多学科和工程领域。目前已被“国际演化计算会议( c e c ) ”列 为讨论专题之一。由于p s o 算法建立在对社会模型仿真的基础上，因而在方法 提出初期劳没有严格的数学基础，随着c l e r c 和v a nd e n & 嘞等x 研究成果t 2 4 2 5 , 2 6 1 的公开发表，p s o 算法的严格数学基础正在逐步建立。 基本p s o 是函数优化的有力工具，其优点是收敛速度快且需设置的参数较 少，缺点是易陷入局部极小点，搜索精度不高。针对这些缺点，目前典型的改进 算法有自适应p s o 算法、模糊p s o 算法、杂交p s o 算法、混合粒子p s o 算法 ( h p s o ) 、离散p s 0 算法等等。 其中自适应和模糊p s o 算法 2 8 1 是s h i 、e b e r h a r t 在研究惯性权值w 对优化性 能的影响 2 6 , 2 7 1 时，发现较大的w 值有利于跳出局部极小点，较小的w 值有利于 算法的收敛后提出来的。自适应p s o 算法通过线性地减小w 值动态地调整参数 w ，而模糊p s o 算法则在此基础上利用模糊规则动态调整参数w 以改善p s o 性 能。杂交和混合p s o 算法( h p s o ) 2 9 , 3 0 是受遗传算法、自然选择机制的启示， 将遗传算予与基本p s o 相结合而得。其中，杂交p s o 在基本p s o 中引入了杂交 算子，而混合p s o 则采用了自然选择机制。两者均取得了满意的结果，改善了 算法的性能。 基本p s o 算法是求解连续函数优化的有力工具，但对离散问题却无能为力。 因此k e n n e d y 和e b e r h a r t 发展了离散型p s o 算法口“。并将其应用于货郎担问题 ( t s p ) 的求解上，取得了较好的效果。离散p s o 算法扩展了基本p s o 算法的 应用领域，让我们看到了p s o 在一类组合优化问题中的应用前景。 目前p s o 算法已广泛应用于多目标优化、神经网络训练、模式分类、模糊 系统控制以及其他应用领域。文献 3 2 ，3 3 的研究表明，p s o 除了解决一般的函数 优化问题外，还能解决各种复杂的优化问题，而文献 3 4 ，3 5 1 q 6 将p s o 算法用于 训练神经网络，结果显示p s o 算法还是一种很有希望的训练神经网络的手段。 当前，c l e r c 等人正在进行自2 0 0 4 年l o 月开始的三年x p s ( e x t e n d e dp a r t i c l e s w a r m ) p r o j e e t 计划，2 0 0 6 年最新的研究动态包括“部落”式的( t r i b e ) a p s o 、 “瑞士军刀”式的( s w i s sk n i f e ) p s o t 3 6 , 37 1 等，此外，在动态环境( d y n a m i c e n v i r o n m e n t s ) 、离散优化问题、二进制p s o 、算法停滞及算法收敛等问题上的 4 兰州大学研究生学位论文 研究更进一步地系统、深入。总之，p s o 算法的应用十分广泛，具有十分诱人的 发展前景，吸引着众多学者持续不断地进行着研究。 1 1 4 鱼群算法( f s a ) 鱼群算法p m 是由李晓磊、邵之江等人提出的群智能优化算法的又一具体实 现模型。它采用了自上而下的寻优模式去模仿自然界鱼群的觅食行为，主要利用 鱼的觅食、聚群和追尾现象，构造个体的底层行为；通过鱼群中各个体的局部寻 优，达到全局最优值在群体中凸现的目的。在基本鱼群算法中引入鱼群的生存机 制、竞争机制以及鱼群的协调行为，可提高算法的优化效率。据此李晓磊等采用 分解协调的思想又构造了一种改进的人工鱼群算法，并以换热器系统为例，验证 该算法，结果表明该算法具有较好的收敛性。最近，俞洋、田亚菲、殷志锋等嘲 人开发的自适应人工鱼群算法a a f s af s 和a a f s ac s ，并将其运用于解决多 用户检测等问题上，特别克服了鱼群算法及其他群智能算法搜索的盲目性，较好 地保持了探索和开发之间的平衡，取得了明显的效果，具有一定的应用前景。同 前几种算法相类似，人工鱼群算法也属于进化算法，但由于诞生不久且算法建立 在仿真基础之上，故其性能以及理论基础还有待于我们进一步研究。 1 2群智能算法的发展 群智能算法是一类新型的进化算法，其主要特点是群体搜索策略及群体之间 的信息交换。这类算法对目标函数的性态没有特殊要求，在求解时不依赖于梯度 信息，因而特别适用于传统方法解决不了的大规模复杂问题，具有广泛的应用前 景，但群智能算法的研究刚刚起步，还有着更大的发展空间，下面我简要探讨一 下群智能算法将来的研究方向。 理论基础的研究。目前除了g a 已形成并具有了比较完善的系统分析方法和 定的数学基础外，其余算法均停留在仿真阶段，还未能提出一个完善、系统的 理论分析，对它们的有效性也没有给出严格的数学解释。因此，在进行理论分析 与研究的基础上，可进一步发展和完善各算法的性能指标。 算法的适用范围研究。没有免费午餐定理( n of l e el u n c ht h e o r e m ，n f l ) 告 诉我们，由于对所有可能函数的相互补偿，最优化算法的性能是等价的，即不可 能存在一个普遍适用于任何问题的优化算法，因此，研究各群智能算法的适用范 围成为一件必要和紧迫的研究任务。 系统框架的构建。目前这几种群智能算法均基于仿生机理，且具有许多相似 特征。因此系统地建立算法框架有利于该领域研究的深入及混合型算法的发展， 兰州大学研究生学位论文 从而不断提高算法性能。 6 兰州大学研究生学位论文 2 1 群智能 2 1 1 蚁群算法 2 群智能各优化算法分析与比较 蚁群算法由意大利学者c o l o r n i a 、d o r i g o 朋和m a n i e z z o 盱1 9 9 2 年首先提出 的一种新型模拟进化算法。这种算法用蚁群在搜索食物源的过程中所体现出来的 寻优能力来解决一些离散系统优化中的困难问题。如用该方法求解旅行商问题、 指派问题、调度问题等，取得了一系列较好的实验结果。蚁群算法是一种新型的 模拟进化算法，鉴于目前国内尚缺乏这一方面的研究，远未像遗传算法、模拟退 火等算法那样形成系统的分析方法和坚实的数学基础，有许多问题有待进一步研 究，如算法的收敛性、理论依据等更多细致的工作还有待于进步展开。 2 1 1 1 算法原理 像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径， 原因是什么昵? 虽然单个蚂蚁的行为极其简单，但由这样的单个简单个体所组成 的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还 图2 1 蚁群觅食过程示意图 能适应环境的变化，比如在蚂 蚁运动路线上突然出现障碍 物时，蚂蚁能够很快重新找到 最优路径。蚂蚁是如何完成这 些复杂任务的呢? 人们经过 大量的研究发现，蚂蚁个体间 通过一种称为信息素 ( p h e r o m o n e ) 的物质进行信 息传递，从而相互协作，完成 复杂任务。蚂蚁在运动过程 中，能够在它所经过的路径上 留下该物质，并以此指导自己 的运动方向。蚂蚁倾向于朝着信息素强度高的方向移动。因此，由大量蚂蚁组成 的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多， 7 兰州大学研究生学位论文 则后者选择该路径的概率越大。蚂蚁个体之间就是通过这种信息的交流达到搜索 食物的目的的。这里，我们举一个简单的例子来形象地说明蚁群路径搜索的原理 和机制。 假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源( 如图2 1 所 示) ： 巢一甲乙丁一食和巢一甲丙丁一食，分别具有长度4 和6 。蚂蚁在单 位时间内可移动一个单位长度的距离。开始时所有道路上都没有留下任何信息 素。 在r = 0 时刻，4 0 只蚂蚁从巢穴出发移动到“甲”，它们以相同概率选择向 北或向南两条道路，因此平均有2 0 只蚂蚁向偏北方向走，2 0 只向偏南方向走； 在t = 4 时刻，第一组到达食物源的蚂蚁将折回，此时第二组蚂蚁到达“丙 丁”的中点处； 在r = 5 时刻，两组蚂蚁将在“丁”点相遇。此时“乙丁”上的信息素数量和“丙 丁”上的相同，因为各有2 0 只蚂蚁选择了相应的道路，从而有l o 只返回的蚂 蚁将选择“丁乙”而另l o 只蚂蚁将选择“丁丙”，第二组蚂蚁继续向食物方向移动： 在t = 8 时刻，前1 0 只蚂蚁将返回巢穴，后1 0 只蚂蚁在“丙甲”中点处， 而“丁丙”中点处以及乙点上各有t o 只蚂蚁； 在产9 时刻，前5 只蚂蚁又来到甲处并再次面对往北还是往南的选择。此 时“甲乙”上的轨迹数是4 0 而“甲丙”上是3 0 ，因此将有较多的蚂蚁选择前往偏 北方向，从而增加了该路线上的信息素数量。 随着该过程的继续，两条道路上的信息素数量的差距将越来越大，直至绝大 多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在 相同的时间区间内，短的路线会有更多的机会被选择。 蚁群算法是一种随机搜索算法，与其他模型进化算法一样，通过候选解组成 的群体进化过程来寻求最优解。该过程包含两个阶段，即适应阶段和协作阶段。 在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解 之间通过信息交流，以期产生性能更好的解。 2 1 1 2算法机制 作为与遗传算法同属一类的通用型随机优化方法，蚁群算法不需要任何先验 知识，最初只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得有规律， 并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空问的“了解”机制主要以 下包括3 个方面： a 、蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被选择，由 8 兰州大学研究生学位论文 此在蚁群算法中建立禁忌( t a b u ) 列表来进行模拟； b 、蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信。蚂蚁在所选择的路径上会 释放一种叫信息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行 选择，这样信息素就成为蚂蚁之间进行通信的媒介； c 、蚂蚁的集群活动。通过只蚂蚁的运动很难到达食物源，但整个蚁群进 行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息 素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从 而进一步增加该路径的信息素强度，而某些路径上通过的蚂蚁较少时，路径上的 信息素就会随时间的推移而蒸发。因此，模拟这种现象就可利用群体智能建立路 径选择机制，使蚁群算法的搜索向最优解方向推进。 蚁群算法所利用的搜索机制呈现出一种自催化或正反馈( a u t oc a t a l y t i c b e h a v i o r ) 的特征，可将蚁群算法模型理解成增强型学习系统( r e i n f o r c e m e n t l e a r n i n gs y s t e m ) 。这种选择不满足马尔可夫性。这是因为蚂蚁每次选择路径后 就将路径存到t a b u 列表中，选择下一条路径时，只能在列表不包括的路径中进 行选择，而t a b u 列表正是蚂蚁前面所有时刻采取的行动形成的。因此，蚁群算 法模型不是一个马尔可夫决策过程，也不能理解为动态规划( d y n a m i cp r o g r a m ) 和蒙特卡罗( m o n t e c a r l o ) 一类的增强学习算法，而应理解为一种q 学习。信 息素可理解为d 学习中的回报。 2 1 1 3 基本算法 在解决货郎担( t s p ) 问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路 线，并留下虚拟“信息素”。虚拟的“信息素”会挥发，每只蚂蚁每次随机选择要走 的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较 浓的路线更近”的原则，即可选择出最佳路线。由于这个算法采用了正反馈机制， 使得较短路径具有较大机率被选择，并且采用了概率算法，所以能较好地跳出局 部最优解。 以t s p 问题为例，简要介绍其基本算法。 设有历只蚂蚁，每只蚂蚁有如下特征： 它根据以城市距离和连接边上外激素的数量为变量的概率函数选择下一个 城市( 设( f ) 为t 时刻边e ( i ，_ ，) 上外激素的强度) 。规定蚂蚁走合法路线， 除非周游完成，不允许转到已访问的城市，由禁忌表控制( 设t a b u k 表示第七只 蚂蚁的禁忌表，t a b u k ( s ) 表示禁忌表中第s 个元素) 。它完成周游后，蚂蚁在它 每一条访问的边上留下外激素。 9 兰州大学研究生学位论文 设b a t ) ( i = j ，甩) 是在，时刻城市f 的蚂蚁数，设脚= 6 i ( f ) 为全部蚂蚁 个城市( 设( f ) 为t 时刻边e ( i ，j ) 上外激素的强度i n t e n s i t y ) 。 p ，( t ) 表示在t 时刻蚂蚁七由位置j 转移到位置的概率。 。f 毒避攀小口黼d 荔= 。毛榭醒( f ) 刊“w “ 旺，) 其中，a l l o w e d k = 0 ，l 一h 1 ) 一t a b uk 表示蚂蚁七下一步允许选择的城 市，与实际蚁群不同，人工蚁群系统具有记忆功能，t a b u ( k = l ，2 ，m ) 用 以记录蚂蚁k 当前所走过的城市，集合t a b u k 随着进化过程做动态调整。叩打表 示边弧( f ，) 的能见度( v i s i b i l i t y ) ，用某种启发式算法算出，一般取r 口= l 西， 幽表示城市i 与城市j 之间的距离。n 表示轨迹的相对重要性，芦表示能见度 的相对重要性，p 表示轨迹的持久性，1 一p 理解为轨迹衰减度随着时间的推移， 以前留下的信息逐渐消失，用参数l p 表示信息消逝程度，经过2 个时刻， 蚂蚁完成一次循环，各路径上信息量要根据以下公式做调整： f f o + n ) = p r u ( t ) + 乃 ( 2 2 ) 勺= ap k ( 2 3 ) i = i 表示第k 只蚂蚁在本次循环中留在路径f _ ，上的信息量，研表示本 次循环中路径u 上的信息量增量。ff ( f ) 、7 f ( r ) 、助( t ) 的表达形式根据 具体问题的不同而有相应的改变，d o r i g om 给出3 种模型，分别为蚁周( a n t - c y c l e s y s t e m ) 、蚁量( a n t - q u a n t i t ys y s t e m ) 、蚁密( a n t - d e n s i t ys y s t e m ) 模型，分别表示 如下： 1 ) 蚁周模型： 0 兰州大学研究生学位论文 ：j 詈，i m 咄t h a n tw h i c h a t t h i “t e r a t i o n 印叫。：舢 【0 ， e l s e li 表示第七只蚂蚁环游一周的路径长度，q 为常数a 2 ) 蚁量模型： 呓：罢。f m e k m a n t 胛州k 似e e n t i m “肌d t + l 。：射 3 ) 蚁密模型： 峰行舭p a s 哨k 骶e n n m e 如t + l 晓6 ， 它们的区别在于，蚁周模型采用了全局信息，而蚁量、蚁密模型采用的是局 部信息。在求解t s p 问题时，仿真证明蚁周模型性能优于蚁量、蚁密模型，因 而通常采用蚁周模型。 2 1 1 4 算法的基本步骤 1 ) c 一0 ；( n c 为迭代步数或搜索次数) 各f 和“的初始化，将r t l 只 蚂蚁置于, 个顶点上； 2 ) 将各蚂蚁的初始出发点置于当前解集中，对每只蚂蚁| i ( 后= l ，2 ，所) ， 按概率pf 移到下顶点，将顶点_ ，置于当前解集； 3 ) 计算各蚂蚁的路径长度l i ( | = l ，2 ，m ) ，记录当前的最好解； 4 ) 按更新方程修改轨迹强度； 5 ) 对各边弧( f ，) ，置勺一0 ，聊+ ，l c + 1 ： 6 ) 若聊 k 。时取= k 。；当 4 4 三暑翟：“：3 等：嚣薯。；望：。 口 图2 7 收缩因子在c l e r e 类型1 中的应用 其中e o ，1 ，标准值为1 ，可做适度增减来改变收缩度；t r e l e a 4 1 1 等人 提出了p 的两种取值，t y l $ 2 取4 1 ，从而使收缩系数z = o 7 2 9 8 4 4 ，t y p e s l 取4 2 6 6 7 ，收缩系数z = 0 6 。c l e r c 在推导出收缩系数法时，不再需要最 大速度限制。但是，后来的研究发现设定最大速度限制可以提高算法的性 能。从数学上分析，惯性权值w 和限定系数z 这两个参数是等价的。当= 1 和0 8 时，收缩因子曲线如图2 7 所示。 根据张丽平等人的研究 4 2 1 ，算法收敛的充分条件为 w ；( q + c 2 ) 一1 ，w o ，即当满足上述条件时，粒子必定收敛到极值 点。 在原始p s o 算法中，一般设定c l = c 2 = 2 ，w = l 。根据上式 ( c l + c 2 ) 一1 = l = w ，恰好是既不满足w l 又不满足w l 的一 种情况。原始p s o 算法造成的粒子轨迹为正弦函数，其幅度和频率由初始位置和 初始速度确定，其粒子的轨迹是发散的，所以，在原始p s o 算法中需要限制速 度的范围【一。，k 。 来限定粒子的运动轨迹。 在收缩系数p s o 中，当c l = c 2 = 1 4 9 6 1 8 ，z = w = o 7 2 9 8 时，以及 a = c 2 = 1 2 8 ，z = ，= 0 6 时，均满足粒子群算法收敛条件，其中自= z 伊l ，c 22z 妒2 1 7 兰州大学研究生学位论文 因此，收缩系数p s o 的参数可使粒子轨迹收敛，而不需限定对粒子的速度 。 2 1 2 。6 算法的伪代码 f o re a c hp a r t i c l e i n i t i a l i z ep a r t i c l e e n d d o f o re a c hp a r t i c l e c a l c u l a t ef i t n e s sv a l u e i ft h ef i t n e s sv a l u ei sb e t t e rt h a nt h eb e s tf i t n e s sv a l u e ( p b e s t ) i nh i s t o r ys e t c u r r e n tv a l u ea st h en e w p b e s t e n d c h o o s et h ep a r t i c l ew i t i lt h eb e s tf i t n e s sv a l u eo fa l l ( o rl o c a l ) t h ep a r t i c l e sa s t h eg b e s t ( o rl b e s t ) f o re a c hp a r t i c l e c a l c u l a t ep a r t i c l ev e l o c i t ya c c o r d i n ge q u a t i o n u p d a t ep a r t i c l ep o s i t i o na c c o r d i n ge q u a t i o n e n d w h i l em a x i m u mi t e r a t i o n so rm i n i m u me l t o rc r i t e r i ai sn o ta t t a i n e d 在每一维粒子的速度都会被限制在一个最大速度，如果某一维更新后 的速度超过用户设定的，那么这一维的速度就被限定为。 2 1 2 7 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和p s o 的比较 大多数演化计算技术，包括遗传算法和p s o 优化算法等都是用同样的过程， 即 a 种群随机初始化； b 对种群内的每一个个体计算适应值( f i t n e s sv a l u e ) 。适应值与最优解的距离 直接有关； c 种群根据适应值进行复制； d 如果终止条件满足的话，就停止，否则转步骤b 。 从以上步骤，我们可以看到p s o 和g a 有很多共同之处。两者都随机初 始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机 兰州大学研究生学位论文 搜索。两个系统都不是保证一定找到最优解。 但是，p s o 没有遗传操作如交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ，而是根据 自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。 与遗传算法比较，p s o 的信息共享机制是很不同的。在遗传算法中，染色 体( c h r o m o s o m e s ) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域 移动。在p s o 中，只有g b e s t ( o rl b e s t ) 给出信息给其他的粒子，这是单向的 信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大 多数的情况下，所有的粒子可能更快的收敛于最优解。 2 1 2 8 人工神经网络和p s o 的关系 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 是模拟大脑分析过程的简单 数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始 利用演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术来研究人工神经网络的各个方面。 演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构( 网 络拓扑结构，传递函数) ，网络学习算法。 不过大多数这方面的工作都集中在网络连接权重和网络拓扑结构上。在g a 中，网络权重和( 或) 拓扑结构一般编码为染色体( c h r o m o s o m e ) ，适应度函数 ( f i t n e s sf u n c t i o n ) 的选择一般根据研究目的确定。例如在分类问题中，错误分类 的比率可以用来作为适应值。 演化计算的优势在于，可以处理些传统方法不能处理的例子。例如不可导 的节点传递函数或者没有梯度信息存在。但是缺点在于，a 、在某些问题上性能 并不是特别好。b 、网络权重的编码而且遗传算子的选择有时比较麻烦。 最近已经有一些利用p s o 来代替反向传播算法来训练神经网络的论文。研 究表明p s o 是一种很有潜力的神经网络算法。p s o 速度比较快而且可以得到 比较好的结果，而且还没有遗传算法碰到的问题。 这里用一个简单的例子说明p s o 训练神经网络的过程。这个例子使用分类 问题的基准函数( b e n c h m a r kf u n c t i o n ) i r i s 数据集( i r i s 是一种鸢尾属植物) 。 在数据记录中，每组数据包含i r i s 花的四种属性：萼片长度，萼片宽度，花瓣 长度，和花瓣宽度，三种不同的花各有5 0 组数据。这样总共有1 5 0 组数据或 模式。 我们用3 层的神经