遗传算法GeneticAlgorithm学习.pptx

《遗传算法GeneticAlgorithm学习.pptx》由会员分享，可在线阅读，更多相关《遗传算法GeneticAlgorithm学习.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/27遗传算法(GA)Darwin(1859):“物竟天择，适者生存”John Holland(university of Michigan,1975)Adaptation in Natural and Artificial System遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。第1页/共49页2023/3/27 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解

2、，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制第2页/共49页2023/3/27局部局部全局全局遗传算法(GA)第3页/共49页2023/3/27We have a dream!We have a dream!I am at the topI am at the topHeight is.Height is.I am not at the top.I am not at the top.My high is better!My high is better!I will c

3、ontinueI will continue遗传算法(GA)GA-第0代第4页/共49页2023/3/27Dead oneDead oneNew oneNew one遗传算法(GA)GA-第1代第5页/共49页2023/3/27Not at the top,Not at the top,Come Up!Come Up!遗传算法(GA)GA-第?代第6页/共49页2023/3/27I am the I am the BESTBEST!遗传算法(GA)GA-第N代第7页/共49页2023/3/27适者生存(Survival of the Fittest)GA主要采用的进化规则是“适者生存”较好的解

4、保留，较差的解淘汰遗传算法(GA)第8页/共49页2023/3/27生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数第9页/共49页2023/3/27遗传算法的基本操作选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体

5、，以某个概率Pc(称为交叉概率，crossvoer rate)交换它们之间的部分染色体。变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。第10页/共49页2023/3/27如何设计遗传算法如何进行编码？如何产生初始种群？如何定义适应函数？如何进行遗传操作(复制、交叉、变异)？如何产生下一代种群？如何定义停止准则？第11页/共49页2023/3/27编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间=0,1L011101001010001001100

6、1001010010001第12页/共49页2023/3/27选择(Selection)选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中 主要思想:适应值较高的染色体体有较大的选择(复制)机会实现1：”轮盘赌”选择(Roulette wheel selection)将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率Ps产生一个在0与总和之间的的随机数m从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m第13页/共49页2023/3/27选择(Selection)设种群的规模为Nxi是i为种群中第i个染色体AC

7、1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色体xi被选概率第14页/共49页2023/3/27选择(Selection)染色体的适应值和所占的比例轮盘赌选择第15页/共49页2023/3/27选择(Selection)随机数234913 386 27所选号码 26 2 51 4所选染色体110000001111000011000111010010染色体编号 1 2 3 4 5 6染色体011101100000100100100110000011适应度 8 152 5 128被选概率0.160.30.040.10.240

8、.16适应度累计 8 23 25 30 42 50染色体被选的概率被选的染色体第16页/共49页2023/3/27选择(Selection)轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。模拟“轮盘赌”算法：(1)r=random(0,1)，s=0，i=0；(2)如果sr，则转(4)；(3)s=s+p(xi)，i=i+1,转(2)(4)xi即为被选中的染色体，输出I(5)结束第17页/共49页2023/3/27选择(Selection)其他选择法：随机遍历抽样(Stoch

9、astic universal sampling)局部选择(Local selection)截断选择(Truncation selection)竞标赛选择(Tournament selection)特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。第18页/共49页2023/3/27交叉(crossover,Recombination)遗传交叉(杂交、交配、有性重组)操作发

10、生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不同，且彼此不同,每个子染色体都带有双亲染色体的遗传基因。第19页/共49页2023/3/27单点交叉(1-point crossover)在双亲的父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代染色体交叉概率Pc 一般范围为(60%,90%)，平均约80%1 11 11 11

11、 11 11 11 11 1父代父代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 0子代子代1 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 11 1交叉点位置交叉点位置第20页/共49页2023/3/27交叉(crossover,Recombination)单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。假如交叉概率Pc 50%,则交配池中50%的染色体(一半染色体)将进行交叉

12、操作，余下的50%的染色体进行选择(复制)操作。GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体第21页/共49页2023/3/27变异(Mutation)以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率Pm 一般介于1/种群规模与1/染色体长度之间，平均约1-2%1 11 10 01 10 01 10 00 0父代父代0 01 10 01 10 01 10 01 1子代子代变异基因变异基因变异基因变异基因第22页/共49页2023/3/27变异(Mutation)比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复

13、群体中失去的多样性多样性方面具有潜在的作用。在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联系，选择操作就越会使群体的遗传多样性损失。等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最优解所需要的。第23页/共49页2023/3/27适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群

