基于AC與LmaxRPC的自適應約束傳播求解算法

王海燕　歐陽丹彤　張永剛　楊明明

摘 要：在現(xiàn)有自適應約束求解方法基礎上，提出一種新的自適應約束傳播求解算法ADAPTACLmaxRPC.該算法能根據(jù)約束的不同特性，在傳播能力強但開銷高的LmaxRPC與傳播能力弱卻開銷低的AC之間自適應地切換進行約束傳播.多個Benchmark實例類上的測試實驗數(shù)據(jù)表明，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

近年來，由于具有濃厚產(chǎn)業(yè)背景和重大商業(yè)價值，約束程序（Constraint Programming，CP）研究得到蓬勃發(fā)展，并已成為問題建模及求解如資源分配、調(diào)度問題、時序推理、規(guī)劃和圖著色等領域困難組合問題的典范.約束滿足問題（Constraint Satisfaction Problem，CSP）^{[1] 是約束程序的核心，自提出以來受到了廣泛關注.國內(nèi)外有很多學者致力于這方面的研究，主要的工作有約束程序理論、設計與應用的研究、約束歸納邏輯程序設計等方面，以及CSP求解研究等[2].其中，CSP的求解一直是人工智能領域研究的熱點，具有重要的理論研究和實際應用價值.}

CSP的主要推理技術(shù)是約束傳播，它對約束程序的成功與否起著至關重要的作用，是影響約束求解算法效率和適應性的關鍵因素.因此，多種約束傳播技術(shù)應運而生^{[3]，包括早期的FC，廣泛使用的GAC，以及maxRPC，SAC等.雖然約束傳播技術(shù)選擇豐富，但簡單的約束求解器通常在整個搜索過程中對所有的約束都使用同一個標準方法.由于不同約束的刪除能力各不相同，同一種約束傳播技術(shù)很難適用于所有約束.比如，如果為很少或不刪除值的約束選用了一種過濾能力很強的約束傳播方法，必然會導致不必要的CPU開銷.所以，考慮到時間和空間復雜性，盡量想為刪除能力強的約束選擇過濾能力強的約束傳播方法，為刪除能力弱的約束選擇過濾能力弱的約束傳播方法.因此，如何在搜索中為約束動態(tài)選擇約束傳播方法成為一個重要的研究方向.}

隨著約束求解方法的發(fā)展，“自適應”概念越來越受到人們關注.這一概念的出現(xiàn)使“動態(tài)”選擇約束傳播方法成為可能.越來越多研究者開始考慮從問題的結(jié)構(gòu)化信息入手，從CSP求解的各個角度提出具有更強適應性的自適應約束求解方法，最終從根本上提高算法的效率和“智能性”.在眾多自適應約束求解方法中，自適應約束傳播約束求解方法另辟蹊徑，在效率上取得了突破^{[4-8].尤其是文獻[8]中提出的4種自適應啟發(fā)式，根據(jù)域空（Domain Wipeout，DWO）和值刪除（Deletion）這些信息，在強弱約束傳播方法之間切換，為自適應約束傳播方法的進一步發(fā)展奠定了堅實的基礎.}

本文提出一種為不同約束自動選擇傳播技術(shù)的動態(tài)自適應約束傳播方法ADAPTACLmaxRPC.利用[8]中提出的啟發(fā)式H1，H2，H3，H4及它們的析取和合取應用，根據(jù)條件滿足與否動態(tài)在強卻開銷高的約束傳播方法和弱但開銷低的約束傳播方法之間切換.實驗限定在二元問題上，用AC為弱相容（W），LmaxRPC為強相容（S）.在Benchmark多類問題上對ADAPTACLmaxRPC算法進行了詳細的實驗評估，實驗結(jié)果證實了ADAPTACLmaxRPC算法的有效性，且具有很強的競爭力.

1 背 景

