遗传算法ppt学习.pptx

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

1、目录目录1、智能优化算法 2、基本遗传算法 3、遗传算法特点4、遗传算法的数学基础5、遗传算法的收敛性分析6、遗传算法应用举例 7、遗传算法小结 第1页/共66页1 1、智能优化算法、智能优化算法 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。第2页/共66页常用的智能优化算法常用的智能优化算法（1）遗传算法 （Genetic Algorithm，简称GA）（2）模拟退火算法 （Simulated Annealing，简称SA）（3）禁忌搜索算法

2、 （Tabu Search，简称TS）第3页/共66页智能优化算法的特点智能优化算法的特点智能优化算法的特点智能优化算法的特点它们的共同特点：都是从任一组解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。第4页/共66页遗传算法起源遗传算法起源遗传算法是由美国Michigan大学的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。第5页/共66页遗传算法的搜索机制遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交

3、叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从候选解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。第6页/共66页2 2、基本遗传算法、基本遗传算法基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。第7页/共66页基本遗传算法的组成基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、

4、变异）（4）运行参数第8页/共66页SGA的框图的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次第9页/共66页染色体及其编码染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串,所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命科学中所称的生物体的表现型(phenotype),而

5、其编码即“染色体”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示,而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象,则我们就可以用它的二进制数串1001作为它的染色体编码。第10页/共66页基因型：1000101110110101000111 n n表现型：0.637197 编码解码个体（染色体）基因第11页/共66页适应度与适应度函数适应度与适应度函数遗遗传传算算法法对对一一个个个个体体（解解）的的好好坏坏用用适适应应度度函函数数值值来来评评价价，适适应应度度函函数数值值越越大大，解解的的质质量量越越好好。适应度(fitness)就是借鉴

6、生物个体对环境的适应程度,而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitness function)就是问题中的全体对象与其适应度之间的一个对应关系,即对象集合到适应度集合的一个映射。它它一一般般是是定定义义在在论论域域空空间间上上的的一一个个实实数数值值函函数数。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。说明：“论域”是数数理理逻逻辑辑中的概念。“在一个逻辑系统中，所有的个体组成的集合，称为个体域，亦称论域。”第12页/共66页种群种群(population)SGASGA采采用用随随机机方方法法生生成成若若干干

7、个个个个体体的的集集合合，该该集集合合称称为为初初始始种种群群。初初始始种种群群中中个个体体的的数数量量称称为为种种群群规规模。模。或种群就是模拟生物种群而由若干个染色体组成的群体,它一般是整个论域空间的一个很小的子集。第13页/共66页遗传操作遗传操作遗传算法中有三种关于染色体的运算（遗遗传传算算子子）:选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(genetic operator)。第14页/共66页选择选择-复制算子和选择概率复制算子和选择概率选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算,就是从种群中选择适应

8、度较高的染色体进行复制,以生成下一代种群。选择-复制的通常做法是,对于一个规模为N 的种群S,按每个染色体xiS 的选择概率P(xi)所决定的选中机会,分N 次从S中随机选定N 个染色体,并进行复制。这里的选择概率P(xi)的计算公式为 Note:复制即为个体被选中并遗传到下一代；第15页/共66页其中,f f 为适应度函数,f(xi)为xi 的适应度。可以看出,染色体xi被选中的概率就是其适应度f(xi)所占种群中全体染色体适应度之和的比例。显然,按照这种选择概率定义,适应度越高的染色体被随机选定的概率就越大,被选中的次数也就越多,从而被复制的次数也就越多。相反,适应度越低的染色体被选中的次

9、数也就越少,从而被复制的次数也就越少。如果把复制看做染色体的一次换代的话,则这就意味着适应度越高的染色体其后代也就越多,适应度越低的染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰的自然选择法则。第16页/共66页SGA选择算子选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。第17页/共66页轮盘赌选择又称轮盘赌选择又称比例选择算子比例选择算子，它的基本思想是：，它的基本思想是

10、：各个个体被选中的概率与其适应度函数值大小成各个个体被选中的概率与其适应度函数值大小成正比。正比。第18页/共66页上述按概率选择的方法可用一种称为赌轮的原理来实现。即做一个单位圆,然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图1所示)。这样,每次选择时先转动轮盘,当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。例如,假设种群S中有4个染色体:s1,s2,s3,s4,其选择概率依次为:0.11,0.45,0.29,0.15,则它们在轮盘上所占的份额如图1中的各扇形区域所示。图1 赌轮选择示例 第19页/共66页在算法中赌轮选择法可用下面的过

11、程来模拟:在0,1区间内产生一个均匀分布的伪随机数r。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率,其计算公式为：第20页/共66页一个染色体xi被选中的次数,可以用下面的期望值e(xi)来确定：其中f 为种群S中全体染色体的平均适应度值。第21页/共66页交叉交叉(crossover)算子算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换两个染色体某些位上的基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主

