遗传算法综述

金玲，刘晓丽，李鹏飞，王妍

华北理工大学冀唐学院

遗传算法综述

金玲，刘晓丽，李鹏飞，王妍

华北理工大学冀唐学院

本文对遗传算法的基本概念、运算过程和特点做了概述，并在此基础上分析了遗传算法的现状及前景。

遗传算法；生物进化；最优化

1.引言

遗传算法仿效自然选择下的生物进化,是一种仿生物进化过程的随机化搜索方法,该算法通过有限的代价来解决搜索和优化问题，由于其随机性和非线性为其他科学技术无法或难以解决的问题提供了新的模型，这与传统的搜索和优化方法不同。

2.基本概念

遗传算法是仿照自然界适者生存优胜劣汰的进化规律得到的一种随机化搜索方法。对于优化问题要求一个求函数的最大值，可以用下面的数学规划模型来进行描述:

其中(1)式作为目标函数，X是决策变量，(2)式、(3)式作为约束条件，R是基本空间U的子集。可行解X是指满足约束条件的解，可行解集合R是指满足约束条件的解所组成的集合。

3.遗传算法定义

遗传算法是从一个种群开始的，对于数学规划模型就是从可行解集合开始的。染色体作为遗传物质的主要载体，种群中一定数目的个体都是经过基因编码得到的，个体的基因型决定了这个个体的表现型，我们需要通过编码实现从表现型到基因型的映射，由于生物体内基因编码的工作是非常复杂的，所以我们要做一下必要的简化例如二进制编码。根据适者生存优胜劣汰的遗传规律，首先要确定初代种群，在每一代的种群迭代中再按照个体的适应度函数以及进行交叉、变异算子的运算选出较优的个体，进入下一代的演化从而逐代产生出一个最优的种群。在逐代演化的过程中，种群的适应能力越来越强，最后通过对末代种群中最优个体进行解码就可以得到数学规划模型的近似最优解。

4.遗传算法的特点

遗传算法可以很好的解决搜索问题，具有以下几方面的特点：

(1)遗传算法是从一个种群开始同时处理种群中的每个个体而不是单个个体，这是遗传算法与传统优化算法的最大区别。遗传算法是从数学规划模型的解集开始进行嫂索，同时评估搜索空间中的多个解而不是单个解。传统优化算法是从单个解开始迭代求最优解常常会陷入局部最优解，而遗传算法不仅减少了这种风险而且易于实现并行化。

(2)遗传算法对个体的评估只要借助适应度函数就可以完成，几乎不需要搜索空间的知识或其它辅助信息。而适应度函数的定义域可以任意设定且不会受到连续可微的限制，那么这很大程度上扩展了遗传算法的应用范围。

(3)遗传算法的搜索方向是由概率的变迁规则来引导，而不是确定性规则。

(4)遗传算法在逐代演化的过程中通过得到的信息自行组织搜索时，硬度较大的个体相应的生存概率也较高并且他获得的基因结构也更适应环境。遗传算法具有自适应性、自组织性和自学习性。

5.运算过程

为实现优胜劣汰的进化过程就需要根据环境适应度对群体中的个体施加一定的操作，使模型的解在优化搜索的角度逐代优化并逼近最优解，这就是模拟生物基因遗传的遗传操作，包括选择、交叉、变异三个基本遗传算子，具有如下特点:

(1)选择算子。选择是在个体适应度评估的基础上从群体中选择优胜淘汰劣质个体的操作，其目的是将较优的个体遗传到下一代，较优的个体可能是直接遗传到下一代的也可能是通过配对交叉产生新个体再遗传到下一代的。目前常用的选择算子有随机遍历抽样法、适应度比例方法、局部选择法等。

(2)交叉算子。交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，交叉算子期望将有益基因组合在一起，对种群中的两个个体根据交叉率随机交换某些基因产生新的基因组合。生物进化过程中遗传基因重组发挥了主要作用，交叉算子在遗传算法中的地位就等同于基因重组，交叉算子很大程度上提高了遗传算法的搜索能力。

(3)变异算子。变异算子是指改变群体中个体串的某些基因座上的基因值。变异算子使遗传算法具有局部的随机搜索能力，这种局部随机搜索能力在遗传算法通过交叉算子已接近最优解邻域时可以加速向最优解收敛。另外，变异算子还能防止遗传算法出现未成熟收敛现象从而维持群体多样性。

交叉算子可以提高遗传算法的全局搜索能力，而变异算子对提高遗传算法的局部搜索能力有帮助，交叉算子和变异算子之间既相互配合又相互竞争，也正因为如此遗传算法具有均衡的搜索能力。那么，交叉算子和变异算子如何有效地配合使用就成为目前遗传算法的一个重要研究内容。

(4)终止条件。当出现以下情况时算法终止：最优群体和个体的适应度不再上升；最优个体的适应度达到给定的阀值；迭代次数达到预设的代数，预设的代数一般为100-500代。

6.遗传算法的现状

进入90年代遗传算法在理论研究和应用研究方面都取得了很大的进展。遗传算法不但应用研究的领域扩大而且利用遗传算法解决优化和规则问题的能力也显著提高，同时对于产业应用方面的研究也在摸索之中。

由于遗传算法思想简单、易于实现在许多应用领域例取得了丰硕的成果与进展，例如如函数优化、组合优化、图像处理和模式识别、人工生命、生产调度问题、机器学习和自动控制等领域。对于遗传算法，我们应该从收敛性，编码方法，增强算子适应性，适应度函数进行更为深入的研究。

[1]遗传算法理论及应用.周明，孙树栋编著.国防工业出版社1999

[2]遗传算法：理论、应用与软件实现.王小平、曹立明著.西安交通大学出版社2002

[3]遗传算法的基本理论与应用.李敏强等著.科学出版社2002