第 18 卷 第 4 期 Vol.18 No.4 2005 年 04 月 JOURNAL OF WUHAN UNIVERSITY OF SCIENCE AND ENGINEERING Apr. 2005 武 汉 科 技 学 院 学 报 遗传算法及其应用 臧 辉 (武汉科技学院 ，湖北 武汉 430074) 摘要：遗传算法是模拟自然界生物进化过程的计算模型。这种算法具有搜索过程简单、通用性和鲁棒性强的 特点以及广泛的应用潜力。本文概要地介绍了遗传算法的基本原理、理论，并在此基础之上阐述了遗传算法 在三个领域的应用。最后对遗传算法做了一定的展望。 关键词：遗传算法；模式定理；机器学习；组合优化 中图分类号：TP312 文献标识码：A 文献编号：1009－5160（2005）－0055－03 1 引言 遗传算法(Genetic Algorithms, GA)正在迅速发展。GA 是由美国学者 Holland 于 1975 年首先提出的[1]，它是模拟达尔文的 遗传选择和自然淘汰的生物进化论的计算模型。GA 的主要优点是简单、通用、鲁棒性强，适合于并行分布处理。 GA 以其很强的解决问题的能力和广泛的适应性渗透到研究与工程的各个领域，在机器学习[2]、智能控制[3]、组合优化等 方面[4]，GA 算法已经得到了广泛的应用，并取得了良好的效果。 2 遗传算法 遗传算法(Genetic Algorithms 简称 GA)是建立在自然选择和遗传变异 基础上的迭代自适应概率搜索算法，在这种算法中，染色体是二进制字符 串编码，即有一群候选解，染色体是主要的进化对象，象生物进化一样有 繁殖(Reproduction)、交叉(Cross-over)和变异(Mutation)三种现象，这些现 象称为遗传算子(Genetic Operator)。在每一代中，对于某一给定问题，保 持一定数目 N 为定值的解群 P(t)，经过对各解的适应度(Fitness)值 f，使解 群中各解得到评价，各解的适应度值的大小作为染色体复制机会大小的先 决条件。交叉和变异算子使得最终得到的解具有全局性。 遗传算法是具有“生成＋检测”(generate-and-test)的迭代过程的搜索 算法。它的基本处理流程如下图所示： 由上图可知，遗传算法中包含了以下 5 个基本要素：1）参数编码；2） 初始群体的设计；3）适应度函数的设计；4）遗传操作设计；5）控制参 数设定。这 5 个要素构成了遗传算法的核心内容。 3 遗传算法的理论基础 编码和初始集团生成 集团中个体适应度的检测 选择 交叉 变异 图 1 遗传算法的基本流程 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可以通过模式定理和构造假设等分析加以讨论。 3.1 模式定理 收稿日期：2005-03-04 作者简介：臧辉（1976－），男，硕士在读，研究方向：计算机数据库. 基金项目：湖北省教育厅科研项目(20004Q001). 

