王海燕　歐陽(yáng)丹彤　張永剛　楊明明

摘 要：在現(xiàn)有自適應(yīng)約束求解方法基礎(chǔ)上，提出一種新的自適應(yīng)約束傳播求解算法ADAPTACLmaxRPC.該算法能根據(jù)約束的不同特性，在傳播能力強(qiáng)但開(kāi)銷高的LmaxRPC與傳播能力弱卻開(kāi)銷低的AC之間自適應(yīng)地切換進(jìn)行約束傳播.多個(gè)Benchmark實(shí)例類上的測(cè)試實(shí)驗(yàn)數(shù)據(jù)表明，ADAPTACLmaxRPC算法有效地平衡了求解效率和算法開(kāi)銷之間的矛盾，大幅度提高了約束求解的效率.

關(guān)鍵詞：人工智能；約束程序；約束滿足問(wèn)題；自適應(yīng)約束求解；約束傳播

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：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

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

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

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

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

1 背 景

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

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

2 ADAPTACLmaxRPC自適應(yīng)約束傳播算法

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

算法的輸入為X，C，Q，H.其中Q為傳播隊(duì)列，H為某種自適應(yīng)啟發(fā)式，運(yùn)用不同的自適應(yīng)啟發(fā)式，算法效率有很大差別.算法剛開(kāi)始先把傳播隊(duì)列Q初始化為所有需要傳播的約束集合，然后依次取出約束，根據(jù)啟發(fā)式H選擇強(qiáng)相容或弱相容方法進(jìn)行約束傳播.不論選擇誰(shuí)，只要校驗(yàn)之后變量論域改變，則根據(jù)變化程度判斷是在傳播隊(duì)列中加入新的相關(guān)約束繼續(xù)傳播還是失敗而終.直到Q中無(wú)待傳播約束且x論域不再發(fā)生變化時(shí)，成功結(jié)束.步驟8中的更新過(guò)程，實(shí)為將所有與當(dāng)前傳播變量相關(guān)的其他約束放入Q的過(guò)程.

在步驟4用Revise（C， xi，LmaxRPC）進(jìn)行強(qiáng)相容校驗(yàn)時(shí)，判斷過(guò)程為：對(duì)當(dāng)前變量xi論域中每個(gè)值，若不是AC的，則被刪除；若是AC的，則用LmaxRPC相容方法再校驗(yàn)一次是否也有支持.即，當(dāng)前變量xi論域中所有值校驗(yàn)完畢后，剩下的值都是LmaxRPC的.而在步驟5的用Revise（C， xi，AC）進(jìn)行弱相容校驗(yàn)時(shí)，判斷過(guò)程為：對(duì)每個(gè)值，如果沒(méi)有AC支持，則從當(dāng)前變量xi論域中刪除；若有AC支持，接著判斷下個(gè)值，直到論域中所有值都用AC校驗(yàn)一遍后，才判斷是否用強(qiáng)相容校驗(yàn).即，只有當(dāng)AC刪除了值時(shí)，才用LmaxRPC校驗(yàn)，而如果AC相容未刪除任何值，那么所有值都是AC的，則不再用LmaxRPC繼續(xù)校驗(yàn)，即最后當(dāng)前變量xi論域中剩余值一定是AC的，卻不一定是LmaxRPC的，因此Revise（C， xi，AC）比Revise（C， xi，LmaxRPC）要弱一些，詳細(xì)的Revise過(guò)程可參看文獻(xiàn)[8].

3 實(shí)驗(yàn)結(jié)果

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

