基于思维进化算法的PID控制器参数优化论文（很完整）

《基于思维进化算法的PID控制器参数优化论文（很完整）》由会员分享，可在线阅读，更多相关《基于思维进化算法的PID控制器参数优化论文（很完整）（94页珍藏版）》请在装配图网上搜索。

1、*毕业设计（论文）设计说明书设计(论文)题目：基于思维进化算法的PID控制器参数优化学 生： *专 业： 自动化班 级： *班指导教师： *设计日期：*年6月18日*毕业设计（论文）任务书毕业设计（论文）题目：基于思维进化算法的PID控制器参数优化毕业设计（论文）要求及原始数据（资料）：在工业过程控制的发展史上，PID控制是历史最悠久、生命力最强的控制方式。在当前的工业控制器中，有半数以上的控制采用PID或变形PID控制。PID控制器被广泛应用主要是因为其结构简单、实际中容易被理解和实现，而且许多高级控制都是以PID控制为基础的。它直接影响控制效果的好坏，并和系统的安全、经济运行有着密不可分得

2、关系。但PID参数的整定一般需要经验丰富的工程技术人员来完成，既耗时又耗力，加之实际系统千差万别，使PID参数的整定有一定的难度。思维进化算法(MEA)也是针对遗传算法(GA)所出现的问题而提出的一种行之有效的解决方法。它模仿人类思维进化的过程，引入了遗传算法的群体概念，但从根本上与GA存在着不同，它提出了用于进化的趋同和异化算子，引入了公告板记录进化过程中的信息，从而能充分利用计算机的记忆功能，利用异化过程使得其具有很好的全局搜索性能。由于引入了记忆与定向学习机制，增强了演化算法的智能性，大大提高了搜索效率，MEA成功地解决了演化算法中早熟和收敛速度慢等问题，并在一些领域得到成功应用。第1页

3、本设计是在获取控制对象模型后，采用算法优化PID参数，并程序实现。要求设计（论文）包括以下几方面内容：1. 掌握PID控制的基本知识；2. 了解进化计算的基本原理；3. 掌握思维进化算法的基本过程；4. 掌握Matlab的设计与仿真及Smulink软件包；5. 编程实现思维进化算法优化PID控制器参数；6. 仿真实例研究、结果分析；7. 进化计算的不足与展望。毕业设计（论文）主要内容：本毕业设计主要工作内容包括：1. 中英文摘要及关键字；2. 查找及阅读相关文献资料，介绍工业中PID控制的应用现状；3. 掌握PID控制的基本知识；4. 查找及阅读相关文献资料，了解进化计算；5. 查找及阅读相关

4、文献资料，介绍进化计算及思维进化算法的应用；6. 掌握思维进化算法的基本步骤； 7. 掌握Matlab软件的程序设计与仿真；8. 设计思维进化算法优化PID参数；9. 应用Matlab软件及Smulink软件包仿真；10.进行编程、实验并分析结果；第2页11. 总结思维进化算法的不足，展望应用前景；12. 总结PID控制和各种智能方法的结合应用前景。学生应交出的设计文件（论文）：毕业论文一份，论文文本文件及程序源代码一份。英文10000字符翻译。第3页主要参考文献（资料）：1 谢克明,王丽坤,谢刚,郭红波.基于克隆思维进化算法的机器人足球协作策略. 太原理工大学学报.2007.(5).2 李士

5、勇.模糊控制神经控制和智能控制论M.哈尔滨：哈尔滨工业大学出版社,1996.3 顾峻,沈炯,陈来九.遗传算法对模糊控制的优化及其应用J.东南大学学报,Vol.28,1998.4 臧辉.遗传算法及其应用.武汉科技学院学报,2005,(4).5 杨俊杰,任雪梅,黄鸿,.基于遗传算法的多智能体协作行为研究.计算机仿真,2006,(3).6 丁轲轲,刘久斌,林青.热工过程自动调节M.北京:中国水利电力出版社,2000.7 荣雅君,窦春霞,袁石文.过热汽温模糊神经网络预测控制器的设计.中国电机工程学报,Vol.23No.1,Jan.2003.8 孙增圻等.智能控制理论与技术M.北京:清华大学出版社,19

6、97.9 陈来九.热工过程自动调节原理和应用M.北京:水利电力出版社,1982.10 刘金琨.先进PID控制MATLAB仿真.电子工业出版社M,2006.11 王丽爱,周旭东,陈崚,孙承意.双层MEC算法优化多峰问题.计算机工程与应用, 2007,12.专业班级自动化*级班学生*要求设计(论文)工作起止日期2008年2月25日2008年6月18日指导教师签字日期教研室主任审查签字日期系主任批准签字日期第4页太原理工大学毕业设计（论文）摘 要进化计算是模拟生物进化过程与机制的一类随机优化计算模型。根据对GA存在问题的思考以及对人类思维进步的分析，模仿人类社会中存在的趋同和异化现象，1998年提出

7、了思维进化算法(MEA)。本文首先介绍了进化计算的基本知识，阐述了思维进化算法的基本框架，特点和应用，并且利用思维进化算法进行了函数优化，MATLAB软件的仿真结果表明思维进化算法对函数优化达到了比较好的效果。在工业过程控制的发展史上，PID控制是历史最悠久、生命力最强的控制方式。接下来本文介绍了PID控制器的原理和应用，并且用MATLAB软件实现了基于思维进化算法的PID控制器参数优化。仿真结果表明思维进化算法应用于PID控制器参数优化设计的可行性和有效性。最后本文总结了思维进化算法的不足并且展望了其应用前景。关键词：进化计算；思维进化算法；MATLAB；PID控制器AbstractThe

