遗传算法综述

遗传算法综述

摘要：遗传算法是基于自然界生物进化基本法则而进展起来的一类新算法，应用

广泛。本文主要以下几个方面：遗传算法的的起源和进展分支、重要人物和经典

文章、算法的结构、最新讨论成果及其在计算机领域的应用。

关键词：遗传算法，编码，搜寻，优化，交叉，遗传。

一、遗传算法的起源和进展分支

遗传算法（GenelicAlgorithm,简称GA）是生命科学与工程科学相互交叉、

相互渗透的产物，它是模拟达尔文生的遗传选择和自然淘汰的物进化论一种计算

模型，是一种通过模拟自然进化过程搜寻最优解的方法，它也可以被看成是对潜

在解空间的一种优化搜寻过程，它能在搜寻过程中自动猎取和积累有关搜寻空间

的学问，并自适应地掌握搜寻过程以求得最优解。“遗传算法由Michigan高校

的John-Holland和他的同事于二十世纪六十年月在对细胞自动机（cellular

automata）进行讨论时领先提出，并于1975年出版了颇影响的专著《Adaptation

inNaturalandArtificialSystems》，GA这个名称才渐渐为人所知，John・Holland

教授所提出的GA通常为简洁遗传算法（SGA）。”[A]

在二十世纪八十年月中期之前，对于遗传算法的讨论还仅仅限于理论方面，

直到在伊利诺伊高校召开了第一届世界遗传算法大会。随着计算机计算力量的进

展和实际应用需求的增多，遗传算法不论是在应用上、算法设计上，还是在基础

理论上，均取得了长足的进展，并且渐渐进入实际应用阶段。1989年，纽约时

报作者约翰•马科夫写了一篇文章描述第一个商业用途的遗传算法一进化者（英

文：Evolver)o之后，越来越多种类的遗传算法消失并被用于很多领域中，己

成为信息科学、计算机科学、运筹学和应用数学等诸多学科所共同关注的热点讨

论领域，财宝杂志500强企业中大多数都用它进行时间表支配、数据分析、将来

趋势猜测、预算、以及解决很多其他组合优化问题。

二、重要人物和经典文章

随着现代科学技术的快速进展以及社会进展对人工智能的迫切需要(在人工

智能领域中，有不少问题需要在简单而浩大的搜寻空间中查找最优解或准优

解。)，遗传算法被广发应用与各个领域，也有越来越多的人去讨论遗传算法。

有一大批学者对其作出深化的讨论，并且得到了相当好的收货，并发表了具有重

要价值和意义的著作或文章。

1975年Holland出版了他的闻名专著《自然系统和人工系统的自适应》

(Ad叩tationinNaturalandArtificialSystems),因这是第一本系统论述遗传算法

的专著，有人把1975年作为遗传算法的诞生年。Holland在该书中系统阐述了

遗传算法的基本理论和方法，并提出了对遗传算法的理沦讨论和进展极其重要的

模式理论(schematheory)。该理论首次确认了结构重组遗传操作对于获得隐并

行性的重要性。同年，Jong完成了他的博士论文《一类遗传自适应系统的行为

分析》(AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem)。

1989年,Holland的同学出版专著《搜寻、优化和矶器学习中的遗传算法》

(GeneticAlgorithmsinSearch,Optimization,andMachineLearning)。该书总结

了遗传算法讨论的主要成果，对遗传算法及应用作了全面系统的论述。

1991年，L.Davis编辑出版了《遗传算法手册》

(HandbookofGeneticAlgorithms),其中包括了遗传算法在工程技术和社会生

活中的大量应用实例。

1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机

程序设计》"。1994年，他又出版了《遗传程序设计，其次册:可重用程序的自

动发觉》深化了遗传程序设计的讨论，使程序设计自动化呈现了新局面。【B】

遗传算法的主要著作一览：

1.J.H.Holland,AdaptationinNaturalandArtificialSystems.AnnArbor:Univ.Of

MichiganPress,1975

2.L.D.Davis,HandbookofGeneticAlgorithms,VanNostrandReinhold

3.Bauer,GeneticAlgorithmsandInvestimentStrategies,1994

4.Wiely,GeneticAlgorithmsinEngineeringandComputerScience,1995

5.Z.Michalewicz,GeneticAlgorithms+DataSlructures=EvolutionPrograms,

SpingerPress,1996

6.Davis,GeneticAlgorithmsandSimulatedAnnealing,1987

7.陈国良等，遗传算法及其应用，国防出版社u

三、算法结构

遗传算法是从代表问题可能潜在解集的一个种群开头的，一个种群由经过基

因编码的肯定数目的个体蛆■成，初始种群产牛.之后，依据适者牛.存和优胜劣汰的

原理，逐步演化产生出越来越好的近似解。在每•代，依据问题域中个体的适应

度大小选择个体，并借助自然遗传学的遗传算子进行交叉和变异，产生出代表新

的解集的种群。这个过程将导致种群向自然进化一样的言代种群比前代更加适应

环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

遗传算法所涉及的四大要素：参数编码和初始群体、适应度函数、遗传操作

和掌握参数，其详细内容如下：

(1)参数编码和初始群体，遗传算法中常用的编码方法是二进制编码，它将问题

空间的参数用字符集｛0,1｝构成染色体位串，符合最小字符集原则，操作简洁,

便于用模式定理分析。

(2)适应度函数。适应度函数是评价个体适应环境的力量，使选择操作的依据，

是由目标函数变换而成。适应度的尺度变换是对目标区数值域的某种映射变换，

可克服未成熟收敛和随机漫游现象。

