遗传算法的发展及其应用.doc

遗传算法的发展及其应用

摘要：遗传算法GA（Genetic Algorithms）由美国学者J.H.Holland提出， 它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。它是一种模拟自然界生物进化过程的计算模型。它的求解问题是从多个可行解开始，然后通过一定的法则进行迭代以产生新解，直到得到最优结果。就实质而言，遗传算法是一种具有内在并行性，能有效解决计算量大的问题。

关键词：遗传算法，最优化方法，遗传算法的应用

The Development And Application of Genetic Algorithms
Shi Huimin
(School of Control Science and Engineering, Shandong University , Jinan, 250061)
Abstract: Genetic Algorithms (GA) is put forward by the American scholars J.H.Holland, it is based on the Darwin's theory of evolution and Mendel's biological Genetic theory on the basis of the algorithm. Gene and gene mutations may produce hybrid of environment adaptable offspring of the survival of the fittest, through natural selection, adapt to the genetic structure of high value is preserved. It is a natural evolution process of the simulation calculation model. It was solved DuoGe feasible solution from the start, and then through the certain principles of the iteration to produce new, get the optimal results until. Just parenchyma, genetic algorithm is a has intrinsic parallelism, can effectively solve the problem of large amount of calculation.

Key words: Genetic Algorithms, optimization method, the development of Genetic Algorithms

1遗传算法的介绍
遗传算法以其广泛的适应性渗透到研究与工程的各个领域，已有专门的遗传算法国际会议，每两年召开一次，如今已开了四次，发表了数千篇论文，对其基本的理论、方法和技巧做了充分的研究。今天，遗传算法的研究已成为国际学术界跨学科的热门话题之一。本文将论述遗传算法的基本原理、数学基础、特点，并介绍遗传算法的应用领域。

1.1遗传算法的产生和发展
50 年代末60 年代初， 生物学家Fraser 试图通过计算的方法来模拟生物界"遗传与选择"的进化过程，这便是GA 的雏形。受此启发，Holland 教授认识到自然遗传可以转化为人工遗传算法。1967 年Bagley 在其博士论文中首次提出了"遗传算法"这一术语。1975 年，Holland 出版了《自然与人工系统中的适应性行为》。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理， 从而奠定了遗传算法的理论基础。20 世纪80 年代初，Holland 教授实现了第一个基于遗传算法的机器学习系统--分类器系统(Classifier System 简称CS)，开创了基于遗传算法的机器学习的新概念。l992 年，John R．Koza 出版了专著《遗传编程》，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展， 关于遗传算法的国际学术活动越来越多， 遗传算法已成为一个多学科、多领域的重要研究方向。
遗传算法是一种基于生物的自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和突变现象。它将每个可能的解看做是群体（所有可能解）中的一个个体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适应度值。开始时总是随机地产生一些个体（即候选解），根据这些个体的适应度利用遗传算子对这些个体进行操作，得到一群新个体，这群新个体由于继承了上一代的一些优良性状，因而明显优于上一代，这样逐步朝着更优解的方向进化。遗传算法在每一代同时搜索参数空间的不同区域，然后把注意力集中到解空间中期望值最高的部分，从而使找到全局最优解的可能性大大增加。
1.2遗传算法的特点
作为进化算法的一个重要组成部分，遗传算法不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能：
1) 在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有函数导数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解问题。
2) 若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约O（n3）个模式，具有很高的并行性，因而具有明显的搜索效率。
3) 在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。
4) 对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性。
5) 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。

2遗传算法理论
2.1遗传算法对问题的描述
对于一个求函数最大值的优化问题（求函数最小值也雷同），一般可描述为下述数学规划模型：
(1)
式中，X=[x1,x2,…,xn]T 为决策变量，f(X)为目标函数，和为约束条件，U是基本空间，R是U的一个子集。集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们的关系如图1所示。
基本空间
可行解集合
U
R
X
可行解

图1 最优化问题的可行解及可行解集合
在遗传算法中，将n维决策向量X=[x1,x2,…,xn]T用n个记号Xi（i=1，2，…，n）所组成的符号串X来表示：
X = X1X2…Xn X=[x1 , x2 ,…,xn]T
把每个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。一般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个符号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。通常个体的表现型和基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。染色体X也称为个体X，对于每个个体X，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。
在遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。
生物的进化是以集体为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第ｔ代群体记做P(t)，经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P(t+1)。
这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。
生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。
选择（selection）：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。
交叉（crossover）：将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率（称为交叉概率，crossover rate）交换它们之间的部分染色体。
变异（mutation）：对群体P(t)中的每一个个体，以某一概率（称为变异概率，mutation rate）改变某一个或某一些基因座上的基因值为其他的等位基因。

2.2遗传算法的运算流程
遗传算法的主要运算流程如下：
步骤一：初始化。设置进化代数计数器t=0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。
步骤二：个体评价。计算群体P(t)中各个个体的适应度。
步骤三：选择运算。将选择算子作用于群体。
步骤四：交叉运算。将交叉算子作用于群体。
步骤五：变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
步骤六：终止条件判断。若t≤T，则：t=t+1，转到步骤二；若t>T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。
具体的流程示意图见图2所示。

群体P(t)
选择运算
交叉运算
变异运算
群体P(t+1)
解 码
解集合
个体评价
遗传空间
解空间