12、要方法。SGA中交叉算子采用单点交叉算子。第22页/共66页例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即：则得新串s1=01000101,s2=10011011。s1和s2可以看做是原染色体s1和s2的子代染色体。交叉交叉(crossover)算子算子单点交叉运算：单点交叉运算：交叉前：交叉前：00000|00000|011100000000100000111000000001000011100|11100|0000011111100010100000111111000101交叉后：交叉后：00000|00000|000001111110001010000

13、011111100010111100|11100|0111000000001000001110000000010000交叉点交叉点第23页/共66页变异变异(mutation)算子算子变异(mutation)亦称突变,就是改变染色体某个(些)位上(基因座)的基因。是依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。第24页/共66页基本位变异算子基本位变异

14、算子基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。第25页/共66页基本位变异算子的执行过程基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点变异点第26页/共66页运行参数运行参数（1）M ：种群规模(20-100)（2）T ：遗传运算的终止进化代数(100-500)（3）Pc ：交叉概率(0.4-0.9)（4）Pm：变异概

15、率(0.001-0.01)参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc。由于生物繁殖时染色体的交叉是按一定的概率发生的,因此参加交叉操作的染色体也有一定的比例,而交叉率也就是交叉概率。变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm。由于在生物的繁衍进化过程中,变异也是按一定的概率发生的,而且发生概率一般很小,因此变异率也就是变异概率。第27页/共66页SGA的框图的框图产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交

16、叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次第28页/共66页基本遗传算法流程说明：步1 在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2 随机产生U中的N个染色体s1,s2,sN，组成初始种群S=s1,s2,sN，置代数计数器t=1；步3 计算S中每个染色体的适应度f(si)；步4 若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；第29页/共66页步6

17、 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；第30页/共66页需要说明的是,在应用遗传算法解决实际问题时,还需给出结构模式的表示方案、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串,字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。第31

18、页/共66页3 3、遗传算法的特点、遗传算法的特点（1）GA搜索群体中的点是并行,而不是单点；（2）GA使用概率变换规则,而不是确定的变换规则;（3）适应度函数不受连续、可微等条件的约束，适用范围很广。只需要影响搜索方向的目标函数和相对应的适应度函数;(4)GA使用编码参数集,而不是自身的参数集;第32页/共66页4 4、遗传算法的数学基础、遗传算法的数学基础（1）模式定理(Pattern Theorem)（2）积木块假设(Building Block Hypothesis)第33页/共66页模式模式 模式是指种群个体基因串中的相似样板，它是一种用来描述基因串中某些位置上具有结构相似性的0、1

19、字符串集合的方法。在二进制编码中，基于三值字符集(0,1,*)的字符串所产生的能描述具有某些结构相似性的0,1字符串集的字符串称为模式.符号*代表任意字符，即 0 或者 1。模式示例：*0001描述了具有”0001”特征的所有字符串,即(00001,10001);第34页/共66页两个定义两个定义 定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3。O(011*1*)=4;O(0*)=1 note:一个模式阶数越高，其样本数就越少,因而确定性就越高 定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(1

20、0*1)=4;(0*)=0 第35页/共66页模式的阶和定义距的含义模式的阶和定义距的含义 模式的阶用来反映不同模式间确定性的差异，一个模式阶数越高，其样本数就越少,因而确定性就越高。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。第36页/共66页模式定理模式定理 模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中将以指数级增长。(GA必要条件)模式定理保证了较优模式（遗传算法的较优解）的样本数目呈指数级增长，为解释遗传算法机理提供了数学基础。第37页/共66页模式定理模式定理 从模式定理可

21、看出，有高平均适应度、短定义距、低阶的基因模式，其样本在子代里获得至少以指数增长的数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义距的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。第38页/共66页积木块假设积木块假设 积木块假设：阶数低、短定义距、适应度高的模式（此类模式称为积木块此类模式称为积木块），在遗传算子作用下相互结合，能生成阶数高、长度长、适应度高的模式,可最终接近全局最优解。与积木块一样,一些好的模式在遗传算子作用下相互拼搭、结合,产生适应度更高的串,从而找到了更优的可行解,这正是积木块假设所揭示的内容.第39页/共66页

22、S1AAS2S3CCS4BBS5S6S7AAS8BB初始初始种群种群S1AAS2BBS3AACCS4BBS5S6CCS7AABBS8第二第二代种代种群群积木块：AA BB CC第40页/共66页S1AAS2BBS3AABBCCS4S5S6BBS7AACCS8第三代种群第三代种群第41页/共66页模式定理保证了较优模式(遗传算法的较优解)的样本数呈指数增长，从而满足了寻找最优解的必要条件,即遗传算法存在着寻找到全局最优解的可能性；积木块假设则指出,GA具备找到全局最优解的能力,即积木块在遗传算子的作用下，能生成阶数高、长度长、适应度高的模式,最终生成全局最优解。小小 结结第42页/共66页5.5

