3.2 遗传算法的基本算子

选择算子

所谓选择，就是根据个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。

“轮盘赌”选择法是遗传算法中最早提出的一种选择方法，由Holland提出，因为它简单实用，所以被广泛采用。它是一种基于比例的选择方法，利用各个个体适应度所占比例的大小来决定其子孙保留的可能性。若某个个体i的适应度为f_i，种群大小为N_P，则它被选取的概率表示为

个体适应度越大，则其被选择的机会也越大；反之亦然。为了选择交叉个体，需要进行多轮选择。每一轮产生一个[0，1]内的均匀随机数，将该随机数作为选择指针来确定被选个体。

交叉算子

交叉是指将群体P(t)中选中的各个个体随机搭配，对每一对个体以某一概率（交叉概率P_c）交换它们之间的部分染色体。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉操作一般分为以下步骤：

（1）从交配池中随机取出要交配的一对个体；

（2）根据位串长度L，对要交配的一对个体，随机选取[1，L-1]中的一个或多个整数k作为交叉位置；

（3）根据交叉概率P_c实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。

变异算子

变异是指对群体中的每个个体，以某一概率（变异概率P_m）将某一个或某一些基因座上的基因值改变为其他的等位基因值。根据个体编码方式的不同，变异方式有：二进制变异、实值变异。对于二进制变异，对相应的基因值取反；对于实值变异，对相应的基因值用取值范围内的其他随机值替代。

变异操作的一般步骤为：先对种群中所有个体按事先设定的变异概率判断是否要进行变异；然后对要进行变异的个体随机选择变异位进行变异。