遗传算法及其应用

遗传算法及其应用

作者：黄少荣

来源：《电脑知识与技术》2008年第34期

摘要：遗传算法是智能优化方法中应用最为广泛也最为成功的算法，在各个领域得到广泛应用。该文在介绍了遗传算法的发展历史和具体操作步骤的基础上，总结出遗传算法的特点，并对它的各个应用领域进行了详细阐述。

关键词： 遗传算法；交叉；变异；选择；应用

中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)34-1874-03 Application and Theory of Genetic Algorithm HUANG Shao-rong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Abstract: Genetic algorithm (GA) is an intelligent optimization algorithm that has been used the most extensively, and has the most influential effect. This paper introduces the GA’s history of the development and the process of operation, sums up its characteristics and introduces its application in various fields in detail.

Key words: genetic algorithm; crossover; mutation; selection; application 1 引言

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰）演化而来的一种自适应全局优化概率搜索方法，它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。

近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，使其成为一个多领域、多学科的重要研究方向。 2 遗传算法的发展

遗传算法起源于本世纪40年代对生物系统所进行的计算机模拟研究，从生物学的角度进行生物的进化过程模拟、遗传过程模拟等操作。60年代，美国的Holland教授认识到生物的遗

龙源期刊网 http://www.qikan.com.cn

传和自然进化现象与人工自适应系统的相似性，提出研究人工自适应系统时，可借鉴生物的遗传机制以群体的方法进行自适应搜索。1975年Holland出版了《自然系统和人工系统的适配》[1]系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式定理，这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。与此同时，De Jong基于遗传算法的思想并结合模式定理在计算机上进行了大量的纯数值函数优化计算机实验，并提出了诸如代沟等新的遗传操作技术，树立了遗传算法的工作框架[2]，Holland和De Jong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。80年代由Goldberg进行归纳总结，对遗传算法的基本原理及其应用进行了全面而完整的论述，奠定了现代遗传算法的科学基础[3]。

进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题，尤其是遗传算法的应用领域也不断扩大。 3 基本遗传算法

遗传算法是一种迭代的算法，它首先随机生成一个初始种群，这个初始种群由经过基因编码的一定数目的个体组成。这个初始种群按照一定的操作规则，如选择，复制，交叉，变异等，不断地演化出新的一代。并根据个体的适应度，按适者生存和优胜劣汰的原则，引导搜索过程向最优解逼近，末代种群的最优个体经过解码，可以作为问题近似最优解。 3.1 遗传算法的步骤

Holland提出的遗传算法常被称为“简单遗传算法（SGA）”，主要步骤如下： 1) 初始化群体；

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

3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体； 4) 按概率Pc进行交叉操作； 5) 按概率Pm进行变异操作；

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

7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 根据上述算法思想可得其算法框图如图1所示。

龙源期刊网 http://www.qikan.com.cn

1) 编码

遗传算法中，种群中的每个个体（染色体）是由基因构成的，所以个体要与优化问题的解如何对应，就需要通过基因来表示，即对个体进行正确编码。遗传算法的进化过程是建立在编码机制基础上的，编码对于算法的性能影响很大。常用的编码技术有[4]： 二进制编码：

使用固定长度的0，1二进制字符串来表示一个染色体，例如： X=（110110111）

就可以表示一个染色体，该个体的染色体长度为n=7。 浮点数编码：

个体的基因值用某一范围内的一个浮点数来表示，个体的染色体长度等于其决策变量的个数。例如某优化问题含有4个变量xi（i=1,2,3,4），xi∈[0,10]，则： X=（3.2,8.7,6.4,2.1）

就可以表示一个染色体，该个体的染色体长度为n=4。

二进制编码优点是编码解码简单，交叉，变异等遗传操作便于实现，而且易于运用理论（如模式定理等）进行分析。浮点编码则在变异操作上能够保持更好的种群多样性，不过，其搜索能力比二进制要弱一些。后来，又提出了格雷编码、符号编码、整数编码、树编码等编码策略。

2) 初始群体的生成

