清华大学出版社：《智能技术》课程教学资源（PPT课件讲稿）第6章 遗传算法（genetic algorithms，GA）

清华大学出版社 TSINGHUA UNIVERSITY PRESS 普通高校本科计算机专业特色教材精选 曹承志编著 智能技术

智能技术 普通高校本科计算机专业特色教材精选 曹承志 编著

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第6章遗传算法 6.1遗传算法的基本原理 6.2遗传算法的模式理论 6.3遗传算法应用中的一些基本问题 64高级遗传算法 6.5微种群和双种群遗传算法 6.6基于遗传算法的系统在线辨识 6.7基于遗传算法的模糊控制 6.8免疫遗传算法 合

第6章 遗传算法 6.1 遗传算法的基本原理 6.2 遗传算法的模式理论 6.3 遗传算法应用中的一些基本问题 6.4 高级遗传算法 6.5 微种群和双种群遗传算法 6.6 基于遗传算法的系统在线辨识 6.7 基于遗传算法的模糊控制 6.8 免疫遗传算法

清华大学出版社 TSINGHUA UNIVERSITY PRESS 遗传算法 遗传算法（genetic algorithms,简称GA)是人工智能 的重要新分支，是基于达尔文进化论，在微型计算机上模 拟生命进化机制而发展起来的一门新学科。它根据适者生 存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。 对许多用传统数学难以解决或明显失效的非常复杂问题， 特别是最优化问题，GA提供了一个行之有效的新途径。 近年来，由于遗传算法求解复杂优化问题的巨大潜力及其 在工业控制工程领域的成功应用，这种算法受到了广泛的 关注

遗传算法 遗传算法（genetic algorithms,简称GA）是人工智能 的重要新分支，是基于达尔文进化论，在微型计算机上模 拟生命进化机制而发展起来的一门新学科。它根据适者生 存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。 对许多用传统数学难以解决或明显失效的非常复杂问题， 特别是最优化问题，GA提供了一个行之有效的新途径。 近年来，由于遗传算法求解复杂优化问题的巨大潜力及其 在工业控制工程领域的成功应用，这种算法受到了广泛的 关注

清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.1遗传算法的基本原理 6.1.1遗传算法的基本遗传学基础 6.1.2遗传算法的原理和特点 6.1.3遗传算法的基本操作 u

6.1 遗传算法的基本原理 6.1.1 遗传算法的基本遗传学基础 6.1.2 遗传算法的原理和特点 6.1.3 遗传算法的基本操作

清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.1.1遗传算法的基本遗传学基础 遗传算法是根据生物进化的模型提出的一种优化算法。 自然选择学说是进化论的中心内容，根据进化论，生物的 发展进化主要由三个原因，即遗传、变异和选择。 遗传是指子代总是和亲代相似。遗传性是一切生物所 共有的特性，它使得生物能够把它得特性、性状传给后代。 遗传是生物进化的基础。 变异是指子代和亲代有某些不相似的现象，即子代永 远不会和亲代完全一样。它是一切生物所具有的共有特性， 是生物个体之间相互区别的基础。引起变异的原因主要是 生活环境的影响、器官使用的不同及杂交。生物的变异性 为生物的进化和发展创造了条件

6.1.1 遗传算法的基本遗传学基础 遗传算法是根据生物进化的模型提出的一种优化算法。 自然选择学说是进化论的中心内容，根据进化论，生物的 发展进化主要由三个原因，即遗传、变异和选择。 遗传是指子代总是和亲代相似。遗传性是一切生物所 共有的特性，它使得生物能够把它得特性、性状传给后代。 遗传是生物进化的基础。 变异是指子代和亲代有某些不相似的现象，即子代永 远不会和亲代完全一样。它是一切生物所具有的共有特性， 是生物个体之间相互区别的基础。引起变异的原因主要是 生活环境的影响、器官使用的不同及杂交。生物的变异性 为生物的进化和发展创造了条件

清华大学出版社 TSINGHUA UNIVERSITY PRESS 选择是指具有精选的能力，它决定生物进化的方向。 在进化过程中，有的要保留，有的要被淘汰。自然选择是 指生物在自然界的生存环境中适者生存，不适者被淘汰的 过程。通过不断的自然选择，有利于生存的变异就会遗传 下去，积累起来，使变异越来越大，逐步产生了新的物种 生物就是在遗传、变异和选择三种因素的综合作用过 程中，不断地向前发展和进化。选择是通过遗传和变异起 作用的，变异为选择提供资料，遗传巩固与积累选择的资 料，而选择则能控制变异与遗传的方向，使变异和遗传向 着适应环境的方向发展。遗传算法正是吸取了自然生物系 统“适者生存、优胜劣汰”的进化原理，从而使它能够提 供一个在复杂空间中随机搜索的方法，为解决许多传统的 优化方法难以解决的优化问题提供了新的途径

