（计算机应用技术专业论文）基于免疫算法的粒子群优化算法的研究.pdf

摘要 粒子群优化算法( 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 算法) 源于鸟群和 鱼群群体运动行为的研究，是一种基于群体智能的进化计算技术，是进化计算 领域中的一个新的分支。作为一种新的并行优化算法，粒子群算法可用于解决 大量的非线性，不可微和多峰值的复杂问题优化，并己广泛应用于科学和工程 领域。粒子群优化算法的收敛速度快，运算简单，易于实现，没有遗传算法的 编解码和杂交变异等复杂运算。因此，粒子群算法一经提出，立即引起了进化 计算领域的学者们的广泛关注，并在短短的几年时间里出现大量的研究成果。 但是粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向“飞 行”，在进化后期收敛速度明显变慢，同时算法收敛到一定精度时，算法无法继 续优化，因此算法所能达到的精度较差。 本文系统地论述了p s o 算法及其各种研究成果，并且针对基本粒子群算法的 容易陷入局部极小值，搜索精度不高等缺点，在算法改进方面提出了与免疫算 法相结合的p s o 算法，利用免疫算法能够保持个体多样性的特点，使算法能够 跳出局部极值。并使用四个经典的测试函数对其进行了测试，试验结果表明， 这些改进取得了较好的效果。本文的重点在于对p s o 算法的改进，主要内容包 括： 1 抛弃传统的随机初始化粒子和粒子的速度方法，采用l o g i s t i c 映射生成初 始化粒子，以及粒子的初始速度； 2 将免疫算法中的基于浓度的选择机制引入到p s o 算法中，这样结合了p s o 算 法的全局寻优能力和免疫算法保持群体多样性的机制，使得p s o 算法具有了 摆脱局部极值点能力，提高算法进化过程中的收敛速度和精度： 3 引入信息熵的概念来衡量粒子浓度，这区别于以往的简单的定义粒子浓度的 方法，使粒子浓度的定义更加合理，更能体现出粒子浓度的真实性。 关键词粒子群优化算法进化计算免疫算法信息熵l o g is t i c 映射 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 l le 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 e d e v e l o p e db yd r e b e r h a r ta n dd r k e n n e d yi n19 9 5i n s p i r e db ys o c i a lb e h a v i o ro f b i r df l o c k i n go rf i s h s c h o o l i n g s i m i l a rt og e n e t i ca l g o r i t h m s ( g a ) ，p s oi s a p o p u l a t i o nb a s e do p t i m i z a t i o nt 0 0 1 t h es y s t e mi si n i t i a l i z e dw i t hap o p u l a t i o no f r a n d o ms o l u t i o n sa n ds e a r c h e sf o ro p t i m ab yu p d a t i n gg e n e r a t i o n s h o w e v e r ，m a l i k e g a ，p s oh a so ne v o l u t i o no p e r a t o r ss u c ha sc r o s s o v e ra n dm u t a t i o n i np s o ，t h e p o t e n t i a ls o l u t i o n s ，c a l l e dp a r t i c l e s ，a r e “f l o w n t h r o u g h t h ep r o b l e ms p a c eb y f o l l o w i n gt h ec u r r e n to p t i m u mp a r t i c l e s 1 a b a n d o nt r a d i t i o n a lm e t h o dw h i c hg e n e r a t ep a r t i c l e sa n dt h e i rv e l o c i t yb y r a n d o m ，a n du s i n gan e ww a y t oi n i t i a l i z ep a r t i c l e s ； 2 i n t r o d u c ed e n s e n e s sm e c h a n i s mi n t op s oa l g o r i t h m ，w h i c hi su s e di ni m m u n e a l g o r i t h m i nt h en e wa l g o r i t h m ，t h ea b i l i t yo fs e a r c h i n gt h eb e s ts o l u t i o ni nt h e g l o b a ls p a c ea n dt h em e c h a n i s mt ok e e pt h ev a r i e t yo f p a r t i c l e sa r ei n t e g r a t e d b y t h i sw a y , t h en e wc o m b i n a t i o n a lp s oa l g o r i t h mc a nj u m pf r o me a s i l ya n dt h e c o n v e r g e n tv e l o c i t ya n dp r e c i s i o nc a nb ei m p r o v e dg r e a t l yi nt h ep r o c e s so f e v a l u a t i o n ； 3 i n t r o d u c et h et h e o r ya b o u ti n f o r m a t i o ne n t r o p yt os c a l et h ed e n s e n e s so f p a r t i c l e s i t i sm u c hd i f f e r e n tf r o mt h et r a d i t i o n a lm e t h o dd e f i n i n gt h ed e n s e n e s so f p a r t i c l e s t h i sm e t h o di sm o r er e a s o n a b l e k e y w o r d sp a r t i c i es w ar mo p t i m i z a t i o n ，e v a iu a t i o na i g o r i t h m ，i m n l u n e a l g o r i t h m ，i n f o r m a t i o ne n t r o p y 1 0 9 is t i cf u n c t i o n i i 论文原创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上己属于他人的任何形式的研究成果，也不包含本人已用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损 害，进行公开道歉。 4 本人负责因论文成果不实产生的法律纠纷。 论文作者签名： ：毯焦日期：苎竺年三月曼l 日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人 离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单 位仍然为东北电力学院。 论文作者签名：交塞缘 导师签名：蒸亟盏 日期：蔓丝五年王月_ 日 日期：兰! ! ! 年三月三l 同 第1 章前言 第1 章前言 当前科学技术正进入多学科相互交叉、相互渗透、相互影响的时代，这一点 在计算机科学领域表现的尤其突出。一方面，计算机科学的迅猛发展，从根本 上改变了人类的生活、学习和工作的方式，使人类进入了一个崭新的时代：另一 方面，随着人类的生存空间的扩大和认识世界范围的拓宽，人们又对计算机科 学提出了新的要求与期望。而所有的期望之中，对计算机的计算速度和具有智 能的要求也许是最迫切和最基本的。 很多实际应用问题不仅涉及到大量的计算而且需要实时响应，这对计算机 的速度提出了强有力的挑战。在单机速度受到其物理极限的限制的情况下，解 决的根本途径就是并行化。而9 0 年代出现的人工智能技术，使人们看到了制造 具有智能的机器的梦想的希望，但随着人工智能应用领域的不断扩展，传统的 基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸 等方面所碰到的问题变得越来越突出。 科学家们在苦苦寻找一种适合大规模并行且具有智能特性如自组织、自适 应、自学习等算法同时，也同时把目光投向了大自然中的一些现象。 1 1 自然界中的群体现象 大自然是我们解决各种问题的源泉，几百年来，将生物界提供的答案应用于 实际问题求解已经被证实是一种成功的方法。并由此形成了一种专门的学科一 一仿生学( b i o n i c s ) 。 不妨先让我们来思考一下自然界存在的一些现象吧： 数以百万计的蚂蚁如何组成一个群落? 在蚁群中，单只蚂蚁的能力和智力 如此简单，不论工蚁还是蚁后都不可能有足够的能力来指挥完成筑巢、觅食、 迁徙、清扫蚁穴等复杂行为。那么，它们是如何相互协调、分工、合作来完成 这些任务昵? 像蚁巢这样复杂结构的信息又是如何存储在这群蚂蚁当中呢? 这些 奎j ：皇之盔兰至士兰堡兰兰 一直是困扰生物学家的问题。 我们经常能够看到成群的鸟、鱼或者浮游生物。这些生物的聚集行为有利 于它们觅食和逃避捕食者。它们的群落规模动辄以十、百、千甚至万计，并且 经常不存在一个统一的指挥者。它们是如何完成聚集、移动这些功能呢? 生态学 家对这个问题一直十分感兴趣。 您是否从上面的这些问题看出了什么? 其实，这些看似毫不相关的问题都具 有相同的特征，即相对简单的个体在没有一个集中控制的情况下，通过相互作 用产生复杂的群体行为，它们都属于复杂自适应系统研究的范围。 1 2 复杂自适应系统( o o m p i e xa d a p t i v es y s t e m ) 及其新型的建 模方法 复杂自适应系统是一类特殊的复杂系统，是近几年来系统科学与系统工程界 关注的热点之一，其理论的基本内容可以简要地归纳为以下一些要点： a c a s 理论从一般系统中区分出了复杂自适应系统。它认为这种由具有自 适应能力的主动个体( a c t i v ea g e n t ) 组成的系统，具有产生复杂结构、分化发 育等一系列特殊的性质和规律，从而不同于一般的系统。相对于此，以前我们 谈的系统观点，往往是把个体看作死的、被动的零件、部件。c a s 理论认为正是 这方面的局限，使以前的系统理论难以解释生命、种群、社会等活的复杂系统 的规律。 b 主动个体与环境之问不断地相互作用，个体根据一定的规则对环境的刺激 做出反应。这些规则以所谓“染色体”的方式存放在个体内部。它们在一定的 条件下被选中并且被应用，这种选择既有确定性的方面( 按一定的条件挑选) ， 也有随机性的方面( 按一定的概率选择) 。 c 这些规则不是固定不变的，每次应用的成功或失败将改变该规则的“适应 函数”( f i t n e s s ) ，这是一个标志该规则与客观环境相符程度的指标。每应用成 功一次，这个数值就增大：每应用失败一次，它就减小。 d 这种“刺激一反应一检查效果，修改适应度函数”的过程，多次反复进 行，符合环境的“染色体”不断增强，不符合环境的“染色体”则不断减弱， 到一定程度就消亡了。同时，“染色体”还会按一定的规则产生新的“染色体护”。 2 一 第1 章前言 e 对每个主动个体而吉，它的环境不仅包括周围的基础条件( 如温度、压力、 营养、资源等) ，还包括其他主动个体。主动个体之间的相互作用同样遵循着刺 激一反应模式，并从而发展出吸引、排斥、资源交换、复制、结合等复杂的相 互关系，进而产生分工、分化，直到形成更高一层的主动个体，并导致整个系 统结构的突变。 各个领域的专家已经对这些问题有了长期、深入的研究，提出了一些解释 并建立了一些模型。 例如，1 9 8 6 年c r a i gr e y n o l d s 提出了g o i d ( b i t d o i d ) 模型用以模拟鸟类 聚集飞行的行为。在这个模型中，每个个体的行为只和它周围邻近个体的行为 有关，每个个体只需遵循以下3 条规则： 避免碰撞( c o l l i s i o na v o i d a n c e ) ：避免和邻近的个体相碰撞。 速度一致( v e l o c i t ym a t c h i n g ) ：和邻近的个体的平均速度保持一致。 向中心聚集( f l o c kc e n t e r i n g ) ：向邻近个体的平均位置移动。 鸟群中的每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但 是随着时间的推移，这些初始处于随机状态的鸟通过自组织逐步聚集成一个个 小的群落，并且以相同速度朝着相同方向飞行，然后几个小的群落又聚集成大 的群落，大的群落可能又分散为一个个小的群落。这些行为和现实中的鸟类飞 行的特性是一致的。 我们可以看出鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的 局部感知上面，而且并不存在一个集中的控制者。也就是说整个群体组织起来 但却没有一个组织者，群体之间相互协调却没有一个协调者，这和前面我们对 这些系统的整体感觉是一致的。 因此，在对g a s 系统进行数学建模的时候，可以利用计算机的方法，通过 对个体行为准则的模拟、仿真，让一群这样的个体在计算机所营造的虚拟环境 下进行相互作用并演化，从而让整体系统的复杂性行为自下而上的“涌现”出 来。这种建模方式被称作基于主体的仿真，与传统的基于复杂方程的建模方式 有着很大的不同。 1 3 进化计算( e v o iu t i o n a r yc o m p u t a t i o n ) 自从电子计算机出现以来，生物模拟便构成了计算机科学的个组成部分。 其目的一是试图建立一种人工模拟的环境，以便使用计算机进行仿真以更好的 了解人类自己和人类的生存空间：另一个目的则是从研究生物系统出发，探索产 生基本认知行为的微观机理，然后设计成具有生物智能的机器或系统以解决复 杂问题。 自然界的进化是经过漫长的自适应过程进化过程而获得结果的，进化 计算正是基于这种思想而发展起来的一种通用的问题求解方法。它可以在不用 描述问题的全部特征的情况下，采用简单的编码技术来表示各种复杂的结构， 并通过对一组编码表示简单的遗传操作和优胜劣汰的自然选择来指导学习和确 定搜索方向。由于它采用种群的方式组织搜索，这使得它可以同时搜索空间内 的多个区域。而且用种群组织搜索的方式使得进化算法特别适合大规模的并行。 在赋予进化计算组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和 简单的遗传操作使得进化计算具有不受搜索空间限制性条件( 如可微、连续、单 峰等) 的约束及不需要其它辅助信息( 如导数) 的特点。这种崭新的特点使得进化 计算不仅能获得较高的效率而且具有简单、易于操作和通用的特性，而这些特 性正是进化计算越来越受到人们青睐的主要原因之一。 进化计算具有四大分支：遗传算法，进化规划，进化策略以及遗传程序设计， 下面我们将逐一做简单介绍。 1 3 1 遗传算法( g e n e t ica i g o ri t h m ，6 a ) 自然界的生物体在遗传、选择和变异的作用下，优胜劣汰，不断地由低级向 高级进化和发展，人们注意到这种适者生存的进化规律的实质可加以形式化而 构成一种优化算法。最早意识到自然遗传规律可以转化为人工遗传算法的是 h 0 1l a n d 教授，遗传算法采用简单的编码技术和繁殖机制来表现复杂的现象，从 而解决非常困难的问题。 从数学角度看，遗传算法是一种随机搜索算法。从工程角度看，它是一种 一4 第1 章前言 自适应的迭代寻优过程。它从某一随机产生的初始群体开始，按照一定的操作 规则，如选择、复制、交叉、变异等等，不断地迭代计算，并根据每一个个体 的适应度值，保留优良个体，淘汰劣质个体，引导搜索过程向最优解逼近。与 传统的优化方法相比，遗传算法具有以下特点： 1 ) 遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码。 2 ) 遗传算法不是从单个点，而是从一个群体开始搜索。 3 ) 遗传算法直接对结构对象进行操作，不存在求导和函数连续性的限定。 4 ) 遗传算法具有内在的隐并行性和较好的全局寻优能力。 5 ) 遗传算法采用概率转移规则，不需要确定性的规则。 这些特点使得遗传算法在诸如工业规划设计、图像及信号处理、药物分子 设计、过程建模等等领域得到越来越多的关注。 h o l l a n d 的遗传算法常被称为简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ， s g a ) ，s g a 的操作对象是一群二进制串( 称为染色体、个体) ，即种群。使用选 择算子、交叉算子和变异算子这三种基本遗传操作，它们的遗传操作实施简单， 是其他遗传算法的基础，给各种遗传算法提供了一个基本的框架。 构成简单遗传算法的要素主要有：染色体编码、个体适应度评价、遗传算子 以及遗传参数设置等等。 1 ) 染色体编码方法 在对一个问题采用遗传算法进行求解之前，必须对问题的解空间进行编码， 以便能够由遗传算法操作。常见的编码方法是二进制编码，使用固定长度的二 进制符号串来表示群体中的个体。求解结束后再通过解码变换成实变量。在编 码和解码的过程中，参变量的精度不可避免会受到影响。因此，有人提出了基 于实数编码的遗传算法，其基本原理与二进制编码相同，只是实数编码的染色 体是由各个实参变量构成的向量，初始群体中的各个个体的基因可用均匀分布 的随机数来构成。 2 ) 适应度函数 在遗传算法中，遗传操作主要通过适应度函数( f i t n e s sf u n c t i o n ) 的导向来 实现的。它是用来评估一个染色体相对于整个群体的优劣的相对值的大小。 东北电力大学硕士学位论文 3 ) 遗传算子 基本遗传算法通常使用下述三种遗传算子： 选择算子：按照某种策略从父代中挑选个体进入中间代。 交叉算子：随机地从中间群体中取得两个个体，并按照某种交叉策略使两个 个体互相交换部分染色体码串，从而形成两个新的个体。 变异算子：通常按照一定的概率，改变染色体中的某些基因的值。 4 ) 遗传算法的运行参数 有以下四个运行参数需要提前设定：群体大小( n ) ，即群体中所含个体数量： 终止迭代代数( t ) ：交叉概率( p 。) ：变异概率( p 。) 。这四个参数对遗传算法的求解 结果和求解效率都有很大的影响。因此，要合理设定这些参数，才能获得较好 的效果。 1 3 2 进化策略( e v o iu t i o n a r ys t r a t e g i e s ，e s ) 早期进化策略的种群中只包含一个个体，而且只是使用变异操作。在每一进 化代，变异后的个体与其父体进行再选择两者之优。这一策略目前称为( 1 + 1 ) 策 略。它使用的变异算子是基于正态分布的变异操作，这种进化策略称为( 1 + 1 ) 进 化策略或二元进化策略。 进化策略主要用于求解数值优化问题。近年来，遗传算法也采用十进制编码 ( 或称浮点数编码) 技术来求解数值优化问题。e s 和g a 的相互渗透已使得它们没 有很明显的界限。 1 3 3 进化规划( e v o iu t i o n a r yp r o g r a m m in g ，e p ) 进化规划的方法最初是由l j f o g e l 等在2 0 世纪6 0 年代提出的。他们在 人工智能行为即是要具有能预测其所处的环境的状态下，并按照给定的目标做 出适当响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中的符 号组成的序列。于是问题便转化成：怎样根据当前观察到的符号序列做出响应以 获得最大的受益，这里受益的计算是按照环境中将要出现的下一个符号及预先 定义好的效益目标来确定。进化规划中的常用有限状态机( f i n i t es t a t e m a c h i n e ，f s m ) 来表示这样的策略。 那么，如何设计一个有效的f s m ? 其中l j f o g e l 等借用进化的思想对一群 f s m 进行进化以获得较好的f s m 。他们将此方法应用到数据诊断、模式识别和分 类以及控制系统的设计等问题中，并取得了较好的效果。 1 3 4 遗传程序设计( 6 e n e t icp r o g r a m m in g ，g p ) 自计算机出现以来，计算机可以以科学的一个重要目标即是让计算机自动进 行程序设计，即：只要明确的告诉计算机要解决的问题，而不需要告诉它如何 去做，遗传程序设计便是在该领域的一种尝试。它采用遗传算法的基本思想， 但使用一种更为灵活的表示方式一分层结构来表示解空问。这些分层结构的叶 结点就是问题的原始变量，中间结点则是组合这些原始变量的函数。他们很类 似l i s p 语言中的s 表达式。这样的每一个分层结构对应问题的一个解，也可以 理解为求解该问题的一个计算机程序。遗传程序设计即是使用一些遗传操作动 态的改变这些结构以获得该问题的可行的计算机程序。遗传程序设计的思想是 s t a n f o r d 大学的j r k o z a 在2 0 世纪9 0 年代初提出的。 1 3 5 进化计算的主要特点 进化算法与传统的算法有很多不同之处，但最主要的差别在于进化计算具有 智能性和本质并行性的特征。 进化计算的智能性包括自组织、白适应和自学习等。应用进化计算求解问题 时，在确定了编码方案、适应度函数及遗传算子之后，算法将利用进化过程中 获得的信息自行组织搜索。由于基于自然的选择策略为适者生存、不适者淘汰， 故而适应度值大的个体具有较高的生存概率。通常适应度值大的个体具有更适 应环境的基因结构，再通过杂交和基因突变等遗传操作就可能产生更适应环境 的后代。进化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境 的变化自动发现环境的特性和规律的能力。此外，自然选择消除了算法设计过 东北电力大学硕士学位论文 程中的一个最大障碍，即需要事先描述问题的全部特点，并说明针对问题的不 同特点算法应采取的措施。于是，利用进化计算的方法我们可以解决那些结构 尚无人理解的复杂问题。 进化计算的本质并行性表现在两个方面：一是进化计算是内在并行的，即进 化算法本身非常适合大规模并行。最简单的并行方式是让几百甚至数千台计算 机各自进行独立种群的进化计算，运行过程中甚至不进行任何通信，直到运算 结束时才通信比较，选取最佳个体，这种并行处理方式对并行系统结构也没有 什么限制和要求。可以说，进化计算适合在目前所有的并行机或分布式系统上 进行并行处理，而且对其并行效率没有太大的影响。二是进化计算的内含并行 性，由于进化计算采用种群的方式组织搜索，从而可以同时搜索解空间的多个 区域，并相互交流信息。虽然每次只执行与种群规模n 成比例的计算，而实质 上已进行了大约o ( n 3 ) 次有效搜索，使进化计算能以较少的计算获得较大的收 益。 1 4 群体智能( s w a r m in t e li j g e n c e ，s i ) 的研究 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了 系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能 ( s w a r mi n t e l i g e n c e ) 中的群体( s w a r m ) 指的是“一组相互之间可以进行直接通 信或者间接通信( 通过改变局部环境) 的主体，这组主体能够合作进行分布问题 求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特 性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分 布式问题的解决方案提供了基础。蚁群算法和粒子群算法是其中两类具有代表 型的优化算法。 1 4 1 蚁群算法( a n ta i g o r i t h i no p t i m iz a t i o n ，a o o ) 根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索 的模型，蚁群算法对搜索空间的“了解”是从观察蚁群觅食活动从中启发而建 立的机制，主要包括三个方面： 第l 章前言 ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会被选择，由此 在蚁群算法中建立t a b o o ( 禁忌) 列表柬进行模拟： ( 2 ) 蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信。蚂蚁在所选择的路径上会 释放一种叫做信息素的物质，当同伴进行路径选择时，会根据路径上的信息素 进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介。 ( 3 ) 蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进 行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信 息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加， 从而进一步增加该路径的信息素强度，而某些路径上通过的蚂蚁较少时，路径 上的信息素就会随时间的推移而蒸发。因此，模拟这种现象从而利用群体智能 建立的路径选择机制，使蚁群算法的搜索向最优解推进。 1 4 2 粒子群算法( p a r t i c i es w a r mo p t i m iz a t io n ，p s o ) p s o 算法最早是由e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出的“1 ，它的基本概 念源于对人工生命( i r t i f i c i a ll i f e ) 和鸟群捕食行为的研究。设想这样一个 场景： 一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道 食物在哪罩，但是它们知道当前的位置离食物还有多远。那么找到食物的最优 策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 p s o 算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在 p s o 中，每个优化问题的潜在解都可以想象成d 维搜索空问上的一个点，我们称 之为“粒子”( p a r t i c l e ) ，所有的粒子都有一个被目标函数决定的适应度值 ( f i t n e s sv a l u e ) ，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒 子们就追随当前的最优粒子在解空间中搜索。详细的步骤将在以后的章节介绍。 可见，粒子群优化算法也是基于个体的协作与竞争来完成复杂搜索空间中 最优解的搜索，是一种基于群智能方法的进化计算技术。p s o 同遗传算法类似， 是一种基于群体的优化工具。但p s o 并没有遗传算法用的交叉( c r o s s o v e r ) 、变 异( m u t a t i o n ) 等操作，而是粒子在解空间追随最优的粒子进行搜索，因此具有 东北电力大学硕士学位论文 简单容易实现并且没有许多参数需要调整的优点。 p s o 的提出至今不到十年，但是它已经得到了广泛关注。在基本p s o 算法的 基础上，已经出现了各种有意义的改进p s o 算法，例如自适应p s o 算法、协同 p s o 算法、混合p s o 算法等等，这可以在以后的章节中看到一些较详细的介绍。 p s o 算法非常适合于求解连续函数的优化问题，主要应用于神经网络训练。“， 多目标优化。”等应用领域：也有将p s o 用于解决一些离散型优化问题的相关研 究，例如用于求解t s p 问题”“4 ”，任务分配问题等组合优化问题。但是，p s o 在国内研究却刚刚起步，可以见得到文献并不多，文献。“3 等也算是国内对 p s o 算法的一些综述性文章或应用。 1 4 3 群智能的特点 1 群体中相互合作的个体是分布的( d i s t r i b u t e d ) ，这样更能够适应当前网 络环境下的工作状态： 2 没有中心的控制与数据，这样的系统更具有鲁棒性( r o b u s t ) ，不会由于 某一个或者某几个个体的故障而影响整个问题的求解： 3 可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系 统具有更好的可扩充性( s c a l a b i l i t y ) 。由于系统中个体的增加而增加的系统的 通信开销在这里是十分小： 4 系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并 且实现也比较简单，具有简单性( s i m p l i c i t y ) 。 因为具有这些优点，虽说群智能的研究还处于初级阶段，并且存在许多困 难，但是可以预言群智能的研究代表了以后计算机研究发展的一个重要方向。 第2 章粒子群算法 第2 章粒子群算法 2 1 引言 从2 0 世纪9 0 年代初，就产生了模拟自然生物群体( s w a r m ) 行为的优化技 术。d o r i g o 等从生物进化的机理中受到启发，通过模拟蚂蚁的寻径行为，提出 了蚁群优化方法：e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出的粒子群优化算法是基 于对鸟群、鱼群的模拟。这些研究可以称为群体智能( s w a r mi n t e l l i g e n c e ) 。 通常单个自然生物并不是智能的，但是整个生物群体却表现出处理复杂问题的 能力，群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化( p s o ) 最初是处理连续优化问题的，目前其应用已扩展到组合优化问题。由于其简单、 有效的特点，p s o 已经得到了众多学者的重视和研究。 2 。2p s o 基本原理 2 2 1 基本p s o 原理 粒子群优化算法是基于群体的进化算法，其思想来源于人工生命和进化计 算理论。r e y n o l d s 对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居， 但最终的整体结果是整个乌群好像在一个中心的控制之下，即复杂的全局行为 是由简单规则的相互作用引起的。p s o 即源于对鸟群捕食行为的研究，一群鸟 在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效 的策略就是搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从这种模型中 得到启示而产生的，并用于解决优化问题。另外，人们通常是以他们自己及他 人的经验来作为决策的依据，这就构成了p s o 的一个基本概念。 p s o 求解优化问题时，问题的解对应于搜索空间中一只鸟的位置，称这些 鸟为“粒子”( p a r t i c l e ) 或“主体”( a g e n t ) 。每个粒子都有自己的位置和速 度( 决定飞行的方向和距离) ，还有一个由被优化函数决定的适应度值。各个粒 子记忆、追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随 机的，如果找到较好解，将会以此为依据来寻找下一个解。令p s o 初始化为一 群随机粒子( 随机解) ，在每一次迭代中、粒子通过跟踪两个“极值”来更新自 己：第一个就是粒子本身所找到的最好解，叫做个体极值点( 用p b e s t 表示其位 置) ，全局版p s o 中的另一个极值点是整个种群目前找到的最好解称为全局极值 点( 用g b e s t 表示其位置) ，而局部版p s o 不用整个种群而是用其中一部分作为 粒子的邻居，所有邻居中的最好解就是局部极值点( 用i b e s t 表示其位置) 。在 找到这两个最好解后，粒子根据如下的式( 1 ) 和式( 2 ) 来更新自己的速度和位 管。粒子j 的信息可以用口维向量表示，位置表示为j 。= x 儿，一，x ，d ) 1 ，速 度为= v “，v ：，。v 。r ，其他向量类似。则速度和位置更新方程为： v 等1 = v 0 + c l ，d n d ? b 6 e 甜品一x 暑) 4 - c 2 ，d d ：k 、一e 耐k x 埘k ) ( 2 1 ) x 1 = x 当+ v 1 ( 2 2 ) v ：是粒子j 在第膏次迭代中第d 维的速度；c 1 ，也是加速系数( 或称学习 因子) ，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长，若太 小，则粒子可能远离目标区域，若太大则会导致突然向目标区域飞去，或飞过 目标区域。合适的c l ，c 2 可以加快收敛且不易陷入局部最优，通常令c l = c 2 = 2 ：r a n d 是厂o ，l _ ，之间的随机数：x ：是粒子j 在第七次迭代中第d 维 的当前位置；p b e s t 。是粒子j 在第d 维的个体极值点的位置( 即坐标) ；g b e s t 。， 是整个群在第d 维的全局极值点的位置。为防止粒子远离搜索空间，粒子的每 一维速度v 。都会被钳位在卜v 。，+ v 。】之间，v 。太大，粒子将飞离最好 解，太小将会陷入局部最优。假设将搜索空间的第d 维定义为区间 【j 一，+ b j ，则通常屹。= h 。一，0 1 膏o 5 ，每一维都用相同的 设置方法。基本p s o 的流程可以描述为： s t e p1 初始化初始搜索点的位置盖? 及其速度口通常是在允许的范围内 随机产生的，每个粒子的p b e s t 坐标设置为其当前位置，且计算出其相应的个 体极值( 即个体极值点的适应度值) ，而全局极值( 即全局极值点的适应度值) 就是个体极值中最好的，记录该最好值的粒子序号，并将g b e s t 设置为该最好 粒子的当前位置。 s t e p2 评价每一个粒子计算粒子的适应度值，如果好于该粒子当前的个 第2 章粒子群算法 体极值，则将p b e s t 设置为该粒子的位置，且更新个体极值。如果所有粒子的个 体极值中最好的好于当前的全局极值，则将g b e s t 设置为该粒子的位置，记录 该粒子的序号，且更新全局极值。 s t e p3 粒子的更新用式( 2 - 1 ) 和式( 2 2 ) 对每一个粒子的速度和位置进 行更新。 s t e p4 检验是否符合结束条件如果当前的迭代次数达到了预先设定的最 大次数( 或达到最小误差要求) ，则停止迭代，输出最优解，否则转到s t e p2 。 p s o 的一些特点： 1 ) 基本p s o 算法最初是处理连续优化问题的。 2 ) 类似于遗传算法( g a ) p s o 也是多点搜索。 3 ) 式( 1 ) 的第一项对应多样化( d i v e r s i f i c a t i o n ) 的特点，第二项、第三 项对应于搜索过程的集中化( i n t e n s i f i c a t i o n ) 特点，因此这个方法在多样化 和集中化之间建立均衡“3 。 p s o 有全局版和局部版两种，全局版收敛快，但有时会陷入局部最优。局 部版p s o 通过保持多个吸引子来避免早熟，假设每一个粒子在大小，的邻域内 定义为一个集合 n ，= 切b e s t h ，p b e s t h + l ，p b e s t h ，p b e s t ，p b e s t m ，p b e s t m p b e s t ( 2 3 ) 从，中选出最好的，将其位置作为i b e s t 代替公式中的g b e s t ，其他与全 局版p s o 相同。实验表明，局部版比全局版收敛慢，但不容易陷入局部最优。1 。 在实际应用中，可以先用全局p s o 找到大致的结果，再用局部p s o 进行搜索。 2 2 2 二进制p s o 最初的p s o 是从解决连续优化问题发展起来的，e b e r h a r t 等又提出t p s o 的离散二进制版，用来解决工程实际中的组合优化问题”。他们在提出的模型中 将每一维勘和p b e s t 限制为1 或者为o ，而速度v “不作这种限制。用速度来 更新位置时，如果v 。高一些，粒子的位置更有可能选1 ，v 。低一点则选0 ， 阈值在 0 ，1 之间，而有这种特点的函数就是s i g n o i d 函数： s i g ) = 1 ( 1 + e x p ( - v 盘) ) 二进制版本p s o 的公式为 i f 甜1 r e n t , 以) ( 2 1 1 ) c 嗽) = 厮p a r e 葡n t l ( v 两, ) + 确p a r e n t 2 ( v , ) ，i p a r e n t 2 以】 ( 2 1 2 ) 的代数杂交操作，产生子代的粒子取代父代。选择父代没有基于适应度值，防 止了基于适应度值的选择对那些多局部极值的函数带来潜在问题“。p ，是( 0 ， 1 ) 间的随机数。理论上讲繁殖法可以更好地搜索粒子间的空间，2 个在不同次 优峰处的粒子经繁殖后，可以从局部最优逃离。结果显示，对单峰函数，繁殖 法虽略加快了收敛速度，却不如基本p s o 和g a 找到的解好，而对于多局部极 值的函数，繁殖p s o 不仅加快了收敛速度，而且找到了同样好或更好的解。 第2 章粒子群算法 2 。3 。2 增加多样性的改进 1 空间邻域( s p a t i a ln e i g h b o r h o o d s ) 法 基本的局部搜索版p s o 中粒子的邻域是基于粒子序号划分的。s u g a n t h a n 提出了基于粒子的空间位置划分的方案”1 。在迭代中，计算每一个粒子与群中 其他粒予的距离，记录任何两个粒子阃的最大距离为d 。a 对每一粒子按照 阻一瓦一 ( 2 1 3 ) 计算一个比值，其中1 i x 。一x 。0 是当前粒子a 到粒子b 的距离。而选择阈值f r a c 根据迭代次数而变化。当另一粒子6 满足f l 工。一f f d 。 ( 4 3 ) 对于一维连续型随机变量x ，若它的概率密度分布函数为f ( 互) ，则x 在区 间( a ，6 ) 的信息熵为： 第4 章基于免疫算法的粒子群优化算法 2 - 1 ( z = 一以摊州弧 ( 4 4 ) 信息熵的概念建立，为测试信息的多少找到了一个统一的科学的定量计量方 法，奠定了信息论的基础。 4 2 2 基于信息熵的浓度 假设有n 个抗体，每个抗体的编码长度为l ，那么抗体基因位置j 的信息熵： 日，( ) = 一f ，o ) h a f ( x ) d x ( 4 5 ) 这里f ( x ) 为x 的概率密度分布函数，因此平均熵h ( n ) ： 日( ) = q ( ) ( 4 6 ) 根据熵的概念，两个抗体之间亲和力u 和v 可定义为： 4 广而历( 4 - 7 ) a i , ，( o ，1 ) 的值越大，抗体u 和v 之间的亲和度和相似度就越大。如果a 。= l ， 那么u 和v 的基因编码是相同的，所以抗体i 的浓度可定义为： c ，一一堡垒型盟( 4 - 8 ) t h et o m ln u m b e r o fa n t i b o d i e s 这里c o u n t ( i ) 是：所有和抗体i 亲和度大于某一值的抗体总数，所以抗体浓度 e 是群体中相似抗体的百分数。 在计算每一个抗体的浓度后，抗体的促进和抑制调节可以通过选择机制实 现。个体的选择概率p ，由两方面组成：适应度概率p ，和浓度概率p a ，所以： ：，：旦一1一魁(4-9)pp p a x e j2 ，。可。2 一一一 。 芝月f ( ，) 口 2 = 1 这里口和卢是两个正的调节因素常数，为了方便，这罩使用1 。f i t ( i ) 为抗 体i 的适应值。 由等式( 4 9 ) 可以看出，与抗体i 相似的抗体越多，抗体i 被选中的概率就 东北电力大学硕上学位论文 越小。反之，与抗体i 相似的抗体越少，抗体i 被选中的概率就越大。这使得低 适应度个体也可获得进化的机会。因此，基于抗体浓度的概率选择公式在理论 上保证了抗体的多样性。 4 2 3 混沌和虫口方程( 1 0 9 is t ic 映射) 混沌是存在于非线性系统中的一种较为普遍的现象。混沌并不是一片混乱， 而是有着精致内在结构的一类现象。混沌运动具有遍历性、随机性等特点，混 沌运动能在一定范围内按照其自身的规律不重复地遍历所有状态。因此，如果 利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。 描述生态学上的虫口模型l o g i s t i c 映射自m a y 于1 9 7 6 年开始研究以来，受到 了非线性科学家的高度关注，l o g i s t i c 映射是混沌理论发展史上不可多得的典 范性的混沌模型。它只是一令简单的一维映射，却具有拥有所有混沌模型所拥 有的特征和性质。 在生态学中，研究动植物群体与环境之间的相互作用非常重要。出于自然界 中孤立的单一群体几乎不存在，所以群体数目的多少取决于食物来源、竞争者、 捕食者等因素。在所建立的各种模型中，最为典型的就是如下的l o g i s t i c 模型： x = 。( 1 一x 。) ( 4 1 0 ) 式中为控制参数，且0 兰1 ，x 【o ，1 】。l o g i s t i c 模型描述了生物群体 数目随世代的变化。若n 代表进化代数，则可用x 。代表第r l 代的出生数，x 。代 表第n + l 代的出生数。由上式可见，其右边第一项表示第n + l 代的群体数x 。和第 n 代的群体数x 。成正比，第二项则反映环境限制因素引起的非线性项，即群体与 环境的相互作用导致x 。存活率的降低