兩種智能值排序啟發(fā)式研究

王海燕，管 瑩，李 闖，楊明明

(1.吉林師范大學(xué)計算機(jī)學(xué)院，吉林四平136000;2.吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，長春130012; 3.阜新高等?？茖W(xué)校計算機(jī)信息技術(shù)系，遼寧阜新123000)

兩種智能值排序啟發(fā)式研究

王海燕1，2，管 瑩3，李 闖2，楊明明2

(1.吉林師范大學(xué)計算機(jī)學(xué)院，吉林四平136000;2.吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，長春130012; 3.阜新高等?？茖W(xué)校計算機(jī)信息技術(shù)系，遼寧阜新123000)

為提升約束滿足問題求解效率，對最受推崇的智能值排序啟發(fā)式Look-ahead和Survivors-first進(jìn)行深入研究。比較兩種值排序啟發(fā)式在常規(guī)和自適應(yīng)兩種環(huán)境下的效率表現(xiàn)。結(jié)果顯示，在多數(shù)問題類上，常規(guī)情況下Survivors-first效果更好，而在自適應(yīng)環(huán)境下效率有所下降;在不同環(huán)境下使用不同啟發(fā)式可提升約束滿足問題求解效率。

約束滿足問題;約束求解;值排序啟發(fā)式;效率

0 引 言

約束滿足問題(CSP:Constraint Satisfaction Problems)［1］一直是人工智能的一個重要研究方向，相關(guān)技術(shù)被廣泛應(yīng)用于航天、配置及組合問題求解等領(lǐng)域。約束求解是CSP的關(guān)鍵問題，其效率備受矚目。經(jīng)典的求解基于回溯搜索與約束傳播的結(jié)合模式，搜索過程在分支策略與變量排序啟發(fā)式(VOH: Variable Ordering Heuristic)和值排序啟發(fā)式(V-O-H:Value Ordering Heuristic)配合下探索問題的解。一段時間在某種程度上，V-O-H被忽略了，因為很多情況下它需要大量計算資源，但越來越多的研究證明，它是影響約束求解效率的一個重要因素。

V-O-H指變量選擇值進(jìn)行優(yōu)先實例化的順序，值排序的變化會直接影響搜索樹各個結(jié)點(diǎn)產(chǎn)生分支的變化。值排序最初的評判依據(jù)是CSP解的數(shù)量［2］。隨之，研究逐步擴(kuò)展到借鑒貝葉斯網(wǎng)絡(luò)思想增加判定準(zhǔn)確性［3］，接著尋求策略選擇對結(jié)果影響最大化的值［4］，但當(dāng)遇到相當(dāng)昂貴的開銷問題時，降低開銷的研究工作逐漸深入。一系列V-O-H被相繼提出。這些V-O-H在不同情況下作用效果差異較大，尤其是新近推出的智能V-O-H，智能程度受環(huán)境影響明顯。筆者意在找出智能V-O-H在何種情況下發(fā)揮最佳效果。

筆者詳細(xì)說明了兩種智能V-O-H。然后對智能V-O-H在常規(guī)和自適應(yīng)方式下進(jìn)行詳細(xì)對比。最后對比較結(jié)果進(jìn)行理論分析，并得出結(jié)論。

1 約束滿足問題背景知識

一個CSP表示為一個三元組(X，D，C)，其中X={x1，…，xn}是n個變量的集合;D={D(x1)，…，D(xn)}是對應(yīng)于每個變量的一組論域;C={c1，…，ce}是e個約束的集合。每個約束c表示為有序?qū)?var(c)，rel(c))，其中var(c)={x1，…，xk}是X的一個有序子集，而rel(c)是D(x1)×…×D(xk)的子集。驗證一個元組是否滿足約束c的過程稱為一次約束檢查［5］。變量論域中值實例化的順序影響CSP的求解效率，因此在搜索過程中經(jīng)常會借助部分信息作啟發(fā)性引導(dǎo)，確定論域中值選擇的順序，這種方式稱為V-O-H。常用的V-O-H有l(wèi)exico、look-ahead、impact［6］、survivors-first等。

Lexico是字典序V-O-H，顧名思義，變量論域各值按字典順序排序。Lexico雖然使值選擇有了某種順序，但這種順序沒有智能參照搜索中的任意信息，不能把握搜索分支的動向。

