两种智能值排序启发式研究

王海燕，管 莹，李 闯，杨明明

(1.吉林师范大学计算机学院，吉林四平136000;2.吉林大学计算机科学与技术学院，长春130012; 3.阜新高等专科学校计算机信息技术系，辽宁阜新123000)

两种智能值排序启发式研究

王海燕1，2，管 莹3，李 闯2，杨明明2

(1.吉林师范大学计算机学院，吉林四平136000;2.吉林大学计算机科学与技术学院，长春130012; 3.阜新高等专科学校计算机信息技术系，辽宁阜新123000)

为提升约束满足问题求解效率，对最受推崇的智能值排序启发式Look-ahead和Survivors-first进行深入研究。比较两种值排序启发式在常规和自适应两种环境下的效率表现。结果显示，在多数问题类上，常规情况下Survivors-first效果更好，而在自适应环境下效率有所下降;在不同环境下使用不同启发式可提升约束满足问题求解效率。

约束满足问题;约束求解;值排序启发式;效率

0 引 言

约束满足问题(CSP:Constraint Satisfaction Problems)［1］一直是人工智能的一个重要研究方向，相关技术被广泛应用于航天、配置及组合问题求解等领域。约束求解是CSP的关键问题，其效率备受瞩目。经典的求解基于回溯搜索与约束传播的结合模式，搜索过程在分支策略与变量排序启发式(VOH: Variable Ordering Heuristic)和值排序启发式(V-O-H:Value Ordering Heuristic)配合下探索问题的解。一段时间在某种程度上，V-O-H被忽略了，因为很多情况下它需要大量计算资源，但越来越多的研究证明，它是影响约束求解效率的一个重要因素。

V-O-H指变量选择值进行优先实例化的顺序，值排序的变化会直接影响搜索树各个结点产生分支的变化。值排序最初的评判依据是CSP解的数量［2］。随之，研究逐步扩展到借鉴贝叶斯网络思想增加判定准确性［3］，接着寻求策略选择对结果影响最大化的值［4］，但当遇到相当昂贵的开销问题时，降低开销的研究工作逐渐深入。一系列V-O-H被相继提出。这些V-O-H在不同情况下作用效果差异较大，尤其是新近推出的智能V-O-H，智能程度受环境影响明显。笔者意在找出智能V-O-H在何种情况下发挥最佳效果。

笔者详细说明了两种智能V-O-H。然后对智能V-O-H在常规和自适应方式下进行详细对比。最后对比较结果进行理论分析，并得出结论。

1 约束满足问题背景知识

一个CSP表示为一个三元组(X，D，C)，其中X={x1，…，xn}是n个变量的集合;D={D(x1)，…，D(xn)}是对应于每个变量的一组论域;C={c1，…，ce}是e个约束的集合。每个约束c表示为有序对(var(c)，rel(c))，其中var(c)={x1，…，xk}是X的一个有序子集，而rel(c)是D(x1)×…×D(xk)的子集。验证一个元组是否满足约束c的过程称为一次约束检查［5］。变量论域中值实例化的顺序影响CSP的求解效率，因此在搜索过程中经常会借助部分信息作启发性引导，确定论域中值选择的顺序，这种方式称为V-O-H。常用的V-O-H有lexico、look-ahead、impact［6］、survivors-first等。

Lexico是字典序V-O-H，顾名思义，变量论域各值按字典顺序排序。Lexico虽然使值选择有了某种顺序，但这种顺序没有智能参照搜索中的任意信息，不能把握搜索分支的动向。

人们研究发现，在求解CSP的搜索过程中，向前看可以得到许多有用信息，如通过发现冲突最少的值提高找到解的可能性、通过选择论域包含值最多的变量提高找到解的可能性等。Daniel等［4］在1995年就困难CSP提出一组向前看智能V-O-H(又称Look-ahead)。Look-ahead优先选择当前变量中与未来变量的某些值冲突最少的值进行实例化。符合Look-ahead思想的V-O-H有很多，例如MC(Min-Conflicts)、MD(Max-Domain-size)、WMD(Weighted-Max-Domain-size)、PDS(Point-Domain-Size)等，其中MC在实际应用中效果最为突出。MC被称为最小冲突启发式，是一种考虑相关联未实例化变量论域中与当前变量当前值不相容值的个数的V-O-H，论域中值的顺序按照此冲突个数升序排序，选择冲突个数最少的值优先实例化。

