9.1　遗传算法的基本原理

遗传算法的基本思想是基于达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传学说。关于生物的进化，达尔文的进化论认为：生物是通过进化演化而来的。在进化过程中，每一步由随机产生的前辈到自身的产生都足够简单。但生物从初始点到最终产物的整个过程并不简单，而是通过一步一步的演变构成了绝非是一个纯机遇的复杂过程。整个演变过程由每一步的幸存者控制，每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新特征。在环境变化时，只有那些能适应环境的个体方能保留下来。孟德尔遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在于细胞中，并以基因形式包含在染色体内，每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过优胜劣汰，适应性高的基因结构得以保存下来。

20世纪70年代初，美国Michigen大学的Holland教授受到达尔文进化论的启发，并将其用于机器的研究中，后来发展成为一个新的研究领域即遗传算法。它通过模拟生物进化过程来搜索问题的解。遗传算法中的生物群体为采用特殊编码技术编码为“串”即染色体的问题的解；进化即是对算法所产生的每个染色体进行评价，并基于一个适合的值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会；自然进化过程中的“适者生存”选择规律在遗传算法中就是有效地利用已有的信息去搜索那些有希望改善质量的串。

遗传算法是对自然界的有效类比，并从自然界现象中抽象出来，所以它的生物学概念与相应生物学中的概念不一定等同，而只是生物学概念的简单“代用”。

下面介绍遗传算法的基本概念。

1．名词解释

个体（individual）：GA所处理的基本对象、结构。

群体（population）：个体的集合称为种群体，该集合内个体的数量称为群体的大小。例如，如果个体的长度是100，适应度函数变量的个数为3，就可以将这个种群表示为一个100×3的矩阵。相同的个体在种群中可以出现不止一次。每一次迭代，遗传算法都对当前种群执行一系列的计算，产生一个新的种群。每一个后继的种群称为新的一代。

串（bit string）：个体的表现形式，对应于生物界的染色体。在算法中其形式可以是二进制的，也可以是实值型的。

基因（gene）：串中的元素，用于表示串中个体的特征。例如有一个串S_二进制＝1011，则其中的1、0、1、1这4个元素分别称为基因，它们的值称为等位基因（alletes）。一个个体的适应度函数值就是它的得分或评价。

基因位置（gene position）：一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S_二进制＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点（locus）。

基因特征值（gene feature）：在用串表示整数时，基因的特征值与二进制数的权一致。例如在串S＝1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

串结构空间（bit string space）：在串中，基因任意组合所构成的串的集合，基因操作是在串结构空间中进行的。串结构空间对应于遗传学中的基因型（genotype）的集合。

参数空间（parameters space）：这是串空间在物理系统中的映射，它对应于遗传学中的表现型（Phenotype）的集合。

适应度及适应度函数（fitness）：表示某一个体对于生存环境的适应程度，其值越大，即对生存环境适应程度较高的物种将获得更多的繁殖机会；反之，其繁殖机会相对较少，甚至逐渐灭绝。适应度函数则是优化目标函数。

多样性或差异（diversity）：一个种群中各个个体间的平均距离。若平均距离大，则种群具有高的多样性；否则，其多样性低。多样性是遗传算法必不可少的本质属性，它能使遗传算法搜索一个比较大的解的空间区域。

父辈和子辈：为了生成下一代，遗传算法在当前种群中选择某些个体（称为父辈），并且使用它们来生成下一代中的个体（称为子辈）。典型情况下，算法更可能选择那些具有较佳适应度函数值的父辈。

遗传算子：遗传算法中的算法规则，主要有选择算子、交叉算子和变异算子。

2．遗传算法的基本原理

遗传算法把问题的解表示成“染色体”，也即以二进制或浮点数编码表示的串。然后给出一群“染色体”即初始种群，也就是假设解集，把这些假设解置于问题的“环境”中，并按适者生存和优胜劣汰的原则，从中选择出较适应环境的“染色体”进行复制、交叉、变异等过程，产生更适应环境的新一代“染色体”群。这样，一代代地进化，最后收敛到最适应环境的一个“染色体”上，经过解码，就得到问题的近似最优解。

基本遗传算法的数学模型可表示为

GA＝F（C，E，P₀，M，φ，Γ，ψ，T）

其中，C为个体的编码方法；E为个体适应度评价函数；P₀为初始种群；M为种群大小；φ为选择算子；Γ为交叉算子；ψ为变异算子；T为遗传运算终止条件。

遗传算法的具体步骤如下：

①对问题进行编码；

②定义适应度函数后，生成初始化群体；

③对于得到的群体进行选择、复制、交叉、变异操作，生成下一代种群；

④判断算法是否满足停止准则，若不满足，则从步骤③起重复；

⑤算法结束，获得最优解。

整个操作过程可用图9.1来表示。

图9.1　GA流程图

3．遗传算法的优点

遗传算法从数学角度讲是一种概率性搜索算法，从工程角度讲是一种自适应的迭代寻优过程。与其他方法相比，它具有以下的优点：

编码性：GA处理的对象不是参数本身，而是对参数集进行了编码的个体，遗传信息存储在其中。通过在编码集上的操作，GA因而不受函数条件的约束，使得具有广泛的应用领域，适用于处理各类非线性问题，并能有效地解决传统方法不能解决的某些复杂问题。

多解性和全局优化性：GA是多点、多途径搜索寻优，且各路径之间有信息交换，因此能以很大的概率找到全局最优解或近似全局最优解，并且每次能得到多个近似解。

自适应性：GA具有潜在的学习能力，利用适应度函数，能把搜索空间集中于解空间中期望值最高的部分，自动挖掘出较好的目标区域，适用于具有自组织、自适应和自学习的系统。

不确定性：GA在选择、杂交和变异操作时，采用概率规则而不是确定性规则来指导搜索过程向适应度函数值逐步改善的搜索区域发展，克服了随机优化方法的盲目性，只需较少的计算量就能找到问题的近似全局最优解。

隐含并行性：对于n个群体的GA来说，每迭代一次实际上隐含能处理o（n³）个群体，这使GA能利用较少的群体来搜索可行域中较大的区域，从而只需以较少的代价就能找到问题的全局近似解。

智能性：遗传算法在确定了编码方案、适应值函数及遗传算子之后，利用进化过程中获得的信息自行组织搜索。这种自组织和自适应的特征赋予了它能根据环境的变化自动发现环境的特征和规律，消除了传统算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并说明针对问题的不同，算法应采取的措施。于是利用遗传算法可以解决那些结构尚无人能理解的复杂问题。