多台制冷机组控制系统研究及优化

分类号U D 业研究生姓名导师姓名及专I呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。作者签名：埤 日期：业年上月型日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：婢导师签名盟日期：业年上月旦日摘要本文针对现有多台制冷机组单独供冷量，智能化控制程度低，管理难度大，水泵不能调速或者控制水平低，能耗大，难以满足生产要求的现状，设计开发了多台制冷机组控制系统，可适用于工厂制冷系统，选题紧密结合实际，具有重要的实际应用价值。本文以多台制冷机组为研究对象，对多台制冷机组控制系统设计方案和数学优化调度模型进行了重点研究。针对多台制冷机组控制系统的需求，结合西门子文将多台制冷机组控制系统分为二层：楼下监控管理层、屋顶现场监控层进行实现。结合叙了多台制冷机组控制系统的硬件和软件具体实现框图，给出了系统总体结构图和关键程序实现，在实际的工程应用中，本系统很好的完成了控制任务，取得很好的控制效果。在多台制冷机组动态调节建模原理基础上，通过用遗传优化蚁群算法和常规的梯度调度对模型进行了软件编程仿真结果表明，该方法能较好的满足实际生产需求。关键词：频调速，优化蚁群算法，制冷机组调度of to or of of O，to of n of or PI be is to LC of of is to in to n on of of a LC，论文选题的背景和意义目前研究现状1121目前算法和多台联合机组运行研究现状2。 122对算法目前研究的评价313论文的总体思路及研究方法5131总体思路5132研究方法一514论文的主要工作6141论文的主要工作6142重难点解决的问题7第2章蚁群算法和遗传算法的原理与分析821蚁群算法原理及其研究8211基本蚁群算法8212蚁群算法的拓展：12213蚁群算法小结1322遗传算法原理及其研究14221基本遗传算法l 5222遗传算法的拓展l 7223遗传算法小结18第3章遗传蚂蚁混合算法1 931优化算法的背景及思想19311算法的背景l 9312混合算法的优化思想1932优化算法的数学模型及其实现：20321算法的数学模型20322算法的实例研究实现23323算法的复杂度分析26第4章多台制冷机组控制系统研究2841引言2842制冷机组控制系统研究及方案28421控制系统研究28422系统研究方案及意义2943系统总体设计与控制网络结构。30431系统总体控制设计30432控制网络结构3444系统功能分析36第5章基于遗传蚁群混合算法的多台制冷机组优化调度3851引言3852节能运行控制模型。3853基于混合算法的多台制冷机组优化调度4454混合算法收敛性分析5 53参考文献54致谢58攻读硕士学位期间科研及论文完成情况59一章绪论11论文选题的背景和意义第一章绪论弗一早殖记组合调度优化问题【l 组、次序或筛选等等，是运筹学的一个经典且重要的分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域。组合调度最优化问题，就是在给定约束条件下，求出使目标函数极小(或极大)变量的组合调度能量分配问题。解决组合调度优化问题主要使用了优化方法，所谓优化方法，其实就是一种搜索的过程和方法规则，它是基于某种思想和机制，通过一定的途径或方法规则来得到满足用户要求的问题的解121。智能优化方法是一种重要的优化方法，是一个近几年来发展起来的非常活跃的研究领域。智能优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。智能优化技术作为一个重要的科学分支一直受到人们的广泛重视，并在很多工程领域中得到迅速推广和应用，如系统工程、管理工程、计算机、自动化、采矿、机械等许多领域，遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法和粒子群优化算法等，在国民经济的各个行业中都获得了广泛的应用【3】。制冷机组组合调度分配问题是制冷系统经济调度的一个很重要的环节，制冷机组组合调度的基本任务是在满足负荷平衡、系统安全约束、机组特性约束等条件下，经济、合理地安排机组次日的调度计划曲线。狭义地讲，制冷机组组合调度问题是指在满足负荷平衡和系统约束前提下，以系统运行费用最小化为目标来确定制冷机组的开停方案。经济功率分配是以整个系统消耗功率的费用最小为目标决定制冷机组的那些机组启停，广义的制冷机组组合调度问题包含经济功率分配本文除特别指明外，制冷机组组合调度均为广义概念。蚁群算法是一种新兴的用于解决组合调度最优化问题的高效的内启发式搜索技术，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合的特点，目前已经在许多优化问题中得到了成功应用。12目前研究现状本论文是运用蚁群算法、遗传算法研究制冷机组组合调度能量分配问题，涉及主要核心内容是进化计算原理思想和多台制冷机组模型分析及优化，进化计算硕士学位论文 第一章绪论(称是最近四十年来兴起的、受到生物进化思想启发而在学术界产生的一类新型优化算法的统称，它既是一种模仿生物进化过程的优化方法，也是属于模仿人的智能优化的范畴。进化计算采用了简单的编码技术来表示各种复杂的结构，并通过简单的遗传操作和优胜劣汰的自然选择来指导性学习和确定搜索的方向。进化计算有自组织、自适应、自学习的特点，而且不受到其搜索空间限制性条件(如可微、单峰等)的约束，不需要其他辅助信息(如导数)【4】。这使得进化计算不仅能得到较高的效率，而且简单、通用性好。它的三大分支主要包括：遗传算法(进化规划(进化策略(这三大分支在算法实现方面具有一定细微的差别，但它们具有一个共同的特点，即都是借助生物进化的思想和原理来很好地解决实际问题。另外，本文还还涉及制冷机组改造系统软硬件设计方面介绍，并阐述了系统改造后的优越性。在假设的理想条件下建立了系统算法模型，并运用优化算法对其进行了仿真分析得出结论。 1目前算法和多台联合机组运行研究现状1、蚁群算法和遗传算法目前研究现状最近几年，蚁群算法得到了不断的发展、改进和完善，并且进一步了验证了些改进了的51算法都是更加增强了蚂蚁搜索过程中对最优解的搜寻能力，只是搜索控制策略有所不同。这种算法求解-题的能力比遗传算法和模拟退火算法具有显著的优势。吴庆洪教授等【6】从遗传算法中变异算子的作用得到了启发，在蚁群算法中采用了逆转变异机制，进而提出了一种具有变异性能的蚁群算法。最近几年来，众多研究学者把格划分、自适应、网络规划等思想融合到蚁群算法中，基本上去改进和完善蚁群算法局部参数，获得了一定可观的结果。比较典型的应用研究包括：数据挖掘、网络路由优化以及一些经典的组合优化问题，目前这方面的应用研究越来越受到重视。近年来，随着对于遗传算法【7】研究的不断深入，有越来越多的人认识会了解了遗传算法，并将它应用到越来越广泛的领域。将遗传算法用于解决各种实际问题后，人们在实际运用中发现遗传算法也会由于各种原因过早向目标函数的局部最优解收敛，从而很难找到目录函数的全局最优解。其中有些是因目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是因算法设计不准确。为此，不断有人对遗传算法提出各式各样的改进方案。例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对2硕士学位论文 第一章绪论关于按比例的选择机制，提出了竞争选择、连续挑选等改进方案；针对原先设计的一点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中一些不变的情况，提出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。2、多台制冷机组联合运行研究现状从上个世纪90年代开始以来，中国资源方面形势日益严峻。制冷系统行业的迅速发展产生了巨大的能量损耗，相应地也给环境造成严重的污染问题。从节能减排出发，研究了通过制定中国制冷系统能效标准来逐渐控制和降低资源消耗。让制冷机组系统利用最小的能量损耗，而得到较多的制冷量，在国内外的专家学者们经过多年来无数次的不断探索，研究制冷机组运行及多台联合运作节能众多新技术，使制冷系统行业不断地向前发展【8】。国际上制冷机组系统的计算机仿真实验研究开始于20世纪70年代末，而在国内，当从陈芝久教授提出“制冷系统热动力学的看法之后，已经有不少研究学者投身于制冷机组系统仿真的分析研究，并且取得了大量的令人瞩目节能成效。制冷机组系统实验仿真技术进行到现在，历经了从单个部件模型分析到整体系统模型分析研究，从稳态的、集中的各个参数模型发展到动态的、分布式的各个参数模型分析研究，从瞬态状态到长时间工作过程的实验仿真研究。研究制冷机组组合优化分配运行的控制问题时，需要按照以下几个原则【9】求解：(1)整体性原则；(2)最优化原则；(3)模型化原则；(4)动态原则，因此对于制冷机组控制系统的实例仿真和优化，动态数学模型才会更具有更加直观的意义。然而，当前绝大多数智能化控制算法仍只是以制冷机组系统的单台机组作为被控制对象进行智能控制。要使制冷机组系统的组合分配控制策略和智能化控制算法真正相融合起来，这样有必要分析研究制冷机组系统的变量智能控制算法。目前对制冷机组系统变量分配控制问题投入研究还是比较少。从节能技术方面却具有巨大的应用研究发展前景，所以也就成为当前研究的重要课题之一。122对算法目前研究的评价1、对蚁群算法目前研究的评价蚁群算法凭借其突出的问题和简单的算法结构求解能力，以及稳定、灵活、自组织能力和分布式控制等特点，吸引了很多研究者，并取得了令人注目的成果。该理论特别适合于工程问题112】中日益复杂的信息处理需求，尤其是那些动态特性突出的问题。然而，由于其理论依据源自于对生物群落社会性的可模拟性，因此其相关数学分析还较薄弱，这就导致了现有研究还存在以下几个主要重要的问题：3硕士学位论文 第一章绪论(1)蚁群算法的数学理论基础薄弱，缺乏普遍意义的理论性分析。算法中涉及的参数设置没能够有确切的理沦依据，一般按照经验来确定，对具体问题的依赖性较大；(2)比较性研究不足，与各种成熟的优化算法之间的基本特性及性能特点的对比研究还不是十分充分。将来的研究工作应加强算法特性的分析，进一步明确与算法原理相关的重要意义，如：单个个体的复杂性、学习能力和推理能力等。还应扩展蚁群算法与其他算法如神经网络、禁忌搜索和支持向量机等先进技术的混合，以改善其自身的性能。作为一种新型的模拟进化算法，蚁群算法研究时间较短，不像其他启发式算法那样具有系统的分析方法和坚实的数学理论。挥发因子等参数【l 3】的选择基本是依靠实验和经验，目前尚无通用及确定的理论方法去确定，因此理论和实践方面尚有许多问题需要更待深人的研究与探讨，但是该算法的并行特性和强鲁棒性等优点吸引着许多学者不断对其进行深入研究。随着理论研究和实践经验的积累，蚁群算法必将成为求解复杂组合优化同题的高效算法。对蚁群算法的很多方面有待完善，需要加强并进行深入研究：(1)加强对蚁群算法数学理论模型基础和系统分析方法的研究目前各种改进的蚁群算法的收敛性、有效性、通用性，参数的设定主要根据大量实验的统计结果，没有很成熟的理论和系统的分析方法作指导，算法模型也有待更进一步深入研究，这些问题就限制了蚁群算法的推广应用及蚁群算法的改进与完善；(2)加强蚁群算法各种改进方法的综合研究目前的研究主要针对蚁群算法不同的部分做修改，因而算法各个参数的相互作用、最优配置，各种方法的综合使用及各种改进方法的相互作用是以后研究的重点之一；(3)加强蚁群算法与其他算法的混合蚁群算法具有很强的藕合性，易与其他进化算法或者局部搜索算法结合，将蚁群算法与神经网络、遗传算法、模拟退火算法等相混合，必将成为今后蚁群算法新的研究热点；(4)加强蚁群算法与应用的结合，尽管蚁群算法在众多领域得到了推广，但大多数研究者仅局限于仿真试验和思想的引入，充分挖掘蚁群算法在实际应用中的潜力，对现有应用领域进行深化研究的同时，进一步扩大其应用范围具有重要意义；(5)改进算法在连续优化问题中的性能研究，4】研究了求解连续空间优化问题的蚁群系统模型，并用来解决某些实际工程设计问题，但是蚁群算法在求解连续优化问题方面的优越性相对要弱一些，而实际工程应用中存在着许多此类问题，如不能将蚁群算法应用于求解连续优化问题，将会束缚蚁群算法在其他研究领域的应用。2、对遗传算法目前研究的评价4硕士学位论文 第一章绪论遗传算法具有很强的全局搜索能力，并且这种搜索能力不依赖于特定的求解模型。但是直接应用简单遗传算法来解决优化问题，算法性能可能不尽人意。要设计出有效的遗传算法，必须尽可能地应用特定问题域的知识，或是结合局部寻优的方法，设计收敛速度较快的混合遗传算法。根据有限状态齐次马尔可夫链方法，可以证明某些算法是以概率1收敛至全局最优点的。然而，实验表明，当规模较大时，算法常常会产生早熟现象，即过早地收敛于局部极小点的现象，问题的规模越大，早熟越容易发生。虽然某些算法在理论上是以概率1收敛至全局最优的，但是这种收敛性是由变异过程中概率转移矩阵的互通性保证的，而通常变异概率是很小的；当算法出现早熟现象时，仅仅依靠变异操作仍然很难从局部最优点跳出，遗传算法从初始状态到全局最优点的收敛时间的平均期望可能大大超过我们的预期。因此，好的遗传算法应当兼顾局部收敛性能和全局收敛性能【l 51。13论文的总体思路及研究方法131总体思路本论文总体思路可以概括为：“立足好一个中心，把握好两个基本，做好三个结合”。所谓“立足一个中心就是立足于蚁群算法，从基本上对蚁群算法进行展开研究，深刻分析研究基本蚁群算法的工作原理，以基本蚁群算法为中心进行改进及提高，做出一个更真实更智能化的蚁群系统。所谓“把握两个基本就是把握遗传算法的基本原理和制冷机组组合调度优化问题。所谓“做好三个结合就是(1)将遗传算法和蚁群算法相结合起来，构造出智能化混合算法：(2)将遗传蚂蚁混合算法和制冷机组组合调度起来，使得遗传蚂蚁算法得以应用；(3)将遗传蚂蚁算法运行结果和传统的制冷机组组合调度算法运行结果结合起来进行比较分析，最后得出一个结论。132研究方法本论文是从整体上着眼，从局部着手，逐个分析，综合分析研究运用。按照“总体规划、局部突破、先破后立、综合归纳”的方法进行论述。通过整体规划制定出一条综述思路来，通过局部突破，使得蚁群、遗传算法的性能上都能提高，通过逐个分析、先破后立把蚁群算法、遗传算法混合在一起，得出一个改进的遗传蚂蚁混合算法，然后将遗传蚂蚁算法运用在制冷机组组合调度实例之中，通过综合归纳，总结遗传蚂蚁算法。5硕士学位论文 第一章绪论14论文的主要工作141论文的主要工作基本文就是利用机组最优启停能量分配问题与试把机组最优启停能量分配问题设计成类似于灵活地处理各种约束，从而可以用外对基本蚁群算法局部进行了优化和完善，本文运用蚁群算法和遗传算法的相结合及综合分析制冷机组合，和以往应用相比，在基本蚁群算法上主要有五个方面改进：(1)每个蚂蚁在进行一次搜索回到本部后，和其相邻伙伴交流信息，进行智能化学习；(2)当蚂蚁进行数次搜索后，可以自由结合成为群体(群)，群的信息量能够更加丰富，指导搜索能力能够更加强。这里的群是一个虚拟的团体，其行为对单个蚂蚁有一定的指导和参考意义。每个群对其成员并没有绝对的控制行为，即每个蚂蚁无论是否加入一个群里，都会令其保持自身的独立性。在这里组建群的原则是：性格(参数)相同的蚂蚁结合为一个群，强强相联合而结合为一个群，弱弱相联合而结合为一个群，强者帮助带弱者结合为一个群，随机调集一些蚂蚁进行联合结合为一个群；(3)由于蚂蚁是一个生物体，受到遗传作用，他们的后代可能要比父辈们更有智能化，工作能力更加强，于是当每个蚂蚁进行若干次搜索后，他们会进行遗传运算，这里主要从几个方面考虑，随机对13蚂蚁进行了交叉运算，交叉运算采用了二次搜索互为引导方法，使得交叉运算能够充分保证不丢失最优解的可能性，随机对13蚂蚁进行变异运算，变异分随机自由变异和受强壮的种子蚂蚁影响而进行诱导性变异，剩下13蚂蚁默认为是进行了遗传运算；(4)每个蚂蚁都会有简单的记忆，在进行搜索时会适当参考上次经过的路线，进行智能化学习；(5)在程序实现上使用多线进程，让所有蚂蚁真正同步工作，并行搜索，即时动态更新路线上的信息素。同时动态的更新蚂蚁的各个参数指标，动态改变转移概率中的得蚂蚁性能多样化，尽可能的找到(次)最优解。在基本遗传算法的基础上有三个方面的改进：(1)交叉运算主要用在蚂蚁身上，和蚂蚁搜索的结果上，而不是对所求得最终结果进行操作；(2)变异采用自身随机变异和诱导性变异；(3)无论对哪个对象进行遗传算子，都没有进行重新编码，而是直接运用遗传原理对蚂蚁的性能和搜索结果进行了调整，使得程序的实现更加简单化。本论文把遗传算法移植到蚁群算法内部，对蚁群算法的改进突出放在对蚂蚁本身进行遗传操作，通过遗传操作使得蚂蚁性能得到进化，并提出系统，让蚂蚁6硕士学位论文 第一章绪论系统模拟人类社会去找最优解，这种改进不但使算法本身整体性能得到提高，而且使得算法既吸收了遗传算法优点，避免收敛过快的缺点，又保证了算法运行时间复杂度不因遗传算法而增加。 另外本文还对制冷机组改造系统进行了硬软件方面介绍和分析，在附加理想的条件下去分析制冷机组改造系统节能函数模型建立和分析，从而运用蚁群遗传混合算法对系统模型算法进行了优化和仿真分析。142重难点解决的问题机组最优组合分配问题是寻求一个周期内各个负荷水平下机组的最优组合分配方式及开停机计划，使运行费用最小，它是一个高维数、非凸的、非线性的、离散的优化问题，很难找出理论上的最优解。因此，本文的难点在于：虽然蚁群算法具有强的鲁棒性和易干并行实现的优点。但是这种算法也存在一定的缺陷，如搜索时间比较长，会容易出现停滞现象。即搜索到一定程度之后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，会容易限入局部最优解。因此难点之一就是用遗传算法对基本蚁群算法进行改进。由于制冷机组组合分配问题是一个复杂的、多约束优化问题，各种约束之间相互影响，相互制约。本文的难点之一就是编程时如何合理正确的处理各种约束的关系。本文最后用遗传优化蚁群算法仿真求解制冷机组组合优化问题。并用验证改进蚁群算法的性能。7硕士学位论文 第2章蚁群算法和遗传算法的原理与分析第2章蚁群算法和遗传算法的原理与分析21蚁群算法原理及其研究蚂蚁是一种既渺小而又平常的社会性昆虫，单只蚂蚁的能力和智力是非常简单，但它们通过相互协调、分工、合作却能表现出极为复杂的行为，能够完成复杂的任务。比如蚂蚁在觅食过程中能够通过释放一种信息素来相互协作找到食物源和巢穴之间的最短路径。不仅如此，蚂蚁还能够适应环境的变化，如：在蚂蚁运动路线上突然出现障碍物时，蚂蚁能够很快重新找到最优路径，这种任务的完成同样归因于蚂蚁个体之间释放的信息素。蚂蚁之所以表现出复杂有序的行为，个体之间的信息交流和相互协作起着重要的作用。意大利M过大量的观察和实验发现，蚂蚁在觅食过程中留下了一种外激素，又叫信息激素，它是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物的时候会在经过的路上留下这种物质，以便在回巢时不会迷路，而且方便找到回巢的最好路径。由此，M叫蚁群系统(6】)，M郎担问题”。如果有要对所有解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素117l。虚拟的“信息素”也会挥发，每只蚂蚁每次都随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较多的路径。根据“信息素较多的路线更近“的原则，即可选择出最佳路线。蚁群算法的主要特点是：正反馈、分布式计算，与某种启发式算法相结合，正反馈过程使得该方法能够很快发现较好合理的解；分布式易于并行实现，与启发式算法相结合，使得该方法易于发现较好合理的解【步的研究表明，蚁群算法是一种基于种群的鲁棒性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一种新思路。211基本蚁群算法1、蚁群算法原理蚂蚁在到外面寻找食物的工作中，会不断地在走过的地方上会释放一种信息激素方便能够和其他的蚂蚁取得联系，这类信息激素的浓度会随着走过该地方上的蚂蚁数量多少而增加，并且蚂蚁在返回巢或寻找食物时也会选择信息激素浓度8硕士学位论文 第2章蚁群算法和遗传算法的原理与分析较大的地方，这就会使得有更多的蚂蚁去选择该地方，这种现象就称为一种正反馈机制。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的几率就越大。为了区别于真实蚂蚁群体系统，称这种算法为“人工蚁群算法【19l，蚂蚁这类群居性昆虫，虽然单个蚂蚁的行为极简单。但由这样的单个简单的个体所组成的蚁群群体却会表现出极为复杂的行为，能够完成复杂的任务，而且，蚂蚁还能够适应环境的变化120。下面详细说明蚁群中的这些简单规则：l、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径(一般是3)，那么它能观察到的范围就是3*3个方格世界，并且能够移动的距离也会在这个范围之内。2、环境：蚂蚁所在的环境是一个虚拟的世界，其中会有障碍物，有别的蚂蚁，还有外激素，外激素有两种，一种是找到了食物的蚂蚁洒下的食物外激素，一种是找到了窝的蚂蚁洒下的窝的外激素。每个蚂蚁都仅仅能感知它范围内的环。境信息。环境以一定的速率让外激素消失。3、觅食规则：在每只蚂蚁能感知的范围内去寻找是否有食物，如果有就会直接过去。否则看是否有外激素，并且比较在能感知的范围内哪一点的外激素最多，这样，它就朝外激素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往外激素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的外激素做出反应，而对食物外激素没反应。4、移动规则：每只蚂蚁都朝向外激素最多的方向移，并且，当周围没有外激素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有外激素指引的话，它会按照觅食的规则行为。6、播撒外激素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的外激素最多，并随着它走远的距离，播撒的外激素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过外激素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒外激素，当其它的蚂蚁经过它附近的时候，就会感觉到外激素的存在，进而根据外激素的指引找到了食物。成功的觅食算法正是最小化搜索食物的时间。蚁群算法的自组织能力机制使得蚁群算法不需要对所求问题的每一方面都有非常详尽的认识，可以使得蚁群算法在没有外界作用情况下实现了从无序到有9硕士学位论文 第2章蚁群算法和遗传算法的原理与分析序的动态演化，其的逻辑结构如图21所示。图21蚁群算法的逻辑结构由上图21可见，先将具体的组合分配优化问题表述成规范的格式，然后利用蚁群算法在“探索(和“利用(之间根据信息素这一反馈体来决定决策点，同时必须按照相应的信息素更新规则对每个蚂蚁个体的信息素进行了增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合分配优化问题的最优解。2、蚁群算法的实现大家都知道，蚁群算法最成功的就是运用在在就对该问题简单的介绍一下，如何实现标准蚁群算法。旅行商问题的简单形象描述是：给定一个旅行商从某一城市出发，访问各城市一次并且仅有一次后返回原出发城市，要求找出一条最短的巡回路线。其图论描述为：给定图G=(V，A)，其中为各顶点相互连接组成的边集，己知各顶点间的连接距离，要求确定一条长度最短的遍历所有顶点当且仅当一次的最短回路。定义21 2，e)是=乇C是集合市)两两连接的集合，d。(f，刀)是Z，的2章蚁群算法和遗传算法的原理与分析即 =(C，三)是一个有向图，即一条对c=Cl，G)中市)访问且只访问一次的设包(r)表示6f(f)。乃(f)表示在闾肋 肋(于)磋(力 J K (22)其中，o，1，示蚂蚁真实蚁群不同，人工蚁群系统具有记忆功能，k=1，2，m)用以记录蚂蚁合着进化过程作动态调整。，为由城市如，可以取嘞=，表示的作用。当口=法就是传统的贪心算法；而当=0时，就成了纯粹的正反馈的启发式算法。经过蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此时，要根据下式对各路径上的信息量作更新：t+1)=(1一p)勺(f)+勺 (23)其中P(O，1)为蒸发因子，因为随着时间的推移，路径上以前留下的信息将逐渐消逝，用参数f)随时I息增量ru(t)可表示为：硕士学位论文 第2章蚁群算法和遗传算法的原理与分析(24)，表示蚂蚁的计算公式根据计算模型而定，例如在最常用的t：Q 若蚂蚁经过磬市I O 否则其中，经过若干次循环以后，可以根据适当的停止条件来结束计算。根据具体算法的不同，f“及露(f)的表达形式可以不同，要根据具体f别称之为，它们的差别在于公式(34)的不同。在=6，在=宇耦眦过臀娴拥 协7，它们的区别在于后两种模型中利用的是局部信息，而前者解而我们采用前者为基本模型。212蚁群算法的拓展蚁群算法是一种起源于模拟自然界中生物的仿生类进化算法，在对求解复杂组合优化问题方面有如下的优势：较强的鲁棒性，对蚁群算法模型稍加改动，便可以应用于其他问题；分布式计算，蚁群算法是一种基于种群的进化算法，具有良好并行性；蚁群算法易于与其他启发式算法结合，从而改善算法的性能。但是蚁群算法的研究才刚起步，不像此参数的选择依靠更多实验和经验，且计算时间长，容易出现早熟和停滞现象。为此，学者们就提出了一种动态更新信息素的自适应蚁群算法【2l】，实验表明，改进的蚁群算法具有比传统蚁群算法和具有更好的稳定性和收敛性。自适应蚁群算法作为一种新型的生物进化算法，目前还没有遗传算法、模拟退火等那样形成较系统的分12硕士学位论文 第2章蚁群算法和遗传算法的原理与分析析方法和坚实的数学基础，各种参数的确定也没有一定的理论指导信随着蚁群算法分析研究的不断深入，自适应蚁群算法在动态自适应调整信息素的改进算法可以明显地提高蚁群算法的寻优能力。相信经过进一步研究，自适应蚁群算法在求解人类基因的问题中的应用前景会更广阔。自适应蚁群算法也将会同其他生物进化算法一样获得越来越广泛的应用和坚实的理论根据。213蚁群算法小结1、基本蚁群算法的优点(1)较强的鲁棒性，对该算法模型稍加修改，便可以应用于其它问题，蚂蚁算法对初始路线要求不高，即蚂蚁算法的求解结果依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整，其次，蚂蚁算法的参数数目少，设置简单，易于蚂蚁算法应用到其它组合优化问题的求解；(2)分布式计算，该算法是一种基于种群的拟生态系统算法，具有本质并行性，易于并行实现；(3)易于与其它方法结合，该算法很容易与多种启发式算法结合，以改善算法的性能；(4)蚁群算法是一种本质上并行的算法，每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强大的全局搜索能力。2、基本蚁群算法的缺点(1)需要较长的计算时间，容易出现停滞现象。蚂蚁中各个体的运动是随机的，虽然通过信息激素交换能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从大量杂乱无章的路径中找到一条较好的路径；(2)所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引导信息，从而造成大量的无效搜索，使系统出现停滞现象；(3)采用了信息素均匀分配策略，即对己搜索路径中的所有路段采用同样的信息素增量，与路段的重要性无关，没有考虑当连续空间优化问题转换到有向图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的影响。众多研究已经证明了蚁群算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可加快进化过程，而且是一种本质并行13硕士学位论文 第2章蚁群算法和遗传算法的原理与分析的算法，在不同个体之间不断进行信息交流和传递，从而能够相互协作，有利于发现较好优化解，蚁群算法可以解释为一种特殊的强化学习算法4J【251。蚁群算法与中，信息素相当于学习中的示学习所得到的经验。由某种启发式算法确定，如何将这两者结合起来，是提高蚁群算法效率的关键。虽然蚁群算法有许多优点，但是，这种算法也存在一些缺陷，如：与其它方法相比，该算法一般需要较长的搜索时间，蚁群算法的复杂度可以反映这一点；而且该方法容易出现停滞现象。即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。22遗传算法原理及其研究遗传算法(称美国JH61，当时并没有能够在学术界中引起关注，因而发展比较缓慢。从80年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法也就逐步成熟，并且应用日渐增多，不仅应用于人工智能领域(如机器学习和神经网络)，也开始在工业系统，如控制、土木、机械、电力工程中得到了成功应用，显示出了诱人可观的前景。它是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题优化求解。遗传算法(基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法【271。其主要特点是群体搜索策略和在群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密执根(学的霍兰(授发展起来的。1975年霍兰教授发表了第一本比较系统论述了遗传算法【28】的专著自然系统与人工系统中的适应性(。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。14硕士学位论文 第2章蚁群算法和遗传算法的原理与分析221基本遗传算法要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。遗传算法(下简称基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。把搜索空间(欲求解问题的解空间)映射为遗传空间，即把每一个可能的解编码为一个向量(称为一个染色体(个体)129，向量的每一个元素称为基因(所有染色体组成群体(集团)。并按预定的目标函数(或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等)对每个染色提进行评价，根据其结果给出一个适应度的值。l、遗传算法的运行机理在利用进化算法求解优化问题时，首先需要随机生成包含一定数量个体的初始种群，其中的每一个个体都代表问题的一个可行解；然后根据问题评价这些可行解的优劣，并赋以相应的适应度值；再根据适应度值，按照较好的个体对应较大的生存空间的指导原则，引入具有一定随机性的遗传操作，生成下一代的新种群；然后重复上述过程直至满足运行终止条件【301。算法开始时先随机地产生一些染色体(欲求解问题的侯选解)，计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低(性能不佳)的染色体，留下适应度高(性能优良)的染色体，从而得到新的群体。2、)参数编码：不是采用问题参数本身，一般都会选择二进制编码；(2)初始种群设定：也可根据一定的限制条件来产生。种群规模是指种群中所包含染色体的数目；(3)适应度函数的设定：适应度函数是用来鉴别种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适应度函数；(4)遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程；(5)遗传基本算子包括：选择算子，交叉算子，变异算子和其他的高级遗传算子；