第二章-遗传算法.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第,2,章 遗传算法,黔南民族师范学院数学系,2.1,遗传算法的基本结构,在遗传算法中，在对规模为,N,的种群初始化和对种群中个体计算适应值后，按照基于个体适应值的某个概率函数选择,N,个父体，适应值较大的个体被选择作为父体的可能性较大。通过杂交，,N,个父体产生,N,个后代，,N,个后代以一定的概率进行变异，并都存活下来，形成下一代种群。在遗传算法中，杂交算子是一个主要的遗传算子，而以较小的概率对孩子进行变异。,2.1,遗传算法的基本结构,2.2,一个例子,考虑下面的优化问题：,目标函数的三维图形如下图所示。,2.2,一个例子,2.2,一个例子,1,个体的编码,问题的可能解为实数对 的形式。我们将问题的可能解编码为二进制位串。为此，首先将每个变量编码为二进制位串，然后将表示各个变量的二进制数串连接起来便得到问题可能解的一种表示。表示每个变量的二进制位串的长度取决于变量的定义域和所要求的精度。,设 ，所要求的精度为小数点后,t,位。这要求将区间划分为至少 份。假设表示变量 的位串的长度用 表示，则 可取为满足下列不等式的最小整数,m,：,2.2,一个例子,即有,将的二进制表示转换为十进制可按下式计算：,其中 表示变量 的二进制子串,对应的十制数。,2.2,一个例子,对于上面的优化问题，假定所要求的精度为小数点后,4,位，那么由,知，表示变量 的二进制位串的长度为 。,由,知，表示变量 的二进制位串的长度为 。,2.2,一个例子,表示问题解的二进制位串如下图所示,:,其中前,18,位表示变量 ，后,15,位表示变量 。,2.2,一个例子,例如给定下列,33,位二进制位串,那么前,18,位所表示的变量 的值为：,2.2,一个例子,而后,15,位所表示的变量 的值为：,二进制位串所表示问题的可能解为,:,2.2,一个例子,2,产生初始种群,假定初始种群的规模为 。,随机产生初始种群如下：,1.3,演化算法的设计,1.3,演化算法的设计,3,计算适应值,在本例中，这是一个最大值问题，我们直接取目标函数,作为适应函数 。,计算一个染色体的适应值的过程由下面两步组成：,(1),将该染色体转换为所表示的问题可能解；,(2),计算个体的适应值。,1.3,演化算法的设计,例如,2.2,一个例子,4,父体选择,采用轮盘赌选择,(Roulette Wheel Selection),。轮盘赌选择是遗传算法中使用最多的选择策略之一。,轮盘赌选择模拟博彩游戏中的轮盘赌。,一个轮盘被划分为,N,个扇形，每个扇形,表示种群中的一个染色体，而每个扇,形的面积与它所表示的染色体的适应,值成正比。,表示,6,个染色体的轮盘,1,2,3,4,5,6,2.2,一个例子,为了选择种群中的个体，设想有一个指针指向轮盘，转动轮盘，当轮盘停止后，指针所指向的染色体被选择。因此一个染色体的适应值越大，表示该染色体的扇形面积就越大，因此它被选择的可能性也就越大。,轮盘赌选择可以如下实现：,(1),计算种群中所有染色体适应值之和：,2.2,一个例子,(2),计算每个染色体的选择概率,(3),计算每个染色体的累计概率,(4),转动轮盘,N,次，从中选出,N,个染色体。,2.2,一个例子,选择过程可如下实现：,用,0,1,中的一个随机数,r,来模拟转动一次轮盘，轮盘停止转动后指针所指向的位置。若 ，这说明指针指向第一个扇形，这时选择第一个染色体 ，一般若 ，这说明指针指向第,k,个扇形，这时选择第,k,个染色体。,2.2,一个例子,若种群中各染色体的累计概率如下：,现在转动圆盘,20,次，每一次选择一个染色体。假定所产生,0,1,中的,20,个随机数为,第一个随机数,=0.513870,比 大，但比 小，故所选择的第一个染色体为 ；第二个随机数,=0.175741,比 大，但比 小，故所选择的第二个染色体为 ；如此进行下去，所选择的,20,个染色体为：,1.3,演化算法的设计,轮盘赌选择算法如下所示。,其中,random,生成,0,1,上的一个随机数,。,1.3,演化算法的设计,5,遗传算子,遗传算子有两种：杂交算子和变异算子。,杂交算子：使用单点杂交。该方法对两个父体进行杂交，杂交后产生两个后代个体。,单点杂交过程如下：设二进制位串的长度为,L,，随机地产生一个整数,pos,作为杂交点的位置,，然后将两个父体在该杂交点右边的子串进行交换，生成两个后代个体。,1.3,演化算法的设计,单点杂交的示意图。,父体,1,父体,2,杂交点,交换,后代,1,后代,2,1.3,演化算法的设计,杂交算子的应用过程：从步骤,4,中产生的父体中，按一定的概率,p,c,从中挑选出若干个染色体进行杂交。首先从,0,1,中产生,N,个随机数 ，若 ，则挑选父体中的第,k,个染色体。若这样挑选出来的染色体是奇数个，则或从父体中随机地再挑选一个染色体，或从已挑选的染色体中删除一个。这样共挑选出来偶数个染色体，再将这偶数个染色体随机地两两配对进行杂交。,2.2,一个例子,对本例而言，假定 ，所产生的,20,个随机数为：,0.822951,0.151932,0.625477,0.314685,0.346901,0.917204,0.519760,0.401154,0.606758,0.785402,0.031523,0.869921,0.166525,0.674520,0.758400,0.581893,0.389248,0.200232,0.355635,0.826927,这意味着 被选择进行杂交。随机地对这四个染色体配对，譬如说 为一对和 为一对。,2.2,一个例子,下面讨论变异算子。,变异算子的目的在于引入种群中染色体的多样性，防止算法的过早收敛。,变异算子以某一预先指定的概率,p,m,对种群中染色体的基因进行变异。若染色体的某一基因被选择进行变异时，当该位为,1,时，则变为,0,，否则变为,1,。,2.2,一个例子,在遗传算法中应用变异算子过程是：对种群中的每一个染色体的每一基因，产生一个随机数,r,，若 ，那么该基因进行变异，否则不进行变异。,在实现遗传算法时，一个常用的方法是将到当前代为止演化的最好个体单独存放起来，在遗传算法结束后，将演化过程中发现的最好个体作为问题的最优解或近似最优解。,2.3,遗传算法的实现技术,虽然遗传算法的结构非常简单，但用遗传算法求解问题的功效常常依赖于一些具体的实现技术，与所采用的编码方案，选择策略，遗传算子等有密切的关系，本节介绍遗传算法的一些常用实现技术。,2.3.1,编码,二进制编码,例,2.1 0-1,背包问题：给定,n,种物品和一个背包，假设第,i,种物品重,价值为,背包可容纳的重量为,W,求将物品放入背包的一种放法，使得背包所装的物品价值最大,.,0-1,背包问题可描述为下列优化问题：,2.3.1,编码,二进制编码存在以下缺点,：,(1),相邻整数的二进制编码可能具有较大的,Hamming,距,离。,例如,15,和,16,的二进制编码分别为,01111,和,10000,，它们的,Hamming,距离为,5,。,(2),在求解连续优化问题时，采用二进制编码，一般要预先给出解的精度以确定串长，而一旦精度确定后难以在算法中调整。从而使算法缺乏微调,(,fine-tuning,),功能。,2.3.1,编码,(3),在求解高维、高精度优化问题时，二进制编码串将非常之长，从而使算法的搜索效率很低。,例如，若问题可能解的形式为,解的精度为小数点后,6,位，那么问题可能解的二进制编码的长度为,3000,。,2.3.1,编码,Gray,编码,采用,Gray,编码的目的是为了克服二进制编码的,Hamming,悬崖缺陷,。,n,位,Gray,编码将 中的每个整数编码为一个长度为,n,的二进制位串，使得相邻整数的二进制位串的,Hamming,距离为,1,，,这里,0,和 认为是相邻的。,2.3.1,编码,3,位二进制码与,Gray,码,0 000 000,1 001 001,2 010 011,3 011 010,4 100 110,5 101 111,6 110 101,7 111 100,整数 二进制码,Gray,码,2.3.1,编码,有许多不同的,n,位,Gray,码。,例如当 时,，,序列,：,00,，,01,，,11,，,10,和,00,，,10,，,11,，,01,都是,2,位,Gray,码,。,n,位二元,-,反射,Gray,码递归定义如下,：,(1),1,位二元,-,反射,Gray,码为,0,，,1,；,(2),若位二元,-,反射,Gray,码为,，,那么,n,位,二元,-,反射,Gray,码为,2.3.1,编码,下面给出非负整数的,n,位二进制码与二元,-,反射,Gray,码之间的转换算法。,设整数 的,n,位二进制码为,，,其中 为最高位,，,即有,，,相应的,Gray,码为,，,则从二进制码到,Gray,码的变换为,：,2.3.1,编码,而从,Gray,码到二进制码的变换为：,例如，二进制码,1101011,对应的,Gray,码为,1011110,。,2.3.1,编码,实数向量编码,例,2.2,考虑下列优化问题,其中,。,由于问题解的形式为实数向量，所以我们可以直接用实数向量 作为解的编码。,2.3.1,编码,排列编码,例,2.3,旅行商问题,(TSP),：,一个商人欲从自己所在的城市出发，到若干个城市推销商品，然后回到其所在的城市。如何选择一条周游路线使得商人经过每个城市一次且仅一次后回到起点且使他所走过的路径最短？,设有,n,个城市,，,分别用,1,2,3,n,来表示，两个城市,i,和,j,之间的距离用,d,ij,来表示，那么商人的一条周游路线,可以用,1,2,3,n,的一个排列,来表示,。,2.3.1,编码,TSP,可以描述为下列优化问题：,其中 为,1,2,n,的一个全排列,。,2.3.1,编码,结构式编码,例,2.4,运输问题：已知有,m,个产地，可以供应某种产品。有,n,个销地，需要该种产品。,m,个产地的产量分别为 ，而,n,个销地的销量分别为,，,从第,i,个产地到第,j,个销地的单位运价为 。在产销平衡的条件下，如何制定运输方案，使总的运输费用最小？,若用 表示从第,i,个产地到第,j,个销地的运输量，则上述运输问题可以描述为下列优化问题,：,2.3.1,编码,2.3.1,编码,这时，问题解的一种自然的表示是一个的矩阵：,树编码在遗传程序设计中用以演化程序或表达式，而图编码则在演化神经网络时经常用到。,2.3.2,适应函数及其比例变换,设计适应函数时，通常应遵守以下原则：,最优解与具有最大适应值的个体相对应,.,适应值能够反映个体质量的差异,.,计算量应尽可能的少,.,此外，有些选择策略，譬如轮盘赌选择，还要求适应值非负。,2.3.2,适应函数及其比例变换,1,常见的适应函数,(1),原始应函数,原始适应函数是直接由目标函数表示的适应函数。,当优化问题为 时，适应函数可取为 ；而当优化问题为 时，适应函数可取为 。,原始适应函数简单直观，直接反映了优化问题的求解目标。但存在以下不足之处：适应值有可能为负，这样就不能满足某些选择策略的要求。,2.3.2,适应函数及其比例变换,(2),简单适应函数,为了防止适应值为负的情形，常常需要对目标函数作简单变换。,对优化问题 ，适应函数可定义为 ，其中 是目标函数的一个下界。在 未知的情况下，可以用当前代或到当前代为止的各演化代中 的最小值来替代。,对优化问题 ，适应函数可以定义为 ，其中 是目标函数的一个上界，在 未知的情况下，可以用当前代或到当前代为止的各演化代中 的最大值来替代。,2.3.2,适应函数及其比例变换,也可以对目标函数作其它的变换。,对于优化问题 ，适应函数可以定义为,其中,对于优化问题 ，适应函数可以定义为,其中,2.3.2,适应函数及其比例变换,2,适应值比例变换,适应值比例变换是将个体,v,的原始适应值 通过一个变换函数 转换为一个新的适应值，即有,通常函数 将原始适应值变换到一个合适的范围，使得变换后个体之间的适应值保持合理的差距，以满足早期限制竞争，晚期鼓励竞争的需要。函数 的不同形式导致了不同的适应值比例变换方法。,2.3.2,适应函数及其比例变换,(1),线性比例变换,设 为原适应函数，变换后的适应函数为 ，那么有,其中 为常数且 。常数 的选择有多种方法，但应满足以下条件：,原平均适应值等于变换后的平均适应值；,变换后的最大适应值等于原平均适应值的,c,倍，其中,c,是一个预先指定的常数。,2.3.2,适应函数及其比例变换,设,分别表示原平均适应值和变换后的平均适应值，分别表示原最大适应值和变换后的最大适应值，那么由条件 ，得,解上述方程组得,2.3.2,适应函数及其比例变换,当,c,取不同的值时，得到不同的,a,b,。当种群中个体的数目为 时，常取,c,为,。,图,2.4,线性比例变换,图,2.5,变换后出现负适应值的情况,2.3.2,适应函数及其比例变换,(2),截断,截断是,Forrest,为改进线性比例变换而提出的，以便能将问题的信息结合到映射中，从而能适应有负适应值问题的需要。,Goldberg,改进后的公式为：,这里，,C,是一个小整数，通常取为 ，为种群中个体适应值的标准方差，为种群中个体的平均适应值。当 为负时，令其为,0,。,2.3.2,适应函数及其比例变换,(3),幂函数变换,该方法是由,Gillies,提出的，其中函数取原始适应值的指定幂的形式：,这里 是一个常数，,Gillies,取 。,最好与最坏染色体的适应值之差随着 的增加而增加。当 趋于,0,时，其差也趋于,0,，采样变为随机搜索。当,时，其差加大。,2.3.3,父体选择策略,父体选择策略可以分为三类：,基于适应值比例的选择策略,基于排名的选择策略,基于竞争的选择策略。,2.3.3,父体选择策略,1.,基于适应值比例的选择,在该方法中，每个个体被选择的期望个数与该个体的适应值的大小成比例。,在这种选择方法中，首先根据当前种群中个体的适应 值，按下式计算出各个个体的选择概率：,2.3.3,父体选择策略,(1),确定性选择,确定性选择根据计算出来的选择概率，按照下列式计算每个个体的期望数：,首先对第,i,个个体选择 个，这样选择的染色体个数通常要比种群的规模,N,小，不足的部分，再按照每个个体期望数的小数部分从大到小的次序选择若干个补齐。,2.3.3,父体选择策略,(2),轮盘赌选择,轮盘赌选择是遗传算法中用的最多的选择策略之一。在轮盘赌选择中，一个轮盘被划分为,N,个扇形，第,i(i=1,2,N),个扇形面积的大小与第,i,个个体的适应值成正比。然后转动轮盘,N,次，每次选择一个个体。,轮盘赌选择与确定性选择的不同之处在于：种群中的每个个体在轮盘赌选择策略下，都有被选择的机会，而在确定性选择策略下，具有较小适应值的个体将被剥夺生存的权利。,2.3.3,父体选择策略,(3),随机通用采样,(stochastic universal sampling),随机通用抽样首先构造一个轮盘，轮盘被划分为,N,个扇形，每个扇形的面积与它表示的个体的期望个数成比例。第,i,个染色体的期望个数为 。,转动轮盘一次，当轮盘停,止转动后，将,N,个指针所指向,的,N,个个体选择出来。,图,2.7,随机通用采样示意图,e,1,e,2,e,3,e,N,随机通用采样算法,2.3.3,父体选择策略,(4)Boltzmann,选择,在,Boltzmann,选择中，选择概率由下式计算：,其中,T,是一个控制参数。当,T,取较大值时，具有较小的选择压力，即适应值的相对比例变小，当,T,取较小值时，具有较大的选择压力，即适应值的相对比例变大。当用上式计算出个体的选择概率后，再用轮盘赌方法进行父体的选择。,2.,基于排名的选择,(1),线性排名选择,在线性排名选择中，先将种群中的个体按照其适应值从小到大排序为 ，即 是适应值最小的个体，是适应值最大的个体，然后按照某个关于个体排名的线性函数来分配每个个体的选择概率。有许多不同的线性函数可以用来计算个体的选择概率，下面是一种常用的选择概率分配方法。,2.3.3,父体选择策略,假定 在选择操作后的期望数量为 ，即有,.,在选择操作后的期望数量为 ，即有,.,其中,分别为 ，的选择概率,是预先指定的常数。,其它个体的期望数量按等差数列计算。即若令,那么第,i,个个体的的期望数量为,2.3.3,父体选择策略,于是个体 的选择概率为,其中 为最差个体的选择概率，为最好个体的选择概率。,由 可以推出 ，所以要求 满足,2.3.3,父体选择策略,(2),指数排名选择,指数排名选择与线性排名选择类似，先将种群中的个体按照其适应值从小到大排序为 ，然后按照下式分配个体的选择概率,其中 是一个预先指定的常数。,2.3.3,父体选择策略,3.,基于局部竞争的选择,(1),锦标赛,(tournament),选择,锦标赛选择从种群中随机地选择,k,个个体进行比较，适应值最大的个体将被选择作为生成下一代的父体，这个过程反复进行,N,次。参数,k,称为竞争规模，通常取,k=2,。,2.3.3,父体选择策略,(2)Boltzmann,锦标赛选择,该方法首先在种群中选择两个个体 ，若 ，则选择适应值较大的个体作为父体；否则计算,若 ，则选择适应值较小的个体，否则选择适应值较大的个体。是两个控制参数。称为阈值，是一个常数；而,T,则类似于模拟退火算法中温度，它随着演化的推进逐渐减小,(,称为冷却过程,),。,2.3.4,遗传算子设计,1.,二进制编码,(1),杂交算子,点式杂交,点式杂交分为单点杂交和多点杂交。,图,2.8,两点杂交示意图,父体,1,父体,2,后代,1,后代,2,2.3.4,遗传算子设计,均匀杂交,随机地产生一个与父体等长的二进制位串，其中,0,表示不交换，,1,表示交换，这个二进制位串称为杂交模板。然后根据所产生的杂交模板对两个父体进行杂交。,2.3.4,遗传算子设计,例如，给定两个父体如下：,f1=(1 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1),f2=(0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0),假设所产生的杂交模板为：,(0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1),所得到的两个后代如下：,s1=(1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0),s2=(0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1),2.3.4,遗传算子设计,(2),变异算子,二进制编码时的变异算子非常简单，只是依一定的概率,(,称为变异概率,),将所选个体的位取反。即若是,1,，则取,0,；若是,0,，则取,1,。,2.3.4,遗传算子设计,2.,实数向量编码,在下面的讨论中，我们假设解向量的形式为,(1),杂交算子,离散杂交,离散杂交模仿二进制编码的杂交算子。最基本的是单点杂交，其方法与二进制编码时一样。,2.3.4,遗传算子设计,给定两个父体,随机地在,1,之间选择一个杂交位置,k,，将两个父体在位置,k,右端的两个子串进行交换，便得到两个后代：,类似地，可将二进制编码方式下的多点杂交，均匀杂交推广到实数向量表示中。,2.3.4,遗传算子设计,算术杂交,(1),部分算术杂交。,部分算术杂交首先在父体向量中选择一部分分量，譬如说第,k,个分量之后的 个分量，然后生成,0,1,上的,个随机数 ，经杂交算子后，所得到的两个后代为,若取 ，则只需要生成一个随机数 。,2.3.4,遗传算子设计,(2),整体算术杂交,先生成,0,1,上的,n,个随机数 ，经杂交算子后，所得到的两个后代为,同样，可以取,2.3.4,遗传算子设计,(2),变异算子,均匀变异,设 是要变异的个体，均匀变异如下产生的一个后代：首先选一随机整数 ，然后产生后代 ，其中 是 中服从均匀分布的一个随机数。,2.3.4,遗传算子设计,非均匀变异,设 是要变异的个体，非均匀变异如下产生的一个后代：首先选一随机整数 ，然后产生后代 ，其中,这里,t,是当前演化代数，函数 返回 中的一个值，并且 随,t,的增加而趋于,0,的概率增大。,2.3.4,遗传算子设计,函数的具体表达式可以取为,或,其中,r,是,0,1,上的一个随机数，,T,表示最大演化代数。,b,是确定非均匀度的一个参数，通常,b,的取值为,25,。,