遗传算法理论研究综述.pdf

遗 传 算 法 理 论 研 究 综 述* 戴晓晖 李敏强 寇纪淞 ( 天津大学系统工程研究所 300072) 摘 要 针对遗传算法在理论研究方面存在的不足, 系统地讨论了遗传算法理论研究的主要内容和方 法, 包括模式定理、 编码策略、 Markov 链与全局收敛性、 维数分析、 BGA 理论、 可分离函数、 Walsh 与傅 立叶函数分析及二次动力系统等, 介绍了No Free Lunch定理, 并指出相关的研究方向 关键词 遗传算法, 收敛性, 计算复杂性, 模式 分类号 TP 301. 6 Survey on the Theory of Genetic Algorithms Dai Xiaohui, Li Minqiang, K ou Jisong (Tianjin University) Abstract Aimming at the drawbacks of theory of genetic algorithms,the main content and methods used in the theory of genetic algorithms such as schema theorem, coding strategies, M arkov chains and convergence, dimensional analysis are discussed systemically. No Free Lunch theorem is introduced, and the research direction is pointed out. Key words genetic algorithms,convergence,computational complexity,schema 1 引 言 遗传算法( GA) 是模拟遗传选择和自然淘汰的 生物进化过程的计算模型, 是由 Michigan 大学 Holland 教授于 1975 年首次提出的 [ 1]。

这是一种新 的全局优化搜索算法, 因其简单通用, 鲁棒性强, 适 于并行处理, 已广泛应用于计算机科学、 优化调度、 运输问题、 组合优化等领域 尽管遗传算法在实际应用中取得了巨大成功, 但相对于鲜明的生物基础, 其数学基础则不够完 善[ 2, 3], 主要表现为: 1) 缺乏广泛而完整的遗传算法 收敛性理论; 2) Holland 模式定理尚不能清楚地解 释遗传算法的早熟现象和欺骗问题; 3) 遗传算法的 搜索效率及其时间复杂性问题 [ 4- 6]这些不足严重 地阻碍了遗传算法的推广与应用 针对上述不足, 本文系统地讨论了遗传算法理 论研究的主要内容和方法, 介绍了 No Free Lunch 定理, 并指出了相关的研究方向 * 国家自然科学基金项目( 69974026) 1999- 05- 24 收稿 2 GA 理论与方法 2. 1 模式定理 Holland 首先用模式定理“ 解释” 了遗传算法的 搜索行为, 该研究成果奠定了遗传算法的数学理论 基础[ 1, 7] 根据隐并行性得出每一代处理有效模式的 下限值是 o( N 3) , 其中 N 为群体大小, 这是遗传算 法能够有效搜索的根本原因之所在。

Bertoni 和 Dorigo [ 8]推广了此项研究, 并获得了 N= 2?l, 给出 ? 为任意值时处理多少有效模式的表达式每代遗传 会产生多少新模式是衡量遗传算法效率的一个重要 因 素 恽为民和席裕庚[ 9]给出了每代至少产生 o( 2 N- 1) 数量级的新模式 最近, 一些学者对模式定理的正确性提出了质 疑马丰宁 [ 10] 通过测试黎曼函数和相应的理论分 析, 指出模式定理推导中的错误, 并提出了新模式定 理; 张铃等 [ 11] 也得出类似的结论, 并对模式定理进 行了修正; Grefenstette [ 12] 指出模式定理不能保证适 应度变换的唯一性; Muhlenbein [ 13] 指出了模式定理 中计算模式适应度中存在的问题; Radcliffe[ 14, 15]通 过对模式定理的分析, 指出遗传算法并不总比随机 第 15 卷 第 3 期 Vol. 15 No. 3 控 制 与 决 策 CONT ROL A ND DECISION 2000 年 5 月 M ay 2000 搜索算法好; Vose 等[ 16]也论述了模式定理中存在 的一些问题 尽管大量成功的实际应用支持了模式定理所依 赖的积木块假设, 但至今还没有一种方法用来判别 “ 对 于 一 个 给 定 的 问 题, 积 木 块 假 设 是 否 成 立[ 17, 18]” 。