第一組數(shù)據(jù)是應(yīng)用了ADAPTACLmaxRPC算法之后，約束求解效率相對(duì)于在搜索中單獨(dú)維持AC或LmaxRPC算法有大幅度提高的實(shí)例類結(jié)果，如表1、表2所示.表1為單獨(dú)應(yīng)用4種啟發(fā)式與AC和LmaxRPC對(duì)比的結(jié)果，而表2為4種啟發(fā)式的析取及合取應(yīng)用與AC和LmaxRPC的對(duì)比結(jié)果.2個(gè)表中從第二列到最后一列分別表示用各種約束傳播方法進(jìn)行約束求解的情況，其中4種啟發(fā)式及其合取和析取應(yīng)用分別表示用這些啟發(fā)式來(lái)引導(dǎo)自適應(yīng)約束傳播搜索.這類結(jié)果表明，應(yīng)用了自適應(yīng)約束傳播求解方法之后，雖然自適應(yīng)約束傳播方法得到的實(shí)驗(yàn)結(jié)果不是最優(yōu)的，但相比于單獨(dú)維持AC或LmaxRPC的情況，效率上都有實(shí)質(zhì)性提高.即，ADAPTACLmaxRPC算法集合了AC和LmaxRPC的優(yōu)點(diǎn)，在保證了求解效率的同時(shí)，適當(dāng)避免了開(kāi)銷和冗余的困擾，減少了二者之間的矛盾.例如，qcporder15holes120balanced21QWH15實(shí)例中，幾種自適應(yīng)約束傳播求解算法的CPU運(yùn)行時(shí)間均遠(yuǎn)小于單獨(dú)維持LmaxRPC的運(yùn)行時(shí)間1 028.75 s，最好情況是563.06 s，接近于單獨(dú)維持AC的運(yùn)行時(shí)間508.39.另外，實(shí)例le4505a4ext.txt中單獨(dú)維持AC情況的運(yùn)行時(shí)間超過(guò)了兩個(gè)小時(shí)，而自適應(yīng)約束傳播求解方法的最好情況是1369.22 s，相對(duì)前者提高了6倍左右.表中的CPU運(yùn)行時(shí)間取的是十次運(yùn)行的平均值. 在上組實(shí)驗(yàn)基礎(chǔ)上繼續(xù)展開(kāi)，得到第二組實(shí)驗(yàn)結(jié)果.此組結(jié)果顯示的是應(yīng)用ADAPTACLmaxRPC算法之后，自適應(yīng)約束傳播求解方法的綜合效率明顯優(yōu)于在搜索中單獨(dú)維持AC或LmaxRPC算法的測(cè)試實(shí)例，如表3、表4所示.表3為單獨(dú)應(yīng)用4種自適應(yīng)啟發(fā)式的求解算法與維持AC和LmaxRPC算法性能對(duì)比結(jié)果，而表4為4種啟發(fā)式的析取及合取應(yīng)用對(duì)應(yīng)的算法與維持AC和LmaxRPC算法性能對(duì)比結(jié)果.CPU時(shí)間開(kāi)銷最好情況均加粗顯示.

表3 ADAPTACLmaxRPC自適應(yīng)約束傳播算法與維持AC和LmaxRPC算法性能對(duì)比（1）

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

實(shí)例qcporder15holes120balanced20QWH15中，自適應(yīng)約束傳播算法最好情況下（H∧12的8.375 s）比AC的70.766 s提高了近9倍，比LmaxRPC的65.75 s提高了7倍多，實(shí)例frb30155bis的最好自適應(yīng)方式也比單獨(dú)應(yīng)用AC或LmaxRPC情況提高了近三倍.從這些數(shù)據(jù)上可進(jìn)一步看出，應(yīng)用自適應(yīng)約束傳播求解算法，在遇到特定約束后，ADAPTACLmaxRPC能根據(jù)需要適應(yīng)到最合適的約束傳播方法，因此，有效提高了約束求解的效率.此外，從綜合實(shí)力上講，4種啟發(fā)式的析取形式相比于單獨(dú)應(yīng)用4種啟發(fā)式及其合取形式，更能準(zhǔn)確探查出更合適的約束傳播方法，而啟發(fā)式的合取在某些特例上效率提高幅度比較明顯.例如在frb30155bis實(shí)例上，單獨(dú)應(yīng)用4種啟發(fā)式的效率沒(méi)有析取應(yīng)用的效率高，合取應(yīng)用的效率也相對(duì)析取應(yīng)用稍遜一點(diǎn)，但合取應(yīng)用在qcporder15holes120balanced20QWH15實(shí)例上的表現(xiàn)卻尤為突出，這和問(wèn)題本身結(jié)構(gòu)有關(guān).

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

4 總 結(jié)

本文在現(xiàn)有約束傳播方法研究的基礎(chǔ)上，提出一種自適應(yīng)約束傳播求解算法ADAPTACLmaxRPC，它根據(jù)搜索過(guò)程中探查到的約束活躍程度（Deletion個(gè)數(shù)及DWO次數(shù)），并借助于自適應(yīng)啟發(fā)式，在強(qiáng)約束傳播方法（LmaxRPC）和弱約束傳播方法（AC）之間靈活切換，從根本上提高約束求解效率.來(lái)自于多個(gè)Benchmark實(shí)例類上的實(shí)驗(yàn)數(shù)據(jù)表明，ADAPTACLmaxRPC算法實(shí)現(xiàn)了降低求解效率和算法開(kāi)銷之間矛盾的目的，整體性能明顯優(yōu)于在搜索中單獨(dú)維持AC和LmaxRPC的算法.未來(lái)工作考慮將此算法與我們改進(jìn)的自適應(yīng)分支求解算法進(jìn)行求解效率的比較分析，并更深入研究將學(xué)習(xí)型自適應(yīng)約束傳播^{[14]應(yīng)用到約束求解中.}

參考文獻(xiàn)

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

[2] 王秦輝，陳恩紅，王煦法. 分布式約束滿足問(wèn)題研究及其進(jìn)展[J]. 軟件學(xué)報(bào)， 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.