二进制编码的遗传算法技术

1.算法过程

不失一般性，设优化问题为

式中：C＝{cj}为模型p个待优化参数（优化变量）；[aj，bj]为cj的初始变化区间（搜索区间）；X为模型N维输入向量；Y为模型M维输出向量；F为一般非线性模型，即F：RN→RM；{（Xi，Yi）|i＝1，2，…，m}为模型输入、输出m对观测数据；‖‖为取范数；q为实常数，如q＝1则为最小一乘准则，为q＝2时为最小二乘准则，等等，可视实际建模要求而定；f为优化准则函数。

二进制编码遗传算法包括如下步骤[1]：

步骤1：变量初始变化空间的离散和二进制编码。研究表明，采用二进制编码时，杂交操作的搜索能力比十进制编码时的搜索能力强，而且随着群体规模的扩大，这种差别就越明显。设编码长度为e，把每个变量的初始变化区间[aj，bj]等分成（2e-1）个子区间，则

式中：子区间长度dj＝（bj-aj）/（2e-1）是常数，它决定了遗传算法解的精度；搜索步数Ij为小于2e的任意十进制非负整数，是变数。

经过编码，变量的搜索空间离散成（2e）p个网格点。遗传算法中称每个网格点为个体，它对应p个变量的一种可能取值状态，并用p个e位二进制数{ia（j，k）|j＝1，2，…，p；k＝1，2，…，e}表示，即

通过式（5-6）和式（5-7）的编码，p个变量cj的取值状态、网格点、个体、p个二进制数{ia（j，k）}之间建立了一一对应的关系。可见，优化变量的变化区间及编码长度决定了模型参数实际搜索空间的大小。遗传算法的直接操作对象就是这些二进制数。

步骤2：初始父代群体的随机生成。设群体规模大小为n。从上述（2e）p 个网格点中均匀随机选取n个点作为初始父代群体。即生成n组[0，1]区间上的均匀随机数（以下简称随机数），每组有p个，即{u（j，i）|j＝1，2，…，p；i＝1，2，…，n}，这些随机数经下式转换得到相应的随机搜索步数，即

式中：INT（·）为取整函数，显然有Ij（i）＜2e。这些随机搜索步数{Ij（i）}由式（5-7）对应二进制数{ia（j，k，i）|j＝1，2，…，p；k＝1，2，…，e；i＝1，2，…，n}，又由式（5-6）与n组优化变量{cj（i）|j＝1，2，…，p；i＝1，2，…，n}一一对应，并把它们作为初始父代个体。

步骤3：二进制数的解码和父代个体适应度的评价。把父代个体编码串ia（j，k，i）经式（5-7）和式（5-6）解码成优化变量cj（i），把后者代入式（5-5）得相应的优化准则函数值fi。fi值越小表示该个体的适应度值越高，反之亦然。把{fi|i＝1，2，…，n}按从小到大排序，对应的变量{cj（i）}和二进制数{ia（j，k，i）}也跟着排序，为简便，这些记号仍沿用。称排序后最前面几个个体为优秀个体（Superior individuals）。定义排序后的第i个父代个体的适应度函数值为

步骤4：父代个体的概率选择。取比例选择方式，则个体i的选择概率为

生成n个随机数{u（k）|k＝1，2，…，n}。若u（k）∈（pi-1，pi），则第i个个体被选中，其二进制数记为ia1（j，k，i）。同理可得另外的n个父代个体{ia2（j，k，i）}。这样从原父代群体中以概率p′i选择第i个个体，共选择两组各n个个体。

步骤5：父代个体的杂交。由于杂交概率pc控制杂交算子应用的频率，在每代新群体中，有npc对串进行杂交，pc越高，群体中串的更新就越快，遗传算法搜索新区域的机会就越大，因此这里pc取定为1.0。在标准遗传算法中是采用单点杂交的方式进行父代个体的杂交，然而，目前普遍认为两点杂交方式优于单点杂交方式，因此这里决定采用两点杂交。由步骤4得的两组父代个体随机两两配对，成为n对双亲。先生成2个随机数U1和U2，再转成十进制整数：IU1＝INT（1+U1e），IU2＝INT（1+U2e）。设IU1≤IU2，否则交换其值。第i对双亲ia1（j，k，i）和ia2（j，k，i）的两点杂交，是指将它们的二进制数串中第IU1位至第IU2位的数字段相互交换，生成两个子代个体

步骤6：子代个体的变异。这里采用两点变异，因为它与单点变异相比更有助于增强群体的多样性。生成4个随机数U1～U4。若U1≤0.5时子代取式（5-11），否则取式（5-12），得n个子代，记其二进制数为{ia（j，k，i）}。把U2，U3转化成不大于e的整数，即

变异率pm为子代个体发生变异的概率。子代个体ia（j，k，i）的两点变异，即如下变换

在步骤6中，利用随机数U1以0.5的概率选取杂交后生成的两个子代个体的任一个，利用U2和U3来随机选取子代个体串中将发生变异的两个位置，利用U4来控制子代个体发生变异的可能性。

步骤7：进化迭代。由步骤6得到的n个子代个体作为新的父代，算法转入步骤3，进入下一次进化过程，如此循环往复，优秀个体将逼近最优点。

以上7个步骤便构成了二进制编码标准遗传算法，其计算过程可描述为如图5-2的流程图。

图5-2　二进制编码标准遗传算法计算流程图

2.优点与不足

二进制编码是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。(www.xing528.com)

二进制编码方法有下述一些优点[5]：

（1）编码、解码操作简单易行。

（2）杂交和变异等遗传操作便于实现。

（3）符合最小字符集编码原则。

（4）便于利用模式定理进行理论分析。

（5）具有一定的全局搜索能力。

（6）具有一定的并行处理能力。

同时，值得注意的是，一方面，二进制编码存在着连续函数离散化时的映射误差，可能达不到要求的精度，而个体编码串的长度较长时，虽然能提高精度，但却会使遗传算法的搜索空间急剧扩大[24]；同时还需要频繁地编码和解码，计算量大且只能产生有限的离散点阵，还可能产生额外的最优点。另一方面，二进制编码有时不便于反映所求问题的结构特征，对于一些连续函数的优化问题，遗传算法的局部搜索能力也较差。二进制编码存在Hamming悬崖问题，这种缺陷将降低遗传算子的搜索效率。为此，人们提出用格雷码、动态参数编码或实数编码来对个体进行编码，格雷码编码可用于克服二进制编码映射的不连续问题，动态参数编码有利于克服搜索效率与表示精度间的矛盾，同时对克服过早收敛现象也有所帮助。由于实数编码基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易从传统优化方法中借鉴好的技巧来形成有效的遗传算子[5]。

因此，接下来将简要阐述较为常用的实数编码遗传算法计算过程。关于格雷码编码遗传算法的相关理论和计算过程可参阅文献[5]。