用遗传算法解决问题的案例分析

为了对遗传算法求解优化问题的过程有一个较为清晰的认识，我们从一个具体的例子入手。

考虑下面的优化问题：

1.编码

为了用遗传算法求解该问题，首先需要将问题的解表示为二进制位串，在本例中，问题的解为一实数对（x1，x2）。所以，我们首先将每个变量编码为二进制位串，而位串的长度依赖于变量的变化区间和所要求的精度，然后将表示各个变量的二进制位串连接起来便得到问题解的一种表示，称为染色体。当遗传算法计算结束后，我们还需要一种从染色体得到各个变量值的方法。

设aj ≤xj ≤bj，所要求的精度为10-t。将区间[aj，bj]划分为至少（bj-aj）10t 个小区间，而每一个小区间用一个二进制数来表示。表示变量xj 所需要位串的长度mj 用式（2-2）确定：

由二进制位串到实数xj 的转换由式（2-3）确定：

式中，decimal（substringj）表示变量xj 的二进制数串substringj 所代表的十进制数。

对于上述的优化问题，假定所要求的精度为10-4，那么变量x1 和x2 所需要的位串长度m1、m2 的计算如下：

计算出变量x1 和x2 所需要的位串长度m1、m2 后，便可以得到表示问题解（x1，x2）的二进制位串长度m 为33（m=m1+m2），如图2-1所示。

图2-1　二进制位串长度

例如给定下列染色体：

图2-2　染色体与位串长度示意图

可以如下得到变量x1 和x2 的值。

表2-1　二进制数与十进制数对照关系表

2.产生初始群体

初始群体中染色体的个数M 是预先指定的，初始群体通常随机地产生。在本例中，假定M=10。初始群体由10个随机产生的、串长为33的二进制位串组成，假定随机产生的10个染色体如下：

这10个染色体所对应的问题解分别如下：

v1′=(x1,x2)=(-2.687 969,5.361 653),v2′=(x1,x2)=(0.474 101,4.170 144)

v3′=(x1,x2)=(10.419 457,4.661 461),v4′=(x1,x2)=(6.159 951,4.109 598)

v5′=(x1,x2)=(-2.301 286,4.777 282),v6′=(x1,x2)=(11.788 084,4.174 346)

v7′=(x1,x2)=(9.342 067,5.121 702),v8′=(x1,x2)=(-0.330 256,4.694 977)

v9′=(x1,x2)=(11.671 267,4.873 501),v10′=(x1,x2)=(11.446 273,4.171 908)

在遗传算法中，我们可以用如下说明的二维数组表示群体。

初始化过程如下所示：

3.设计适应度函数

在本例中，这是一个求最大值问题，所以我们直接取目标函数作为适应度函数。

计算每个染色体所表示个体的适应值的过程由下面两步组成：

（2）计算目标函数值f（xk）。

具体过程如下：

在上述的过程中，Power2 是一个一维数组，Power2[i]存储的是2i。变量Temp1 和Temp2分别记录当前染色体中表示变量x1 和x2 的二进制位串的十进制数。Eval是一个一维数组，Eval[i]存储第i个个体vi 的适应值。

用上述过程，我们可以计算出上述10个染色体的适应值如下：

从染色体的适应值可以看出，群体中个体v4 的适应值最大，v3 的适应值最小，这说明作为优化问题的最优解或近似最优解，v4′ = （6.159951，4.109598）最好，而v5′ =（-2.301286，4.777282）最差。

4.选择策略的确定

在遗传算法中，选择群体中的一些染色体作为父体，通过杂交或/和变异，使之产生后代。如何从群体中选择一些染色体是设计遗传算法的关键技术之一。根据达尔文进化论，适应值较大的个体存活下来的概率也较大，因而产生后代的概率也较大。有许多选择策略符合达尔文进化论。在本例中，我们采用轮盘赌选择。轮盘赌选择是最简单的选择策略之一，也是遗传算法中使用得最多的选择策略之一。

轮盘赌选择首先计算每个个体的选择概率，其步骤如下。

（1）计算群体中所有个体适应值之和：

（2）计算每个染色体的选择概率：

用上述过程可计算出群体中每个染色体的选择概率如下：

p1=0.111 180,p2=0.097 515,p3=0.053 839,p4=0.165 077,

