（控制科学与工程专业论文）多台制冷机组控制系统研究及优化.pdf

摘要 本文针对现有多台制冷机组单独供冷量，智能化控制程度低，管 理难度大，水泵不能调速或者控制水平低，能耗大，难以满足生产要 求的现状，设计开发了多台制冷机组控制系统，可适用于工厂制冷系 统，选题紧密结合实际，具有重要的实际应用价值。 本文以多台制冷机组为研究对象，对多台制冷机组控制系统设计 方案和数学优化调度模型进行了重点研究。针对多台制冷机组控制系 统的需求，结合西门子m p i 网络通信技术，本文将多台制冷机组控制 系统分为二层：楼下监控管理层、屋顶现场监控层进行实现。结合 p l c 技术，描叙了多台制冷机组控制系统的硬件和软件具体实现框图， 给出了系统总体结构图和关键程序实现，在实际的工程应用中，本系 统很好的完成了控制任务，取得很好的控制效果。 在多台制冷机组动态调节建模原理基础上，通过用遗传优化蚁群 算法和常规的梯度调度对模型进行了软件编程仿真结果表明，该方法 能较好的满足实际生产需求。 关键词：p l c ，变频调速，优化蚁群算法，制冷机组调度 a bs t r a c t i nt h i sp a p e r ，t h ee x i s t i n gm u l t i p l es e p a r a t er e f r i g e r a t i o nu n i tc o o l i n g c a p a c i t y , t h el o wl e v e lo fi n t e l l i g e n tc o n t r o l ，d i f f i c u l tt om a n a g e ，p u m p s c a nn o tc o n t r o lt h es p e e do rt h el o wl e v e lo f e n e r g yc o n s u m p t i o n ，t h i sc a l l n o tm e e tt h ep r o d u c t i o nr e q u i r e m e n t so ft h e s i t u a t i o n ，8 0 ，t h ep a p e r d e s i g n sa n dd e v e l o p sm o r et h a no n er e f r i g e r a t i o nu n i tc o n t r o ls y s t e m a p p l i c a b l e t ot h ef a c t o r y c o o l i n gs y s t e m ，s e l e c t i o no fr e a l i t i e s ，h a s i m p o r t a n tp r a c t i c a la p p l i c a t i o n s i nt h i sp a p e r , m u l t i p l er e f r i g e r a t i o nu n i t sf o rt h es t u d yo fm u l t i p l e c h i l l e rc o n t r o ls y s t e md e s i g na n dm a t h e m a t i c a lo p t i m i z a t i o nm o d e lf o ra k e yr e s e a r c h f o rm u l t i p l er e f r i g e r a t i o nu n i tc o n t r o ls y s t e mr e q u i r e m e n t s ， c o m b i n e dw i t hs i e m e n sm p in e t w o r kc o m m u n i c a t i o nt e c h n o l o g y , t h i s p a p e r w i l lb em u l t i p l er e f r i g e r a t i o nu n i tc o n t r o ls y s t e mi sd i v i d e di n t ot h e s e c o n df l o o r ：d o w n s t a i r ss u p e r v i s i o na n dm a n a g e m e n t ，s i t em o n i t o r i n g l a y e rt oa c h i e v et h er o o f c o m b i n a t i o no fp l ct e c h n o l o g yd e p i c t st h e m u l t i p l ec h i l l e rc o n t r o ls y s t e mb l o c kd i a g r a mo fh a r d w a r ea n ds o f t w a r e r e a l i z a t i o n ，t h eo v e r a l ls t r u c t u r eo ft h es y s t e mi sg i v e nt h ek e yt op r o g r a m i m p l e m e n t a t i o np l a na n d ，i np r a c t i c a l e n g i n e e r i n ga p p l i c a t i o n s ，t h e s y s t e mc o n t r o lt a s k w e l ld o n e ，t oo b t a i ng o o dc o n t r o le f f e c t i nt h em u l t i p l er e f r i g e r a t i o nu n i t sb a s e do nt h ep r i n c i p l eo f d y n a m i c a d j u s t m e n tm o d e l ，t h r o u g ht h eu s eo fg e n e t i ca n tc o l o n ya l g o r i t h ma n d c o n v e n t i o n a l g r a d i e n ts c h e d u l i n g as o f t w a r e p r o g r a m m i n g m o d e l s i m u l a t i o nr e s u l t ss h o wt h a tt h em e t h o dc a nb e a e rm e e tt h en e e d so f a c t u a lp r o d u c t i o n k e y w o r d s ：p l c ，v a r i a b l ef r e q u e n c ya n ds p e e dr e g u l a t i o n ，o p t i m i z e d a n tc o l o n ya l g o r i t h m ，t h er e f r i g e r a t i o nu n i tc o m m i t m e n t s c h e d u l i n g i i 硕士学位论文第一章绪论 1 1 论文选题的背景和意义 第一章绪论帚一早殖记 组合调度优化问题【lj 是通过对数学方法的研究去寻找离散事件的最优化编 排、分组、次序或筛选等等，是运筹学的一个经典且重要的分支，所研究的问题 涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域。组合调 度最优化问题，就是在给定约束条件下，求出使目标函数极小( 或极大) 变量的 组合调度能量分配问题。 解决组合调度优化问题主要使用了优化方法，所谓优化方法，其实就是一种 搜索的过程和方法规则，它是基于某种思想和机制，通过一定的途径或方法规则 来得到满足用户要求的问题的解【2 】。智能优化方法是一种重要的优化方法，是一 个近几年来发展起来的非常活跃的研究领域。智能优化技术是一种以数学为基 础，用于求解各种工程问题优化解的应用技术。智能优化技术作为一个重要的科 学分支一直受到人们的广泛重视，并在很多工程领域中得到迅速推广和应用，如 系统工程、管理工程、计算机、自动化、采矿、机械等许多领域，遗传算法、禁 忌搜索算法、模拟退火算法、蚁群算法和粒子群优化算法等，在国民经济的各个 行业中都获得了广泛的应用【3 】。 制冷机组组合调度分配问题是制冷系统经济调度的一个很重要的环节，制冷 机组组合调度的基本任务是在满足负荷平衡、系统安全约束、机组特性约束等条 件下，经济、合理地安排机组次日的调度计划曲线。狭义地讲，制冷机组组合调 度问题是指在满足负荷平衡和系统约束前提下，以系统运行费用最小化为目标来 确定制冷机组的开停方案。经济功率分配是以整个系统消耗功率的费用最小为目 标决定制冷机组的那些机组启停，广义的制冷机组组合调度问题包含经济功率分 配本文除特别指明外，制冷机组组合调度均为广义概念。蚁群算法是一种新兴的 用于解决组合调度最优化问题的高效的内启发式搜索技术，具有较强的鲁棒性、 优良的分布式计算机制、易于与其他方法结合的特点，目前已经在许多优化问题 中得到了成功应用。 1 2 目前研究现状 本论文是运用蚁群算法、遗传算法研究制冷机组组合调度能量分配问题，涉 及主要核心内容是进化计算原理思想和多台制冷机组模型分析及优化，进化计算 硕士学位论文第一章绪论 ( e v o l u t i o n a r yc o m p u t i n g ，简称e c ) ，是最近四十年来兴起的、受到生物进化思 想启发而在学术界产生的一类新型优化算法的统称，它既是一种模仿生物进化过 程的优化方法，也是属于模仿人的智能优化的范畴。进化计算采用了简单的编码 技术来表示各种复杂的结构，并通过简单的遗传操作和优胜劣汰的自然选择来指 导性学习和确定搜索的方向。进化计算有自组织、自适应、自学习的特点，而且 不受到其搜索空间限制性条件( 如可微、单峰等) 的约束，不需要其他辅助信息 ( 如导数) 【4 】。这使得进化计算不仅能得到较高的效率，而且简单、通用性好。 它的三大分支主要包括：遗传算法( g e n e t i ca l g o r i t h m 简称g a ) 、进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g 简称e p ) 和进化策略( e v o l u t i o ns t r a t e g y 简称e s ) ， 这三大分支在算法实现方面具有一定细微的差别，但它们具有一个共同的特点， 即都是借助生物进化的思想和原理来很好地解决实际问题。 另外，本文还还涉及制冷机组改造系统软硬件设计方面介绍，并阐述了系统 改造后的优越性。在假设的理想条件下建立了系统算法模型，并运用优化算法对 其进行了仿真分析得出结论。 t 1 2 1 目前算法和多台联合机组运行研究现状 l 、蚁群算法和遗传算法目前研究现状 最近几年，蚁群算法得到了不断的发展、改进和完善，并且进一步了验证了 t s p 以及许多实际优化问题的求解，这些改进了的a s ( a n ts y s t e m ) 1 5 1 算法都是 更加增强了蚂蚁搜索过程中对最优解的搜寻能力，只是搜索控制策略有所不同。 这种算法求解t s p l h 题的能力比遗传算法和模拟退火算法具有显著的优势。吴庆 洪教授等【6 】从遗传算法中变异算子的作用得到了启发，在蚁群算法中采用了逆转 变异机制，进而提出了一种具有变异性能的蚁群算法。最近几年来，众多研究学 者把q 智能化学习、网格划分、自适应、网络规划等思想融合到蚁群算法中，基 本上去改进和完善蚁群算法局部参数，获得了一定可观的结果。比较典型的应用 研究包括：数据挖掘、网络路由优化以及一些经典的组合优化问题，目前这方面 的应用研究越来越受到重视。 近年来，随着对于遗传算法【7 】研究的不断深入，有越来越多的人认识会了 解了遗传算法，并将它应用到越来越广泛的领域。将遗传算法用于解决各种实际 问题后，人们在实际运用中发现遗传算法也会由于各种原因过早向目标函数的局 部最优解收敛，从而很难找到目录函数的全局最优解。其中有些是因目标函数的 特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是因 - 算法设计不准确。为此，不断有人对遗传算法提出各式各样的改进方案。例如： 针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对 2 硕士学位论文 第一章结论 关于按比例的选择机制，提出了竞争选择、连续挑选等改进方案；针对原先设计 的一点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传 算法各控制参数在进化过程中一些不变的情况，提出了退化遗传算法、自适应遗 传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。 2 、多台制冷机组联合运行研究现状 从上个世纪9 0 年代开始以来，中国资源方面形势日益严峻。制冷系统行业 的迅速发展产生了巨大的能量损耗，相应地也给环境造成严重的污染问题。从节 能减排出发，研究了通过制定中国制冷系统能效标准来逐渐控制和降低资源消 耗。让制冷机组系统利用最小的能量损耗，而得到较多的制冷量，在国内外的专 家学者们经过多年来无数次的不断探索，研究制冷机组运行及多台联合运作节能 众多新技术，使制冷系统行业不断地向前发展【8 j 。 国际上制冷机组系统的计算机仿真实验研究开始于2 0 世纪7 0 年代末，而在 国内，当从陈芝久教授提出“制冷系统热动力学 的看法之后，已经有不少研究 学者投身于制冷机组系统仿真的分析研究，并且取得了大量的令人瞩目节能成 效。制冷机组系统实验仿真技术进行到现在，历经了从单个部件模型分析到整体 系统模型分析研究，从稳态的、集中的各个参数模型发展到动态的、分布式的各 个参数模型分析研究，从瞬态状态到长时间工作过程的实验仿真研究。研究制冷 机组组合优化分配运行的控制问题时，需要按照以下几个原则【9 j 求解：( 1 ) 整体 性原则；( 2 ) 最优化原则；( 3 ) 模型化原则；( 4 ) 动态原则，因此对于制冷机组 控制系统的实例仿真和优化，动态数学模型才会更具有更加直观的意义。然而， 当前绝大多数智能化控制算法仍只是以制冷机组系统的单台机组作为被控制对 象进行智能控制。要使制冷机组系统的组合分配控制策略和智能化控制算法真正 相融合起来，这样有必要分析研究制冷机组系统的变量智能控制算法。目前对制 冷机组系统变量分配控制问题投入研究还是比较少。从节能技术方面却具有巨大 的应用研究发展前景，所以也就成为当前研究的重要课题之一。 1 2 2 对算法目前研究的评价 l 、对蚁群算法目前研究的评价 蚁群算法凭借其突出的问题和简单的算法结构求解能力，以及稳定、灵活、 自组织能力和分布式控制等特点，吸引了很多研究者，并取得了令人注目的成果。 该理论特别适合于工程问题【l2 j 中日益复杂的信息处理需求，尤其是那些动态特 性突出的问题。然而，由于其理论依据源自于对生物群落社会性的可模拟性，因 此其相关数学分析还较薄弱，这就导致了现有研究还存在以下几个主要重要的问 题： 3 硕士学位论文第一章绪论 ( 1 ) 蚁群算法的数学理论基础薄弱，缺乏普遍意义的理论性分析。算法中 涉及的参数设置没能够有确切的理沦依据，一般按照经验来确定，对具体问题的 依赖性较大； ( 2 ) 比较性研究不足，与各种成熟的优化算法之间的基本特性及性能特点 的对比研究还不是十分充分。将来的研究工作应加强算法特性的分析，进一步明 确与算法原理相关的重要意义，如t 单个个体的复杂性、学习能力和推理能力等。 还应扩展蚁群算法与其他算法如神经网络、禁忌搜索和支持向量机等先进技术的 混合，以改善其自身的性能。作为一种新型的模拟进化算法，蚁群算法研究时间 较短，不像其他启发式算法那样具有系统的分析方法和坚实的数学理论。 挥发因子等参数【l3 】的选择基本是依靠实验和经验，目前尚无通用及确定的 理论方法去确定，因此理论和实践方面尚有许多问题需要更待深人的研究与探 讨，但是该算法的并行特性和强鲁棒性等优点吸引着许多学者不断对其进行深人 研究。随着理论研究和实践经验的积累，蚁群算法必将成为求解复杂组合优化同 题的高效算法。对蚁群算法的很多方面有待完善，需要加强并进行深人研究： ( 1 ) 加强对蚁群算法数学理论模型基础和系统分析方法的研究目前各种改 进的蚁群算法的收敛性、有效性、通用性，参数的设定主要根据大量实验的统计 结果，没有很成熟的理论和系统的分析方法作指导，算法模型也有待更进一步深 入研究，这些问题就限制了蚁群算法的推广应用及蚁群算法的改进与完善； ( 2 ) 加强蚁群算法各种改进方法的综合研究目前的研究主要针对蚁群算法 不同的部分做修改，因而算法各个参数的相互作用、最优配置，各种方法的综合 使用及各种改进方法的相互作用是以后研究的重点之一； ( 3 ) 加强蚁群算法与其他算法的混合蚁群算法具有很强的藕合性，易与其 他进化算法或者局部搜索算法结合，将蚁群算法与神经网络、遗传算法、模拟退 火算法等相混合，必将成为今后蚁群算法新的研究热点： ( 4 ) 加强蚁群算法与应用的结合，尽管蚁群算法在众多领域得到了推广， 但大多数研究者仅局限于仿真试验和思想的引入，充分挖掘蚁群算法在实际应用 中的潜力，对现有应用领域进行深化研究的同时，进一步扩大其应用范围具有重 要意义； ( 5 ) 改进算法在连续优化问题中的性能研究，b i l c h e vg a 等【1 4 】研究了求解 连续空间优化问题的蚁群系统模型，并用来解决某些实际工程设计问题，但是蚁 群算法在求解连续优化问题方面的优越性相对要弱一些，而实际工程应用中存在 着许多此类问题，如不能将蚁群算法应用于求解连续优化问题，将会束缚蚁群算 法在其他研究领域的应用。 2 、对遗传算法目前研究的评价 4 硕士学位论文第一章绪论 遗传算法具有很强的全局搜索能力，并且这种搜索能力不依赖于特定的求解 模型。但是直接应用简单遗传算法来解决优化问题，算法性能可能不尽人意。要 设计出有效的遗传算法，必须尽可能地应用特定问题域的知识，或是结合局部寻 优的方法，设计收敛速度较快的混合遗传算法。根据有限状态齐次马尔可夫链方 法，可以证明某些算法是以概率1 收敛至全局最优点的。然而，实验表明，当规 模较大时，算法常常会产生早熟现象，即过早地收敛于局部极小点的现象，问题 的规模越大，早熟越容易发生。虽然某些算法在理论上是以概率1 收敛至全局最 优的，但是这种收敛性是由变异过程中概率转移矩阵的互通性保证的，而通常变 异概率是很小的；当算法出现早熟现象时，仅仅依靠变异操作仍然很难从局部最 优点跳出，遗传算法从初始状态到全局最优点的收敛时间的平均期望可能大大超 过我们的预期。因此，好的遗传算法应当兼顾局部收敛性能和全局收敛性能【1 5 1 。 1 3 论文的总体思路及研究方法 1 3 1 总体思路 本论文总体思路可以概括为：“立足好一个中心，把握好两个基本，做好三 个结合”。所谓“立足一个中心 就是立足于蚁群算法，从基本上对蚁群算法进 行展开研究，深刻分析研究基本蚁群算法的工作原理，以基本蚁群算法为中心进 行改进及提高，做出一个更真实更智能化的蚁群系统。所谓“把握两个基本 就 是把握遗传算法的基本原理和制冷机组组合调度优化问题。所谓“做好三个结合” 就是( 1 ) 将遗传算法和蚁群算法相结合起来，构造出智能化混合算法：( 2 ) 将 遗传蚂蚁混合算法和制冷机组组合调度起来，使得遗传蚂蚁算法得以应用；( 3 ) 将遗传蚂蚁算法运行结果和传统的制冷机组组合调度算法运行结果结合起来进 行比较分析，最后得出一个结论。 1 3 2 研究方法 本论文是从整体上着眼，从局部着手，逐个分析，综合分析研究运用。按照 “总体规划、局部突破、先破后立、综合归纳”的方法进行论述。通过整体规划 制定出一条综述思路来，通过局部突破，使得蚁群、遗传算法的性能上都能提高， 通过逐个分析、先破后立把蚁群算法、遗传算法混合在一起，得出一个改进的遗 传蚂蚁混合算法，然后将遗传蚂蚁算法运用在制冷机组组合调度实例之中，通过 综合归纳，总结遗传蚂蚁算法。 5 硕士学位论文第一章绪论 1 4 论文的主要工作 1 4 1 论文的主要工作 基本a c o 模型就是根据t s p 例子描述的来说明a c o 在求解t s p 问题时具 有明显的优势。本文就是利用机组最优启停能量分配问题与t s p 问题之间的相 似性，尝试把机组最优启停能量分配问题设计成类似于t s p 问题的模式，并灵 活地处理各种约束，从而可以用a c o 算法来求解。 另外对基本蚁群算法局部进行了优化和完善，本文运用蚁群算法和遗传算法 的相结合及综合分析制冷机组合，和以往应用相比，在基本蚁群算法上主要有五 个方面改进：( 1 ) 每个蚂蚁在进行一次搜索回到本部后，和其相邻伙伴交流信息， 进行智能化学习；( 2 ) 当蚂蚁进行数次搜索后，可以自由结合成为群体( 群) ， 群的信息量能够更加丰富，指导搜索能力能够更加强。这里的群是一个虚拟的团 体，其行为对单个蚂蚁有一定的指导和参考意义。每个群对其成员并没有绝对的 控制行为，即每个蚂蚁无论是否加入一个群里，都会令其保持自身的独立性。在 这里组建群的原则是：性格( 参数) 相同的蚂蚁结合为一个群，强强相联合而结 合为一个群，弱弱相联合而结合为一个群，强者帮助带弱者结合为一个群，随机 调集一些蚂蚁进行联合结合为一个群；( 3 ) 由于蚂蚁是一个生物体，受到遗传作 用，他们的后代可能要比父辈们更有智能化，工作能力更加强，于是当每个蚂蚁 进行若干次搜索后，他们会进行遗传运算，这里主要从几个方面考虑，随机对 1 3 蚂蚁进行了交叉运算，交叉运算采用了二次搜索互为引导方法，使得交叉运 算能够充分保证不丢失最优解的可能性，随机对1 3 蚂蚁进行变异运算，变异分 随机自由变异和受强壮的种子蚂蚁影响而进行诱导性变异，剩下1 3 蚂蚁默认为 是进行了遗传运算；( 4 ) 每个蚂蚁都会有简单的记忆，在进行搜索时会适当参考 上次经过的路线，进行智能化学习；( 5 ) 在程序实现上使用多线进程，让所有蚂 蚁真正同步工作，并行搜索，即时动态更新路线上的信息素。同时动态的更新蚂 蚁的各个参数指标，动态改变转移概率中的q 和1 3 的比例关系，使得蚂蚁性能多 样化，尽可能的找到( 次) 最优解。在基本遗传算法的基础上有三个方面的改进： ( 1 ) 交叉运算主要用在蚂蚁身上，和蚂蚁搜索的结果上，而不是对所求得最终 结果进行操作；( 2 ) 变异采用自身随机变异和诱导性变异；( 3 ) 无论对哪个对象 进行遗传算子，都没有进行重新编码，而是直接运用遗传原理对蚂蚁的性能和搜 索结果进行了调整，使得程序的实现更加简单化。 本论文把遗传算法移植到蚁群算法内部，对蚁群算法的改进突出放在对蚂蚁 本身进行遗传操作，通过遗传操作使得蚂蚁性能得到进化，并提出系统，让蚂蚁 6 硕士学位论文第一章绪论 系统模拟人类社会去找最优解，这种改进不但使算法本身整体性能得到提高，而 且使得算法既吸收了遗传算法优点，避免收敛过快的缺点，又保证了算法运行时 间复杂度不因遗传算法而增加。另外本文还对制冷机组改造系统进行了硬软件 方面介绍和分析，在附加理想的条件下去分析制冷机组改造系统节能函数模型建 立和分析，从而运用蚁群遗传混合算法对系统模型算法进行了优化和仿真分析。 1 4 2 重难点解决的问题 机组最优组合分配问题是寻求一个周期内各个负荷水平下机组的最优组合 分配方式及开停机计划，使运行费用最小，它是一个高维数、非凸的、非线性的、 离散的优化问题，很难找出理论上的最优解。因此，本文的难点在于： 虽然蚁群算法具有强的鲁棒性和易干并行实现的优点。但是这种算法也存在 一定的缺陷，如搜索时间比较长，会容易出现停滞现象。即搜索到一定程度之后， 所有个体发现的解完全一致，不能对解空间进一步进行搜索，会容易限入局部最 优解。因此难点之一就是用遗传算法对基本蚁群算法进行改进。 由于制冷机组组合分配问题是一个复杂的、多约束优化问题，各种约束之间 相互影响，相互制约。本文的难点之一就是编程时如何合理正确的处理各种约束 的关系。 本文最后用遗传优化蚁群算法仿真求解制冷机组组合优化问题。并用验证改 进蚁群算法的性能。 7 硕士学位论文第2 章蚁群算法和遗传算法的原理与分析 第2 章蚁群算法和遗传算法的原理与分析 2 1 蚁群算法原理及其研究 蚂蚁是一种既渺小而又平常的社会性昆虫，单只蚂蚁的能力和智力是非常简 单，但它们通过相互协调、分工、合作却能表现出极为复杂的行为，能够完成复 杂的任务。比如蚂蚁在觅食过程中能够通过释放一种信息素来相互协作找到食物 源和巢穴之间的最短路径。不仅如此，蚂蚁还能够适应环境的变化，如t 在蚂蚁 运动路线上突然出现障碍物时，蚂蚁能够很快重新找到最优路径，这种任务的完 成同样归因于蚂蚁个体之间释放的信息素。蚂蚁之所以表现出复杂有序的行为， 个体之间的信息交流和相互协作起着重要的作用。 意大利m d o r i g o ，v m a n i e z z o ，a c o l o m i 等人从蚂蚁觅食的过程中受到启发， 经过大量的观察和实验发现，蚂蚁在觅食过程中留下了一种外激素，又叫信息激 素，它是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物的时候会在经过的路上留下 这种物质，以便在回巢时不会迷路，而且方便找到回巢的最好路径。由此， m d o r i g o 等人首先提出了一种新的启发式优化算法，又叫蚁群系统( a n tc o l o n y s y s t e m 1 6 】) ，m d o r i g o 用蚁群算法来解决计算机算法学中经典的“货郎担问题”。 如果有n 个城市，需要对所有n 个城市进行访问且只访问一次的最短距离。在解决 货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁 将摸索不同路线，并留下会随 时间逐渐消失的虚拟“信息素 【1 7 l 。虚拟的“信息素”也会挥发，每只蚂蚁每 次都随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较多的路径。 根据“信息素较多的路线更近“的原则，即可选择出最佳路线。 蚁群算法的主要特点是：正反馈、分布式计算，与某种启发式算法相结合， 正反馈过程使得该方法能够很快发现较好合理的解；分布式易于并行实现，与启 发式算法相结合，使得该方法易于发现较好合理的解【i 引。初步的研究表明，蚁 群算法是一种基于种群的鲁棒性较强的算法，具有许多优良的性质，为求解复杂 的组合优化问题提供了一种新思路。 2 1 1 基本蚁群算法 1 、蚁群算法原理 蚂蚁在到外面寻找食物的工作中，会不断地在走过的地方上会释放一种信息 激素方便能够和其他的蚂蚁取得联系，这类信息激素的浓度会随着走过该地方上 的蚂蚁数量多少而增加，并且蚂蚁在返回巢或寻找食物时也会选择信息激素浓度 8 硕士学位论文 第2 章蚁群算法和遗传算法的原理与分析 较大的地方，这就会使得有更多的蚂蚁去选择该地方，这种现象就称为一种正反 馈机制。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的几率就越 大。为了区别于真实蚂蚁群体系统，称这种算法为“人工蚁群算法0 9 1 ，蚂蚁 这类群居性昆虫，虽然单个蚂蚁的行为极简单。但由这样的单个简单的个体所组 成的蚁群群体却会表现出极为复杂的行为，能够完成复杂的任务，而且，蚂蚁还 能够适应环境的变化【2 0 】。 下面详细说明蚁群中的这些简单规则： l 、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径 ( 一般是3 ) ，那么它能观察到的范围就是3 * 3 个方格世界，并且能够移动的距 离也会在这个范围之内。 2 、环境：蚂蚁所在的环境是一个虚拟的世界，其中会有障碍物，有别的蚂 蚁，还有外激素，外激素有两种，一种是找到了食物的蚂蚁洒下的食物外激素， 一种是找到了窝的蚂蚁洒下的窝的外激素。每个蚂蚁都仅仅能感知它范围内的环 。 境信息。环境以一定的速率让外激素消失。 3 、觅食规则：在每只蚂蚁能感知的范围内去寻找是否有食物，如果有就会 直接过去。否则看是否有外激素，并且比较在能感知的范围内哪一点的外激素最 多，这样，它就朝外激素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而 并不是往外激素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的外 激素做出反应，而对食物外激素没反应。 4 、移动规则：每只蚂蚁都朝向外激素最多的方向移，并且，当周围没有外 激素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运 动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过 了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 5 、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一 个方向，并且有外激素指引的话，它会按照觅食的规则行为。 6 、播撒外激素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的外激素最 多，并随着它走远的距离，播撒的外激素越来越少。 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生 交互，而通过外激素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一 只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒外 激素，当其它的蚂蚁经过它附近的时候，就会感觉到外激素的存在，进而根据外 激素的指引找到了食物。成功的觅食算法正是最小化搜索食物的时间。 蚁群算法的自组织能力机制使得蚁群算法不需要对所求问题的每一方面都 有非常详尽的认识，可以使得蚁群算法在没有外界作用情况下实现了从无序到有 9 硕士学位论文第2 章蚁群算法和遗传算法的原理与分析 序的动态演化，其的逻辑结构如图2 1 所示。 图2 1 蚁群算法的逻辑结构 由上图2 1 可见，先将具体的组合分配优化问题表述成规范的格式，然后利 用蚁群算法在“探索( e x p l o r a t i o n ) 和“利用( e x p l o i t a t i o n ) 之间根据信息素这一 反馈体来决定决策点，同时必须按照相应的信息素更新规则对每个蚂蚁个体的信 息素进行了增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始， 即可求出组合分配优化问题的最优解。 2 、蚁群算法的实现 大家都知道，蚁群算法最成功的就是运用在t s p 问题上，现在就对该问题 简单的介绍一下，如何实现标准蚁群算法。旅行商问题的简单形象描述是：给定 n 个城市，有一个旅行商从某一城市出发，访问各城市一次并且仅有一次后返回 原出发城市，要求找出一条最短的巡回路线。其图论描述为：给定图g = ( v ，a ) ， 其中v 为顶点集，a 为各顶点相互连接组成的边集，己知各顶点间的连接距离， 要求确定一条长度最短的h a m i l t o n 回路，即遍历所有顶点当且仅当一次的最短 回路。 定义2 1t s p 设c = c l ，c 2 ，e 是n 个城市的集合，= 乇l q , c j c 是集 合c 中元素( 城市) 两两连接的集合，d 。( f ，j = l ，2 ，刀) 是z ，的e u c l i d e a n 距离， l o 硕士学位论文第2 章蚁群算法和遗传算法的原理与分析 即 d g = 厄i 再而 ( 2 - 1 ) g = ( c ，l ) 是一个有向图，t s p 的目的是从有向图g 中寻出长度最短的 h a m i l t o n 圈，此即一条对c = c l ，g ，e ) 中n 个元素( 城市) 访问且只访问一次的 设6 i ( ，) 表示t 时刻位于城市i 的蚂蚁个数所= 6 j ( f ) 。乃( f ) 表示在t 时刻城 筋_ j 一 a p 闾脚啵协2 ， p ；2 ，口f 胁w p d 七j ，f r ( 于) 托 ( 2 2 ) 其中，a l l o w e d - - o ，1 ，n - 1 - t a b u 。表示蚂蚁k 下一步允许走过的城市的集 合。与真实蚁群不同，人工蚁群系统具有记忆功能，t a b u 。( 后= 1 ，2 ，m ) 用以记 录蚂蚁k 当前所走过的城市，集合t a b u 。随着进化过程作动态调整。a 表示路径 上的信息量对蚂蚁选择路径所起的作用大小，仍，为由城市i 转移到城市j 的期望 程度，例如，可以取嘞= ，表示的作用。当口= o 时，算法就是传统的 贪心算法；而当= 0 时，就成了纯粹的正反馈的启发式算法。经过n 个时刻， 蚂蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此 时，要根据下式对各路径上的信息量作更新： t o ( t + 1 ) = ( 1 一p ) 勺 ) + ， ( 2 - 3 ) 其中p ( o ，1 ) 为蒸发因子，因为随着时间的推移，路径上以前留下的信息将 逐渐消逝，用参数p 表示信息量靠( f ) 随时间的推移而衰减的程度。信息增量r u ( t ) 可表示为： 硕士学位论文第2 章蚁群算法和遗传算法的原理与分析 = k = l ( 2 4 ) t ，表示蚂蚁k 在本次循环中在城市i 和j 之间留下的信息量，它的计算公式 根据计算模型而定，例如在最常用的a n tc i r c l es y s t e m 模型中 a t ：q e若蚂蚁经过磬市i 和城市j 之间( 2 - 5 ) 9 10否则 其中，q 为常数，f 为蚂蚁k 在本次循环中所走路径的长度。在经过若干次循 环以后，可以根据适当的停止条件来结束计算。根据具体算法的不同，t i ( f ) ，f “ 及嘭( f ) 的表达形式可以不同，要根据具体问题而定。m d o r i g o 曾给出3 种不同模 型，分别称之为a n t - c y c l es 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 ，它 们的差别在于公式( 3 4 ) 的不同。在a n t q u a n t i t ys y s t e m d g ： 叫孑耦蚁篙莉和炳拥 协6 ， 在a n t - d e n s i t ys y s t e m 中： 硝= 孑耦蚣过臀娴加 协7 ， 它们的区别在于后两种模型中利用的是局部信息，而前者解t s p 问题时性能较 好。因而我们采用前者为基本模型。 2 1 2 蚁群算法的拓展 蚁群算法是一种起源于模拟自然晃中生物的仿生类进化算法，在对求解复杂 组合优化问题方面有如下的优势：较强的鲁棒性，对蚁群算法模型稍加改动，便 可以应用于其他问题；分布式计算，蚁群算法是一种基于种群的进化算法，具有 良好并行性；蚁群算法易于与其他启发式算法结合，从而改善算法的性能。但是 蚁群算法的研究才刚起步，不像g a ，s a 等启发式算法那样已有系统的分析方法和 坚实的数学基础。因此参数的选择依靠更多实验和经验，且计算时间长，容易出 现早熟和停滞现象。为此，学者们就提出了一种动态更新信息素的自适应蚁群算 法【2 l 】，实验表明，改进的蚁群算法具有比传统蚁群算法和m m a s 蚁群算法更强的 搜索全局最优解的能力，并具有更好的稳定性和收敛性。自适应蚁群算法作为一 种新型的生物进化算法，目前还没有遗传算法、模拟退火等那样形成较系统的分 1 2 硕士学位论文 第2 章蚁群算法和遗传算法的原理与分析 析方法和坚实的数学基础，各种参数的确定也没有一定的理论指导f 2 羽，相信随 着蚁群算法分析研究的不断深入，自适应蚁群算法在d n a 的应用对中的应用取得 了较好的效果，而动态自适应调整信息素的改进算法可以明显地提高蚁群算法的 寻优能力。相信经过进一步研究，自适应蚁群算法在求解人类基因的问题中的应 用前景会更广阔。自适应蚁群算法也将会同其他生物进化算法一样获得越来越广 泛的应用和坚实的理论根据。 2 1 3 蚁群算法小结 1 、基本蚁群算法的优点 ( 1 ) 较强的鲁棒性，对该算法模型稍加修改，便可以应用于其它问题，蚂 蚁算法对初始路线要求不高，即蚂蚁算法的求解结果依赖于初始路线的选择，而 且在搜索过程中不需要进行人工的调整，其次，蚂蚁算法的参数数目少，设置简 单，易于蚂蚁算法应用到其它组合优化问题的求解； ( 2 ) 分布式计算，该算法是一种基于种群的拟生态系统算法，具有本质并 行性，易于并行实现； ( 3 ) 易于与其它方法结合，该算法很容易与多种启发式算法结合，以改善 算法的性能； ( 4 ) 蚁群算法是一种本质上并行的算法，每只蚂蚁搜索的过程彼此独立， 仅通过信息激素进行通信。它在问题空间的多点同时开始进行独立的解搜索，不 仅增加了算法的可靠性，也使得算法具有较强大的全局搜索能力。 2 、基本蚁群算法的缺点 ( 1 ) 需要较长的计算时间，容易出现停滞现象。蚂蚁中各个体的运动是随 机的，虽然通过信息激素交换能够向着最优路径进化，但是当群体规模较大时， 很难在较短时间内从大量杂乱无章的路径中找到一条较好的路径； ( 2 ) 所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增 量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引 导信息，从而造成大量的无效搜索，使系统出现停滞现象； ( 3 ) 采用了信息素均匀分配策略，即对己搜索路径中的所有路段采用同样 的信息素增量，与路段的重要性无关，没有考虑当连续空间优化问题转换到有向 图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的 影响。 众多研究已经证明了蚁群算法具有很强的发现较好解的能力，这是因为该算 法不仅利用了正反馈原理，在一定程度上可加快进化过程，而且是一种本质并行 1 3 硕士学位论文第2 章蚁群算法和遗传算法的原理与分析 的算法，在不同个体之间不断进行信息交流和传递，从而能够相互协作，有利于 发现较好优化解，蚁群算法可以解释为一种特殊的强化学习算法f 2 3 j 【2 4 j 【2 5 1 。蚁群 算法与q _ 学习算法之间的联系。其中，信息素相当于学习中的q 值，表示学习所 得到的经验。由某种启发式算法确定，如何将这两者结合起来，是提高蚁群算法 效率的关键。虽然蚁群算法有许多优点，但是，这种算法也存在一些缺陷，如： 与其它方法相比，该算法一般需要较长的搜索时间，蚁群算法的复杂度可以反映 这一点；而且该方法容易出现停滞现象。即搜索进行到一定程度后，所有个体所 发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。 2 2 遗传算法原理及其研究 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 由美国j h h o l l a n d 博士1 9 7 5 年提出【2 6 1 ，当时并没有能够在学术界中引起关注，因而发展比较缓慢。从8 0 年 代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法也就逐步成熟， 并且应用日渐增多，不仅应用于人工智能领域( 如机器学习和神经网络) ，也开 始在工业系统，如控制、土木、机械、电力工程中得到了成功应用，显示出了诱 人可观的前景。它是人工智能的重要新分支，是基于达尔文进化论，在计算机上 模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然 进化规则来进行搜索计算和问题优化求解。 遗传算法( g e n e t i ca l g o r i t h m s ) 是基于生物进化理论的原理发展起来的一 种广为应用的、高效的随机搜索与优化的方法【2 7 】。其主要特点是群体搜索策略 和在群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在7 0 年代初期 由美国密执根( m i c h i g a n ) 大学的霍兰( h o l l a n d ) 教授发展起来的。1 9 7 5 年霍 兰教授发表了第一本比较系统论述了遗传算法【2 8 】的专著自然系统与人工系统 中的适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) 。遗传 算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、 进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。 迄今为止，遗传算法是进化算法中最广为人知的算法。 近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取 得了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、 进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与 排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问 题等等。 1 4 硕士学位论文 第2 章蚁群算法和遗传算法的原理与分析 2 2 1 基本遗传算法 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来 了解一下什么是遗传算法。遗传算法( g e n e t i ca l g o r i t h m s ，以下简称g a ) 是 基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。 g a 贝t j 模拟了上述进化现象。它把搜索空间( 欲求解问题的解空间) 映射为遗 传空间，即把每一个可能的解编码为一个向量( - - 进制或十进制数字串) ，称为 一个染色体( c h r o m o s o m e ，或个体) 1 2 9 ，向量的每一个元素称为基因( g e n e s ) 。 所有染色体组成群体( p o p u l a t i o n ，或集团) 。并按预定的目标函数( 或某种评 价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等) 对每个染 色提进行评价，根据其结果给出一个适应度的值。 l 、遗传算法的运行机理 在利用进化算法求解优化问题时，首先需要随机生成包含一定数量个体的初 始种群，其中的每一个个体都代表问题的一个可行解；然后根据问题评价这些可 行解的优劣，并赋以相应的适应度值；再根据适应度值，按照较好的个体对应较 大的生存空间的指导原则，引入具有一定随机性的遗传操作，生成下一代的新种 群；然后重复上述过程直至满足运行终止条件【3 0 1 。 算法开始时先随机地产生一些染色体( 欲求解问题的侯选解) ，计算其适应度， 根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低( 性能 不佳) 的染色体，留下适应度高( 性能优良) 的染色体，从而得到新的群体。 2 、g a 通常包含六个基本要素