上海大学毕业设计(论文)
控制还可分为位置式PID控制和增量式PID控制，增量式PID控制不需要累加，误动作影响小，更适合工业生产。
21
上海大学毕业设计(论文)
第三章 遗传算法
3.1 引言
遗传算法（Genetic Algorithms,GA)是基于自然选择和基因遗传学原理的优化搜索方法。它最先是由John Holland于1975年提出的。遗传算法的创立过程有两个研究目的：一是抽象和严谨地解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到工程系统、计算机系统或商业系统等人工系统的设计中。遗传算法在计算机上模拟生物的进化过程和基因的操作，并不需要对象的特定知识，也不需要对象的搜索空间是连续可微的，它具有全局寻优的能力。一些用常规的优化算法有效解决的问题，采用遗传算法寻优技术往往能得到较好的结果。人们常把它用于许多领域的实际问题，如函数优化、自动控制、图像识别、机器学习等。目前，遗传算法正在向其他学科和领域渗透，正在形成遗传算法、神经网络和模糊控制相结合，从而构成一种新型的智能控制系统整体优化的结构形式。本章讨论遗传算法的基本原理、操作流程，模式定理等问题。
3.2 遗传算法概述
3.2.1 遗传算法的发展史
Holland的早期工作主要集中于生物学，控制工程，人工智能等领域中的中一类动态系统的适应性问题，其中适应性概念在环境表现出较好行为和性能的系统结构的渐进改变过程，简称系统的适应过程。Holland认为：通过简单的模拟机制可以描述复杂的适应性现象。因此，Holland试图建立适应过程的一般描述模型，并在计算机上进行模拟试验研究，分析自然系统或者人工系统对环境变化的适应性现象，其中遗传算法仅仅是一种具体的算法形式。
Bremermann，De Jong等人则注重遗传算法应用于参数优化问题，极大的促进了遗传算法的应用。所以，遗传算法既是一种自然进化系统的计算模型，也是一种通用的求解优化问题的适应性搜索方法。
1962年，John Holland在“Outline for a Logic Theory Adaptive Systems”一
22
上海大学毕业设计(论文)
文中，提出了所谓的监控程序的概念，即利用群体进化模拟适应性系统的思想。在这篇文章中尽管它没有给出实现这些思想的具体技术，但却引进了群体，适应值，选择，交叉等基本概念。1966年，Fogel等人也提出了类似的思想，但是其重点是放在变异算子而不是采用交叉算子。1967年，Holland的学生J.D.Bagley通过对跳棋游戏参数的研究，其博士论文中首次提出了“遗传算法”一词。
在20世纪60年代中期至70年代末期，基于自然进化的思想遭到了怀疑和反对。Holland及其数位博士坚持了这一方向的研究。1975年，Holland出版了专著《自然与人工系统中的适应性行为》（Adaptation in Natural and Artificial Systems），该书系统的阐述了遗传算法的基本理论和方法，提出了对遗传算法和理论发展极为重要的模式理论，其中首次确认了选择，交叉，变异等遗传算子，以及遗传算法的隐并行性，并将遗传算法应用于适应性系统模拟，函数优化，机器学习，自动控制等领域。
1975年以后，遗传算法作为函数优化器不但在各个领域的得到了广泛应用，而且还丰富和发展了若干遗传算法的基本理论。1980年，Bethke对函数优化GA进行了研究，包括应用研究和数学分析。Smith在1980年首次提出使用变长位串的概念。这在某种程度上为以后的遗传规划奠定了基础。
1989年，David Goldberg出版了《Genetic Algorithms in Search Optimization and Machine Learning》一书，这是第一本遗传算法的教科书，它是对当时关于遗传算法领域研究工作的全面而系统的总结，因而也成为引用最多的参考书之一。
随着遗传算法研究和应用的不断深入与扩展，1985年，在美国召开了第一届遗传算法国际会议，即ICGA(International Conference on Genetic Algorithm)这次会议是遗传算法发展的重要里程碑，此会以后每隔一年举行一次。
随着Internet技术的发展和普及应用，遗传算法的有关研究单位建立了大量的专题网站，其中最为著名的是由美国海军人工智能应用研究中心建立的GA_Archives检索网站http://www.aic.nrl.navy.mil/galist/它包括了世界范围内的开展遗传算法和进化计算研究的大学和机构，历年来的公开发表的论文和报告，
23
上海大学毕业设计(论文)
有关国际会议消息，典型应用案例和程序的源代码等。
这众多的研究单位和频繁的国际学术活动集中反映了遗传算法的学术意义的应用价值。目前，遗传算法已经成为一个多学科、多领域的重要研究方向。
3.2.2 遗传算法的概念
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质上是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。在这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。
个体或当前近似解被解码为由字母组成的串，即染色体（Chromosome)，使基因（Gene，染色体值）能在表现域决策便利上被惟一地描述。尽管可以使用二进制、整数、实值等，但是在遗传算法表现型上最常见的仍是二进制字符串。
在决策变量域中的染色体表现型被编码后，可以估计种群的个体成员的特性或适应度。通过特征目标函数来估计个体在问题域中的特性。目标函数建立的基础就是在整个繁殖过程中选择成对的个体进行交配。
在复制期间，每个个体均被计算适应度值，它由目标函数给出。这个值用来在选择中偏向更加合适的个体。对整个种群，适应度高的个体具有高的被选中参加交配的概率，而适应度低的个体具有相对低的选中概率。一旦个体计算了适应度值，个体能根据它们的相对适应度从种群中被选中并重组，产生下一代。遗传算子直接操作染色体的基因，使用一般情况下个体的基因代码，产生更适合的个体。重组算子用在一对个体或一组个体中交换基因信息。最简单的重组算子是单点交叉。
交叉进一步的遗传算法称为变异。变异能根据一些概率准则引起个体基因表现型发生变化，在二进制表现型中，变异引起单个位的状态变化，即0变1，
24
上海大学毕业设计(论文)
或者1变0.变异具有阻止局部最优收敛的作用。
在重组和变异后，如果需要，这些个体串随后被解码，进行目标函数评估，计算每个个体的适应度值，个体根据适应度被选择参加交配，并且这个过程继续直到产生子代（Offspring)。在这种方法中，种群中个体的平均性能希望得到提高，好的个体被保存并且相互产生下一代，而低适应度的个体则消失。当一些判定条件满足后，遗传算法则终止，例如，一定的遗传代数、种群的均差或遇到搜索空间的特殊点。
3.2.3 遗传算法的特点
遗传算法通过对参数空间编码并用随机选择作为工具来引导搜索过程朝着更高效的方向发展。同常规优化算法相比，遗传算法有以下特点：
① 遗传算法是对参数的编码进行操作，而非对参数本身。
② 遗传算法从许多点开始并行操作，而非局限于一点，可有效防止搜索过程收敛于局部最优解。
③ 遗传算法通过目标函数来计算适配值，不需导数等其他信息，从而对问题依赖性小。
④ 遗传算法的寻优规则是由概率决定的，而非确定性的，即具有随机操作算子。
3.2.4 遗传算法的基本用语
遗传算法是自然遗传学和计算机科学相互结合渗透而形成的新的计算方法，它经常使用自然进化中的一些基本用语，以下表3.1是遗传学和遗传算法中基本用语对照表。
25