《现代智能优化算法遗传算法课件》由会员分享，可在线阅读，更多相关《现代智能优化算法遗传算法课件（40页珍藏版）》请在金锄头文库上搜索。
1、现代智能优化算法遗传算法华北电力大学输配电技术研究所刘自发2008年2月1 1a a现代智能优化算法遗传算法华北电力大学输配电技术研究所1a简 介1995 1995 毕业于东北电力学院，获学士学位毕业于东北电力学院，获学士学位20002000年毕业于东北电力学院，获硕士学位年毕业于东北电力学院，获硕士学位20052005年毕业于天津大学，获博士学位年毕业于天津大学，获博士学位20072007年年Univeristy of Strathclyde Univeristy of Strathclyde 博士后博士后2 2 a a简 介1995 毕业于东北电力学院，获学士学位2a现代智能优化算法遗传算
2、法禁忌算法蚁群算法粒子群算法细菌算法混沌算法TSGAACOPSOBCCOA混沌算法DE3 3 a a现代智能优化算法遗禁蚁粒细混TSGAACOPSOBCCOA混遗传算法（Genetic Algorithm, GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它是由美国Michigan大学的J. Holland教授于1975年首先提出的。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制等领域，是21世界有关智能计算中的关键技术之一。 4 4 a a遗传算法（Ge
3、netic Algorithm, GA），是模GA 四个基本条件1.存在由多个生物个体組成的种群2.生物个体之间存在着差异，或全体具有 多样性3.生物能够自我繁殖4.不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力強，反之則弱5 5 a aGA 四个基本条件1.存在由多个生物个体組成的种群5aGA - 特点遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目
4、标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。6 6 a aGA - 特点遗传算法以决策变量的编码作为运算对象。传统GA - 特点遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。遗传算法使用概率搜索技术 。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总
5、是以概率1收敛于问题的最优解。7 7 a aGA - 特点遗传算法同时进行解空间的多点搜索。传统的优达尔文1858年用自然选择来解释物种起源和生物的进化，其自然选择学说包括以下三个方面1 遗传 种瓜得瓜，种豆得豆。生物有了这个特征，物种才能稳定存在；2 变异 一母生九子，九子各不同。变异的选择和积累是生物多样性的根源；3 适者生存 具有适应性变异的个体被保留下来，通过一代代生存环境的选择作用，物种一代代进化，演变为新的物种8 8 a a达尔文1858年用自然选择来解释物种起源和生物的进化，其自然GA的基础术语染色体（Chromosome） 生物细胞中含有的一种微小的丝状化合物。是遗传物质的主要
6、载体，由多个遗传基因组成DNA & RNA in the chromosome基因 （gene）也称遗传因子，DNA 或RNA长链中占有一定位置的基本单位。生物的基因数量根据物种不同多少不一，从几个（病毒）到几万个（动物）。9 9 a aGA的基础术语染色体（Chromosome） 生物细胞中含有GA的基础术语基因座 （locus）染色体中基因的位置表现型 （phenotype）由染色体决定性状的外部表现基因型 （genetype）与表现型密切相关的基因组成个体（individual）指染色体带有特征的实体种群（population）一定数量个体的集合1 10 0 a aGA的基础术语基因座
7、（locus）染色体中基因的位置10aGA的基础术语适应度（fitness）个体对环境的适应程度进化（evolution）生物逐渐适应其生存环境，使得其品质不断提高选择（selection）指决定以一定概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程复制（reproduction）细胞分裂时，遗传物质DNA通过复制转移到新的细胞中，新的细胞就继承了旧细胞的基因1 11 1 a aGA的基础术语适应度（fitness）个体对环境的适应程度1GA的基础术语交叉（crossover）两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体变
8、异（mutation）在细胞复制时，基因的某个位发生某种突变，产生新的染色体编码（coding）DNA中遗传信息按一定的方式排列，也可看作从表现型到遗传型的映射解码（decoding）从遗传型到表现型的映射1 12 2 a aGA的基础术语交叉（crossover）两个染色体的某一相同GA的三个基本算子复制选择(Reproduction / Selection) 依据每一物种的适应程度来决定其在下一代中应被复制或淘汰个数的多少轮盘式选择竞争式选择1 13 3 a aGA的三个基本算子复制选择(Reproduction / GA 三个基本算子交叉 交叉式一种提供个体间彼此交换信息的机制，交叉过程
9、主要是母代中较优良的染色体作某些基因的交换，预期产生更优良的后代。一般常见的交叉方式有：（1）单点交叉(One-point crossover)（2）双点交叉(Tail-tail crossover) （3）均匀交叉1 14 4 a aGA 三个基本算子交叉 交叉式一种提供个体间彼此交换GA 三个基本算子变异 通过突变的方式，使得解可以跳脱单纯的交叉产生的区域，进而产生新的染色体，变异的过程主要以随机的方式，将染色体的基因位由0变成1或由1变成0，主要的变异方式有：（1）等位基因突变(Simple Mutation)（2）均匀突变(Uniform Mutation)（3）非均匀突变(Non-U
10、niform Mutation)1 15 5 a aGA 三个基本算子变异 通过突变的方式，使得解可以跳脱GA的基本流程根据问题编码，并初始化种群计算群体适应度选择操作交叉操作变异操作满足收敛条件否N输出计算结果Y1 16 6 a aGA的基本流程根据问题编码，并初始化种群计算群体适应度选择操算 例 说 明编码求解问题求解问题 max f(x) = xmax f(x) = x2 2 0,310,31 x x取正整数取正整数第一步：编码第一步：编码 采用二进制形式采用二进制形式我们把变量我们把变量x x编码为编码为5 5位长的二进制无符号整位长的二进制无符号整数表示形式数表示形式 0 00000
11、 0 00000 31 11111 31 11111 7 00111 7 00111 12 01100 12 011001 17 7 a a算 例 说 明编码求解问题 max f(x) =算 例 说 明种群生成第二步第二步 初始种群的生成初始种群的生成 由于遗传算法的群体型操作需要，所以为遗传操作由于遗传算法的群体型操作需要，所以为遗传操作准备了一个由若干初始解组成的初始群体。准备了一个由若干初始解组成的初始群体。 这里我们取群体大小为这里我们取群体大小为4 4，即群体由，即群体由4 4个个体组成，个个体组成，每个个体通过随机初始化产生每个个体通过随机初始化产生 初始群体也称为进化的初始代，即
12、第一代初始群体也称为进化的初始代，即第一代 （first generationfirst generation），初始化后，群体为），初始化后，群体为 01101 11000 01000 10011 01101 11000 01000 10011 1 18 8 a a算 例 说 明种群生成第二步 初始种群的生成18算 例 说 明适应度评价遗传算法用评价函数（适应度函数值）来评估个体（解）的优劣，并作为以后遗传操作的依据。这里 我们根据 f(x) = x2 在评价个体适应度值大小时，首先要解码，即把基因型个体变成表现型个体（即搜索空间的解） 这里就是二进制到十进制的转换 基因型 01101 11
13、000 01000 10011 表现型 x 13 24 8 19 f(x) = x2 169 576 64 361 （适应值）1 19 9 a a算 例 说 明适应度评价遗传算法用评价函数（适应度函算 例 说 明选择选择概率选择概率 适应度总和适应度总和11701170，平均值，平均值293293运用轮盘赌选择结果运用轮盘赌选择结果 1 2 0 1 1 2 0 1计算结果为 0.14 0.49 0.06 0.312 20 0 a a算 例 说 明选择选择概率 计算结果为 20a算 例 说 明选择初始族群初始族群適應值適應值E(i)E(i)複製個數複製個數01110011101961960.18
14、0.180.710.711 111000110005765760.520.522.072.072 210001100012892890.260.261.041.041 1001110011149490.040.040.180.180 0初始族群初始族群0111001110110001100010001100010011100111选择后选择后01110011101100011000100011000111000110002 21 1 a a算 例 说 明选择初始族群適應值E(i)複製個數01算 例 说 明交叉单点交叉为例两个染色体 10111001 11001100假设交叉点在位置4 1011
15、|1001 1100|1100 1011 1100 1100 10012 22 2 a a算 例 说 明交叉单点交叉为例22a算 例 说 明交叉0111001110110001100011000110001000110001选择后的结果配对情况 1 和 2 配对 3 和4 配对 01110 11000 11000 10001交叉点选择 第一对 位置3，第二对 位置1交叉前 01|110 1100|0 11|000 1000|1交叉后 01 000 1100 1 11 110 1000 02 23 3 a a算 例 说 明交叉01110110001100010算 例 说 明交叉交配池交配池配對配
16、對交叉点交叉点 交叉后交叉后x xf(x)f(x)01110011102 23 301000010008 8646411000110001 13 31111011110303090090011000110004 41 11100111001252562562510001100013 31 110000100001616256256f=1845 平均适应度值f=4612 24 4 a a算 例 说 明交叉交配池配對交叉点交叉后xf(x)0算 例 说 明变异变异基因数的决定基因总数变异概率 = (45)0.1=2 有兩個基因將被突變随机选取染色体进行变异随机选取要变异染色体的基因位变异目的在避免陷
17、入局部最优解2 25 5 a a算 例 说 明变异变异基因数的决定25a算 例 说 明变异01000 11001 11110 10000假设变异基因发生在 第一个染色体的第3位和第四个染色体的第二位上变异就是把二进制的0 变成1 把1 变成0变异前 01000 11001 11110 10000变异后 01100 11001 11110 100102 26 6 a a算 例 说 明变异01000 11001 算 例 说 明变异变异池变异池是否有是否有变异变异变异点变异点变异后变异后 f ff(x)f(x)0100001000是是3 301011 100001010100100110011100
18、1否否3 3111101111030309009001111011110否否1 1110011100125256256251000010000是是1 11001001 10 01818324324f=1949 平均适应度值f=4872 27 7 a a算 例 说 明变异变异池是否有变异变异点变异后ff算 例 说 明进化过程进化进化代数代数染色体染色体x xf(x)f(x) f f平均值平均值最佳最佳值值1 101101 11000 01101 11000 01000 1001101000 1001113 24 13 24 8 198 19169 576169 576 64 36164 3611
19、170117029229219192 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 5762489248962262230304 410101 11101 10101 11101 11111 0001011111 00010 21
20、29292231 31 2 2 441 841 841442961 961 4 42247224756256231312 28 8 a a算 例 说 明进化过程进化代数染色体xf(x)f平算 例 说 明终止准则一般而言，遗传算法终止条件有以下几种：（1）达到最大的进化代数；（2）所求的解达到可接受的范围；（3）连续几代最佳解无变化或变化非常微小；（4）达到最大的运算时间。2 29 9 a a算 例 说 明终止准则一般而言，遗传算法终止条件有以遗传算法-参数配置种群数量 视具体问题和解空间的维数 问题越复杂，维数越高，种群数量要求越大遗传运算的终止进化代数 根据问题的复杂程度，一般取为10050
21、0交叉率 一般选取范围在 0.40.99之间 变异率 一般选取范围在 0.0010.1之间现代一般采用自适应变化的交叉率和变异率3 30 0 a a遗传算法-参数配置种群数量30a遗传算法应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。3 31 1 a a遗传算法应用遗传算法提供了一种求解复杂系统优化问题的通用框遗传算法应用组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。3 32 2 a a遗传算法应用组合
22、优化：遗传算法是寻求组合优化问题满意解的最遗传算法应用生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。3 33 3 a a遗传算法应用生产调度问题：生产调度问题在很多情况下所建立起遗传算法应用自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。3 34 4 a a遗传算法应用自动控制：遗传算法
23、已经在自动控制领域中得到了很遗传算法应用机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。机器学习：基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。3 35 5 a a遗传算法应用机器人学：机器人是一类复杂的难以精确建模的人工遗传算法应用图象处理：图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些
24、误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。3 36 6 a a遗传算法应用图象处理：图像处理是计算机视觉中的一个重要研究遗传算法应用人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。3 37 7 a a遗传算法应用人工生命：人工生命是用计算机、机械等人工媒体模遗传算法在电力系统中的应用电力系统无功优化电力系统规划配电网络重构电力系统负荷预测（和神经网络结合）电力市场故障诊断参数辨识3 38 8 a a遗传算法在电力系统中的应用电力系统无功优化38a遗传算法在电力系统中的应用机组经济出力电力系统滤波器优化设计电压稳定分析发电计划稳定控制发电机励磁器控制状态估计3 39 9 a a遗传算法在电力系统中的应用机组经济出力39aEnd谢谢大家遗传算法4 40 0 a a遗传算法40a
