3.2　遗传算法

遗传算法是基于自然选择理论的宏启发式算法，它利用交叉、变异等算子来生成或搜索种群中更高质量的解以试图确定最优解决方案[1-3]。

3.2.1　遗传表达与编码

John Holland最早提出的遗传算法种群个体表示方式是一串比特。该比特串称为染色体，每个比特称为基因，这两个术语都直接来自遗传学。

种群由一组染色体组成，每个染色体都由基因组成。染色体通常代表群体中的一个完整的“个体”，换句话说，代表一个完整的解决方案或一个分类，也有可能将染色体组合在一起形成生物，这更接近真实的遗传学，因为现实世界中的每个个体都有许多染色体。人们采用Holland的方法，用染色体代表一个完整的个体。

染色体中的每个基因都代表个体遗传构成的某个方面。例如，基因可以是完全独立的，代表动物体内某些身体部位的存在。更常见的是，基因以不太透明的方式组合在一起。例如，人们将看到遗传算法如何用于解决数学问题，其中染色体的位通常被视为代表问题解决方案的二进制数位。

3.2.2　简单遗传算法

遗传算法的步骤如下。

（1）生成随机的染色体群（这是第一代）。

（2）如果满足终止标准，就停止；否则，继续执行步骤（3）。

（3）确定每条染色体的适应度。

（4）对本代染色体进行交叉和突变，产生下一代新的染色体群。

（5）返回步骤（2）。

种群规模应提前确定。通常情况下，种群规模从一代到下一代都保持不变。在某些情况下，种群规模发生变化是很有用的。

一般每个染色体的大小保持相同。运行染色体大小可变的遗传算法是合理的，但通常不这么做，应该在每一代中选择适应度较高的染色体以彼此配对，产生两个后代。由此产生的一组后代染色体取代了上一代，也有可能允许特别健康的父代生产相对较多的后代，并允许某一代的某些成员生存到下一代。

1.适应度

在传统的遗传算法中，需要一个度量标准来客观地确定染色体的适应度。例如，在使用遗传算法将数字顺序排序时，可以通过运行该算法并计算其放置在正确位置的数字数量来确定合适的适应度。通过测量每个错误放置的数字与正确位置之间的距离，可以获得更复杂的适应度。

2.交叉操作

交叉操作应用于两条长度相同的染色体。

（1）选择一个随机交叉点。

（2）将每条染色体分成两部分，在交叉点处分裂。

（3）通过将一条染色体的前部与另一条的后部相结合来重新组合断裂的染色体，反之亦然，从而产生两条新的染色体。

例如，考虑以下两条染色体。

可以在第六和第七基因之间选择交叉点。

现在染色体重组的部分如下。

这一过程基于DNA链在人类繁殖过程中相互重组的方式，即子代结合父代的特征。单点交叉是最常用的形式，但也可以使用具有两个或更多交叉位置的交叉。

在两点交叉中，选择两个点将染色体分成两个部分：外侧部分和内侧部分。外侧部分被认为连接在一起以将染色体变成环。交叉时两个部分相互交换，如图3-9所示。

在均匀交叉中，概率p用于确定子代是使用来自父代1的给定位还是来自父代2的给定位。换句话说，一个子代可以从它的父代那里随机接收任意的比特。例如，假设有以下两个父代。

父代1：10001101

父代2：00110110

可以确定这两条染色体的后代，如图3-10所示。其中，来自父代1的基因以灰色阴影显示，而来自父代2的基因没有阴影。

第一个子代的第一个比特来自父代1的概率为p，来自父代2的概率为1-p。如果子1选择了来自父代1的比特，则子2选择来自父代2的相应比特；反之亦然。与传统的单点或双点交叉每对父代产生两个后代不同，均匀交叉通常用于从一对父代产生一个后代。

均匀交叉确实会将基因库中的基因大量混合在一起，在某些情况下，使用非常高（或非常低）的p值是非常明智的，这样可以确保大多数基因来自一方父代（或另一方）。在某些情况下，可以采用克隆的方法，从而从根本上不应用交叉，并且产生与其单亲相同的新后代。

3.突变操作