8、evolution computation which simulated the organic evolution process and mechanism was a kind of stochastic optimization computation model. According to the questions of GA and the human thinking progressive analysis, imitating the similartaxis and dissimilation phenomenon in the human society, Mind

9、Evolution Algorithm (MEA) was proposed in 1998. This paper firstly introduced the basic knowledge of evolution computation, then introduced the basic architecture, the characteristic and the application of Mind Evolution Algorithm. Then the Mind Evolution Algorithm carried on the function optimizati

10、on, the MATLAB softwares simulation results had indicated that the Mind Evolution Algorithm achieved the quite good effects to the function optimization.In the history of commercial process control, the PID control was the control mode with the longest histories and the strongest vitality. This pape

11、r also introduced the PID controllers principles and the applications, then realized the PID controller parameter optimization design based on the Mind Evolution Algorithm by the MATLAB software. The simulation results had indicated that the Mind Evolution Algorithm applied in the PID controller par

12、ameter optimization feasibly and effectively. Finally this paper summarized the deficiency of Mind Evolution Algorithm and looked forward to its application perspective.Key words: Evolution computation; Mind Evolution Algorithm; MATLAB; PID controller- I -目 录第1章 绪 论11.1 引言11.1.1 进化计算的发展背景11.1.2 智能控制

13、的发展背景21.2 本文选题的意义3第2章 进化计算42.1 进化计算的概述42.2 进化计算的主要分支62.2.1 遗传算法62.2.2 进化策略72.2.3 进化规划82.2.4 遗传程序设计82.3 进化计算的主要特点92.4 进化计算的研究内容及其前景9第3章 思维进化算法123.1 思维进化算法的提出123.2 思维进化算法的基本框架133.2.1 思维进化算法的系统结构和基本知识133.2.2 三个基本机制163.3 思维进化算法的特点173.4 思维进化算法的应用17第4章 MATLAB软件实现思维进化算法及其在函数优化中的应用194.1 程序流程图194.2 源程序204.3

14、子程序及仿真结果234.4 结果分析29第5章 PID控制的原理和应用305.1 PID控制的原理和特点305.2 PID控制原理315.2.1 模拟PID控制器315.2.2 数字PID控制器345.3 PID参数整定方法概述375.4 PID控制的性能指标395.5控制器参数对控制性能的影响415.6 PID控制的应用现状41第6章 MATLAB软件及Simulink实现思维进化算法的PID控制器参数优化446.1 MATLAB与Simulink介绍446.1.1 MATLAB软件介绍446.1.2 Simulink介绍466.2 基于思维进化算法的PID控制器参数优化方案476.3 程序

15、流程图476.3.1 主程序流程图476.3.2 子程序流程图486.4 源程序及仿真结果496.4.1 主程序496.4.2 子程序1536.4.3 仿真结果及结果分析546.4.4 子程序2576.4.5 仿真结果及结果分析58第7章 总结与展望627.1 工作总结627.2 应用前景展望62参考文献64设计总结66致 谢67附录一：英文68附录二：中文78- i -第1章 绪 论1.1 引言1.1.1 进化计算的发展背景传统的进化计算是模拟“物竞天择”与“自然遗传”的生物进化过程所产的随机化计算模型。它的起源可以追溯到二十世纪50年代后期，其中Bremermann，Friedberg，B

16、ox所做的工作是最具有影响的。但是，在以后的三十年时间里，这一领域的工作对于广大科学工作者来说，还是相当陌生的。造成这种状况的原因主要是当时缺少强大的计算机硬件平台和早期进化计算本身的方法论缺陷。一直到了二十世纪70年代，Holland，Rechenberg，Schwefel，Fogel等人的奠基性工作才慢慢地改变了这种状况。特别是最近十年，以进化计算为主题的出版物和学术会议逐年增加，充分说明了进化计算作为一个新兴学科分支的巨大潜力。如今，面向应用的进化计算研究几乎渗透到各行各业，正掀起了一个世界范围内的进化计算研究热潮。那么，是什么原因使得进化计算在最近十年来被广泛研究和应用呢？除了计算机性

17、能有了极大的提高以外，最主要的应当归功于进化计算具有自组织性，自学习性，自适应性，自优化等智能特征，同时又具有内在并行性，原理的简单性，优良的全局性，计算的随机性与应用的广泛性。传统的进化计算是由几个相互联系，但事实上又是彼此独立发展起来的分支组成的，它们是遗传算法，进化策略，进化规划和遗传程序设计。其中以遗传算法最具代表性。20世纪60年代中期，Holland教授提出了遗传算法(Genetic Algorithm，太原理工大学硕士学位论文简记为GA)，它是以生物遗传原则和类似于进化的操作为基础的模仿的是自然界生物进化过程。经过三十多年的发展，无论在算法的改进方面，还是理论以及应用研究方面，都

18、已取得了很大的进步。但是遗传算法中仍然存在许多问题，如建筑块假设、早熟收敛和进化时间长等问题。根据对GA存在问题的思考以及对人类思维进步的分析，模仿人类社会中存在的趋同和异化现象，孙承意教授于1998年8月提出了思维进化算法(Mind Evolutionary Algorithm，缩写为MEA)。MEA继承了GA的“群体”和“进化”的思想，但其它方面与GA均不相同，进行了重大创新。MEA将群体划分为若干子群体，提出了“趋同”和“异化”两种操作。“趋同”起开采的作用，而“异化”起勘探的作用，这两个操作都隐含有选择操作。重要的是，这二者的作用是非对立的，它们是协调工作的。趋同对系统从环境得到局部信

