基于AC与LmaxRPC的自适应约束传播求解算法

王海燕　欧阳丹彤　张永刚　杨明明

摘 要：在现有自适应约束求解方法基础上，提出一种新的自适应约束传播求解算法ADAPTACLmaxRPC.该算法能根据约束的不同特性，在传播能力强但开销高的LmaxRPC与传播能力弱却开销低的AC之间自适应地切换进行约束传播.多个Benchmark实例类上的测试实验数据表明，ADAPTACLmaxRPC算法有效地平衡了求解效率和算法开销之间的矛盾，大幅度提高了约束求解的效率.

关键词：人工智能；约束程序；约束满足问题；自适应约束求解；约束传播

中图分类号：TP31 文献标识码：A

Adaptive Constraint Propagation Solving

Based on AC and LmaxRPC

WANG Haiyan1，2，3，OUYANG Dantong1，2，ZHANG Yonggang1，2，YANG Mingming 1，2

（1.College of Computer Science and Technology， Jilin Univ， Changchun，Jilin 130012， China；

2.Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education， Jilin Univ，

Changchun，Jilin 130012， China； 3. College of Computer， Jilin Normal Univ， Siping，Jilin 136000， China）

Abstract：On the basis of the current adaptive constraint solving algorithms， this paper proposed a new adaptive constraint propagation solving algorithm ADAPTACLmaxRPC， which adaptively switches between enforcing a strong and expensive local consistency LmaxRPC and a weak but more cheaper one AC according to the activity of individual constraints. Test data from several Benchmark instances shows that ADAPTACLmaxRPC balances the contradiction between the constraint solving efficiency and algorithm cost effectively， and it improves the efficiency of constraint solving substantially.

Key words：artificial intelligence； constraint programming； constraint satisfaction problem； adaptive constraint solving； constraint propagation

近年来，由于具有浓厚产业背景和重大商业价值，约束程序（Constraint Programming，CP）研究得到蓬勃发展，并已成为问题建模及求解如资源分配、调度问题、时序推理、规划和图着色等领域困难组合问题的典范.约束满足问题（Constraint Satisfaction Problem，CSP）^{[1] 是约束程序的核心，自提出以来受到了广泛关注.国内外有很多学者致力于这方面的研究，主要的工作有约束程序理论、设计与应用的研究、约束归纳逻辑程序设计等方面，以及CSP求解研究等[2].其中，CSP的求解一直是人工智能领域研究的热点，具有重要的理论研究和实际应用价值.}

CSP的主要推理技术是约束传播，它对约束程序的成功与否起着至关重要的作用，是影响约束求解算法效率和适应性的关键因素.因此，多种约束传播技术应运而生^{[3]，包括早期的FC，广泛使用的GAC，以及maxRPC，SAC等.虽然约束传播技术选择丰富，但简单的约束求解器通常在整个搜索过程中对所有的约束都使用同一个标准方法.由于不同约束的删除能力各不相同，同一种约束传播技术很难适用于所有约束.比如，如果为很少或不删除值的约束选用了一种过滤能力很强的约束传播方法，必然会导致不必要的CPU开销.所以，考虑到时间和空间复杂性，尽量想为删除能力强的约束选择过滤能力强的约束传播方法，为删除能力弱的约束选择过滤能力弱的约束传播方法.因此，如何在搜索中为约束动态选择约束传播方法成为一个重要的研究方向.}

随着约束求解方法的发展，“自适应”概念越来越受到人们关注.这一概念的出现使“动态”选择约束传播方法成为可能.越来越多研究者开始考虑从问题的结构化信息入手，从CSP求解的各个角度提出具有更强适应性的自适应约束求解方法，最终从根本上提高算法的效率和“智能性”.在众多自适应约束求解方法中，自适应约束传播约束求解方法另辟蹊径，在效率上取得了突破^{[4-8].尤其是文献[8]中提出的4种自适应启发式，根据域空（Domain Wipeout，DWO）和值删除（Deletion）这些信息，在强弱约束传播方法之間切换，为自适应约束传播方法的进一步发展奠定了坚实的基础.}

