遗传操作设计优化方案

对保留的候选解进行某些操作，生成新的候选解，这些操作就是遗传操作，这是从优化搜索的角度，执行遗传算法的过程。换句话说，就是通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度（适应度评估）施加一定的操作，以便实现优胜劣汰的进化过程。遗传操作的效果与所取的操作概率、编码方法、群体大小、初始群体以及适应度函数的设定密切相关。

遗传操作包括三个基本遗传算子：选择、交叉、变异。每个个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。这种随机化操作和传统的随机搜索方法是有区别的，遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。

（1）选择

选择是重要的一个遗传算子，有时又称为再生算子。所谓选择就是从群体中选择优胜的个体，淘汰劣质个体，其目的是把优化的个体（或解）直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是以建立在群体中个体的适应度评估为基础，个体的适应度越高，被选择的机会就越多。目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。其中赌轮（见图5-5）选择法是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率与其适应度值成比例。个体被选后，可随机地组成交配对，以供后面的交叉操作。

设群体大小为n，其中个体i的适应度为F，则i被选择的概率为

赌轮选择法的实现步骤：

1）计算群体中所有个体的适应度函数值需要解码。

2）利用比例选择算子式（5-4），计算每个个体被选中遗传到下一代群体的概率。

3）采用模拟赌轮操作（即生成0～1之间的随机数与每一个体遗传到下一代的概率进行匹配）来确定各个个体是否遗传到下一代群体中。

步骤说明，概率反映个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高，反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个［0，1］之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。

（2）交叉

交叉算子是根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。

交叉加上下面将要讲述的变异所形成的遗传基因的重组是自然界生物进化过程的核心，也是遗传算法中的核心。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

最常用的交叉算子为单点交叉。具体操作是：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：

个体A：1001↑111→1001000新个体

个体B：0011↑000→0011111新个体(www.xing528.com)

（3）变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：

① 实值变异；

② 二进制变异。

一般变异算子操作的基本步骤如下：

① 对群中所有个体以事先设定的编译概率判断是否进行变异；

② 对进行变异的个体随机选择变异位进行变异。

变异算子的具体操作是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动（以变异概率P做变动），对（0，1）二值码串中的基本变异操作如下：

基因位上方标有∗号的基因发生变异。

选取变异率，变异率一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001～0.1。

例：个体A 10^∗11^∗1^∗0^∗1→1110011个体A′

遗传算法引入变异的目的有两个：

1）使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力，可以加速向最优解收敛。显然，这种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。

2）使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

到此我们可以归纳如下：遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合，是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块（见下面所述）时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法中的一个重要研究内容。