19、息加以开采，迅速搜索局部的最优。而异化操作在整个解空间进行搜索，选择较优的个体作为中心，创建新的临时子群体。1.1.2 智能控制的发展背景从1932年奈魁斯特(H.Nyquist)发表反馈放大器的稳定性论文以来，控制理论学科的发展已走过近70年的历程，自动控制理论经历了经典控制理论和现代控制理论两个重要发展阶段。前者主要解决单变量系统的反馈控制问题，而后者则着重解决多变量系统的优化问题。他们在许多领域均取得了成功的应用，促进了社会生产力的发展。二十世纪七十年代中期以来，科学技术的高度发展，致使被控对象结构上的日益复杂化和大型化。传统的自动控制理论面临复杂性所带来的困境，力图突破旧的模式以适应社

20、会对自动化学科提出的新要求。能否建立新一代的控制理论来解决复杂系统的控制问题，已经成为各国控制控制理论界共同关心的热点。在二十世纪七十年代大系统理论问世后的一段时间里，有人曾推测它是第三代控制理论的雏形。但这种观点未能得到实践的认可。实际上大系统理论仍未突破以往控制理论的基本思想与框架，除了高维线性系统之外，它对其它复杂系统仍然束手无策。人们开始认识到，在许多系统中，复杂性不仅仅表现在高维性上，更多的则是表现在系统信息的模糊性、不确定性、偶然性和不完全性上。基于精确数学模型的大系统理论当然无法解决好它们的控制问题。正当人们为寻找一种新理论费尽心机时，模糊逻辑、神经网络、进化计算等人工智能技术由

21、于得益于计算机技术而飞速发展，渐渐形成一门学科，并在实际应用中显示出很强的生命力。与此同时，国际学术界对智能控制的研究十分活跃，1985年IEEE在美国纽约召开了第一届智能控制学术讨论会，这次会议的召开，为智能控制作为一个独立的新学科在国际学术界的崛起奠定了基础。接着1988年8月召开了第二届智能控制的国际会议，以后智能控制会议每年都举行一次。到了二十世纪九十年代，各种智能控制的国际学术会议日益频繁。国内在八十年代初开始智能控制的研究，并在许多领域成功进行了应用。智能控制是一个新兴的学科领域，它是随着计算机技术的进步在经典控制理论和现代控制理论的基础上发展起来的。与传统的控制理论相比，智能控制

22、对于环境和任务的复杂性有更大的适配程度。它不仅仅是对建立的模型，而且对于环境和任务能抽取多级的描述精度，进而发展了自学习、自适应和自组织等概念，所以能在更广泛的领域中获得应用。虽然智能控制理论只有十几年的历史，尚未形成比较完整的理论体系，但其应用成果和理论发展己说明智能控制正成为自动控制的前沿学科之一。PID控制3是工业生产中应用较为广泛的一种控制方式，它原理简单、形式固定，控制效果一般比较令人满意，容易被广大工程技术人员所接受，因此研究PID控制器参数的整定技术具有重要意义。1942年Ziegler-Nichols方法被提出，并得到了广泛的应用和改进；后来又出现了Cohen-Coon响应曲线

23、方法和KappaKau调节方法。但是，由于此类PID控制器参数整定技术大都是对经验的总结，只能适用于满足经验公式条件的对象，且只利用了较少的系统动态特性信息，所以得到的控制器性能也是很局限的。随着遗传算法(GA)的提出，又出现了利用遗传算法对PID控制器参数进行优化整定的算法。但遗传算法22要涉及到繁琐的编码、译码过程以及较大的计算量，而且在整个搜索过程中，染色体互相共享信息，整个种群是比较均匀地向最优区域移动，影响该算法的寻优效率。针对遗传算法存在的问题并受到新研究进展的启发，孙承意于1998年提出了基于思维进化的机器学习算法，即思维进化算法MEA(Mind Evolutionary Alg

24、orithm)，该算法继承了进化算法(EC)中“群体”和“进化”的概念，引入趋同和异化两种操作，模拟人类思维、知识的进化过程。思维进化算法突破了自然进化的限制，在进化中引入了记忆与定向学习机制，增强了进化算法的智能程度，提高了搜索效率，成功解决了进化计算中早熟和收敛速度慢等问题。本文借助MEA算法的群体寻优能力来优化整定PID控制参数。1.2 本文选题的意义在工业过程控制中，目前采用最多的控制方式依然是PID方式。PID3控制器被广泛应用主要是因为其结构简单、实际中容易被理解和实现，而且许多高级控制都是以PID控制为基础的。它直接影响控制效果的好坏，并和系统的安全、经济运行有着密不可分得关系。

25、然而，PID参数复杂繁琐的整定过程一直困扰着工程技术人员，研究PID参数自整定技术具有十分重大的工程实践意义。PID的设计与参数整定依然是工业控制中的一个研究重点。原因就在于PID比例系数、积分系数、微分系数三个参数需要设计和整定，再加上采样周期等系统参数需要选择，因此要设计出理想的参数有相当的难度。传统的整定方法有Ziegler-Nichols整定算法、Cohen-Coon整定算法，基于幅值与相位裕量设定的算法等，这些方法都属于经验设计方法。新的设计和整定方法都把重点放在PID控制器的优化设计及自适应设计上。本文试图利用思维进化算法的群体寻优能力来优化PID控制器的参数，通过Matlab软件