Look-ahead对大型或困难问题算法性能提升效果显著，但对简单可解决问题效果不明显。原因是实现起来稍复杂，有时还会引发许多额外开销;而对于求解较多的简单问题时，有许多可选择的值，求解过程可以近似无回溯建立搜索路径，这种检查每个变量每个值的额外开销则是多余的。

许多学者研究了多种方法用于降低这种开销，一种是使寻找值的信息学习过程更廉价。早期学习工作主要集中在nogoods上，即不参与解的实例化。它可使搜索避免对失败子树的再次探索，特别强调nogoods与restart［7］配合的效果更好。

直到2008年，Zhang等［8］提出一种自适应学习值排序方法Survivors-first(幸存者优先)。该方法在搜索中学习传播信息，廉价搜索那些常被幸存传播的值，用于加速个别问题求解。自此，自适应V-O-H的研究逐渐展开。Survivors-first的典型代表是选择R/S最低值值排序启发式(以下简称RSVO:RIS-Value-Ordering)，这种V-O-H用到R和S两个技术指标。其中R表示某值在传播过程中被移去的频率，S表示某值在传播过程中被挑战是否有支持的频率。此V-O-H的主导思想是，R越高，相容的可能性则越低; S越高，R对某值幸存能力认可的准确程度越强。RSVO选择常被挑战但很少被移去(R/S最低)的值进行优先实例化。

2 两种智能V-O-H间比较

对于Look-ahead值排序启发式和Survivors-first值排序启发式对约束求解效率的影响，笔者在前阶段已经做出深入的研究［9，10］，两种智能V-O-H对求解效率都有极大的提升作用。但对于两者性能比较并未做深入探讨。

为清楚了解二者间性能差异，方便对智能V-O-H的进一步创新，笔者将它们进行详细比较。测试环境仍然是主频1.90 GHz、内存1.00 GByte的DELL主机。不同的是，扩展研究标准测试库Benchmark中 7种测试类 Bqwh18_141、Driver、geom、QCPp-20、RlfapGraphs、Rlfap ModGraphs、RlfapModScens的Sat(可满足问题)和Unsat(不可满足问题)两类问题，并在每类中选取5种以上实例细化测试。

测试建立在两种程序环境下，第1种是普通的约束求解模式下，即在MAC过程引导的常规约束求解［11］;另一种是在自适应约束求解模式下，具体为在MAC过程中嵌入文献［12］中两种自适应启发式的析取。在这两种模式下，分别引入Look-ahead和Survivors-first两种智能V-O-H，比较分析两种智能V-O-H在两种模式下作用的不同。

2.1 常规模式下比较

常规模式是指普通MAC过程引导的约束求解过程，也就是将回溯搜索与弧相容约束传播交替结合，不断过滤不相容的论域值，并依据固定分支选择方式，借助某种VOH和V-O-H选择合适的变量和实例化论域值，增量扩展部分解为完全解或以失败告终。在此，限定VOH为备受关注的dom/wdeg，V-O-H则分别用Look-ahead和Survivors-first两种智能排序方式进一步引导。笔者得到的实验结果如表1和表2所示。

表1 Sat问题类在常规模式下的效率比对Tab.1 Comparison of sat on efficiency under the normal situation

表1和表2分别是Benchmark中几个典型实例类在常规模式下的效率比对(以时间消耗作为比较对象)，Sat问题类的Driver类中测试了6个实例，其中有5个实例Survivors-first的求解效率高于Look-ahead的求解效率。

从表1、表2的测试数据可以看出，除了QCPp-20的Easy类，其余的测试类借助Survivorsfirst V-O-H引导值选择排序的方式，效率均要高于Look-ahead引导的情况。这是由于Survivors-first在搜索的过程中，有效学习了传播信息，廉价搜索到了常被幸存传播的值用于加速个别问题求解，使约束求解的效率得到大幅提升。

而对于QCPp-20的Easy类，主要包括实例为qcp-order20-holes187-balanced-13-QWH-20、qcp-order20-holes187-balanced-14-QWH-20、qcp-order20-holes187-balanced-15-QWH-20、qcp-order20-holes187-balanced-16-QWH-20和qcp-order20-holes187-balanced-17-QWH-20。进一步分析此类问题，发现这些实例约束松紧度较低，即约束上禁止的值对个数少，相比于Hard类里的实例问题稍简单，较容易求解。带有学习过程的Survivors-first与无学习过程的Look-ahead对比便失去了优势。学习过程反而加重了时间消耗，因而效率降低。