56 武 汉 科 技 学 院 学 报 2005 年 我们将种群中的个体即基因串中的相似样板称为“模式”，即描述在某些串位置相似的串的子集。模式是基于三个字符 集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 模式(schema) 定理, 或称 GA 基本定理用数学形式表示为: m(H,t+1)≥m(H,t) ⋅ Hf ( f ) [1- p c H ( ) δ l 1 − − pHO ) ( ] m 其中,m(H,t+1)表示在 t+1 代种群中存在模式 H 的个体数目。m(H,t)表示在 t 代种群中存在模式 H 的个体数目.f(H)表示在 t 代种群中存在模式 H 的个体平均适应度。 f 表示在 t 代种群中所有个体的平均适应度。 l 表示个体的长度。 cp 表示交叉概 率。 mp 表示变异概率。δ (H)定义为模式 H 中第一个确定位置和最后一个确定位置之间的距离。 模式定理用数学表达式预测包含图式 H 的某群体通过进化, 在下一代群体中存在于 H 中的串的数量有多少, 从而使人们 根据问题要求, 给出一些适当的参数, 以便更好地模拟“适者生存”、“优胜劣汰”等进化规律, 以求得具有好的特征的最优 解。模式定理是遗传算法的基本理论，保证了较优的模式的数目呈指数增长。 3.2 积木块假设 从模式定理可看出, 有好的特征的、短定义长的、底阶的模式, 在连续的后代里获得至少以指数增长的串数目。主要因为 选择使最好的模式有更多的复制, 简单的交换不容易破坏高频率出现的、短定义长的模式,而一般突变的概率又相当小, 因而 它对这些重要的模式几乎没有影响。遗传算法通过短定义距、低阶以及高平均适应度的模式(积木块)，在遗传操作下相互结 合，最终接近全局最优解。这就是积木块假设。 目前大量的实践支持积木块假设，并在很多领域内都取得了成功，如：平滑多峰问题。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了 在遗传算子的作用下，能生成全局最优解。 4 遗传算法的优点和应用 遗传算法与传统的搜索方法相比较而言，具有以下几个优点： （1）遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作使得遗传算法可直接对结构对 象进行操作。 （2 ）许多传统搜索方法都是采用单点搜索算法，这种点对点的搜索方法对于多峰分布的搜索空间经常会陷入局部的某 个单峰的局部最优解。而遗传算法采用的是同时对搜索空间的多个解进行评估。所以使得遗传算法具有较好的全局搜索能力。 （3）在标准的遗传算法中，基本上不需要其他的辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传 操作。 它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。正是基于以上的几个优点，遗传算法在很多领域都有着 广泛的应用。 4.1 遗传算法在机器学习方面的应用 机器学习是为解决专家系统设计中的知识获取瓶颈问题而兴起的[5],力图实现知识的自动获取。遗传算法从一开始就与机 器学习有着非常密切的关系。第一个基于遗传算法的机器学习系统分类器系统 CS-1 就是遗传算法的创立者 Holland 教授实现 的[6]。近年来由于遗传算法的发展，基于进化机制的遗传学习成为一种新机器学习方法，它将知识表达为另一种符号形式－ 遗传基因型，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习。在机器学习中，最主要有两种方法：密歇根 方法(Michigan approach)和匹茨堡方法(pitt approach)。密歇根方法的操作对象是单条规则，而匹茨堡方法的操作对象是规则 集合。但是这两种方法都存在一些自身的缺点。日本名古屋大学的市桥等结合了两种方法的优点提出了“名古屋方法”(nagoya approach),这些方法都分别在复杂机器学习系统中获得了成功的应用。 4.2 遗传算法在智能控制方面的应用 遗传算法在控制领域的应用大致分为两类：一类是离线设计和分析；另一类是在线自适应调整。对第一类而言，遗传算 法作为优化器，对于已知的控制对象寻求合适的控制规则满足控制品质方面的要求，或者对于特定的控制器结构搜索最优的 参数。而对于第二类，遗传算法则是作为一种学习机制来确定未知的或非稳定系统的特征，或者对控制器进行自适应调整。 4.3 遗传算法在组合优化问题方面的应用 组合优化是遗传算法最基本也是最重要的应用领域之一。所谓组合优化问题是指在离散的、有限的数学结构上, 寻找一 个满足给定约束条件并使其目标函数值达到最大或最小的解。在日常生活中，特别是在工程设计中，有许多这样的问题。最 

第 4 期 臧 辉：遗传算法及其应用 57 典型的就是巡回旅行商问题(Traveling Salesman Problem, TSP)和背包问题(knapsack problem)。 TSP 问题是 GA 的一个十分活跃的研究内容。据报道[7]，用遗传算法对 431 个城市的 TSP 问题求解已经可以得到最优解， 对 666 个城市求解可以得到准优化解。与其他的搜索算法相比较而言，遗传算法具有较好的鲁棒性和并行性。 5 结论 本文对 GA 的现状、理论和应用进行了概括性的叙述。尽管目前对遗传算法的研究还存在着一些有争议的问题，而且整 个遗传算法的理论基础还显得比较薄弱。但是研究表明，GA 模拟自然具有进化特征的搜索过程简单、通用强和鲁棒性强。 我们相信，利用广泛的数学方法和计算机模拟工具，遗传算法必将取得长足的进展。 J. H. Holland. Adaptation in Natural and Artificial System[M]. The Univ Michigan Press , 1975. 参考文献： [1] [2] De Jong K. Learning with Genetic Algorithm[J]. An Overview. Machine Learning , 1988,3(2,3): 121-138. [3] 郭旭红， 芮延年， 李军涛 基于遗传算法模糊智能控制系统的研究[J]. 苏州大学学报 2004,5. [4] 罗映红 遗传算法求解组合优化问题研究[J]. 甘肃科学学报 1997，2 [5] 陈国良, 王煦法, 庄镇泉等. 遗传算法及其应用[J]. 北京：人民邮电出版社, 1985: 164-191. [6] Holland J H, Reitman. J.S, Cognitive Systems Based on Adaptive Algorithms. In: Waterman D A, Hayes-Roth F(Eds.).Pattern Directed Inference Systems[M]. New York:Academic Press, 1978,313-329. [7] G. Rawlins. Foundations of Genetic Algorithm[M]. Morgan kaufmann.1991. GENETIC ALGORITHM AND ITS APPLICATIONS (Dep. Of Computer Science, Wuhan University of Science and Engineering, Wuhan Hubei 430074, China) ZANG Hui Abstract：Genetic algorithm is a computational model which simulates the nature evolution procedures. This algorithm characters its simple operations ,generalization ,robustness. This paper briefly introduces the main ideas of genetic algorithm , its basic theory and explains the applications of GA in three fields. Finally, do certain prospect to the genetic algorithm. Keywords: genetic algorithm; schema theorem; machine learning; combination and optimization