本文提出一种为不同约束自动选择传播技术的动态自适应约束传播方法ADAPTACLmaxRPC.利用[8]中提出的启发式H1，H2，H3，H4及它们的析取和合取应用，根据条件满足与否动态在强却开销高的约束传播方法和弱但开销低的约束传播方法之间切换.实验限定在二元问题上，用AC为弱相容（W），LmaxRPC为强相容（S）.在Benchmark多类问题上对ADAPTACLmaxRPC算法进行了详细的实验评估，实验结果证实了ADAPTACLmaxRPC算法的有效性，且具有很强的竞争力.

1 背 景

maxRPC是一种比AC具有更强删除能力的局部相容技术.然而，现有maxRPC算法受开销和冗余的困扰，因为算法中重复执行许多不能触发任何Deletion的约束检查.因此，在搜索中运用maxRPC与应用AC相比虽然节省了搜索树的空间，但减慢了搜索过程.LmaxRPC是maxRPC的近似算法，它仅传播AC支持的丢失，而不传播PC证人的丢失.LmaxRPC相对于maxRPC来说取得了低层次的相容，但仍比AC强，而且当用于搜索中时，比maxRPC更划算.多个文献^{[10-11]的实验证实，LmaxRPC确实是一个比maxRPC更好的选择.例如[10]中通过利用支持的余数和一个回溯表以及高效的数据结构改善了maxRPC的性能，提出了LmaxRPCrm.[11]中提出的LmaxRPC3和LmaxRPC3rm利用数据结构，通过删除一些冗余来保证低的空间复杂性.虽然仅在实际中少删了一点值，却可以避免许多冗余的约束检查，进而提高了搜索速度.}

在自适应约束传播中，首要问题是基本传播方法的选择.既要考虑约束传播方法删除能力的差异，又要考虑其执行开销.鉴于AC，maxRPC和LmaxRPC三者的特性，考虑在AC和LmaxRPC之间进行自适应约束传播.其次，自适应启发式能在不同约束传播方法之间起到导向作用，选择一个合适的自适应启发式是自适应约束传播方法成功的关键.文献[8]4种自适应启发式利用DWO和Deletion这些反应约束活跃程度的关键信息，在不同约束传播方法之间自由导向，表现出良好的求解效率.

2 ADAPTACLmaxRPC自适应约束传播算法

为进一步提高自适应约束求解的效率，以AC為弱相容（W），LmaxRPC为强相容（S），并在自适应启发式H1，H2，H3，H4及其合取和析取应用（简记为：H∨12，表示H1和H2两种启发式的析取；H∨124，表示H1和H2，H43种启发式的析取；H∨134，表示H1和H3，H43种启发式的析取；H∧12，表示H1和H2两种启发式的合取）的指导下，研究了自适应约束传播算法ADAPTACLmaxRPC.

算法的输入为X，C，Q，H.其中Q为传播队列，H为某种自适应启发式，运用不同的自适应启发式，算法效率有很大差别.算法刚开始先把传播队列Q初始化为所有需要传播的约束集合，然后依次取出约束，根据启发式H选择强相容或弱相容方法进行约束传播.不论选择谁，只要校验之后变量论域改变，则根据变化程度判断是在传播队列中加入新的相关约束继续传播还是失败而终.直到Q中无待传播约束且x论域不再发生变化时，成功结束.步骤8中的更新过程，实为将所有与当前传播变量相关的其他约束放入Q的过程.

在步骤4用Revise（C， xi，LmaxRPC）进行强相容校验时，判断过程为：对当前变量xi论域中每个值，若不是AC的，则被删除；若是AC的，则用LmaxRPC相容方法再校验一次是否也有支持.即，当前变量xi论域中所有值校验完毕后，剩下的值都是LmaxRPC的.而在步骤5的用Revise（C， xi，AC）进行弱相容校验时，判断过程为：对每个值，如果没有AC支持，则从当前变量xi论域中删除；若有AC支持，接着判断下个值，直到论域中所有值都用AC校验一遍后，才判断是否用强相容校验.即，只有当AC删除了值时，才用LmaxRPC校验，而如果AC相容未删除任何值，那么所有值都是AC的，则不再用LmaxRPC继续校验，即最后当前变量xi论域中剩余值一定是AC的，却不一定是LmaxRPC的，因此Revise（C， xi，AC）比Revise（C， xi，LmaxRPC）要弱一些，详细的Revise过程可参看文献[8].

3 实验结果