选择是指具有精选的能力，它决定生物进化的方向。 在进化过程中，有的要保留，有的要被淘汰。自然选择是 指生物在自然界的生存环境中适者生存，不适者被淘汰的 过程。通过不断的自然选择，有利于生存的变异就会遗传 下去，积累起来，使变异越来越大，逐步产生了新的物种。 生物就是在遗传、变异和选择三种因素的综合作用过 程中，不断地向前发展和进化。选择是通过遗传和变异起 作用的，变异为选择提供资料，遗传巩固与积累选择的资 料，而选择则能控制变异与遗传的方向，使变异和遗传向 着适应环境的方向发展。遗传算法正是吸取了自然生物系 统“适者生存、优胜劣汰”的进化原理，从而使它能够提 供一个在复杂空间中随机搜索的方法，为解决许多传统的 优化方法难以解决的优化问题提供了新的途径

清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.1.2遗传算法的原理和特点 遗传算法将生物进化原理引入待优化参数形成的编码 串群体中，按着一定的适值函数及一系列遗传操作对各个 体进行筛选，从而使适值高的个体被保留下来，组成新的 群体，新群体包含上一代的大量信息，并且引入了新的优 于上一代的个体。这样周而复始，群体中各个体适值不断 提高，直至满足一定的极限条件。此时，群体中适值最高 的个体即为待优化参数的最优解。正是由于遗传算法独具 特色的工作原理，使它能够在复杂空间进行全局优化搜索， 并且具有较强的鲁棒性；另外，遗传算法对于搜索空间， 基本上不需要什么限制性的假设（如连续、可微及单峰 等)

6.1.2 遗传算法的原理和特点 遗传算法将生物进化原理引入待优化参数形成的编码 串群体中，按着一定的适值函数及一系列遗传操作对各个 体进行筛选，从而使适值高的个体被保留下来，组成新的 群体，新群体包含上一代的大量信息，并且引入了新的优 于上一代的个体。这样周而复始，群体中各个体适值不断 提高，直至满足一定的极限条件。此时，群体中适值最高 的个体即为待优化参数的最优解。正是由于遗传算法独具 特色的工作原理，使它能够在复杂空间进行全局优化搜索， 并且具有较强的鲁棒性；另外，遗传算法对于搜索空间， 基本上不需要什么限制性的假设（如连续、可微及单峰 等）

清华大学出版社 TSINGHUA UNIVERSITY PRESS 遗传算法的特点 同常规划优化算法相比，遗传算法有以下特点： ①遗传算法是对参数的编码进行操作，而非对参 数本身。 ② 遗传算法是从许多点开始并行操作，并非局限 于一点，从而可有效防止搜索过程收敛于局部最 优解 。 ③ 遗传算法通过目标函数计算适值，并不需要其 它推导和附加信息，因而对问题的依赖性较小

遗传算法的特点 同常规划优化算法相比，遗传算法有以下特点： ① 遗传算法是对参数的编码进行操作，而非对参 数本身。 ② 遗传算法是从许多点开始并行操作，并非局限 于一点，从而可有效防止搜索过程收敛于局部最 优解。 ③ 遗传算法通过目标函数计算适值，并不需要其 它推导和附加信息，因而对问题的依赖性较小

清华大学出版社 TSINGHUA UNIVERSITY PRESS ④ 遗传算法的寻优规则是由概率决定的，而非确 定性的。 ⑤ 遗传算法在解空间进行高效启发式搜索，而非 盲目地穷举或完全随机搜索。 ⑥遗传算法对所求解的优化问题没有太多的数学 要求。 ⑦遗传算法具有并行计算的特点，因而可通过大 规模并行计算来提高计算速度

④ 遗传算法的寻优规则是由概率决定的，而非确 定性的。 ⑤ 遗传算法在解空间进行高效启发式搜索，而非 盲目地穷举或完全随机搜索。 ⑥ 遗传算法对所求解的优化问题没有太多的数学 要求。 ⑦ 遗传算法具有并行计算的特点，因而可通过大 规模并行计算来提高计算速度

清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.1.3遗传算法的基本操作 般的遗传算法都包含三个基本操作：复制(reproduction)、 交叉(crossover)和变异(mutation)。 1.复制 复制 (又称繁殖)，是从一个旧种群(old population) 中选择生命力强的个体位串（或称字符串）(individual string)产生新种群的过程。或者说，复制是个体位串根 据其目标函数f(即适值函数)拷贝自己的过程。直观地 讲，可以把目标函数看作是期望的最大效益的某种量度。 根据位串的适值所进行的拷贝，意味着具有较高适值的位 串更有可能在下一代中产生一个或多个子孙。显然，在复 制操作过程中，目标函数（适值）是该位串被复制或被淘汰 的决定因素

6.1.3 遗传算法的基本操作 一般的遗传算法都包含三个基本操作：复制(reproduction)、 交叉(crossover)和变异(mutation)。 1. 复制 复制（又称繁殖），是从一个旧种群（old population） 中选择生命力强的个体位串（或称字符串）（individual string）产生新种群的过程。或者说，复制是个体位串根 据其目标函数f（即适值函数）拷贝自己的过程。直观地 讲，可以把目标函数f看作是期望的最大效益的某种量度。 根据位串的适值所进行的拷贝，意味着具有较高适值的位 串更有可能在下一代中产生一个或多个子孙。显然，在复 制操作过程中，目标函数(适值)是该位串被复制或被淘汰 的决定因素