遗传算法基本概念及其在控制工程中的应用 - Read.PPT

关于遗传算法的一般性介绍 报告人:杨再跃 报告时间:2003.1 主要内容 1 GA的起源及发展 2 GA的基本思想 3 GA的几个近亲 4 SGA的实现方法 5 GA的特点和适用范围 6 需要注意的几个问题 7 一些改进后的算法 8 GA在控制工程中的应用 1 GA的起源及发展 1950年，图灵提出可以通过模拟进化和自然选择过程自动生成智能程序。 1960s’~1970s’，基于进化和自然选择思想的各种算法的提出和应用。 1975年，Holland发表Adaptation in Nature and Artificial Systems，完整描述了GA的原理及实现步骤。 1975年，De Jong提出了5个评价GA效率的测试函数。 1987年，Goldberg发表Genetic Algorithms in Search，Optimization and Machine Learning,详细介绍了GA在工程上的应用。 2 GA的基本思想 GA的思想本源是自然界中的“优胜劣汰”现象。各种生物在自然选择的压力下，器官和结构不断演变以适应环境，最终实现从简单到复杂、从不适应到适应的进化过程。 GA中的几个术语。个体：进化的最小单元；种群：个体的集合；个体适应度：评价每个个体优劣的标量值；选择：从种群中根据适应度选取一定数量的个体组成新种群；遗传操作：包括重组和变异两种操作；重组：一对个体按某种方式结合生成一对新个体；变异：单个个体随机发生变化。 2 GA的基本思想 GA是一种模拟自然选择和进化过程来求解问题的计算模型。 GA求解问题的过程：随机产生一个种群，其中的个体代表问题的可行解；根据问题确定评价个体适应度的方式，并对个体赋以适应度值；根据个体适应度选择一定数量的个体参加遗传操作；被选个体通过重组或者变异操作生成新个体；新个体连同以前的个体，按照某种方式保存一部分到下一代。重复前面的步骤，直到满足终止条件，得到最佳个体，即问题的近似最优解。 3 GA的几个近亲及其特点 遗传编程（Genetic Programming），个体为一段程序。 演化策略（Evolution Strategies），只有一个个体，通过变异不断进化。 演化规划（Evolutionary Programming），根据以前的状态估计未来的状态，个体长度不断增加。 硬件演化（Evolvable Hardware），结合PLD实现硬件本身自动地改变结构以适应环境的变化。 4 SGA的实现步骤 4.1 编码 4.2 种群设定 4.3 适应度函数 4.4 选择 4.5 遗传操作 4.6 个体保存方式 4.1 编码 把问题的解转换成GA可以操作的对象的过程叫做编码。 编码是一种将解同个体、将解空间同染色体空间、将表现型同基因型对应起来的映射。 在SGA中，一般直接用二进制数表示问题的解；或者用Gray码表示问题的解。 目前在工程上使用最广泛的是浮点数直接编码方式，这是因为它在概念上更靠近解空间，同时也便于使用封闭的算子。 4.2 种群设定 种群规模（即所包含的个体数目）与问题的有哪些信誉好的足球投注网站空间正相关，一般选取为20～100之间的一个常数。 确定种群规模后，随机初始化种群，即随机产生指定数量的可行个体。 可以通过选择代沟（generation gap）确定选取多少个体参加遗传操作，代沟通常为0.7～0.9之间的常数。 4.3 适应度函数 适应度函数用于根据问题（目标函数）赋给个体相应的适应度值。 常见的几种适应度函数类型：线性定标形式；幂乘形式；排序赋值等。其中以排序赋值使用最为广泛。 4.4 选择 从群体中根据个体适应度依概率选取一部分个体参加遗传操作的过程叫做选择。 选择的个体数量等于种群规模与代沟的乘积。 常用的选择方法有：轮盘赌选择法，期望值法，最优个体选择法，排序选择法，部分放回随机选择法，随机均匀选择法，联赛选择法，排挤法等。 4.5 遗传操作 遗传操作是按概率执行的，它包括重组和变异两部分，可以根据实际情况选择执行两种操作或者其中的某一种操作。 如何确定遗传操作一直是学术界争论的焦点，或者说由于GA针对性太强而无法给出普适性的结论。 总的说来，重组操作趋向于在深度方向进行有哪些信誉好的足球投注网站，变异操作趋向于在广度方向进行有哪些信誉好的足球投注网站。 4.5 遗传操作 重组操作是指将个体两两配对，重新组合生成新个体的过程。 重组操作的设计需要结合编码方式来考虑。例如针对二进制形式的编码，通常是将两个体对应位相互交换而生成新个体，如001和010 → 011和000。习惯上称这种重组方式为交叉，交叉又可以细分为单点交叉、两点交叉和多点交叉。而对于浮点数编码，重组操作通常是将两个个体分别乘以系数后相加，如3.14和4.13 → 3.14× α +4.13× β和3.14× β+4.13× α，通常