26、在给定的目标函数下，利用思维进化算法，搜索最优参数，并利用程序实现。第2章 进化计算2.1 进化计算的概述当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代。这一点在计算机科学领域表现得尤为突出。一方面，计算机科学的迅猛发展，从根本上改变了人类的生活、学习和工作的方式，使人类文明进入了一个崭新的时代；另一方面，随着人类生存空间的扩大和认识世界改造世界范围的拓宽，人们又对计算机科学提出了新的要求与期望。而所有的期望值中，对计算机的计算速度和具有智能的要求可能是最迫切和最基本的。很多实际应用问题不仅涉及到大量的计算而且需要实时响应，这对计算机的速度提出了强有力的挑战。由于提高单机速度受其物

27、理极限的限制，解决这一问题的根本途径便是并行化。虽然目前并行机已较为普遍，但因为缺乏有效的并行算法，以至于使用并行机难以获得较高的加速比。制造出具有智能的机器一直是人类的梦想，直到1956年人工智能技术的出现，人们已为此作出了巨大的努力。近年来，随着人工智能应用领域的不断拓宽，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的困难己变得越来越突出，甚至使得某些学者对强人工智能提出了强烈批评，对人工智能的可能性提出了质疑。基于上述原因，寻求一种适于大规模并行机且具有某些智能特征如自组织、自适应、自学习等的算法已成为有关学科的一个研究目标。近年来，一些新的研究

28、方向如神经网络、细胞自动机和进化计算等，由于它们都是模拟某一自然现象或过程而发展起来的，并且具有适于高度并行、自组织、自适应、自学习的特征，因而引起了人们的极大兴趣。这些新方法通过“拟物”与“仿生”以使问题得到解决，它们也许能为解决某些复杂问题提供新的契机。大自然是我们解决各种问题时获得灵感的源泉。几百年来，将生物界所提供的答案应用于实际问题的求解已被证明是一个成功的方法，并且已形成了一个专门的科学分支仿生学(Bionics)。自然界所提供的答案是经过漫长的自适应过程进化过程而获得的结果。除了进化过程的最终结果，我们也可以利用这一过程本身去解决一些较为复杂的问题。这样，我们不必非常明确的描述问

29、题的全部特征，只需要根据自然法则来产生新的更好解。进化计算正是基于这种思想而发展起来的一种通用的问题求解方法。从19世纪50年代开始就有许多作者开始利用达尔文的进化论解决优化问题，在以后的30年中出现了许多基于此概念的算法，一般称为“进化计算方法”，它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用种群（即一组表示）的方式组织搜索，这使得它可以同时搜索解空间的多个区域。而且用种群组织搜索的方式使得进化计算特别适合大规模并行。在赋予进化计算自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作

30、使进化计算具有不受其搜索空间限制性条件（如可微、连续、单峰等）的约束及不需要其它辅助信息（如导数）的特点。这些崭新的特点使得进化计算不仅能获得较高的效率而且具有简单、易于操作和通用的特性，而这些特性正是进化计算越来越受到人们青睐的主要原因之一。进化计算在20世纪六七十年代并未受到普遍的重视。其主要原因一是当时这些方法本身还不够成熟；二是由于这些方法需要较大的计算工作量，而当时的计算机还不够普及而且速度也跟不上要求，这样便限制了它们的应用；三是当时基于符号处理的人工智能方法正处于其顶峰状态，使得人们难以认识到其它方法的有效性及适应性。到了20世纪80年代，人们越来越清楚地意识到传统人工智能方法的

31、局限性，并且由于计算机速度提高以及并行计算机的普及，进化计算对机器速度的要求己不再是制约其发展的因素。更由于进化计算的不断发展及其在一些应用领域内取得的成功，表现出了良好的应用前景。德国Dortmund大学1993年末的一份研究报告报导，据不完全统计进化计算已在16个大领域250多个小领域获得了应用。由于进化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成功，己引起了包括数学、物理学、化学、生物学、计算机科学、社会科学及工程应用等领域科学家们的极大兴趣。自80年代中期以来，世界上许多国家都掀起了进化计算的研究热潮。目前，有数种以进化计算为主题的国际会议在世界各地定期召开。国际互联网上

32、也有多种相关的mailing list，USENET还有专门的新闻组comp.ai.genetic。由于化计算应用范围之广泛，从一些杂志及国际会议论文集中都比较容易看到这方面的文章。现在已出版两种专门关于进化计算的新杂志“Evolutionary Computation”和“IEEE Transactions on Evolutionary Computation”而且一些国际性期刊也竞相出版以进化计算为主题的专刊。新的一轮日本计算机发展规划RWC计划(Real World Computing Program)也把进化计算作为它的主要支撑技术之一，以进行信息的集成、学习及组织等19。另外，某些

33、学者研究了进化计算的自现行为(emeregent behavior)后声称，进化计算将与混沌理论和分形几何一道成为人们研究非线性现象和复杂系统的新的三大方法，并将与神经网络一道成为人们研究认知过程的重要工具。当前，进化计算的研究内容十分广泛，如进化计算的设计与分析、进化计算的理论基础及其在各个领域中的应用等等。可以预料随着进化计算研究的不断深入和应用领域的不断拓宽，进化计算将取得更大的成功16。2.2 进化计算的主要分支自计算机出现以来，生物模拟（也称仿生）成了计算机科学的一个组成部分。其目的一是企图建立一种人工模拟环境，以便使用计算机进行仿真，以更好地了解人类自己和人类的生存空间；二是从研究

