摘要：本文试图以活泼的笔调，讨论一个计算机科学难题，SAT问题。并由此展开，展示计算机算法的魅力，与计算机算法分析和设计的一些基本思想。最后，给出一个SAT问题的演化计算的算法和程序实现。
关键字：SAT问题，组合爆炸，爬山法，A算法，演化计算
SAT问题展开说（2）[上]
问题的解决方案
我们现在可以仔细的看看演化计算的思路了。
演化计算，或称进化计算，是遗传算法的超集，其特点是群体搜索策略和群体中个体之间的信息交换。目前研究的进化算法主要有遗传算法、进化规划和进化策略。尽管它们之间很相似，但历史上这三种算法是彼此独立发展起来的。
演化计算采取了随机搜索的策略，不苛求问题的动力学信息（如连续、可微等），是解决NPC问题较具前景的方案。我们这次详细讨论如何用之给出一个SAT问题的解决方案。
它解决的问题的一般描述：
J = max F(x) ,x ∈X, x = (x1,x2,…,xn )’，
其中 F(x) 为评价函数，
x为解向量，
X为定义域。
而它解决问题的一般步骤为：
• 染色体编码和解码；
• 设置初始种群和适应度函数；
• 选择遗传算子 以概率Pc杂交的杂交算子和以概率Pm变异的变异算子；
• 淘汰策略。
染色体的编码方案有多种，而就如一开始所提到的，SAT问题采用二进制进行染色体编码是十分自然和方便的。我们使用c#语言来实现一个演化计算的算法，采用二进制编码，下面详细分析设计过程，最后附上分析和数值计算的例选。
整个系统的界面如下：
图6 SAT问题方案的软件界面
继续采用开始所建立的模型，对于基于逻辑变量集合A的染色体组，和句子集合F，我们分别用
private StringBuilder []satGenes;
private int[,] bSentence;
表示，其中|A|的值（即n）由valNum表示，|F|的值（即m）由maxNum表示：
private int maxNum;
private int valNum;
染色体组中，每一个染色体使F中的句子成真的总数是个重要的标志，我们用score表示，且记录其中最好的和最差的：
private int[] score;
private StringBuilder best;
private StringBuilder worst;
然后就是杂交和变异的概率，和随机数生成器：
private double Pc;
private double Pm;
private System.Random randNum;
这些都定义在类SAT中，由如下构造函数初始化：
public SAT(int N,int valnum,double pc,double pm)
{
//
// TODO: 在此处添加构造函数逻辑
//
maxNum=N;
valNum=valnum;
score=new int[maxNum];
satGenes=new StringBuilder[maxNum];
for(int i=0;i<maxNum;i++)
satGenes[i]=new StringBuilder();
bSentence=new int[maxNum,valNum];
for(int i=0;i<maxNum;i++)
for(int j=0;j<valNum;j++)
bSentence[i,j]=0;
Pc=pc;
Pm=pm;
randNum=new Random(unchecked((int)DateTime.Now.Ticks));
}
染色体组我们由如下过程进行初始化：
public void InitGenes()
{
for(int i=0;i<maxNum;i++)
for(int j=0;j<valNum;j++)
satGenes[i].Insert(j,randNum.Next(1).ToString());
}
那么由染色体组的演化，我们就可以详细设计算法了。
