《高等运筹学》PPT课件.ppt

《《高等运筹学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《高等运筹学》PPT课件.ppt（24页珍藏版）》请在三一办公上搜索。

1、1,第7章 遗传算法,生物进化表现为“适者生存，不适者被淘汰”一类新型的全局优化技术仿生类算法：遗传算法(Genetic Algorithms,GA)仿生过程算法：演化策略 进化程序仿生结构算法：人工神经网络仿生行为算法：蚁群优化算法,2,主要内容,7.1 生物进化和遗传学基本知识概述 7.2 遗传算法描述 7.3 遗传算法的关键参数和操作设计,3,7.1 生物进化和遗传学基本知识概述,1.达尔文自然选择学说 自然选择学说主要包括以下三个方面：(1)遗传父代通过繁殖把生物信息传给子代，子代按照所得信息而发育、分化(2)变异随机发生，变异的选择和积累是生命多样性的根源(3)生存斗争和适者生存 繁

2、殖是现存物种得以生存、延续的必要条件；变异是生物进化的根本保证；在竞争的环境下，自然界不可避免地会对生物的生存进行选择,4,物种被后代所继承的就是那些更能适应环境的个体特征 生物进化：是遗传与变异相互作用的结果 遗传的主要物质是细胞核中染色体上的基因 基因结构：基因位置的排列 基因结构的性质及其与物种的关系：,通过优胜劣汰的自然选择，适应值高的基因结构就被保存下来,5,2.现代综合进化论 用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论 种群遗传学：研究种群中基因的组成及其变化种群：在一定地域中，一个物种的全体成员构成一个种群生物的进化实际上是种群的进化，个体总是要消亡，但种群则可以

3、继续保留每一代中个体基因结构的改变会影响种群基因库的组成，而种群基因库组成的变化就是这个种群的进化 通过个体繁殖机会的差异，也能造成后代遗传组成的改变，自然选择也能够进行,6,生物进化的基本过程：,种群,被淘汰的子种群,获繁殖机会的子种群,子代种群,选择,变异,婚配,(新一代),7,归纳：生物的进化表现为“适者生存，不适者被淘汰”最适合自然环境的种群往往产生了更大的后代种群 生物进化是遗传和变异相互作用的结果遗传是通过父代对子代的基因传递来实现；某些遗传信息的改变决定了生物的变异3.基本概念和术语 染色体(chromosome)：是遗传物质的主要载体，由多个基因(遗传因子)组成DNA(脱氧核糖

4、核酸)：构成染色体的主要物质 基因(gene)：染色体上具有遗传效应的DNA片段.,8,基因型（genotype）：基因组合的模型，染色体的内部表现，它决定了个体的外部表现 表现型（phenotype）：由染色体决定的个体的外部表现，即根据基因型形成的个体 基因座（locus）：基因在染色体中所占据的位置个体（individual）：指染色体带有特征的实体 种群（population）：个体的集合称为种群该集合内个体的数目称为种群的规模 进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化生物的进化是以种群的形式进行的 适应度（

5、fitness）：度量某个物种对于生存环境的适应程度,9,选择（selection）：指以一定的概率从种群中选择若干个体的操作 复制（reproduction）：生物的繁殖过程是由其基因的复制过程来完成的 交叉（crossover）：指有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异编码（coding）：DNA中遗传信息的模式排列遗传编码可以看作从表现型到基因型的映射解码（decoding）：从基因型到表现型的映射,10,7.2 遗传算法描述,1.生物遗传概念与优化问题的对应关系,1

6、1,2.算法思想 从优化问题的一个种群（一组可行解）开始，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的一个种群（一组可行解）在每一代，根据个体（可行解）的适应度（目标函数值）的优劣挑选一部分优良个体复制（繁殖）到下一代，并对其进行交叉和变异操作，产生出代表新的解集合的种群这个过程将导致种群像自然进化一样的子代种群比父代更加适应于环境（即新可行解比旧可行解更接近问题的最优解），整个进化过程中的最优个体就作为问题的最终解,12,3.算法步骤,确定解的编码方案随机产生初始种群,计算各个体的适应度,按适应度大小执行复制操作,random0,1Pc？,执行交叉操作,ra

7、ndom0,1Pm？,执行变异操作,终止准则满足否？,输出结果,Y,Y,Y,N,N,N,13,5.遗传算法的特点 与其它优化算法相比具有如下特点：(1)GA以决策变量的编码作为运算对象(2)GA只用适应度函数值作为搜索信息(3)GA同时使用多个搜索点的搜索信息具有隐含并行性(4)GA使用概率搜索技术,14,7.3 遗传算法的关键参数和操作设计,1.编码 将问题的可行解用一种编码来表示称一个解的编码为一个染色体，组成编码的元素称为基因编码是设计GA时要解决的首要问题，是影响算法性能与效率的重要因素决定了个体的染色体排列形式决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法影响到交叉、变

