《高等运筹学7.ppt》由会员分享，可在线阅读，更多相关《高等运筹学7.ppt（24页珍藏版）》请在课桌文档上搜索。
1、1,第7章 遗传算法,生物进化表现为“适者生存，不适者被淘汰”一类新型的全局优化技术仿生类算法：遗传算法(Genetic Algorithms,GA)仿生过程算法：演化策略 进化程序仿生结构算法：人工神经网络仿生行为算法：蚁群优化算法,戌绎径草蜕搁妒紧宫韧澄猩竿愚惰绒滦孕般碱贤瓢确进亡喻搜岳稚弱狡命高等运筹学7高等运筹学7,2,主要内容,7.1 生物进化和遗传学基本知识概述 7.2 遗传算法描述 7.3 遗传算法的关键参数和操作设计,姓嫁硼乙嘘僳哲旋代怨逾助侵抛慈媚自涧这旷甭傣谢谰熔掀玫超锹颤患滥高等运筹学7高等运筹学7,3,7.1 生物进化和遗传学基本知识概述,1.达尔文自然选择学说 自然选
2、择学说主要包括以下三个方面：(1)遗传父代通过繁殖把生物信息传给子代，子代按照所得信息而发育、分化(2)变异随机发生，变异的选择和积累是生命多样性的根源(3)生存斗争和适者生存 繁殖是现存物种得以生存、延续的必要条件；变异是生物进化的根本保证；在竞争的环境下，自然界不可避免地会对生物的生存进行选择,季闪绘踩脾赣钎稻抖滞嫂娱枚轮扇如真刃师斌坡淹霸旁哥笑践偷礼姚何袭高等运筹学7高等运筹学7,4,物种被后代所继承的就是那些更能适应环境的个体特征 生物进化：是遗传与变异相互作用的结果 遗传的主要物质是细胞核中染色体上的基因 基因结构：基因位置的排列 基因结构的性质及其与物种的关系：,通过优胜劣汰的自然
3、选择，适应值高的基因结构就被保存下来,劳瑞淋湿俯曰荷矽锁襟扔笼啄畴耕醛漆惨这簇炽曳彼筑出坷钓膨臂绚乞苑高等运筹学7高等运筹学7,5,2.现代综合进化论 用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论 种群遗传学：研究种群中基因的组成及其变化种群：在一定地域中，一个物种的全体成员构成一个种群生物的进化实际上是种群的进化，个体总是要消亡，但种群则可以继续保留每一代中个体基因结构的改变会影响种群基因库的组成，而种群基因库组成的变化就是这个种群的进化 通过个体繁殖机会的差异，也能造成后代遗传组成的改变，自然选择也能够进行,庙讨痉包谚霄瞬沼哩碳呛洲恫每姚倍雄蔚团绅郧哪篡否式峭囤纱姚啦梧磋高等
4、运筹学7高等运筹学7,6,生物进化的基本过程：,种群,被淘汰的子种群,获繁殖机会的子种群,子代种群,选择,变异,婚配,(新一代),陶处铃笑埋勘巫乓棕试抡渤滓距质扯荤收沫龙挠熬雇粱鹏番爸集啮瞅粳尝高等运筹学7高等运筹学7,7,归纳：生物的进化表现为“适者生存，不适者被淘汰”最适合自然环境的种群往往产生了更大的后代种群 生物进化是遗传和变异相互作用的结果遗传是通过父代对子代的基因传递来实现；某些遗传信息的改变决定了生物的变异3.基本概念和术语 染色体(chromosome)：是遗传物质的主要载体，由多个基因(遗传因子)组成DNA(脱氧核糖核酸)：构成染色体的主要物质 基因(gene)：染色体上具有
5、遗传效应的DNA片段.,委英渣榜枫摈沛中穿胆蝴搞列糙舱悄痢屁迫菊涌湛哪辱罩魏注坞詹迫郧熊高等运筹学7高等运筹学7,8,基因型（genotype）：基因组合的模型，染色体的内部表现，它决定了个体的外部表现 表现型（phenotype）：由染色体决定的个体的外部表现，即根据基因型形成的个体 基因座（locus）：基因在染色体中所占据的位置个体（individual）：指染色体带有特征的实体 种群（population）：个体的集合称为种群该集合内个体的数目称为种群的规模 进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化生物的进化
6、是以种群的形式进行的 适应度（fitness）：度量某个物种对于生存环境的适应程度,脆糜肤这妥给濒阀咏饰芯可归的养释偶葛渊铅搔牌酗挺靶炮途鸯护磺卧鸯高等运筹学7高等运筹学7,9,选择（selection）：指以一定的概率从种群中选择若干个体的操作 复制（reproduction）：生物的繁殖过程是由其基因的复制过程来完成的 交叉（crossover）：指有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异编码（coding）：DNA中遗传信息的模式排列遗传编码可以看作从表现型到基因型的映
7、射解码（decoding）：从基因型到表现型的映射,斟跨死俄腾宴晓扇皑坷昆痛缕岂习哗告篓痢具戒迎篓奔莉苦缎眶安换谓闭高等运筹学7高等运筹学7,10,7.2 遗传算法描述,1.生物遗传概念与优化问题的对应关系,艰扭脑注蹄邹敦湍竞流羡遭截卜台预死雁毗悟用痔你颓瘤韵耀厢茵所骆架高等运筹学7高等运筹学7,11,2.算法思想 从优化问题的一个种群（一组可行解）开始，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的一个种群（一组可行解）在每一代，根据个体（可行解）的适应度（目标函数值）的优劣挑选一部分优良个体复制（繁殖）到下一代，并对其进行交叉和变异操作，产生出代表新的解集合
8、的种群这个过程将导致种群像自然进化一样的子代种群比父代更加适应于环境（即新可行解比旧可行解更接近问题的最优解），整个进化过程中的最优个体就作为问题的最终解,宣邦韦涯淖鼻适奋疫响肚分骗意伙慨怖试迢汕灿缀衬鼻师踌招缕仙很樊赤高等运筹学7高等运筹学7,12,3.算法步骤,确定解的编码方案随机产生初始种群,计算各个体的适应度,按适应度大小执行复制操作,random0,1Pc？,执行交叉操作,random0,1Pm？,执行变异操作,终止准则满足否？,输出结果,Y,Y,Y,N,N,N,敷骄宪扎芭蛙栗帽词狈呜刚夜位伞给戮创变散惮显巷拄诈喷仇载孰裂逸饥高等运筹学7高等运筹学7,13,5.遗传算法的特点 与其它
9、优化算法相比具有如下特点：(1)GA以决策变量的编码作为运算对象(2)GA只用适应度函数值作为搜索信息(3)GA同时使用多个搜索点的搜索信息具有隐含并行性(4)GA使用概率搜索技术,峨东匣蹬校耻修韦惑皆猛掩啃欧韩敌虚魁蜀尺债咋渭息扒过婚赔种碳亡淬高等运筹学7高等运筹学7,14,7.3 遗传算法的关键参数和操作设计,1.编码 将问题的可行解用一种编码来表示称一个解的编码为一个染色体，组成编码的元素称为基因编码是设计GA时要解决的首要问题，是影响算法性能与效率的重要因素决定了个体的染色体排列形式决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法影响到交叉、变异等遗传算子的运算方法如何设计
10、一种完美的编码方案一直是遗传算法的应用难点之一,迂眩弘可相壤抨要萄柜影福灌暴奠预钡钒妈投彪粉冻侗疼品烁唁侩腺位积高等运筹学7高等运筹学7,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
11、,沃痪轻生巍些肿窑鸟垦贯娟克线织络么屹羽牵鬃锣伶坞甄出雨唯秆援渣鬃高等运筹学7高等运筹学7,16,2.适应度函数度量个体适应度的函数称为适应度函数GA仅使用适应度函数值，就可确定进一步的搜索方向和搜索范围 适应度函数的值必须为正值 适应度函数的设计要结合问题本身的要求而定：可以直接利用目标函数作为适应度函数；适应度函数是由目标函数变换而成3.种群设定 种群的规模：一般建议取20100之间在优化过程中可以保持确定不变，也可以是动态变化的初始种群的选取：应随机产生,脓晴坦掂郝炮羔巨她投舱忆玛磕允储神德丁侧惹捎涵已豆瘤硅劈阁基诣物高等运筹学7高等运筹学7,17,4.选择算子指从种群中选择优良个体、淘
12、汰劣质个体的操作(1)比例选择算子个体被选中并被复制到下一代种群中的概率与该个体的适应度大小成正比也叫做赌盘选择具体执行过程是：计算个体i被选中遗传到下一代的概率 模拟赌盘操作来确定各个个体被选中的次数(2)最佳个体(精英)保存策略把种群中适应度最高的个体不参与交叉和变异运算，而直接复制到下一代种群中这种选择操作又称为复制,剐桌掐尼鸳冗站戮泽皋壮象及岛汰叙孰肩缎直午庄掉滨例褒农眩太才讯祖高等运筹学7高等运筹学7,18,5.交叉概率与交叉算子 生物进化过程中起核心作用的是遗传基因的重组 遗传算法中起核心作用的是交叉操作，即把两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新个体(1
13、)交叉概率(Pc)用于控制种群中参与交叉操作的个体的数量一般Pc=0.40.99(2)交叉算子一般要求是既不能太多地破坏个体编码串中表示优良性状的基因结构，又要能够有效地产生出一些较多的新个体对由选择操作形成的种群中的个体进行随机配对按预先设定的交叉概率Pc来决定每对是否需要进行交叉操作,宏碍扳肚预臃港腿蹈义搭徽只堡伦揭蔚悦吁愉汹惭焚歇寇贺抗噬檬峰尸掷高等运筹学7高等运筹学7,19,交叉算子的设计包括：如何确定交叉点的位置：一般是随机设定如何进行部分基因的交换常用的方法介绍如下：(1)针对二进制编码的交叉方法 单点交叉将交叉点前面或后面的基因相互交换 父个体1:1011001 子个体1:101
14、1110父个体2:0010110 子个体2:0010001双点交叉将两个交叉点之间的基因相互交换 父个体1:1011011 子个体1:1001011父个体2:0001000 子个体2:0011000,堂漫堂诺经韵侮韭馒暑兼堆盼由摊贬叔蓄淀俊长阜桨殊愁烘颅包耕炼毛牡高等运筹学7高等运筹学7,20,(2)针对符号编码的交叉方法.符号编码给使用基本的遗传操作带来了新的问题：交叉操作前：父代个体1：0 1 2|3 4 5 父代个体2：0 4 3|2 5 1 交叉操作后（变为非法）：子代个体1：0 1 2|2 5 1 子代个体2：0 4 3|3 4 5,逢只脱兹诬挥交邵淘样孝芽告舶潮宣件脱撑堰究薛台枪范
15、誓耕辈哲病溜劫高等运筹学7高等运筹学7,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
16、 7|9 2 4 3 其它交叉方法：顺序交叉(OX)，循环交叉(CX)等,芯沽努趴贪窍逢拳淀最氖土照扑斤敢椎古迅苔死师吭鞍傍臆淹趁企例屁最高等运筹学7高等运筹学7,22,6.变异概率与变异算子 GA中的变异运算，是指对个体染色体编码串中的某些基因值作变动，从而形成一个新的个体 交叉运算是GA中产生新个体的主要方法，决定了算法的全局搜索能力 变异运算是产生新个体的辅助方法，决定了算法的局部搜索能力(1)变异概率(Pm)通常取Pm0.00010.1(2)变异算子 变异算子的设计包括：如何确定变异点的位置：随机确定 如何进行基因值的替换：以Pm对这些基因座的基因值进行变异常用的方法如下：,车绚仔罐呸
17、突啮赌斜觉泳挂田劝景狞拧冬桔逃琴疙垮陆惜谰钨介捉疆鸳荒高等运筹学7高等运筹学7,23,基本位变异把选定的基因座上的基因值取反 父个体:1011011 子个体:1001011 逆转变异将两个逆转点间的基因值逆向排序 父个体:101101000 子个体:100101100 对于符号编码的个体，有 父个体:123456789 子个体:127654389 交换变异相互交换两个随机选取的基因座上的基因值父个体:BCADEJHIFG 子个体:BCAIEJHDFG插入变异将一个基因座上的基因插入到另一个基因座之后父个体:BCADEJHIFG 子个体:BCADIEJHFG,甸窝违渤马蓟慈迭烤拷纬给誓怠蛔纫碱售佐沛暗淫互首仿乌塔萨彭涯豫则高等运筹学7高等运筹学7,24,7.算法的终止条件(1)给定一个最大的进化代数，一般是1001000代(2)当前的最好解连续若干代没有变化(3)连续几代个体平均适应度的差异小于某一个极小的值,榨涅哦货橱侗镶峙破疗渍诵刁宣焰嫩诫纯抱申甥砒槛求寓怜少月劲线揽绷高等运筹学7高等运筹学7,
