高等运筹学7.ppt

第7章 遗传算法生物进化表现为“适者生存，不适者被淘汰”一类新型的全局优化技术仿生类算法：遗传算法(Genetic Algorithms,GA)仿生过程算法：演化策略 进化程序仿生结构算法：人工神经网络仿生行为算法：蚁群优化算法主要内容 7.1 生物进化和遗传学基本知识概述 7.2 遗传算法描述 7.3 遗传算法的关键参数和操作设计7.1 生物进化和遗传学基本知识概述1.达尔文自然选择学说物种被后代所继承的就是那些更能适应环境的个体特征 生物进化：是遗传与变异相互作用的结果 遗传的主要物质是细胞核中染色体上的基因 基因结构：基因位置的排列 基因结构的性质及其与物种的关系：基因结构物种稳健性差异性变易性稳定性多样性进化通过优胜劣汰的自然选择，适应值高的基因结构就被保存下来2.现代综合进化论生物进化的基本过程：种群被淘汰的子种群获繁殖机会的子种群子代种群选择变异婚配(新一代)归纳：基因型（genotype）：基因组合的模型，染色体的内部表现，它决定了个体的外部表现 表现型（phenotype）：由染色体决定的个体的外部表现，即根据基因型形成的个体 基因座（locus）：基因在染色体中所占据的位置个体（individual）：指染色体带有特征的实体 种群（population）：个体的集合称为种群该集合内个体的数目称为种群的规模 进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化生物的进化是以种群的形式进行的 适应度（fitness）：度量某个物种对于生存环境的适应程度 选择（selection）：指以一定的概率从种群中选择若干个体的操作 复制（reproduction）：生物的繁殖过程是由其基因的复制过程来完成的 交叉（crossover）：指有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异编码（coding）：DNA中遗传信息的模式排列遗传编码可以看作从表现型到基因型的映射解码（decoding）：从基因型到表现型的映射7.2 遗传算法描述1.生物遗传概念与优化问题的对应关系 生物遗传概念 在优化问题中表示的概念 个体染色体基因个体适应度种群生物进化过程适者生存复制交叉变异一个可行解解的编码（字符串、向量等），即解的表示形式解中每一分量的特征（如各分量的值）解的目标函数值或所对应的适应函数值多个可行解组成的集合，其个数称为种群规模求解的迭代过程目标函数值越好的解，被选择作为下一迭代过程的当前解的可能性越大根据目标函数值的优劣选取的一组解将一对解中的部分分量的取值对换改变一个解中某一分量的取值 2.算法思想3.算法步骤确定解的编码方案随机产生初始种群计算各个体的适应度按适应度大小执行复制操作random0,1Pc？执行交叉操作random0,1Pm？执行变异操作终止准则满足否？输出结果YYYNNN5.遗传算法的特点7.3 遗传算法的关键参数和操作设计1.编码常用的两种编码方法：二进制编码方法：是GA中最常用的一种编码方法，使用的编码符号集是0,1 符号编码方法：染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如A,B,C,D,；1,2,3,4,；A1,A2,A3,等等2.适应度函数4.选择算子),.,2,1(/1MiffPMjjii5.交叉概率与交叉算子 交叉算子的设计包括：如何确定交叉点的位置：一般是随机设定 如何进行部分基因的交换常用的方法介绍如下：(1)针对二进制编码的交叉方法 单点交叉将交叉点前面或后面的基因相互交换 父个体1:1011001 子个体1:1011110父个体2:0010110 子个体2:0010001双点交叉将两个交叉点之间的基因相互交换 父个体1:1011011 子个体1:1001011父个体2:0001000 子个体2:0011000(2)针对符号编码的交叉方法.符号编码给使用基本的遗传操作带来了新的问题：交叉操作前：父代个体1：部分匹配交叉（其它交叉方法：顺序交叉(OX)，循环交叉(CX)等6.变异概率与变异算子基本位变异把选定的基因座上的基因值取反7.算法的终止条件(1)给定一个最大的进化代数，一般是1001000代(2)当前的最好解连续若干代没有变化(3)连续几代个体平均适应度的差异小于某一个极小的值