34、生物系统出发，探索产生基本认知行为的微观机理，然后设计成具有生物智能的机器或模拟系统以解决更为复杂的问题。如神经网络、细胞自动机和进化计算都是从不同角度模拟生物系统而发展起来的研究方向。进化计算最初具有三大分支：遗传算法(genetical gorithm，简称GA)，进化规划(evolutionary programming，简称EP)和进化策略(evolution strategy，简称ES)。20世纪90年代初，在遗传算法的基础上又发展了一个分支：遗传程序设计(genetic programming，简称GP)。虽然这几个分支在算法实现方面具有一些细微的差别，但它们具有一个共同特点，都是

35、借助生物进化的思想和原理来解决实际问题的。下面本文将分别对几个分支作一个简单的介绍。2.2.1 遗传算法把计算机科学与进化论结合起来的尝试始于20世纪50年代末，但由于缺乏一种通用的编码方法，使得人们只能依赖变异而不是交叉来产生新的基因结构，故而收效甚微。到20世纪60年代中期，美国密西根大学的John Holland在A.S.Frase和H.J.Bremermann等工作的基础上提出了位串编码技术，这种编码既适合于变异又适合交叉（即杂交）操作，他还强调将交叉作为主要的遗传操作。随后，John Holland将该算法用于自然和人工系统的自适应行为的研究之中，并于1975年出版了其开创性的著作(

36、daptationin Nauraland Artificial System)后来，John Holland与他的学生们将该算法加以推广并应用到优化及机器学习的问题之中，并且正式定名为遗传算法。遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础6。John Holland的遗传算法常被称为简单遗传算法(SGA)，其操作对象是一群二进制串（称为染色体、个体），即种群(population)。这里每个染色体都对应于问题的一个解。从初始群体出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交(crossover)和变异(mutation)来产生下一代种群。如此一代

