基本遗传算法和改进算法的比较与SAT-IEA算法

一般的实验方法是求解随机生成的可满足测试样本，为了测试所提出的算法的有效性，我们按如下方法生成测试样例：

选定命题变元集V={x1，x2，…，xm}，每次随机地从V 中挑选3个两两不同的命题变元，以50%的概率决定每个变元是否取非，这样得到3个文字组成的一个子句，重复上述步骤l次，得到l 个子句组成一个CNF。按此方法产生的CNF称为一个随机产生的长度为l的m 元3-SAT 样例。

根据Mitchell D 的研究[3]，随机生成的最难求解的3-SAT 测试样本是子句数目l 与变元数目m 的比值，为4.3，为此，我们按照l/m 从1.5递增至4.3的规律，生成了可满足的3-SAT 测试样本（保证每个样本是可满足的），对算法进行了测试，表4-1列出了测试过程中的参数设置，表4-2列出了测试结果。

表4-1　算法参数设置

表4-2　SAT-EA算法和SAT-IEA算法实验结果比较

从表4-2的结果可以看出，随着子句数与变元数比值的增长，基本遗传算法能够求得的可满足样例数越来越少，这也同时说明了问题越来越难求解，而从改进的遗传算法的结果来看，其可满足样例数均达到最大，即求得全部实例的可满足解，这表明改进的遗传算法对原始演化算法所做的改进是十分有效的，算法的求解速度也较基本遗传算法大为提高。(www.xing528.com)

Solar算法是一个基于拟物拟人思想的求解SAT 问题的快速算法[4]。这里我们将改进的遗传算法和Solar算法进行比较实验，可以从侧面反映改进的遗传算法的性能。实验中的实例来自国际通用的SATLIB 库中的Uniform Random-3-SAT 实例集。表4-3 显示了SAT-IEA 算法和Solar算法的实验结果。

表4-3　SAT-IEA算法和Solar算法实验结果比较

表4-3的结果则表明，对于3-SAT 问题，改进的遗传算法也有较好的求解质量和求解速度，其求解成功率和平均运算时间都与目前一种快速的求解算法——Solar算法性能相当，从而表明，改进的遗传算法是一种能有效求解难SAT 问题的快速算法。