8、异等遗传算子的运算方法如何设计一种完美的编码方案一直是遗传算法的应用难点之一,15,常用的两种编码方法：二进制编码方法：是GA中最常用的一种编码方法，使用的编码符号集是0,1符号编码方法：染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如A,B,C,D,；1,2,3,4,；A1,A2,A3,等等例如，对于TSP问题，假设有n个城市分别记为C1,C2,Cn，将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体如X：C1,C2,Cn若将各个城市按其代号的下标进行编号，则这个个体也可表示为X：1,2,n,16,2.适应度函数度量个体适应度的函数称为适应度函数GA

9、仅使用适应度函数值，就可确定进一步的搜索方向和搜索范围 适应度函数的值必须为正值 适应度函数的设计要结合问题本身的要求而定：可以直接利用目标函数作为适应度函数；适应度函数是由目标函数变换而成3.种群设定 种群的规模：一般建议取20100之间在优化过程中可以保持确定不变，也可以是动态变化的初始种群的选取：应随机产生,17,4.选择算子指从种群中选择优良个体、淘汰劣质个体的操作(1)比例选择算子个体被选中并被复制到下一代种群中的概率与该个体的适应度大小成正比也叫做赌盘选择具体执行过程是：计算个体i被选中遗传到下一代的概率 模拟赌盘操作来确定各个个体被选中的次数(2)最佳个体(精英)保存策略把种群中

10、适应度最高的个体不参与交叉和变异运算，而直接复制到下一代种群中这种选择操作又称为复制,18,5.交叉概率与交叉算子 生物进化过程中起核心作用的是遗传基因的重组 遗传算法中起核心作用的是交叉操作，即把两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新个体(1)交叉概率(Pc)用于控制种群中参与交叉操作的个体的数量一般Pc=0.40.99(2)交叉算子一般要求是既不能太多地破坏个体编码串中表示优良性状的基因结构，又要能够有效地产生出一些较多的新个体对由选择操作形成的种群中的个体进行随机配对按预先设定的交叉概率Pc来决定每对是否需要进行交叉操作,19,交叉算子的设计包括：如何确定交叉点

11、的位置：一般是随机设定如何进行部分基因的交换常用的方法介绍如下：(1)针对二进制编码的交叉方法 单点交叉将交叉点前面或后面的基因相互交换 父个体1:1011001 子个体1:1011110父个体2:0010110 子个体2:0010001双点交叉将两个交叉点之间的基因相互交换 父个体1:1011011 子个体1:1001011父个体2:0001000 子个体2:0011000,20,(2)针对符号编码的交叉方法.符号编码给使用基本的遗传操作带来了新的问题：交叉操作前：父代个体1：0 1 2|3 4 5 父代个体2：0 4 3|2 5 1 交叉操作后（变为非法）：子代个体1：0 1 2|2 5

12、1 子代个体2：0 4 3|3 4 5,21,部分匹配交叉（Partially Matched Crossover,PMX）:交叉操作过程分两步，对个体编码串进行常规的双点交叉操作，按交叉区域内各基因值间的映射关系来修改交叉区域之外的各个基因座的基因值。交叉前：父代个体1：9 8 4|5 6 7|1 3 2 0 父代个体2：8 7 1|2 3 0|9 5 4 6 交叉后：子代个体1：9 8 4|2 3 0|1 3 2 0 子代个体2：8 7 1|5 6 7|9 5 4 6 映射关系：2-5，3-6，0-7 替换：子代个体1：9 8 4|2 3 0|1 6 5 7 子代个体2：8 0 1|5 6

13、 7|9 2 4 3 其它交叉方法：顺序交叉(OX)，循环交叉(CX)等,22,6.变异概率与变异算子 GA中的变异运算，是指对个体染色体编码串中的某些基因值作变动，从而形成一个新的个体 交叉运算是GA中产生新个体的主要方法，决定了算法的全局搜索能力 变异运算是产生新个体的辅助方法，决定了算法的局部搜索能力(1)变异概率(Pm)通常取Pm0.00010.1(2)变异算子 变异算子的设计包括：如何确定变异点的位置：随机确定 如何进行基因值的替换：以Pm对这些基因座的基因值进行变异常用的方法如下：,23,基本位变异把选定的基因座上的基因值取反 父个体:1011011 子个体:1001011 逆转变异将两个逆转点间的基因值逆向排序 父个体:101101000 子个体:100101100 对于符号编码的个体，有 父个体:123456789 子个体:127654389 交换变异相互交换两个随机选取的基因座上的基因值父个体:BCADEJHIFG 子个体:BCAIEJHDFG插入变异将一个基因座上的基因插入到另一个基因座之后父个体:BCADEJHIFG 子个体:BCADIEJHFG,24,7.算法的终止条件(1)给定一个最大的进化代数，一般是1001000代(2)当前的最好解连续若干代没有变化(3)连续几代个体平均适应度的差异小于某一个极小的值,