遗传算法是一种基于群体寻优的方法，算法运行时是以一个种群在搜索空间进行搜索，一般采用随机法产生一个初始种群，即随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成了一个群体。 3) 适应性评估检测

为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，称适应度。适应度是群体中个体生存机会的唯一确定性指标，表明个体或解的优劣性，其选取直接影响到遗传算法的收敛速度以及能否找到最优解，基本上依据优化的目标函数来确定。

龙源期刊网 http://www.qikan.com.cn

4) 选择

从当前群体中选择适应度高的个体以生成交配池。选择原则是适应性强的个体为下一代贡献一个或多个后代的概率大，选择之前必须计算每个个体的适应度。常用选择算法有： 轮盘赌选择：是最知名的选择方式，基本原理是根据每个染色体适应度的比例来确定该个体的选择概率或生存概率。个体适应度按比例转化为选中概率，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]的均匀随机数，将该随机数作为选择指针来确实被选个体。 锦标赛选择：随机地从种群中挑选一定数目的个体，然后将最好个体选做父个体，重复这个过程直至得到足够的个体。

另外，还有一些其他的选择方法，如随机遍历抽样法、（μ+λ）选择、稳态选择、排序与比例变换、随机剩余选择、基因池选择、选择等。 5) 交叉

是最主要的遗传操作，同时对两个染色体进行操作，组合两者的特性产生新的后代。算法性能很大程度上取决于采用的交叉运算，双亲的染色体是否进行交叉由交叉率来控制交叉一般可分为实值替换和二进制交叉两种：

实值替换：包括离散重组，中间重组和线性重组。

二进制交叉重组：最简单的二进制交叉是单点交叉，它的交叉原理如下： 父个体p1：01110011010 父个体p2：10101100101

交叉点的位置为5，则交叉后产生的两个子个体为： 子个体q1：01110│100101 子个体q2：10101│011010

除了单点交叉，还有两点交叉、多点交叉和均匀交叉等。 6) 变异

龙源期刊网 http://www.qikan.com.cn

在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。变异使算法具有一定的局部的随机搜索能力，也可防止发生因遗漏最优值而无法再找到最优解的情况，保持了算法的有效性和种群的多样性，是算法的一个重要操作过程。染色体是否变异由变异率来控制。常用的变异有： 二进制变异：

对每个个体染色体上的二进制编码串进行操作，每一位以很小的概率从1变为0，或从0变为1。比如有如下二进制编码表示： ■

其码长为8，随机产生一个1至8之间的数K，假如现在K=5，对从右往左的第5位进行变异操作，将原来的0变为1，得到如下数码串（第四个1是被变异操作后出现的）： ■

向梯度方向变异：

对于目标函数可微的最大化问题，可采用如下变异操作： Z=X+▽f(X).α α∈U(0,a)

其中，▽f(X)是目标函数在X处的梯度。 对于最小化问题，则采用如下变异： Z=X-▽f(X).α α∈U(0,a)

另外，还有实值变异、基本位变异、均匀变异、边界变异、非均匀变异以及高斯变异等。 7) 参数控制

遗传算法有4个运行参数需要提前设定，并且实际应用中，需要多次测试后才能确定这些参数合理的取值：

M：种群大小。它对算法的效率有明显的影响，规模太小不利于进化，而规模太大将导致程序运行时间过长。不同问题，种群规模不同，通常为20～100。 T：终止进化代数。一般取100～500。

龙源期刊网 http://www.qikan.com.cn

Pc：交叉概率。并不是所有被选择的染色体都要进行交叉或变异操作，而是以一定的概率进行。在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级，一般取0.4～0.99。

Pm：变异概率。一般取0.0001～0.1。 8) 中止条件控制

遗传算法的终止条件通常可以从两方面进行控制：一个是预先设定最大的进化代数，另一个是当算法在规定的代数内还没有找到更优解则终止算法。 3.2 遗传算法的特点

遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为： ① 首先组成一组候选解； ② 依据某些适应性条件测算这些候选解的适应度； ③ 根据适应度保留某些候选解，放弃其他候选解； ④ 对保留的候选解进行某些操作，生成新的候选解。遗传算法将上述特征组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。此外，还具有以下特点：

1) 搜索过程从一群初始点开始，而不是单一的初始点。覆盖面大，可有效防止陷入局部最优，利于全局择优。

2) 仅用适应度来评估个体并在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，大大扩展了其应用范围。 3) 使用概率搜索技术，而非确定性规则。

4) 具有潜在的并行性。采用种群的方式组织搜索，可同时搜索多个有效区域并相互交流信息，能以较少的计算获得较高的效率。

5) 具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

6) 结构简单明了，容易与其他方法结合，而且算法内在的并行性使它适合大规模的运算，可以有效对复杂系统进行模拟和优化。 4 遗传算法的应用

龙源期刊网 http://www.qikan.com.cn

由于遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类具有很强的鲁棒性，前面描述是简单的遗传算法模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域[5]： 1)优化

优化问题在运筹学、管理学和工程设计中处于非常重要的地位，遗传算法在优化问题的上应用包括：

① 函数优化问题：是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。

② 组合优化问题：组合优化问题的本质可归纳为下列类型之一[6]：

确定与问题相关的某些项的排列（如资源约束的项目调度问题、车辆路径和调度问题等） 确定某些项的组合（如集覆盖问题和群体问题等） 确定某些项的排列和组合（如并行机器调度问题等） 任何带有约束的上述类型

组合优化理论上可通过牧举法找到最优解，但随着问题规模的增大，探索空间也急剧增大，在目前的计算机上很难求出最优解。遗传算法作为复杂问题优化方法的潜质已经受到了普遍的关注，实践证明，遗传算法对于组合优化中的NP完全问题非常有效。 ③ 多目标优化

该类问题存在多个目标需要同时优化，由于目标之间的无法比较和矛盾等现象，导致不一定存在使所有目标最优的解。由于遗传算法具有多方向和全局搜索特点，在解决这类问题上具有优势。 2) 自动控制

对大规模控制系统进行综合设计并建立数学模型，在对数学模型的优化上，遗传算法具有其它进化算法无法比拟的优点，已取得一定成绩。例如用遗传算法对自动控制系统数学模型寻优、用遗传算法优化PID控制系统、遗传算法在加工过程智能最优自适应控制的应用、基于遗传算法的模糊控制器的优化设计等。 3) 人工生命

龙源期刊网 http://www.qikan.com.cn

人工生命是用计算机模拟自然界的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，与遗传算法有密切关系。遗传算法已经在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力。 4) 图像处理和模式识别

遗传算法可以对图像进行优化，使图像处理中产生的一些误差达到最小。目前已经图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。 5) 机器人智能控制

是遗传算法的一个重要应用领域，已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到了应用。（下转第1882页）

（上接第1876页） 6) 程序设计

遗传算法可以用于某些特殊任务的计算机程序设计。 7) 机器学习

遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，特别是分类器系统，在很多领域中都得到了应用。 8) 经济学与社会经济问题

应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。 9) 免疫系统

应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。 10) 进化现象和学习现象

遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。

龙源期刊网 http://www.qikan.com.cn

5 结论

遗传算法作为强有力且应用广泛的随机搜索和优化方法，无论是理论研究还是应用研究都成了十分热门的课题，尤其是遗传算法的应用研究显得格外活跃。本文首先介绍遗传算法的发展与操作步骤，并总结出遗传算法的特点，最后详细介绍了遗传算法的各个应用领域。 参考文献：

[1] Holland J H.Adaptation in Nature and Artificial Systems[M].MIT Press,1992.

[2] De Jong K A.An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph. D Dissertation[D].University of Michigan,No.76-9381,1975.

[3] Goldberg D E.Genetic Algorithms in Search, Optimization and Machine Learning[M].Addison-Wesley,19.

[4] 汪定伟.智能优化方法[M].北京:高等教育出版社,2007:21-23.

[5] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 2005:15-17. [6] 玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2003.