人們研究發(fā)現(xiàn)，在求解CSP的搜索過程中，向前看可以得到許多有用信息，如通過發(fā)現(xiàn)沖突最少的值提高找到解的可能性、通過選擇論域包含值最多的變量提高找到解的可能性等。Daniel等［4］在1995年就困難CSP提出一組向前看智能V-O-H(又稱Look-ahead)。Look-ahead優(yōu)先選擇當(dāng)前變量中與未來變量的某些值沖突最少的值進(jìn)行實例化。符合Look-ahead思想的V-O-H有很多，例如MC(Min-Conflicts)、MD(Max-Domain-size)、WMD(Weighted-Max-Domain-size)、PDS(Point-Domain-Size)等，其中MC在實際應(yīng)用中效果最為突出。MC被稱為最小沖突啟發(fā)式，是一種考慮相關(guān)聯(lián)未實例化變量論域中與當(dāng)前變量當(dāng)前值不相容值的個數(shù)的V-O-H，論域中值的順序按照此沖突個數(shù)升序排序，選擇沖突個數(shù)最少的值優(yōu)先實例化。

Look-ahead對大型或困難問題算法性能提升效果顯著，但對簡單可解決問題效果不明顯。原因是實現(xiàn)起來稍復(fù)雜，有時還會引發(fā)許多額外開銷;而對于求解較多的簡單問題時，有許多可選擇的值，求解過程可以近似無回溯建立搜索路徑，這種檢查每個變量每個值的額外開銷則是多余的。

許多學(xué)者研究了多種方法用于降低這種開銷，一種是使尋找值的信息學(xué)習(xí)過程更廉價。早期學(xué)習(xí)工作主要集中在nogoods上，即不參與解的實例化。它可使搜索避免對失敗子樹的再次探索，特別強(qiáng)調(diào)nogoods與restart［7］配合的效果更好。

直到2008年，Zhang等［8］提出一種自適應(yīng)學(xué)習(xí)值排序方法Survivors-first(幸存者優(yōu)先)。該方法在搜索中學(xué)習(xí)傳播信息，廉價搜索那些常被幸存?zhèn)鞑サ闹担糜诩铀賯€別問題求解。自此，自適應(yīng)V-O-H的研究逐漸展開。Survivors-first的典型代表是選擇R/S最低值值排序啟發(fā)式(以下簡稱RSVO:RIS-Value-Ordering)，這種V-O-H用到R和S兩個技術(shù)指標(biāo)。其中R表示某值在傳播過程中被移去的頻率，S表示某值在傳播過程中被挑戰(zhàn)是否有支持的頻率。此V-O-H的主導(dǎo)思想是，R越高，相容的可能性則越低; S越高，R對某值幸存能力認(rèn)可的準(zhǔn)確程度越強(qiáng)。RSVO選擇常被挑戰(zhàn)但很少被移去(R/S最低)的值進(jìn)行優(yōu)先實例化。

2 兩種智能V-O-H間比較

對于Look-ahead值排序啟發(fā)式和Survivors-first值排序啟發(fā)式對約束求解效率的影響，筆者在前階段已經(jīng)做出深入的研究［9，10］，兩種智能V-O-H對求解效率都有極大的提升作用。但對于兩者性能比較并未做深入探討。

為清楚了解二者間性能差異，方便對智能V-O-H的進(jìn)一步創(chuàng)新，筆者將它們進(jìn)行詳細(xì)比較。測試環(huán)境仍然是主頻1.90 GHz、內(nèi)存1.00 GByte的DELL主機(jī)。不同的是，擴(kuò)展研究標(biāo)準(zhǔn)測試庫Benchmark中 7種測試類 Bqwh18_141、Driver、geom、QCPp-20、RlfapGraphs、Rlfap ModGraphs、RlfapModScens的Sat(可滿足問題)和Unsat(不可滿足問題)兩類問題，并在每類中選取5種以上實例細(xì)化測試。

測試建立在兩種程序環(huán)境下，第1種是普通的約束求解模式下，即在MAC過程引導(dǎo)的常規(guī)約束求解［11］;另一種是在自適應(yīng)約束求解模式下，具體為在MAC過程中嵌入文獻(xiàn)［12］中兩種自適應(yīng)啟發(fā)式的析取。在這兩種模式下，分別引入Look-ahead和Survivors-first兩種智能V-O-H，比較分析兩種智能V-O-H在兩種模式下作用的不同。