2. 2 编码策略 Holland 模式定理建议采用二进制编码, 并给 出了最小字符集编码规则为了克服早熟现象, Schraudolph 等[ 19]提出了动态变量编码, 通过对 De- Jong 的 5 个函数进行测试, 发现动态变量编码比普 通二进制编码的优化效果好得多双倍体是高等生 物染色体的重要特性, 有长期记忆等作用, 早期的研 究者[ 29]多考虑双倍体表示 Goldberg 和Smith[ 21]用 动态背包问题进行比较研究, 实验表明双倍体比单 倍体的跟踪能力强 浮点数编码具有精度高、 便于大 空 间 搜 索 的 优 点, 因 此 越 来 越 受 到 重 视 Michalewicz 等 [ 22, 23] 比较了两种编码的优缺点; Qi 和 Palmieri [ 24] 基于 Markov 链, 对浮点数编码的遗 传算法进行了严密的数学分析张晓缋等[ 25]研究了 二进制和十进制编码在搜索能力和保持群体稳定性 上的差异, 结果表明二进制编码比十进制编码的搜 索能力强, 但前者不能保持群体稳定性Vose 等[ 26] 扩展了 Holland 的模式概念, 揭示了不同编码之间 的同构性。

由于编码是遗传算法应用中的首要问题, 因此建立完善的理论指导是非常必要的 目前, 关于采用何种编码策略仍然存在许多争 议 一派根据模式定理, 建议尽量用少的符号进行编 码; 另一派以数值优化计算的方便和精度为准, 采用 一个基因一个参数的方法, 并把相应的基因操作改 造成适合实数操作的形式Bosworth 等[ 27]是后一 派的开创者近年来, 许多学者 [ 28, 29]发现在有些问 题上, 采用大符号集编码的遗传算法比采用二进制 编码的遗传算法的性能要好, 最小字符集编码规则 受到了怀疑Antonisse[ 30, 31]从理论上证明了 Hol- land 在推导最小字符集编码规则时存在的错误, 指 出大符号集编码的设计可提供更多的模式, 与最小 字符集编码规则得出的结论截然不同 2. 3 Markov 链与收敛性 生物进化的“ 趋势向上” 性似乎蕴含着遗传算法 的最终收敛性, 但还须从理论上对这一事实给予证 明遗传算法是全局收敛的这一结论主要是根据 Holland 的模式定理得出的, 事实上这一结论普遍 受到怀疑并引起争论 近几年, 遗传算法全局收敛性分析取得了突破 性进展 Goldberg 和 Segrest [ 32]首先使用Markov 链 分析了一个极为简单的遗传算法的性能; Eiben 等 [ 33] 用Markov 链证明了一类基于保留最优个体的 抽象 GA 的全局收敛性; Fogel [ 34] 分析了没有变异 算子的 GA 的渐近收敛性; Suzuki[ 35]用 Markov 链 状态转移矩阵的特征根分析了 GA 的收敛行为; Qi 和 Palmieri [ 24]基于 Markov 链对浮点数编码的遗传 算法进行了严密的数学分析, 但其分析基于群体无 穷大这一假设; Rduolph [ 36] 用齐次 Markov 链证明 了标准遗传算法收敛不到全局最优解, 若采用保留 最优个体的选择机制, 则改进的 GA 全局收敛; 王丽 薇等[ 37]用类分析方法分析了 GA 的收敛性; 李书全 等[ 38]用随机泛函分析证明了保留最优个体 GA 的 全局收敛性; 田军 [ 39] 用 Markov 链和随机摄动理论 证明了 GA 进入最小能量集的条件; 梁艳春等[ 40]用 Markov 链研究了基于扩展串的等价遗传算法的收 敛性; 张讲社等 [ 41] 提出了一类非齐次、 保证收敛且 容易判断是否收敛的新型 GA, 证明了算法收敛的 充要条件。

