人工智能_第三章_遗传算法、蚁群算法、粒子群算法.ppt

1、2020/8/13，1，第三章遗传算法，蚁群算法和粒子群算法，2020/8/13，2，3.1遗传算法，2020/8/13，3，生物在自然界中的生存繁殖受到启发，人们对生物各种生存特性的遗传算法(Genetic Algorithm，简称GA )是这种生物行为的修正计算机仿真中备受关注的重要成果。 基于生物遗传和进化过程的修正算机仿真，遗传算法使各种人工系统具有很好的适应能力和优化能力。 遗传算法参考的生物学基础是生物的遗传和进化。 2020/8/13，4，4，人们还没有完全弄清遗传和进化的奥秘，没有完全掌握其机制，也没有完全了解染色体编码和解码过程的细节，但遗传和进化的以下几个特征是人们共同的：

2、 (1)生物的所有遗传信息都包括其染色(3)生物繁殖过程是通过其基因的复制过程完成的： (4)同源染色体之间的交叉和染色体的变异产生新的物种，使生物呈现新的性状。 (5)环境适应性好的基因和染色体比适应性差的基因和染色体有更多的机会遗传给下一代。 2020/8/13，5，5，遗传算法是模拟生物自然环境力的遗传和进化过程而形成的自适应全局优化概率搜索算法。 美国密执安大学的Holland教授最初提倡的，是从60年代关于自然和人工适应系统的研究开始的。 70年代De Jong根据遗传算法的思想在修正算法机上进行了许多纯数值函数最优化修正算法实验。 在系列研究的基础上，80年代Goldberg进行了

3、归纳，形成了遗传算法的基本框架。2020/8/13，6，6，一、遗传算法概述、表达式中的决策变量、f(X )是目标函数、下面两个表达式是约束条件、u是基本空间、r是u的子集。 对于求函数最大值的最优化问题(与求函数最小值相同)，满足约束条件的解x称为可执行解，集合r表示由满足约束条件的所有解组成的一个集合，并且可以被描述为被称为可执行解集合的数学校正像素模型。 这些关系如图所示。 2020/8/13、7、2020/8/13、8对于上述优化问题，目标函数和限制条件的种类多，有线性的也有非线性的。 有些是连续的，有些是离散的，有些是单峰的，有些是多峰的。 随着研究的进展，人们认识到在很多复杂的情况

4、下不可能完全正确地求出其最佳解，也不现实，求出其近似最佳解或满足解是主要的着眼点。 2020/8/13，9，9，求最佳解或近似最佳解的方法，(1)列举法。 列举可行解集合内的所有可行解，求出正确的最佳解。 对于连续函数，利用该方法需要先进行离散化处理，有可能产生离散误差而不能获得最佳解。 同时，列举空间较大时，该方法求解效率低，有时连目前最先进的修正算法工具也无法求解。 (2)启发式算法。 查找可以生成可执行解的启发式规则，以找到最佳解或近似最佳解。 该方法求解效率很高，但每个要求解的问题必须找到特有的启发式规则，这个启发式规则缺乏通用性，不适合其他问题。 搜索算法，2020/8/13，10，

5、(3)搜索算法。 求出在可执行解集合的子集内进行搜索操作的搜索算法，以找出问题的最佳解或近似最佳解。 该方法不一定能得到问题的最佳解，但如果适当利用一些启发知识，近似解的质量和求解效率的平衡就会很好。遗传算法为解决这类问题提供了有效的方法和共同的框架，开发了新的全局优化搜索算法。 在遗传算法中，n维决定向量用由n个符号Xi (nl，2，n )组成的符号串x来表示，将各个Xi视为一个基因，将其所有可能的值称为等位基因，但染色体的长度n都是固定的在一些情况下，这里的等位基因可以是一组整数，可以是在一定范围内的实数值或者是纯符号。 最简单的等位基因由0和l两个整数组成。 对应的染色体可以表示为二进制

