（运筹学与控制论专业论文）动态环境下改进的粒子群算法.pdf

一 j，_-_l-1li j，l_， at h e s i si no p e r a t i o n a lr e s e a r c ha n d c y b e r n e t i c s i m p r 0 v e d p a r t i c l es w a r m o p t i m i z a t i o n a l g o r i t h m u n d e r d y n a m i c e n v i r o n m e n t b y x u p i n g s u p e r v i s o r ： p r o f 色s s o rz h a n gq i n g l i n g ，p r o f e s s o rd u a nx i a o d o n g n o r t h e a s t e mu n i v e r s i t y j a n u a r y2 0 0 8 帅6洲5 肌424啪8 iiii_y ll1lr k 、j_ ，0僵14_ ，+地。 广。i b，+，l，一 l j _ f 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献都己经在论文中作了明确的说明并表示谢 ：也 恧。 学位论文作者签名：徐军 日期：珈害，弓 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： t r ；，鼻 东北大学硕士学位论文摘要 动态环境下改进的粒子群算法 摘要 粒子群优化算法( p 抓i c l es 硼眦o p t i m i z a t i o n ，简称p s 0 ) 是由k e m l e d y 和 e b e r l 斌于1 9 9 5 年提出的一种基于群智能( s w 锄i n t e l l i g e n c e ) 的演化计算技术。 它是在鸟群、鱼群和人类社会行为规律的启发下提出的。粒子群优化算法在函数 优化、神经网络训练、模式分类、模糊系统控制以及其它工程领域都得到广泛地 应用。本文综述了粒子群算法的基本思想和提出背景群智能计算，详细介绍 了基本粒子群算法及其各种改进算法。本文主要将粒子群算法与进化规划相结 合，在动态优化环境下给出一种改进的粒子群算法。在不同动态优化环境下对算 法的跟踪效果进行了实验；在此基础上，引入了种群熵的概念，分析了改进的粒 子群算法的种群多样性与跟踪效果的关系。 本文重点包括以下两个方面： ( 1 ) 由于基本p s o 方法种群多样性损失过快，进化过程中易于陷入局部极值， 引起算法过早收敛，这就使基本p s o 方法对动态变化的极值点不能进行及时有 效的跟踪。本文在动态优化环境下给出一种改进的粒子群算法，并在不同动态环 境下将这种方法与现有的几种动态优化环境下的粒子群算法在跟踪效果上进行 了对比。实验表明，改进的粒子群方法有很强的适应动态优化环境的能力，能够 对动态变化的最优点进行有效的跟踪，无论在跟踪速度还是跟踪精度上都比其它 方法有明显提高。 ( 2 ) 在动态优化环境下，对现有粒子群算法的种群多样性进行了分析，并对 改进的粒子群算法的种群多样性与跟踪效果的关系进行了实验。实验表明种群中 粒子运动的不同方式对种群多样性的变化及算法的搜索效果有影响。群体中如果 发散个体太少，算法在环境变化时不一定能够跟踪到最优点，跟踪效果也变差。 而群体中发散的个体太多，会降低群体的趋同效果，导致跟踪误差增大，针对不 同的问题需要选择合适的群体多样性保持效果。 关键词：群智能；粒子群优化；种群熵；动态优化环境：进化规划 簟 l j -ii_，jl*bil 、，- l， i m p r o v e dp 抓i c l es w 甜mo p t i m i z a t i o nu n d e r d y n a m i ce n v i r o n m e n t a b s t r a c t t 1 1 ep a n i c l es w 撇o p t i m i z a t i o n ( p s o ) m e t h o d 懿a n e v o l u t i o r l a r yt e c l l i l i q 眦w 私 o r i g i m l l yi n t r o d u c e db yk e r u l e d y 锄de b e r h 甜i n19 9 5 1 1 1 ep s oi d e aw a si n s p i r e d b yn a t u r a lc o n c e p t ss u c h 觞b i r dn o c k i n g ，f i s hs c h o o l i n g 觚dh u m a i ls o c i a lr e l a t i o i l s n h a sb e e n 印p l i e ds u c c e s s 如l l yi nv 撕o l l s o p t i m i z a t i o np r o b l e m s ，n e u r a ln e 铆o r k s 舰i 1 1 i n g ，p a t t e mc l 嬲s i f i c a t i o n ，如z z ) ，s y s t e mc o r l t r o la n ds o m ee n g i n e e r i n gd o m a i 璐 t m s p a p e rs u m m 撕z e dt h ei d e 嬲锄db a c k g r o u l l d so ft h ep s om e m o d ，i n t r o d u c e dt h e s 协d a r dp s om e t h o d 趾ds o m eo t h e r i m p r o v e dp s 0m e t h o d si nd e t a i l l s b v c o m b i i l i n gt h e i d e a0 fp s o 觚de v o l u t i o n a 叮p r 0 鲫姗m i n g ( e p ) ，“s p a p e r i 劬r o d u c e d觚 i m p r o v e d p s om e t h o du d e rt l l e d y n 锄i ce n v i r o m n e n t ， t h e e 疏c t i v e n e s so ft l l i sm e t h o di i l t r a c k i n gc h a n g i n go p t i m 啪w 弱i n v e s t i g a t e du i l d e r d i 虢r e n t c h a j l g i n g e n v i r o m n e n t s f u r t h e 珊o r e ，w ei n 仃d d u c e dm ec o n c e p to f p o p u l a t i o ne n 仃o p y 觚d 锄a l y z e dt h er e l a t i o n sb e t 、e e nt h ep o p u l a t i o nd i v e r s 时a i l d t l l ee f f e c t i v e n e s so f t r a c k i n gc h a n g i n go p t i m 啪 t h i sp a p e rc o n t a i n st w o i m p o r t a n ta s p e c t s ： f i r s t ，t h es t a i l d a r dp s om e t h o d sp o p u l a t i o nd i v e r s i t yo r e nl o s s e st o of a s ti nt h e e v o l v i n gp r o c e s so fw h i c hr c s u l t e di nt h ep r c m a t u l eo ft h ca l g o r i t h m 1 l l i sm a k e si t c 锄tt m c kc h a n g i n go p t i m u ms u c c e s s m l l y 觚dp r o m p t l y 1 1 1 i sp a p e ri n t r o d u c e d 跹 i m p r o v e dp s om e t h o d ( i p s o ) u n d e rt t l ed y n 锄i ce n v i r o i l i i l e n t s ，t h ee 位c t i v e n e s st l l i s m e t h o d 锄ds o m eo t h e rm e t h o d si nt r a c k i n gc h a n g i n go p t i m u mw e r ee x p e r i m e n t e d u n d e rd i f f e r e n tc h a n g i n ge n v i r o l m e n t s e x p e r i m e n t si n d i c a t et h a tt h ei p s om e t h o d c 锄a p p l i e di nd ) r i l 锄i ce n v i r o m e n t sm o r es u c c e s s f u l l yt h 锄o t h e rm e t h o d s ，t h es p e e d 髓dp r e c i s i o nw e r ei m p r o v e d s e c o n d ，t 1 1 i sp a p e r 锄a l y z e dt h ep o p u l a t i o nd i v e 娼i t ) ，o fs o m ep s om e t h o d su n ( 1 e r d y n 锄i ce n v i r o m n e n t s f u f t h e m o r e ，r e l a t i o n sb e t w e e nt h ep o p u l a t i o nd i v e r s i t ya i l d i i i ， m ee f f e c t i v e n e s sw e r ee x p e r i m e m e d e x p e 血1 e n t si i l d i c a t e d t 胁p 积i c l e ，sd i f 诧r e n t m o v e m e m sc 觚a f j e - e c tm ep o p u l a t i o nd i v e r s i 锣锄dt 1 1 e e 伍；c t i v e n e s so fn - a c l ( i n g c l l a i l g i n go p t i m u m i ft l l em l n l b e ro fd i v e 玛e n tp a i t i c l e si i lt 1 1 ep o p u l a t i o ni st o os m a l l 。 恤m e t h o dp r o b a b l yc 锄t 咖kt h ec h 觚g i n go p t i m 啪，b u ti ft h j sn u l l l k i st o ol a r g e ， 龇p o p u l a t i o n sc o n v e 培e n c ei sw e a k e n e d ，仃a c h n ge 玎0 ri s 妣r e 弱e d s o d i 舵r e n t p r o b l e m ss h o l l l dh a v ed i f 诧r e n tp o p u l a t i o n d i v e r s i t ) rb a s e do nt h en e e d so ft h e p r o b l e m s k e yw o r d s ：s w a 肋i n t e l l i g e n c e ，p 积i c l es 啪锄o p t 妇i z a t i o i l p o p u l a t i o ne m o p y d y l l 锄i ce n v i r o n m e n t ，e v o l u t i o n a r yp r 0 伊锄m 她 i j fl，io 、 ，：；， r 0i i 东北大学硕士学位论文目录 目录 独创性声明1 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 优化问题1 1 2 动态优化问题3 1 3 群智能及其技术发展现状5 1 4 月、结。6 第二章群智能计算方法7 2 1 蚁群算法7 2 2 粒子群算法。9 2 3 文化算法9 2 3 1 文化算法的起源9 2 3 2 文化算法的框架1 0 2 3 3 文化算法的理论1 1 2 3 4 文化算法算例1 2 2 4 三种算法的关系。1 4 2 5 小结1 6 第三章粒子群算法原理1 7 3 1 基本粒子群算法1 7 3 1 1p s o 算法基本原理1 8 3 1 2p s o 的信息交换方式2 0 3 2 粒子群算法的改进2 1 3 2 1 基于参数的改进算法2 1 3 2 2 基于行为模式的改进算法2 2 3 2 3 融合其它算法的改进算法2 4 。卜、 目录 ：1 6 2 7 2 8 ：；】【 ：；：； 3 z i 3 l 3 1 ； 5 1 2a m t o m j c s w a n i l 方法。3 6 5 2 动态条件下改进的粒子群算法3 7 5 2 1 算法描述。3 8 5 2 2 实验环境及参数设置3 8 5 2 3 实验及结果分析3 9 5 3 小结4 1 第六章种群多样性与跟踪效果的关系研究4 2 6 1 种群多样性的度量4 2 6 2 种群多样性与跟踪效果的关系研究4 3 6 2 1 实验环境及参数设置4 3 6 2 2 实验及结果分析4 4 6 3 小结4 7 第七章总结与展望4 8 参考文献4 9 致j 射。5 3 附录：5 4 v 1 ，+“， 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早瑁v 匕 粒子群算法( p a n i c l es w a 咖o p t i m i z a t i o n ，p s o ) n3 是由k e l u l e d y 和e b e r h 硪 于1 9 9 5 年提出的一种新的群体智能算法，其起源于对鸟群群体行为的模拟。p s o 算法简洁，易于实现，没有很多的参数需要调整，而且不需要优化函数的梯度信 息，所以算法一经提出就引起了广泛的关注，并被应用于很多研究领域。粒子群 优化算法不同于传统的确定性优化算法，它属于进化计算、群智能范畴，是一种 灵活的，具有随机性的优化算法。 1 1 优化问题 优化方法是科学研究、工程技术和经济管理等领域的重要研究工具。它所研 究的问题是讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计 参数，使设计方案既满足设计要求又能降低成本：资源分配中，怎样分配有限资 源，使分配方案既能满足各方面的基本要求，又能获得好的经济效益。在人类活 动的各个领域中，诸如此类，不胜枚举。优化这一技术，正是为这些问题的解决 提供理论基础和求解方法，它是一门应用广泛、实用性很强的科学。 典型的最优化问题模型可以描述为如下形式： m i n 厂( x ) l x d ( 1 1 ) 其中x = ( 五，吃，吒) 。表示一组决策变量，葺( f 1 ，刀) 通常在实数域r 内取 值，称决策变量的函数厂( x ) 为该最优化模型的目标函数；d 为玎维欧氏空间r ” 的某个子集，通常由一组关于决策变量的等式或不等式即约束函数来刻画。若 d 均有厂( x ) 厂( x ) ，称x d 为最优化模型m i n ( x ) i x d 的最优 解，称目标函数值厂( f 1 为该最优化问题的最优值。 在优化问题中，目标函数种类繁多，有的是线性的，有的是非线性的；有的 是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入， 人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解是不可能的，因 而求出其近似最优解或满意解是人们的主要着眼点之一。总的说来，求最优解或 近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。 ，卜、 东北大学硕士学位论文第一章绪论 ( 1 ) 枚举法。枚举出可行解空间内的所有可行解，以求出精确最优解。对于 连续问题，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永 远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低。 ( 2 ) 启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解 或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必 须找出其特有的启发式规则。这种启发式规则无通用性，不适合于其他问题。 ( 3 ) 搜索算法。寻找一种搜索算法，该算法在可行解空间的一个子空间内进 行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够 得到问题的最优解，但若适当地利用一些启发知识，就可近似地使解的质量和求 解效率达到一种较好的平衡。 搜索算法可分为两大类：平行搜索法( s i m u l t a l l e o u sm e t h o d s ) 和序贯搜索法 ( s e q u e n t i a lm e t h o d s ) 。作平行搜索时，需要计算目标函数值的自变量节点位置在 事先一起选定。而作序贯搜索时则根据前一轮计算得到的目标函数值的情况用以 确定下一轮计算目标函数值的自变量节点位置，因此它带有迭代性。 搜索算法又可分为确定性搜索法和随机性搜索法两种。确定性搜索算法在寻 优过程中，一个搜索点到另一个搜索点转移有确定的转移方法和转移关系，因而 其过程可再现，其不足在于寻优结果与初值有关，初值选取不当往往有可能使搜 索永远达不到最优点。随机性算法在算法执行过程中加入随机性( 因为真正理论 意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数) ，需计 算算法输出结果的概率平均值。随机性算法往往比确定性算法计算时间少，但它 的准确率稍微降低。 最优化理论的发展之一是w ，o l p e r t 和m a c r e a d y 提出了没有免费的午餐定理 0 妯f r c el u i l c ht h e o r e m ，简称n f l ) 1 2 j 。该定理的结论是，由于对所有可能函数 的相互补偿，最优化算法的性能是等价的。该定理暗指，没有其它任何算法能够 比搜索空间的线性列举或者纯随机搜索算法更优。该定理只是定义在有限的搜索 空间，对无限的搜索空间结论是否成立尚不清楚。在计算机上实现的搜索算法都 只能在有限的搜索空间实施，所以该定理对现存的所有算法都可直接使用。 尽管该定理认为对所有函数集，任何最优化算法是等价的。但对某个函数集， 则结论不再成立。有限域内的所有函数集包括了该域内所有排列。很多函数没有 简洁的描述，故这些函数更多的表现为随机性。但大多数现实生活中的函数通常 2 ， 东北大学硕士学位论文 第一章绪论 有一定的结构。并有简洁的描述。这些类型的函数形成了所有函数集的相当多的 子集。这些考虑都使得n f l 发展增强版本来对更小的函数子集进行研究。 一个比较有建设性的方法是c s t e n s e n 等人口1 提出可搜索函数的定义，以及 对可搜索函数集，通常算法要比随机算法具有优越性。 本文与后者观点相同，也就是对有限的函数子集，可以设计出性能更优的算 法，这也是本文研究的一个重要基础。 1 2 动态优化问题 动态优化是相对静态优化而言的。静态优化问题中优化问题本身的各种状 态与时间无关，不随时间的变化而变化。然而，在实际环境中遇到的问题比较复 杂，问题本身往往随着时间的变化而变化。例如，在物流配送过程中，由于受到 客户优先级、交通环境等因素变化的影响，物流配送问题相应发生变化。在当前 时刻得到的最优值，不一定是下一时刻的最优值。这就需要对问题进行重新建模 求解，但也不能保证计算结果的实时有效性。所以，在动态系统中追踪系统极值 变化的优化问题一直备受关注。 在实际的很多优化问题中需要考虑一些不确定性因素的影响。一般来说， 优化问题中的不确定性大致分为以下几种情形h 1 ： ( 1 ) 待优化问题的适应值函数受到噪声的干扰。产生噪声的来源有很多，例 如：误差测量、随机仿真等因素。一个带有噪声的适应值函数可以描述如下： f ( x ) = e ( x ) + z p ( z ) 比，z ( o ，仃2 ) ( 1 2 ) 其中x 是设计变量，z 是一个附加的噪声，经常将其假设为0 和盯2 之间正态分 布的随机数。优化过程中可以测得的适应值是一个随机值厂( x ) + z 而非( x ) 的 值。因此，在实际优化过程中，式( 1 2 ) 中的适应值函数经常被近似为一些随机样 本和的平均值，即 ( x ) = 吉 厂( x ) + z ， ( 1 3 ) 1 - l 其中是样本的数目，f ( x ) 是f ( x ) 的近似值。 ( 2 ) 待优化问题的设计变量受到扰动。在这种情况下，通常的要求是当设计 东北大学硕士学位论文 第一章绪论 变量受到轻微扰动的情况下，优化问题的解要仍然能满足优化问题的需要，此时 的解称为鲁棒解，期望的适应值函数可以描述如下： ，( x ) = e ( x + 万) p ( 万膨 ( 1 4 ) 其中p ( 万) 是扰动万的概率分布函数。此时，( x ) 通常被称为有效适应值函数嫡1 。 由于有效适应值函数的这种解析形式不是总能够得到，所以一般将其近似为下面 的形式： 盒( x ) = 专喜厂( 彳+ 刚 ( 1 5 ) 其中是样本的数目，f ( x ) 是f ( x ) 的近似值。 ( 3 ) 待优化问题的目标函数的适应值随着时间的变化而变化，其形式为 f ( x ) = z ( x ) ( 1 6 ) 由于适应值函数随着时间发生变化，所以问题的最优解也随着时间的变化而变 化，这种情况下就需要优化算法能够对最优解的变化进行连续有效的跟踪，而不 是在优化函数发生变化的时候重新启动优化过程。 本文主要研究的动态优化问题就属于第( 3 ) 种情况，优化问题的目标函数使 用由m o r r i s o n 和d ej o n g 提出的d f l 函数嘲。它利用一些锥体的组合来产生的 环境。对于二维问题，d f l 函数中的静态评价函数被定义为： 厂( x ，y ) = m a x 瑚五 h ，一r ：石i j i 严i 孑= 订 ( 7 ) 其中是环境中锥体的个数，( x ，r ) 是第f 个锥体的顶点位置，只是第f 个锥 体的高度，足是第f 个锥体的斜度。图1 1 是由d f l 函数生成器随机生成的一个 适应度曲面。 图1 1 一个由d f l 生成的适应度曲面 f i g 1 1as u h c eo f f i 仃l e s sg e n e 戎l t e db yd f l 4 i 东北大学硕士学位论文第一章绪论 在优化过程中，目标函数厂( x ，】，) 随迭代的进行不断变化。这种变化可以通 过环境中锥体的变化来实现。根据每个锥体的可变性，动态优化环境可以分为两 种类别： ( 1 ) 一部分锥体发生变化而另一部分锥体不发生变化。 ( 2 ) 所有锥体都发生变化。 其中，发生变化的锥体的变化方式又可以分为三种： ( 1 ) 只变化锥体的高度； ( 2 ) 只变化锥体的位置： ( 3 ) 同时变化锥体的高度和位置； 1 3 群智能及其技术发展现状 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一 系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能 ( s 、 ，a mi n t e l l i g e n c e ) 中的群体( s w 锄) 指的是“一组相互之间可以进行直接通信或 者间接通信( 通过改变局部环境) 的主体，这组主体能够合作进行分布问题求解 。 而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性 。群集 智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的 解决方案提供了基础。目前，群智能计算采用的方法主要有三种：蚁群算法、粒 子群算法和文化算法。 群智能研究还处于萌芽阶段，还存在很多问题。首先，它们都是概率算法， 从数学上对于它们的正确性与可靠性的证明还是比较困难的，所做的工作也比较 少；其次，这些算法都是专用的算法，一个算法只能解决某一类问题，各种算法 之间的相似性很差，并且系统高层次的行为是需要通过低层次的昆虫之间的简单 行为交互涌现( e m e r g e ) 产生的。单个个体控制的简单并不意味着整个系统设计的 简单，我们必须能够将高层次的复杂行为( 也就是系统所要执行的功能，例如货 郎担问题、数据聚类、搬运箱子) 映射到低层次的简单个体的简单行为( 例如信息 素的遗留、物体的拾起与放下) 上面，而这二者之间是存在较大差别的，并且我 们在系统设计时也要保证多个个体简单行为的交互能够涌现出我们所希望看到 的高层次的复杂行为，这可以说是群体智能中一个极为困难的问题。 东北大学硕士学位论文第一章绪论 群智能有如下特点和优点：群体中相互合作的个体是分布的( d i 嘶h l t e d ) ， 这样更能够适应当前网络环境下的工作状态；没有中心的控制与数据，这样的系 统更具有鲁棒性限o b u s t ) ，不会由于某一个或者某几个个体的故障而影响整个问 题的求解；可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的 系统具有更好的可扩充性( s c a l a b i l 蚵) 。由于系统中个体的增加而增加的系统通信 开销在这里是十分小的；系统中每个个体的能力十分简单，这样每个个体的执行 时间比较短，并且实现也比较简单，具有简单性( s i m p l i c i 锣) 。 群智能的研究还处于初级阶段，并且存在许多困难，但是可以预言群智能的 研究代表了以后计算机研究发展的一个重要方向。国外的学者发明了很多群智能 仿生算法并利用其解决复杂的工程问题，国内很多学者主要的研究方向在算法的 改进和应用上，很少有学者提出过得到广泛认可的群智能算法。归结起原因，主 要是对技术背景和算法发现规律的认识不够，“不是苹果砸到每个人，都会找到 万有引力定律的”。 1 4 小结 本章首先介绍了优化问题，并在此基础上介绍了动态优化问题，最后介绍了 群智能技术的发展现状和面临的主要问题。 东北大学硕士学位论文第二章群智能计算方法 第二章群智能计算方法 2 0 世纪9 0 年代初，就产生了模拟自然生物群体行为的优化技术。d o r i g o 等 人从生物进化机理中受到启发，通过模拟蚂蚁寻径行为提出了蚁群优化算法口1 ； e b e r h a n 和k e i l i l e d y 基于对鸟群捕食行为的研究提出了粒子群优化算法；r e y n o d s 等人基于对人类社会演化过程的模拟提出了文化算法1 ，这些研究都可以称为是 群智能行为的研究。通常单个的自然生物个体并不是智能的，但是整个生物群体 却表现出处理复杂问题的能力，群体智能就是这些群体行为在人工智能问题中的 应用。本章将介绍群智能计算的三种主要方法：蚁群算法、粒子群算法和文化算 法。 2 1 蚁群算法 蚂蚁世界一直被人类学与社会学者关注，它们的组织体系和快速灵活的运转 能力始终是人类学习的楷模。蚂蚁有严格的组织分工和由此形成的组织框架。它 们在工作场合的自组织能力特别强，不需要任何首领的监督就可以形成一个很好 的团队而有条不紊地完成工作任务。 蚂蚁个体的行为极其简单，但由这些简单的个体所组成的蚁群却表现出极其 复杂的行为特征，能够完成复杂的任务；不仅如此，蚂蚁还能够适应环境的变化， 如在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚂 蚁个体之间是通过一种称之为“信息素( p h e r o m o n e ) 的物质进行信息传递的， 从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之 间的信息交流与相互协作起着重要的作用阳3 。 蚂蚁觅食过程中，会在它走过的路径上留下“信息素 ，以此作为蚁群前往 食物所在地的标记，信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采 取不同路线回到巢中，那么比较绕弯的一条路线上信息素的气味会比较淡，蚁群 将倾向于沿另一条更近的路线前往食物所在地。而且蚂蚁在运动过程中，能够感 知这种物质的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着该物 质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信 息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 东北大学硕士学位论文 第二章群智能计算方法 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 如图2 1 所示，蚂蚁的移动路线可沿a b c ，也可沿a c ，设各蚂蚁寻到食物 后沿原路回穴，并在路上留下信息素，那么因a c 路径短，故当它们沿a c 返回 时，就在a c 上留下两次信息素。而沿a b c 返回者，因其路径长，在相同的时 间内，从c 点未能返回a 点，所以在a 点附近只能留下一次信息素( 即其上的信 息素的浓度比a c 上的浓度淡) ，所以这时从蚁穴出来寻食者就会沿浓度大的路 径a c 行走。最后大多数的蚂蚁都会沿较短的路程进行寻食。利用这个原理科学 者们设计了蚂蚁优化算法用来求解最短路径问题。 b 图2 1 蚂蚁觅食过程演示 f i g 2 11 1 1 ep r c i c e s so f 瓣s a r c h i n gf o rr o d 受到蚂蚁觅食过程中通信机制的启发，9 0 年代d o r i g o 提出了蚁群优化算法 ( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 来解决随机算法学中经典的“t s p 问题 如 果有玎个城市，需要对所有刀个城市进行访问且只访问一次的最短距离。 蚁群优化算法设计虚拟的“蚂蚁 将摸索不同的路线，并留下会随时间逐 渐消失的虚拟“信息素 。虚拟的“信息素 也会挥发，每只蚂蚁每次随机选择 要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息 素较浓的路线更近 的原则，即可选择出最佳路线。由于这个算法利用了信息的 正反馈机制，使得较短的路径能够有较大的机会被选择，并且由于采用了概率算 法，所以它能够不局限于局部最优解。 作为一种随机优化方法，蚁群算法不需要任何先验知识，最初只是随机地 选择搜索路径，随着对解空间的“了解”，搜索变得有规律，并逐渐逼近直至最 终达到全局最优解。蚁群算法对搜索空间的“了解”机制主要包括三个方面： ( 1 ) 蚂蚁的记忆：一只蚂蚁搜索过的路径在下次搜索时就不会再被选择。 ( 2 ) 蚂蚁利用信息素进行相互通信：蚂蚁在所选择的路径上会释放信息素， 东北大学硕士学位论文第二章群智能计算方法 当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成为蚂 蚁之间进行通讯的媒介。 ( 3 ) 蚂蚁的集群活动：通过一只蚂蚁的运动很难到达食物源，但整个蚁群进 行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息 素数量也越来越多，导致信息素增大，蚂蚁选择该路径的概率随之增加，从而进 一步增加该路径的信息强度；而某些路径上通过的蚂蚁较少时，路径上的信息素 就会随时间的推移而蒸发。因此，蚁群算法所利用的搜索机制呈现出一种正反馈 的特征。可将蚁群算法模拟理解成增强型学习系统。 2 2 粒子群算法 粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作 与竞争产生的群体智能来指导优化搜索。与进化算法比较，p s o 保留了基于种群 的全局搜索策略，但是其采用的速度一位移模型操作简单，避免了复杂的遗传操 作。它特有的记忆功能使其可以动态跟踪当前的搜索情况调整其搜索策略。因此， 与进化算法比较，粒子群优化算法是一种更高效的并行搜索算法。由于粒子群算 法收敛速度快，设置参数少，近年来受到学术界的广泛重视，并且提出了许多针 对控制参数的改进方案和其它改进方案来增强算法逃出局部极小点的能力n0 1 。文 献 1 0 详细介绍粒子群的基本算法和一些主要的改进算法。粒子群算法的原理将 在第三章中作详细介绍。 粒子群优化算法在函数优化、神经网络训练、模式分类、模糊系统控制以及 其它工程领域都得到广泛地应用，同时它也有着深刻的智能背景，非常适合对群 体行为进行研究。 2 3 文化算法 2 3 1 文化算法的起源 从人类学角度来看，文化被定义为“在社会中的不同人群之间和不同年代的 人群之间历史地传递的，用符号表示的概念现象的系统1 1 h 。“c u l t u r a l 一词在 麦克米伦高阶词典描述为“包括知识、信念，艺术，习惯和其它社会人能获得的 东北大学硕士学位论文第二章群智能计算方法 能力和养成的习惯”。文化的定义假定文化的内容中存在一般的智力知识。在人 类社会中，文化被看成是保存信息的载体，这些信息可以被社会的所有成员获得 并用来指导他们的行为。换句话说，文化的继承给社会的新一代成员提供信息和 指导来帮助他们适应环境。没有这些信息，个体人适应环境的唯一方法就是通过 试验和犯错误来获得经验。 2 0 世纪9 0 年代初就产生了模拟自然生物群体行为的优化技术，基于对人类 社会演化过程的模拟，r e y n o d s 提出了文化算法，其重要思想就在于从进化的种 群中获取待解决问题的知识，并反馈这些知识用于指导搜索过程。文化算法是一 种用于解决复杂计算的新型全局优化搜索算法，是一种基于种群的多进化过程的 计算模型，为进化搜索机制和知识存储的结合提供了构架。任何一种符合文化算 法要求的进化算法，都可以嵌入文化算法框架中，作为种群空间的一个进化过程。 目前文化算法已应用于资源调度，函数优化，图象处理，数据挖掘，故障诊断等 领域。 2 3 2 文化算法的框架 文化算法将算法的演化看作是在两个层面上：微观层面和宏观层面之间相互 交互、共同合作的继承系统。它由两个空间组成：群体空间和信念空间。微观层 面的演化发生于群体空间，宏观层面演化发生于信念空间。在微观层面，利用演 化算法的演化群体进行迭代求解形成知识信息；在宏观层面，知识群体保存上述 知识信息，并通过与微观层面的交流，对微观层面的后续演化迭代进行指导。在 文化算法中称前者为群体空间，称后者为信念空间，其主要思想就是保存群体可 接受的知识，抛弃不接受的知识。所以，应用文化算法解决全局优化问题，就是 用可接受的全局最优点的信息来引导微观群体的演化。 文化算法的基本框架如图2 2 所示，种群空间和信念空间是两个相对独立的 进化过程，通过一定的通讯协议相互联系。在种群空间中，通过性能函数d 6 7 ( 1 来评价其中个体的适应值，并将其中的个体在进化过程中所形成的个体经验，通 过接受函数叩c 叫( ) 传递给信念空间，信念空间将收到的个体经验按一定的规 则进行比较优化，形成群体经验，并通过更新函数批( ) 不断更新现有的信 念空间，信念空间用更新后的群体经验，通过影响函数聊“p 掀( ) 修改群体空 1 0 东北大学硕士学位论文 第二章群智能计算方法 间中个体的行为规则，进而高效地指导群体空间的进化。 长一啪 、触删一 东北大学硕士学位论文第二章群智能计算方法 s a l e e m 和r e y n o l d s 定义了知识的五种基本类型：形势知识( s i 似i o n a l k n o w l e d g e ) ，标准化知识( n o 皿a t i v ek n o w l e d g e ) ，区域知识( d o m a i l lk n o w l e d g e ) ， 历史知识( h i s t o 巧k n o w l e d g e ) 和拓扑知识( t o p o g r 印l l i c 鼬l o w l e d g e ) 。标准化知识给 出了一系列期望变量的范围，用于为个体行为提供标准，指导个体进行调整。标 准化知识引导个体进入最优范围。形势知识提供了一系列的范例，有利于特定个 体经验的表示，引导个体以范例移动。区域知识使用有关问题区域的知识去指导 搜索，例如，在一个由圆锥构成的函数空间，关于圆锥的形状和参数的知识在搜 索的过程中将被用来确定向哪个方向移动。拓扑知识根据空间特点来将整个区域 分成“元，每个“元 跟踪它的范围内的最好的个体，拓扑知识使个体来仿效 最好的个体，类似于局部优化。历史知识用来监控搜索过程，记录搜索过程中的 重要事件( 例如个体在搜索空间内有意义的移动) ，引导个体选择搜索方向。 根据不同问题的特点，可以选择不同的知识类型，任何文化知识都能由以上 五种类型的几种联合表示。 2 3 4 文化算法算例 本文用文献【1 7 】中的文化粒子群算法来介绍文化算法的具体运用。 算例：引自文献【1 7 】和文献【1 8 】中给出的一个以人造卫星舱布局方案设计为 背景的二维布局问题，要求给出卫星舱布局的最佳方案。该问题简化为：在半径 为r = 7 5 m m 放置= 9 个圆形待布物，各待布物的圆心坐标、半径和质量分别 ( ，”) ，c 和，其中c = 3 0 m m ，= 2 ，3 ，4 ，5 ；= 3 0 ( 2 一1 ) m m ，f = 1 ，6 ，7 ，8 ，9 ， 设聊，取值与c 相等。要求待布物在圆容器内摆放时满足下述条件：( 1 ) 待布物之 间以及待布物与容器之间不发生干涉；( 2 ) 待布物尽量向圆容器的中心聚集，即 所有待布物的外包络圆的半径最小；( 3 ) 静不平衡量小于某一允许值万。具体数 学模型如下： 求置( f ，) ，使其满足： m i n f ( 置) = m a x 届可+ 以 ( 2 1 ) 其中约束条件如下： ( 1 ) 待布物之间的互不干涉条件： 1 2 东北大学硕士学位论文 第二章群智能计算方法 z ( x ，) ：+ 。一百：i i i 了r ：而o ，；， ( 2 ) 待布物与容器之间的不干涉条件： 石( 墨) = 厢+ 一尺o ( 3 )静不平衡条件： 六cx，：萎_：j：丽一l万i。 ( 2 2 ) ( 2 3 ) ( 2 4 ) 文化粒子群算法的构造如下口7 1 ： ( 1 ) 群体空间的设计 a 编码方案 群体空间采用的是粒子群算法。采用实数的编码方案，粒子群个体编码为 g l j ，l x 2 y 2 x | y ) 。 b 适应度函数 采用惩罚函数法确定粒子群个体的适应度函数，即约束条件作为惩罚项加入 适应度函数，并采用适当的惩罚系数，适应度函数表示为： 矽( 置，五) = e x p if ( 置) + 五。z ( 一) m ( z ) i ( 2