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

1、1基于 AC 与 LmaxRPC 的自适应约束传播求解算法摘 要：在现有自适应约束求解方法基础上，提出一种新的自适应约束传播求解算法 ADAPTACLmaxRPC.该算法能根据约束的不同特性，在传播能力强但开销高的 LmaxRPC与传播能力弱却开销低的 AC之间自适应地切换进行约束传播.多个 Benchmark实例类上的测试实验数据表明，ADAPTACLmaxRPC算法有效地平衡了求解效率和算法开销之间的矛盾，大幅度提高了约束求解的效率. 关键词：人工智能；约束程序；约束满足问题；自适应约束求解；约束传播 中图分类号：TP31 文献标识码：A Adaptive Constraint Propa

2、gation 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

3、Univ， Changchun，Jilin 130012， China； 3. College of Computer， Jilin Normal Univ， Siping，Jilin 136000， China） 2Abstract：On the basis of the current adaptive constraint solving algorithms， this paper proposed a new adaptive constraint propagation solving algorithm ADAPTACLmaxRPC， which adaptively switc

4、hes 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

5、 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）研究得到蓬勃

6、发展，并已成为问题建模及求解如资源分配、调度问题、时序推理、规划和图着色等领域困难组合问题的典范.约束满足问题（Constraint Satisfaction Problem，CSP）1 是约束程序的核心，自提出以来受到了广泛关注.国内外有很多学者致力于这方面的研究，主要的工作有约束程序理论、设计与应用的研究、约束归纳逻辑程序设计等方面，以及 CSP求解研究等2.其中，CSP 的求解一直是人工智能领域研究的热点，具有重要的理论研究和实际应用价值. 3CSP 的主要推理技术是约束传播，它对约束程序的成功与否起着至关重要的作用，是影响约束求解算法效率和适应性的关键因素.因此，多种约束传播技术应运而

7、生3，包括早期的 FC，广泛使用的 GAC，以及maxRPC，SAC 等.虽然约束传播技术选择丰富，但简单的约束求解器通常在整个搜索过程中对所有的约束都使用同一个标准方法.由于不同约束的删除能力各不相同，同一种约束传播技术很难适用于所有约束.比如，如果为很少或不删除值的约束选用了一种过滤能力很强的约束传播方法，必然会导致不必要的 CPU开销.所以，考虑到时间和空间复杂性，尽量想为删除能力强的约束选择过滤能力强的约束传播方法，为删除能力弱的约束选择过滤能力弱的约束传播方法.因此，如何在搜索中为约束动态选择约束传播方法成为一个重要的研究方向. 随着约束求解方法的发展， “自适应”概念越来越受到人们

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

9、8中提出的启发式 H1，H2，H3，H4 及它们的4析取和合取应用，根据条件满足与否动态在强却开销高的约束传播方法和弱但开销低的约束传播方法之间切换.实验限定在二元问题上，用 AC为弱相容（W） ，LmaxRPC 为强相容（S）.在 Benchmark多类问题上对ADAPTACLmaxRPC算法进行了详细的实验评估，实验结果证实了ADAPTACLmaxRPC算法的有效性，且具有很强的竞争力. 1 背 景 maxRPC 是一种比 AC具有更强删除能力的局部相容技术.然而，现有maxRPC算法受开销和冗余的困扰，因为算法中重复执行许多不能触发任何 Deletion的约束检查.因此，在搜索中运用 m

10、axRPC与应用 AC相比虽然节省了搜索树的空间，但减慢了搜索过程.LmaxRPC 是 maxRPC的近似算法，它仅传播 AC支持的丢失，而不传播 PC证人的丢失.LmaxRPC 相对于maxRPC来说取得了低层次的相容，但仍比 AC强，而且当用于搜索中时，比 maxRPC更划算.多个文献10-11的实验证实，LmaxRPC 确实是一个比maxRPC更好的选择.例如10中通过利用支持的余数和一个回溯表以及高效的数据结构改善了 maxRPC的性能，提出了 LmaxRPCrm.11中提出的LmaxRPC3和 LmaxRPC3rm利用数据结构，通过删除一些冗余来保证低的空间复杂性.虽然仅在实际中少删