23、.遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解；其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。第43页/共66页种群规模对收敛性的影响 通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。第44页/共66页选择操作对收敛性的影响 选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保留策略，即将父代群体中最佳个体保留下来，不参

24、加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。1.轮盘赌2.随机竞争选择(按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的选中，如此反复，直到选满为止)3.最优保留策略(当前种群中适应度最高的个体不参与交叉和变异操作，而是用它来替换掉本代种群中经交叉、变异等操作后所产生的适应度最低的个体，保证算法终止时得到的最后结果是历代出现过得最高适应度个体)4.5.第45页/共66页交叉概率对收敛性的影响 交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作

25、很少进行，从而会使搜索停滞不前，造成算法的不收敛。第46页/共66页变异概率对收敛性的影响 变异操作是对种群模式的扰动，有利于增加种群的多样性变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。概率太大则会使遗传算法成为随机搜索算法。第47页/共66页第48页/共66页遗传算法的本质 遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的

26、方向进化，最终得到问题的最优解。第49页/共66页6.6.遗传算法应用举例 例例1.利用遗传算法求解区间0,31上的二次函数y=x2的最大值；【分分析析】可以看出,只要能在区间0,31中找到函数值最大的点a,则函数y=x2的最大值也就可以求得。于是,原问题转化为在区间0,31中寻找能使y取最大值的点a的问题。显然,对于这个问题,任一点x0,31都是可能解,而函数值f(x)=x2也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看,区间0,31就是一个(解)空间,x就是其中的个体对象,函数值f(x)恰好就可以作为x的适应度。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法

27、来解决。第50页/共66页解：解：(1)定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面,5位二进制数也刚好能表示区间0,31中的全部整数。所以,我们就仅取0,31中的整数来作为参加进化的个体,并且用5位二进制数作为个体x的基因型编码,即染色体即染色体。(2)设定种群规模,产生初始种群。设定种群规模为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8),s4=10011(19)组成初始种群S1。第51页/共66页(3)计算各代种群中的各染色体的适应度

28、,并进行遗传操 作,直 到 适 应 度 最 高 的 染 色 体(该该 问问 题题 中中 显显 然然 为为“1111111111”=31=31)出现为止。计算S1中各染色体的适应度、选择概率、积累概率等并列于表1中。第52页/共66页表表 1 1 第一代种群第一代种群S S1 1中各染色体的情况中各染色体的情况 r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503 设从区间0,1中产生4个随机数如下:第53页/共66页选择-复制 设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503

29、 按赌轮选择法，染色体s1,s2,s3,s4的被选中次数依次为：1,2,0,1。于是，经复制得到新的群体如下：s1=11000（24）,s2=01101（13）,s3=11000（24）,s4=10011（19）可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低的染色体s3一次也没有选中而遭淘汰。第54页/共66页交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换染色体后两位基因，得新染色体：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）变 异

30、设 变 异 率 pm=0.001。这 样，群 体 S1中 共 有540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，我们得到了第二代种群S2：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）Note:s1=11000（24）,s2=01101（13）,s3=11000（24）,s4=10011（19）第55页/共66页假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体：s1=11001（25）,s2=0

31、1100（12）,s3=11011（27）,s4=10000（16）然后，做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得 s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。于是，得第三代种群S3：s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）表表 2 2 第二代种群第二代种群S S2 2中各染色体的情况中各染色体的情况 第56页/共66页表表3 3 第三代种群第三代种群S S4 4中各染色体的情况中各染色体的情况 第57页/共66页设这一轮的选择-复制结

32、果为：s1=11100（28）,s2=11100（28）,s3=11000（24）,s4=10011（19）然后，做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）,s2=11100（28）,s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。于是，得第四代种群S4：s1=11111（31）,s2=11100（28）,s3=11000（24）,s4=10000（16）第58页/共66页显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”

33、解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。第59页/共66页第60页/共66页第61页/共66页7.7.遗传算法小结遗传算法小结 由上所述,我们看到,遗传算法模拟自然选择和有性繁殖、遗传变异的自然原理,实现了优化搜索和问题求解。遗传算法的主要特点是:遗传算法一般是直接在解空间搜索;遗传算法的搜索随机地始于搜索空间的一个点集,而不是固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。第62页/共66页二维优化问题的迭代过程第63页/共66页梯度方向与等值线的关系 第64页/共66页遗传算法总是在寻找优解(最优解或次优解),所以遗传算法又是一种优化搜索算法。遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。第65页/共66页感谢您的观看！第66页/共66页