2.1 常規(guī)模式下比較

常規(guī)模式是指普通MAC過程引導(dǎo)的約束求解過程，也就是將回溯搜索與弧相容約束傳播交替結(jié)合，不斷過濾不相容的論域值，并依據(jù)固定分支選擇方式，借助某種VOH和V-O-H選擇合適的變量和實例化論域值，增量擴(kuò)展部分解為完全解或以失敗告終。在此，限定VOH為備受關(guān)注的dom/wdeg，V-O-H則分別用Look-ahead和Survivors-first兩種智能排序方式進(jìn)一步引導(dǎo)。筆者得到的實驗結(jié)果如表1和表2所示。

表1 Sat問題類在常規(guī)模式下的效率比對Tab.1 Comparison of sat on efficiency under the normal situation

表1和表2分別是Benchmark中幾個典型實例類在常規(guī)模式下的效率比對(以時間消耗作為比較對象)，Sat問題類的Driver類中測試了6個實例，其中有5個實例Survivors-first的求解效率高于Look-ahead的求解效率。

從表1、表2的測試數(shù)據(jù)可以看出，除了QCPp-20的Easy類，其余的測試類借助Survivorsfirst V-O-H引導(dǎo)值選擇排序的方式，效率均要高于Look-ahead引導(dǎo)的情況。這是由于Survivors-first在搜索的過程中，有效學(xué)習(xí)了傳播信息，廉價搜索到了常被幸存?zhèn)鞑サ闹涤糜诩铀賯€別問題求解，使約束求解的效率得到大幅提升。

而對于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。進(jìn)一步分析此類問題，發(fā)現(xiàn)這些實例約束松緊度較低，即約束上禁止的值對個數(shù)少，相比于Hard類里的實例問題稍簡單，較容易求解。帶有學(xué)習(xí)過程的Survivors-first與無學(xué)習(xí)過程的Look-ahead對比便失去了優(yōu)勢。學(xué)習(xí)過程反而加重了時間消耗，因而效率降低。

基于求解過程所得數(shù)據(jù)，對于bqwh類中5個實例，也能夠得出結(jié)論，簡單的問題實例用Look-ahead V-O-H求解速度明顯更快。Geo10問題類也是一樣(由于篇幅有限，此部分?jǐn)?shù)據(jù)未予給出)。

表2 Unsat問題類在常規(guī)模式下的效率比對Tab.2 Comparison of unsat on efficiency under the normal situation

2.2 自適應(yīng)模式下比較

自適應(yīng)模式是指在常規(guī)MAC過程引導(dǎo)的約束求解模式基礎(chǔ)上，嵌入文獻(xiàn)［12］中兩種自適應(yīng)啟發(fā)式的析取應(yīng)用模式(簡記為Heur∨)，仍以增量擴(kuò)展部分解為完全解或以失敗告終為根本目標(biāo)。VOH仍然啟用dom/wdeg，在此基礎(chǔ)上依次引入Look-ahead和Survivors-first兩種智能V-O-H引導(dǎo)值選擇過程。比較分析兩種智能V-O-H，得到結(jié)果列入表3和表4。

表3 Sat問題類在自適應(yīng)模式下的效率比對Tab.3 Comparison of Sat on efficiency under the adaptive circumstance

表3中Driver和QCPp-20中各有3個實例由常規(guī)下Survivors-first的效果好，轉(zhuǎn)變成自適應(yīng)模式下Look-ahead效果勝出。表4的兩個類中也分別有2和1個實例發(fā)生了同樣的效果轉(zhuǎn)變。究其原因可知，依據(jù)Heur∨指導(dǎo)下的自適應(yīng)約束求解模式將一部分時間放在自適應(yīng)啟發(fā)式的判斷上，雖然在自適應(yīng)過程后，啟發(fā)式有效地選擇了一種分支方式繼續(xù)求解，但在判斷兩種自適應(yīng)啟發(fā)式滿足其一與否的過程中，消耗了相對多的時間;而在這些實例上，Look-ahead搜尋的信息又恰好相對有效地減少了回溯次數(shù)，所以求解效率發(fā)生了逆轉(zhuǎn)?？偨Y(jié)自適應(yīng)模式下兩種智能V-O-H引導(dǎo)值選擇的規(guī)律可見，在常規(guī)模式下，Survivors-first在稍難問題實例求解上相對于Look-ahead效果要更好，而在自適應(yīng)模式下卻加重了搜索負(fù)擔(dān)，所以效率下降。而Look-ahead則適用于求解相對簡單的問題實例。