(3)遗传操作。包括选择、交叉、变异。

①选择(Selection)选择是用来确定交叉个体，以及被选个体将产生多少个

子代个体。其主要思想是人体的复制概率正比于其适应值，但按比例选择不肯定

能达到好的效果。选择操作从早期的轮盘赌选择进展到现在最佳个体保存法、排

序选择法、联赛选择法、随机遍历抽样法、局部选择法、柔性分段复制、稳态复

制、最优串复制、最优申保留等。

②交叉(Crossover)交叉是指把两个父代个体的部分结构加以替换重组而生

成新个体的操作，其作用是组合出新的个体，在串空间进行有效搜寻，同时降低

对有效模式的破坏概率。

交叉操作的简洁方式是将被选择出的两个个体P1和P2作为父母个体，将两者的

部分码值进行交换。假设与如下八位长的二个体：

1000111011011001

产生一个在1到7之间的随机数c,假如现在产生的是3,将P1和P2的低

三位交换：PI的高五位与P2的低三位组成数串10001001,这就是P1和P2的

一个后代QI个体；P2的高五位与P1的低三位组成数串11011110,这就是P1

和P2的一个后代Q2个体。其交换过程如下图所示：

③变异(Mutation)•变异是指将个体编码串中的某些基因值用其它基因值来

替换，形成一个新的个体。遗传算法中的变异运算是产生新个体的帮助方法，其

目的是使遗传算法具有局部的随机搜寻力量和保持群体的多样性。变异算法包括

确定变异点的位置和进行基因值替换。变异操作的简洁方式是转变数码串的某个

位置上的数码。我们先以最简洁的二进制编码表示方式来说明，二进制编码表示

的每一个位置的数码只有0与1这两个可能，比如有如下二进制编码表示：

10100110

其码长为8,随机产生一个1至8之间的数k,假如现在k=5,对从右往左

的第5位进行变异操作，将原来的0变为1,得到如下数码串(红色的数字1是

被变异操作后消失的)：

10110110

二进制编码表示时的简洁变异操作是将0与1互换：0变异为1,1变异为0。

(4)掌握参数。遗传算法需要确定一些参数取值，主要有串长Z,群体大小

pop_size,交叉概率Pc,变异概率Pm等。目前对参数依据状况进行调整变化讨

论比较多，参数范围一般是：pop_size=20—200,Pc=0.5—1.0,Pm=0—0.05。

遗传算法的基木流程

(1)初始化群体；

(2)计算群体上每个个体的适应度值；

(3)按由个体适应度值所打算的某个规章选择将进入下一代的个体；

(4)按概率Pc进行交叉操作；

(5)按概率Pc进行突变操作；

(6)没有满足某种停止条件，则转第⑵步，否则进入(7)。

(7)输出种群中适应度值最优的染色体作为问题的满足解或最优解。

程序的停止条件最简洁的有如下二种：完成了预先给定的进化代数则停止；

种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有

改进时停止。

(结♦束)

四、最新讨论成果

遗传算法在计算机科学与人工智能领域中的应用包括数据库查询优化、数据

挖掘与学问猎取、人工神经网络结构与参数优化、模式识别、专家系统等。此外,

遗传算法在软件测试用自动生成方面也作出了很大的贡献。

1）自动掌握领域:遗传算法可用于求解系统参数辨识问题。Karr采纳遗传算法

设计自适应模糊规律掌握器,取得显著的效果；Es-posito等人将基于GA的优

化技术应用于RBF神经网络输出层权值的优化;Vesin等人将GA用于解决网

络结构和权值的完全优化问题。遗传算法也可用于掌握器参数优化整

定;Fonesca等人将MOGA（多目标遗传算法）用于掌握器的优化设计以解决

磁悬浮列车的掌握器设计问题;颜文俊等人则提出一类新型的多目标鲁棒优

化掌握器设计方法,通过有效算法求解满足系统鲁棒稳定性和鲁棒性能的优

化解。止匕外,GA在故障诊断和机器人行走路径规划中的应用也取得了胜利。

2）在多目标函数优化问题方面：多目标问题最早由意大利经济学家Pareto在

1896年从政治经济学的角度提出的。多目标群体决策是当前管理科学、决策

理论、系统工程、运筹学、福利经济学等学科讨论中非常重要的内容。GA

很适合求解多目标优化问题，由于GA可以并行地处理各个目标，避开了目标

间的优先排序处理.GA通过保持一个潜在解的种群进行多方向搜寻，这种种

群对种群的搜寻可以跳出局部最优解，从而突破了数学规划法的点对点的搜

寻方法。GA在整个解空间同时开头寻优搜寻,注意区域搜寻和空间扩展的

平衡，因此可以有效地避开陷入局部极值点，具备全局最优搜寻性，不会受到

如Pa©。曲面外形、目标个数等条件的限制,还可处理带随机的、不确定的

离散搜寻空间问题，这正是数学规划法所难以克服内。Hajcla等人把多目标

问题通过效用函数转换为单目标问题,再用GA来求解。目前,怎样采用GA

的智能性来求解多目标函数优化问题，仍旧是一个值得讨论的新课题。

3）遗传学习：将遗传算法用于学问猎取，构成以遗传算法为核心的机器学习系

统。比较经典的是Holland设计的用于序列决策学习的桶链算法

（buckelbrigade）反馈机制（该系统被称为分类器系统;,以及机器人规章、概念

学习、模式识别等。[C]

五、在计算机专业学科的应用以及代表性文章

1.遗传算法在计算机帮助药物分子设计中的应用（侯廷军徐筱杰）

作为一种重要的启发式优化算法，