6、符号串。 2020/8/13、12，该编码形成的序列形式x是个体的基因型，与之相对应的x值是个体的表现型。 通常个体的表现型和其基因型是一对一对应的，但基因型和表现型也有可能是多对一的关系。 染色休x也被称为个体x。 每个个体x，必须按照一定的规则决定适应度的个体的适应度与其对应的个体表现型x的目标函数值相关联，x越接近目标函数的优点适应度越大，相反，其适应度越小则越小。 遗传算法中，决策变量x构成了问题的解空间。 问题最优解的搜索通过染色体x的搜索过程进行，由所有的染色体x构成问题的搜索空间。 2020/8/13，13，生物进化以集团为主体。 与此相对，遗传算法的运算对象是由m个个体组成的集

7、合，被称为集团。 与生物一代的自然进化过程相似，遗传算法的演算过程也是一个重复的过程，第t代的集合标记为P(t )，经过一代的遗传和进化得到第t 1代的集合，它们也是由多个个体组成的集合，标记为P(t 1)。 该组经过不断的遗传和进化操作，每次都按照优胜劣化的规则将适应度高的个体更多地遗传到下一代，最终得到组中优良的个体x，其对应的表现型x能否达到或接近问题的最佳解X*。 生物进化过程主要是由染色体间的交叉和变异构成的，遗传算法中最优解的搜索过程也模仿生物的这一进化过程，即所谓的遗传算子作用于群体P(t )，通过进行下一代群体P(t ) 2020/8/13，14，选择：根据各个体的适应度，从第

8、t代集合P(t )中选择几个优秀的个体遗传到下一代集合P(t 1)。 交叉(crossover ) :随机组合集团P(t )内的各个体，对于各个个体，以某种概率(交叉概率，称为crossover rate )交换它们之间的染色体的一部分。 变异(mutation ) :对于群体P(t )的各个个体，改变某个概率(变异概率，称为mutation rate )或基因座的基因值是另一个等位基因。 2020/8/13，15，2，遗传算法的运算过程，使用上述3种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下：步骤1 :初始化。 设置进化代数计数器t0设置最大进化代数t随机生成m个个

9、体作为初始集合P(0)，步骤2 :个人评价。 修正集团P(t )中各个体的适应度。 步骤3 :选择运算。 使选择的操作符作用于组。 2020/8/13，16，步骤4 :交叉运算。 让交叉算子作用于集团。 步骤5 :变异运算。 使变异作用于集团。 群P(t )经过选择、交叉、变异运算得到下一代群P(t 1)。 步骤6 :结束条件判断。 如果是tT，则进入tt 1、步骤2。 如果是tT，则把在进化过程中得到的具有最大适应度的个体作为最佳解输出，结束修正算法。 2020/8/13、17、3，遗传算法的特征，(1)遗传算法将决策变量的代码作为运算对象。以往的优化算法通常直接利用决定变量的实际值本身来进

10、行优化补正运算，但遗传算法不是直接利用决定变量的值，而是以某种形式的决定变量的代码为运算对象。 这种决策变量的编码处理方式，我们在优化修正算法过程中可以借鉴生物学中的染色体和基因等概念，模仿自然界中生物的遗传和进化等机制，简单地应用遗传操作算子。 特别是，只对于没有数值概念或者数值概念很难的代码概念的优化问题，编码处理方式显示出独自的优势。 (2)遗传算法将直接目标函数值作为搜索信息。 另外，在现有的优化算法中，不仅目标函数值，而且大多需要目标函数的导数值等其他辅助信息。 遗传算法仅通过使用从目标函数值转换而来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，不需要目标函数值等其他辅助信息

11、。 对于许多目标函数无法求导数或难以求导数、不存在导数的函数的优化问题、组合优化问题等，此特性在应用遗传算法时很方便。 那是因为函数避免了求导数的障碍。 并且，通过原样利用目标函数值和个体适应度，能够将搜索范围集中在适应度高的部分搜索空间，从而可提高搜索效率。 (3)遗传算法同时使用多个搜索点的搜索信息。 传统的优化算法是从解空间的一个初始点开始最优解的这一代搜索过程，由于一个搜索点提供的搜索信息结果不太多，所以搜索效率不高，有时使搜索过程陷入局部最优解而停滞不前。 遗传算法不是从单一个体开始，而是从多个个体组成的初期集团开始最佳解的搜索过程。 对这个组的选择、交叉、变异等的运算，形成下一代的

