遗传算法的具体实现与操作

在掌握遗传算法基本内容之后，就易于理解遗传算法的实现。

遗传算法的具体实现过程如下：

（1）初始化

选择一个群体，即选择一个串或个体的集合b_i，i＝1，2，…，n。这个初始的群体也就是问题假设解的集合。一般取n＝30～160。通常以随机方法产生串或个体的集合b_i，i＝1，2，…，n。问题的最优解将通过这些初始假设解进化而求出。设置进化代数计数器t＝0，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。

遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的、由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作（问题的）表示。

评估编码策略常采用以下三个规范：

1）完备性：问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）表现。

2）健全性：GA空间中的染色体能对应所有问题空间中的候选解。

3）非冗余性：染色体和候选解一一对应。

如上所述，目前常用的编码技术为二进制编码，即是由二进制数字字符集｛0，1｝产生通常的0、1字符串来表示问题空间的候选解。它具有以下特点：

① 简单易行；

② 符合最小字符集编码原则；

③ 便于用模式定理进行分析，因为模式定理就是以二进制编码为基础的。

（2）选择操作

根据适者生存原则，选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。选择的目的是把优化的个体直接遗传到下一代，或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。首先进行个体评价：计算群体P（t）中各个个体的适应度；再进行选择运算，将选择算子作用于群体；给出目标函数f，则f（b_i）称为个体b_i的适应度。以下式P为选中b_i为下一代个体的次数。

(www.xing528.com)

显然，从式（5-8）可知：

1）适应度较高的个体，繁殖下一代的数目较多。

2）适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。

（3）交叉操作

将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中，起核心作用的就是交叉算子。对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体S₁＝100101，S₂＝010111；选择它们的左边3位进行交叉操作，则有S₁＝010101，S₂＝100111。一般而言，交叉概率P取值为0.25～0.75。

（4）变异操作

将变异算子作用于群体，即是对群体中的个体串的某些基因座上的基因值作变动。根据生物遗传中基因变异的原理，以变异概率P_m对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率P_m与生物变异极小的情况一致，所以P_m的取值较小，一般取0.01～0.2。例如有个体S＝101011，对其的第1、4位置的基因进行变异，则有S′＝001111。单靠变异不能在求解中得到好处，但是它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。

（5）全局最优收敛

群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t₁），不断运行下去，得出全局最优收敛，终止运行。

终止条件判断：若迭代次数为t_T，则以进化过程中所得到的具有最大适应度个体作为最优解输出终止计算。或当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。

遗传算法执行示意图如图5-2，选择淘汰4，5，提高1，2用作下一代交叉，2，3交叉产生6，7，变异1变异为9。整个操作流程图如图5-3所示。

图5-2 遗传算法的执行过程