遗传算子构造理论-完全版

遗传算子及遗传操作理论 摘要 摘要 遗传算法作为一种高效的搜索与寻求最优问题的方法 对解决现实问题 有着很大的帮助 它面向结构对象进行操作 采取选取 交叉 变异等基本操 作 进行问题的解决 且选取操作下有概率方式选取 贪婪选取等方式 重组 分实值重组 离散重组等 变异有单点变异 离散变异等 除此外在特定的算 法中还有响应的遗传操作 看上去和基本算法有些不同 但其本质未发生变化 这对于解决问题有着很大的帮助 也为寻求一个问题的最优解提供他了重要的 解决方法 关键词 关键词 遗传原理 遗传算子 遗传操作 编码方式 改进算法 0 目录目录 一 绪 论 2 二 遗传算法的一些概 念 3 1 何为遗传算法 2 遗传算法的原理 3 一般遗传算法的遗传操作 三 遗传操 作 4 1 选择 复制 selection reproduction 2 交叉 重组 Crossover Recombinantion 3 变异 Mutation 四 基于改进算法的遗传算子或遗传 作 9 1 分层遗传算法 2 CHC 算法 3 并行遗传算法 1 五 结 语 16 参考文献参考文献 绪论绪论 遗传算法 Genetic Algorithm 是模拟达尔文生物进化论的自然选择和遗传 学机理的生物进化过程的计算模型 是一种通过模拟自然进化过程搜索最优解 的方法 其主要特点是直接对结构对象进行操作 不存在求导和函数连续性的 限定 具有内在的隐并行性和更好的全局寻优能力 采用概率化的寻优方法 能自动获取和指导优化的搜索空间 自适应地调整搜索方向 不需要确定的规 则 遗传算法的这些性质 已被人们广泛地应用于组合优化 机器学习 信号 处理 自适应控制和人工生命等领域 它是现代有关智能计算中的关键技术 2 一 遗传算法的一些概念一 遗传算法的一些概念 1 何为遗传算法 遗传算法简称 GA Genetic Algorithm 在本质上是一种不依赖具体问题的 直接搜索方法 其主要特点是直接对结构对象进行操作 不存在求导和函数连 续性的限定 具有内在的隐并行性和更好的全局寻优能力 采用概率化的寻优 方法 能自动获取和指导优化的搜索空间 自适应地调整搜索方向 不需要确 定的规则 其基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的 Darwin 进化论最重要的是适者生存原理 它认为每一物种在发展中越来越 适应环境 物种每个个体的基本特征由后代所继承 但后代又会产生一些异于 父代的新变化 在环境变化时 只有那些熊适应环境的个体特征方能保留下来 而 Mendel 遗传学说最重要的是基因遗传原理 它认为遗传以密码方式存在 细胞中 并以基因形式包含在染色体内 每个基因有特殊的位置并控制某种特 殊性质 所以 每个基因产生的个体对环境具有某种适应性 基因突变和基因 杂交可产生更适应于环境的后代 经过存优去劣的自然淘汰 适应性高的基因 结构得以保存下来 2 遗传算法的原理 遗传算法 GA 把问题的解表示成 染色体 在算法中也即是以二进制编码 的串 并且 在执行遗传算法之前 给出一群 染色体 也即是假设解 然后 把这些假设解置于问题的 环境 中 并按适者生存的原则 从中选择出较适 3 应环境的 染色体 进行复制 再通过交叉 变异过程产生更适应环境的新一 代 染色体 群 这样 一代一代地进化 最后就会收敛到最适应环境的一个 染色体 上 它就是问题的最优解 在这里 染色体 chromosome 就是 问题中个体的某种字符串形式的编码表示 字符串中的字符也就称为基因 gene 例如 个体 染色体 9 1001 2 5 6 010 101 110 3 一般遗传算法的遗传操作 一般遗传算法的遗传操作 遗传操作亦称遗传算子 genetic operator 就是关于染色体的运算 遗传算 法中有三种遗传操作 选择 复制 selection reproduction 交叉 重组 crossover recombinantion 亦称交换 交配或杂交 变异 mutation 亦称突变 二 遗传操作二 遗传操作 1 选择 复制 selection reproduction 选择操作也叫复制操作 是建立在对个体的适应度进行评价的基础之上的 目的是为了避免基因缺失 提高全局收敛性和计算效率 意思是从群体中按个 体的适应度函数值选择出较适应环境的个体 一般地说 选择将使适应度高的 个体繁殖下一代的数目较多 而适应度较小的个体 繁殖下一代的数目较少 甚 至被淘汰 最通常的实现方法是轮盘赌 roulette wheel 模型 既比例选择算 子个体的适应度越高 被选中的概率越大 令 f xi 表示群体的适应度值之总 和 f xi 表示种群中第 i 个染色体的适应度值 它被选择的概率正好为其适应 度值所占份额值为 如下图表中的数据适应值总和 fi 6650 适应度为 2200 变选择的可能为 f xi N j j i i xf xf xP 1 4 f xi 2200 6650 0 394 图图 1 1 轮盘赌模型轮盘赌模型 Fitness 值 2200 18001200 950400100 选择概率 3331 0 271 0 18 0 143 0 06 0 015 除此之外还有其他的选择方法 例如贪婪选择法 级差选择法 竞争选择 法 排序选择法 随机联赛选择法等等 必须指出的是在基于适应度比例的选择下 高适应度的个体很容易大量繁 殖 这使得参加交叉运算的两个个体相同的可能性很大 从而很难生成新的个 体 而变异算子生成的个体即使适应度高 但由于数量小 所以被淘汰的概率 仍然很大 从而导致过早收敛至局部最优解 同时 如果群体中的个体适应度 相差不大 则它们后代的个体数量也会基本相同 好的个体得不到更多繁殖的 机会 从而延缓了算法的速度 总之 复制算子具有 优胜 的性质 那么就 要找到一种较好的方法来保存适应度较好的个体 下面来介绍一种方式 最优保存策略 最优保存策略进化模型可进行优胜劣汰操作 既当前群体中适应度最高的 个体不参与交叉运算和变异运算 而是用它来替换掉本带群体中经过交叉 变 5 异等操作后产生的适应度较低的个体 其操作过程如下 1 找出当前群体中适应度最小的个体和适应度最高的个体 2 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还 要高 则以当前群体中的最佳个体作为新的迄今为止的最好个体 3 用迄今位置最好个体替换掉当前群体中的最差个体 最优保存策略可视为选择操作的一部分 它是算法收敛性的一个重要保证 条件 对产生较优的搜索结果起着至关作用 2 2 交叉 交叉 重组重组 Crossover Crossover R Recombinantion 重组是结合来自父代基因信息而生成的 而交叉是将被选中的两个个体的 基因链按一定概率 pc 进行交叉 从而生成两个新的个体 交叉位置 pc Pc 是 一个系统参数 是随机的 根据问题的不同 实值重组分为离散重组 discrete recombinantion 中间重组 intermediate recombinantion 等 交叉可分为单点交叉算子 Single Point Crossover 双点交叉算子 Two Point Crossover 均匀交叉算子 Uniform Crossover 洗牌交叉 Shuffle Crossover 等在此我们只讨论中间重组和单点交叉的情况 中间重组只适合于实变量 而非二进制变量 见下图 2 示 父个体 1 12 25 5 父个体 2 123 4 34 的样本为 样本 1 0 5 1 1 0 1 样本 2 0 1 0 8 0 5 6 计算出的新个体为 子个体 1 67 5 1 9 2 1 子个体 2 23 1 8 2 19 5 下图 3 为中间重组后子个体的可能位置 变量 1 可能的子个体 父个体 变量 2 单点交叉操作的简单方式是将被选择出的两个个体 S1 和 S2 作为父母个体 将 两者的部分基因码值进行交换 假设如下两个 8 位的个体 S1 1000 1111 S2 1110 1100 产生一个在 1 到 7 之间的随机数 c 假如现在产生的是 2 将 S1 和 S2 的 低二位交换 S1 的高六位与 S2 的低六位组成数串 10001100 这就是 S1 和 S2 的一个后代 P1 个体 S2 的高六位与 S1 的低二位组成数串 11101111 这就是 S1 和 S2 的一个后代 P2 个体 其交换过程如下图所示 CrossoverCrossover1111000011110000CrossoverCrossover1111000011110000 S11000 1111S21110 1100 P11000 1100P21110 1111 3 3 变异 变异 Mutation Mutation 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动 依据个体编码表示方法的不同 可以有以下的算法 a 实值变异 b 二进制变异 一般来说 变异算子操作的基本步骤如下 a 对群中所有个体以事先设定的编译概率判断是否进行变异 b 对进行变异的个体随机选择变异位进行变异 对于二进制的变异其实就是在选中的个体中 将新个体的基因链的各位按概 7 率 pm 进行异向转化 最简单方式是改变串上某个位置数值 将 0 与 1 互换 0 变异为 1 1 变异为 0 如下 8 位二进制编码 1 1 1 0 1 1 0 0 随机产生一个 1 至 8 之间的数 i 假如现在 k 6 对从右往左的第 6 位进行变异 操作 将原来的 1 变为 0 得到如下串 1 1 0 0 1 1 0 0 整个交叉变异过程如下图 除了上述基本变异方法外 还有其他的变异方法 如换位 复制 插入 删除等等 三 基于改进算法的遗传算子或遗传操作三 基于改进算法的遗传算子或遗传操作 自从 1975 年 J H Holland 系统的提出遗传算法的完整结构和理论以来 各 学者致力于遗传算法的性能改进 对编码方式 控制参数的确定 选择方式和 交叉机理的进行了深入的研究 提出了不同操作的遗传算法 其基本途径概括 而来有以下几个方面 改变遗传算法的组成部分或使用技术 如选用优化控制参数 适合问题特 性的编码技术等 采用混合遗传算法 8 采用动态适应技术 在进化过程中调整算法控制参数和编码粒度 采用非标准的遗传操作算子 采用并行遗传算法 基于以上几种思想所产生的算法有分层遗传算法 CHC 算法 messy GA 算法 自适应遗传算法 混合遗传算法 并行遗传算法等等 在这里我们只简 单地介绍几种算法 1 分层遗传算法 对于一个问题 分层算法也像普通算法一样 首先随机生成 N n 个样本 只是将样本分成 N 个种群各自进行自己的遗传操作 进行到一定的代数后再将 N 个遗传结果记录到二维数组 R 1 N 1 n 中 则 R i j i 1 N j 1 n 表示 GAi的结果种群的第 j 个个体 同时 用 A 1 N 记录 N 个结果种群的平均适应度 A i 表示第 i 个种群的平均适应度 高层遗 传算法也可分为选择 交叉 变异操作 选择 基于数组 A 1 N 即 N 个遗传算法的平均适应度值 对数组 R 代表的结果种群进行选择操作 一些结果种群会因为适应度值高而被复制至少 一次 另一些则会因为适应度值低而被淘汰 交叉 如果数组 A 1 N 和 R j 1 n 被随机的匹配到一起 而且从位 置 x 进行交叉 1 i j N 1 x n 1 则 R i x 1 n 和 R j x 1 n 相互交换 相应的部分 即交换 GAi和 GAj中结果种群的 n x 个个体 变异 以很小的概率将少量的随机生成的新个体替换 R 1 N 1 n 中 随机抽取的个体 至此 高层遗传算法的第一轮运行结束 从而 N 个遗传算法 GAi可以从相 应于新的 R 1 N 1 n 中继续各自的操作 并在此基础上再运行一次后更 新数组 R 1 N 1 n 和 A 1 N 进入第二轮高层操作 如此反复的进 行 直至得到满意的结果 流程图如下 9 2 CHC 算法 CHC 算法是 同样进行选择 交叉 变异操作 只是和普通算法进行机 制略有不同 选择 将上世代的种群与通过交叉发放产生的个体种群混合 从中按一定 的概率选择较优的个体 这一策略称为跨世代精英选择 交叉 CHC 使用的重组操作是对均匀交叉的一种改进 改进之处为当两个 父个体位值相异的位数为 m 时 从中选取 m 2 个位置 实行父个体位值的互换 显然这样的从中模式具有很强的破坏性 因此 要限定个体间的海明距离在一 确定阀值内才能交叉 并该值随种群收敛而减小 变异 CHC 算法在进化前期不采取变异操作 当中群进化到一定收敛时期 从优秀个体中选择一部分个体进行初始化 其方法为选择一定比例的基因座 随机决定它们的位值 这个比例值称为扩散率 一般取 0 35 3 并行遗传算法 一般来说 遗传算法中适应度的计算最为费时间 再加之随进化规模会扩 大 所以提高运算速率很重要 由于遗传算法的并行机制 其并行处理理所当 然 并行遗传算法的实现方案可分为 全局型 主从模式 master slave model 独立型 粗粒度模型 coarse grained model 分散型 细粒 度模式 fine grained model 在这种算法中 引入了一个新的遗传算子 迁移 它是指在进化过程中 10 子群体间交换个体的过程一般迁移方法是将子群体中最好的个体发给其它的子 群体 通过迁移可以加快较好个体在种群间的传播 提高收敛速度和解的精度 其特点为 更适合全局搜索 计算量较小 以基于粗粒度模型的并行算法为例 其迁移策略可分为以下两种 一传多一传多 每个处理器对应有若干个相邻处理器 每个处理器产生新一代 个体后 都将自己最好的一个个体传送给其所有相邻的处理器 并且接受来自 相邻处理器的最好个体 将这些个体与自己的个体同时考虑 淘汰适应度差的 个体 其程序流程图如下所示 一传多流程图 终止条件满 足否 结束 Y N 计算适应度 选择 进行交叉 变异 将最好的个体传送给相邻的处理器 接受来自相邻处理器的最好个体 淘汰适应度差的个体 Generation Generation 1 初始化种群 Generation 0 开始 11 一传一一传一 考虑到染色体的多样性 每个处理器都将自己最好的个体仅传给 与之相邻的一个处理器同时增加两个参数 一是 send rate 决定处理器之间通讯 的频率 如 send rate 3 时表示当遗传代数是 3 的倍数时 各处理器之间相互传 送个体 二是 send best 决定每次传送最好个体的数目 如 send best 5 时表示 每个处理器把最好的前五个个体传送给各自相邻的处理器 其流程图如下所示 选择 进行交叉 变异 计算适应度 Generation Se nd rate 0 终止条件满足 否 结束 Generation 0 初始化种群 开始 Y N N Y 12 一般的 个体迁移的方法可以有 均匀随机挑选个体作为迁移对象 按适应度挑选个体作为迁移对象 对于种群间的个体迁移结构也有多种可能性 例如 迁移发生在所有的 种群 即发生在完全的网络拓扑 迁移发生在环状拓扑 迁移发生在临集 拓扑 而最一般化的是完全网络拓扑 并行算法提高了效率 究其效果如何 人们在评价其性能过程中提出了 许多不同的评价方法 其中最重要的一个评价标准是加速比 设 T 为某算法在 串行时对的运行时间 Tp 是该算法在 p 个处理机构成的并行机上所用时间 则 加速比 Sp 为 Sp T Tp 但对于并行遗传算法 由于搜索的随机性 仅加速比 不足以衡量其优劣程度 比较现实的方法是 设计一些好的几何特性的测试函 数和时间计算函数 来测试达到最优化的平均时间和平均进化代数 以衡量其 优劣性能 并行算法的性能主要体现在收敛速度和精度两个方