遗传算法理论及其应用研究进展

摘要：本文阐述了遗传算法的基本原理以及求解问题的一般过程，讨论了遗传算法存在的不足和针对其不足采取的弥补措施，概述了遗传算法常见的应用领域。最后，讨论了遗传算法的未来研究方向。 关键词：遗传算法；算子；优化

Development on Genetic Algorithm Theory And Its

Application

Liu Jun (201320620181)

(College of Mechanical Engineering of University of South China Hengyang Hunan

421001)

Abstract: This paper stated the basic theory of Genetic Algorithm (GA) and the process of solving the problem, discussed the weakness of genetic algorithm and the improving measures about genetic algorithm. Then summarized the common application fields of genetic algorithm. Finally, pointed out the genetic algorithm’s research directions in the future.

Keywords: genetic algorithm (GA); operator; optimization

遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法，具有坚实的生物学基础；它提供从智能生成过程观点对生物智能的模拟，具有鲜明的认知学意义；它适合于无表达或有表达的任何类函数，具有可实现的并行计算行为；它能解决任何种类实际问题，具有广泛的应用价值。因此，遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维空间寻优问题。虽然遗传算法已成功应用于许多领域，但其自身还存在一些不足，如收敛速度慢或易出现“早熟”现象，局部搜索能力差等，导致

了算法的收敛性能差，需要很长时间才能找到最优解等问题。这些不足阻碍了遗传算法的推广应用。因此，如何提高算法收敛速度以及改善遗传算法的搜索能力，使其更好地应用于实际问题的解决中，成为各国研究者一直探索的重要课题。

1 遗传算法的执行过程

遗传算法作为一种自适应全局优化搜索算法，使用二进制遗传编码，即等位基因Γ={0,1}，个体空间HL={0,1}Ｌ，且繁殖分为交叉与变异两个独立的步骤进行。其流程图如图1.1所示

图1. 1 遗传算法流程图

其基本执行过程如下：

1) 初始化。确定种群规模Ｎ、交叉概率Pc、变异概率Pm和置终止进化准则;随机生成N个个体作为初始种群X(0)；置进化代数计数器t→0。

2) 个体评价。计算或估价X(t)中各个体的适应度。 3) 种群进化。

a) 选择(母体)。从X(t)中运用选择算子选择出M/2对母体(M≥N)。 b) 交叉。对所选择的M/2对母体，依概率Pc执行交叉形成M个中间个体。 c) 变异。对M个中间个体分别独立依概率Pm执行变异，形成M个候选

个体。

d) 选择(子代)。从上述所形成的M个候选个体中依适应，选择出N个个体组成新一代种群X(t+1)。

4) 终止检验。如已满足终止准则，则输出X(t+1)中具有最大适应度的个体作为最优解，终止计算；否则置t→t+1并转3）。

2 遗传算法的理论研究

遗传算法是进化算法的一种，国内外学习者对其理论研究主要注重以下几个方面：

? 编码表示

在许多问题求解中，编码是遗传算法中首要解决的问题，对算法的性能有很重要的影响。Holland提出的二进制编码是遗传算法中最常用的一种编码方法，它采用最小字符编码原则,编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。但二进制编码用于多维、高精度数值问题优化时,不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高，并且个体长度大、占用内存多。

? 适应度函数

在遗传算法中,适应度是描述个体性能的主要指标，根据适应度的大小对个体进行优胜劣汰。对于求解有约束的优化问题时，一般采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数；然后再将目标函数作适当处理，建立适合遗传算法的适应度函数。将目标函数转换成适应度函数一般应遵循两个原则：适应度必须非负；优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。在使用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验或算法来确定相应的参数。

? 遗传算子

在遗传算法中通过一系列算子来决定后代，算子对当前群体中选定的成员进行重组和变异。遗传操作包括以下三个基本遗传算子(genetic operator)：选择(selection)；交叉(crossover)；变异(mutation)。

