遗传算法综述及简单应用实例的Matlab程序课件

遗传算法综述及简单应用实例及Matlab程序

1遗传算法综述及简单应用实例14.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模式定理►24.1遗传算法简介►24.1遗传算法简介

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

34.1遗传算法简介产生4.1.1遗传算法4.1遗传算法简介

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

44.1遗传算法简介产生4.1.1遗传算法4.1遗传算法简介

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

54.1遗传算法简介发展4.1.1遗传算法4.1遗传算法简介

发展1988年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《Handbookofgeneticalgorithms》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。4.1.1遗传算法的产生与发展

64.1遗传算法简介发展4.1.1遗传算法4.1遗传算法简介

达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。

自然选择过程是长期的、缓慢的、连续的过程。4.1.2生物进化理论和遗传学的基本知识

74.1遗传算法简介达尔文的自然选择说4.1.4.1遗传算法简介

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

84.1遗传算法简介遗传学(Genetics)基本概念4.1遗传算法简介

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

1111111

111011194.1遗传算法简介遗传学基本概念与术语4.14.1遗传算法简介

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

104.1遗传算法简介遗传学基本概念与术语4.14.1遗传算法简介

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

114.1遗传算法简介遗传学基本概念与术语4.14.1遗传算法简介

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

124.1遗传算法简介遗传学基本概念与术语4.14.1遗传算法简介

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

134.1遗传算法简介遗传学基本概念与术语4.14.1遗传算法简介

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

144.1遗传算法简介进化论与遗传学的融合4.14.1遗传算法简介

遗传算法的基本思路4.1.3遗传算法的思路与特点

154.1遗传算法简介遗传算法的基本思路4.1.4.1遗传算法简介

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

164.1遗传算法简介自组织、自适应和自学习性44.1遗传算法简介

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

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）174.1遗传算法简介简单实例4.1.4遗传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.152174184.1遗传算法简介简单实例4.1.4遗传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.000000194.1遗传算法简介简单实例4.1.4遗传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淘汰！淘汰！204.1遗传算法简介简单实例4.1.4遗传00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遗传算法简介

简单实例交叉4.1.4遗传算法的基本操作

000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100112100011000001110010110114.1遗传算法简介

简单实例变异4.1.4遗传算法的基本操作

0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011224.1遗传算法简介简单实例4.1.4遗传4.1遗传算法简介

简单实例至下一代，适应度计算→选择→交叉→变异，直至满足终止条件。4.1.4遗传算法的基本操作

234.1遗传算法简介简单实例4.1.4遗传4.1遗传算法简介

选择1.适应度计算：按比例的适应度函数（proportionalfitnessassignment）基于排序的适应度计算（Rank-basedfitnessassignment）

4.1.4遗传算法的基本操作

244.1遗传算法简介选择4.1.4遗传算法4.1遗传算法简介

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

254.1遗传算法简介选择4.1.4遗传算法4.1遗传算法简介

交叉或基因重组

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

264.1遗传算法简介交叉或基因重组4.1.44.1遗传算法简介

交叉或基因重组

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

274.1遗传算法简介交叉或基因重组4.1.44.1遗传算法简介

变异

实值变异

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

284.1遗传算法简介变异4.1.4遗传算法4.1遗传算法简介

函数优化是遗传算法的经典应用领域;组合优化实践证明，遗传算法对于组合优化中的NP完全问题非常有效;自动控制如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;4.1.5遗传算法的应用

294.1遗传算法简介函数优化4.1.5遗传4.1遗传算法简介

机器人智能控制遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;4.1.5遗传算法的应用

304.1遗传算法简介机器人智能控制4.1.54.1遗传算法简介

人工生命基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序。4.1.5遗传算法的应用

314.1遗传算法简介人工生命4.1.5遗传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模式定理►324.1遗传算法简介►324.2基本遗传算法

问题的提出一元函数求最大值：4.2.1简单函数优化的实例

334.2基本遗传算法问题的提出4.2.1简4.2基本遗传算法

问题的提出用微分法求取f(x)的最大值：解有无穷多个：4.2.1简单函数优化的实例

344.2基本遗传算法问题的提出4.2.1简4.2基本遗传算法

问题的提出当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内的最大值点：此时，函数最大值f(x19)比f(1.85)=3.85稍大。4.2.1简单函数优化的实例

