（系统工程专业论文）菌群算法的研究及改进.pdf

一种新型群智能算法。它是一种简单有效的随机全局优化技术。但是，基本b f o 算法也存在精度不够高、收敛速度不够快的缺点。本文中，为了解决上述问题， 对基本菌群算法的4 个行为进行了重新定义，并将新的概念引入到算法中，提出 了一种改进的菌群优化算法( a b f o ) 。最后，本文将改进后的菌群优化算法应用 到热工过程辨识以及p i d 参数辨识当中，仿真结果充分表明了改进算法的可行 性和有效性。 关键词：菌群算法，a b f o ，热工过程辨识，群智能 a b s t r a c t b a c t e r i a lf o r a g i n go p t i m i z a t i o n ( b f o ) i sar e c e n t l y d e v e l o p e ds w a r m i n t e l l i g e n c ea l g o r i t h mb a s e do nt h ef o r a g i n gb e h a v i o ro fe c o l ib a c t e r i a i ti sa s i m p l es t o c h a s t i cg l o b a lo p t i m i z a t i o nt e c h n i q u e h o w e v e r , t h ea c c u r a c yo ft h e o r i g i n a lb f oa l g o r i t h mi sn o th i g h ；t h ec o n v e r g e n c er a t ei sn of a s te n o u g h t o r e s o l v et h e s ep r o b l e m s ，f o u rb a s i cb e h a v i o r so ft h eb f 0 a l g o r i t h mb e h a v i o rh a s b e e nr e d e f i n e da n di m p r o v e d ，a n dn e wc o n c e p t sw a si n t r o d u c e dt oi m p r o v et h e p r o c e s so ft h ee n t i r ea l g o r i t h m t h ei m p r o v e db f 0a l g o r i t h mi sc a l l e da d v a n c e d b f oa l g o r i t h m ( a b f o ) s u b s e q u e n t l y , t h i sa b f oa l g o r i t h mi s a p p l i e di nt h e a c t u a lt h e r m a l0 b i e c ti d e n t i f i c a t i o na n dt h eo p t i m i z a t i o no ft h ep i dc o n t r o l l e r p a r a m e t e r s t h ei d e n t i f i c a t i o nr e s u l t ss h o wt h a tt h en a t u r eo ft h ei m p r o v e d a l g o r i t h m i se f f e c t i v e t h es i m u l a t i o nr e s u l t ss h o wt h a tt h i s o p t i m i z a t i o n a l g o r i t h mi sv a l i da n de f f e c t i v e f a nf e i z h i ( s y s t e me n g i n e e r i n g ) d i r e c t e db yp r o f l u oy i k e yw o r d s ：b f o ，a b f o ，t h e r m a lo b j e c ti d e n t i f i c a t i o n ，s w a r mi n t e l l i g e n c e 华北电力人学硕十学位论文 目录 摘要“。i a b s t r a c t i 第一章引言l 1 1 选题背景及意义l 1 1 1 概述1 1 1 2 选题背景1 1 1 3 研究意义4 1 2 国内外研究动态5 1 3 论文的主要工作内容6 第二章基本菌群算法及其特点8 2 1 菌群算法的基本原理8 2 1 1 趋药性行为( c h e m o t a xis ) 8 2 1 2 聚集行为( s w a r m in g ) l o 2 1 3 繁殖行为( r e p r o d u c t io n ) 1 l 2 1 4 迁徙行为( e l ir n i n a t i 0 1 3a n dd is p e r s a i ) 1 1 2 2 对聚集行为的分析1 2 2 3 小结15 第三章变步长的菌群算法j 1 6 3 i 菌群算法的改进思路1 6 3 1 1 对趋药性行为的改进1 6 3 1 2 对繁殖行为的改进1 7 3 2 仿真算例l8 3 3 小结2 0 第四章改进的菌群算法a b f o 2 1 4 1 算法相关符号2 2 4 2 细菌的作用力范围2 2 4 3 趋药性行为的改进2 4 4 4 聚集行为的改进2 7 4 4 1 聚集行为1 ：2 7 4 4 2 聚集行为2 ：2 9 4 5 繁殖行为的改进3 0 4 6 变异行为3 l 4 7 仿真算例3 3 4 8 ，j 、结3 5 第五章基于a b f o 算法的系统辨识3 6 5 1 系统辨识的基本原理3 6 5 2 热工对象的辨识方法3 7 5 2 1 过程辨识原理3 8 l i 华北电力人学硕十学位论文 5 2 2 电厂热工过程研究对象3 9 5 3 基于a b f o 算法的热工对象辨识4 0 5 3 1 给定模毽的辨识4 0 5 3 2 利用实验数据的辨识4 3 5 4 ，j 、结4 7 第六章基于a b f o 算法的控制器参数优化设计4 8 6 1 控制系统数字仿真方法4 8 6 1 1 目标函数选取4 8 6 1 2 理想数字pid 控制算法5 0 6 1 3 控制对象的离散方法5 l 6 1 4 一阶惯性环节的仿真5 1 6 2 基于a b f o 算法的单网路p 1 d 控制器参数整定5 2 6 2 1单网路p i d 仿真算例5 2 6 2 2a b f 0 算法仿真结果5 3 6 3 基于a b f o 算法的串级p i d 控制器参数整定5 5 6 3 1 串级pid 仿真算例5 5 6 ，3 2 串级p i d 法仿真结果一5 6 6 4 本章小结5 8 第七章总结与展望5 9 7 1 论文总结5 9 7 2 研究展望6 0 参考文献6 l 致谢6 5 在学期间发表的学术论文和参加科研情况6 6 u i 华北电力人学硕十学位论文 1 1 选题背景及意义 1 1 1 概述 第一章引言 2 0 世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发， 提出了许多用以解决复杂优化问题的新方法，如遗传算法、蚁群算法、粒子 群算法、进化规划、进化策略等。群智能算法作为一种新兴的演化计算技术 已成为越来越多研究者的关注焦点，它与人工生命，特别是进化策略以及遗 传算法有着极为特殊的联系。群智能中的群体指的是“一组相互之间可以进 行直接通信或者阳】接通信( 通过改变局部环境) 的主体( a g e n t ) ，这组主体 能够合作进行分布式的问题求解”，而群智能则是指“无智能的主体通过合 作表现出智能行为的特性 。群智能在没有集中控制且不提供全局模型的前 提下，为寻找复杂的分布式问题求解方案提供了基础。自然界生物系统通过 自身无意识的寻优行为来进化其生存状态，群智能算法是基于该思想的一类 新型的最优化方法。 与各种各样的自适应随机搜索算法相比，演化计算技术创造了被称为“种 群 的潜在解，并通过种群间个体的相互协作与竞争来实现对优化问题最优解 的搜索。这类方法一般能够比传统优化方法更快地发现复杂优化问题的最优 解。群智能算法( s w a r mi n t e l l i g e n c e a l g o r i t h m ，s i a ) 是人工智能的一个重要 分支，起源于对人工生命的研究，它作为一种新兴的演化计算方法已越来越受 到国内外研究者的关注。 菌群优化算法( b a c t e r i a lf o r a g i n go p t i m i z a t i o na l g o r i t h m s ) 是于2 0 0 2 年由 k e v i nm p a s s i n o 教授提出来的一种新型的群智能算法，是继模拟退火算法、 遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法后的又一种 新型启发式搜索算法。b f o 算法通过群体中各个细菌间的合作与竞争而产生 的群体智能指导优化搜索，算法本身具备分布并行的寻优能力、对初值不敏 感、较好的全局搜索能力的特点。近些年来，菌群优化算法开始逐渐引起国 内外专家学者的关注，并对此算法的理论及应用开展了相应的研究。 1 1 2 选题背景 ( 1 ) 群智能的发展现状 作为一种最著名的进化算法，遗传算法( g a ，g e n e t i ca l g o r i t h m s ) 的 华北电力人学硕十学位论文 应用十分广泛，但其传统的二进制编码使得其在高维、高精确度优化问题上 的应用具有一定的局限。传统的遗传算法虽然在理论上已经形成了一套较为 完善的算法体系并在许多优化问题中都有成功的应用，它的如下优点决定了 该算法能够成为优化问题的一种新型方法：对参数的编码进行操作，而非对 参数本身；从许多点开始并行操作，而非局限于一点，更适合大规模复杂问 题的优化；通过目标函数来计算适配值，而不需要其他推导，从而对问题的 依赖性较小：其寻优规则是由概率决定的，而非确定性的；在解空间进行高 效启发式搜索，而非盲目地穷举或完全随机搜索。其缺点在于对于一些多维、 高精度要求的连续函数的优化，二进制编码存在着连续函数离散化时的映射 误差，个体编码串较短时，可能达不到精度要求，因此现在常采用十进制编 码方法。 粒子群优化算法【2 】【3 】( 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 ) 是一种基于群 智能的优化方法，是由美国社会心理学家j a m e sk e n n e d y 和电气工程t ) i t i r u s s e l l e b e r h a r t 根据对鸟群觅食行为研究成果于1 9 9 5 年提出的一种优化算法。同遗 传算法类似，它也是一种基于群体迭代的优化算法，系统由一群粒子组成， 粒子群在问题空间中进行协同搜索，它没有遗传算法的交叉、变异等操作。 它更强调群体内部个体之间的协同与合作，而不是g a 所体现的达尔文“适者 生存”理论。因为其具有快速性和易于实现等特点，目前成为了计算智能领 域的新研究热点，其理论研究工作还处于起步阶段。p s o 算法最大的优点在 于：易于描述，易于理解；对优化问题定义的连续性无特殊要求；只有非常 少的参数需要调整；算法实现简单，速度快；相对其它演化算法而言，只需 要较小的演化群体；算法易于收敛，相比其它演化算法，只需要较少的评价 函数计算次数就可达到收敛；无集中控制约束，不会因个体的故障影响整个问 题的求解，确保了系统具备很强的鲁棒性1 4 j 。 1 9 9 2 年意大利学者c o l o r n ia 、d o r i g om 和m a n i e z z ov 等人首先提出来蚁 群优化【5 1 ( a c o ：a n tc o l o n yo p t i m i z a t i o n ) 算法。在过去的十多年问，这种新型 的模拟进化算法引起了学者们的极大关注，并在优化组合、网络路由、函数 优化、路径规划等领域得到了广泛应用。蚁群算法特别适合求解规模较大的 或问题状态随时问变化的组合优化问题，如著名的t r a v e l i n gs a l e s m a n p r o b l e m ( t s p ) 、q u a d r a t i ca s s i g n m e n tp r o b l e m ( q a p ) 、j o b s h o ps c h e d u l i n g p r o b l e m ( j s p ) 等复杂组合优化问题。此外，蚁群算法在连续空间优化中的应 用也是近年来许多学者关注的研究方向。蚁群算法的主要特点是算法利用正 反馈的原理使得该方法能很快发现较好解；分布式计算使得该方法易于并行 实现，与启发式算法相结合，使得该方法易于发现较好解。 2 华北电力人学硕十学位论文 人工鱼群算法【6 j ( 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 ，a f s a ) 是2 0 0 2 年由 国内李晓磊博士提出来的一种仿生优化算法，它是一种基于动物行为的寻求 全局最优的新思路，是行为主义人工智能的一个典型应用。算法利用了鱼的 觅食、聚群和追尾行为，从构造单条鱼的简单的底层行为做起，通过鱼群中 各个体的局部寻优行为，最终在群体中使全局最优值突现出来。该算法具有 良好的克服局部极值、取得全局极值的能力，并且算法的实现无需目标函数 的梯度值等特性，故其对搜索空间具有一定的自适应能力。 ( 2 ) 菌群优化算法的产生与发展 细菌是一种单细胞生物体，是构成地球上各种高级生命体的最简单的形 体。尽管它们简单，然而经过亿力年的进化和自然选择，它们具备了一定的 智能性，来帮助它们从所处的环境中获取信息，以达到生存的目的。近些年 来，人们从细菌所具有的智能性的研究结果获得很多关于优化的灵感，提出 了几种基于细菌的优化算法，包括b f o t 刀( b a c t e r i a lf o r a g i n go p t i m i z a t i o n a l g o r i t h m s ) 、b c ( b a c t e r i a lc h e m o t a x i s ) t 8 】【9 1 3 2 1 、b c c l1 0 】( b a c t e r i a l c o l o n v c h e m o t a x i s ) 。 本文中将着重研究菌群算法b f o ( b a c t e r i a lf o r a g i n go p t i m i z a t i o n ) 。在一 些文献中，它也被称为b f a ( b a c t e r i a lf o r a g i n ga l g o r i t h m s ) 】。 b f o 算法的生物模型源自于大肠杆菌菌群的觅食行为【1 2 】【1 6 】。2 0 0 2 年， k e v i nm p a s s i n o 在上述模型之上，提出了b f o 算法【7 】。与其它群智能仿生算 法相似，b f o 优化算法也采用“群体 与“进化”的概念，群体中每个个体 都是问题的一个解，通过个体间的协作和竞争实现全局搜索。算法初始化时， 将产生一组随机解，每个细菌对应一个随机解；随后将大肠杆菌的觅食行为 细分为趋药、聚集、繁殖、迁徙等四个步骤对细菌群体进行模拟；然后再用 一个健康度函数用来衡量细菌的觅食结果，通过选择健康的成熟细菌进行繁 殖，而不健康的细菌不予繁殖的方式来实现优胜劣汰，去掉解空间中适应值 较低的个体。最后细菌群体通过以一定的概率迁徙到新的觅食区域中的迁徙 机制，减小了菌群收敛于局部最优的概率，提高了找到最优解的概率。 ( 3 ) 热工过程辨识 近些年来，对能源需求的只益增加促进了电力工业的发展，增加了对高 参数、大容量机组的需求。大机组的自动控制系统结构更加复杂，机组的安 全经济运行更为重要，因此对工程控制系统设计人员和现场人员提出了更高 的要求。掌握被控对象特性( 即数学模型) 是确定最佳控制参数，对提高火 电机组的控制品质有着重要的意义。现代的系统辨识大都是基于离散系统差 分模型的参数估计，并发展了以最小二乘法为基础的理论和方法，近年来又 华北t 乜力人学硕十学位论文 出现了基于神经网络、遗传算法等智能的辨识手段，但基于最小二乘机理的 现代的系统辨识方法对测试信号和噪声干扰均具有一定的要求。因此，研究 一种能适用于各种有效测试信号且精度较高的通用辨识方法具有重要的实 际意义。近年来又出现了基于神经网络、遗传算法、群智能算法等智能辨识 手段。将新兴的菌群算法应用于热工过程的辨识，对于扩展菌群算法的应用 领域和提高火电机组的控制品质均有有着重要的意义。 ( 4 ) 控制器参数优化 随着现代电厂机组容量的增大，对它运行的安全性和经济性要求也在逐 步提高，这就要求控制器( p i d ) 的品质能够达到要求。目前，p i d 控制仍 在电厂控制系统中广泛采用，即使是在大量采用d c s 控制的现代化装置中， 这类回路仍占总回路数的8 0 - - 9 0 。控制器在投入运行前虽然经过调试 人员的整定已经达到要求的指标，但是随着机组运行特性改变，需要重新整 定控制器参数。因为在现场没有根据运行曲线来自整定控制器参数的设备和 软件，所以运行人员只能根据经验来改变参数，反复试凑工作量比较大，虽 然这样在一定程度上也能满足运行要求，但是不能保证控制器参数是最优的 或者是比较优的，这不利于机组经济运行。 传统的p i d 控制器参数多采用试验加试凑的方式由人工进行优化。这种 优化工作不仅需要熟练的技巧，而且往往相当费时，由于p i d 控制器没有自 适应能力，当被控对象特性发生变化需要控制参数相应改变时，只能依靠人 工重新优化参数。许多学者提出了各种智能整定p i d 方法，如遗传算法、模 糊推理算法、神经网络学习算法、粒子群算法等，来对p i d 参数进行优化设 计。但是这些智能整定方法也还存在某些不足。 本文选取菌群算法进行参数优化的研究，该算法具备分布并行的寻优能 力，对初值不敏感的特点，能够快速对p i d 的参数进行优化，优化后的p i d 控制器具有良好的控制效果。 1 1 3 研究意义 目前，随着对菌群优化算法研究的深入，人们对其工作原理的理解也在 不断加深。作为一种新兴的群智能算法，菌群算法的理论体系尚未完整建立。 菌群算法中参数较多，目前对于相关参数的选取没有成系统的方法。因此， 研究算法中相关参数的选取方法对于提高算法的性能，加深对算法的理解均 有重要意义。另外，继续对菌群优化算法的模型进行完善和改进，建立完整 的菌群算法理论体系，以提高算法性能，拓展算法的应用领域，具有重要的 理论和实际意义。 4 华北电力人学硕十学仲论文 菌群优化算法具并行的寻优能力，对初值不敏感等特点，适合处 理复杂问题。将其应用在热工过程辨识和控制器参数优化领域，必将有利于 提高辨识精度和参数性熊指标。 1 2 国内外研究动态 目前算法的研究大致分为算法的改进、分析和应用。经过近几年的研究， 菌群算法在算法的改进、分析和应用方面都到了发展。 文献 17 】在k m p a s s i n o 提出的基本菌群优化算法基础上，改进了大肠杆 菌细菌问的相互作用，并且给出了一种新的细菌一粘细菌的模型和仿真，以 及这两种细菌模型的关系和比较。 在理论研究方面，文献 1 8 对菌群算法在一维情况下的稳定性进行了分 析和证明。文献 1 9 】将菌群优化算法应用于高维问题，对菌群算法在高维度 情况下的行为分析和收敛性证明方面进行了初步的研究工作，文献【2 0 】对菌 群算法的稳定性做出了相应的探讨。更深入的研究还有待进一步展丌。 在应用方面，在文献 7 】中，菌群优化算法被应用于液位控制系统的自适 应控制；文献 2 1 】与文献 2 2 1 中，菌群算法被应用到决策系统设计中的任务类 型选择和任务过程长度选择中；文献【l l 】中，对基本的b f o 算法的算子进行了 改进，提出了一种b s a 算法，并将此改进算法与p s o 以及f e p 算法针对特 定测试函数的最小值进行寻优，验证了改进算法的有效性。文献 2 3 1 与文献 【2 4 将b f o 算法应用于p i d 控制器参数的整定。文献 2 5 】中，成功的将b f o 算法应用于图像压缩技术。 菌群算法的另外一个研究方向是将b f o 与其它优化方法相结合，文献 【2 6 2 9 】中，都把b f o 算法与模糊方法相结合来得到改进，并且研究结果表 明都取得了不错的改进。文献 3 0 】中，在基本的b f o 算法基础上，提出了一 种变种群大小的b f s v p 算法，并通过与p s o 算法以及g a 算法相比较，验 证了b f s v p 算法的有效性。文献 3 l 】中，将b f o 算法与d e 方法相结合，提 出了一种混合的b f o 算法，并通过大量测试函数的验证，表明了该改进算法 的有效性。文献 3 2 】中，将b f o 算法应用与解决经济负荷分配问题( e l d ) ， 并与p s o 算法进行横向比较，验证了b f o 算法。文献 3 3 】中，提出了一种自 适应的b f o 算法( s a b f o ) ，通过对特定测试函数的寻优，并与b f o 、p s o 、 g a 算法进行横向比较，表明了改进算法的取得了不错的效果。 另外，研究细菌的优化算法还有以b r c m e r m a n n 为先驱的细菌趋药性算法 3 4 1 ( b a c t e r i a lc h e m o t a x i s ，b c ) ，后来经过m u l l e r 进一步的突破提出了更好的算 法【35 1 ，他们的研究出发点是细菌在引诱剂环境下的应激机制和梯度下降方法 5 华北电力人学硕j 卜学位论文 的相似性。与其它进化算法不同的是b c 算法只依赖于单个细菌的运动行为， 这使得算法具有简单性，但是因为缺少了个体之问的协作使得算法的全局寻 优能力较差。文献【l o 】中，李威武等人借鉴微粒群算法的群体信息交互模式 提出了一种改进的算法一细菌群体趋药性算法( b a c t e r i a l c o l o n y c h e m o t a x i s ，b c c ) ，b c c 算法虽然提高了算法的寻优能力，但增加了算法的 复杂度，有待进一步的完善。文献【3 6 _ 3 9 】中有研究者做了b c c 算法应用方 面的研究，文献 4 0 将侧重点放在细菌的进化方面，提出了细菌进化算法 ( b e a ) ，并解决了车问作业调度问题。 1 3 论文的主要工作内容 本论文的主要工作内容分为以下两个方面： i 理论研究 介绍菌群算法的基本原理，分析算法的特点，找出其优势和不足，提出 具有代表性的改进策略。以往的b f o 算法的参数的选择没有一个确切的指导 性法则，本文通过对菌群算法的原理以及算例进行分析，给出了参数选取应 遵循的法则。 随后通过对已有的b f o 的理论研究，提出了一种变步长的菌群优化算 法。利用算例表明此改进算法比原算法具有更快的收敛速度和精度。 经过上述工作之后，对b f o 算法有了更深的认识。从鱼群算法和粒子群 算法中得到灵感，将新的参数以及概念引入菌群算法，并将菌群算法的行为 进行了相应改动，提出了一种改进的菌群算法a b f o ，从而达到了对原b f o 算法的不足之处进行改善的目的。 该算法的创新之处有： ( 1 ) 提出了作用力范围矩阵与步长矩阵的概念。论文中针对原b f o 算 法中在所有维度上取都取相同作用力范围和统一的步长的不足，将算法改为 对应于不同维度取不同的作用力范围和不同的步长，从而引入了作用力范围 矩阵与步长矩阵，最终使得算法的搜索效率得以提高。 ( 2 ) 重新定义了a b f o 算法的趋药性、聚集、繁殖、变异4 种行为。其 中包含了基本菌群算法中的趋药性，聚集，繁殖三种行为，而变异行为是在 原迁徙行为的基础上加以改进而来。a b f o 算法重新定义的聚集行为是本文算 法的独到之处。 、 ( 3 ) 在聚集行为中，引入了粒子群算法中的加速因子用以加快整个细 菌群体的寻优速度；并且重新改写了聚集行为的表达式，使细菌间的作用力 范围方便可调，同时也保留了原算法所具有的特点。 6 华北电力人 ( 4 ) 在趋药性行为以及聚集行为 学硕十学位论文 中加入溢出检测环节保证细菌不会脱离优 化问题的可行域。在繁殖行为中，让子代的步长比父代更小；以及在变异行为中 加入新参数的调整；通过这两种方式来调整菌群算法的搜索精度和速度之间的关 系。 i i 应用研究 在上述理论研究工作进行完毕之后，需要对改进菌群算法的有效性、实 用性、合理性进行验证。本文的应用研究主要是基于上述改进菌群算法的热 工对象的模型辨识和基于改进的菌群算法的p i d 控制器参数优化两个方面。 针对传统的系统辨识方法存在着一定的不足和局限，提出基于改进菌群算法 ( a b f o ) 的热工过程辨识方法。随后提出改进的菌群算法的p i d 参数优化设计 方法，并应用于单回路控制系统和主汽温串级控制系统。文中将运用c + + 语 言和m a t l a b 语言对改进算法进行编程仿真，观察算法的收敛速度、解的 质量和控制效果，验证该算法在热工对象模型阶次辨识与p i d 控制器参数优 化中的有效性、可行性。 7 华北电力人学硕十学位论文 第二章基本菌群算法及其特点 2 1 菌群算法的基本原理 大肠杆菌( e c o l i ) 是生活在人体大肠内的一种细菌，而大肠内的生存环 境实际上为一种溶液环境，溶液中有大肠杆菌生存所需要的各种营养物质。 大肠杆菌个体之间有其特有的通信机制：大肠杆菌通过向自己的周围散 播化学信息( 一种称之为引诱剂的化学物质即引诱剂) ，来通知同伴在环境 中的营养物质的分布情况，实现通信的目的。引诱剂的释放范围是以细菌为 中心的一个区域，并且浓度随着离开细菌的距离增大而减小。引诱剂又分为 两种，一种是具有吸引作用的信息，另外一种是具有排斥作用的信息，而前 者作用的范围远远比后者要大；这两种化学信息所带来的效果类似于引力与 斥力所造成的效果，因此，又将细菌问的这种通信机制称为引力斥力机制。 具有吸引作用的引诱剂浓度越高则代表该位置上的营养物质越多，因此细菌 群体就朝着环境中引诱剂浓度高的方向上运动。对于大肠杆菌而言，引诱剂 的浓度信息就是细菌群体之问相互通信的一种桥梁，细菌通过接收到来自其 它细菌的化学信息，进而进行判断，改变自己的运动趋势，从而完成觅食行 为。 2 0 0 2 年，k e v i nm p a s s i n o 教授通过模拟大肠杆菌的觅食行为，提出了 b f o 算法【7 1 。其定义的菌群行为包括以下四个行为：趋药性行为( c h e m o t a x i s ) ， 聚集行为( s w a r m i n g ) ，繁殖行为( r e p r o d u c t i o n ) 和迁徙行为( e l i m i n a t i o na n d d i s p e r s a l ) 等四个步骤。 为了模拟实际细菌的行为，首先引入如下记号： 细菌的种群规模，菌群算法所优化问题的维度为，细菌的位置信息 由向量x = ( 五，毛，j c v ) 所表示。置= ( ，而，) 表示第i 细菌所处的位置， 其中玉o = l ，1 ，) 表示细菌的第i 个分量；细菌当前所在位置x 处的食物浓度 表示为j = 厂( x ) ，其中，为适应度函数；s t e p 表示第f 细菌的步长；t r ) r n u m 为 细菌在一次趋药性行为中的最大尝试次数； 乙为细菌进行的繁殖行为的数 目；心为细菌进行的迁徙行为的次数。 2 1 1 趋药性行为( c h e m o t a x is ) 大肠杆菌趋药性行为有两个基本动作：前进( s w i m ) 和翻转( t u m b l e ) 。前 进是沿与上一步相同的方向运动，而翻转是取一个新的方向运动。细菌的趋 8 华北电力人学硕十学位论文 药性行为就是对这两种基本动作的模拟。其行动方式如下：朝某一随机方向 上前进一步；如果此位置上的适应值要优于原位置，那么就一直在这个方向 上执行前进动作；如果此方向上的适应值不再优于上一步所处位置的适应 值，则执行翻转动作，朝另外一个随机方向运动；如果达到最大尝试数目， 则终止该细菌的趋药性行为，跳转到下一个细菌执行趋药性行为。 趋药性行为的程序流程如下： ( 1 ) 假定细菌群体中第i 个细菌的当前位置为x = ( x i ，屯，x 1 ) ，计算细菌 在此位置上的适应度函数值j ( x ) ，并令= j ( x ) ，把它记为细菌i 的历史 最优值； ( 2 ) 随后产生一个随机方向向量，并将之单位化，记为a ；同时产生一个 步数的计数器t ，并令t = o ，用来保存在此随机方向上走过的步数。然后在此 随机方向前迈出一步，步长为s t e p ，计数器t + + ；得到细菌的新位置删。 新位置的计算公式如下所示： 以删= x + s t e p a ( 2 1 ) ( 3 ) 计算k 。位置上的适应度函数值以州= 厂( k 喇) 。如果有k 优于 ( 对于最小值问题，即以州 ) ，那么表明在此 随机方向上的前进动作是j 下确的，令儿= 以州，然后继续在此随机方向不 断前进，按( 1 ) 式不断更新坐标，直到删不再优于或者在当前方向上 达到最大试探次数为止；否则，令t = t r y n u m ，结束当前细菌的趋药性行为。 对整个细菌群体的位置信息采用如下异步更新的方式：每次执行趋药性 行为时，对于群体中的每一个细菌而言，都拥有t r y n u m 的次试探次数来更新 自己位置信息；如果达到t r y n u m 所规定的试探次数，那么就跳转到下一个细 菌，对下一个细菌模拟趋药性行为。在其它所有细菌都实执行了一轮趋药性 行为之后，再次轮到本细菌执行趋药性行为，开始第二轮的趋药性行为。由 于第二轮趋药性行为会产生新的随机方向，从而在新方向上执行前进动作， 从而间接的实现了翻转动作。 其程序流程图如下所示： 9 华北电力人学硕十学位论文 第i 个细菌的位置x ，令 t = 0 ：计算在此位置上的 适应值j ( x ) ，并令 j l a s t ；j ( x ) ，( 同时可对j 修正) 上 设定细菌在同一个方向 上的最大尝试数目 t r y n u m 图2 - 1 趋药性行为流程图 2 1 2 聚集行为( s w a r m in g ) 、 在菌群寻取食物的过程中，细菌个体之间通过相互间的作用来实现群体 的聚集行为。对于最小值问题，设第i 个细菌的位置信息由向量 五= ( 五，毛，毛) 表示，整个细菌群体对它所处位置施以的聚集作用的数学表 达式为： l o 华北电力人学硕十学位论文 奠= n 川+ n m i 川 ( 2 2 ) 一d 。，。二e 王p ( w a t t r ac t 。：c 工。一x ：，2 ) c2 3 ， 而，p ，。，e ，c p ( v 矿，。，薹c ，c ，c ：，2 ) c 2 。4 ， 其中，吃帅“为引力的深度，舯“为引力的宽度，i i 聊讹州为斥力的高度， 妇小为斥力的宽度。艺为细菌f 的第m 个分量，为整个细菌群体中其它 细菌的第m 个分量。此公式的含义为：整个细菌群体在细菌f 所处位置置处 所产生的作用力之和。一般情况下取d a = | i l 删抽。，。 在趋药性循环中引入聚集行为后，第i 个细菌的适应度的计算公式变为 ( z ) = ，( 墨) + 厶( 五) ( 2 5 ) 因此聚集行为就是通过上述公式( 5 ) 来对适应值进行修j 下，来使细菌达 到聚集的目的。 2 1 3 繁殖行为( r e p r o d u o t i o n ) 在执行完指定步数的趋药性行为之后，根据各个细菌的健康度进行排 序。健康度可以通过对相应细菌在它的生命过程中所吸收到的营养值的多少 来判断。即把健康度定义为单个细菌在前面的趋药性行为中所经历位置的适 应值的代数和。因此有如下的健康度函数 h e a t h ( i ) = 以 ( 2 6 ) 其中h e a l t h ( i ) 表示第f 个细菌的当前的健康度，：表示第f 个细菌的适应 度函数值，h u m 表示到当前位置之时，第f 个细菌所完成的趋药性行为的数 目。 然后按照式( 2 - 6 ) 所定义的健康度函数对整个菌群按照健康度进行排序。 细菌健康度较高即觅食结果较好的细菌有权利进行繁殖行为，生成子代。子 代的位置、步长以及其它信息都与父代完全相同。健康度不高的细菌没有得 到繁殖权利，它们将死亡，以此来维持菌群的规模不变。 2 1 4 迁徙行为( e ii i l l i n a t i o na n dd is p e r s a l ) 迁徙行为是实际环境中的细菌被外力杀死或者被驱散到新的区域中去 的一种现象。这破坏了细菌的趋药性过程，但是细菌也可能将因此寻找到食 物更加丰富的区域。因此这是使细菌强迫的离开它所在位置的一种方法。在 华北l u 力人学硕十学侥论文 算法中，菌群经过若干代繁殖后，细菌以概率p 。被随机重新分布到寻优区 | 、h j 。p 。被称为迁徙概率。 整个算法的流程如下图所示： 2 2 对聚集行为的分析 图2 - 2b f 0 算法的流程图 基本b f 0 算法通过模拟细菌之间的引力斥力机制从而提出了如表达式 ( 2 - 2 ) 所示的聚集行为，实现了细菌间的通信，从而改善整个群体的搜索 速度，但是并没有就聚集行为何时引入，如何引入以及参数的选取做出说明。 由此函数建立的是一个由n 个细菌的引力和斥力所建立的力场，通过对处于 力场中的不同位置的细菌施加以不同的力以实现聚集行为。下面就在二维寻 优问题中，整个寻优空间上只有两个细菌的情况下，由式( 2 - 2 ) 所描述的 力场的效果进行分析。 设已知的两个细菌的位置坐标分别为五( 1 5 ，1 5 ) ，五( 1 5 ，2 0 ) ，令z = 止( x ) 为z 轴：五轴和而轴上的坐标取值范围分别为工。，工，【0 ，3 0 】，令 吃= k = o 1 ，= o 2 ，w 。阼舳= 1 0 ，将上述参数带入式( 2 2 ) ， 得到对应的表达式，在三维空间画出其图形如下图所示： 1 2 图2 - 3 公式( 2 - 2 ) 仿真曲线( 空间视角) 两个细菌的引力斥力函数 图2 - 4 公式( 2 - 2 ) 仿真曲线( 平面视角) 由图2 - 3 和图2 - 4 中可以看出，两个细菌所建立的力场都是与给定细菌 的位置息息相关的。由于式( 2 2 ) 所处理的问题是最小值问题，因此“海拔 越低的位置表示该位置的适应度越优秀；反之，海拔越高的位置表示该位置 适应值越差。因此从图2 3 中可以观察得知，在比较靠近给定细菌置与正的 位置附近存在着“海拔 最低的“山谷”，即细菌的适应度函数值以，最优的 一个区域；若有新的细菌进入此“山谷区域中，则它会受到细菌疋与置的 合力，其中引力占主导成分，将新细菌吸引向五与x ：所处位置。但是如果 过于靠近给定的细菌墨与五的位置，斥力将会占主导成分，适应值将会迅 速变差，使得新加入的细菌不会过于靠近细菌五与五所处位置，从而避免 1 3 华北电力人学硕十学位论文 了细菌位置的重合，使整个细菌群体的多样性得以保持，如图2 2 中的细小 “山峰”所示。 从图2 - 4 中可以看出：单个细菌引力的作用范围约为5 个单位长度，而 斥力的作用范围比引力的作用范围小一个数量级左右。分析式( 2 2 ) 中限制 引力和斥力作用范围的函数y = e - xx o ，1 0 】，将之仿真图形绘制如下： 图2 - 5y = e “仿真曲线 分析y = e 。仿真曲线可知：当x 5 时，y 0 0 0 6 7 。表明函数值y 衰减到 了坐标原点时函数值的0 1 以下，其函数值基本可以忽略。因此公式( 2 3 ) 与公式( 2 - 4 ) 中的指数函数的指数项如果大于5 ，其对应的引力与斥力作用视 为衰减到可以忽略。 由上述的分析可知，公式( 2 - 2 ) ，( 2 3 ) ，( 2 4 ) 中的参数比，肋“，肌w 的取值就是为了间接的确定单个细菌的引力与斥力的作用范围大小。舳“的 取值直接影响到单个细菌引力范围的大小。舯“取值越大，单个细菌的引力 范围就越小。同理一r 的取值越大， 算公式( 2 3 ) 与公式( 2 4 ) 中的指数项， 范围大小。如上述两个细菌的情况中， 单个细菌的斥力范围就越小。通过计 就可以间接的确定引力与斥力的作用 ：0 2 ，通过j ，e - x 函数的衰减速 率的分析，就可以算出引力的作用范围为5 。斥力的作用范围的确定方法同 理。 对于2 维情况的引力与斥力范围的示意图如下： 图2 - 6 引力与斥力的作h j 范围 图2 6 中，r a n g e r e p e l l 表示斥力的作用半径，r a n g e a t t r a c t 表示引力的作 用半径。在小圆范围内，斥力起主要作用；而在小圆之外，大圆之内，引力 起主要作用。 由前文公式( 2 - 5 ) 可知，厶( 置) 的引入是为了修j 下适应值 因此公式 ( 2 2 ) ，( 2 - 3 ) ，( 2 - 4 ) 中的参数吃舳d ，k 舳的大小就直接影响到修j 下值 厶( ) 的大小。一般来说，引力深度吃舢“取最优适应度值与平均适应度值 的差值的1 1 0 之间。 2 3 小结 本章详细地介绍和分析了菌群优化算法的基本原理，并详细说明了算法 流程。随后研究了着重研究了聚集行为的表达式及其原理，分析了聚集行为 中的4 个参数引力深度、引力宽度、斥力高度和斥力宽度的具体意义：并给 出了这些参数选取应遵循的法则。对这些参数规律的认识，有助于对算法的 进一步研究。本章的理论分析将为后续章节的研究做好准备。 1 5 华北电力人学硕十学位论文 第三章变步长的菌群算法 3 1 菌群算法的改进思路 3 1 1 趋药性行为的改进 对于优化算法而言，在更小的步长之下能够进行更精密的搜索，因而得 出的计算结果的精度也就会越高，但是同时也会导致计算速度的下降；因此 在在整个算法流程的哪个阶段引入变长的因素，以及何时引入就成了关键问 题。 从下述事件中可得出菌群算法的第一种改进策略： 考试事件：学生是通过一次次的考试，从而不断提高自己的成绩，从而 最终达到自己的最佳成绩。每一次考试中满分为1 0 0 。假定有某一个班的全 班同学在经历一次考试行为之后，公布分数。然后从分数中分析不足，提出 在下一次考试中将成绩提高的策略。策略1 ：分数低的同学通过向分数高的