maxRPC是一種比AC具有更強刪除能力的局部相容技術(shù).然而，現(xiàn)有maxRPC算法受開銷和冗余的困擾，因為算法中重復執(zhí)行許多不能觸發(fā)任何Deletion的約束檢查.因此，在搜索中運用maxRPC與應用AC相比雖然節(jié)省了搜索樹的空間，但減慢了搜索過程.LmaxRPC是maxRPC的近似算法，它僅傳播AC支持的丟失，而不傳播PC證人的丟失.LmaxRPC相對于maxRPC來說取得了低層次的相容，但仍比AC強，而且當用于搜索中時，比maxRPC更劃算.多個文獻^{[10-11]的實驗證實，LmaxRPC確實是一個比maxRPC更好的選擇.例如[10]中通過利用支持的余數(shù)和一個回溯表以及高效的數(shù)據(jù)結(jié)構(gòu)改善了maxRPC的性能，提出了LmaxRPCrm.[11]中提出的LmaxRPC3和LmaxRPC3rm利用數(shù)據(jù)結(jié)構(gòu)，通過刪除一些冗余來保證低的空間復雜性.雖然僅在實際中少刪了一點值，卻可以避免許多冗余的約束檢查，進而提高了搜索速度.}

在自適應約束傳播中，首要問題是基本傳播方法的選擇.既要考慮約束傳播方法刪除能力的差異，又要考慮其執(zhí)行開銷.鑒于AC，maxRPC和LmaxRPC三者的特性，考慮在AC和LmaxRPC之間進行自適應約束傳播.其次，自適應啟發(fā)式能在不同約束傳播方法之間起到導向作用，選擇一個合適的自適應啟發(fā)式是自適應約束傳播方法成功的關鍵.文獻[8]4種自適應啟發(fā)式利用DWO和Deletion這些反應約束活躍程度的關鍵信息，在不同約束傳播方法之間自由導向，表現(xiàn)出良好的求解效率.

2 ADAPTACLmaxRPC自適應約束傳播算法

為進一步提高自適應約束求解的效率，以AC為弱相容（W），LmaxRPC為強相容（S），并在自適應啟發(fā)式H1，H2，H3，H4及其合取和析取應用（簡記為：H∨12，表示H1和H2兩種啟發(fā)式的析?。籋∨124，表示H1和H2，H43種啟發(fā)式的析?。籋∨134，表示H1和H3，H43種啟發(fā)式的析?。籋∧12，表示H1和H2兩種啟發(fā)式的合?。┑闹笇?，研究了自適應約束傳播算法ADAPTACLmaxRPC.

算法的輸入為X，C，Q，H.其中Q為傳播隊列，H為某種自適應啟發(fā)式，運用不同的自適應啟發(fā)式，算法效率有很大差別.算法剛開始先把傳播隊列Q初始化為所有需要傳播的約束集合，然后依次取出約束，根據(jù)啟發(fā)式H選擇強相容或弱相容方法進行約束傳播.不論選擇誰，只要校驗之后變量論域改變，則根據(jù)變化程度判斷是在傳播隊列中加入新的相關約束繼續(xù)傳播還是失敗而終.直到Q中無待傳播約束且x論域不再發(fā)生變化時，成功結(jié)束.步驟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繼續(xù)校驗，即最后當前變量xi論域中剩余值一定是AC的，卻不一定是LmaxRPC的，因此Revise（C， xi，AC）比Revise（C， xi，LmaxRPC）要弱一些，詳細的Revise過程可參看文獻[8].

3 實驗結(jié)果