11、了一点值，却可以避免许多冗余的约束检查，进而提高了搜索速度. 在自适应约束传播中，首要问题是基本传播方法的选择.既要考虑约束传播方法删除能力的差异，又要考虑其执行开销.鉴于 AC，maxRPC 和LmaxRPC三者的特性，考虑在 AC和 LmaxRPC之间进行自适应约束传播.其次，自适应启发式能在不同约束传播方法之间起到导向作用，选择一个合适的自适应启发式是自适应约束传播方法成功的关键.文献84 种自适5应启发式利用 DWO和 Deletion这些反应约束活跃程度的关键信息，在不同约束传播方法之间自由导向，表现出良好的求解效率. 2 ADAPTACLmaxRPC 自适应约束传播算法 为进一步提

12、高自适应约束求解的效率，以 AC为弱相容（W） ，LmaxRPC为强相容（S） ，并在自适应启发式 H1，H2，H3，H4 及其合取和析取应用（简记为：H12，表示 H1和 H2两种启发式的析取；H124，表示 H1和 H2，H43 种启发式的析取；H134，表示 H1和 H3，H43 种启发式的析取；H12，表示 H1和 H2两种启发式的合取）的指导下，研究了自适应约束传播算法 ADAPTACLmaxRPC. 算法的输入为 X，C，Q，H.其中 Q为传播队列，H 为某种自适应启发式，运用不同的自适应启发式，算法效率有很大差别.算法刚开始先把传播队列 Q初始化为所有需要传播的约束集合，然后依次

13、取出约束，根据启发式 H选择强相容或弱相容方法进行约束传播.不论选择谁，只要校验之后变量论域改变，则根据变化程度判断是在传播队列中加入新的相关约束继续传播还是失败而终.直到 Q中无待传播约束且 x论域不再发生变化时，成功结束.步骤 8中的更新过程，实为将所有与当前传播变量相关的其他约束放入 Q的过程. 在步骤 4用 Revise（C， xi，LmaxRPC）进行强相容校验时，判断过程为：对当前变量 xi论域中每个值，若不是 AC的，则被删除；若是 AC的，则用 LmaxRPC相容方法再校验一次是否也有支持.即，当前变量 xi论域中所有值校验完毕后，剩下的值都是 LmaxRPC的.而在步骤 5的

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

15、TACLmaxRPC算法的优势，本文采用 Christophe Lecoutre整理的多个 Benchmark问题实例3来对其进行测试.算法采用dway12分支，dom/wdeg13变量排序启发式和字典序值排序启发式.LmaxRPC用的是 LmaxRPC3的 rm版本11.具体选择的问题实例类有qcp15， qwh20， frb3015， bqwh15_106， rlfapGraphs， rlfapScens， rlfapModGraphs等.所有实验都是在主频为 1.60 GHz，内存为 1.99 GB，操作系统为 Microsoft Windows XP Professional的电脑上完

16、成的.测试环境为 Eclipse，编程语言为 VC+.将 ADAPTACLmaxRPC应用于搜索中，并和单独维持 AC及 LmaxRPC的算法进行比较，综合考查CPU时间开销（简记为 time，单位：s） 、约束检查次数（简记为#ccks）和搜索树生成节点数（简记为#nodes）三项技术指标，得到两组实验结果. 第一组数据是应用了 ADAPTACLmaxRPC算法之后，约束求解效率相对于在搜索中单独维持 AC或 LmaxRPC算法有大幅度提高的实例类结果，如7表 1、表 2所示.表 1为单独应用 4种启发式与 AC和 LmaxRPC对比的结果，而表 2为 4种启发式的析取及合取应用与 AC和

17、LmaxRPC的对比结果.2 个表中从第二列到最后一列分别表示用各种约束传播方法进行约束求解的情况，其中 4种启发式及其合取和析取应用分别表示用这些启发式来引导自适应约束传播搜索.这类结果表明，应用了自适应约束传播求解方法之后，虽然自适应约束传播方法得到的实验结果不是最优的，但相比于单独维持 AC或 LmaxRPC的情况，效率上都有实质性提高.即，ADAPTACLmaxRPC算法集合了 AC和 LmaxRPC的优点，在保证了求解效率的同时，适当避免了开销和冗余的困扰，减少了二者之间的矛盾.例如，qcporder15holes120balanced21QWH15实例中，几种自适应约束传播求解算法

18、的 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所示

19、.表 3为单独应用 4种自适应启发式的求解算法与维持 AC和 LmaxRPC算法性能对比结果，而表 4为 4种启发式的析取及合取应用对应的算法与维持 AC和 LmaxRPC算法性能对比结果.CPU 时间开销最好情况均加粗显示. 表 3 ADAPTACLmaxRPC自适应约束传播算法与维持 AC和 LmaxRPC算法性8能对比（1） Tab.3 The performance comparison of ADAPTACLmaxRPC， AC and LmaxRPC（1） 实例 qcporder15holes120balanced20QWH15中，自适应约束传播算法最好情况下（H12 的 8.37

