第七章-遗传算法的理论基础PPT课件

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