遗传算法的实现及应用举例 教育学习

第六节算法实现及应用,一、算法实现遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定问题编码方案确定适配值函数设计遗传算子（选择、交叉、变异）确定算法参数确定算法终止条件生成初始种群,1,优质课件,SGA实现,个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是负数。,2,优质课件,为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：对于目标函数是求极大化，方法为：,3,优质课件,式中，为一个适当地相对比较小的数它可用下面几种方法之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。,4,优质课件,比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(RouletteWheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。,5,优质课件,单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。,6,优质课件,基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。,7,优质课件,简单演示,问题：求（1）编码：编码长度为5（2）初始群体生成：群体大小设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度函数：,8,优质课件,（4）轮盘赌选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择11000和01101交配产生下一代,9,优质课件,（5）交叉操作：发生交叉的概率取大交叉点位置的选取是随机的（单点交叉）01101011001100011001,10,优质课件,（6）变异：发生变异的概率取小改变某个字节1100111101（7）新群体的产生：保留上一代最优个体，1个新个体取代旧个体11101，11000，01000，10011（8）重复上述操作20次，或许就能够得到最优解！,11,优质课件,应用实例：TSP,问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学描述给定图G=(V,E),V为顶点集,E为边集，确定一条长度最短的Hamilton回路,12,优质课件,TSP问题,问题复杂度:指数增长的！(NP完全问题),12个城市，具有39916800条不同的路径。,一条路径对应一个排列！,交叉算子,传统的交叉算子可能产生无效路径。,13,优质课件,交叉算子,（1）基于位置的交叉,把一个父代在向量上的被选元的位置强加到另一个父代。,父代1：12345678910,父代2：59246110738,所选位置：*,子代1：19236457810,子代2：92345618107,14,优质课件,交叉算子,（2）部分映射交叉,利用父代所选段内元的对应定义子代。,父代1：26438151079,父代2：85110762439,子代1：51437621089,子代2：72610815439,15,优质课件,变异算子,起双重作用：1、提供和保持群体的多样性；2、搜索算子的作用。,(1)基于位置的变异：随机选择两个元，然后把第二个元放在第一个元之前；,(2)基于次序的变异：随机选择两个元，然后交换他们的位置；,(3)打乱变异：随机选择一段，然后打乱这段内的次序。,16,优质课件,编码方案路径表达：对一个旅行最自然的表达一个旅行517894623的编码就是（517894623）编码空间和解空间一一对应，总量为n!个？其实一些解是相同的，因为（51789|4623）=（4623|51789）二者是同一个解(n-1)!/2,应用实例1：TSP,17,优质课件,适应度函数就取为目标函数的倒数，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定,18,优质课件,选择操作算子:轮盘式选择首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i。,19,优质课件,交叉操作算子Davis提出OX算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代例如：p1=（123|4567|89）p2=（452|1876|93）首先保持中间部分o1=（XXX|4567|XX）o2=（XXX|1876|XX）,20,优质课件,交叉操作算子然后移走p2中已在o1中的城市4、5、6和7后，得到21893该序列顺次放在o1中：o1=（218|4567|93）类似地，可以得到另一个后代：o2=（234|1876|59）,21,优质课件,变异操作算子采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转例如原个体：（123456789）随机选择两点：（12|3456|789）倒置后的个体：（12|6543|789）,22,优质课件,23,优质课件,中国城市TSP的一个参考解,24,优质课件,应用实例2：函数优化,函数优化编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处理，然后根据离散化后待定解的个数选择合适长度的二进制字符串进行编码例如；0，1，计算精度0.001,则0，0.001,0.002,0.998,0.999,1.000，个数为1001则用长度为10的二进制字符串一次表征所有离散点0000000000，000000001，1111110001。,25,优质课件,适应度函数例如，f(x)=x2-x5，取Cmax=2,即可得到满足要求的F(x)其它的就类似于TSP的求解了,26,优质课件,已知函数其中，用遗传算法求解y的最大值。,例1多元函数优化问题,27,优质课件,运行步骤,28,优质课件,运行步骤,29,优质课件,运行步骤,30,优质课件,运行步骤,31,优质课件,运行步骤,32,优质课件,运行步骤,33,优质课件,运行步骤,34,优质课件,35,优质课件,例2一元函数优化问题,问题的提出一元函数求最大值：,36,优质课件,问题的提出用微分法求取f(x)的最大值：解有无穷多个：,37,优质课件,问题的提出当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间-1,2内的最大值点此时，函数最大值f(x19)比f(1.85)=3.85稍大。,38,优质课件,编码表现型：x基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系：若要求求解精度到6位小数，区间长度为2-(-1)3，即需将区间分为3/0.000001=3106等份。所以编码的二进制串长应为22位。,39,优质课件,产生初始种群产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模），如30，50，111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000,40,优质课件,计算适应度不同的问题有不同的适应度计算方法本例：直接用目标函数作为适应度函数将某个体转化为-1,2区间的实数：s=x=0.637197计算x的函数值（适应度）：f(x)=xsin(10x)+2.0=2.586345,41,优质课件,计算适应度二进制与十进制之间的转换：第一步，将一个二进制串（b21b20b0）转化为10进制数：第二步，x对应的区间-1,2内的实数：,(0000000000000000000000)-1(1111111111111111111111)2,42,优质课件,遗传操作选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异,43,优质课件,模拟结果设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。得到的最佳个体：smax=;xmax=1.8506;f(xmax)=3.8503;,44,优质课件,模拟结果进化的过程：,45,优质课件,主程序,%用遗传算法进行简单函数的优化clearbn=22;%个体串长度inn=50;%初始种群大小gnmax=200;%最大代数pc=0.75;%交叉概率pm=0.05;%变异概率,Continue,算法的设计与实现,46,优质课件,主程序,%产生初始种群，0,1向量s=round(rand(inn,bn);%计算适应度,返回适应度f和累积概率pf,p=objf(s);,Continue,47,优质课件,主程序,gn=1;whilegnl）特征送入分类器进行识别。,遗传算法的应用,5在模式识别中的应用,150,优质课件,用遗传算法进行特征提取例：作品鉴别个体的表示：l位长，每位代表一个特征的序号，不可重复；适应度函数的设计：识别率的函数；遗传算子：符合个体编码要求的算子。,遗传算法的应用,5在模式识别中的应用,151,优质课件,遗传算法今后研究的主要课题,1、优化搜索方法的研究2、学习系统的遗传算法研究3、生物进化与遗传算法的研究4、遗传算法的并行分布处理5、人工生命与遗传算法的研究,152,优质课件,GA研究内容与方向,153,优质课件,与GA相关的重要学术期刊与国际会议,重要学术期刊EvolutionaryComputationIEEETransactionsonEvolutionaryComputation重要国际会议InternationalConferenceonGeneticAlgorithmACMGeneticandEvolutionaryComputationConferenceWorkshoponFoundationsofGeneticAlgorithmsandClassifierSystemsGeneticProgrammingConferenceInternationalWorkshoponArtificialLife,154