该算法收敛速度快, 有极强的避免早熟的 全局优化能力, 具有合理的停机标准 以上这些研究成果, 要么基于群体无穷大这一 假设( 破坏了 GA 实现的可能性) , 要么基于分析简 单化的或特殊的 GA, 要么实际应用中的可操作性 太差, 但文献[ 41] 的研究成果是值得借鉴的 尽管如 此, 一般遗传算法的收敛性分析以及如何构造一个 收敛的遗传算法, 仍是这一领域亟待解决的重要理 论问题 上述的收敛性分析都是建立在计算时间趋于无 穷这一条件上 事实上, 遗传算法的计算复杂性问题 是实际应用中更为关心的问题Baeck [ 42], Muhlen- bein [ 43] 和 Asoh [ 44] 等对简化的遗传算法进行了计算 复杂性研究; 恽为民等 [ 45] 基于 Markov 链对此做了 粗略的 分析; Niwa 等[ 46]基于 群体 遗传 学中 的 Wright- Fisher 模型, 使用扩散方程对此进行了分 析 最近, Aytug 和 Koehler 等 [ 47, 48] 基于有限群体下 的 Markov 模型, 通过引入置信水平, 得出了遗传算 法达到置信水平时算法迭代次数的上下限。

尽管研 究成果在实际应用中存在概率转移矩阵过大, 以致 难以计算等缺点, 但他们的分析思路是值得借鉴的 2. 4 维数分析 因为使用 Markov 链无法判断遗传算法中控制 参数的重要性, 所以一些学者 [ 49, 50] 利用了维数分析 方法 维数分析来源于工程科学, 它试图辨识一个复 264控 制 与 决 策2 0 0 0 年 杂系统中的重要因素( 维数) , 并在它们之间建立函 数关系当使用维数分析来分析遗传算法时, 选择、 交叉和选择算子等因素被放到各自的函数关系中 可以说, 这些函数关系是一种“ 猜测” 的结果, 并且必 须通过模拟来判断这些函数关系的有效性这种分 析思路有助于遗传算法的研究 2. 5 BGA 理论 Muhlenbein 和 Schlierkamp[ 51, 52]根据数量遗传 学, 构造出一种特殊的遗传算法——复制遗传算法 ( BGA) , 并受到广泛的关注因为它提供了一套完 整的理论框架, 证明了 BGA 在求解多峰函数时的 计算复杂性为 o( NlnN) , 分析过程是基于球形对称 和群体无穷大这两个假设 事实上, 当变异概率较小 时, BGA 理论所依赖的旋转不变性并不成立, 从而 使得球形对称假设也不成立。

这时所有变量相互依 赖, 算法仅沿着坐标轴方向搜索, 从而导致算法的计 算复杂性变为 o( N N ) , 比随机搜索算法的计算复杂 性 o( e N ) 高得多 [ 18] 2. 6 可分离函数 文献[ 7, 53] 分析了当变异概率 Pm= 1/ N 时, 遗传算法求解所有可分离函数的计算复杂性为 o( NlnN) 所谓函数可分离, 即函数满足 f ( x) = ∑ i fi( xi)( 1) 根据这一定义, 目前的测试函数大都是可分离函数 试验表明, 如果变量 xi相互独立, 遗传算法将有较 好的性能 文献[ 54] 将这种方法推广到二进制编码 的遗传算法中, 分析表明, 在连续函数的优化过程 中, 采用浮点数编码比二进制编码的遗传算法性能 更好, 因为二进制编码增加了算法的复杂性 2. 7 Walsh 函数分析 傅立叶, Walsh 和 Harr 函数都是正交函数, 被 应用于构造 GA 难/ 易问题和。