选择算子。选择操作通过适应度选择优质个体而抛弃劣质个体，体现了“适

者生存”的原理。

交叉算子。交叉是指对两个相互交叉的染色体按某种方式相互交换其部分基因,，而形成两个新的个体。它是产生新个体的主要方法，决定了遗传算法的全局搜索能力，在遗传算法中起关键作用。

变异算子。变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。它是产生新个体的辅助方法,决定了遗传算法的局部搜索能力。变异算子与交叉算子相互配合，可以共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子主要有以下两个目的：改善遗传算法的局部搜索能力；维持群体的多样性,防止出现早熟现象。

? 收敛性分析

遗传算法的收敛性通常是指遗传算法所生成的迭代种群(或其分布)收敛到某一稳定状态(或分布)，或其适应值函数的最大或平均值随迭代趋于优化问题的最优值。

? 欺骗问题

欺骗问题是遗传算法研究中的一个热点。根据模式定理可知，低阶、短距的优模式在遗传子代中将以指数级增长，最终，不同的最优模式相互组合，从而得到最优解。但是，对于欺骗问题，复制算子受欺骗条件的“迷惑”，使最优低阶模式在组合后形成非最优高阶模式，从而使遗传算法偏离最优解。由于欺骗问题的存在，许多问题被归结为遗传算法难题，使遗传算法的应用受到一定的局限。目前遗传算法的欺骗问题研究主要集中在三个方面：a)设计欺骗函数，如Goldberg曾设计一个离散遗传算法的最小欺骗问题。b)修改遗传算法以解决欺骗函数的影响，如黄炎等人提出一种基于可调变异算子求解遗传算法中欺骗问题的方法，即在遗传搜索过程中通过改变变异算子的方向和概率求解遗传算法的欺骗问题。该方法能够在消除遗传算法中欺骗性条件的同时保持群体的多样性，使遗传算法可以顺利地收敛到全局最优解。c)理解欺骗函数对遗传算法的影响，何军等人讨论了一类遗传算法求解完全欺骗性问题的平均计算时间。

3 遗传算法的改进

目前在遗传算法的应用中，最突出的问题是局部搜索能力差和容易出现早熟

现象。近年来，众多学者围绕这两个核心问题发表了大量有价值的学术论文，从各方面对遗传算法进行了改进。

1) 遗传算子的改进

在遗传算子方面，夏虎等人[7]提出了一种考虑环境作用的协同免疫遗传算法，在该算法中，设计了克隆环境演化算子和自适应探索算子，并构造了三个子种群协同进化来发挥克隆环境演化算子的作用，从而提高了算法的全局搜索能力。蔡良伟等人[8]提出一种改进的交叉操作，根据种群的多样性和个体的相关性选择不同的交叉策略以减少无效的交叉操作，从而提高了交叉操作的效率并改善了算法的收敛性能。江雷等人[9]提出的基于并行遗传算法求解TSP对遗传算法的杂交算子进行改进，探讨了使用弹性策略来维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。

2) 多种群遗传算法

一些学者提出了基于多种群的遗传算法，将一个大的种群分成多个小的种群，每个小种群独立地进行进化，进化一定代数后进行种群间的通信。由于这种方式可以采用并行计算的模式,取得了较好的效果。贺新等人介绍了一种基于新的变异算子多种群的新遗传算法，该算法引入一种基于主群、附属子群的结构，可避免传统遗传算法难以克服的早熟收敛问题。叶在福等人引入多种群，对不同种群赋予不同的控制参数,实现不同的搜索目的，通过移民算子联系各种群，通过人工选择算子保存各种群每个进化代中的最优个体，对遗传算法的早熟现象有了很大的改进。

3) 与其他智能算法结合