354.2基本遗传算法问题的提出4.2.1简4.2基本遗传算法

编码表现型：x基因型：二进制编码（串长取决于求解精度）

串长与精度之间的关系：若要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。所以编码的二进制串长应为22位。4.2.1简单函数优化的实例

364.2基本遗传算法编码4.2.1简单函数4.2基本遗传算法

产生初始种群产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……4.2.1简单函数优化的实例

374.2基本遗传算法产生初始种群4.2.14.2基本遗传算法

计算适应度不同的问题有不同的适应度计算方法本例：直接用目标函数作为适应度函数①将某个体转化为[-1,2]区间的实数：

s=<1000101110110101000111>→x=0.637197②计算x的函数值（适应度）：

f(x)=xsin(10πx)+2.0=2.5863454.2.1简单函数优化的实例

384.2基本遗传算法计算适应度4.2.1简4.2基本遗传算法

计算适应度

二进制与十进制之间的转换：第一步，将一个二进制串（b21b20…b0）转化为10进制数：第二步，x’对应的区间[-1,2]内的实数：4.2.1简单函数优化的实例

(0000000000000000000000)→-1(1111111111111111111111)→2394.2基本遗传算法计算适应度4.2.1简4.2基本遗传算法

遗传操作选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异4.2.1简单函数优化的实例

404.2基本遗传算法遗传操作4.2.1简单4.2基本遗传算法

模拟结果

设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。

得到的最佳个体：smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;4.2.1简单函数优化的实例

414.2基本遗传算法模拟结果4.2.1简单4.2基本遗传算法

模拟结果

进化的过程：4.2.1简单函数优化的实例

世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503424.2基本遗传算法模拟结果4.2.1简单4.2基本遗传算法

编码原则完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；健全性（soundness）：任何一个基因型都对应于一个可能解；非冗余性（non-redundancy）：问题空间和表达空间一一对应。4.2.2遗传基因型

434.2基本遗传算法编码原则4.2.2遗传4.2基本遗传算法

多种编码方式二进制编码；浮点数编码；格雷码编码；符号编码；复数编码；DNA编码等。4.2.2遗传基因型

444.2基本遗传算法多种编码方式4.2.24.2基本遗传算法

二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数编码差。4.2.2遗传基因型

454.2基本遗传算法二进制编码与浮点数编码的比较4.2基本遗传算法

适应度函数的重要性适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换（fitnessscaling）。4.2.3适应度函数及其尺度变换

464.2基本遗传算法适应度函数的重要性4.2.4.2基本遗传算法

适应度函数的设计单值、连续、非负、最大化合理、一致性（能够反映解的优劣）计算量小通用性强4.2.3适应度函数及其尺度变换

474.2基本遗传算法适应度函数的设计4.2.34.2基本遗传算法

几种常见的适应度函数直接转换若目标函数为最大化问题：Fit(f(x))=f(x)若目标函数为最小化问题：Fit(f(x))=-f(x)4.2.3适应度函数及其尺度变换

484.2基本遗传算法几种常见的适应度函数4.24.2基本遗传算法

几种常见的适应度函数界限构造法1若目标函数为最大化问题：若目标函数为最小化问题：4.2.3适应度函数及其尺度变换

494.2基本遗传算法几种常见的适应度函数4.24.2基本遗传算法

几种常见的适应度函数界限构造法2若目标函数为最大化问题：若目标函数为最小化问题：

c为目标函数的保守估计值。4.2.3适应度函数及其尺度变换

504.2基本遗传算法几种常见的适应度函数4.24.2基本遗传算法

适应度函数的作用适应度函数设计不当有可能出现欺骗问题：（1）进化初期，个别超常个体控制选择过程；（2）进化末期，个体差异太小导致陷入局部极值。4.2.3适应度函数及其尺度变换

514.2基本遗传算法适应度函数的作用4.2.34.2基本遗传算法

适应度函数的线性变换法

f’=α*f+β系数的确定满足以下条件：①f’avg=favg②f’max=cmultf’avg

cmult=1.0~2.0，α和β取适当值，以保证适应度值非负。4.2.3适应度函数及其尺度变换

524.2基本遗传算法适应度函数的线性变换法4.4.2基本遗传算法