12、组，其中含有很多组信息。 实际上相当于检索更多的点，因为这些信息可以避免不需要检索的点的检索，这是遗传算法特有的隐式并行性。 (4)遗传算法使用概率搜索技术。 传统的优化算法通常使用确定性搜索方法，从一个搜索点向另一个搜索点的转换与确定性转换方法相关，这种确定性可能永远不能达到搜索的最大优点，并且算法的应用范围也受到限制。 遗传算法是一种自适应概率搜索技术，其选择、交叉、变异等运算都是随机进行的，提高了搜索过程的灵活性。 尽管这种概率特性也会使群体产生适应度不高的个体，但随着进化过程的进行，新的群体总是会产生许多优良的个体，实践和理论已经证明了遗传算法在一定条件下总是以概率1收敛于问题的最优解

13、。 当然，交叉概率和变异概率等残奥参数也影响算法的搜索效果和搜索效率，所以如何选择遗传算法的残奥参数是其应用中的重要问题。 另一方面，与其他算法相比，遗传算法的鲁棒性尽量降低残奥仪表对其搜索效果的影响。 2020/8/13、21、4，遗传算法的发展，遗传算法始于对生物系统的纠错机仿真研究。 从上世纪40年代开始，有学者开始研究利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物进化过程模拟、遗传过程模拟等研究。 进入60年代以后，美国密执安大学的Ho11and教授及其学生们受到了这种生物模拟技术的启发，创造了适用于基于生物遗传和进化机制的复杂系统优化修正算法的自适应概率优化技术遗传算法。

14、 以下是一些重要人物在遗传算法发展过程中所作的主要贡献。2020/8/13，22，1，JHHolland 60年代，Ho11and在研究、修订人工适应系统时，可以参考生物遗传机制，用集体的方法进行适应搜索，并充分认识到交叉、变异等运算策略在适应系统中的重要性70年代初，Ho11and教授提出了遗传算法的基本定理模型定理(schema Theorem )，为遗传算法奠定了理论基础。 模式定理表明群体中优良个体(良模式)的样本数呈指数规律增加，从而理论上保证了遗传算法是求最佳可行解的优化过程。 1975年，Ho11and出版了第一个系统描述遗传算法和人工适应系统的专业自然系统和人工系统适应性(ad

15、aptationinnaturalandartificialsystem )。 80年代，霍尔兰教授实现了第一个基于遗传算法的机器学习系统分类器系统(C1assifier system，简称CS )，开发了基于遗传算法的机器学习新概念，为分类器系统构建了完整的框架。 2020/8/13，23，2，JDBagley 1967年，Ho11and的学生Bagley在博士论文中首次提出了“遗传算法”一词，并发表了关于遗传算法应用的首篇论文。 他开发了复制、交叉、变异、显性、重排等遗传算子，个体编码采用了二倍体的编码方法。 这些与现在遗传算法中使用的算子和方法类似。 他还敏锐地意识到在遗传算法执行的非阶

16、段可以使用不同的选择率，有助于防止遗传算法的早熟现象，建立了自适应遗传算法的概念。 2020/8/13，24，3，KADe Jong l975年，De Jong在其博士论文中结合模式定理进行了大量纯数值函数优化修正实验，建立了遗传算法机制，得出了重要且指导性的结论。 例如，对于50100个规模的群体，经过l020代的演化，遗传算法可找到具有高概率的最佳或近似最佳解。 他推荐了适用于许多优化问题的遗传算法的残奥仪表，并构建了著名的德琼五函数测试平台，定义了评价遗传算法性能的在线和离线指标。 4、DJDe Jong 1989年，De Jong出版了专业检索、优化和机器学习的遗传冲击法(Genetic Algorithms in Search，优化和机器学习)。 本系统总结了遗传算法的主要研究成果，全面而完整地阐述了遗传算法的基本原理及其应用。 这本书为现代遗传算法奠定了科学基础，引起了众多研究和发展遗传算法的学者的关注。2020/8/13、25、5、LDavis 1991年，Davis编辑出版了一本遗传算法手册，书中描述了遗传算法在科学校订、工程技术和社会经济中的体现6JRKoza 1992年，Koza将遗传算法应用于校正算法程序的优化设置校正和自动生成，提出了遗传编程(Genetic Programming，简称GP )