遗传算法讲稿培训课件

遗传算法算法讲稿稿n n遗传算法遗传算法(Genetic Algorithms(Genetic Algorithms，简称，简称GA)GA)是一种是一种模拟生物遗传和进化过程的计算方法。模拟生物遗传和进化过程的计算方法。n n进化学说的三个方面：进化学说的三个方面：遗传遗传：生物从其父代继承特性或性状的生命现象，即：生物从其父代继承特性或性状的生命现象，即种种瓜得瓜，种豆得豆。瓜得瓜，种豆得豆。遗传保持了物种的稳定遗传保持了物种的稳定。变异变异：一母生九子，九子各不同。：一母生九子，九子各不同。变异的选择和积累是变异的选择和积累是生物多样性生物多样性的根源；的根源；适者生存适者生存：生物之间存在竞争，根据对环境的适应能力，：生物之间存在竞争，根据对环境的适应能力，适者生存。适者生存。遗传算法概述2 2遗传算法讲稿遗传算法讲稿GA 四个基本条件n n1.1.存在由多存在由多个个生物生物个体个体組成的組成的种群种群n n2.2.生物生物个体个体之之间间存在存在着差异着差异，或，或全体全体具有具有多样性多样性n n3.3.生物能生物能够够自我繁殖自我繁殖n n4.4.不同不同个体个体具有不同的具有不同的环境环境生存能力，具有生存能力，具有优良优良基因基因结构结构的的个体个体繁殖能力強，反之則弱繁殖能力強，反之則弱3 3遗传算法讲稿遗传算法讲稿GA -特点n n遗传算法遗传算法以决策变量的编码作为运算对象以决策变量的编码作为运算对象，从而可，从而可以很方便地引入和应用遗传操作算子。传统的优化以很方便地引入和应用遗传操作算子。传统的优化算法往往直接利用决策变量的实际值本身进行优化算法往往直接利用决策变量的实际值本身进行优化计算。计算。n n遗传算法直接遗传算法直接以目标函数值作为搜索信息以目标函数值作为搜索信息，实现比，实现比较方便。传统的优化算法往往不只需要目标函数值，较方便。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，实现困难。标函数无法求导或很难求导的函数，实现困难。4 4遗传算法讲稿遗传算法讲稿GA -特点n n遗传算法同时遗传算法同时进行解空间的多点搜索进行解空间的多点搜索。传统的优化。传统的优化算法往往从解空间的一个初始点开始搜索，这样容算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种进化。这些是遗传算法所特有的一种隐含并行性隐含并行性。n n遗传算法遗传算法使用概率搜索技术使用概率搜索技术。遗传算法属于一种自。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其是以一种概率的方式来进行的，从而增加了其搜索搜索过程的灵活性过程的灵活性。5 5遗传算法讲稿遗传算法讲稿GA的基础术语n n染色体（染色体（ChromosomeChromosome）生物细胞中含有的一生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，种微小的丝状化合物，是遗传物质的主要载体，由多个遗传基因组成。由多个遗传基因组成。n n基因（基因（genegene）也称遗传因子，）也称遗传因子，DNA DNA 链中占有一链中占有一定位置的基本单位。生物的基因数量根据物种不定位置的基本单位。生物的基因数量根据物种不同多少不一，从几个（病毒）到几万个（动物）。同多少不一，从几个（病毒）到几万个（动物）。n n个体个体（individualindividual）指带有染色体特征的实体。）指带有染色体特征的实体。n n种群种群（populationpopulation）一定数量的个体的集合。）一定数量的个体的集合。6 6遗传算法讲稿遗传算法讲稿GA的基础术语n n适应度适应度（fitnessfitness）个体对环境的适应程度）个体对环境的适应程度n n进化进化（evolutionevolution）生物逐渐适应其生存环境，使）生物逐渐适应其生存环境，使得其品质不断提高得其品质不断提高n n选择选择（selectionselection）指决定以一定概率从种群中选）指决定以一定概率从种群中选择若干个体的操作。一般而言，选择的过程是一择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程种基于适应度的优胜劣汰的过程n n复制复制（reproductionreproduction）细胞分裂时，遗传物质）细胞分裂时，遗传物质DNADNA通过复制转移到新的细胞中，新的细胞就继通过复制转移到新的细胞中，新的细胞就继承了旧细胞的基因承了旧细胞的基因7 7遗传算法讲稿遗传算法讲稿GA的基础术语n n交叉交叉（crossovercrossover）两个染色体的某一相同位置）两个染色体的某一相同位置处处DNADNA被切断，其前后两串分别交叉组合形成两被切断，其前后两串分别交叉组合形成两个新的染色体个新的染色体n n变异变异（mutationmutation）在细胞复制时，基因的某个位）在细胞复制时，基因的某个位发生某种突变，产生新的染色体发生某种突变，产生新的染色体n n编码编码（codingcoding）DNADNA中遗传信息按一定的方式排中遗传信息按一定的方式排列，也可看作从表现型到遗传型的映射列，也可看作从表现型到遗传型的映射n n解码解码（decodingdecoding）从遗传型到表现型的映射）从遗传型到表现型的映射8 8遗传算法讲稿遗传算法讲稿GA的三个基本算子复制复制选择选择(Reproduction/Selection)(Reproduction/Selection)n n 依据每一物种的适应程度来决定其在下一依据每一物种的适应程度来决定其在下一代中应被复制或淘汰个数的多少代中应被复制或淘汰个数的多少n n轮盘式选择轮盘式选择n n竞争式选择竞争式选择9 9遗传算法讲稿遗传算法讲稿GA 三个基本算子交叉 交叉式一种提供个体间彼此交换信息的机制，交交叉式一种提供个体间彼此交换信息的机制，交叉过程主要是母代中较优良的染色体作某些基因叉过程主要是母代中较优良的染色体作某些基因的交换，预期产生更优良的后代。一般常见的交的交换，预期产生更优良的后代。一般常见的交叉方式有：叉方式有：（1 1）单点交叉单点交叉(One-point crossover(One-point crossover)（2 2）双点交叉双点交叉(Tail-tail crossover(Tail-tail crossover)（3 3）均匀交叉均匀交叉1010遗传算法讲稿遗传算法讲稿GA 三个基本算子变异 通过突变的方式，使得解可以跳脱单纯的交叉产通过突变的方式，使得解可以跳脱单纯的交叉产生的区域，进而产生新的染色体，变异的过程主生的区域，进而产生新的染色体，变异的过程主要以随机的方式，将染色体的基因位由要以随机的方式，将染色体的基因位由0 0变成变成1 1或或由由1 1变成变成0 0，主要的变异方式有：，主要的变异方式有：（1 1）等位基因突变等位基因突变(Simple Mutation)(Simple Mutation)（2 2）均匀突变均匀突变(Uniform Mutation)(Uniform Mutation)（3 3）非均匀突变非均匀突变(Non-Uniform Mutation)(Non-Uniform Mutation)1111遗传算法讲稿遗传算法讲稿GA的基本流程1212遗传算法讲稿遗传算法讲稿算 例 说 明编码n n求解问题求解问题 max f(x)=xmax f(x)=x2 2 0,310,31 x x取正整数取正整数n n第一步：编码第一步：编码 采用二进制形式采用二进制形式n n我们把变量我们把变量x x编码为编码为5 5位长的二进制无符号位长的二进制无符号整数表示形式整数表示形式 n n 0 00000 0 00000 n n 31 11111 31 11111n n 7 00111 7 00111n n 12 01100 12 011001313遗传算法讲稿遗传算法讲稿算 例 说 明种群生成n n第二步第二步 初始种群的生成初始种群的生成 由于遗传算法的群体型操作需要，所以为遗传操由于遗传算法的群体型操作需要，所以为遗传操作准备了一个由若干初始解组成的初始群体。作准备了一个由若干初始解组成的初始群体。这里我们取群体大小为这里我们取群体大小为4 4，即群体由，即群体由4 4个个体组个个体组成，每个个体通过随机初始化产生成，每个个体通过随机初始化产生 初始群体也称为进化的初始代，即第一代初始群体也称为进化的初始代，即第一代 （first generationfirst generation），初始化后，群体为），初始化后，群体为 01101 11000 01000 10011 01101 11000 01000 10011 1414遗传算法讲稿遗传算法讲稿算 例 说 明适应度评价n n遗传算法用评价函数（适应度函数值）来评估个遗传算法用评价函数（适应度函数值）来评估个体（解）的优劣，并作为以后遗传操作的依据。体（解）的优劣，并作为以后遗传操作的依据。这里这里 我们根据我们根据 f(x)=xf(x)=x2 2 n n在评价个体适应度值大小时，首先要解码，即把在评价个体适应度值大小时，首先要解码，即把基因型个体变成表现型个体（即搜索空间的解）基因型个体变成表现型个体（即搜索空间的解）这里就是二进制到十进制的转换这里就是二进制到十进制的转换 基因型基因型 01101 11000 01000 1001101101 11000 01000 10011 表现型表现型 x x 13 24 8 19 13 24 8 19 f(x)=x f(x)=x2 2 169169 576 64 361576 64 361 （适应值）（适应值）1515遗传算法讲稿遗传算法讲稿算 例 说 明选择n n选择概率选择概率 n n适应度总和适应度总和11701170，平均值，平均值293293n n运用轮盘赌选择结果运用轮盘赌选择结果 n n 1 2 0 11 2 0 1计算结果为 0.14 0.49 0.06 0.311616遗传算法讲稿遗传算法讲稿算 例 说 明选择初始族群初始族群适应值适应值F F(i)(i)复制个数复制个数01110011101961960.180.180.710.711 111000110005765760.520.522.072.072 210001100012892890.260.261.041.041 1001110011149490.040.040.180.180 0初始族群初始族群0111001110110001100010001100010011100111选择后选择后01110011101100011000100011000111000110001717遗传算法讲稿遗传算法讲稿算 例 说 明交叉n n单点交叉为例n n两个染色体 10111001 11001100n n假设交叉点在位置4n n 1011|1001 n n 1100|1100n n 1011 1100n n 1100 10011818遗传算法讲稿遗传算法讲稿算 例 说 明交叉交交叉前叉前配對配對交叉点交叉点交叉后交叉后x xf(x)f(x)01110011102 23 301000010008 8646411000110001 13 31111011110303090090011000110004 41 11100111001252562562510001100013 31 110000100001616256256f=1845 平均适应度值f=4612020遗传算法讲稿遗传算法讲稿算 例 说 明变异变异变异基因基因数数的的决定决定基因总数基因总数变异概率变异概率 =(=(45)0.1=245)0.1=2 有兩個基因將被突有兩個基因將被突变变随机选取染色体进行变异随机选取染色体进行变异随机选取要变异染色体的基因位随机选取要变异染色体的基因位变异变异目的在避免陷入局部最目的在避免陷入局部最优优解解2121遗传算法讲稿遗传算法讲稿算 例 说 明变异n n01000 11001 11110 1000001000 11001 11110 10000n n假设变异基因发生在假设变异基因发生在 第一个染色体的第第一个染色体的第3 3位位和第四个染色体的第二位上和第四个染色体的第二位上n n变异就是把二进制的变异就是把二进制的0 0 变成变成1 1 把把1 1 变成变成0 0n n变异前变异前 01010 000 11001 11110 10000 11001 11110 1000 00 0n n变异后变异后 01011 100 11001 11110 10000 11001 11110 1001 10 02222遗传算法讲稿遗传算法讲稿算 例 说 明变异变异池变异池是否有是否有变异变异变异点变异点变异后变异后ff(x)f(x)0100001000是是3 301011 1000010101001001100111001否否3 3111101111030309009001111011110否否1 1110011100125256256251000010000是是1 11001001 10 01 18 8324324f=1949 平均适应度值f=4872323遗传算法讲稿遗传算法讲稿算 例 说 明进化过程进化进化代数代数染色体染色体x xf(x)f(x)f平均值平均值最佳最佳值值1 101101 11000 01101 11000 01000 1001101000 1001113 24 13 24 8 198 19169 576169 576 64 36164 3611170117029229219192 201100 11001 01100 11001 11110 1001011110 1001012 1312 1330 1830 18144 169144 169900 324900 324 1537153738438430303 310100 11001 10100 11001 11110 1101011110 1101022 2322 2330 2430 24484 529484 529900 576900 5762489248962622 230304 410101 11101 10101 11101 11111 00010 11111 00010 2121 292931 2 31 2 441 841441 841961 4961 42247224756256231312424遗传算法讲稿遗传算法讲稿算 例 说 明终止准则一般而言，遗传算法终止条件有以下几种：一般而言，遗传算法终止条件有以下几种：（1 1）达到最大的进化代数；达到最大的进化代数；（2 2）所求的解达到可接受的范围；所求的解达到可接受的范围；（3 3）连续几代最佳解无变化或变化非常微小连续几代最佳解无变化或变化非常微小；（4 4）达到最大的运算时间。达到最大的运算时间。2525遗传算法讲稿遗传算法讲稿遗传算法-参数配置n n种群数量种群数量 视具体问题和解空间的维数，问题越复杂，维数视具体问题和解空间的维数，问题越复杂，维数越高，种群数量要求越大，一般取越高，种群数量要求越大，一般取n n遗传运算的终止进化代数遗传运算的终止进化代数 根据问题的复杂程度，一般取为根据问题的复杂程度，一般取为100500100500n n交叉率交叉率 一般选取范围在一般选取范围在 0.40.990.40.99之间之间 n n变异率变异率 一般选取范围在一般选取范围在 0.0010.10.0010.1之间之间现代一般采用自适应变化的交叉率和变异率现代一般采用自适应变化的交叉率和变异率2626遗传算法讲稿遗传算法讲稿遗传算法应用n n遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。2727遗传算法讲稿遗传算法讲稿遗传算法应用n n组合优化：遗传算法是寻求组合优化问题满意解组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合的最佳工具之一，实践证明，遗传算法对于组合优化问题中的优化问题中的NPNP完全问题非常有效。完全问题非常有效。2828遗传算法讲稿遗传算法讲稿遗传算法应用n n生产调度问题：生产调度问题在很多情况下所建生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。解决复杂调度问题的有效工具。2929遗传算法讲稿遗传算法讲稿遗传算法应用n n自动控制：遗传算法已经在自动控制领域中得到自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。行人工神经网络的结构优化设计和权值学习等。3030遗传算法讲稿遗传算法讲稿遗传算法应用n n机器人学：机器人是一类复杂的难以精确建模的机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。法的一个重要应用领域。n n机器学习：基于遗传算法的机器学习，在很多领机器学习：基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。于人工神经网络的网络结构优化设计。3131遗传算法讲稿遗传算法讲稿遗传算法应用n n图象处理：图像处理是计算机视觉中的一个重要图象处理：图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很算法在这些图像处理中的优化计算方面得到了很好的应用。好的应用。3232遗传算法讲稿遗传算法讲稿遗传算法应用n n人工生命：人工生命是用计算机、机械等人工媒人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。命现象的重要理论基础。3333遗传算法讲稿遗传算法讲稿Thanks for your attention！3434遗传算法讲稿遗传算法讲稿