基本遗传算法：优化搜索策略

基本的遗传算法（或称标准的遗传算法）由初始化、选择、交叉和变异四个部分组成，其流程如图9.2.1所示。

图9.2.1　遗传算法的基本流程

先把待寻优的参数或变量表示成“染色体串”（一般是用二进制码串表示），染色体中的基因是最基本的单位，用一个二进制码表示。有遗传特性的基因串，称为基因型。染色体即由这些基因型组成。每个染色体所代表的生物体的性状（即搜索空间的参数或解）称为染色体的表现型。所以在使用遗传算法时，要进行两个基本的数据转换操作：一个是从表现型到基因型的转换，此过程又称为编码（coding）；另一个是从基因型到表现型的转换，此过程又称为译码（decoding）。

每一基因型有相应的适应度（fitness），表示该基因型生存与复制（reproduction）的能力，适应度fi越大的染色体，复制下一代种群数（染色体个数）越多（表示“适者生存”）。在下一代染色体种群中，还要进行基因型之间的交换（crossover，又称杂交），并在某个基因型的某个或某几个位置上进行代码的突变（mutation，又称变异）。这样就得到交换和变异以后的下一代染色体种群。然后再进行适应度计算，若收敛于最优解，遗传计算便结束，输出最优解，否则继续复制、交换和变异，再进行迭代计算，直到求得最优解为止。

为了更清楚地说明上述过程的细节，我们举一实例。设需要求解的问题是：当自变量x在0～31之间取整数时，寻找函数f（x）=-x2+31x+10的最大值。若要用枚举方法来求解，则要比较x从0至31的所有值，尽管此法是可靠的，但这是一种效率很低的方法。而若要做到小数点后若干位，枚举法甚至由于计算工作量过大而成为不可能，下面我们运用遗传算法来求解这个问题。

1.编码（决定初始化种群）

其目的是将寻求优化解的参数用若干代码串来表示。这种代码串就称为染色体，这个过程便称为编码。编码的方法很多，最简单的办法就是用二进制代码来编码。编码的基本要求是要为染色体的基因型（代码串）和表现型（参数值）建立对应关系，采用二进制代码时，这种对应关系就是二进制数与十进制数的转换关系。在本例中，x值在0～31之间变化，所以有5位二进制代码串就可组成所有染色体的基因型，即所有的染色体基因型在00000～11111之间，接下来是要选择初始染色体种群的个体数及个体的具体基因型。一般种群的个体数要适中，太少了可能迭代次数要增加，甚至得不到结果；太大了会增加很多计算工作量，降低效率。在本例中，我们设种群大小为4，即有4个个体。基因型的选取是随机的，一般在x值的定义域中较均匀地随机分布，我们在本例中随机取4个x值：1，28，8，19。相对应的4个基因型为

00001

11100

01000

10011

这样便完成了遗传算法的准备工作，产生了初始染色体种群的基因型。

2.计算适应度

决定适应度fi的计算公式是一个技巧性很高，但理论研究又很不充分的复杂问题。一般要根据优化的目标函数来决定。在本例中，选择求解最大值的函数f（x）=-x2+31x+10来作适应度fi的计算公式。对应所选的4个个体，计算出的适应度fi的值分别是：40，94，194，238，如表9.2.1所示。

表9.2.1　复制操作之前的各项数据

3.复制

按照达尔文的适者生存理论，越能适应环境的生物品种，越能繁衍（复制）其后代，而不适应环境的生物，其生存和繁衍能力则较低，甚至被淘汰。在本例中，初始种群的适应度fi已计算出来。复制的原则是：适应度fi越高的染色体，其复制的可能及复制的个数越多。具体的计算是利用随机方法来实现的。首先按式（9.2.1）来计算复制概率为

再用式（9.2.2）来计算期望的复制个数为(www.xing528.com)

式中：是fi的期望值（平均值）。

根据四舍五入的规则，将圆整为整数Ri。本例经过上述步骤后所得的结果为：串1被淘汰掉，串2被复制一次，串3被复制一次，而串4则被复制了两次。复制后的新种群的4个染色体基因型如表9.2.2所示。

4.交换

交换分两个步骤。第一步是选择两两匹配的对象，通常是随机选取的。在本例中，选择新串号1与4匹配，新串号2与3匹配，这样选取是为了避免让新串号3与4匹配（因为两者的基因型相同，这对交换操作没有实际意义）。第二步是决定交换点及交换规则。在遗传算法中，对此步骤的研究也不多，现在一般还是随机选取。例如在本例中，新串1与4的交换点选在左起第3位，交换规则是第3位以后的2位代码交换；新串2与3的交换点选在左起第2位，交换规则是第2位以后的3位代码交换，具体过程如下：

这样就得到了新种群的4个染色体基因型，如表9.2.2所示。

表9.2.2　复制操作之后的各项数据

5.变异

变异是生物体中某一个或某几个基因位变化，这种概率是很小的，在自然选择中，通常是千分之几或百分之几。在人工选择中，为了得到某个新品种，有时人为改变某几个基因，而造成转基因物种。在遗传算法中，变异就是随机选取的串位的代码由1变成0或由0变成1。变异操作可以防止染色体中丢失一些有用的遗传因子，保证物种基因型的多样性。在本例中，若变异概率取为0.001，则对于种群的总共20个基因位（4个个体，每个个体有5位，所以总共有20位），期望的变异位数为20×0.001=0.02（位），所以本例无变异位。

6.迭代

经过复制、交换、变异操作后得到新一代种群的基因型，对此种群再进行适应度计算，这一过程称为迭代。根据新一代个体的适应度值，按照预先确定的评判规则来估计是否已得到最优解，通常使用的评判规则如下：

式中：是两次迭代的相对误差；分别为第k次迭代和第k+1次迭代时各染色体的最大适应度（从k=0开始）；ε是给定的评判标准（一般取百分之一到千分之一）。若相对误差小于给定的标准，则遗传算法结束，输出最优解；否则继续进行复制、交换和变异。

在本例中，第一次迭代的最大适应度=250，初始种群的最大适应度=238，由此计算出两代种群最大适应度的相对误差为

若选择ε=0.01，则判定遗传算法还要继续进行。第一次迭代以后进行复制及交换操作的计算结果如表9.2.3所示。由此表可知，在这一次得到的新种群中，已有两个染色体基因型保持未变，其适应度仍为250。这就是说，本次计算的最大适应度与上次相同，相对误差为0，遗传算法便结束，所得的最优解是：x=16，f（x）=250。由此例可见，仅通过一次迭代便得到结果，遗传算法的效率是很高的。

表9.2.3　第一次迭代以后的各项数据

从数学分析可知，函数f（x）=-x2+31x+10的极值点为x=15.5，最大函数值为max（f（x））=250.25。可见用遗传算法计算的结果也是很精确的。