适应度函数的幂函数变换法

f’=fk

k与所求优化问题相关4.2.3适应度函数及其尺度变换

k534.2基本遗传算法适应度函数的幂函数变换法44.2基本遗传算法

适应度函数的指数变换法

f’=e-af

a决定了复制的强制性。a越大，大适应度的个体被复制的强制性就越弱。4.2.3适应度函数及其尺度变换

α544.2基本遗传算法适应度函数的指数变换法4.4.2基本遗传算法

几个概念选择压力（selectionpressure）:最佳个体选中的概率与平均个体选中概率的比值；偏差（bias）：个体正规化适应度与其期望再生概率的绝对差值；个体扩展（spread）：单个个体子代个数的范围；多样化损失（lossofdiversity）：在选择阶段未选中个体数目占种群的比例；4.2.4遗传操作——选择

554.2基本遗传算法几个概念4.2.4遗传4.2基本遗传算法

几个概念选择强度（selectionintensity）:将正规高斯分布应用于选择方法，期望平均适应度；选择方差（selectionvariance）：将正规高斯分布应用于选择方法，期望种群适应度的方差。4.2.4遗传操作——选择

564.2基本遗传算法几个概念4.2.4遗传4.2基本遗传算法

个体选择概率的常用分配方法按比例的适应度分配（proportionalfitnessassignment）某个体i，其适应度为fi，则其被选取的概率Pi为：如果尺度变换不合适，可能造成早熟。4.2.4遗传操作——选择

个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09574.2基本遗传算法个体选择概率的常用分配方法4.2基本遗传算法

个体选择概率的常用分配方法基于排序的适应度分配（rank-basedfitnessassignment）线性排序（byBaker）

μ为种群大小，i为个体序号，ηmax代表选择压力。4.2.4遗传操作——选择

584.2基本遗传算法个体选择概率的常用分配方法4.2基本遗传算法

个体选择概率的常用分配方法基于排序的适应度分配（rank-basedfitnessassignment）非线性排序（byMichalewicz）i为个体序号，c为排序第一的个体的选择概率。4.2.4遗传操作——选择

594.2基本遗传算法个体选择概率的常用分配方法4.2基本遗传算法

常用选择方法轮盘赌选择法（roulettewheelselection）

4.2.4遗传操作——选择

个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00604.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法随机遍历抽样法（stochasticuniversalsampling）

4.2.4遗传操作——选择

个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00614.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法局部选择法（localselection）(1)线形邻集4.2.4遗传操作——选择

624.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法局部选择法（localselection）(2)两对角邻集4.2.4遗传操作——选择

634.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法局部选择法（localselection）(2)两对角邻集4.2.4遗传操作——选择

644.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法截断选择法（truncationselection）个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阈值（被选作父个体的百分比）。4.2.4遗传操作——选择

截断阈值1％10％20％40％50％80％选择强度2.661.761.20.970.80.34654.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法锦标赛选择法（tournamentselection）随机从种群中挑选一定数目个体（竞赛规模），其中最好的个体作为父个体，此过程重复进行完成个体的选择。4.2.4遗传操作——选择

竞赛规模12351030选择强度00.560.851.151.532.04664.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

常用选择方法早熟现象——适应度高的个体迅速繁殖，使搜索过程过早结束；种群中个体的适应度接近，导致进化过程陷入局部最优点；基本遗传算法达到收敛的代数与选择强度成反比，较高的选择强度是很好的选择方法，但太高会导致收敛过快。4.2.4遗传操作——选择

674.2基本遗传算法常用选择方法4.2.44.2基本遗传算法

实值重组离散重组子个体的每个变量可以按等概率随机地挑选父个体。4.2.5遗传操作——交叉/基因重组

父个体112

25

5父个体2123

4

34子个体1123

4

5子个体212

4

34684.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

实值重组中间重组子个体＝父个体1＋α×（父个体2－父个体1）

α是比例因子，由[-d,1+d]上均匀分布地随机数产生。

d=0时为中间重组，一般取d=0.25。子代的每个变量均产生一个α。4.2.5遗传操作——交叉/基因重组

694.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

实值重组中间重组

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

父个体112255父个体2123434子个体1子个体2α值样本10.51.1-0.1α值样本20.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.5704.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