為驗證ADAPTACLmaxRPC算法的優(yōu)勢，本文采用Christophe Lecoutre整理的多個Benchmark問題實例^{[3]來對其進行測試.算法采用dway[12]分支，dom/wdeg[13]變量排序啟發(fā)式和字典序值排序啟發(fā)式.LmaxRPC用的是LmaxRPC3的rm版本[11].具體選擇的問題實例類有qcp15， qwh20， frb3015， bqwh15_106， rlfapGraphs， rlfapScens， rlfapModGraphs等.所有實驗都是在主頻為1.60 GHz，內(nèi)存為1.99 GB，操作系統(tǒng)為Microsoft Windows XP Professional的電腦上完成的.測試環(huán)境為Eclipse，編程語言為VC++.將ADAPTACLmaxRPC應用于搜索中，并和單獨維持AC及LmaxRPC的算法進行比較，綜合考查CPU時間開銷（簡記為time，單位：s）、約束檢查次數(shù)（簡記為#ccks）和搜索樹生成節(jié)點數(shù)（簡記為#nodes）三項技術(shù)指標，得到兩組實驗結(jié)果.}

第一組數(shù)據(jù)是應用了ADAPTACLmaxRPC算法之后，約束求解效率相對于在搜索中單獨維持AC或LmaxRPC算法有大幅度提高的實例類結(jié)果，如表1、表2所示.表1為單獨應用4種啟發(fā)式與AC和LmaxRPC對比的結(jié)果，而表2為4種啟發(fā)式的析取及合取應用與AC和LmaxRPC的對比結(jié)果.2個表中從第二列到最后一列分別表示用各種約束傳播方法進行約束求解的情況，其中4種啟發(fā)式及其合取和析取應用分別表示用這些啟發(fā)式來引導自適應約束傳播搜索.這類結(jié)果表明，應用了自適應約束傳播求解方法之后，雖然自適應約束傳播方法得到的實驗結(jié)果不是最優(yōu)的，但相比于單獨維持AC或LmaxRPC的情況，效率上都有實質(zhì)性提高.即，ADAPTACLmaxRPC算法集合了AC和LmaxRPC的優(yōu)點，在保證了求解效率的同時，適當避免了開銷和冗余的困擾，減少了二者之間的矛盾.例如，qcporder15holes120balanced21QWH15實例中，幾種自適應約束傳播求解算法的CPU運行時間均遠小于單獨維持LmaxRPC的運行時間1 028.75 s，最好情況是563.06 s，接近于單獨維持AC的運行時間508.39.另外，實例le4505a4ext.txt中單獨維持AC情況的運行時間超過了兩個小時，而自適應約束傳播求解方法的最好情況是1369.22 s，相對前者提高了6倍左右.表中的CPU運行時間取的是十次運行的平均值. 在上組實驗基礎上繼續(xù)展開，得到第二組實驗結(jié)果.此組結(jié)果顯示的是應用ADAPTACLmaxRPC算法之后，自適應約束傳播求解方法的綜合效率明顯優(yōu)于在搜索中單獨維持AC或LmaxRPC算法的測試實例，如表3、表4所示.表3為單獨應用4種自適應啟發(fā)式的求解算法與維持AC和LmaxRPC算法性能對比結(jié)果，而表4為4種啟發(fā)式的析取及合取應用對應的算法與維持AC和LmaxRPC算法性能對比結(jié)果.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情況提高了近三倍.從這些數(shù)據(jù)上可進一步看出，應用自適應約束傳播求解算法，在遇到特定約束后，ADAPTACLmaxRPC能根據(jù)需要適應到最合適的約束傳播方法，因此，有效提高了約束求解的效率.此外，從綜合實力上講，4種啟發(fā)式的析取形式相比于單獨應用4種啟發(fā)式及其合取形式，更能準確探查出更合適的約束傳播方法，而啟發(fā)式的合取在某些特例上效率提高幅度比較明顯.例如在frb30155bis實例上，單獨應用4種啟發(fā)式的效率沒有析取應用的效率高，合取應用的效率也相對析取應用稍遜一點，但合取應用在qcporder15holes120balanced20QWH15實例上的表現(xiàn)卻尤為突出，這和問題本身結(jié)構(gòu)有關.

綜合考慮以上各實驗數(shù)據(jù)，可發(fā)現(xiàn)，新提出的自適應約束傳播求解算法ADAPTACLmaxRPC有很強的競爭優(yōu)勢.原因是：ADAPTACLmaxRPC能夠利用強弱約束傳播方法的優(yōu)點，在遇到某個特定約束后，根據(jù)約束的特性，自適應的選擇合適的約束傳播方法，即為刪除能力強的約束選擇過濾能力強的約束傳播方法，而為刪除能力弱的約束選擇過濾能力弱的約束傳播方法，最終實現(xiàn)在保證求解效率的同時，有效避免求解效率和算法開銷間矛盾的目的.算法ADAPTACLmaxRPC不論從CPU時間開銷上，還是從約束檢查次數(shù)以及搜索樹生成節(jié)點數(shù)上，綜合性能都以較大優(yōu)勢勝出.

4 總 結(jié)

本文在現(xiàn)有約束傳播方法研究的基礎上，提出一種自適應約束傳播求解算法ADAPTACLmaxRPC，它根據(jù)搜索過程中探查到的約束活躍程度（Deletion個數(shù)及DWO次數(shù)），并借助于自適應啟發(fā)式，在強約束傳播方法（LmaxRPC）和弱約束傳播方法（AC）之間靈活切換，從根本上提高約束求解效率.來自于多個Benchmark實例類上的實驗數(shù)據(jù)表明，ADAPTACLmaxRPC算法實現(xiàn)了降低求解效率和算法開銷之間矛盾的目的，整體性能明顯優(yōu)于在搜索中單獨維持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.