遗传算法专业专家讲座

第四章遗传算法

智能优化计算遗传算法专业专家讲座第1页4.1遗传算法介绍

4.1.1遗传算法产生与发展

4.1.2生物进化理论和遗传学基本知识

4.1.3遗传算法思绪与特点

4.1.4遗传算法基本操作

4.1.5遗传算法应用4.2基本遗传算法

4.2.1简单函数优化实例

4.2.2遗传基因型

4.2.3适应度函数及其尺度变换

4.2.4遗传操作——选择

4.2.5遗传操作——交叉/基因重组

4.2.6遗传操作——变异

4.2.7算法设计与实现

4.2.8模式定理智能优化计算遗传算法专业专家讲座第2页4.3遗传算法改进

4.3.1CHC算法

4.3.2自适应遗传算法

4.3.3基于小生境技术遗传算法4.4遗传算法应用

4.4.1处理带约束函数优化问题

4.4.2处理多目标优化问题

4.4.3处理组合优化问题

4.4.4遗传算法在过程建模中应用

4.4.5遗传算法在模式识别中应用智能优化计算遗传算法专业专家讲座第3页4.1遗传算法介绍

智能优化计算产生早在50年代，一些生物学家开始研究利用数字计算机模拟生物自然遗传与自然进化过程；1963年，德国柏林技术大学I.Rechenberg和H.P.Schwefel，做风洞试验时，产生了进化策略初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划思想。1966年Fogel等出版了《基于模拟进化人工智能》，系统阐述了进化规划思想。4.1.1遗传算法产生与发展

遗传算法专业专家讲座第4页4.1遗传算法介绍

智能优化计算产生60年代中期，美国Michigan大学J.H.Holland教授提出借鉴生物自然遗传基本原理用于自然和人工系统自适应行为研究和串编码技术；1967年，他学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名“AdaptationinNaturalandArtificialSystems”，标志遗传算法诞生。4.1.1遗传算法产生与发展

遗传算法专业专家讲座第5页4.1遗传算法介绍

智能优化计算发展70年代初，Holland提出了“模式定理”（SchemaTheorem），普通认为是“遗传算法基本定理”，从而奠定了遗传算法研究理论基础；1985年，在美国召开了第一届遗传算法国际会议，而且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；4.1.1遗传算法产生与发展

遗传算法专业专家讲座第6页4.1遗传算法介绍

智能优化计算发展1989年，Holland学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全方面而系统叙述；1991年，L.Davis编辑出版了《遗传算法手册》，其中包含了遗传算法在工程技术和社会生活中大量应用实例。4.1.1遗传算法产生与发展

遗传算法专业专家讲座第7页4.1遗传算法介绍

智能优化计算几个名词概念

遗传算法——进化计算——计算智能——人工智能4.1.1遗传算法产生与发展

遗传算法专业专家讲座第8页4.1遗传算法介绍

智能优化计算几个名词概念进化计算：4.1.1遗传算法产生与发展

因为遗传算法、进化规划和进化策略是不一样领域研究人员分别独立提出，在相当长时期里相互之间没有正式沟通。直到90年代，才有所交流。他们发觉彼此基本思想含有惊人相同之处，于是提出将这类方法统称为“进化计算”(EvolutionaryComputation)。遗传算法专业专家讲座第9页4.1遗传算法介绍

智能优化计算几个名词概念计算智能：4.1.1遗传算法产生与发展

计算智能主要包含神经计算、进化计算和含糊计算等。它们分别从不一样角度模拟人类智能活动，以使计算机含有智能。通常将基于符号处理传统人工智能称为符号智能，以区分于正在兴起计算智能。符号智能特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基础，偏重于数值计算。遗传算法专业专家讲座第10页4.1遗传算法介绍

智能优化计算达尔文自然选择说遗传（heredity）：子代和父代含有相同或相同性状，确保物种稳定性；变异（variation）：子代与父代，子代不一样个体之间总有差异，是生命多样性根源；生存斗争和适者生存：含有适应性变异个体被保留，不具适应性变异个体被淘汰。自然选择过程是长久、迟缓、连续过程。4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第11页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语染色体（chromosome）：遗传物质载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置基本遗传单位；4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第12页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语基因型（genotype）：遗传因子组合模型；表现型（phenotype）：由染色体决定性状外部表现；4.1.2生物进化理论和遗传学基本知识

1111111