37、代演化下去，直到满足期望的终止条件5。遗传算法可以形式化描述如下：这里=(（0）,(0),.,(0)，表示初始群体；表示长度为的二进制串全体，称为位串空间；N表示种群中含有个体的个数；表示二进制串的长度；s:表示选择策略；g表示遗传算子，通常它包括繁殖算子:、杂交算子和变异算子；表示遗传算子的操作概率，包括繁殖概率,杂交概率和变异概率；是适应度函数；是终止准则。当然，目前的遗传算法己不再局限于二进制编码。同Z.Michalewicz将不同的编码策略(即不同的数据结构)与遗传算法的结合称为进化程序(evolution program)。2.2.2 进化策略20世纪60年代初，柏林工业大学的Z.R

38、echenberg和H.-P.Schwefel等在进行风洞实验时，当遇到设计中描述物体形状的参数难以用传统方法进行优化时，他们利用生物变异的思想来随机地改变参数值并获得了较好的结果。随后，他们便对这种方法进行了深入地研究，使其不断发展完善，形成了进化计算的另一个分支进化策略。早期进化策略的种群中只包含一个个体，而且只使用变异操作。在每一进化代，变异后的个体与其父体进行比较再选择两者之优。这一选择策略日前称为(1+1)策略。它使用的变异算子是基于正态分布的变异操作，这种进化策略称为(1+1)进化策略和二元进化策略。(1+1)进化策略存在很多弊端，如有时收敛不到全局最优、效率较低等。它的改进即是增

39、加种群内个体的数量，从而形成(+l)进化策略。此时种群内含有个个体，随机地选取一个个体进行变异，然后取代群体中最差的个体。(+1)进化策略与(1+1)进化策略的相似之处是每次只产生一个后代。为了进一步提高效率，后来发展成(+)进化策略和(，)进化策略，并且引进了重组(recombination)操作，即由二个个体按类似于杂交方式生成一个新个体(+)进化策略根据种群内的个个体产生个个体(用变异和重组)，然后将这(+)个体进行比较再在其中选取个优胜者。(，)进化策略则是在新产生的()个个体中选择个最优者。这两种进化策略的选择方法分别被称为(+)和(，)选择。进化策略与遗传算法不同之处还在于遗传算法

40、要将原问题的解空间映射到位串空间中，然后再施行遗传操作，它强调个体基因结构的变化对其适应度的影响。而进化策略则是直接在解空间上进行操作，它强调进化过程中从父代到后代行为的自适应性和多样性。从搜索空间的角度来说，进化策略所强调的是直接在解空间上进行操作，强调进化过程中搜索方向和步长的自适应调节。进化策略主要用于求解数值优化问题。近年来，遗传算法也采用十进制编码（或称浮点数编码）技术来求解数值优化问题。进化策略与遗传算法的相互渗透使得它们之间没有很明显的界限。2.2.3 进化规划进化规划(evolutionary programming)的方法最初是由L.J.Fogel等在20世纪60年代提出的。

41、他们在人工智能的研究中发现，智能行为即是要具有能预测其所处环境的状态，并按照给定的目标作出适当响应的能力。在研究中，他们将模拟环境描述成为由有限字符集中的符号组成的序列。于是问题便转化为怎样根据当前观察到的符号序列作出响应以获得最大的收益，这里收益的计算是按照环境中将要出现的下一个符号及预先定义好的效益目标来确定的。进化规划中常用的有限态自动机(finite statemachine，简称FSM)来表示这种的策略。这样，问题便成为如何设计出一个有效的FSM?L.J.Fogel等借用进化的思想对一群FSM进行进化以获得较好的FSM。他们将此方法应用到数据诊断、模式识别和分类以及控制系统的设计等方

42、面，并取得了较好的结果。后来，D.B.Fogel借助于进化策略方法对进化规划进行了发展，并用到解决数值优化及神经网络的训练等问题之中。2.2.4 遗传程序设计自从计算机出现以来，计算机科学的一个重要目标是让计算机自动进行程序设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传程序设计(genetic programming)便是在该领域中的一种尝试。它采用遗传算法的基本思想，但使用一种更为灵活的表示方式分层结构来表示其解空间。这些分层结构的叶结点是问题的原始变量，中间节点则是组合这些原始变量的函数。它们还类似于LISP语言中的S一表达式。这样的每一个分层结构对应问题的一个解。

43、也可以理解为求解该问题的一个计算机程序。遗传程序设计是使用一些遗传操作动态地改变这些机构，从而获得解决该问题可行性的计算机程序。遗传程序设计的思想是斯坦福大学的J.R.Koza在20世纪90年代初提出的，并于1992年出版了专著“Genetic Programming”，1994年又出版了第二卷。由于遗传程序设计所采用的是一种更自然的表示方式，所以它应用领域非常之广。日本ATR研究中心的H.de Garis甚至提出遗传程序设计不仅可以进化计算机程序，而且可以进化任何复杂系统。他目前正致力于CAM-Brain计划，正是基于这种思想之上的。该计划的目标是要制造具有人类大脑部分功能的人工脑(arti

44、ficial brain)。2.3 进化计算的主要特点进化计算与传统的方法有很多不同之处，但最主要的特点体现在下述两方面:1.智能性进化计算的智能性包括自组织、自适应和自学习性等。应用进化计算求解问题时，确定了编码方案、适应值函数及遗传算子之后，算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为适者生存、不适应者淘汰，故适应值大的个体具有较高的生存概率。通常适应值大的个体具有对环境较适应的基因结构，再通过杂交和基因突变等遗传操作就可能产生与环境更适应的后代。进化计算的这种自组织、自适应特征也赋予了它具有根据环境的变化自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中

45、的一个最大障碍即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采取的措施。因而，利用进化计算的方法，可以解决那些结构尚无人能理解的复杂问题。2.本质并行性进化计算的本质并行性表现在两个方面:一是进化计算是内在并行(inherent parallelism)，即进化计算本身非常适合大规模并行。最简单的并行方式是上几百甚至数千台计算机各自进行独立种群的进化计算，运行过程中不进行任何通信，等到运算结束时才通信比较，选取最佳个体，这种并行处理方式对并行系统结构也没有什么限制和要求。可以说，进化计算适合在目前所有的并行机和分布式系统上进行并行处理，而且对其并行效率没有太大的影响。二是进化计算

46、的内含进行性(implicit parallelism),由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间的多个区域，并相互交流信息，这种搜索方式使得它虽然每次只执行与种群规模成比例的计算，而实际上己进行了大约次有效搜索。这使得进化计算能以较少的计算获得较大的收益。2.4 进化计算的研究内容及其前景进化计算的研究内容相当广泛，反映了多学科相互交叉的特点。目前进化计算的研究主要集中在以下几个方面:1.进化计算的理论研究:由于进化计算缺乏统一、完整的理论体系，目前一些理论结果主要集中在收敛性分析，但很难给出收敛速度的估计。诸如在编码方案的选择、控制参数的选取、如何根据特定的编码方案设计

47、有效的遗传算子以及算法的分析和性能评价等等方面，只能就具体问题具体分析。而且分析主要依赖计算机模拟的实验结果，现在还缺乏严密、科学的一般规律和方法。为了推动进化计算研究的发展，迫切需要宏观的理论指导。2.新的计算机模型:进化计算目前实现的计算模型只是生物进化模型的很小一部分。近年来实现的免疫系统模型和协同进化模型等在解决某些问题是取得了较好效果。这对尝试新的进化模型是一种促进。3.进化优化:当代科学技术的各个领域都存在大量的优化问题。虽然优化方法有很多分支且硕果累累，但是实际存在的问题是千变万化的，形成的数学模型自然也是千姿百态五花八门。因此要想以一种优化方法有效地解决所有的问题是不现实也是不

48、可能的。近年来，进化计算在解决复杂优化问题方面取得了振奋人心的成就。但是在如何根据具体问题设计有效的进化算法以提高计算速度及解决约束优化等方面，还有许多工作需要去做。4.进化人工神经网络:人工神经网络(ANN)是近年来受到广泛关注的一个研究领域。在神经网络的应用中，ANN的网络结构的设计和权值的训练是一个十分困难而重要的问题，传统方法大多是凭经验或启发知识来设计网络，用梯度法来确定其中的权值，因此常常需要进行反复试验而且还很难找到最优的网络结构和权值。而进化计算为ANN的自动设计和训练提供了一种新的途径。但目前的一些研究成果还主要集中在小型网络的设计上，在实用化方面还面临着很多问题需要解决。5

49、.并行和分布式进化计算:对并行进化计算的研究表明，通过多个种群的进化和适当地控制种群的相互作用，可以提高求解的速度和解的质量。并行化甚至可以使进化计算获得超线性加速比。由于进化计算的并行处理平台可以是大规模并行计算机系统也可以是分布式处理系统(如工作站群集等)。因此，近几年来，对并行和分布式进化计算的研究也越来越受到重视孟目前已有几种较为成功的并行化和分布式模型。但是，种群之间以什么方式进行联系和进行多大的通信才能获得更大的效率以及其它并行化模型的研究都将是以后研究的重点。6.进化机器学习:传统的机器学习方法都是根据预先确定的规则和知识来决定所采取的策略。因而它很难用于环境不断变化的问题之中，

50、而进化计算正好可以为此助一臂之力。目前，进化计算的机器学习方法，如分类系统等正被越来越多地应用到实际问题中。将进化计算与一些启发式的机器学习方法相结合将可能是今后研究的一个重点。7.进化计算应用系统:在理论与算法研究的基础上，利用进化计算组成实际的应用系统，如用于图像处理和模式识别、制造机器人、进行最优控制等等。在设计各类应用系统的算法时，把进化计算与传统的启发式搜索算法结合起来可能会取得更好的结果。8.进化硬件:微电子工业的发展使得计算机硬件的成本越来越低，而软件的成本越来越高。利用硬件的冗余实现对硬件的可编程是提高软件效率的一种途径。同时硬件可随环境的变化而变化本身在工业中也可以找到很多的

51、应用。随着硬件电路的复杂度和密度增加，按照蓝图设计方法进行设计，对于设计人员来说，必将超出其极限而不堪重负。实现硬件的自动演化将是对传统的硬件设计方法蓝图设计的一次革命。它也将给我们带来新的机遇与挑战。9.进化软件:基于遗传程序设计而展开的自动式程序设计，正在发展成对进化软件的研究。10.进化计算内涵的扩充:进化计算已从模拟生物的进化过程扩充到模拟大自然的进化过程(problem solving from nature，也称natural computation)。它不仅采用“仿生”策略，也通过模拟“拟物”，进化过程来进行问题求解。随着进化计算研究热潮的兴起，人工智能再次成为人们关注的一个焦点

52、。有些学者甚至提出进化计算是人工智能的未来。其观点是虽然我们不能完全用机器代替人的自然智能，但我们可以利用进化获得智能圈。目前，进化计算与神经网络、模糊系统一起己形成一个新的研究方向计算智能(computational intelligence)。人工智能己从传统的基于符号处理的符号主义向以神经网络为代表的连接主义和以进化计算为代表的进化主义方向发展。虽然进化计算模拟了生物的进化过程，但是目前进化算法中群体的规模远远小于生物进化系统。随着大规模并行计算机和分布式计算机系统性能的不断提高以及对生物进化系统的进一步认识，我们将有可能模拟更接近于自然的进化系统。这样，进化计算的本质并行性将得到充分发

53、挥，从而为进一步揭示生命和智能的奥秘写下新的篇章。第3章 思维进化算法3.1 思维进化算法的提出遗传算法是由Holland教授提出来的，它模仿的是自然界的生物进化过程。经过三十多年的发展，无论在算法的改进方面，还是理论以及应用研究方面，都已取得了很大的进步和成功。但是遗传算法中仍然存在许多问题，如建筑块假设、早熟收敛和进化时间长等问题。自然界的生物通过遗传和自然选择，进化了数亿年。而人类的思维进步的速度却远高于生物的进化。其原因为：人类能向前人和周围的成功者学习。随着信息技术的进步、信息交流的便利，近二百年人类的思维进步越来越快。人类的这种学习并不是简单的模仿前人和成功者的行为，而是在他们的经

54、验的基础上发展进步。同时人类不断地改变自己的思维方式，探索新的领域。正是这种探索，使新科学、新技术、新方法和新观念不断涌现。这两种思维方式相互作用加速了科技的发展，推动了生产力的快速进步。针对GA存在的缺点，模仿人类思维进步的过程，孙承意教授于1998年8月提出了思维进化算法1(Mind Evolutionary Algorithm，缩写为MEA)他给出了MEA的框架，阐述了MEA的产生。需要说明的是：在早期，该算法的名称为“基于思维进化的机器学习(Mind-evolution-based machine learning，缩写为MEBML)”，为了便于提及，接受国内外一些学者的建议，后来决定

55、改名为“思维进化算法”，其内容完全不变。MEA继承了GA的“群体”和“进化”的思想，但其它方面与GA均不相同，进行了重大创新。MEA将群体划分为若干子群体，提出了“趋同”和“异化”算子。进化操作“趋同”起开采的作用，“异化”起勘探的作用，这两个操作都隐含有选择操作。重要的是，这二者的作用是非对立的。趋同对系统从环境得到局部信息加以开采，迅速搜索局部最优。而异化操作在整个解空间进行搜索，选择较优的个体作为中心创建新的临时子群体。这两种操作是协调工作的，趋同和异化操作的改进对整个算法提高搜索效率都有贡献。另外需要说明的一点是：这里使用了术语“思维进化”，严格地说应该是“思维进步”。生物的进化采用的

56、是一种非定向的机制，进化的概念并不天然地包含进步意义，即不包含某种目标，也不暗示某种方向。生物进化中的适应是非常局部的、非定向的和近似的。这里借用进化一词是要表明MEA算法的基本思想是与进化计算的基本思想是一致的，MEA属于进化计算的一部分1。3.2 思维进化算法的基本框架3.2.1 思维进化算法的系统结构和基本知识MEA的主要组成部分如图3-1所示。下面我们将详细介绍结构图中的组成部分13。1群体和子群体思维进化算法是一种通过迭代进行进化的“学习”方法。进化的每一代中的所有个体的集合称为一个群体。一个群体分为若干个子群体。子群体有两类：优胜子群体(superior group)和临时子群体(

57、temporary group)。优胜子群体记录全局竞争中的优胜者的信息，临时子群体记录全局竞争的中间过程。2公告板公告板(billboard)为个体之间和子群体之间交流信息提供了机会。公告板包含三个基本信息(或称为必要信息)：个体或子群体的序号，动作(action)，得分(score)。动作的描述是与领域有关的，即动作的描述因领域而异。根据需要，还可以包含其它信息，如前若干代的信息。个体的得分是个标量，它是环境对个体动作的评价。这些信息就是个体得到的关于环境的知识。公告板中的信息根据应用的不同可以按不同的要求排序。子群体内的个体在局部公告板(local billboard)张贴各自的信息。全

58、局公告板(global billboard)用于张贴各子群体的信息。3趋同和异化趋同(Similartaxis)和异化(Dissimilation)是MEA重要的概念。下面给出它们的定义。在“学习”初期，个体在解空间中随机散布，计算每个个体的得分。一些得分高的个体成为胜者，并以它们为中心形成子群体。定义1：在子群体范围内，个体为成为胜者而竞争的过程叫做趋同。定义2：一个子群体在趋同过程中，若不再产生新的胜者，则称该子群体已经成熟。当子群体成熟时，该子群体的趋同过程结束。子群体从诞生到成熟的期间叫做生命期。定义3：在整个解空间内，各子群体为成为胜者而竞争，不断地探测解空间中新的点，这个过程叫做异

59、化。异化有两个含义：(1)各子群体进行全局竞争，若一个临时子群体的得分高于某个成熟的优胜子群体的得分，则该优胜子群体被获胜的临时子群体替代，原优胜子群体中的个体被释放；若一个成熟的临时子群体的得分低于任意一个优胜子群体的得分，则该临时子群体被废弃，其中的个体被释放。(2)被释放的个体在全局范围内重新进行搜索并形成新的临时群体。在算法开始时，所有的个体进行全局搜索，并形成若干子群体，即产生初始群体及子群体。 定义1和定义3是从竞争的角度定义的，类似地也可以从解空间的搜索角度进行定义。趋同进行局部搜索，异化进行全局搜索。从另一个角度分析，趋同可以看成是对局部信息开发利用，异化可以看成是全局性的探测

60、。同时，趋同和异化要反复进行，所以也可以看作是MEA的两个算子，两种进化操作。4个体每个个体可以拥有自己的知识，并管理他们。每个个体都有其自己的性格，如有保持自己的成功经验的趋势，或有向其它个体“学习”的趋势。5特征提取系统特征提取系统通过分析个体所包含的特征获取环境信息并利用这些信息指导产生新的个体。思维进化算法系统结构图如图3-1所示。图3-1 思维进化算法系统结构图思维进化算法的基本知识如下：1初始化(1)在解空间均匀散布个体,并计算每个个体的得分。从中选出Ns个得分最高的个体(Ns取决于目标函数最优解的个数)，作为优胜者并将其排序，公布于全局公告板上。以这Ns个个体为中心，服从正态分布

61、，构成Ns个优胜子群体，胜者的得分作为优胜子群体的得分。优胜子群体用来记录全局竞争中优胜者的信息。(2)再从中选出Nt个胜者，以此为中心形成Nt个临时子群体(Nt取25个)。胜者的得分作为临时子群体的得分。临时子群体用来记录全局竞争的中间过程。2趋同趋同发生在每个子群体(优胜和临时子群体)的内部，在局部竞争中寻找局部最优点。在每次趋同操作中都是以胜者为中心，服从正态分布产生新的子群体，每个个体在胜者周围进行搜索，并相互竞争，从中找出新的胜者。胜者的得分作为子群体的得分，并公布于局部公告板上。当子群体的得分得不到进一步的提高、几乎停滞时，认为该子群体成熟。3异化异化是子群体为成为优胜子群体而与其

62、它子群体所进行的一种全局竞争。若某一临时子群体的得分大于任一成熟优胜子群体的得分，则优胜子群体被临时子群体替代；同样，若某一成熟临时子群体得分小于任意优胜子群体的得分，则该临时子群体被放弃。被替代与放弃的子群体在解空间随机产生新的个体，以形成新的临时子群体，参加新一轮的趋同与异化。反复进行趋同与异化，当优胜子群体得分增长趋近于零时，认为算法收敛。此时优胜子群体的优胜者，即为全局最优解。4趋同与异化算法(1)趋同算子描述：a.计算子群体内每一个个体的得分及子群体平均得分；b.搜索得分大于平均得分的个体，即优良个体；c.求取优良模式；d.非优良个体向优良模式学习，得到新的子群体，转a，直到子群体得

63、分得不到进一步改善，认为子群体成熟。(2)异化算子描述：以优胜群体的最大模式为参考，在解空间产生个体作为优胜者，然后以每一个优胜者为中心，形成临时子群体，各临时子群体内进行趋同操作，参与局部竞争。5MEA的框架其中：一个群体分为若干个子群体(Groups)层次结构。公告板为个体间和子群体间信息交流提供了机会。局部公告板是用于子群体内的个体张贴信息。而子群体在全局公告板上张贴信息。每个个体可以拥有自己的知识，并管理他们。每个个体都有其自己的性格，如有保持自己的成功经验的趋势，或有向其他个体学习的趋势。特征提取系统通过分析个体的动作和得分提取环境的特征。MEA只有两个进化操作:趋同、异化。没有单独的选择操作，但是趋同、异化中包含有选择。MEA模仿人类的思维进化过程，将群体划分为若干子群体，提出了“趋同”和“异化”算子。提出MEA的目的是为了解决遗传算法计算量大、早熟、遗传操作的不可预知性以及“勘探”与“开采”功能相互矛盾的等一系列问题4。3.2.2 三个基本机制近二十多年来，人们进行了许多探索，从不同的角度改进GA，但是在提高效率与解决早熟两方面的效果并不理想。对