遗传算法中的种群选择优化和交叉操作

1.选择算子

在基本遗传算法中，选择操作是种群的第一次重组操作，顾名思义是选择所需的个体，这个过程一般而言不会产生新的个体，只是一种简单的复制操作，选择算子的根据是适应度函数，因此，选择操作起到一个承上启下的作用，保留原有模式，个体设计好的选择算子会保证种群最终收敛。常用的选择操作有轮盘赌方法、锦标赛方法、随机遍历选择和基于种群交流选择。其中，锦标赛方法的优点是对于种群个体的适应度是正值还是负值并没有具体的要求，但此方法的随机性更强，存在更大的随机误差。此方法有较高的概率让最优的种群个体被选择，最差个体被淘汰。而基于种群交流选择是遗传算法中经常出现的问题，可能发生过早收敛，或者出现超级个体的情况。

本章算法的选择操作运用的是随机联赛选择和精英保留机制结合的方式，将所有种群个体按照适应值从高向低排序，保留适应值前n 个个体，n 为精英个体的数量。余下的种群个体由随机联赛操作进行生产。

随机联赛选择根据适应值来进行。在每次循环选择中，适应度最高的个体进入下一代种群。在联赛选择操作中，只有个体适应值之间的大小比较，而无个体适应度之间的运算，所以它对适应度是正是负并没有要求。操作如下：

（1）从群体中随机选取n 个个体进行适应度比较，适应值最高者遗传到下一代；

（2）将步骤（1）重复直到种群个体达到初始规模为止。

在选择操作时，算法遵循文献[8]关于比较两个个体之间关系的规则：

（1）可行解总是优于不可行解；

（2）如果两个个体都是可行解，那么比较其适应度大小，选择适应度高的个体；

（3）如果两个个体都是不可行解，那么选择违反约束条件程度小的个体。

2.交叉算子

算法中的交叉操作就是将两个父体部分结构加以替换，生成新的个体的操作。基本遗传算法中，交叉操作是产生新个体的主要手段，生成依据是父代个体，通过杂交把两个父体的优势基因进行组合，试图产生更高适应度、更好的个体。交叉操作不根据适应度进行交叉，算法与编码方式有关。当交叉概率Pc 越高时，交叉算子生成新个体的能力越强，但个体的优良模式被破坏的可能性也较大。

文献[9]提出了一种新的交叉算子，这种交叉算子的主要思想是将父代的3个个体一起进行交叉操作产生3个新的子代，即GA-MPC（GA with Multi-Parent Crossover）。本章的算法采用这种交叉算子，具体的交叉操作步骤如下所述：(https://www.xing528.com)

（1）当种群完成选择操作后，形成一个新的临时的种群，作为交叉操作的标的种群；

（2）随机从新种群中选取3个种群个体，如果出现选取的个体重复的情况，将重复个体舍去，重新随机选取一个新个体，保证3个个体不同；

（3）将3个个体按照适应值的大小进行排序，由小到大依次表示为x1，x2，x3；

（4）以均值μ，标准差σ 的正态分布公式随机产生一个随机值β，μ、σ 需要事先设定；

（5）生成3个子个体o1、o2、o3，其中f（x1）≤f（x2）≤f（x3）

这种操作实际是算术交叉算子的另一种变形体，在第二章的交叉算子一节介绍过，两个个体通过一定的线性组合而产生新的个体，这里的操作用3个个体取代两个个体，而且根据适应度进行一定的排序。

在式（3-13）～式（3-15）中，个体根据适应度组合的顺序并不是完全一样，式（3-13）与式（3-15）是相同的，式（3-14）与其他两个不同。实际上，式（3-13）与式（3-15）是为了产生的子代个体向适应度更好的个体靠近，而式（3-14）是为了保持子代的多样性而存在的。

3.变异算子

算法中的变异操作是针对单个个体进行操作的，以概率Pm 改变基因上的值。针对每个个体，每次变异都是独立的。变异的目的在于通过破坏当前解的模式，不断地在交叉算子产生新个体的基础上进行微调，能在一定程度上防止基因出现“早熟”的现象。变异算子Pm 越高，破坏能力越大。常见的变异算子与交叉算子类似，主要有基本位变异（针对每个基因，对变异值进行反转）、均匀变异（分别用符合某一范围内均匀分布的随机数，以某个概率进行变异）、高斯变异（利用高斯分布的随机数进行变异）。

普通的变异算子目的是为了破坏当前个体的模式，本章的算法采用非均匀变异操作，变异操作按式（3-16）进行，式中u 为正态分布的随机数，β 为0到1之间的随机数。当满足变异条件后，个体按式（3-17）更新。式中，t为当前迭代次数，T 为总迭代次数，β 为权重因子，b 为系统参数，自行设置。

式（3-16）、式（3-17）说明在迭代初期，算子能大范围地搜索整个空间，在迭代后期，算子在当前解的小范围内搜索，这种操作类似模拟退火的思想，高温时大步长搜索，低温时小步长搜索，保证了种群个体能发现可能的最优解的所在。