1110111遗传算法专业专家讲座第13页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语基因座（locus）：遗传基因在染色体中所占据位置，同一基因座可能有全部基因称为等位基因（allele）；个体（individual）：指染色体带有特征实体；种群（population）：个体集合，该集合内个体数称为种群大小；4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第14页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语进化（evolution）：生物在其延续生存过程中，逐步适应其生存环境，使得其品质不停得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境适应程度。对生存环境适应程度较高物种将取得更多繁殖机会，而对生存环境适应程度较低物种，其繁殖机会就会相对较少，甚至逐步灭绝;4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第15页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语选择（selection）：指决定以一定概率从种群中选择若干个体操作；复制（reproduction）：细胞在分裂时，遗传物质DNA经过复制而转移到新产生细胞中，新细胞就继承了旧细胞基因;交叉（crossover）：在两个染色体某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新染色体。又称基因重组，俗称“杂交”;4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第16页4.1遗传算法介绍

智能优化计算遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小概率产生一些复制差错，从而使DNA发生某种变异，产生出新染色体，这些新染色体表现出新性状;编码（coding）：表现型到基因型映射；解码（decoding）：从基因型到表现型映射。4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第17页4.1遗传算法介绍

智能优化计算进化论与遗传学融合1930～1947年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表《遗传学与物种起源》是融合进化论与遗传学代表作。生物进化与智能学关系生物物种作为复杂系统，含有奇妙自适应、自组织和自优化能力，这是一个生物在进化过程中表达智能，也是人工系统梦寐以求功效。4.1.2生物进化理论和遗传学基本知识

遗传算法专业专家讲座第18页4.1遗传算法介绍

智能优化计算遗传算法基本思绪4.1.3遗传算法思绪与特点

遗传算法专业专家讲座第19页4.1遗传算法介绍

智能优化计算自组织、自适应和自学习性在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中取得信息自行组织搜索。本质并行性内在并行性与内含并行性不需求导只需目标函数和适应度函数概率转换规则强调概率转换规则，而不是确定转换规则4.1.3遗传算法思绪与特点

遗传算法专业专家讲座第20页4.1遗传算法介绍

智能优化计算选择

适应度计算：按百分比适应度函数（proportionalfitnessassignment）基于排序适应度计算（Rank-basedfitnessassignment）

选择算法：轮盘赌选择（roulettewheelselection）4.1.4遗传算法基本操作

遗传算法专业专家讲座第21页4.1遗传算法介绍

智能优化计算选择

选择算法：随机遍历抽样（stochasticuniversalselection）局部选择（localselection）截断选择（truncationselection）锦标赛选择（tournamentselection）4.1.4遗传算法基本操作

遗传算法专业专家讲座第22页4.1遗传算法介绍

智能优化计算交叉或基因重组

实值重组（realvaluedrecombination）：离散重组（discreterecombination）中间重组（intermediaterecombination）线性重组（linearrecombination）扩展线性重组（extendedlinearrecombination）4.1.4遗传算法基本操作

遗传算法专业专家讲座第23页4.1遗传算法介绍

智能优化计算交叉或基因重组

二进制交叉（binaryvaluedcrossover）：单点交叉（single-pointcrossover）多点交叉（multiple-pointcrossover）均匀交叉（uniformcrossover）洗牌交叉（shufflecrossover）缩小代理交叉（crossoverwithreducedsurrogate）4.1.4遗传算法基本操作

遗传算法专业专家讲座第24页4.1遗传算法介绍

智能优化计算变异

实值变异

二进制变异4.1.4遗传算法基本操作

遗传算法专业专家讲座第25页4.1遗传算法介绍

智能优化计算简单实例产生初始种群计算适应度4.1.4遗传算法基本操作

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）遗传算法专业专家讲座第26页4.1遗传算法介绍

智能优化计算简单实例选择4.1.4遗传算法基本操作

个体染色体适应度选择概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174遗传算法专业专家讲座第27页4.1遗传算法介绍

智能优化计算简单实例选择4.1.4遗传算法基本操作

个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000遗传算法专业专家讲座第28页4.1遗传算法介绍

智能优化计算简单实例选择在0～1之间产生一个随机数：4.1.4遗传算法基本操作

个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！遗传算法专业专家讲座第29页00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遗传算法介绍

智能优化计算简单实例交叉4.1.4遗传算法基本操作

00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011遗传算法专业专家讲座第30页4.1遗传算法介绍

智能优化计算简单实例变异4.1.4遗传算法基本操作

000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100110001100000111001011011000000011001110100101010101011100101101001011011110000000110011