遗传算法与人们惯常使用的爬山法非常相似。爬山法包括产生一个可能的问题解决方案，并朝着比目前更好的解决方案前进，直到找不到一个更好的解决方案为止。在有局部最大值的情况下，爬山算法表现不好。为了使遗传算法避免这个问题，引入了变异算子。变异算子是一元运算符（只应用于一个参数——单个基因），通常以较低的概率应用变异算子，如0.01或0.001。突变只涉及逆转染色体中位的值。例如，当突变率为0.01时，100个基因的染色体中的一个基因可能被逆转。下面可以看到应用于上述例子中的一个后代的突变。

4.终止准则

遗传算法有两种终止运行的方式：通常，对进化次数有一个限制，在这之后运行终止；对于一些问题，当使用特定解决方案得到结果时，或者当群体中的最高适应度达到特定值时，运行终止。在3.2.3节中将看到如何用遗传算法求解数学函数。在这种情况下，很明显，当达到正确的解决方案时，运行终止，这很容易进行测试。

3.2.3　应用实例：数学函数优化

下面介绍如何使用遗传算法来找到数学函数的最大值，我们尝试找到以下函数的最大值。

其中，x是以弧度表示的，x取值为0～15。每个染色体使用4位表示x的可能值。图3-11给出了此函数的散点图。

下面使用有4个染色体的群体。第一步是生成随机种群，这是第一代。

要计算染色体的适应度，需要先将其转换为十进制整数，然后计算这个整数的f（x）值。

将适应度指定为0～100，其中0表示最不适合，100表示最适合。

f（x）生成-1～1的实数。指定f（x）=1时的适应度为100，f（x）=-1时的适应度为0，50的适应度将被指定为f（x）=0。因此，x的适应度定义为

染色体的适应度比例是染色体的适应度占总适应度的百分比，下面将看到为什么这是一个有用的计算。表3-2所示为用于计算第一代适应度的计算结果。现在需要运行遗传算法来生成下一代，第一步是选择将要复制的染色体，轮盘法使用适应度比率随机选择染色体进行复制，具体如下。

从0到100给染色体按比例分配每个染色体的适应度。因此，在第一代中，c1将具有46.3%的范围（从0到46.3），c2将具有37.4%的范围（从46.3到83.7），以此类推。

现在生成一个0～100的随机数。该数字将落在一条染色体的范围内，然后选择该染色体用于繁殖，下一个随机数用于选择该染色体的配偶。因此，适应度高的染色体往往比适应度低的染色体产生更多的后代。

重要的是：这种方法不会阻止适应度低的染色体的繁殖，因为这有助于确保种群不会因同一父代不断繁殖而停滞不前。

然而，在上述例子中，染色体c4将不太可能再现，因为只有当随机数落在98.6～100时才会出现这种情况。

需要生成4个随机数来找到将要产生下一代的4个父代。第一个随机数是56.7，这意味着c2被选为第一个父代。然后38.2被选择，所以它的配偶是c1。

现在需要结合c1和c2来产生两个新的后代。首先，需要随机选择一个交叉点，将选择第二位和第三位（基因）之间的点。

现在用交叉产生两个后代：c5和c6。

以类似的方式，c1和c3被选择来产生后代c7和c8，使用第三位和第四位之间的交叉点。

现在，第一代种群c1到c4被第二代种群c5到c8取代。c4没有机会繁殖，因此其基因将丢失。

c1是第一代中最适合的染色体，能够繁殖两次，从而将其高度适合的基因传递给下一代的所有成员。

第二代的适应度值如表3-3所示。

这一代产生了两条非常合适的染色体和两条非常不合适的染色体。事实上，其中一条染色体c7是最优解。此时，终止标准可能会确定运行是否可以停止；否则，算法将继续运行，但找不到更好的解决方案。从随机配置到最优解决方案只需要一步即可完成。

显然，这是一个非常简单的例子，实际问题可能更难解决。它们可能涉及更大的种群规模（通常种群规模为100～500），染色体可能包含更多的比特。在许多情况下，遗传算法可以快速地对组合问题产生最优或接近最优的解。