图2 遗传算法的运算过程示意
2.3基本遗传算法的构成要素
基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（simple genetic algorithms，简称SGA）[20]。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。
下面给出基本遗传算法的构成要素：
(1) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。如：
X=100111001000101101
就可表示一个个体，该个体的染色体长度是n=18。
(2) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。
(3) 遗传算子。基本遗传算法使用下述三种遗传算子：
选择运算使用比例选择算子；
交叉运算使用单点交叉算子；
变异运算使用基本位变异算子或均匀变异算子。
(4) 基本遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定：
N ：群体大小，即群体中所含染色体的数量，一般取为20～100。
maxgen ：遗传运算的终止进化代数，一般取为100～500。
pc ：交叉概率，一般取为0.4～0.99。
pm ：变异概率，一般取为0.0001～0.1。
需要说明的是，这里给出的4个运行参数的取值范围是在经过了多次试验后得到的经验值，它们对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。所以我们在遗传算法的实际应用中，要根据问题的不同并经过多次试验来合理地选择这些参数的取值大小或取值范围。

3遗传算法的应用
遗传算法的初期应用研究主要围绕组合优化问题求解，但近年来已迅速扩展到机器学习、设计规划、神经网络优化、自律分布控制和人工生命等众多领域。此外，还在核反应控制和喷气发动机设计等工程应用中进行了十分有意义的尝试。下面是遗传算法的一些主要应用领域。

3.1在组合优化中的应用
组合优化问题是遗传算法最基本也是最重要的应用领域。所谓组合优化问题是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数达到最大或最小的解。在日常生活中，特别是在工程设计中，有许多这样的问题。最典型的是巡回旅行商问题和背包问题。

3.2在生产调度问题中的应用
在很多情况下，生产调度问题建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。目前，在现实生产中，主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产调度、任务分配等方面遗传算法都得到了有效的应用。

3.3在自动控制中的应用
在自动控制领域中，有很多与优化相关的问题需要求解。例如，用遗传算法进行航空控制系统的优化、设计空间交会控制器等都显示出在这些领域中应用的可能性。

3.4在图像处理中的应用
图象处理是计算机视觉中的一个重要研究领域，如目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方面得到了应用。

3.5在机器学习领域中的应用
基于GA的机器学习是当前GA应用研究的热点，特别是分类器系统，在很多领域中都得到了应用。Holland的分类器系统是基于遗传算法机器学习的一个典型例子，GA部分的主要任务是产生新的分类器，如获取规则集合以预测公司的利润。Brooker等对分类器系统和GA进行了更加详细的评述。

3.6在数据挖掘中的应用
数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含、未知、有潜力、有应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库可看作搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中搜索，对随机产生的一组规则进化，直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。

4总结
本文详细介绍了遗传算法的理论和应用研究，并进行了系统分析和评论。通过讨论得到了如下的结论：遗传算法不是一种单纯的优化算法，而是一种以进化思想为基础的全新的一般方法，是解决复杂问题的有力工具；遗传算法应用日趋广泛，其本身的发展也是不断进化的过程，理论研究需要引入新的数学工具、吸收生物学的最新成果。

参考文献
[1]钱志勤，腾弘飞，孙治国．人机交互的遗传算法及其在约束布局优化中的应用[J]．计算机学报，2001。24：553—558．
[2]王征应，石冰心．基于启发式遗传算法的QOS组播路由问题求解[J]．计算机学报，2001，24：55—61．
[3]马光文，王黎．遗传算法在水电站优化调度中的应用[J]．水科学进展，1997，8(3)：275—280。
[4]Michalewicz Z．A modified Genetic Algorithm for Optimal Control Problems[J]．Computation Math．Application，1992，23(12)：83—94．
[5]林磊，王晓龙，刘家锋．基于遗传算法的手写体汉字识别系统优化方法的研究[J]．计算机研究与发展，2001，38(6)：658—661．
[6]Holland J H．Adaptation。Progress in Theoretical Biology，1976，4：263—293．
[7]Brooke L B，Goldberg D E ，Holland J H．Classifier System and Genetic Algorithms[J]．Artificial Intelligence，1989，40(2)：235—282．
[8]Sunil Choenni，Design and Implementation of a Genetic—Based Algorithm for Data Mining[J]．Proceeding of the VLDB Conference，Cairo，Egypt，2000：33—42．
[9] 王小平 等.遗传算法—理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002.
[10]GOLDBERG D E. Genetic Algorithms in Search, Optimization and Machine Learning[M].Reading, MA: Addison-Wesley, 1989.
[11]RENDERS J-M, FLASSE S P. Hybrid methods using genetic algorithms for global optimization[J].IEEE Transactions on Systems, Man, and Cybernetics(Part B),1996(2).
[12]WRIGHT A H. Genetic algorithm for real parameter optimization. In: Rawlins G ed [D]. Foundations of Genetic Algorithms. San Francisco: Morgan Kaufmann, 1991.
[13]ESHELMAN L J, SCHAFFER J D. Real-coded genetic algorithms and interval-schemata[J].Foundations of Genetic Algorithms, 1993(2).
[14]陈国良，王熙法，庄镇泉.遗传算法及其应用［M］.北京：人民邮电出版社，1996.
[15]张晓缋，戴冠中，徐乃平.遗传算法种群多样性的分析研究［J］.控制理论与应用，1998（1）.
[16]彭伟，卢锡城.一种函数优化问题的混合遗传算法［J］.软件学报，1999（8）
[17]宋远骏，杨孝宗，李德毅，崔东华．考虑环境因素的计算机可靠性评价[J]．计算机研究与发展，2001，38(5)：631— 636．
[18]Zhu Yunfang，Dal Chaohua，Chen Weirong，Lin Jianhui．Adaptive probabilities of crossover and mutation in genetic algorithms based on cloud generators[J]．Journal of Computational Information Systems，2005，1(4)：67l一678．
[19]张葛祥，李娜金炜东，等．一种新量子遗传算法及其应用[J]．电子学报，2004，32(3)：476—479．
[20]Roberto Irizarry．LARES：an artificial chemical process approach for optimization[J]．Evolutionary Computation，2004，12(4)：435—459．