第3章 遗传算法原理与实现

3.1 遗传算法的基本概念

简单而言，遗传算法使用群体搜索技术，将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代的种群，并逐步使种群进化到包含近似最优解的状态。由于遗传算法是自然遗传学与计算机科学相互渗透而形成的计算方法，所以遗传算法中经常会使用遗传学中一些有关自然进化的基础术语^[1]，其对应关系如表3.1所示。

表3.1 遗传学与遗传算法术语对应关系

群体和个体

群体是生物进化过程中的一个集团，表示可行解集。

个体是组成群体的单个生物体，表示可行解。

染色体和基因

染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。

基因是控制生物体某种性状（即遗传信息）的基本单位，表示可行解编码的分量。

遗传编码

遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码、十进制编码（实数编码）等。

二进制编码

这里举例说明二进制编码的原理和实现。例如求实数区间[0，4]上函数f(x)的最大值，传统的方法是不断调整自变量x本身的值，直到获得函数最大值。遗传算法则不对参数本身进行调整，而是首先将参数进行编码，形成位串，再对位串进行进化操作。在这里，假设使用二进制编码形式，可以由长度为6的位串表示变量x，即从“000000”到“111111”，并将中间的取值映射到实数区间[0，4]内。由于从整数上来看，6位长度的二进制编码位串可以表示0～63，所以对应[0，4]的区间，每个相邻值之间的阶跃值为4/63≈0.0635，这个就是编码精度。一般来说，编码精度越高，所得到的解的质量也越高，意味着解更为优良；但同时，由于遗传操作所需的计算量也更大，算法的耗时将更长。因而在解决实际问题时，编码位数需要适当选择。

实数编码

基于二进制编码的个体尽管操作方便，计算简单，但也存在着一些难以克服的困难而无法满足所有问题的要求。例如，对于高维、连续优化问题，由于从一个连续量离散化为一个二进制量本身就存在误差，使得算法很难求得精确解。而要提高解的精度又必须加长编码串的长度，造成解空间扩大，算法效率下降。同时，二进制编码也不利于反映所求问题的特定知识，对问题信息和知识利用得不充分也会阻碍算法效率的进一步提高。为了解决二进制编码产生的问题，人们在解决一些数值优化问题（尤其是高维、连续优化问题）时，经常采用实数编码方式。实数编码的优点是计算精确度高，便于和经典连续优化算法结合，适用于数值优化问题；但其缺点是适用范围有限，只能用于连续变量问题。

适应度

适应度即生物群体中个体适应生存环境的能力。在遗传算法中用来评价个体优劣的数学函数，称为个体的适应度函数。

遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有：目标函数映射成适应度函数、基于序的适应度函数等。

遗传操作

遗传操作是优选强势个体的“选择”、个体间交换基因产生新个体的“交叉”、个体基因信息突变而产生新个体的“变异”这三种变换的统称。在生物进化过程中，一个群体中生物特性的保持是通过遗传来继承的。生物的遗传主要是通过选择、交叉、变异三个过程把当前父代群体的遗传信息遗传给下一代（子代）成员。与此对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子来实现，即选择算子、交叉算子、变异算子。