20、5 s）比 AC的 70.766 s提高了近 9倍，比LmaxRPC的 65.75 s提高了 7倍多，实例 frb30155bis的最好自适应方式也比单独应用 AC或 LmaxRPC情况提高了近三倍.从这些数据上可进一步看出，应用自适应约束传播求解算法，在遇到特定约束后，ADAPTACLmaxRPC能根据需要适应到最合适的约束传播方法，因此，有效提高了约束求解的效率.此外，从综合实力上讲，4 种启发式的析取形式相比于单独应用 4种启发式及其合取形式，更能准确探查出更合适的约束传播方法，而启发式的合取在某些特例上效率提高幅度比较明显.例如在 frb30155bis实例上，单独应用 4种启发式的效

21、率没有析取应用的效率高，合取应用的效率也相对析取应用稍逊一点，但合取应用在qcporder15holes120balanced20QWH15实例上的表现却尤为突出，这和问题本身结构有关. 综合考虑以上各实验数据，可发现，新提出的自适应约束传播求解算法 ADAPTACLmaxRPC有很强的竞争优势.原因是：ADAPTACLmaxRPC 能够利用强弱约束传播方法的优点，在遇到某个特定约束后，根据约束的特性，自适应的选择合适的约束传播方法，即为删除能力强的约束选择过滤能力强的约束传播方法，而为删除能力弱的约束选择过滤能力弱的约束传播方法，最终实现在保证求解效率的同时，有效避免求解效率和算9法开销间矛

22、盾的目的.算法 ADAPTACLmaxRPC不论从 CPU时间开销上，还是从约束检查次数以及搜索树生成节点数上，综合性能都以较大优势胜出. 4 总 结 本文在现有约束传播方法研究的基础上，提出一种自适应约束传播求解算法 ADAPTACLmaxRPC，它根据搜索过程中探查到的约束活跃程度（Deletion 个数及 DWO次数） ，并借助于自适应启发式，在强约束传播方法（LmaxRPC）和弱约束传播方法（AC）之间灵活切换，从根本上提高约束求解效率.来自于多个 Benchmark实例类上的实验数据表明，ADAPTACLmaxRPC算法实现了降低求解效率和算法开销之间矛盾的目的，整体性能明显优于在搜

23、索中单独维持 AC和 LmaxRPC的算法.未来工作考虑将此算法与我们改进的自适应分支求解算法进行求解效率的比较分析，并更深入研究将学习型自适应约束传播14应用到约束求解中. 参考文献 1 ROSSI F， BEEK P V， WALSH T. Handbook of constraint programmingM. Amsterdam， Netherland： Elsevier， 2006： 1-85. 2 王秦辉，陈恩红，王煦法. 分布式约束满足问题研究及其进展J. 软件学报， 2006， 17（10）： 2029-2039. WANG Qinghui， CHEN Enhong， WANG

24、 Xufa. Research and development of distributed constraint satisfaction problemsJ. Journal of Software， 2006， 17（10）： 2029-2039.（In 10Chinese） 3 CHRISTOPHE Lecoutre. Constraint networks： techniques and algorithmsM. London， UK： Wiley， 2009： 39-353. 4 SAKKOUT H E， WALLACE M G， RICHARDS E B. An instance

25、 of adaptive constraint propagationC/ Proceedings of CP-96. Cambridge， Massachusetts， USA， 1996：164-178. 5 FREUDER E C， WALLACE R J. Selective relaxation for constraint satisfaction problemsC/ Proceedings of the Third International IEEE Computer Society Conference on Tools for Artificial Intelligenc

26、e. San Jose， USA， 1991：332-339. 6 SCHULTE C， STUCKEY P J. Speeding up constraint propagationC/ Proceedings of CP2004. Toronto， Canada， 2004： 619-633. 7 MEHTA D， DONGEN Mrc V. Probabilistic consistency boosts MAC and SACC/ Proceedings of IJCAI2007. Hyderabad， India， 2007： 143-148. 8 STERGIOU K. Heuristics for dynamically adapting propagationC/ Proceedings of ECAI2008. Patras， Greece， 2008： 485-489. 9 DEBRUYNE R， BESSIERE C. From restricted path consistency to maxrestricted path consistencyC/ Proceedings of CP97. Schloss Hagenberg， Austria， 1997： 312-326.