七遗传算法的理论基础.pptVIP

第七章遗传算法的理论基础 武汉大学计算机学院 7.1 模式定理 模式定理是由Holland所提出的，其目的是从理论上解释遗传算法的有效性。 Holland的模式定理是针对简单遗传算法(SGA)而言的，即假定在遗传算法中，种群的规模不变，使用二进制编码、基于适应值比例的选择策略、单点杂交算子和通常的变异算子。 7.1 模式定理 字符集{0,1,*}上的一个字符串称为一个模式 在一个模式中，*表示一个不确定的字符，即表示0或1，所以一个模式可以表示一个二进制位串的集合。 例 模式*0101表示集合{00101,10101}，而模式0**1*表示集合{00010，00011，00110，00111，01010，01011，01110，01111}。 在一个模式中，字符0或1所出现的位置称为确定位置，字符*所出现的位置称为不确定位置。 7.1 模式定理 模式H中确定位置的个数称为模式H的阶, 记为 例 模式H中第一个确定位置与最后一个确定位置之间的距离称为模式H的定义长度，记为 例 设s是一个长度为的二进制位串，H是一个长度为的模式，若 则称s与模式H匹配。 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代的适应值，记为 即有 7.1 模式定理 例 假定当前种群中的个体及适应值如表1所示，则模式H及其适应值如表2所示。 7.1 模式定理 定理7.1(模式定理) 设 表示SGA在第t代时的种群，SGA的杂交概率和变异概率分别为 和 H为任一模式， 表示第t代种群中与H匹配个体的个数，则有估计式 其中 为P(t)中个体的平均适应值， 为个体的编码长度。 6.1 模式定理 证 首先考虑选择对模式H的影响。 由于SGA采用基于适应值比例的选择策略，所以在第t代种群P(t)中，与H匹配的个体被选择作为父体的个数的期望值为 6.1 模式定理 再考虑杂交算子对模式的影响。 杂交算子随机地选取1到 中的一个位置，并交换两个父体中所选取位置右边的子串。显然，若选取的杂交位置不在模式H的第一个确定位置和最后一个确定位置之间，那么原来属于H中的个体经杂交后仍然属于H。 若所选取的杂交位置在模式H的第一个确定位置和最后一个确定位置之间，那么原来属于H中的个体经杂交后有可能不再属于H。 例如 那么有 若111000与101011进行杂交，且随机选择的杂交位置为3，杂交后所得到的两个后代分别为111011和101000，这两个后代均不属于H。 6.1 模式定理 原来属于H中的个体经杂交后也有可能仍然属于H。例如 若在上面的例子中111000与001100进行杂交，杂交位置仍为3，那么杂交后所得到的两个子串为111100和001000，其中后代111100仍然属于H。 属于模式H的个体经杂交后不属于模式H的概率至多为 6.1 模式定理 属于模式H的个体经杂交后仍属于模式H的概率至少为 由于选择和杂交是相互独立的，所以经过选择和杂交后种群中近似地有 个与H匹配的个体 6.1 模式定理 最后讨论变异算子对模式H的影响。 对于一个属于模式H的个体v，变异算子以概率对v的每一位相互独立地进行变异，当且仅当变异算子在H的 个确定位置上不对v进行变异时，经变异算子后所得到的个体仍然属于H。由于对某一位不进行变异的概率为 ，于是属于模式H中个体v经变异后仍然属于模式H的概率为 6.1 模式定理 经选择、杂交、变异操作后，第t+1代中包含模式H的个体数目 有以下估计式： 6.1 模式定理 推论 在SGA中，定义长度较短、低阶且适应值大于种群平均适应值的模式H，在种群中的数目呈指数增长 证 设对任意 都有 其中 为一个常数。并设 6.1 模式定理 当时，由定理知 于是推论成立。 6.2基于有限马尔可夫链的收敛性分析 定义 设 是遗传算法当代数