遗传算法的理论研究综述_图文

1、收稿日期 :2003-10-18作者简介 :马玉明 (1972- , 女 , 山东省聊城市人 , 山东轻工业学院讲师 , 硕士研究生 , 主要从事自动控制和遗传算法的研究。遗传算法的理论研究综述马玉明 , 贺爱玲 , 李爱民(山东轻工业学院 计算机科学技术系 , 山东 济南 250100摘要 : 本文简单回顾了遗传算法的发展历史 , 并对遗传算法的理论从数学基础和改进两个方面进行了 综述。关键词 : 遗传算法 ; 模式定理 ; 隐性并行性中图分类号 :TP18 文献标识码 :A ( -04遗传算法 G A (G enetic 上 , 。这种算法的产生归功于美国的 Michigan 世纪 60年

2、代末 70年代初的开创性工作 ,H olland 不仅设计了 , 运用统计决策理论对遗传算法的搜索机理进行了分析 , 还建立了 著名的模式定理和隐性并行性原理 , 为遗传算法的发展奠定了基础 。在过去的三十多年里 , 人们对遗传算法进行了大量的研究 , 从大的方面分 , 这些研究可分 为两大类 , 即遗传算法的应用研究和遗传算法的理论研究 。由于遗传算法本身具备良好的全 局搜索能力 , 信息处理的隐含并行性 , 鲁棒性 , 可规模化等优良特点 , 因此被应用于各种领域 , 例如 :自动控制 、 约束优化 、 数据挖掘等 , 并渗透到其它许多学科如计算数学 、 交通、 计算机科 学 、 电子学等

3、 。1 遗传算法的理论研究遗传算法的基本步骤是编码生成初始种群 , 尔后使用选择 、 交叉和变异等基因操作 , 进行 有组织而又随机的信息交换 , 使优良品质被逐渐不断地继承下来 , 坏的特性被淘汰 。 遗传算法 的理论研究主要有遗传算法的数学基础研究和遗传算法的改进 。1. 1 数学基础研究模式定理及隐含并行性原理被看作遗传算法的两大基石 , 后来又提出了建筑块假设 , 但是 模式定理无法解释遗传算法实际操作中的许多现象 , 隐性并行性的论证存在严重漏洞 , 而建筑 块假设却从未得到过证明 。 对遗传算法的基础理论的研究主要分三个方面 :模式定理的拓广 和深入 、 遗传算法的新模型 、 遗传

4、算法的收敛性理论 。1. 1. 1 模式定理的拓广和深入H olland 给出模式定理 :具有短的定义长度 、 低阶 、 并且模式采样的平均适应值在种群平均 第 18卷第 3期2004年 9月 山 东 轻 工 业 学 院 学 报 JOURNA L OF SHANDONG INSTIT UTE OF LIGHT INDUSTRY Vol. 18No. 3Sep. 2004适应值以上的模式 , 在遗传迭代过程中将按指数增长率被采样 , 模式定理可表达为m (H , t +1 m (H , t f (1-p c l -1-O (H p m 其中 m (H , t :在 t 代群体中存在模式 H 的串

5、的个数f (H :在 t 代群体中包含模式 H 的串的平均适应值f :t 代群体中所有串的平均适应值l 表示串的长度 , p c 表示交换概率 , p m 表示变异概率 。H olland 的模式定理奠定了遗传算法的数学基础 , 根据隐性并行性得出每一代处理有效模 式的下限值是 n 3(C 1l 12 , 其中 n 是种群的大小 , C l 是小整数 。 Bertoui 和 Dorig o 进行了深入 的研究获得当 n =2l , 为任意值时 , 处理多少有效模式的表达式 。 上海交通大学的恽为民等 获得每次至少产生 O (2n -1 数量级的结果 。模式定理中模式适应度难以计算和分析 ,A.

6、 D.算法的模式处理 , 并引入模式变换的概念 , 采用均适应度 , G A 从全局最 最早运用 Walsh 模式转换设计出最小的 G A -。1. 1. 2由于遗传算法中的模式定理和隐性并行性存在不足之处 , 为了搞清楚遗传算法的机理 , 近 几年来人们建立了各种形式的新模型 , 最为典型的是马氏链模型 , 遗传算法的马氏链模型主要 由三种 , 分别是种群马氏链模型 、 Vose 模型和 Cerf 扰动马氏链模型 。种群马氏链模型将遗传算法的种群迭代序列视为一个有限状态马氏链来加以研究 , 运用 种群马氏链模型转移概率矩阵的某些一般性质 , 分析遗传算法的极限行为 , 但转移概率的具体 形式

7、难以表达 , 妨碍了对遗传算法的有限时间行为的研究 ;Vose 模型是在无限种群假设下 , 利 用相对频率 , 导出表示种群的概率的向量的迭代方程 , 通过这一迭代方程的研究 , 可以讨论种 群概率的不动点及其稳定性 , 从而导致对遗传算法的极限行为的刻划 , 但对解释有限种群遗传 算法的行为的能力相对差一些 。 Cerf 扰动模型是法国学者 Cerf 将遗传算法看成一种特殊形式 的广义模拟退火模型 , 利用了动力系统的随机扰动理论 , 对遗传算法的极限行为及收敛速度进 行了研究 。还有其它它改进模型 , 例如张铃 、 张钹等人提出的理想浓度模型 , 它首先引入浓度和家族 的概念 , 通过浓度

8、计算建立理想浓度模型 , 其浓度变化的规律为 :c (H i , t +1 =c (H , t f (H i (0 , t f (t c (H i , t +1 表示模式 H i 在 t 时刻的浓度 , 并对其进行分析 , 得出结论 :遗传算法本质上是 一个具有定向制导的随机搜索技术 , 其定向制导原则是导向适应度高的模式为祖先的染色体 “ 家族” 方向 。1. 1. 3 遗传算法的收敛性理论对于遗传算法的马氏链分析本身就是建立遗传算法的收敛性理论 ,Eiben 等用马尔可夫链 证明了保留最优个体的遗传算法的概率性全局收敛 ,Rudolph 用齐次有限马尔可夫链证明了具 有复制 、 交换 、

9、突变操作的标准遗传算法收敛不到全局最优解 , 不适合于静态函数的优化问题 , 87山 东 轻 工 业 学 院 学 报 第 18卷97第 3期 马玉明等 :遗传算法的理论研究综述 A survery o f the theory o f genetic algorithmMA Yu -ming , HE Ai -ling , LI Ai -min(Department of C om puter Science &techn ology ,shand ong Institute of Light Industry , Jinan 250100,China Abstract :Thispaper offers a sim ple overview of history of G enetic Alg orithm ,and conducts a survey of the theory of G enetic Alg orithm which includes the mathematic