实值重组中间重组

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

714.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

实值重组线性重组

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

父个体112255父个体2123434子个体1子个体2α值样本10.5α值样本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.9724.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

实值重组线性重组

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

734.2基本遗传算法实值重组4.2.5遗传4.2基本遗传算法

二进制交叉单点交叉

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

744.2基本遗传算法二进制交叉4.2.5遗4.2基本遗传算法

二进制交叉多点交叉

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

754.2基本遗传算法二进制交叉4.2.5遗4.2基本遗传算法

二进制交叉均匀交叉

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

父个体101110011010

父个体210101100101子个体11

11

011

11

1

1

1子个体20

01

100

00

0

0

0

样本101100011010样本2100111001011表示由父个体1提供变量值；0表示由父个体2提供变量值。764.2基本遗传算法二进制交叉4.2.5遗4.2基本遗传算法

实值变异一般采用：二进制变异

4.2.6遗传操作——变异

774.2基本遗传算法实值变异4.2.6遗传4.2基本遗传算法

主程序

4.2.7算法的设计与实现

%用遗传算法进行简单函数的优化clearbn=22;%个体串长度inn=50;%初始种群大小gnmax=200;%最大代数pc=0.75;%交叉概率pm=0.05;%变异概率Continue…784.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

主程序

4.2.7算法的设计与实现

%产生初始种群s=round(rand(inn,bn));%计算适应度,返回适应度f和累积概率p[f,p]=objf(s);Continue…794.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

主程序

4.2.7算法的设计与实现

gn=1;whilegn<gnmax+1forj=1:2:inn%选择操作seln=sel(s,p);%交叉操作scro=cro(s,seln,pc);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%变异操作smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…804.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

主程序

4.2.7算法的设计与实现

s=smnew;%产生了新的种群%计算新种群的适应度[f,p]=objf(s);

