遗传算法综述

遗传算法综述

尘本是心

摘 要：遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度有效的随机搜索算法。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注。本文介绍了遗传算法的基本原理和特点，以及在各个领域的应用情况。

关键词：遗传算法，综述，最优化。

A Review of Genetic Algorithms

Chen Benshixin

Abstract: Genetic algorithms are considered as a search used in computing to find exact or a approximate solution for optimization and search problems. This article has a review of the genetic algorithm basic principle and the characteristic and its applications.

Keywords: genetic algorithm, review, Optimization

0 前言

在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准最优解。在计算此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到最优解的通用搜索算法一直是令人瞩目的课题。

遗传算是这类特别有效的算法之一，它(GeneticAlgorithm,GA)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机搜索算法。是由美国Michigan大学的J.Holland教授1975年首先提出，它尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。如著名的TSP、背包问题、排课问题等

1 遗传算法基本原理

遗传算法是建立在自然选择和群众遗传学机理基础上的，具有广泛适应性的搜索方法。遗传算法搜索结合了达尔文适者生存和随机信息交换的思想，适者生存消除了解中不适应因素，随机信息交换利用了原有解中已知的知识，从而有力地加快了搜索过程。

遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码的一定数目的个体组成，初始种群产生之后，按照适者生存和优胜劣汰的原理，逐步演化产生出越来越好的近似解。在遗传算法的执行过程中，每一代有许多不同的种群个体（染色体）同时存在。这些染色体中哪个保留，哪个淘汰，是根据它们对环境的适应能力来决定的，适应度强的有更多的机会保留下来。适应度强弱是通过计算适应度函数的值来判别的，这个值称为适应值。适应度函数的构成与目标函数有密切关系，往往是目标函数的变种。

主要的遗传算子有以下几种: （1）选择(Selection)算子：

又称复制(reproduction)、繁殖算子。是从种群中选择生命力强的染色体，产生新种群的过程。选择的依据是每个染色体的适应度大小，适应度越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。选择的方法根据不同的问题，采用不同的方案。最常见的方法有随机遍历抽样、局部选择和截断选择等。

（2）交叉(Crossover)算子：

又称重组(recombination)、配对(breeding)算子。当许多染色体相同或后代的染色体与上一代没有多大差别时，可通过染色体重组来产生新一代染色体。染色体重组分两个步骤进行：首先，在新复制的群体中随机选取两个染色体，每个染色体由多个位(基因)组成；然后，沿着这两个染色体的基因随机取一个位置，二者互换从该位置起的末尾部分基因。

遗传算法的有效性主要来自选择和交叉操作，尤其是交叉，在遗传算法中起着核心作用，它决定了遗传算法的全局搜索能力。

（3）变异(Mutation)算子：

选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力，即决定了遗传算法的局部搜索能力。.变异就是以很小的概率，随机改变字符串某个位置上的值在二进制编码中，就是将0变成1，将1变成0，它本身是一种随机搜索，但与选择、交叉算子结合在一起，就能避免由复制和交叉算子引起的某些信息的永久性丢失，从而保证了遗传算法的有效性。

2 遗传算法的主要特点及改进

随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决搜索和优化的通用方法，遗传算法正是为我们提供的一个有效的途径，它不同于传统的搜索和优化方法。主要区别在于：

（1）搜索过程不直接作用在变量上，而是作用于参数集进行了编码的个体上。此编码操作，使得遗传算法可直接对结构对象进行操作。

（2）搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。

（3）采用概率的变迁规则来指导搜索方向，不采用确定性搜索规则。

（4）对搜索空间没有任何特殊要求，只利用适应度信息，不需要其它辅助信息，适应范围更广。 （5）对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定。

对全局信息有效利用和隐含并行性是遗传算法的两大特点，同时遗传算法对问题本身的限制较少，因而具有很强的通用优化能力。但遗传算法容易过早收敛，这样就会使其他个体中的有效基因不能得到有效复制，最终丢失；而且在进化后期染色体之间的差别极小，整个种群进化停滞不前，搜索效率较低，这样就会导致搜索到的结果不是全局最优解。

自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来，众多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究，其基本途径概括起来有以下几个方面：

（1）改变遗传算法的组成部分或使用技术； （2）采用混合遗传算法；

（3）采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度； （4）采用非标准的遗传操作算子； （5）采用并行遗传算法等。

3 遗传算法的基本术语

遗传算法效法于自然选择的生物变化，是一种模仿生物进化过程的随机方法，因此下面几个关于生物学的基本概念与术语对理解遗传算法是非常重要的。

（1）染色体(chromosome)是生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子———基因组成。