表4 Unsat問題類在自適應(yīng)模式下的效率比對Tab.4 Comparison of Unsat on efficiency under the adaptive circumstance

3 特殊實例分析

在測試中，有幾類實例效果與其他實例差別很大(見表5、表6)，即RlfapGraphs、RlfapModGraphs和RlfapModScens這3類與其他類差別大。常規(guī)模式下，Look-ahead的效果明顯，自適應(yīng)環(huán)境下，效果也很好，尤其是RlfapModGraphs類，特點(diǎn)更明顯。這與3類問題的結(jié)構(gòu)密切相關(guān)。

表5 Sat中特殊問題類Tab.5 Special problems in Sat

表6 Unsat中特殊問題類Tab.6 Special problems in Unsat

為探究問題的結(jié)構(gòu)，筆者借助C++語言，以RlfapModGraphs中Sat類里的實例graph2_f24、graph8_ f10、graph14_f27為例(這3個實例應(yīng)用 Look-ahead效果更突出)，繪制的3個實例問題的結(jié)構(gòu)圖如圖1所示。

圖1 3個實例問題結(jié)構(gòu)Fig.1 Structure of three problem

圖1中每條弧對應(yīng)一個約束，弧的顏色深淺反映了弧的松緊度，也就是禁止值對數(shù)，即弧的顏色越深，其松緊度越大。從圖1可以看出，這3個實例的結(jié)構(gòu)，約束松緊度不高，密度較高。因此，在常規(guī)模式下，Look-ahead效果更突出(結(jié)合3個實例在兩種模式下的運(yùn)行時間可以看出，如表7所示)。同時還可以看到，graph8_f10和graph14_f27的密度比graph2_f24高，所以在自適應(yīng)模式下graph2_f24發(fā)生逆轉(zhuǎn)，Survivors-first效率明顯。而graph8_f10和graph14_f27兩個實例在Look-ahead下的效率沒有變化。

表7 3個實例在兩種模式下的運(yùn)行時間比對Tab.7 Comparison of three examples runtime under twomodes

4 結(jié) 語

鑒于值排序啟發(fā)式對約束滿足問題求解效率的影響，筆者在現(xiàn)有約束求解方法基礎(chǔ)上，分別在常規(guī)和自適應(yīng)兩種模式下，比較了Look-ahead值排序啟發(fā)式和Survivors-first值排序啟發(fā)式兩種智能值排序啟發(fā)式的效率表現(xiàn)。為全面表現(xiàn)兩種V-O-H的特性，驗證過程建立在Bqwh18_141、Driver、Geom、QCPp-20、RlfapGraphs、RlfapModGraphs、RlfapModScens7類問題上，并且包含Sat和Unsat兩個方面。實驗數(shù)據(jù)表明:在多數(shù)問題類上，常規(guī)情況下Survivors-first效果要更好些，而在自適應(yīng)環(huán)境下Survivors-first加重了搜索負(fù)擔(dān)，所以效率有所下降。

［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］王海燕，歐陽丹彤，張永剛，等.結(jié)合 Look-ahead值排序的自適應(yīng)分支求解算法 ［J］.通信學(xué)報，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］.吉林大學(xué)學(xué)報:理學(xué)版，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.

(責(zé)任編輯:劉俏亮)

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，F(xiàn)uxin Higher Training College，F(xiàn)uxin 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

國家自然科學(xué)基金資助項目(61373052;61100090;61170314;41172294);吉林省教育廳“十二五”科學(xué)技術(shù)研究基金資助項目(［2011］第415號;［2014］第490號);四平市科技發(fā)展計劃基金資助項目(2012042);吉林省科技廳自然科學(xué)基金資助項目(201115220);吉林省科技發(fā)展計劃基金資助項目(20140101206JC-06;20140101206JC-15);吉林師范大學(xué)博士啟動基金資助項目(2013018);吉林師范大學(xué)碩士啟動基金資助項目(2009035)

王海燕(1980—)，女，吉林白城人，吉林師范大學(xué)講師，博士，主要從事約束求解與約束優(yōu)化、約束程序設(shè)計研究，(Tel) 86-15044125882(E-mail)jlsdwhy_0820@sina.cn。