遗传算法及其在工程优化中的应用

1.染色体编码

用二进制位串表示SAT 问题的真值指派是最直观的染色体编码方法，这种编码方法充分利用了SAT 问题本身的特点，便于计算适应度函数和设计各种遗传操作。对于n 个变元的SAT 问题，染色体用n 位二进制位串表示，它与变元的取值直接对应，可直接解释成真值指派。例如，某SAT 问题的逻辑变元的集合为X={x1，x2，…，xN}，则该问题的一个真值指派是一个n 维向量（v1，v2，…，vn ），其中vi ∈{0，1}，0和1分别代表逻辑值的假和真，则染色体编码形如：010…10（共N 位）。

2.适应度函数

用演化算法求解SAT 问题一般是将SAT 问题转换为对适应度函数求极值的最优化问题。这里适应度函数值定义为个体对应的真值指派所能满足的子句数，适应值越大，表示被满足的子句数越多，个体就越优。设有个体X，则计算适应值的评价函数定义为：

式中，N 为CNF范式中子句的数目，Ci 为CNF 范式的第i 个子句，F（Ci）为子句Ci 的真值。如果有两个个体X1 和X2，且有fitness（X1）＞fitness（X2），则约定为个体X1 优于个体X2，显然算法的目标就是找到某个个体Xp，使得fitness（Xp）=N。

3.杂交算子

从SAT 表达式中选择若干子句，将这些子句包含的所有变元在两个个体之中的取值进行交叉，即基于SAT 问题的范式杂交，而非基于变元序列的杂交。此外，在杂交过程中，是选择适应值较差的个体中使得CNF范式为零的那部分子句中的变元值被适应度较好个体中相应的变元值所替换，而不是盲目替换任意变元的值。

例如有个体X1={x1，x2，…，xm}和个体X2={x1′，x2′，…，xm′}被选择要做杂交操作。假设有fitness（X1）＜fitness（X2），即个体X2 优于个体X1，且在X1 的赋值下，CNF范式中有子句集合C={C1，C2，…，Cw}的逻辑值为零，在C 中出现的所有变元组成的变元子集为M={x1，x2，…，xv}，则将X2 中出现在M 中的所有变元的值替换掉X1 中相应的变元的值，显然，该杂交算子一次操作只对两个父体产生一个子代个体。

4.变异算子(www.xing528.com)

和杂交操作一样，在改进的变异算子中，选择个体中不能满足CNF范式中的那部分子句中的若干变元进行翻转，而不是盲目翻转任意变元的值。

例如有个体X={x1，x2，…，xm}被选择做变异操作，已知在X 的赋值下，CNF范式中有子句集合C={C1，C2，…，Cw}的逻辑值为零，在C 中出现的所有变元组成的变元子集为M ={x1，x2，…，xv}，则在M 中选择MutateNum 个变元，将它们的值取反，其中Mutate-Num 为算法参数，在本章的所有实验中，取MutateNum=3。

5.拟人策略

为了提高演化过程的效率，根据SAT 问题的特点，我们在算法中加入拟人算子，该算子按如下策略执行：对于所选择执行该算子的个体，计算该个体中每一变元的冲突数（即由该变元的取值所引起的为零子句的数目），选择引起冲突数最大的变元之一，并将其取值翻转，然后计算翻转之后各变元的新的冲突数，继续翻转引起冲突数最大的变元，如此下去，直到达到某一设定的最大翻转上限，或者所有变元冲突数为零为止。拟人算子的另一个策略是：对于所选择被执行该算子的个体，对其每一变元，计算该变元翻转之后所引起的冲突数，选择翻转之后引起冲突数最小的变元之一，将其翻转，重复这一步骤，直到达到某一设定的最大翻转上限或者所有变元冲突数为零。

可从拟人的角度对以上策略作如下解释：个体X（t）的适应函数值是整个社会对X（t）在这一状态（取值）的满意程度的度量，整个社会由m 个集团（m 个变元）组成，每个集团对X（t）的不满意的程度为这一集团对它所在的群体（出现该变元的子句集合）的满意程度的和（变元在所有子句中引起的冲突数的和）。以上拟人策略可解释为当局实施如下动作：在整个社会中挑选一个最不满意的集团，然后针对此集团修改一项与它有关的政策，使它的不满意度降低。由于政策的改变，有些集团的不满意度可能会升高，然后当局继续这一动作，直到所有集团的不满意度达到最低。上述第二个拟人策略同样可以解释为：当局在整个社会中挑选某项最为所有集团满意的政策进行实施，如此下去，直到所有集团不满意度达到最低。

拟人策略可以避免盲目搜索以及减少陷入局部极小的机会，因为该策略能最大限度地挖掘个体的潜力，使其不仅在靠近最优解时能快速逼近，而且在局部最优解时能跳离局部极值并迅速达到另一个更优的解。

6.停机条件

停机条件也称算法的中止条件，当算法找到问题的可满足解时会停机。另外，当算法达到一定演化代数或运算时间超过一个预设值时，即使仍未找到问题的解也会停机。