14、体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。群体中的每个染色体都需要计算适应值适应函数一般由目标函数变换而成第24页/共49页2023/3/27适应函数(Fitness Function)适应函数常见形式：直接将目标函数转化为适应函数若目标函数为最大化问题：Fitness(f(x)=f(x)若目标函数为最小化问题：Fitness(f(x)=-f(x)

15、缺点:(1)可能不满足轮盘赌选择中概率非负的要求(2)某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。第25页/共49页2023/3/27适应函数(Fitness Function)界限构造法 目标函数为最大化问题其中Cmin为f(x)的最小估计值 目标函数为最小化问题其中Cmaxn为f(x)的最大估计值第26页/共49页2023/3/27停止准则(Termination Criteria)种群中个体的最大适应值超过预设定值种群中个体的平均适应值超过预设定值种群中个体的进化代数超过预设定值第27页/共49页2023/3/27基本步骤(Step

16、 by Step)(1)随机产生初始种群;(2)计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步;(3)按由个体适应值所决定的某个规则选择将进入下一代的个体;(4)按交叉概率Pc进行交叉操作,生产新的个体;(5)按变异概率Pm进行变异操作,生产新的个体;(6)输出种群中适应度值最优的染色体作为问题的满意解或最优解。第28页/共49页2023/3/27流程图(Flow Chart)第29页/共49页2023/3/27基本遗传算法基本遗传算法（Simple Genetic Algorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、

17、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。第30页/共49页2023/3/27SGA伪码描述Procedure Genetic Algorithm beginbegint=0;初始化 P(t);计算 P(t)的适应值;while(不满足停止准则)do begin t=t+1;从P(t-1)中选择 P(t);%selection 重组 P(t);%crossover and mutation 计算 P(t)的适应值;end end第31页/共49页2023/3/27遗传算法的应

18、用函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。第32页/共49页2023/3/27遗传算法的应用组合优化 遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题(Traveling Salesman

19、 Problem,TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem)等方面得到成功的应用。生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。第33页/共49页2023/3/27遗传算法的应用自动控制 遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等

20、。机器人智能控制 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用领域。第34页/共49页2023/3/27遗传算法的应用图象处理和模式识别 图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和

21、自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。第35页/共49页2023/3/27遗传算法的应用遗传程序设计 Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法，基于对一种树形结构所进行的遗传操作来自动生成计算机程序。机器学习 基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。第36页/共49页2023/3/27SGA实例1：函数最值SGA参数

22、:编码方式:二进制码 e.g.00000e.g.000000;0;01101 01101 13;13;11111111113131种群规模:4随机初始群体“转盘赌”选择一点杂交,二进制变异 求函数f(x)=x2的最大值，x为自然数且0 x31.o手工方式完成演示SGA过程第37页/共49页2023/3/27SGA实例1 max x2 :选择操作第38页/共49页2023/3/27SGA实例1 max x2 :交叉操作第39页/共49页2023/3/27SGA实例1 max x2 :变异操作第40页/共49页2023/3/27SGA实例2:连续函数最值求下列函数的最大值：第41页/共49页202

23、3/3/27SGA实例2:编码高精度 编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型)解码算子：:0,1L x,y 染色体长度L决定可行解的最大精度长染色体(慢进化)实数问题：变量z为实数，如何把a1,aL 0,1Lzx,y第42页/共49页2023/3/27SGA实例2:编码设定求解精确到6位小数，因区间长度位2-(-1)=3,则需将区间分为3X106等份。因 2097152221 3X1062224194304。故编码的二进制串长L=22。将一个二进制串(b21b20b0)转化为10进制数：e.g.-1;2 1.627 888 1.627888=-1+3x(1110000000

24、111111000101)2/(222-1)=-1+3x3674053/(222-1)第43页/共49页2023/3/27SGA实例2:初始化种群、适应函数随机初始化种群适应函数 本实例目标函数在定义域内均大于0，且是求函数最大值，故直接引用目标函数作为适应函数：f(s)=f(x)其中二进制串s对于变量x的值。e.g.s1=x1=-0.958 973 适应值:f(s1)=f(x1)=1.078 878 s2=x2=1.627 888 适应值:f(s2)=f(x2)=3.250 650第44页/共49页2023/3/27SGA实例2:遗传操作选择操作(“轮盘赌”选择)交叉操作(单点交叉)交叉前(

25、父):s1=s2=交叉后(子):s1=s2=适应值:f(s1)=f(-0.998 113)=1.940 865 f(s2)=f(1.666 028)=3.459 245 s2的适应值比其双亲个体的适应值高。第45页/共49页2023/3/27SGA实例2:遗传操作变异操作 变异前(父):s2=变异后(子):s2=适应值 f(s2)=f(1.721 638)=0.917 743 比 f(s2)小 变异前(父):s2=变异后(子):s”2=适应值 f(s”2)=f(1.630 818)=3.343 555 比 f(s2)大变异操作有”扰动”作用，同时具有增加种群多样性的效果。第46页/共49页20

26、23/3/27SGA实例2:模拟结果遗传算法的参数:种群规模:50 染色体长度:L=22 最大进化代数:150 交叉概率:Pc=0.25 变异概率:Pm=0.01 第47页/共49页2023/3/27SGA实例2:模拟结果(最佳个体进化情况最佳个体进化情况)世代数染色体编码变量x适应值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.831 6241.842 4161.854 8601.847 5361.853 2901.848 4431.848 6991.850 8971.850 5491.850 5493.534 8063.790 3623.833 2863.842 0043.843 4023.846 2323.847 1553.850 1623.850 2743.850 274第48页/共49页感谢您的观看！第49页/共49页