2024年4月3日发(作者：飞伶俐)
利用改进的HBDE算法求解MAX-k-SAT问题
宋建民;苟海燕
【摘 要】目前,利用进化算法求解组合优化问题已成为智能计算领域中的研究热点.
本文基于二进制差分演化算法和动态变邻域搜索相结合提出了一种求解最大可满足
问题(MAX-k-SAT)的改进算法(记为IBDE),通过与遗传算法和Johnson算法对一
系列随机大规模MAX-k-SAT实例的求解比较表明:IBDE是一种求解MAX-k-SAT
问题非常有效的新方法.
【期刊名称】《河北省科学院学报》
【年(卷),期】2014(031)001
【总页数】7页(P1-7)
【关键词】二进制差分演化;变邻域搜索;组合优化问题;MAX-SAT问题
【作 者】宋建民;苟海燕
【作者单位】石家庄经济学院 数理学院,河北石家庄050031;石家庄经济学院华信
学院,河北新乐 050700
【正文语种】中 文
【中图分类】TP18
近年来，利用进化算法（Evolutionary Algorithms，EAs）求解NP完全问题
（NP Complete Problems，NPC）已成为智能计算领域的一个研究热点问题
［1］，例如利用遗传算法（Genetic algorithm，GA）［2］和蚁群算法（Ant
Colony Optimization，ACO）［3］求解旅行商问题（Traveling Salesman
Problem，TSP）、利用二进制差分演化算法 （Binary Differential Evolution
Algo－rithm with Hybrid Encoding，HBDE）［4］求解0－1背包问题（0－
1Knapsack Problem，0－1KP）以及利用二进制粒子群优化算法（Binary
Particle Swarm Optimization，BPSO）求解可满足问题（Satisfiability
Problem，SAT）和集合覆盖问题（Set Covering Problem，SCP）［5，6］等，
得到了许多满意的结果。本文研究利用HBDE求解在计算机科学中具有重要地位
的最大k－可满足问题（MAX－k－SAT，k≥3）［7］，通过将 HBDE与改进的
动态变邻域搜索（Dynamic Variable Neighborhood Search，DVNS）相结合，
提出了一种求解MAX－k－SAT的改进二进制差分演化算法（Improved Binary
Differential Evolution，IBDE）。对于一系列随机生成的大规模MAX－k－SAT
实例，通过与GA［2］和Johnson算法［8］的求解比较表明，本文方法是一种
求解该问题的可行且有效的新方法。
本文其余内容组织如下：在第1节中首先介绍HBDE算法，然后提出MAX－k－
SAT的最优化形式表示；在第2节中，首先给出一种动态变邻域搜索（DVNS），
然后基于 HBDE与DVNS相结合提出一种求解MAX－k－SAT的IBDE算法；接
着在第3节中，利用一系列随机生成的大规模MAX－k－SAT实例，分别利用
IDBE算法、Johnson算法和GA进行求解与比较；最后总结全文，并提出今后的
研究思路。
1 背景知识
1.1 HBDE算法
差分演化（Differential Evolution，DE）［9，10］是由 Rainer Storn和
Kenneth Price提出的一种EAs，在求解数值优化问题中表现突出，受到了广泛的
关注。贺毅朝等人利用混合编码方法提出了一种二进制差分演化算法（HBDE）
［4］，使得DE能够用于求解各种以二进制向量为可行解的组合优化问题（如0
－1KP，SAT和SCP等）。下面我们仅给出HBDE的算法伪代码描述，详细内容
请参考文献［4］。
设 HBDE的种群规模为N，n为解空间A＝｛0，1｝n与辅助搜索空间S＝［－
5.0，5.0］n 的维数。记第t代种群中第i个个体的混合编码为（Xi（t），Bi
（t）），其中 Xi（t）＝［xi1（t），xi2（t），…，xin（t）］∈S，Bi（t）＝
［bi1（t），bi2（t），…，bin（t）］∈A；记第t＋1代中间种群中第i个中间
个体的混合编码为（Vi（t＋1），Ei（t＋1）），其中Vi（t＋1）＝［vi1（t＋
1），vi2（t＋1），…，vin（t＋1）］∈B，Ei（t＋1）＝［ei1（t＋1），ei2（t
＋1），…，ein（t＋1）］∈A，1≤i≤N。令（Xbest（t），Bbest（t）为第t代
中的最好个体，ITE为HBDE的最大迭代次数，则求解最大优化问题maxf（X）
的HBDE的算法伪代码描述如下：
算法 Algorithm
在 HBDE中，p1≠p2≠p3≠i并且1≤p1，p2，p3，i≤N。参数α和CR 定义见文
献［4，9］；sig（x）＝1/（1＋e－x）是一个单调函数。显然，Step4－Step11
为 HBDE的一次进化迭代，因此算法1的时间复杂度为O（ITE＊N＊n）。此外，
算法1是采用DE/r/1/bin模式的，对于DE的其它各模式，只要修改Step6即可
得到相应模式的HBDE算法。
1.2 MAX－k－SAT问题
最大k－可满足问题（MAX－k－SAT，k≥3）［8，11］是计算机科学中一个具
有重要理论意义的NP完全问题（NPC），是著名的可满足性问题（SAT）［5，
11］的一种推广形式，在人工智能、机器学习、VLSI集成电路设计与检测和数据
库检索等方面有着重要应用。由于MAX－k－SAT是NPC问题，不存在多项式时
间确定算法，目前主要是利用进化算法［2，5］和近似算法［8］对其进行求解，
其中最著名的有GA和Johnson算法。下面先给出MAX－k－SAT的逻辑语言定
义，然后提出它的一种最优化形式表示方法。
令P＝｛p1，p2，…，pn｝是由n个不同的命题变元构成的集合，P中变元的一
个指派t＝（t1，t2，…，tn）是一个函数t：P→ ｛0，1｝。显然在P上存在2n
个不同的指派。对于仅含有P中变元的命题公式C，如果t（C）＝1，则称C在
指派t下是可满足的。一般地，我们将形如C＝pi1∨pi2∨ …∨pi r∨﹁pi，r＋1∨﹁
pi，r＋2∨ …∨﹁pi k的命题公式称为P 上的子句，其中pij∈P，k称为子句C的
长度；公式A＝C1∧C2∧…∧Ci∧…∧Cm称为P上的一个合式范式（Conjunctive
Normal Form，CNF），其中Ci（1≤i≤m）为P上的子句。
所谓MAX－k－SAT（k≥3）问题即为：给定P上的一个CNF A，其中A的每个
子句的长度均为k，判断是否存在一个指派t，使得A中可满足的子句个数最多，
并求出这个最值，即求及其相应指派t。
基于上述逻辑定义，我们提出MAX－k－SAT（k≥3）问题的一种最优化表示形式。
令M＝｛x1，x2，…，xn｝是由n个取值为0或1的整型变量构成的集合，其中
的xi对应于P中变元的pi，1－xi对应于﹁pi。于是对于P上的一个CNF A＝
C1∧C2∧…∧Ci∧…∧Cm，如果将其中的∨看成一种特殊加法，即1⊕0＝0⊕1＝
1⊕1＝1且0⊕0＝0，而将∧看成普通加法，则MAX－3－SAT中求以及相应指派
t的问题等价转换为一个求解定义在｛0，1｝n上的多项式函数f（X）的最大值及
其最优解的最优化问题。其中X＝［x1，x2，…，xn］∈｛0，1｝n，子句Ci＝
pi1∨pi2∨ …∨pi r∨﹁pi，r＋1∨﹁pi，r＋2∨ …∨﹁pi k 对应于f（X）中的项Ei
＝ ［xi1 ⊕xi2 ⊕ …⊕xi r ⊕ （1－xi，r＋1）⊕ （1－xi，r＋2）⊕ …⊕ （1－
xik）］，xij ∈M，且
例如：MAX－3－SAT问题CNF A＝ （﹁p1∨p2∨p3）∧ （p1∨ ﹁p2∨p3）∧
（p1∨p2∨﹁p3），它的8个指派依次为：t0 ＝ （0，0，0），t1 ＝ （0，0，
1），t2 ＝ （0，1，0），t3 ＝ （0，1，1），t4 ＝ （1，0，0），t5 ＝ （1，
0，1），t6 ＝ （1，1，0），t7 ＝ （1，1，1），其中t0，t3，t5，t6 和t7 使
得A中所有子句均满足，从而max∑3 i＝1tj（Cj）＝3，（其中j＝0，3，5，6，
7）。MAX－3－SAT实例CNF A可以等价转换为求解定义在｛0，1｝3上的多
项式函数f（X）＝ ［（1－x1）⊕x2⊕x3］＋［x1⊕ （1－x2）⊕x3］＋
［x1⊕x2⊕（1－x3）］的最值的最优化问题。
对于含有n个不同命题变元的MAX－k－SAT问题，利用强力搜索法求解需要分
别计算2n个指派满足的子句个数，计算时间复杂性为O（2n），显然是不可取的，
因此我们在下面将介绍一种基于HBDE求解MAX－k－SAT问题的有效方法。
2 求解MAX－k－SAT问题的IBDE算法
为了改善HBDE在求解MAX－k－SAT问题时的搜索效果，下面首先给出一种局
部优化方法：动态变邻域搜索算法（Dynamic Variable Neighborhood Search，
DVNS），在此基础上，将HBDE与DVNS相结合提出一种求解MAX－k－SAT
问题的有效方法。
变邻域搜索（Variable Neighborhood Search，VNS）是 Hansen等［12］提
出的一种 Meta－Heuristic算法，已被广泛应用于求解各种NPC问题。与传统的
单一邻域结构所不同的是：VNS首先预定义一系列的邻域结构，并且在搜索中先
由某个邻域开始，按照一定的次序系统性地不断变化邻域的搜索范围，直到有更好
的解产生为止。
在VNS中，最主要的问题是确定邻域的结构、数量以及各邻域在搜索中应用的次
序与在搜索失败时邻域的改变策略，特别是邻域搜索范围的改变策略，其优劣程度
直接决定着其应用的成败。借鉴VNS的思想，为避免HBDE陷入局部最优的情况
发生，下面对于解为二进制向量的最大优化问题maxf（X），给出一种基于局部
随机邻域变化搜索的动态变邻域搜索算法（DVNS）。令L1与L2为随机产生的1
到n之间的两个随机整数，并且满足1≤L2－L1≤n/4，于是DVNS的算法伪代码
描述如下：
算法（X，n）Algorithm
在算法2中，rand［1，n］表示随机产生一个1到n之间的随机整数；X＝［x1，
x2，…，xn］为输入向量，Y＝［y1，y2，…，yn］为输出向量。显然，算法2的
时间复杂性为O（n）。
进化算法的全局搜索能力虽然较强，但其局部搜索能力往往不足［2］。为此，下
面将DVNS与HBDE相结合提出一种用于求解MAX－k－SAT问题的改进二进制
差分演化算法（Improved Binary Differential Evolution，IBDE），以加强差分
演化的局部搜索能力。为了有效地将HBDE与DVNS结合，不必对HBDE的每一
个个体均利用DVNS进行局部优化，而是根据种群的规模随机地选择一定数量
（通常≤N/3，其中N为种群规模）的个体进行优化，这样既提高了算法的局部搜
索，同时又兼顾了算法的效率。下面即给出HBDE与DVNS结合求解MAX－k－
SAT问题的算法IBDE的伪代码描述。
算法 Algorithm
在算法3中，rand（0，1）表示随机产生的一个0与1之间的随机数。由于在算
法3中只利用DVNS对不超过1/3的个体随机进行了局部优化，因此算法3的时
间复杂性为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求解时，同样按照算法3的方法将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
问题［13］，因此将利用随机生成的大规模MAX－3－SAT实例进行仿真计算。
由于IBDE、Johnson和GA均为随机近似算法，对于每一个MAX－3－SAT实例，
取各算法10次计算结果的平均值进行比较。记n为MAX－3－SAT实例中命题
变元的个数，m为其中的子句个数，于是利用各算法计算一系列随机生成的大规
模MAX－3－SAT实例的结果如下：
图1 n＝200时各算法对实例1－5的平均计算结果比较
图2 n＝400时各算法对实例1－5的平均计算结果比较
图3 n＝700时各算法对实例1－5的平均计算结果比较
在图1中，实例1－5的n＝200，m依次为400，500，600，700，800；在图
2中，实例1－5的n＝400，m 依次为900，1000，1100，1200，1300；在图
3中，实例1－5的n＝700，m 依次为1600，1700，1800，1900，2000。
从图1－图3中三个算法所得到的平均最优值可以看出：无论是n和m如何变化，
IBDE求得的平均最优值均优于GA和Johnson算法，并且与n和m之间的比值
无关；GA的计算结果也明显优于Johnson算法，而且也与n和m之间的比值无
关；Johnson算法的求解效果明显是三者中最差的，而且当m/n接近3时求解效
果是最差的。
上述计算结果的比较表明：对于随机大规模 MAX－k－SAT（k≥3）问题的求解，
IBDE是一种比GA和Johnson算法更有效的新方法；此外，从IBDE和GA的平
均求解结果均明显优于Johnson算法还可以看出，利用进化算法求解MAX－k－
SAT（k≥3）问题是一种比Johnson算法更行之效的方法。
4 结束语
本文基于动态变邻域搜索改进二进制差分演化算法的局部搜索能力，给出了一种求
解MAX－k－SAT问题的改进差分演化算法IBDE，通过利用一系列随机生成的大
规模 MAX－k－SAT实例与GA和Johnson算法的仿真计算比较表明：对于大规
模的随机MAX－k－SAT问题，IBDE算法不仅是可行的，而且是高效的。由于
HBDE是一种适于求解可行解能够表示为二进制编码的（动态）组合优化问题的算
法，今后将进一步探讨如何将其与DVNS有效结合以求解其它组合优化问题（例
如Knapsack问题和Partition问题等［7］）。
参考文献：
［1］徐宗本.计算智能—模拟进化计算［M］.北京：高等教育出版社，2005.
［2］陈国良，王熙法，庄镇泉，等.遗传算法及其应用［M］.北京：人民邮电出
版社，2003.
［3］， Ant Colony Optimization meta－
，，，New Ideas in ：
McGraw Hill，1999，11－32.
［4］贺毅朝，王熙照，寇应展.一种具有混合编码的二进制差分演化算法［J］.计
算机研究与发展.2007，44（9）：1476－1484。
［5］贺毅朝，王彦祺，寇应展.一种求解3－SAT问题新方法.计算机工程与应用
［J］.2006，42（16）：70－72.
［6］Frans Van den analysis of particle swarm optimizers
［PhD］.Pretoria：University of Pretoria，2001.
［7］Ding－Zhu Du，Ker－I Ko，Xiaodu and Analysis of
Approximation er Science Business Media，LLC，2012.
［8］Dorit um（Edited）.NP难解问题的近似算法.北京：世界图书出
版公司，1995.
［9］Storn R，Price ential Evolution—A simple and efficient
heuristic for global optimization over continuous l of Global
Optimization，1997，11：341－359.
［10］贺毅朝，王熙照，王彦祺，等.差分演化的收敛性分析与算法改进研究.软件
学报.2010，21（5）：875－885。
［11］堵丁柱，葛可一，王洁.计算复杂性导引［M］.北京：高等教育出版社，
2002.
［12］borty， and ，Differential Evolution with
Local Neighborhood［J］.in Congress on Evolutionary
Computation（CEC 2006），Vancouver，BC， Press，2006.
［13］张健.逻辑公式的可满足性判定―方法、工具及应用.北京：科学出版社，
2000.
2024年4月3日发(作者：飞伶俐)
利用改进的HBDE算法求解MAX-k-SAT问题
宋建民;苟海燕
【摘 要】目前,利用进化算法求解组合优化问题已成为智能计算领域中的研究热点.
本文基于二进制差分演化算法和动态变邻域搜索相结合提出了一种求解最大可满足
问题(MAX-k-SAT)的改进算法(记为IBDE),通过与遗传算法和Johnson算法对一
系列随机大规模MAX-k-SAT实例的求解比较表明:IBDE是一种求解MAX-k-SAT
问题非常有效的新方法.
【期刊名称】《河北省科学院学报》
【年(卷),期】2014(031)001
【总页数】7页(P1-7)
【关键词】二进制差分演化;变邻域搜索;组合优化问题;MAX-SAT问题
【作 者】宋建民;苟海燕
【作者单位】石家庄经济学院 数理学院,河北石家庄050031;石家庄经济学院华信
学院,河北新乐 050700
【正文语种】中 文
【中图分类】TP18
近年来，利用进化算法（Evolutionary Algorithms，EAs）求解NP完全问题
（NP Complete Problems，NPC）已成为智能计算领域的一个研究热点问题
［1］，例如利用遗传算法（Genetic algorithm，GA）［2］和蚁群算法（Ant
Colony Optimization，ACO）［3］求解旅行商问题（Traveling Salesman
Problem，TSP）、利用二进制差分演化算法 （Binary Differential Evolution
Algo－rithm with Hybrid Encoding，HBDE）［4］求解0－1背包问题（0－
1Knapsack Problem，0－1KP）以及利用二进制粒子群优化算法（Binary
Particle Swarm Optimization，BPSO）求解可满足问题（Satisfiability
Problem，SAT）和集合覆盖问题（Set Covering Problem，SCP）［5，6］等，
得到了许多满意的结果。本文研究利用HBDE求解在计算机科学中具有重要地位
的最大k－可满足问题（MAX－k－SAT，k≥3）［7］，通过将 HBDE与改进的
动态变邻域搜索（Dynamic Variable Neighborhood Search，DVNS）相结合，
提出了一种求解MAX－k－SAT的改进二进制差分演化算法（Improved Binary
Differential Evolution，IBDE）。对于一系列随机生成的大规模MAX－k－SAT
实例，通过与GA［2］和Johnson算法［8］的求解比较表明，本文方法是一种
求解该问题的可行且有效的新方法。
本文其余内容组织如下：在第1节中首先介绍HBDE算法，然后提出MAX－k－
SAT的最优化形式表示；在第2节中，首先给出一种动态变邻域搜索（DVNS），
然后基于 HBDE与DVNS相结合提出一种求解MAX－k－SAT的IBDE算法；接
着在第3节中，利用一系列随机生成的大规模MAX－k－SAT实例，分别利用
IDBE算法、Johnson算法和GA进行求解与比较；最后总结全文，并提出今后的
研究思路。
1 背景知识
1.1 HBDE算法
差分演化（Differential Evolution，DE）［9，10］是由 Rainer Storn和
Kenneth Price提出的一种EAs，在求解数值优化问题中表现突出，受到了广泛的
关注。贺毅朝等人利用混合编码方法提出了一种二进制差分演化算法（HBDE）
［4］，使得DE能够用于求解各种以二进制向量为可行解的组合优化问题（如0
－1KP，SAT和SCP等）。下面我们仅给出HBDE的算法伪代码描述，详细内容
请参考文献［4］。
设 HBDE的种群规模为N，n为解空间A＝｛0，1｝n与辅助搜索空间S＝［－
5.0，5.0］n 的维数。记第t代种群中第i个个体的混合编码为（Xi（t），Bi
（t）），其中 Xi（t）＝［xi1（t），xi2（t），…，xin（t）］∈S，Bi（t）＝
［bi1（t），bi2（t），…，bin（t）］∈A；记第t＋1代中间种群中第i个中间
个体的混合编码为（Vi（t＋1），Ei（t＋1）），其中Vi（t＋1）＝［vi1（t＋
1），vi2（t＋1），…，vin（t＋1）］∈B，Ei（t＋1）＝［ei1（t＋1），ei2（t
＋1），…，ein（t＋1）］∈A，1≤i≤N。令（Xbest（t），Bbest（t）为第t代
中的最好个体，ITE为HBDE的最大迭代次数，则求解最大优化问题maxf（X）
的HBDE的算法伪代码描述如下：
算法 Algorithm
在 HBDE中，p1≠p2≠p3≠i并且1≤p1，p2，p3，i≤N。参数α和CR 定义见文
献［4，9］；sig（x）＝1/（1＋e－x）是一个单调函数。显然，Step4－Step11
为 HBDE的一次进化迭代，因此算法1的时间复杂度为O（ITE＊N＊n）。此外，
算法1是采用DE/r/1/bin模式的，对于DE的其它各模式，只要修改Step6即可
得到相应模式的HBDE算法。
1.2 MAX－k－SAT问题
最大k－可满足问题（MAX－k－SAT，k≥3）［8，11］是计算机科学中一个具
有重要理论意义的NP完全问题（NPC），是著名的可满足性问题（SAT）［5，
11］的一种推广形式，在人工智能、机器学习、VLSI集成电路设计与检测和数据
库检索等方面有着重要应用。由于MAX－k－SAT是NPC问题，不存在多项式时
间确定算法，目前主要是利用进化算法［2，5］和近似算法［8］对其进行求解，
其中最著名的有GA和Johnson算法。下面先给出MAX－k－SAT的逻辑语言定
义，然后提出它的一种最优化形式表示方法。
令P＝｛p1，p2，…，pn｝是由n个不同的命题变元构成的集合，P中变元的一
个指派t＝（t1，t2，…，tn）是一个函数t：P→ ｛0，1｝。显然在P上存在2n
个不同的指派。对于仅含有P中变元的命题公式C，如果t（C）＝1，则称C在
指派t下是可满足的。一般地，我们将形如C＝pi1∨pi2∨ …∨pi r∨﹁pi，r＋1∨﹁
pi，r＋2∨ …∨﹁pi k的命题公式称为P 上的子句，其中pij∈P，k称为子句C的
长度；公式A＝C1∧C2∧…∧Ci∧…∧Cm称为P上的一个合式范式（Conjunctive
Normal Form，CNF），其中Ci（1≤i≤m）为P上的子句。
所谓MAX－k－SAT（k≥3）问题即为：给定P上的一个CNF A，其中A的每个
子句的长度均为k，判断是否存在一个指派t，使得A中可满足的子句个数最多，
并求出这个最值，即求及其相应指派t。
基于上述逻辑定义，我们提出MAX－k－SAT（k≥3）问题的一种最优化表示形式。
令M＝｛x1，x2，…，xn｝是由n个取值为0或1的整型变量构成的集合，其中
的xi对应于P中变元的pi，1－xi对应于﹁pi。于是对于P上的一个CNF A＝
C1∧C2∧…∧Ci∧…∧Cm，如果将其中的∨看成一种特殊加法，即1⊕0＝0⊕1＝
1⊕1＝1且0⊕0＝0，而将∧看成普通加法，则MAX－3－SAT中求以及相应指派
t的问题等价转换为一个求解定义在｛0，1｝n上的多项式函数f（X）的最大值及
其最优解的最优化问题。其中X＝［x1，x2，…，xn］∈｛0，1｝n，子句Ci＝
pi1∨pi2∨ …∨pi r∨﹁pi，r＋1∨﹁pi，r＋2∨ …∨﹁pi k 对应于f（X）中的项Ei
＝ ［xi1 ⊕xi2 ⊕ …⊕xi r ⊕ （1－xi，r＋1）⊕ （1－xi，r＋2）⊕ …⊕ （1－
xik）］，xij ∈M，且
例如：MAX－3－SAT问题CNF A＝ （﹁p1∨p2∨p3）∧ （p1∨ ﹁p2∨p3）∧
（p1∨p2∨﹁p3），它的8个指派依次为：t0 ＝ （0，0，0），t1 ＝ （0，0，
1），t2 ＝ （0，1，0），t3 ＝ （0，1，1），t4 ＝ （1，0，0），t5 ＝ （1，
0，1），t6 ＝ （1，1，0），t7 ＝ （1，1，1），其中t0，t3，t5，t6 和t7 使
得A中所有子句均满足，从而max∑3 i＝1tj（Cj）＝3，（其中j＝0，3，5，6，
7）。MAX－3－SAT实例CNF A可以等价转换为求解定义在｛0，1｝3上的多
项式函数f（X）＝ ［（1－x1）⊕x2⊕x3］＋［x1⊕ （1－x2）⊕x3］＋
［x1⊕x2⊕（1－x3）］的最值的最优化问题。
对于含有n个不同命题变元的MAX－k－SAT问题，利用强力搜索法求解需要分
别计算2n个指派满足的子句个数，计算时间复杂性为O（2n），显然是不可取的，
因此我们在下面将介绍一种基于HBDE求解MAX－k－SAT问题的有效方法。
2 求解MAX－k－SAT问题的IBDE算法
为了改善HBDE在求解MAX－k－SAT问题时的搜索效果，下面首先给出一种局
部优化方法：动态变邻域搜索算法（Dynamic Variable Neighborhood Search，
DVNS），在此基础上，将HBDE与DVNS相结合提出一种求解MAX－k－SAT
问题的有效方法。
变邻域搜索（Variable Neighborhood Search，VNS）是 Hansen等［12］提
出的一种 Meta－Heuristic算法，已被广泛应用于求解各种NPC问题。与传统的
单一邻域结构所不同的是：VNS首先预定义一系列的邻域结构，并且在搜索中先
由某个邻域开始，按照一定的次序系统性地不断变化邻域的搜索范围，直到有更好
的解产生为止。
在VNS中，最主要的问题是确定邻域的结构、数量以及各邻域在搜索中应用的次
序与在搜索失败时邻域的改变策略，特别是邻域搜索范围的改变策略，其优劣程度
直接决定着其应用的成败。借鉴VNS的思想，为避免HBDE陷入局部最优的情况
发生，下面对于解为二进制向量的最大优化问题maxf（X），给出一种基于局部
随机邻域变化搜索的动态变邻域搜索算法（DVNS）。令L1与L2为随机产生的1
到n之间的两个随机整数，并且满足1≤L2－L1≤n/4，于是DVNS的算法伪代码
描述如下：
算法（X，n）Algorithm
在算法2中，rand［1，n］表示随机产生一个1到n之间的随机整数；X＝［x1，
x2，…，xn］为输入向量，Y＝［y1，y2，…，yn］为输出向量。显然，算法2的
时间复杂性为O（n）。
进化算法的全局搜索能力虽然较强，但其局部搜索能力往往不足［2］。为此，下
面将DVNS与HBDE相结合提出一种用于求解MAX－k－SAT问题的改进二进制
差分演化算法（Improved Binary Differential Evolution，IBDE），以加强差分
演化的局部搜索能力。为了有效地将HBDE与DVNS结合，不必对HBDE的每一
个个体均利用DVNS进行局部优化，而是根据种群的规模随机地选择一定数量
（通常≤N/3，其中N为种群规模）的个体进行优化，这样既提高了算法的局部搜
索，同时又兼顾了算法的效率。下面即给出HBDE与DVNS结合求解MAX－k－
SAT问题的算法IBDE的伪代码描述。
算法 Algorithm
在算法3中，rand（0，1）表示随机产生的一个0与1之间的随机数。由于在算
法3中只利用DVNS对不超过1/3的个体随机进行了局部优化，因此算法3的时
间复杂性为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求解时，同样按照算法3的方法将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
问题［13］，因此将利用随机生成的大规模MAX－3－SAT实例进行仿真计算。
由于IBDE、Johnson和GA均为随机近似算法，对于每一个MAX－3－SAT实例，
取各算法10次计算结果的平均值进行比较。记n为MAX－3－SAT实例中命题
变元的个数，m为其中的子句个数，于是利用各算法计算一系列随机生成的大规
模MAX－3－SAT实例的结果如下：
图1 n＝200时各算法对实例1－5的平均计算结果比较
图2 n＝400时各算法对实例1－5的平均计算结果比较
图3 n＝700时各算法对实例1－5的平均计算结果比较
在图1中，实例1－5的n＝200，m依次为400，500，600，700，800；在图
2中，实例1－5的n＝400，m 依次为900，1000，1100，1200，1300；在图
3中，实例1－5的n＝700，m 依次为1600，1700，1800，1900，2000。
从图1－图3中三个算法所得到的平均最优值可以看出：无论是n和m如何变化，
IBDE求得的平均最优值均优于GA和Johnson算法，并且与n和m之间的比值
无关；GA的计算结果也明显优于Johnson算法，而且也与n和m之间的比值无
关；Johnson算法的求解效果明显是三者中最差的，而且当m/n接近3时求解效
果是最差的。
上述计算结果的比较表明：对于随机大规模 MAX－k－SAT（k≥3）问题的求解，
IBDE是一种比GA和Johnson算法更有效的新方法；此外，从IBDE和GA的平
均求解结果均明显优于Johnson算法还可以看出，利用进化算法求解MAX－k－
SAT（k≥3）问题是一种比Johnson算法更行之效的方法。
4 结束语
本文基于动态变邻域搜索改进二进制差分演化算法的局部搜索能力，给出了一种求
解MAX－k－SAT问题的改进差分演化算法IBDE，通过利用一系列随机生成的大
规模 MAX－k－SAT实例与GA和Johnson算法的仿真计算比较表明：对于大规
模的随机MAX－k－SAT问题，IBDE算法不仅是可行的，而且是高效的。由于
HBDE是一种适于求解可行解能够表示为二进制编码的（动态）组合优化问题的算
法，今后将进一步探讨如何将其与DVNS有效结合以求解其它组合优化问题（例
如Knapsack问题和Partition问题等［7］）。
参考文献：
［1］徐宗本.计算智能—模拟进化计算［M］.北京：高等教育出版社，2005.
［2］陈国良，王熙法，庄镇泉，等.遗传算法及其应用［M］.北京：人民邮电出
版社，2003.
［3］， Ant Colony Optimization meta－
，，，New Ideas in ：
McGraw Hill，1999，11－32.
［4］贺毅朝，王熙照，寇应展.一种具有混合编码的二进制差分演化算法［J］.计
算机研究与发展.2007，44（9）：1476－1484。
［5］贺毅朝，王彦祺，寇应展.一种求解3－SAT问题新方法.计算机工程与应用
［J］.2006，42（16）：70－72.
［6］Frans Van den analysis of particle swarm optimizers
［PhD］.Pretoria：University of Pretoria，2001.
［7］Ding－Zhu Du，Ker－I Ko，Xiaodu and Analysis of
Approximation er Science Business Media，LLC，2012.
［8］Dorit um（Edited）.NP难解问题的近似算法.北京：世界图书出
版公司，1995.
［9］Storn R，Price ential Evolution—A simple and efficient
heuristic for global optimization over continuous l of Global
Optimization，1997，11：341－359.
［10］贺毅朝，王熙照，王彦祺，等.差分演化的收敛性分析与算法改进研究.软件
学报.2010，21（5）：875－885。
［11］堵丁柱，葛可一，王洁.计算复杂性导引［M］.北京：高等教育出版社，
2002.
［12］borty， and ，Differential Evolution with
Local Neighborhood［J］.in Congress on Evolutionary
Computation（CEC 2006），Vancouver，BC， Press，2006.
［13］张健.逻辑公式的可满足性判定―方法、工具及应用.北京：科学出版社，
2000.