（2）遗传因子(gene)DNA或RNA长链结构中占有一定位置的基本遗传单位，也称为基因。 （3）个体(individual)指染色体带有特征的实体，在问题简化的情况下可代表染色体。

（4）种群(population)染色体带有特征的个体的集合称为种群，该集合内个体数称为群体的大小。有时个体的集合也称为个体群。

（5）进化(evolution)生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。

（6）适应度(fitness)在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖的机会就相对较少，甚至逐渐灭绝。

4 遗传算法的基本步骤

4.1遗传算法设计

（1）编码:遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。

（2）初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体.遗传算法以这N个串结构数据作为初始点开始迭代。

（3）适应度评估检测：适应度函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。

（4）选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法进行选择的原则是适应度强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。

（5）交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。

（6）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，遗传算法中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会，

遗传算法的计算过程为：选择编码方式→产生初始群体→计算初始群体的适应度值→如果不满足条件{选择→交换→变异→计算新一代群体的适应度值}。

4.2遗传参数的确定

在遗传算法的具体实现过程中，优化参数需要事先确定，包括种群数量、交叉概率、变异概率等。参数的选取对遗传算法的性能有重要影响。

（1）种群数量n。

群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当种群数量太小时，遗传算法的优化性能一般不会太好，种群数量较大则可减少遗传算法陷入局部最优解的机率，但也意味着计算复杂度变大，效率变低。一般取n从10到160之间。具体的的种群数量根据具体情况有所不同。 （2）交叉概率

交叉概率的选择决定了交叉操作的频率，频率越高，可以越快地收敛到最优解区域，但过高的频率也可能导致收敛于一个解若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般取Pc从0.25～1.00之间。 （3）变异概率Pm

变异概率通常只取较小的数值，通常为0.001左右。一般而言，低频度的变异可防止群体中重要的、单一基因的可能丢失；若取较高的变异概率将使遗传算法趋于纯粹的随机搜索，一方面会增加样本模式的多样性，另一方面也可能引起不稳定作者认为以上最难把握的是如下几点：第一，要确定采用什么编码，即怎样用基因描述问题的一个有效解。编码一旦确定了，一般就确定交叉和变异算法了。第二，设计出适应度函数，这很重要，因为它决定着算法进化的方向,最终影响算法效率，如果设计的好，可能很快就能收敛到较好的解，如果设计不好，很可能不能进化。第三，适应度函数选择显然要和目标函数一致。

另外，遗传算法的难点就在于评估函数、变异系数、种群大小、交叉和变异方法等问题与收敛速度的关系难以找到定量的描述。比如，变异系数找得不合理，或以上问题处理不好收敛会很慢甚至不会收敛，可能就得不到解。

5 遗传算法的应用领域

遗传算法经过几十年的发展，逐渐被人们接受和运用，遗传算法的应用研究比理论研究更为丰富，下面是遗传算法的一些主要应用领域：

（1）优化问题：优化问题包括函数优化和组合优化两种。函数优化是遗传算法的经典领域，也是对遗传算法进行性能评价的常用算例。对于组合优化，随着问题规模的扩大，搜索空间急剧扩大，这类复杂问题，人们已经意识到把精力放在寻找其满意解上。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。

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

（3）自动控制：在自动控制领域中许多与优化相关的问题需要求解，遗传算法的应用日益增加，并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习，都显示了遗传算法在这些领域中应用的可能性。

（4）机器人智能控制：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。

（5）图像处理和模式识别：图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地产生一些误差，这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。

6 总结

遗传算法作为一种非确定性的模拟自然演化的学习过程的求解问题方法，在很多领域具有广泛的应用价值，但其在很多方面有待于进一步研究、探讨和完善。可以预期，随着计算机技术的进步和生物学研究的深入，遗传算法在操作技术和方法上将更通用、更有效。

参考文献

[1] 高颖. 遗传算法综述[J]. 计算机光盘软件与应用, 2010 (4): 90-91.

[2] 马永, 贾俊芳. 遗传算法研究综述[J]. 山西大同大学学报: 自然科学版, 2008 (6).

[3] Kumar M, Husian M, Upreti N, et al. Genetic algorithm: Review and application[J]. International Journal of

Information Technology and Knowledge Management, 2010, 2(2): 451-454.

[4] 常洪江. 遗传算法综述[J]. 电脑学习, 2010 (3): 115-116.

[5] 刘立平, 牛熠. 遗传算法综述[J]. 东莞理工学院学报, 2005, 12(3): 48-52. [6] Kumar K. Genetic Algorithm Review[J].

[7] Cantú-Paz E. A summary of research on parallel genetic algorithms[J]. 1995.