为验证ADAPTACLmaxRPC算法的优势，本文采用Christophe Lecoutre整理的多个Benchmark问题实例^{[3]来对其进行测试.算法采用dway[12]分支，dom/wdeg[13]变量排序启发式和字典序值排序启发式.LmaxRPC用的是LmaxRPC3的rm版本[11].具体选择的问题实例类有qcp15， qwh20， frb3015， bqwh15_106， rlfapGraphs， rlfapScens， rlfapModGraphs等.所有实验都是在主频为1.60 GHz，内存为1.99 GB，操作系统为Microsoft Windows XP Professional的电脑上完成的.测试环境为Eclipse，编程语言为VC++.将ADAPTACLmaxRPC应用于搜索中，并和单独维持AC及LmaxRPC的算法进行比较，综合考查CPU时间开销（简记为time，单位：s）、约束检查次数（简记为#ccks）和搜索树生成节点数（简记为#nodes）三项技术指标，得到两组实验结果.}

第一组数据是应用了ADAPTACLmaxRPC算法之后，约束求解效率相对于在搜索中单独维持AC或LmaxRPC算法有大幅度提高的实例类结果，如表1、表2所示.表1为单独应用4种启发式与AC和LmaxRPC对比的结果，而表2为4种启发式的析取及合取应用与AC和LmaxRPC的对比结果.2个表中从第二列到最后一列分别表示用各种约束传播方法进行约束求解的情况，其中4种启发式及其合取和析取应用分别表示用这些启发式来引导自适应约束传播搜索.这类结果表明，应用了自适应约束传播求解方法之后，虽然自适应约束传播方法得到的实验结果不是最优的，但相比于单独维持AC或LmaxRPC的情况，效率上都有实质性提高.即，ADAPTACLmaxRPC算法集合了AC和LmaxRPC的优点，在保证了求解效率的同时，适当避免了开销和冗余的困扰，减少了二者之间的矛盾.例如，qcporder15holes120balanced21QWH15实例中，几种自适应约束传播求解算法的CPU运行时间均远小于单独维持LmaxRPC的运行时间1 028.75 s，最好情况是563.06 s，接近于单独维持AC的运行时间508.39.另外，实例le4505a4ext.txt中单独维持AC情况的运行时间超过了两个小时，而自适应约束传播求解方法的最好情况是1369.22 s，相对前者提高了6倍左右.表中的CPU运行时间取的是十次运行的平均值. 在上组实验基础上继续展开，得到第二组实验结果.此组结果显示的是应用ADAPTACLmaxRPC算法之后，自适应约束传播求解方法的综合效率明显优于在搜索中单独维持AC或LmaxRPC算法的测试实例，如表3、表4所示.表3为单独应用4种自适应启发式的求解算法与维持AC和LmaxRPC算法性能对比结果，而表4为4种启发式的析取及合取应用对应的算法与维持AC和LmaxRPC算法性能对比结果.CPU时间开销最好情况均加粗显示.

表3 ADAPTACLmaxRPC自适应约束传播算法与维持AC和LmaxRPC算法性能对比（1）

Tab.3 The performance comparison of ADAPTACLmaxRPC， AC and LmaxRPC（1）

实例qcporder15holes120balanced20QWH15中，自适应约束传播算法最好情况下（H∧12的8.375 s）比AC的70.766 s提高了近9倍，比LmaxRPC的65.75 s提高了7倍多，实例frb30155bis的最好自适应方式也比单独应用AC或LmaxRPC情况提高了近三倍.从这些数据上可进一步看出，应用自适应约束传播求解算法，在遇到特定约束后，ADAPTACLmaxRPC能根据需要适应到最合适的约束传播方法，因此，有效提高了约束求解的效率.此外，从综合实力上讲，4种启发式的析取形式相比于单独应用4种启发式及其合取形式，更能准确探查出更合适的约束传播方法，而启发式的合取在某些特例上效率提高幅度比较明显.例如在frb30155bis实例上，单独应用4种启发式的效率没有析取应用的效率高，合取应用的效率也相对析取应用稍逊一点，但合取应用在qcporder15holes120balanced20QWH15实例上的表现却尤为突出，这和问题本身结构有关.

综合考虑以上各实验数据，可发现，新提出的自适应约束传播求解算法ADAPTACLmaxRPC有很强的竞争优势.原因是：ADAPTACLmaxRPC能够利用强弱约束传播方法的优点，在遇到某个特定约束后，根据约束的特性，自适应的选择合适的约束传播方法，即为删除能力强的约束选择过滤能力强的约束传播方法，而为删除能力弱的约束选择过滤能力弱的约束传播方法，最终实现在保证求解效率的同时，有效避免求解效率和算法开销间矛盾的目的.算法ADAPTACLmaxRPC不论从CPU时间开销上，还是从约束检查次数以及搜索树生成节点数上，综合性能都以较大优势胜出.

4 总 结

本文在现有约束传播方法研究的基础上，提出一种自适应约束传播求解算法ADAPTACLmaxRPC，它根据搜索过程中探查到的约束活跃程度（Deletion个数及DWO次数），并借助于自适应启发式，在强约束传播方法（LmaxRPC）和弱约束传播方法（AC）之间灵活切换，从根本上提高约束求解效率.来自于多个Benchmark实例类上的实验数据表明，ADAPTACLmaxRPC算法实现了降低求解效率和算法开销之间矛盾的目的，整体性能明显优于在搜索中单独维持AC和LmaxRPC的算法.未来工作考虑将此算法与我们改进的自适应分支求解算法进行求解效率的比较分析，并更深入研究将学习型自适应约束传播^{[14]应用到约束求解中.}

参考文献

[1] ROSSI F， BEEK P V， WALSH T. Handbook of constraint programming[M]. Amsterdam， Netherland： Elsevier， 2006： 1-85.

[2] 王秦辉，陈恩红，王煦法. 分布式约束满足问题研究及其进展[J]. 软件学报， 2006， 17（10）： 2029-2039.

WANG Qinghui， CHEN Enhong， WANG Xufa. Research and development of distributed constraint satisfaction problems[J]. Journal of Software， 2006， 17（10）： 2029-2039.（In Chinese）

[3] CHRISTOPHE Lecoutre. Constraint networks： techniques and algorithms[M]. London， UK： Wiley， 2009： 39-353.

[4] SAKKOUT H E， WALLACE M G， RICHARDS E B. An instance of adaptive constraint propagation[C]// Proceedings of CP-96. Cambridge， Massachusetts， USA， 1996：164-178.

[5] FREUDER E C， WALLACE R J. Selective relaxation for constraint satisfaction problems[C]// Proceedings of the Third International IEEE Computer Society Conference on Tools for Artificial Intelligence. San Jose， USA， 1991：332-339.

[6] SCHULTE C， STUCKEY P J. Speeding up constraint propagation[C]// Proceedings of CP2004. Toronto， Canada， 2004： 619-633.

[7] MEHTA D， DONGEN Mrc V. Probabilistic consistency boosts MAC and SAC[C]// Proceedings of IJCAI2007. Hyderabad， India， 2007： 143-148.

[8] STERGIOU K. Heuristics for dynamically adapting propagation[C]// Proceedings of ECAI2008. Patras， Greece， 2008： 485-489.

[9] DEBRUYNE R， BESSI`ERE C. From restricted path consistency to maxrestricted path consistency[C]// Proceedings of CP97. Schloss Hagenberg， Austria， 1997： 312-326.

[10]VION J， DEBRUYNE R. Light algorithms for maintaining maxRPC during search[C]// Proceedings of SARA2009. Lake Arrowhead， CA， 2009： 167-174.

[11]BALAFOUTIS T， PAPARRIZOU A， STERGIOU K， et al. Improving the performance of maxRPC[C]// Proceedings of CP2010. St Andrews， Scotland， 2010： 69-83.

[12]BALAFOUTIS T， PAPARRIZOU， STERGIOU K. Experimental evaluation of branching schemes for the CSP[C]// Proceedings of the TRICS workshop at CP2010. St Andrews， Scotland， 2010： 1-12.

[13]BOUSSEMART F， HEREMY F， LECOUTRE C， et al. Boosting systematic search by weighting constraints[C]// Proceedings of ECAI2004. Valencia， Spain， 2004：482-486.

[14]STAMATATOS E， STERGIOU K. Learning how to propagate using random probing[C]// Proceedings of CPAIOR2009. Pittsburgh， PA， USA， 2009： 263-278.