一种求解MAX-k-SAT问题的新方法

宋建民,弓小影

（石家庄经济学院数理学院,河北石家庄 050031）

近年来,利用二进制差分演化算法求解0-1背包问题、利用二进制粒子群优化算法求解可满足问题和集合覆盖问题等,得到了许多满意的结果[1-3].本文研究利用二进制差分演化算法求解在计算机科学中具有重要地位的最大k-可满足问题[4].通过将二进制差分演化算法与改进的动态变邻域搜索相结合,提出了一种改进二进制差分演化算法,并应用于一系列随机生成的大规模MAX-k-SAT实例.实验结果证明该方法是一种求解该问题的可行新方法.

1 MAX-k-SAT问题

基于MAX-k-SAT（k≥3）的逻辑定义,提出MAX-k-SAT（k≥3）问题的一种最优化表示形式.

2 IBDE算法设计

对于含有n个不同命题变元的MAX-k-SAT问题,利用强力搜索法求解需要分别计算2n个指派满足的子句个数,计算时间复杂性为O（2n）,显然是不可取的,因此我们在下面将介绍一种基于HBDE求解MAX-k-SAT问题的有效方法.

变邻域搜索（VNS）是Hansen等提出的一种meta-Heuristic算法,已被广泛应用于求解各种NPC问题[7].与传统的单一邻域结构所不同的是：VNS首先预定义一系列的邻域结构,并且在搜索中先由某个邻域开始,按照一定的次序系统性地不断变化邻域的搜索范围,直到有更好的解产生为止.借鉴VNS的思想,为避免HBDE陷入局部最优的情况发生,下面对于解为二进制向量的最大优化问题maxf（X）,给出一种基于局部随机邻域变化搜索的动态变邻域搜索算法（DVNS）.令L1与L2为随机产生的1到n之间的两个随机整数,并且满足1≤L2-L1≤n/4,于是DVNS的算法伪代码描述如下.

进化算法的全局搜索能力虽然较强,但其局部搜索能力往往不足[8].为此,下面将DVNS与HBDE相结合提出一种用于求解MAX-k-SAT问题的改进二进制差分演化算法（Improved Binary Differential Evolution,IBDE）,以加强差分演化的局部搜索能力.为了有效地将HBDE与DVNS结合,不必对HBDE的每一个个体均利用DVNS进行局部优化,而是根据种群的规模随机地选择一定数量（通常≤N/3,其中N为种群规模）的个体进行优化,这样既提高了算法的局部搜索,同时又兼顾了算法的效率.下面即给出HBDE与DVNS结合求解MAX-k-SAT问题的算法IBDE的伪代码描述.

在算法IBDE中,rand（0,1）表示随机产生的一个0与1之间的随机数.由于在算法IBDE中只利用DVNS对不超过1/3的个体随机进行了局部优化,因此算法IBDE的时间复杂性为O（ITE*（N*n+N*n/3））+O（N*n/3）=O（ITE*N*n）.可见,虽然 IBDE 是由 HBDE 与 DVNS 相结合而得到的,但其时间复杂性仍然与HBDE相同.

3 仿真计算结果与比较

为了验证IBDE求解MAX-k-SAT问题的可行性与有效性,利用随机产生的一系列大规模MAX-k-SAT实例进行仿真计算,并与Johnson算法和GA进行比较.为了比较的公平性,在利用GA求解时,同样按照上文算法的方法将DVNS用于对其个体进行局部优化.仿真计算使用lenovo X201i笔记本,硬件环境为Intel（R）Pentium（R）CPU：U5400-1.20 GHz,2.00GB内存,操作系统为Windows 7,并利用VC++6.0进行编程实现.

由于每一个MAX-k-SAT（k≥3）问题都可以等值转化为一个MAX-3-SAT问题[9],因此将利用随机生成的大规模MAX-3-SAT实例进行仿真计算.由于IBDE、Johnson和GA均为随机近似算法,对于每一个MAX-3-SAT实例,取各算法10次计算结果的平均值进行比较.记n为MAX-3-SAT实例中命题变元的个数,m为其中的子句个数,于是利用各算法计算一系列随机生成的大规模MAX-3-SAT实例的结果见图1.

图1 n=200时各算法对实例1-5的平均计算结果比较Fig.1 The resultcomparison of each algorithm on average1-5when n=200

在图1中,实例1-5的n=200,m依次为400、500、600、700、800,从3个算法所得到的平均最优值可以看出,无论m如何变化,IBDE求得的平均最优值均优于GA和Johnson算法,并且与n和m之间的比值无关.计算结果比较表明,对于随机大规模MAX-k-SAT（k≥3）问题的求解,IBDE是一种比GA和Johnson算法更有效的新方法.

4 小结

本文基于动态变邻域搜索改进二进制差分演化算法的局部搜索能力,给出了一种求解MAX-k-SAT问题的改进差分演化算法IBDE.通过利用一系列随机生成的大规模MAX-k-SAT实例与GA和Johnson算法的仿真计算进行比较,结果表明：对于大规模的随机MAX-k-SAT问题,IBDE算法不仅是可行的,而且是高效的.由于HBDE是一种适于求解可行解能够表示为二进制编码的（动态）组合优化问题的算法,今后将进一步探讨如何将其与DVNS有效结合以求解其他组合优化问题.

[1]贺毅朝,王熙照,寇应展.一种具有混合编码的二进制差分演化算法[J].计算机研究与发展,2007,44（9）：1476-1484.

[2]贺毅朝,王彦祺,寇应展.一种求解3-SAT问题新方法[J].计算机工程与应用,2006,42（16）：70-72.

[3]Frans V B.An analysis of particle swarm optimizers[D].Pretoria：University of Pretoria,2001.

[4]Du D Z,Ko K I,Hu XD.Design and analysis of approximation algorithms[M].Springer Science BusinessMedia,LLC,2012.

[5]DoritS,Hochbaum E.NP难解问题的近似算法[M].北京：世界图书出版公司,1995.

[6]堵丁柱,葛可一,王洁.计算复杂性导引[M].北京：高等教育出版社,2002.

[7]Chakraborty U K,Das S,Konar A.Differentialevolution with localneighborhood[J].IEEECongress on Evolutionary Computation,2006（7）：2042-2049.

[8]陈国良,王熙法,庄镇泉,等.遗传算法及其应用[M].北京：人民邮电出版社,2003.

[9]张健.逻辑公式的可满足性判定-方法、工具及应用[M].北京：科学出版社,2000.