遗传算法的全局搜索能力较强,能较快地确定全局最优点，但局部搜索能力较弱，进一步精确求解要耗费很长时间。因此,将局部搜索能力强的算法与遗传算法结合可以相互取长补短。任子武等人[10]将遗传算法与粒子群优化方法相结合，采用混沌序列产生初始种群、非线性排序选择、多个交叉后代竞争择优和变异尺度自适应变化等改进遗传操作,并通过精英个体保留、粒子群优化及改进遗传算法（IGA）三种策略共同作用产生种群新个体，以克服常规算法中收敛速度慢、早熟及局部收敛等缺陷。此外，还有遗传算法与模拟退火算法相结合、遗传算法与单纯形法相结合、遗传算法与神经网络相结合、遗传算法与模糊集相结合、

遗传算法与爬山法和梯度法等局部搜索算法相结合、遗传算法与小生境技术结合、将量子计算与遗传算法相结合形成量子遗传算法、在遗传算法中加入免疫算子构成免疫进化算法等。这些混合策略不但提高了算法的性能,还扩展了算法的应用领域。

4 遗传算法的应用

进入 90 年代后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。如工程结构优化、计算数学、制造系统、航空航天、交通、计算机科学、通信、电子学、材料科学等。目前遗传算法所涉及的主要应用领域如下表4.1所示：

表4. 1遗传算法的主要应用领域

应用领域 自适应控制 工业优化控制 规划设计 模糊识别 组合优化 函数优化 图像处理 信号处理 机器学习 机器人 人工生命 遗传编码 神经网络 应用实例 导弹控制 瓦斯管道控制 生产规划、并行机任务分配、网络设计 模糊聚类 TSP问题、背包问题、车间调度、图划分问题 经典应用领域、用于遗传算法自身的研究 特征提取 滤波器设计 知识获取、知识优化 机器人智能控制 生命的遗传进化 遗传程序设计 学习算法的改进 结束语

遗传算法的研究归纳起来可分为理论与技术研究和应用研究两个方面。可以说，遗传算法的应用已经渗透到了各个领域。但目前遗传算法的算法分析和理论分析还没有跟上，还有很多富有挑战性的课题亟待完善与解决，主要有算法规模小、GA编码问题、GA控制参数选择问题、“早熟”收敛与局部搜索能力差问题等问题，对这些问题的深入研究将会大大增进遗传算法理论与应用的发展。

参考文献

[1]吴玫,陆金桂.遗传算法的研究进展综述[J].机床与液压.2008,36(3):176-179. [2]田延硕.遗传算法的研究与应用[D].电子科技大学,2004. [3]梁芳.遗传算法的改进及其应用[D].武汉理工大学,2008.

[4]边霞,米良.遗传算法理论及其应用研究进展[J].计算机应用研究,2010,27(07):2425-2429+2434.

[5]葛继科,邱玉辉,吴春明等.遗传算法研究综述[J].计算机应用研究,2008,25(10):2911-2916.

[6]唐文艳.结构优化中的遗传算法研究和应用[D].大连理工大学,2002.

[7]夏虎,庄健,王立忠,等.一种考虑环境作用的协同免疫遗传算法[J].西安交通大学学报,2009,43(11):80-84.

[8]蔡良伟,李霞.遗传算法交叉操作的改进[J].系统工程与电子技术,2006,28(6):925-928.

[9]江雷.基于并行遗传算法的弹性TSP研究[J].微电子学与计算机,2005,22(8):130-134.

[10]任子武,伞冶.实数遗传算法的改进及性能研究[J].电子学

报,2007,35(2):269-274.

[11] Vasconcelos. J. A.，Ramirez. J. A., Takahashi. R. H. C. and Saldanha.R.

R..Improvements in Genetic Algorithms. IEEE Trans. Magnetics. 2001,37(5): 3414-3417

[12] Talbi H, Draa A, Batouche M. A new quantum-inspired genetic algorithm for

solving the traveling salesman Problem[C].Industrial Conference on Volume. 2004,(3):1192—1197.