遗传算法浅析

[摘要]采用二进制编码的方法建立初始种群，并设计了适应度函数，利用排序法来选择算子及简单的单点交叉来对所构建的初始种群进行计算，详细阐述了遗传算法的编程和运算过程。

[关键词]遗传算法 二进制编码 适应度函数

1 算法理论

遗传算法的基本运算过程如下：

（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。（2）个体评价：计算群体P（t）中各个个体的适应度。（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t+1）。（6）终止条件判断：若t=T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

1.1 编码以及初始种群的产生

遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作（问题的）表示（representation）。二进制编码是目前遗传算法中最常用的编码方法，即由二进制字符集{0，1}产生通常的0，1字符串来表示问题空间的候选解。它具有以下特点：（1）简单易行；（2）符合最小字符集编码原则；（3）便于用模式定理进行分析。本文中，编码采用二进制编码，初始种群采用矩阵的形式，每一行表示一个染色体，每一个染色体由若干个基因位组成。关于染色体的长度（即基因位的个数）可根据具体情况而定。比如说根据要求极值的函数的情况，本文的染色体长度为6，前5个二进制构成该染色体的值（十进制），第6个表示该染色体的适应度值。长度越长，表示解空间搜索范围越大。文后的C代码中函数x即为转换函数。

初始种群结构如下图所示：

该初始种群共有4个染色体，第一列表示各个染色体的编号，第2列表示该染色体值的正负号，0表示正，1表示负。第3列到第7列为二进制编码，第8列表示各个染色体的适应度值。第2列到第7列的0-1值都是随机产生的。

1.2 适应度函数的设计

遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。由于遗传算法在进化搜索中基本不利用外部信息，因此适应度函数的设计要尽量简单且主要满足以下条件：（1）单值、连续、非负、最大化；（2） 合理、一致性；（3）计算量小；（4）通用性强。一般情况下，染色体（也叫个体，或一个解）的适应度函数为目标函数的线性组合。本文直接以目标函数作为适应度函数：f（x）=-x2+5，即每个染色体的适应度值就是它的目标函数值。

1.3 选择算子

初始种群产生后，要从种群中选出若干个体进行交叉、变异，那么如何选择这些个体呢？选择方法就叫做选择算子。一般有赌选择法、锦标赛选择法、排序法等。本文采用排序法来选择，即每次选择都选出适应度最高的两个个体。那么执行一次选择操作后，得到的新种群的一部分为下图所示：

1.4 交叉算子

那么接下来就要对新种群中选出的两个个体进行交叉操作，所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。一般的交叉方法有单点交叉、两点交叉、多点交叉、均匀交叉、融合交叉。方法不同，效果不同。本文采用最简单的单点交叉。交叉点随机产生。但是交叉操作要在一定的概率下进行，这个概率称为交叉率，一般设置为0.5到0.95之间。交叉后产生的新个体组成的新种群如下：

注：黑体字表示子代染色体继承母代个体的基因情况。

1.5 变异

变异就是对染色体的结构进行变异，使其改变原来的结构（值也就改变），达到突变进化的目的。变异操作也要遵从一定的概率来进行，一般设置为0到0.5之间。本文的变异方法直接采取基因位反转变异法，即0变为1，1变为0。要进行变异的基因位的选取也是随机的。

1.6 终止规则

一般常用的终止规则有：若干代后终止，得到的解达到一定目标后终止，计算时间达到一定限度后终止等方法。本文采用迭代数来限制。

2 结论

对于人们构造出的各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等，遗传算法可以方便的得到较好的结果。然而遗传算法通常的效率比其他传统的优化方法低，而且容易过早收敛，另外，遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

参考文献：

[1]陈国良等.遗传算法及其应用[M].北京：人民邮电出版社，1996.

[2]刘英.遗传算法中适应度函数的研究[J].兰州工业高等专科学院学报，2006，（9）.