基于求解过程所得数据，对于bqwh类中5个实例，也能够得出结论，简单的问题实例用Look-ahead V-O-H求解速度明显更快。Geo10问题类也是一样(由于篇幅有限，此部分数据未予给出)。

表2 Unsat问题类在常规模式下的效率比对Tab.2 Comparison of unsat on efficiency under the normal situation

2.2 自适应模式下比较

自适应模式是指在常规MAC过程引导的约束求解模式基础上，嵌入文献［12］中两种自适应启发式的析取应用模式(简记为Heur∨)，仍以增量扩展部分解为完全解或以失败告终为根本目标。VOH仍然启用dom/wdeg，在此基础上依次引入Look-ahead和Survivors-first两种智能V-O-H引导值选择过程。比较分析两种智能V-O-H，得到结果列入表3和表4。

表3 Sat问题类在自适应模式下的效率比对Tab.3 Comparison of Sat on efficiency under the adaptive circumstance

表3中Driver和QCPp-20中各有3个实例由常规下Survivors-first的效果好，转变成自适应模式下Look-ahead效果胜出。表4的两个类中也分别有2和1个实例发生了同样的效果转变。究其原因可知，依据Heur∨指导下的自适应约束求解模式将一部分时间放在自适应启发式的判断上，虽然在自适应过程后，启发式有效地选择了一种分支方式继续求解，但在判断两种自适应启发式满足其一与否的过程中，消耗了相对多的时间;而在这些实例上，Look-ahead搜寻的信息又恰好相对有效地减少了回溯次数，所以求解效率发生了逆转。总结自适应模式下两种智能V-O-H引导值选择的规律可见，在常规模式下，Survivors-first在稍难问题实例求解上相对于Look-ahead效果要更好，而在自适应模式下却加重了搜索负担，所以效率下降。而Look-ahead则适用于求解相对简单的问题实例。

表4 Unsat问题类在自适应模式下的效率比对Tab.4 Comparison of Unsat on efficiency under the adaptive circumstance

3 特殊实例分析

在测试中，有几类实例效果与其他实例差别很大(见表5、表6)，即RlfapGraphs、RlfapModGraphs和RlfapModScens这3类与其他类差别大。常规模式下，Look-ahead的效果明显，自适应环境下，效果也很好，尤其是RlfapModGraphs类，特点更明显。这与3类问题的结构密切相关。

表5 Sat中特殊问题类Tab.5 Special problems in Sat

表6 Unsat中特殊问题类Tab.6 Special problems in Unsat

为探究问题的结构，笔者借助C++语言，以RlfapModGraphs中Sat类里的实例graph2_f24、graph8_ f10、graph14_f27为例(这3个实例应用 Look-ahead效果更突出)，绘制的3个实例问题的结构图如图1所示。

图1 3个实例问题结构Fig.1 Structure of three problem

图1中每条弧对应一个约束，弧的颜色深浅反映了弧的松紧度，也就是禁止值对数，即弧的颜色越深，其松紧度越大。从图1可以看出，这3个实例的结构，约束松紧度不高，密度较高。因此，在常规模式下，Look-ahead效果更突出(结合3个实例在两种模式下的运行时间可以看出，如表7所示)。同时还可以看到，graph8_f10和graph14_f27的密度比graph2_f24高，所以在自适应模式下graph2_f24发生逆转，Survivors-first效率明显。而graph8_f10和graph14_f27两个实例在Look-ahead下的效率没有变化。

表7 3个实例在两种模式下的运行时间比对Tab.7 Comparison of three examples runtime under twomodes

4 结 语

鉴于值排序启发式对约束满足问题求解效率的影响，笔者在现有约束求解方法基础上，分别在常规和自适应两种模式下，比较了Look-ahead值排序启发式和Survivors-first值排序启发式两种智能值排序启发式的效率表现。为全面表现两种V-O-H的特性，验证过程建立在Bqwh18_141、Driver、Geom、QCPp-20、RlfapGraphs、RlfapModGraphs、RlfapModScens7类问题上，并且包含Sat和Unsat两个方面。实验数据表明:在多数问题类上，常规情况下Survivors-first效果要更好些，而在自适应环境下Survivors-first加重了搜索负担，所以效率有所下降。

［1］FRANCOIS ROSSI，PETER VAN BEEK，TOBY WALSH.Handbook of Constraint Programming［M］.Amsterdam，Netherland:Elsevier，2006.

［2］RINA DECHTER，JUDEA PEARL.Network-Based Heuristics for Constraint Satisfaction Problems［J］.Artificial Intelligence，1988，34(1):1-38.

