1、Introduction of Artificial Intelligence第第 6 章章 遗传算法及其应用遗传算法及其应用教材：教材： 王万良王万良人工智能导论人工智能导论（第（第3版）版） 高等教育出版社高等教育出版社第6章遗传算法及其应用o遗遗传传算算法法(GA)是是一一类类借借鉴鉴生生物物界界自自然然选选择择和和自自然然遗遗传传机机制制的的随随机机搜搜索索算算法法，非非常常适适用用于于处处理理传传统统搜搜索索方方法法难难以以解解决决的的复复杂杂和和非非线线性性优优化化问问题题。遗遗传传算算法法可可广广泛泛应应用用于于组组合合优优化化、机机器器学学习习、自自适适应应控控制制、规规划划设
2、设计计和和人人工工生生命命等等领领域域，是是21世世纪纪有有关关智智能能计计算中的重要技术之一。算中的重要技术之一。o本本章章首首先先详详细细介介绍绍遗遗传传算算法法的的基基本本算算法法，然然后后介介绍绍双双倍倍体体、双双种种群群、自自适适应应等等比比较较典典型型的的改改进进遗遗传传算算法法，最最后后简简单单介介绍绍了了遗遗传传算算法法在在生生产产调调度度中中的的应应用用。在在此此基基础础上上，读读者者可可以以进进一一步步学学习习遗遗传传算算法法以以及及其其他进化算法的内容。他进化算法的内容。 2第6章遗传算法及其应用o6.1 遗传算法的产生与发展遗传算法的产生与发展 o6.2 遗传算法的基本
3、算法遗传算法的基本算法 o6.3 遗传算法的改进算法遗传算法的改进算法 o6.4 遗传算法的应用遗传算法的应用3第6章遗传算法及其应用6.1 遗传算法的产生与发展遗传算法的产生与发展 o6.2 遗传算法的基本算法遗传算法的基本算法 o6.3 遗传算法的改进算法遗传算法的改进算法 o6.4 遗传算法的应用遗传算法的应用46.1遗传算法的产生与发展 遗遗传传算算法法（geneticalgorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。5
4、6.1遗传算法的产生与发展6.1.1 遗传算法的生物背景遗传算法的生物背景6.1.2 遗产算法的基本思想遗产算法的基本思想6.1.3 遗产算法的发展历史遗产算法的发展历史6.1.4 设计遗产算法设计遗产算法的基本原则与内容的基本原则与内容66.1.1遗传算法的生物学背景o适适者者生生存存：最最适适合合自自然然环环境境的的群群体体往往往往产产生生了了更更大大的的后后代代群群体。体。 o生物进化的基本过程：生物进化的基本过程：染染色色体体(chromosome)：生生物物的遗传物质的主要载体。的遗传物质的主要载体。基基因因(gene)：扩扩展展生生物物性性状状的的遗遗传传物物质质的的功功能能单单元
5、元和和结结构单位。构单位。基基因因座座（locus）：染染色色体体中中基因的位置。基因的位置。等等位位基基因因（alleles）：基基因因所取的值。所取的值。76.1.2遗传算法的基本思想生物遗传概念生物遗传概念遗产算法中的应用遗产算法中的应用适者生存适者生存目标值比较大的解被选择的可能性大目标值比较大的解被选择的可能性大个体（个体（Individual）解解染色体（染色体（Chromosome） 解的编码（字符串、向量等）解的编码（字符串、向量等）基因（基因（Gene）解的编码中每一分量解的编码中每一分量适应性（适应性（Fitness）适应度函数值适应度函数值群体（群体（Population
6、）根根据据适适应应度度值值选选定定的的一一组组解解（解解的的个个数数为群体的规模）为群体的规模）婚配（婚配（Marry）交交叉叉（Crossover）选选择择两两个个染染色色体体进进行行交叉产生一组新的染色体的过程交叉产生一组新的染色体的过程变异（变异（Mutation）编码的某一分量发生变化的过程编码的某一分量发生变化的过程86.1.2遗传算法的基本思想 遗传算法的基本思想：遗传算法的基本思想： 在在求求解解问问题题时时从从多多个个解解开开始始，然然后后通通过过一一定定的的法法则进行逐步迭代以产生新的解。则进行逐步迭代以产生新的解。96.1.3遗传算法的发展历史o1962年，Fraser提出
7、了自然遗传算法。o1965年，Holland首次提出了人工遗传操作的重要性。o1967年，Bagley首次提出了遗传算法这一术语。o1970年，Cavicchio把遗传算法应用于模式识别中。o1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。o1975年，美国J.Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。o20世纪80年代以后，遗传算法进入兴盛发展时期。106.1.4遗传算法设计的基本内容 编码方案编码方案：怎样把优化问题的解进行编码。怎样把优化问题的解进行编码。适应度函数适应度
8、函数：怎样根据目标函数构建适应度函数。怎样根据目标函数构建适应度函数。选择策略选择策略：优胜劣汰。优胜劣汰。控控制制参参数数：种种群群的的规规模模、算算法法执执行行的的最最大大代代数数、执行不同遗传操作的概率等。执行不同遗传操作的概率等。遗传算子遗传算子：选择、交叉、变异选择、交叉、变异。算算法法终终止止准准则则：规规定定一一个个最最大大的的演演化化代代数数，或或算算法在连续多少代以后解的适应值没有改进。法在连续多少代以后解的适应值没有改进。11第6章遗传算法及其应用o6.1 遗传算法的产生与发展遗传算法的产生与发展 6.2 遗传算法的基本算法遗传算法的基本算法 o6.3 遗传算法的改进算法遗
9、传算法的改进算法 o6.4 遗传算法遗传算法的应用的应用126.2遗传算法的基本算法o遗传算法的五个基本要素遗传算法的五个基本要素：n参数编码n初始群体的设定n适应度函数的设计n遗传操作设计n控制参数设定136.2遗传算法的基本算法6.2.1 编码编码6.2.2 群体设定群体设定6.2.3 适应度函数适应度函数6.2.4 选择选择6.2.5 交叉交叉6.2.6 变异变异6.2.7 遗传算法遗传算法的一般步骤的一般步骤146.2.1编码 1. 位串编码位串编码一一维维染染色色体体编编码码方方法法：将问题空间的参数编码为一维排列的染色体的方法。二二进进制制编编码码：用若干二进制数表示一个个体，将原
10、问题的解空间映射到位串空间B=0，1上，然后在位串空间上进行遗传操作。（1） 二进制编码二进制编码156.2.1编码 (1) 二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。 缺点：缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：0111116：10000要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。166.2.1编码 1. 位串编码位串编码（2） Gray 编码编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。 二
11、进制串 Gray 二进制编码 Gray编码Gray编码 二进制编码 176.2.1编码 2. 实数编码实数编码 采用实数表达法不不必必进进行行数数制制转转换换，可直接在解的表现型上进行遗传操作。 多多参参数数映映射射编编码码的的基基本本思思想想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。 多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围有不同的串长度和参数的取值范围。 181.初始种群的产生初始种群的产生6.2.2群体设定 （1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（
12、2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。 192. 种群规模的确定种群规模的确定6.2.2群体设定 模模式式定定理理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。 群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。 群体规模太大，计算复杂。 201.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法6.2.3适应度函数 若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则将目标函数转换为求最大值
13、的形式将目标函数转换为求最大值的形式, ,且保证函数值非负！且保证函数值非负！ 若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则212.适应度函数的尺度变换适应度函数的尺度变换 在遗传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺欺 骗骗 问问 题题（deceptiveproblem）。 6.2.3适应度函数 过过早早收收敛敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。 停停滞滞现现象象：改变原始适应值的比例关系，以提高个体之间的竞争力。 适应度函数的尺尺度度变变换换（fitness scaling）或
14、者定定标标：对适应度函数值域的某种映射变换。 222.适应度函数适应度函数的尺度变换的尺度变换( (续）续） （1）线性变换：6.2.3适应度函数 满足满足最小适应度值非负 232.适应度函数适应度函数的尺度变换的尺度变换( (续）续） （2）幂函数变换法： 6.2.3适应度函数 （3）指数变换法：246.2.4选择 1. 个体选择概率分配方法个体选择概率分配方法选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。 256.2.4选择 1
15、. 个体选择概率分配方法个体选择概率分配方法（1）适适应应度度比比例例方方法法（fitness proportional model）或蒙特卡罗法或蒙特卡罗法（Monte Carlo） 各个个体被选择的概率和其适应度值成比例。 个体 被选择的概率为： 266.2.4选择 1. 个体选择概率分配方法个体选择概率分配方法（2） 排序方法排序方法 （rank-based model）线性排序：J.E.Baker 群体成员按适应值大小从好到坏依次排列： 个体 按转盘式选择的方式选择父体276.2.4选择 1. 个体选择概率分配方法个体选择概率分配方法（2） 排序方法排序方法 （rank-based m
16、odel）非线性排序：Z.Michalewicz 将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：286.2.4选择 1. 1.个体选择概率分配方法个体选择概率分配方法（2） 排序方法排序方法 （rank-based model） 可用其他非线性函数来分配选择概率，只要满足以下条件： 296.2.4选择 2. 选择个体方法选择个体方法（1）转盘赌选择转盘赌选择（roulettewheelselection） 按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。 产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。 第1轮产生一个随机数：0.81 第2轮产生一个随机数：0.32 306.2.4选择 2. 选择个体方法选择个体方法（2）锦标赛选择方法锦标赛选择方法（tournament selection model） 锦锦标标赛赛选选择择方方法法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。 随随机机竞竞争争方方法法（stochastictournament）：每次按赌轮选