%记录当前代最好和平均的适应度[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…814.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

主程序

4.2.7算法的设计与实现

%记录当前代的最佳个体x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…824.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

主程序

4.2.7算法的设计与实现

%绘制曲线subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('历代适应度变化','fonts',10);legend('最大适应度','平均适应度');string1=['最终适应度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自变量');string2=['最终自变量',num2str(xmax(gn))];gtext(string2);End834.2基本遗传算法主程序4.2.7算法的4.2基本遗传算法

计算适应度和累计概率函数

4.2.7算法的设计与实现

%计算适应度函数function[f,p]=objf(s);[innbn]=size(s);%读取种群大小,有inn个个体,个体长度为bnContinue…844.2基本遗传算法计算适应度和累计概率函数44.2基本遗传算法

计算适应度和累计概率函数

4.2.7算法的设计与实现

fori=1:innx=n2to10(s(i,:));%将二进制转换为十进制xx=-1.0+x*3/(power(2,bn)-1);%转化为[-1,2]区间的实数f(i)=ft(xx);%计算函数值，即适应度endf=f';Continue…854.2基本遗传算法计算适应度和累计概率函数44.2基本遗传算法

计算适应度和累计概率函数

4.2.7算法的设计与实现

%计算选择概率fsum=0;fori=1:innfsum=fsum+f(i)*f(i);endfori=1:innps(i)=f(i)*f(i)/fsum;endContinue…864.2基本遗传算法计算适应度和累计概率函数44.2基本遗传算法

计算适应度和累计概率函数

4.2.7算法的设计与实现

%计算累积概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';Backtomain.m874.2基本遗传算法计算适应度和累计概率函数44.2基本遗传算法

计算目标函数值函数

4.2.7算法的设计与实现

%目标函数functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m884.2基本遗传算法计算目标函数值函数4.2.4.2基本遗传算法

选择操作函数

4.2.7算法的设计与实现

%“选择”操作functionseln=sel(s,p);inn=size(p,1);%从种群中选择两个个体fori=1:2r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%选中个体的序号endBacktomain.m894.2基本遗传算法选择操作函数4.2.74.2基本遗传算法

交叉操作函数

4.2.7算法的设计与实现

%“交叉”操作functionscro=cro(s,seln,pc);[innbn]=size(s);Continue…904.2基本遗传算法交叉操作函数4.2.74.2基本遗传算法

交叉操作函数

4.2.7算法的设计与实现

ifrand<pcchb=ceil(rand*(bn-1));%在[1,bn-1]范围内随机产生一个交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m914.2基本遗传算法交叉操作函数4.2.74.2基本遗传算法

变异操作函数

4.2.7算法的设计与实现

%“变异”操作functionsnnew=mut(snew,pm);bn=size(snew,2);snnew=snew;ifrand<pmchb=ceil(rand*bn);%在[1,bn]范围内随机产生一个变异位snnew(chb)=abs(snew(chb)-1);endBacktomain.m924.2基本遗传算法变异操作函数4.2.74.2基本遗传算法

运行程序

4.2.7算法的设计与实现

934.2基本遗传算法运行程序4.2.7算法4.2基本遗传算法

运行程序

4.2.7算法的设计与实现

944.2基本遗传算法运行程序4.2.7算法4.2基本遗传算法

运行程序

4.2.7算法的设计与实现

954.2基本遗传算法运行程序4.2.7算法4.2基本遗传算法

运行程序

4.2.7算法的设计与实现

964.2基本遗传算法运行程序4.2.7算法4.2基本遗传算法

模式将种群中的个体即基因串中的相似样板称为模式。在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。如模式*1*描述了一个四个元的子集{010，011，110，111}。4.2.8模式定理

974.2基本遗传算法模式4.2.8模式定理4.2基本遗传算法

模式阶和定义距模式H中确定位置的个数称为模式H的模式阶，记作O(H)，如O(011*1*)=4。模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越少。4.2.8模式定理

984.2基本遗传算法模式阶和定义距4.2.84.2基本遗传算法

模式阶和定义距模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作δ(H)，如

δ(011*1**)=4。阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。4.2.8模式定理

994.2基本遗传算法模式阶和定义距4.2.84.2基本遗传算法

模式定理（schematheorem）在给定时间步t,一个特定模式H有m个代表串包含在种群A(t)中，记为m=m(H,t)，在再生阶段，每个串根据它的适应值进行复制，一个串Ai的再生概率为4.2.8模式定理

1004.2基本遗传算法模式定理（schematheor4.2基本遗传算法

模式定理（schematheorem）当采用非重叠的n个串的种群替代种群A(t)，可以得到：其中f(H)是在时间t，模式H的串的平均适应度；

而整个种群的平均适应度为4.2.8模式定理

1014.2基本遗传算法模式定理（schematheor4.2基本遗传算法

4.2.8模式定理

模式定理（schematheorem）假设从t=0开始，某一特定模式适应度值保持在种群平均适应度以上一个cf（c为一常数），则模式的选择生长方程为在种群平均值以上（以下）的模式将按指数增长（衰减）的方式复制。1024.2基本遗传算法4.2.8模式定理模4.2基本遗传算法

模式定理（schematheorem）考虑交叉操作，模式H被破坏的概率为δ(H)/(l-1)，模式H生存概率为1-δ(H)/(l-1)，若交叉操作发生的概率为pc，因此对于模式H的生存概率计算为：

同时考虑选择、交叉操作对模式的影响，可得：4.2.8模式定理

H1=*1****0H2=***10*01034.2基本遗传算法模式定理（schematheor4.2基本遗传算法

模式定理（schematheorem）考虑变异操作，单个等位基因存活的概率为1-pm，当模式H中O(H)个确定位都存活时，模式H才被保留，存活概率为：

同时考虑选择、交叉和变异操作对模式的影响，可得：4.2.8模式定理

H1=*1****0H2=***10*01044.2基本遗传算法模式定理（schematheor4.2基本遗传算法

模式定理（schematheorem）

模式定理：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为积木块。4.2.8模式定理

1054.2基本遗传算法模式定理（schematheor4.2基本遗传算法

积木块假设（buildingblockhypothesis）遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。4.2.8模式定理

1064.2基本遗传算法积木块假设（buildingbl4.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遗传算法在模式识别中的应用►1074.3遗传算法的改进►1074.3遗传算法的改进

改进的途径改变遗传算法的组成成分；采用混合遗传算法；采用动态自适应技术；采用非标准的遗传操作算子；采用并行遗传算法等。

1084.3遗传算法的改进改进的途径1084.3遗传算法的改进

改进思路1991年Eshelman提出的一种改进遗传算法；C：跨世代精英选择（Crossgenerationalelitistselection）策略；H：异物种重组（Heterogeneousrecombination）；C：大变异（Cataclysmicmutation）。4.3.1CHC算法

1094.3遗传算法的改进改进思路4.3.1C4.3遗传算法的改进

选择（C：跨世代精英选择）上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；即使当交叉操作产生较劣个体偏多时，由于原种群大多数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。4.3.1CHC算法

1104.3遗传算法的改进选择（C：跨世代精英选择）4.3遗传算法的改进

交叉（H：异物种重组）均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换；确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。4.3.1CHC算法

1114.3遗传算法的改进交叉（H：异物种重组）4.3遗传算法的改进

变异（C：大变异）在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。4.3.1CHC算法

1124.3遗传算法的改进变异（C：大变异）4.4.3遗传算法的改进

参数分析交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，Pm过大，变成纯粹的随机搜索；4.3.2自适应遗传算法

1134.3遗传算法的改进参数分析4.3.2自4.3遗传算法的改进

自适应策略使Pc和Pm能够随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加；而当群体适应度比较分散时，使Pc和Pm减少；对于适应度较高的个体，对应于较低的Pc和Pm；而较低适应度的个体，对应于较高的Pc和Pm。在保持群体多样性的同时，保证遗传算法收敛性。4.3.2自适应遗传算法

1144.3遗传算法的改进自适应策略4.3.24.3遗传算法的改进

自适应方法fmax——群体中最大的适应度值；favg——每代群体的平均适应度值；f’——要交叉的两个个体中较大的适应度值；f——要交叉或变异的个体适应度值；4.3.2自适应遗传算法

k1、k2、k3、k4取(0,1)的值1154.3遗传算法的改进自适应方法4.3.24.3遗传算法的改进

自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2；采用精英选择策略，将优良个体直接复制到下一代。4.3.2自适应遗传算法

1164.3遗传算法的改进自适应方法进一步改进4.4.3遗传算法的改进

自适应方法进一步改进4.3.2自适应遗传算法

1174.3遗传算法的改进自适应方法进一步改进4.4.3遗传算法的改进

小生境概念小生境（niche）：生物学中，特定环境中的一种组织功能；在SGA中，容易“近亲繁殖”；NGA（NicheGenericAlgorithm），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。4.3.3基于小生境技术的遗传算法

1184.3遗传算法的改进小生境概念4.3.34.3遗传算法的改进

选择策略预选择机制、排挤机制、分享机制；预选择（preselection,1970）机制当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。4.3.3基于小生境技术的遗传算法

1194.3遗传算法的改进选择策略4.3.3基4.3遗传算法的改进

排挤（crowding,1975）机制设置排挤因子CF（CF=2或3），随机选取1/CF个个体组成排挤成员，排挤与其相似（用距离来度量）的个体；个体之间的相似性可用个体编码串之间的海明距离来度量。4.3.3基于小生境技术的遗传算法

1204.3遗传算法的改进排挤（crowding,19754.3遗传算法的改进

共享（sharing,1987）机制通过个体之间的相似性程度的共享函数来调整各个体的适应度；共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；4.3.3基于小生境技术的遗传算法

1214.3遗传算法的改进共享（sharing,1987）4.3遗传算法的改进

共享（sharing,1987）机制共享函数的值越大，表明个体之间越相似，记为S(dij)，dij为两个个体i和j之间的距离；

σshare是niche的半径，由使用者给定。4.3.3基于小生境技术的遗传算法

1224.3遗传算法的改进共享（sharing,1987）4.3遗传算法的改进

共享（sharing,1987）机制共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi：在距离为σshare的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。4.3.3基于小生境技术的遗传算法

1234.3遗传算法的改进共享（sharing,1987）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遗传算法在模式识别中的应用►1244.3遗传算法的改进►1244.4遗传算法的应用

约束最优化问题（ConstrainedOptimizationProblems）的表述

4.4.1解决带约束的函数优化问题

1254.4遗传算法的应用约束最优化问题（Constrai4.4遗传算法的应用

4.4.1解决带约束的函数优化问题

测试函数（Benchmark问题）

其全局最优解和最优值为1264.4遗传算法的应用4.4.1解决带约