第六章 基于有限马尔可夫链的收敛性分析

第六章遗传算法的理论基础 武汉大学计算机学院 6 1模式定理 模式定理是由Holland所提出的 其目的是从理论上解释遗传算法的有效性 Holland的模式定理是针对简单遗传算法 SGA 而言的 即假定在遗传算法中 种群的规模不变 使用二进制编码 基于适应值比例的选择策略 单点杂交算子和通常的变异算子 定义6 1字符集 0 1 上的一个字符串称为一个模式 6 1模式定理 在一个模式中 表示一个不确定的字符 即表示0或1 所以一个模式可以表示一个二进制位串的集合 例6 1模式 0101表示集合 00101 10101 而模式0 1 表示集合 00010 00011 00110 00111 01010 01011 01110 01111 在一个模式中 字符0或1所出现的位置称为确定位置 字符 所出现的位置称为不确定位置 6 1模式定理 定义6 2模式H中确定位置的个数称为模式H的阶 记为 例6 2定义6 3模式H中第一个确定位置与最后一个确定位置之间的距离称为模式H的定义长度 记为例6 3 6 1模式定理 定义6 4设s是一个长度为的二进制位串 H是一个长度为的模式 若则称s与模式H匹配 例6 4二进制位串00与下列模式匹配 00 0 0 二进制位串110与下列模式匹配 110 10 1 0 11 0 1 1 显然一个长度为的二进制位串与个不同的模式匹配 6 1模式定理 定义6 5假设表示SGA在第t代时的种群 f为SGA所使用的适应函数 H为任一模式 则称P t 中与模式H匹配的个体的平均适应值为模式H在第t代的适应值 记为即有 6 1模式定理 例6 5假定当前种群中的个体及适应值如表6 1所示 则模式H及其适应值如表6 2所示 6 1模式定理 定理6 1 模式定理 设表示SGA在第t代时的种群 SGA的杂交概率和变异概率分别为和 H为任一模式 表示第t代种群中与H匹配个体的个数 则有估计式其中为P t 中个体的平均适应值 为个体的编码长度 6 1模式定理 证首先考虑选择对模式H的影响 由于SGA采用基于适应值比例的选择策略 所以在第t代种群中 与H匹配的个体被选择作为父体的个数的期望值为 6 1模式定理 再考虑杂交算子对模式的影响 杂交算子随机地选取1到中的一个位置 并交换两个父体中所选取位置右边的子串 显然 若选取的杂交位置不在模式H的第一个确定位置和最后一个确定位置之间 那么原来属于H中的个体经杂交后仍然属于H 若所选取的杂交位置在模式H的第一个确定位置和最后一个确定位置之间 那么原来属于H中的个体经杂交后有可能不再属于H 6 1模式定理 值得注意的是原来属于H中的个体经杂交后也有可能仍然属于H 例如若在上面的例子中111000与001100进行杂交 杂交位置仍为3 那么杂交后所得到的两个子串为111100和001000 其中后代111100仍然属于H 6 1模式定理 由上所述 属于模式H的个体经杂交后不属于模式H的概率至多为因而 属于模式H的个体经杂交后仍属于模式H的概率至少为 6 1模式定理 由于选择和杂交是相互独立的 所以经过选择和杂交后种群中近似地有个与H匹配的个体 6 1模式定理 最后讨论变异算子对模式H的影响 对于一个属于模式H的个体v 变异算子以概率对v的每一位相互独立地进行变异 当且仅当变异算子在H的个确定位置上不对v进行变异时 经变异算子后所得到的个体仍然属于H 因为对v的某一位进行变异的概率为所以对某一位不进行变异的概率为于是属于模式H中个体v经变异后仍然属于模式H的概率为 因此 经选择 杂交 变异操作后 第t 1代中包含模式H的个体数目有以下估计式 6 1模式定理 推论6 1在SGA中 定义长度较短 低阶且适应值大于种群平均适应值的模式H 在种群中的数目呈指数增长 证设对任意都有其中C为一个常数 并设 6 1模式定理 当时 由定理2 1知于是推论成立 6 1模式定理 例如 那么有若111000与101011进行杂交 且随机选择的杂交位置为3 杂交后所得到的两个后代分别为111011和101000 这两个后代均不属于H 6 2基于有限马尔可夫链的收敛性分析 定义6 6设是一随机变量序列 随机变量在有限状态空间上取值 若对任意及都有则称为有限马尔可夫链 条件概率称为该马尔可夫链在时刻t处于状态的条件下 在时刻t 1转移到状态的转移概率 记为 6 2基于有限马尔可夫链的收敛性分析 若转移概率与时间t无关 即对任和任两时刻都有则称该马尔可夫链是齐次的 此时称为该齐次马尔可夫链的转移矩阵 若是一有限齐次马尔可夫链的转移矩阵 那么有且有 6 2基于有限马尔可夫链的收敛性分析 设是一有限齐次马尔可夫链 对任一时刻该马尔可夫链在时刻t的一维分布定义为一维分布可以表示为向量形式 6 2基于有限马尔可夫链的收敛性分析 6 2基于有限马尔可夫链的收敛性分析 由上式知 有限齐次马尔可夫链在任一时刻t的分布由初始分布和转移矩阵所确定 定义6 7设是一个n阶矩阵 1 若则称A是非负的 记为 2 若则称A是正的 记为 6 2基于有限马尔可夫链的收敛性分析 定义6 8设是n阶非负矩阵 1 若存在正整数k 使得是正的 则称A是本原的 2 若存在方阵C T 使得通过相同的行和列的置换可将矩阵A变换成形式则称A是可约的 否则称A为不可约的 3 若则称A是随机的 6 2基于有限马尔可夫链的收敛性分析 显然 每个正矩阵都是本原的引理6 1若A B是n阶随机矩阵 则AB也是n阶随机矩阵 证矩阵AB第i行元素之和为 6 2基于有限马尔可夫链的收敛性分析 推论6 2若是n阶随机矩阵 则也是n阶随机矩阵定义6 9设A是一个n阶随机矩阵 1 若A具有相同的行 则称A是稳定的 2 若A的每一列至少有一个正元素 则称A是列可允许的引理6 2设C M S是n阶随机矩阵 且M是正的 S是列可允许的 则乘积矩阵CMS是正的 6 2基于有限马尔可夫链的收敛性分析 引理6 3设P是一个n阶本原随机矩阵 则当时 收敛到一个正的稳定随机矩阵其中是满足下列方程的唯一解 其中 6 2基于有限马尔可夫链的收敛性分析 推论6 3设P是一个n阶本原随机矩阵 若那么有 6 2基于有限马尔可夫链的收敛性分析 引理6 4设是一个可约的随机矩阵 其中C是一个m阶本原随机矩阵 且则是一个稳定的随机矩阵 且有其中 6 2基于有限马尔可夫链的收敛性分析 下面讨论简单遗传算法的马尔可夫链表示 由于SGA所处的状态只与种群中的个体有关 故可将SGA的一个种群看作是一个状态 若种群中每个个体是一个长度为的二进制位串 而种群的规模为N 当约定二进制位串之间的一个次序后 譬如说字典序 则每一个状态可用一个长度为的二进制位串来表示 所以简单遗传算法的状态空间为 6 2基于有限马尔可夫链的收敛性分析 例如若 当前种群为 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 则表示当前种群的状态为 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 由于SGA的状态是有限的 且SGA中的杂交 变异和选择算子与演化代数无关 从而第t 1代种群所处的状态只与第t代种群所处的状态有关 而与第t代种群之前种群所处的状态无关 故若用表示SGA第t代种群所处的状态 则可以看作是一个有限齐次马尔可夫链 6 2基于有限马尔可夫链的收敛性分析 下面讨论该有限齐次马尔可夫链的转移矩阵 SGA由选择 杂交和变异三种算子构成 由于SGA应用这些算子是循环往返的 为了证明简单起见 假定遗传算法中的选择 杂交和变异算子的应用次序为 杂交 变异 选择 即使用下列遗传算法的基本结构 6 2基于有限马尔可夫链的收敛性分析 6 2基于有限马尔可夫链的收敛性分析 SGA的一个状态通过杂交 变异和选择算子的作用转移到下一个状态 故转移矩阵P可以表示为三个随机矩阵C M S的乘积 其中C M S分别表示由杂交 变异和选择算子所引起的随机矩阵 1 杂交矩阵设为由杂交算子引起的矩阵 其中表示状态i经杂交算子的作用后变为j状态的概率 因为一个状态经杂交算子的作用后 总要变为另一个状态 所以有即是一个随机矩阵 6 2基于有限马尔可夫链的收敛性分析 2 变异矩阵设为由变异算子引起的矩阵 其中表示状态i经变异算子的作用后变为j状态的概率 因为变异算子是独立地作用在种群中个体的每一个基因位上的 若变异概率满足那么有其中表示状态i与状态j的Hamming距离 6 2基于有限马尔可夫链的收敛性分析 即是一个正的随机矩阵 6 2基于有限马尔可夫链的收敛性分析 3 选择矩阵设为由选择算子引起的矩阵 其中表示状态i经选择算子的作用后变为状态j的概率 因为一个状态经选择算子的作用后 总要变为另一个状态 所以有即是一个随机矩阵 6 2基于有限马尔可夫链的收敛性分析 设状态i所表示的种群为为适应函数 若用轮盘赌选择策略 则个体被选择的概率是于是状态i经选择后仍为状态i的概率为由此知是列可允许的 6 2基于有限马尔可夫链的收敛性分析 由上述关于矩阵C M和S的讨论和引理6 2便得下面的引理6 5 引理6 5设SGA的杂交概率变异概率并采用轮盘赌选择策略 则SGA的转移矩阵为正的随机矩阵 定义6 10设是遗传算法当代数为t时的种群 为适应函数 表示种群的最优适应值 表示全局最优适应值 若则称遗传算法依概率收敛于全局最优解 6 2基于有限马尔可夫链的收敛性分析 定理6 2若杂交概率和变异概率满足适应函数不恒等于一个常数 则SGA不能依概率收敛于全局最优解 证设状态i所表示的种群满足其中是全局最优适应值 设表示第t代种群的最优适应值 是遗传算法在第代时处于状态i的概率 显然 6 2基于有限马尔可夫链的收敛性分析 所以有由引理6 5知转移矩阵是正的随机矩阵 因而是本原随机矩阵 再由推论6 3知于是有 6 2基于有限马尔可夫链的收敛性分析 定理6 2说明了简单遗传算法不能依概率收敛到全局最优解 但只要对简单遗传算法作一点改动 每次将当前找到的最好解保留下来 在算法结束后 将所保留的最好解作为问题的最优解或近似最优解输出 则可证明修改后的遗传算法依概率收敛到全局最优解 改进后的简单遗传算法描述如下 6 2基于有限马尔可夫链的收敛性分析 6 2基于有限马尔可夫链的收敛性分析 改进后的简单遗传算法保留了到当前代为止所得到的最好解 为确定起见 将当前最好的解存放在种群状态的开始 保留的最好解只起记录作用 不参加遗传运算 这样改进后的简单遗传算法第t代所处的状态可以用一个长度为的二进制位串来表示 其中表示遗传算法到第t代为止所得到的最好解 而分别表示第代种群中的个个体 所以修改后的简单遗传算法的状态空间为 6 2基于有限马尔可夫链的收敛性分析 例如若 当前种群为 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 若直到当前种群之前的最好个体为 1 0 1 0 则表示当前种群的状态为 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 利用上述修改后遗传算法的状态表示 将的状态按其最好解的适应值从大到小排序 若最好解的适应值相同 则按原状态空间的顺序排序 若改进后的遗传算法的杂交矩阵 变异矩阵和选择矩阵分别用阶矩阵表示 则 6 2基于有限马尔可夫链的收敛性分析 其中分别为简单遗传算法的阶杂交矩阵 变异矩阵和选择矩阵 在进行选择后 要将当前种群的最好解与保留的最好解进行比较 以获得到目前为止的最好解 这一操作可以用一转移矩阵来表示 6 2基于有限马尔可夫链的收敛性分析 对任一状态设状态i所表示的种群为并设即为适应值最大的个体 则当时 这里状态j表示的种群为 否则 于是矩阵的每一行有且仅有一个元素为1 其它元素为0 6 2基于有限马尔可夫链的收敛性分析 由状态空间中状态的排列顺序知 对任当时 所以矩阵U是一个下三角矩阵 即其中均为阶矩阵 而且为单位矩阵 6 2基于有限马尔可夫链的收敛性分析 定理6 3改进后的简单遗传算法依概率收敛到全局最优解 证由上面的讨论知 改进后的简单遗传算法的转移矩阵为 其中是正的随机矩阵 而 6 2基于有限马尔可夫链的收敛性分析 由引理6 4知于是若为任一初始分布 则存在极限分布 6