第七章遗传算法的理论基础.ppt

7.1 模式定理模式定理 l模式定理是由模式定理是由Holland所提出的，其目的是从理所提出的，其目的是从理论上解上解释遗传算法的有效性。算法的有效性。lHolland的模式定理是的模式定理是针对简单遗传算法算法(SGA)而言的，即假定在而言的，即假定在遗传算法中，种群的算法中，种群的规模不模不变，使用二使用二进制制编码、基于适、基于适应值比例的比例的选择策略、策略、单点点杂交算子和通常的交算子和通常的变异算子。异算子。1.7.1 模式定理模式定理l字符集字符集0,1,*上的一个字符串称上的一个字符串称为一个模式一个模式l在一个模式中，在一个模式中，*表示一个不确定的字符，即表表示一个不确定的字符，即表示示0或或1，所以一个模式可以表示一个二，所以一个模式可以表示一个二进制位串制位串的集合。的集合。l例例 模式模式*0101表示集合表示集合00101,10101，而模式，而模式0*1*表示集合表示集合00010，00011，00110，00111，01010，01011，01110，01111。l在一个模式中，字符在一个模式中，字符0或或1所出所出现的位置称的位置称为确定确定位置，字符位置，字符*所出所出现的位置称的位置称为不确定位置。不确定位置。2.7.1 模式定理模式定理l模式模式H中确定位置的个数称中确定位置的个数称为模式模式H的的阶,记为l例例l模式模式H中第一个确定位置与最后一个确定位置之中第一个确定位置与最后一个确定位置之间的距离称的距离称为模式模式H的定的定义长度，度，记为l例例l设s是一个是一个长度度为的二的二进制位串，制位串，H是一个是一个长度度为的模式，若的模式，若 则称称s与模式与模式H匹配。匹配。3.7.1 模式定理模式定理l二二进制位串制位串00与下列模式匹配：与下列模式匹配：00，*0，0*，*二二进制位串制位串110与下列模式匹配：与下列模式匹配：110,*10,1*0,11*,*0,*1*,1*,*.l定定义 假假设 表表示示SGA在在第第t代代时的的种种群群，f 为SGA所所使使用用的的适适应函函数数，H为任任一一模模式式，则称称P(t)中中与与模模式式H匹匹配配的的个个体体的的平平均均适适应值为模模式式H在在第第t代代的的适适应值，记为 即有即有4.7.1 模式定理模式定理l例例 假定当前种群中的个体及适假定当前种群中的个体及适应值如表如表1所示，所示，则模式模式H及其适及其适应值如表如表2所示。所示。个体个体适适应值1011011001000100101101105 51 12 23 3表表1 1 个体及其适个体及其适应值H Hf(H,t)f(H,t)*0 0*1*1*0000(5+1+2+3)/4=2.75(5+1+2+3)/4=2.75(1+2+3)/3=21+2+3)/3=2(2+3)/2=2.52+3)/2=251/1=11/1=1表表2 2 模式及其适模式及其适应值5.7.1 模式定理模式定理l定理定理7.1(模式定理模式定理)设 表示表示SGA在第在第t代代时的种群，的种群，SGA的的杂交概率和交概率和变异概率分异概率分别为 和和 H为任一模式，任一模式，表示第表示第t代种群中与代种群中与H匹配个体的个数，匹配个体的个数，则有估有估计式式 其中其中 为P(t)中个体的平均适中个体的平均适应值，为个体的个体的编码长度。度。6.6.1 模式定理模式定理l证 首先考首先考虑选择对模式模式H的影响。的影响。由于由于SGA采用基于适采用基于适应值比例的比例的选择策略，所以策略，所以在第在第t代种群代种群P(t)中，与中，与H匹配的个体被匹配的个体被选择作作为父体的个数的期望父体的个数的期望值为7.6.1 模式定理模式定理l再考再考虑杂交算子交算子对模式的影响。模式的影响。l杂交算子随机地交算子随机地选取取1到到 中的一个位置，中的一个位置，并交并交换两个父体中所两个父体中所选取位置右取位置右边的子串。的子串。显然，然，若若选取的取的杂交位置不在模式交位置不在模式H的第一个确定位置的第一个确定位置和最后一个确定位置之和最后一个确定位置之间，那么原来属于，那么原来属于H中的中的个体个体经杂交后仍然属于交后仍然属于H。l若所若所选取的取的杂交位置在模式交位置在模式H的第一个确定位置的第一个确定位置和最后一个确定位置之和最后一个确定位置之间，那么原来属于，那么原来属于H中的中的个体个体经杂交后有可能不再属于交后有可能不再属于H。8.l例如例如 l那么有那么有 若若111000与与101011进行行杂交，且随机交，且随机选择的的杂交位置交位置为3，杂交后所得到的两个后代分交后所得到的两个后代分别为111011和和101000，这两个后代均不属于两个后代均不属于H。9.6.1 模式定理模式定理l原来属于原来属于H中的个体中的个体经杂交后也有可能仍然属于交后也有可能仍然属于H。例如。例如 若在上面的例子中若在上面的例子中111000与与001100进行行杂交，交，杂交位置仍交位置仍为3，那么，那么杂交后所得到的交后所得到的两个子串两个子串为111100和和001000，其中后代，其中后代111100仍然属于仍然属于H。l属于模式属于模式H的个体的个体经杂交后不属于模式交后不属于模式H的概率的概率至多至多为10.6.1 模式定理模式定理l属于模式属于模式H的个体的个体经杂交后仍属于模式交后仍属于模式H的概率的概率至少至少为 l由于由于选择和和杂交是相互独立的，所以交是相互独立的，所以经过选择和和杂交后种群中近似地有交后种群中近似地有 个与个与H匹配的个体匹配的个体 11.6.1 模式定理模式定理l最后最后讨论变异算子异算子对模式模式H的影响。的影响。l对于一个属于模式于一个属于模式H的个体的个体v，变异算子以概率异算子以概率对v的每一位相互独立地的每一位相互独立地进行行变异，当且异，当且仅当当变异算子在异算子在H的的 个确定位置上不个确定位置上不对v进行行变异异时，经变异算子后所得到的个体仍然属于异算子后所得到的个体仍然属于H。由于由于对某一位不某一位不进行行变异的概率异的概率为 ，于是属于模式，于是属于模式H中个体中个体v经变异后仍然属于模异后仍然属于模式式H的概率的概率为12.6.1 模式定理模式定理l经选择、杂交、交、变异操作后，第异操作后，第t+1代中包含模代中包含模式式H的个体数目的个体数目 有以下估有以下估计式：式：13.6.1 模式定理模式定理l推推论 在在SGA中，定中，定义长度度较短、低短、低阶且适且适应值大于种群平均适大于种群平均适应值的模式的模式H，在种群中的数目，在种群中的数目呈指数增呈指数增长 证 设对任意任意 都有都有 其中其中 为一个常数。并一个常数。并设14.6.1 模式定理模式定理l当当时，由定理知，由定理知 于是推于是推论成立。成立。15.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析l 定义 设 是遗传算法当代数为t时的种群，为适应函数，表示种群的最优适应值，表示全局最优适应值。若 则称遗传算法依概率收敛于全局最优解。16.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析17.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析l定理7.2 若杂交概率 和变异概率 满足 适应函数 不恒等于一个常数，则SGA不能依概率收敛于全局最优解。18.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析l定理7.2说明了简单遗传算法不能依概率收敛到全局最优解，但只要对简单遗传算法作一点改动，每次将当前找到的最好解保留下来，在算法结束后，将所保留的最好解作为问题的最优解或近似最优解输出，则可证明修改后的遗传算法依概率收敛到全局最优解。l改进后的简单遗传算法描述如下：19.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析20.6.2基于有限基于有限马马尔尔可夫可夫链链的收的收敛敛性分析性分析l定理7.3 改进后的简单遗传算法依概率收敛到全局最优解。21.演化演化计算算读书报告告题目目(下列下列题目目选择之一之一)1 用遗传算法或演化策略求解下列优化问题(n=2)并研究问题的维数对算法性能的影响。2 使用路径表示设计并实现一个求解具有30个城市 的旅行商问题的遗传算法,假定问题的距离矩阵由平面上随机生成的30个点之间的距离给定。并比较PMX杂交算子和OX杂交算子对算法性能的影响22.3 用用遗传算法算法求解下列求解下列约束束优化化问题：其中4 演化计算学习过程中的一些心得体会。23.