求解SAT问题的遗传算法优化步骤

在求解SAT 问题的遗传算法中，一般要用到变异和杂交等遗传算子。此外，在进行遗传算子操作之前，需要做选择操作，从群体中选择出有待进行杂交或变异等算子操作的个体。一般演化算法中有两种策略挑选个体：一种是随机挑选，即每一个体都以等概率被挑选；另一种是运用轮盘赌策略，根据每个个体适应度的大小确定其被选择的概率，适应值越大，被选中的概率也就越大，即任一个体被选择的概率为：

式中，Pi 为个体i被选中的概率；fi 为个体i的适应值；M 为群体规模。

变异操作是随机挑选染色体的某一位（或几位）进行翻转，即0→1，1→0。

杂交操作是选择两个染色体，将其部分基因位交换，产生出两个新染色体。杂交操作一般分单点杂交、两点杂交和多点杂交。下面详细介绍一下单点杂交，具体来说可分3步：

（1）从群体中选择两个染色体f 和m 作为双亲，设双亲f 和m 的染色体串分别为f1f2…fn 和m1m2…mn，其中fi，mi∈{0，1}（1≤i≤n）；

（2）产生一个随机数k（1≤k≤n）作为杂交点；

（3）在杂交点将两个染色体的基因位进行交叉，则产生两个新个体，它们的染色体串分别为f1f2…frmr+1mr+1…mn 和m1m2…mrfr+1fr+2…fn。

这里将求解SAT 问题的改进遗传算法完整描述如下。

遗传算法描述：

begin

step 1：用概率选择法生成PopSize个长度为m 的二进制位串的第0代群体Population（0）；CurGen：=0；(www.xing528.com)

step 2：对每一个体X∈Population（CurGen），计算适应值fitness（X），并选出最佳个体存入Xbest；

step 3：产生随机数r1（0≤r1≤1），如果r1＜P1，则从当前群体Population（CurGen）中选择一个个体执行变异算子，设个体Xi 经变异操作后产生新个体Xi′，判断fitness（Xi）＜fitness（Xi′）是否成立，若成立，则将Xi′ 直接替换Xi，否则做退火选择：产生随机数r1′ （0≤r1′≤1），判断r1′＜α·P1 是否成立，若成立，则仍将Xi′替换Xi ；

step 4：产生随机数r2（0≤r2≤1），如果r2＜P2，则从当前群体Population（CurGen）中随机选择两个不同的个体执行杂交算子，设个体Xi 和Xj [fitness（Xi）＜fitness（Xj）]经杂交操作后产生新个体X′，则判断fitness（Xi）＜fitness（X′）是否成立，若成立，则将X′直接替换Xi ；

step 5：产生随机数r3（0≤r3≤1），如果r3＜P3，则从当前群体Population（CurGen）中随机选择一个个体执行拟人算子，设个体Xi 经拟人操作后产生新个体Xi′，判断fitness（Xi）＜fitness（Xi′）是否成立，若成立，则将Xi′直接替换Xi ；

step 6：判断新产生的个体中是否存在个体Xi，使得fitness（Xi）＞fitness（Xbest），若存在，则将Xi 替换Xbest；

step 7：判断是否满足停机条件，若满足，则停机并输出结果；

step 8：CurGen：=CurGen+1，转step 3。

end

说明：Population（n）为第n 代的群体，PopSize为群体规模，m 为SAT 问题的变元数目，P1 为变异概率，P2 为杂交概率，P3 为拟人概率，CurGen为当前演化代数。