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

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

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

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 遗传算法的改进

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