遗传算子的设计——二进制与实数编码的杂交和变异算子

遗传算子的设计是与编码表示密切相关的。本节只讨论二进制编码和实数编码表示下杂交算子和变异算子的设计。对其他的编码表示，例如排列表示，将在后面结合具体应用进行讨论。

1.二进制编码

1）杂交算子

（1）点式杂交。点式杂交分为单点杂交和多点杂交。单点杂交在第二章第一节中已经进行了讨论，在此不再赘述。下面讨论多点杂交。

设表示问题解的二进制串长为L，多点杂交在1～（L-1）之间随机地选择多个杂交点，然后在保持第一个杂交点左边的对应子串不交换的情形下，间隔地交换两个父体在杂交点之间的对应子串，生成两个后代。

两点杂交的示意图如图2-9所示。

图2-9　两点杂交示意图

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

假设所选择的两个杂交点分别为6和13，那么交换两个父体串在第6个和第13个基因位之间的子串后，所得到的两个后代如下：

（2）均匀杂交。均匀杂交是依概率交换两个父体位串的每一位。其过程是，先随机地产生一个与父体等长的二进制位串，其中0表示不交换，1表示交换，这个二进制位串称为杂交模板。然后根据所产生的杂交模板对两个父体进行杂交。

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

假设所产生的杂交模板为：

所得到的两个后代如下：

2）变异算子

二进制编码时的变异算子非常简单，只是依一定的概率pm （称为变异概率）将所选个体的位取反。即：若是1，则取0；若是0，则取1。

2.实数向量编码

在下面的讨论中，我们假设解向量的形式为：

1）杂交算子

（1）简单杂交。简单杂交模仿二进制编码的杂交算子。最基本的是单点杂交，其方法与二进制编码时一样。

给定两个父体：

随机地在1～（n-1）之间选择一个杂交位置k，将两个父体在位置k 右端的两个子串进行交换，便得到两个后代：

类似地，可将二进制编码方式下的多点杂交、均匀杂交推广到实数向量表示中。

（2）算术杂交。算术杂交分为部分算术杂交和整体算术杂交。

部分算术杂交首先在父体向量中选择一部分分量，例如第k 个分量之后的（n-k）个分量，然后生成（0，1）上的（n-k）个随机数αk+1，αk+2，…，αn，经杂交算子后，所得到的两个后代为：

当然，我们也可以取αk+1=αk+2=…=αn，从而只需要生成一个随机数即可。

整体算术杂交先生成（0，1）上的n 个随机数α1，α2，…，αn，经杂交算子后，所得到的两个后代为：(www.xing528.com)

同样，我们可以取α1=α2=…=αn。

易知，通过算术杂交产生的后代，其分量仍在其定义区间内。

2）变异算子

在实数向量编码下的变异算子和二进制编码下的遗传算子大不相同，这是因为实数基因可在一定范围内变异。下面是几种常见的变异方法。

（1）均匀变异。

设x=（x1，x2，…，xn）是要变异的个体，均匀变异如下产生x=（x1，x2，…，xn）的一个后代：首先选一随机整数k ∈[1，n]，然后产生后代x′=（x1，…，xk′，…，xn），其中xk′是[lk，uk]中均匀分布的一个随机值。

（2）非均匀变异。

在传统的遗传算法中，算子的作用与代数是没有直接关系的，因而当算法演化到一定代数后，由于缺乏局部搜索，传统的遗传算子将很难获得收益。非均匀变异是由Janilow 和Michalewicz Z提出的，它是为提高精度、增加微调能力而设计的。设x=（x1，x2，…，xn）是要变异的个体，非均匀变异产生x 的一个后代：首先选一随机整数k ∈[1，n]，然后产生后代x′=（x1，…，xk′，…，xn），其中

这里Random（2）表示在[0，2）上随机地取一个整数所得的结果，t 是当前演化代数，函数Δ（t，y）返回[0，y]中的一个值，并且Δ（t，y）随t的增加而趋于0。函数Δ（t，y）的这个性质使得算法在演化初期能够搜索到较大范围，而在后期主要是进行局部搜索。

函数Δ（t，y）的具体表达式可以取为：

式中，r 是[0，1]上的一个随机数；T 表示最大演化代数；b 是确定不均匀度的参数，通常取值为2～5。