现代智能优化算法遗传算法.ppt

《现代智能优化算法遗传算法.ppt》由会员分享，可在线阅读，更多相关《现代智能优化算法遗传算法.ppt（40页珍藏版）》请在三一办公上搜索。

1、现代智能优化算法遗传算法,华北电力大学输配电技术研究所刘自发2008年2月,简 介,1995 毕业于东北电力学院，获学士学位2000年毕业于东北电力学院，获硕士学位2005年毕业于天津大学，获博士学位2007年Univeristy of Strathclyde 博士后,现代智能优化算法,遗传算法,禁忌算法,蚁群算法,粒子群算法,细菌算法,混沌算法,TS,GA,ACO,PSO,BC,COA,混沌算法,DE,遗传算法（Genetic Algorithm,GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它是由美国Michigan大学的J.Holland教授于1975年首先提出的。其

2、主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制等领域，是21世界有关智能计算中的关键技术之一。,GA 四个基本条件,1.存在由多个生物个体組成的种群2.生物个体之间存在着差异，或全体具有 多样性3.生物能够自我繁殖4.不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力強，反之則弱,GA-特点,遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，

3、从而可以很方便地引入和应用遗传操作算子遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。,GA-特点,遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论

4、都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。,达尔文1858年用自然选择来解释物种起源和生物的进化，其自然选择学说包括以下三个方面,1 遗传 种瓜得瓜，种豆得豆。生物有了这个特征，物种才能稳定存在；2 变异 一母生九子，九子各不同。变异的选择和积累是生物多样性的根源；3 适者生存 具有适应性变异的个体被保留下来，通过一代代生存环境的选择作用，物种一代代进化，演变为新的物种,GA的基础术语,染色体（Chromosome）生物细胞中含有的一种微小的丝状化合物。是遗传物质的主要载体，由多个遗传基因组成DNA&RNA in the chromosome基因（gene）也称遗传因子，D

5、NA 或RNA长链中占有一定位置的基本单位。生物的基因数量根据物种不同多少不一，从几个（病毒）到几万个（动物）。,GA的基础术语,基因座（locus）染色体中基因的位置表现型（phenotype）由染色体决定性状的外部表现基因型（genetype）与表现型密切相关的基因组成个体（individual）指染色体带有特征的实体种群（population）一定数量个体的集合,GA的基础术语,适应度（fitness）个体对环境的适应程度进化（evolution）生物逐渐适应其生存环境，使得其品质不断提高选择（selection）指决定以一定概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于

6、适应度的优胜劣汰的过程复制（reproduction）细胞分裂时，遗传物质DNA通过复制转移到新的细胞中，新的细胞就继承了旧细胞的基因,GA的基础术语,交叉（crossover）两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体变异（mutation）在细胞复制时，基因的某个位发生某种突变，产生新的染色体编码（coding）DNA中遗传信息按一定的方式排列，也可看作从表现型到遗传型的映射解码（decoding）从遗传型到表现型的映射,GA的三个基本算子,复制选择(Reproduction/Selection)依据每一物种的适应程度来决定其在下一代中应被复制或淘汰个

7、数的多少轮盘式选择竞争式选择,GA 三个基本算子交叉,交叉式一种提供个体间彼此交换信息的机制，交叉过程主要是母代中较优良的染色体作某些基因的交换，预期产生更优良的后代。一般常见的交叉方式有：（1）单点交叉(One-point crossover)（2）双点交叉(Tail-tail crossover)（3）均匀交叉,GA 三个基本算子变异,通过突变的方式，使得解可以跳脱单纯的交叉产生的区域，进而产生新的染色体，变异的过程主要以随机的方式，将染色体的基因位由0变成1或由1变成0，主要的变异方式有：（1）等位基因突变(Simple Mutation)（2）均匀突变(Uniform Mutation

8、)（3）非均匀突变(Non-Uniform Mutation),GA的基本流程,根据问题编码，并初始化种群,计算群体适应度,选择操作,交叉操作,变异操作,满足收敛条件否,N,输出计算结果,Y,算 例 说 明编码,求解问题 max f(x)=x2 0,31 x取正整数第一步：编码 采用二进制形式我们把变量x编码为5位长的二进制无符号整数表示形式 0 00000 31 11111 7 00111 12 01100,算 例 说 明种群生成,第二步 初始种群的生成 由于遗传算法的群体型操作需要，所以为遗传操作准备了一个由若干初始解组成的初始群体。这里我们取群体大小为4，即群体由4个个体组成，每个个体通

9、过随机初始化产生 初始群体也称为进化的初始代，即第一代（first generation），初始化后，群体为 01101 11000 01000 10011,算 例 说 明适应度评价,遗传算法用评价函数（适应度函数值）来评估个体（解）的优劣，并作为以后遗传操作的依据。这里 我们根据 f(x)=x2 在评价个体适应度值大小时，首先要解码，即把基因型个体变成表现型个体（即搜索空间的解）这里就是二进制到十进制的转换 基因型 01101 11000 01000 10011 表现型 x 13 24 8 19 f(x)=x2 169 576 64 361（适应值）,算 例 说 明选择,选择概率 适应度总和

10、1170，平均值293运用轮盘赌选择结果 1 2 0 1,计算结果为 0.14 0.49 0.06 0.31,算 例 说 明选择,算 例 说 明交叉,单点交叉为例两个染色体 10111001 11001100假设交叉点在位置4 1011|1001 1100|1100 1011 1100 1100 1001,算 例 说 明交叉,选择后的结果,配对情况 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 0,

11、算 例 说 明交叉,f=1845 平均适应度值f=461,算 例 说 明变异,变异基因数的决定基因总数变异概率=(45)0.1=2 有兩個基因將被突變随机选取染色体进行变异随机选取要变异染色体的基因位变异目的在避免陷入局部最优解,算 例 说 明变异,01000 11001 11110 10000假设变异基因发生在 第一个染色体的第3位和第四个染色体的第二位上变异就是把二进制的0 变成1 把1 变成0变异前 01000 11001 11110 10000变异后 01100 11001 11110 10010,算 例 说 明变异,f=1949 平均适应度值f=487,算 例 说 明进化过程,算 例

12、 说 明终止准则,一般而言，遗传算法终止条件有以下几种：（1）达到最大的进化代数；（2）所求的解达到可接受的范围；（3）连续几代最佳解无变化或变化非常微小；（4）达到最大的运算时间。,遗传算法-参数配置,种群数量 视具体问题和解空间的维数 问题越复杂，维数越高，种群数量要求越大遗传运算的终止进化代数 根据问题的复杂程度，一般取为100500交叉率 一般选取范围在 0.40.99之间 变异率 一般选取范围在 0.0010.1之间现代一般采用自适应变化的交叉率和变异率,遗传算法应用,遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用

13、于很多学科。下面列举一些遗传算法的主要应用领域。,遗传算法应用,组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。,遗传算法应用,生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,遗传算法应用,自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优

14、化设计和权值学习等。,遗传算法应用,机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。机器学习：基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。,遗传算法应用,图象处理：图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。,遗传算法应用,人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,遗传算法在电力系统中的应用,电力系统无功优化电力系统规划配电网络重构电力系统负荷预测（和神经网络结合）电力市场故障诊断参数辨识,遗传算法在电力系统中的应用,机组经济出力电力系统滤波器优化设计电压稳定分析发电计划稳定控制发电机励磁器控制状态估计,End谢谢大家,遗传算法,