p5=0.088 057,p6=0.066 806,p7=0.100 815,p8=0.794 234,

p9=0.148 211,p10=0.057 554

计算出每个染色体的选择概率后，如图2-3所示构造一个圆盘：将一个圆盘分为N 个扇形，其中第k 个扇形的中心角为2πpk。构造好圆盘后，选择过程共选择 N 个染色体，可进行如下操作：想象有一个指针指向第一个扇形和第N 个扇形的交界处，将圆盘按逆时针方向旋转M 次，每旋转1次，当圆盘停止旋转后，若指针指向第k 个扇形，则选择第k 个染色体。当指针指向第k 个扇形和第k+1个扇形的交界处时，则选择第k 个染色体。显然，若用转盘式选择策略，当某个体的适应值较大时，它被选择的概率也较大。

图2-3　圆盘示意图

轮盘赌选择过程的具体实现如下：

用上述轮盘赌选择过程，可以计算出群体中每一个染色体的累计概率如下：

q1=0.111 180,q2=0.208 695,q3=0.262 534,q4=0.427 611,

q5=0.515 668,q6=0.582 475,q7=0.683 290,q8=0.794 234,

q9=0.942 446,q10=1.000 000

现在将转盘旋转10次，假设从[0，1]中产生的10个随机数如下：

0.301　431　0.322 062　0.766 503　0.881 893　0.350 871

0.583　392　0.177 618　0.343 242　0.032 685　0.197 577

那么所选择的10个染色体如下：

5.遗传算子的设计(www.xing528.com)

遗传算子主要有两种：杂交算子和变异算子。

1）杂交算子

这里使用单点杂交。设表示问题解的二进制串长为L，该方法在1～（L-1）之间随机地选择一个杂交点，然后将两个父体在该杂交点右边的子串进行交换，生成两个后代。单点杂交过程如图2-4所示。

图2-4　单点杂交过程示意图

例如，给定两个父体如下：

假设杂交点为17，那么交换两个父体串的第17个基因位右边的子串后，所得到的两个后代如下：

杂交算子的目的在于由较好的个体构造出更好的个体。

在遗传算法中应用杂交算子的过程是：从轮盘赌选择产生的群体中，先按一定的概率pc 从中挑选出若干个染色体作为父体。从[0，1]中产生M 个随机数rk（k=1，2，…，M），若rk ≤pc，则挑选群体中第k 个染色体作为父体。若这样挑选出来的父体是奇数个，则从群体中随机地再挑选一个父体，或从已挑选的父体中删除一个。这样共挑选出来偶数个父体，再将这偶数个父体两两进行杂交。

对本例而言，假定pc=0.25，所产生的10个随机数为：

0.625　721　0.266 823　0.288 644　0.295 114　0.163 274

0.567　461　0.085 940　0.392 865　0.770 714　0.548 656

那么从轮盘赌选择产生的群体中，染色体v5′和v7′被挑选出来进行杂交。我们随机地生成[1，32]中的一个整数，设为1。那么交换v5′和v7′第15个基因位的右边部分，便得到两个后代v5″和v7″。

2）变异算子

变异算子的目的在于引入群体中染色体的多样性，防止算法的非成熟收敛。

变异算子以某一预先指定的概率pm 对群体中染色体的基因进行变异。若染色体的某一位被选择进行变异，当该位为1时，则变为0；当该位为0时，则变为1。

例如给定下列染色体v1，若选择v1 的第18个基因进行变异，因为该位基因为1，所以将它变为0，得到一个新的染色体v1′。

概率pm 是期望改变的群体中染色体的基因个数与基因总数的百分比。例如，对本例而言，群体中的基因总数为L×M=33×10=330，若pm=0.01，则我们期望改变群体中染色体的3.3个基因位。

在遗传算法中应用变异算子的过程是：对经过杂交后的群体中的每一个染色体的每一基因位，产生一个随机数r，若r≤pm，那么该基因位进行变异，否则不进行变异。

在本例中，取pm=0.01，产生[0，1]中的330个随机数，即对群体中每一染色体中的每一基因位产生一个随机数。假定如表2-2所示的基因要进行变异。

表2-2　需要变异的基因信息表

那么经过变异后，群体中的染色体如下：

与该群体中10个染色体响应的适应值如下：