3.5 遗传算法流程

遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。

在遗传算法中，将n维决策向量X=[x₁x₂⋯x_n]^T用n个记号X_i（i=1，2,⋯,n）所组成的符号串X来表示：

把每一个X_i看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看作由n个遗传基因所组成的一个染色体。一般情况下，染色体的长度是固定的，但对一些问题来说它也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数，或者是一个纯粹的记号。最简单的等位基因是由0或1的符号串组成的，相应的染色体就可以表示为一个二进制符号串。这种编码所形成的排列形式是个体的基因型，与它对应的X值是个体的表现型。染色体X也称为个体X，对于每一个个体X，要按照一定的规则确定其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，适应度越小。

在遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来完成的，因而所有的染色体X就组成了问题的搜索空间。

生物的进化过程主要是通过染色体之间的交叉和染色体基因的变异来完成的。与此相对应，遗传算法中最优解的搜索过程正是模仿生物的这个进化过程，进行反复迭代，从第t代群体P(t)，经过一代遗传和进化后，得到第t+1代群体P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，将达到或接近于问题的最优解。

遗传算法的运算流程如图3.1所示。具体步骤如下：

（1）初始化。设置进化代数计数器g=0，设置最大进化代数G，随机生成N_P个个体作为初始群体P(0)。

（2）个体评价。计算群体P(t)中各个个体的适应度。

（3）选择运算。将选择算子作用于群体，根据个体的适应度，按照一定的规则或方法，选择一些优良个体遗传到下一代群体。

（4）交叉运算。将交叉算子作用于群体，对选中的成对个体，以某一概率交换它们之间的部分染色体，产生新的个体。

（5）变异运算。将变异算子作用于群体，对选中的个体，以某一概率改变某一个或某一些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)。计算其适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。

（6）终止条件判断：若g≤G，则g=g+1，转到步骤（2）；若g＞G，则此进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。