第7章[1]遗传算法概要.ppt

遗传算法,模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。,什么是遗传算法,遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。,遗传算法的起源,遗传算法最早由美国密歇根大学的Holland教授提出，起源于上世纪60年代对自然和人工自适应系统的研究。上世纪70年代，DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，上世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。,遗传算法的应用,函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,遗传算法的应用,组合优化。遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。,遗传算法的应用,生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,遗传算法的应用,自动控制。遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。,遗传算法的应用,机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。,遗传算法的应用,图象处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。,遗传算法的应用,人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,基本遗传算法的基本步骤,基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,基本遗传算法的框图,初始化种群(t=0),计算适应度的值,选择操作t=t+1,遗传操作(交叉、变异）,结束,终止条件,SGA的步骤：,初代种群的生成根据算法规模，选择N个具有随机染色体的个体。在二进制情况下，即生成规定长度的位串形式编码。例如，设某数的取值范围是A，B，用t位长的二进制码来表示该数，可将B-A分成2t-1等份，即000000000000=0A000000000001=1A+111111111111=2t-1B其中，,假设某一个个体的编码是：x：xtxt-1xt-2x2x1则它对应的实数为：,2.适应度的计算,按照预先确定的适应函数对各个个体xi，计算其相应的适应函数的值f(xi)。,3.终止条件的测试,满足算法停止的最简单的两个条件：完成了预先给定的进化代数则停止；群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。,4.选择操作,从第t代中选择N个进入t+1代的个体。选择按比例选择方式进行，即“转轮盘”。,比例选择的具体执行过程：,先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；,比例选择的具体执行过程：,最后再根据个体总数N，来决定各个个体进入下一代的个数。其中，Ni是个体Xi进入下一代的期望个数，是平均适应度。,例如，某种群有四个个体X1-X4，,其适应度如下表所示：,5.遗传操作,交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。例如，有两个8位的二进制码个体：1000111011011001根据随机产生的交叉位数，如3，进行低3位的交换。得到10001001和11011110这就是它们的后代。,变异操作,变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。例如，某个码长为8位二进制的个体，10100110根据随机产生的变异位数，如5，改变第5位的值，由0变1。得到10110110,基本遗传算法的运行参数,基本遗传算法有下述4个运行参数需要提前设定：种群大小N，即群体中所含个体数目，一般取为20100；遗传运算的终止进化代数T，一般取为100500；交叉概率Pc，一般取为0.40.99；变异概率Pm，一般取为0.00010.1。,简单函数最优化举例,利用SGA算法，在区间-6.4,6.3上求下列函数的最大值。,各参数的设定,设定种群的规模N=10，交叉率pc=0.6，变异率pm=0.006。用二进制编码表示种群中的每一个染色体，来代表变量x的实数值。矢量的长度取决于本题所要求的精度，取小数点后1位。这样-6.4，6.3的区间将被均匀分为个等长的区间。由于27=128，所以码长7位。,假设某一个个体的编码是：x：x7x6x5