［3］AMNON MEISELS，SOLOMON EYAL SHIMONY，GADISOLOTOREVSKY.Bayes Networks for Estimating the Number of Solutions to a CSP［C］∥Proceedings of AAAI-1997.California:AAAIPress/the MIT Press，1997:185-190.

［4］DANIEL FROST，RINA DECHTER.Look-Ahead Value Ordering for Constraint Satisfaction Problems［C］∥Proceedings of IJCAI-1995.San Francisco:Morgan Kaufmann，1995:572-578.

［5］EFSTATHIOS STAMATATOS，KOSTAS STERGIOU.Learning How to Propagate Using Random Probing［C］∥Proc of CPAIOR.New York:Springer-Verlag，2009:263-278.

［6］PHILIPPE REFALO.Impact-Based Search Strategies for Constraint Programming［C］∥Proceedings of CP-2004.New York: Springer-Verlag，2004:556-571.

［7］CHRISTOPHE LECOUTRE，LAKHDAR SAIS，SÉBASTIEN TABARY，et al.Nogood Recording from Restarts［C］∥Proceedings of IJCAI-2007.New York:Springer-Verlag，2007:131-136.

［8］ZHANG Zhijun，SUSAN L EPSTEIN.Learned Value-Ordering Heuristics for Constraint Satisfaction［C］∥Proceedings of AAAI-2008.California:AAAIPress，2008:154-161.

［9］王海燕，欧阳丹彤，张永刚，等.结合 Look-ahead值排序的自适应分支求解算法 ［J］.通信学报，2013，34(6):102-107. WANG Haiyan，OUYANG Dantong，ZHANG Yonggang，et al.Novel Adaptive Branching Constraint Solving Algorithm with Look-Ahead Strategy［J］.Journal on Communications，2013，34(6):102-107.

［10］王海燕，李闯，张良.Dom/ddeg自主分支辅助决策约束求解［J］.吉林大学学报:理学版，2014，52(6):1289-1292. WANG Haiyan，LIChuang，ZHANG Liang.Autonomous-Branching Constraint Solving Aided by Dom/ddeg Decision Making［J］.Journal of Jilin University:Science Edition，2014，52(6):1289-1292.

［11］LIKITVIVATANAVONG C，ZHANG YL，BOWEN J，etal.Arc Consistency During Search［C］∥Proc of IJCAI.New York: Springer-Verlag，2007:137-142.

［12］THANASIS BALAFOUTIS，KOSTAS STERGIOU.Adaptive Branching for Constraint Satisfaction Problems［C］∥Proc of ECAI.Amsterdam:IOSPress，2010:855-860.

(责任编辑:刘俏亮)

Research on Two Intelligent Value Ordering Heuristics

WANG Haiyan1，2，GUAN Ying3，LIChuang2，YANG Mingming2

(1.College of Computer，Jilin Normal University，Siping 136000，China; 2.College of Computer Science and Technology，Jilin University，Changchun 130012，China; 3.Technology of Computer Information System，Fuxin Higher Training College，Fuxin 123000，China)

It is important to select appropriate value ordering heuristics，as it influences the efficiency of constraint solving deeply.In this paper，two of the most respected intelligent value ordering heuristics are researched in depth.One is look-ahead value ordering heuristic，the other is survivors-first value ordering heuristic.The efficiency of the two kinds of value ordering heuristics are compared under the normal situation and the adaptive circumstance.The results display that survivors-first is better than look-ahead under normal environment，but decline in efficiency under adaptive situation.So we can choose different intelligent value ordering heuristics to achieve better property in different enviroments.

constraint satisfaction problem;constraint solving;value ordering heuristics;efficiency

TP31

A

1671-5896(2015)04-0416-05

2015-02-14

国家自然科学基金资助项目(61373052;61100090;61170314;41172294);吉林省教育厅“十二五”科学技术研究基金资助项目(［2011］第415号;［2014］第490号);四平市科技发展计划基金资助项目(2012042);吉林省科技厅自然科学基金资助项目(201115220);吉林省科技发展计划基金资助项目(20140101206JC-06;20140101206JC-15);吉林师范大学博士启动基金资助项目(2013018);吉林师范大学硕士启动基金资助项目(2009035)

王海燕(1980—)，女，吉林白城人，吉林师范大学讲师，博士，主要从事约束求解与约束优化、约束程序设计研究，(Tel) 86-15044125882(E-mail)jlsdwhy_0820@sina.cn。