第13章 遗传算法,13.1 遗传算法概要 13.2 Genetic Algorithm Toolbox,13.1 遗传算法概要,13.1.1 遗传算法模型 13.1.2 遗传算法的特点 13.1.3 遗传算法的发展 13.1.4 遗传算法的应用 13.1.5 基本遗传算法 13.1.6 遗传算法的模式定理,13.1.1 遗传算法模型,(1)选择(Selection):根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。 (2)交叉(Crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，Crossover Rate)交换它们之间的部分染色体。 (3)变异(Mutation):对群体P(t)中的每一个个体，以某一概率(称为变异概率，Mutation Rate)改变某一个或一些基因座上基因值为其他的等位基因。,13.1.2 遗传算法的特点,(1)遗传算法以决策变量的编码作为运算对象。 (2)遗传算法直接以目标函数值作为搜索信息。 (3)遗传算法同时进行解空间的多点搜索。 (4)遗传算法使用概率搜索技术。,13.1.3 遗传算法的发展,20世纪60年代，美国密植安大学的Holland教授及其学生们受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统计算优化的自适应概率优化技术遗传算法。下面是在遗传算法的发展进程中一些关键人物所作出的一些主要贡献。,1. J.H.Holland,20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然与人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。,2. J.D.Bagley,1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法类似。,3. K.A.De,1975年，De 在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。他推荐了在大多数优化问题中都比较适用的遗传算法参数，还建立了著名的De 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。,4. D.J.Goldberg,1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。,5. L.Davis,1991年，Davis编辑出版了遗传算法手册，书中包含了遗传算法在科学计算、工程技术和社会经济中的大量应用实例，该书为推广和普及遗传算法的应用起到了重要的指导作用。,6. J.R.Koza,1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。,13.1.4 遗传算法的应用,(1)函数优化。 (2)组合优化。 (3)生产调度问题。 (4)自动控制。 (5)机器人学。 (6)图像处理。 (7)人工生命。 (8)遗传编程。 (9)机器学习。,(1)函数优化。,函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而用遗传算法却可以方便地得到较好的结果。,(2)组合优化。,遗传算法是寻求组合优化问题满意解的最佳工具之一。实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。,(3)生产调度问题。,生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,(4)自动控制。,遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计，基于遗传算法的参数辨识，基于遗传算法的模糊控制规则的学习，利用遗传算法进行人工神经网络的结构优化设计和权值学习等。,(5)机器人学。,机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。,(6)图像处理。,图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理的优化计算方面得到了很好的应用。,(7)人工生命。,人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,(8)遗传编程。,Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。,(9)机器学习。,基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。,13.1.5 基本遗传算法,1.本遗传算法的构成要素 2.基本遗传算法的实现 3.遗传算法的应用步骤,1.本遗传算法的构成要素,(1)染色体编码方法。 (2)个体适应度评价。 (3)遗传算子。 (4)基本遗传算法的运行参数。 (5)基本遗传算法的形式化定义。,2.基本遗传算法的实现,在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。,3.遗传算法的应用步骤,(1)确定决策变量及其各种约束条件。 (2)建立优化模型。 (3)确定表示可行解的染色体编码方法。 (4)确定解码方法。 (5)确定个体适应度的量化评价方法。 (6)设计遗传算子。,13.1.6 遗传算法的模式定理,1.模式与模式空间 2.模式生存模型 3.模式定理,1.模式与模式空间,图 13-1,2.模式生存模型,3.模式定理,通过以上关于三个遗传算子对生存模式数量的影响分析，可以得出如下“模式定理”：在选择、交叉、变异算子的作用下，那些低阶、定义长度短、超过群体平均适应值的模式的生存数量，将随着迭代次数的增加以指数规律增长。 这就是由Holland提出的模式定理，称之为遗传算法进化动力学的基本原理。,13.2 Genetic Algorithm Toolbox,13.2.1 函数概述 13.2.2 函数使用说明及示例 13.2.3 函数参数设置 13.2.4 遗传算法M文件自动生成,13.2.1 函数概述,图 13-2,13.2.2 函数使用说明及示例,(1)编写目标函数GAobjfun1.m (2)约束函数GaConfun.m (3)在MATLAB的命令窗口(Command Window)输入gatool调用Genetic Algorithm Toolbox(见图13-3)。 (4)输入目标函数与约束条件(见图13-4) (5)迭代过程函数图(见图13-5) (6)算法迭代过程控制及计算结果(见图13-7),图 13-3,13.2.2 函数使用说明及示例,图 13-4,13.2.2 函数使用说明及示例,图 13-5,13.2.2 函数使用说明及示例,图 13-6,13.2.2 函数使用说明及示例,图 13-7,13.2.2 函数使用说明及示例,13.2.3 函数参数设置,(1)种群设置(见图13-8) (2)适应度评分方法(见图13-9) (3)选择策略(见图13-10) (4)繁殖策略(见图13-11) (5)停止条件(见图13-12) (6)其他参数设置(见图13-13),(1)种群设置(见图13-8),图 13-8,(2)适应度评分方法(见图13-9),图 13-9,(3)选择策略(见图13-10),图 13-10,(4)繁殖策略(见图13-11),图 13-11,(5)停止条件(见图13-12),图 13-12,(6)其他参数设置(见图13-13),图 13-13,13.2.4 遗传算法M文件自动生成,在Genetic Algorithm toolFileGenerate M-file可以生成该求解问题的M文件，比如命名为GADemo1.m，存在指定工作目录下，以后可以随时调用。,