基于ParetoHeu和實例化失敗統計的關聯啟發式方法

肖成龍，聶紫陽，王珊珊

遼寧工程技術大學 軟件學院，遼寧 葫蘆島125105

1 引言

約束規劃（Constraint Programming，CP）[1]是用于聲明描述和有效解決約束滿足及約束優化問題的軟件技術，其在實際問題的建模方面具有高度靈活性和求解方式多樣性，具有很高的學術價值和商業價值，在很多領域受到相關專家的高度關注。世界多所知名大學、科研機構和公司紛紛成立了約束規劃研究中心，致力于約束規劃的理論研究、工具研發及成果轉化。目前，約束規劃已經成功應用于包括航空[2]、電氣[3]、運輸[4]、密碼學[5]、生物信息學[6]、生產調度[7]、機器學習[8]、圖形圖像[9]等諸多領域。

約束規劃起源于20世紀60年代，并在20世紀80年代開始積極發展，其中約束邏輯規劃CLP[10]的出現成為了約束規劃領域研究的一座重要里程碑。20世紀90年代，約束規劃進入實際使用時代，一些大學及商業公司相繼研發了多種基于邏輯規劃語言和面向過程語言的約束規劃工具。1996 年，在美國計算機協會ACM 成立五十周年大會上，約束規劃被列為21 世紀計算機領域戰略研究方向之一。同年，約束規劃期刊Constraints創刊。2005 年約束規劃協會ACP 在法國成立，旨在促進約束規劃的理論及應用發展，其每年舉辦的約束規劃理論及實踐國際會議CP 與整合約束規劃、人工智能及運籌學國際會議CPAIOR（非約束規劃協會舉辦）已成為約束規劃研究交流的兩項重要國際學術會議。此外，近些年，在IJCAI、AAAI、ECAI 等一些國際頂級的人工智能會議上，都有對約束規劃相關研究的專題討論。當前，約束規劃已成為人工智能領域的一個研究熱點。

約束規劃采用約束傳播[11]和回溯搜索[12]來解決問題，約束傳播用于修剪搜索空間，回溯搜索對搜索空間進行遍歷，實現問題求解。在搜索過程中如何選擇變量構建搜索樹是一個十分關鍵的步驟，選擇“正確”變量賦值可減少無效搜索分支，提高求解效率。

假設一個簡單的約束滿足問題包含n 個白變量和m 個黑變量。白變量值域為{0，1}，黑變量值域為{0，1，2，…，m-2}，對于黑變量要求其兩兩取值不同，而白變量沒有約束限制。可以很容易分析出該約束滿足問題沒有滿足約束條件的解。假設在回溯搜索過程中采用的變量排序啟發式優先選擇白變量進行賦值，待所有白變量賦值完成后再選擇黑變量賦值，則該啟發式對應的搜索樹如圖1左所示，求解時會對整個搜索空間進行遍歷。若在開始搜索之后采用動態的變量排序啟發式選擇可能導致搜索失敗的變量構建搜索樹，則搜索樹如圖1右所示，可以看到合適的變量排序啟發式策略可對搜索樹進行有效剪枝，提高問題求解效率。

圖1 應用變量排序啟發式效果示例

目前，針對變量選擇已有多種獨立和組合變量排序啟發式被提出，包括dom[13]、deg[14]、IBS[15]、ABS[16]、CBS[17]、CRBS[18]、dom/deg[19]、dom/ddeg[20]、dom/wdeg[13]等。這些啟發式基于變量屬性或問題求解狀態選擇合適變量，加快搜索進程。但由于待解決問題種類、特征不同及啟發式自身特性等原因，一個變量排序啟發式即使在多數問題求解上剪枝效果較好，也無法保證在所有問題求解上都要優于其他啟發式。從搜索過程出發尋找利用問題求解通性，屏蔽問題之間的差異對求解過程的影響，提出和研究改進更為有效、適用范圍更廣的獨立或組合的通用啟發式仍是約束規劃研究中一個重要的研究方向。

本文采用一種新穎的變量排序啟發式組合策略ParetoHeu[21]將經典的啟發式dom/wdeg與基于關聯的啟發式CRBS（Correlation-Based Search）結合，以提高和增強CRBS對問題的求解效率和通用性。同時，加入基于實例化失敗次數的權值統計方法[22]進一步對待實例化變量進行選擇，提出了crbs-sum及crbs-max的兩種改進變量排序啟發式PICS 和PICM。實驗在Choco[23]約束求解器上實現，并在多個約束滿足問題實例上進行測試。實驗結果表明PICS 和PICM 與crbs-sum、crbsmax 及其他經典主流啟發式相比，在多個問題實例求解上，兩種新變量排序啟發式方法的求解效率高于其他啟發式。

2 相關工作

變量排序啟發式對回溯搜索效率有著重要影響，選擇合適變量實例化可以顯著減小搜索空間，從而更快地解決問題。在一些規模較大的問題求解上，一個“正確”或“錯誤”的決定可以使求解時間產生指數級的變化。目前，已有多種變量排序啟發式相繼提出。這些啟發式大多遵循“失敗優先”原則，即優先選擇可能導致搜索失敗的變量進行實例化，并基于變量值域大小、約束圖、約束觸發失敗次數等特征定義得分函數，在每個搜索節點上選擇得分函數最高的變量實例化。

變量排序啟發式可分靜態變量排序啟發式和動態變量排序啟發式兩類。靜態變量排序啟發式在搜索之前計算變量得分并確定實例化變量序列，在搜索過程中不會對變量序列進行調整，一些已經提出的靜態排序啟發式包括選擇相關約束最多變量的啟發式deg[14]、選擇最小約束網絡寬度的啟發式width[12]等。動態變量排序啟發式在搜索期間動態更新變量得分并調整變量排序。在實際使用中，動態排序啟發式的應用多于靜態排序啟發式。早期的獨立或組合動態排序啟發式都是根據變量基本屬性來選擇變量，如第一個動態排序啟發式dom[13]基于值域大小選擇變量、動態的deg 啟發式ddeg[14]、dom/deg[19]、dom/ddeg[20]等。之后，一些基于問題求解狀態和自定義變量特征的啟發式相繼提出，包括基于影響的啟發式IBS（Impact-Based Search）[15]、基于沖突的啟發式wdeg[24]、基于活躍度的啟發式ABS（Activity-Based Search）[16]、dom/wdeg[13]、基于約束緊度和解密度的啟發式RHO[25]等。目前，IBS、ABS 和dom/wdeg 是大多數約束規劃求解器中主要使用的三種啟發式。IBS啟發式通過衡量變量實例化導致潛在搜索空間的減少程度選擇變量。Wdeg啟發式為每個約束賦予一個權重值，當搜索產生沖突時，相應約束的權重會增加，啟發式會優先選擇約束權重之和最大的變量。ABS 啟發式基于每個變量值域變動頻率選擇變量。近些年提出的一些較為新穎的啟發式及改進啟發式主要有基于統計變量賦值在解中出現的頻率的CBS（Count-Based Search）[17]、基于失敗原因解釋的改進wdeg[26]、優先選擇最后沖突的變量的LC（Last Conflict heuristic）[27]、沖突排序的COS（Conflict Ordering Search）[28]、基于約束緊度的改進dom/ddeg和dom/wdeg[29]、基于變量關聯的CRBS以及基于帕累托最優的啟發式組合策略ParetoHeu等。這些變量排序啟發式都基于問題變量、約束的自身屬性或研究人員自定義屬性來選擇變量，不考慮問題本身的性質，從而將問題本身與變量選擇分離，使其可用于對大部分問題求解，而不是只針對一個或一類問題，具有一定的通用性。因此，對于提高變量排序啟發式通用性研究的著手點也在于如何利用變量、約束的基本屬性或與其相關的自定義屬性來選擇變量。此外，在Li等人的研究[21]中，實驗結果顯示組合啟發式在多數情況下要優于原單啟發式，早期的dom/ddeg、dom/wdeg等組合啟發式也很好地印證了這一點，文章中應用其提出的ParetoHeu 啟發式組合策略在問題求解上平均CPU時間要少于傳統的順序啟發式組合策略和得分乘積啟發式組合策略，ParetoHeu為組合啟發式提供了一個新的思路。

除上述獨立啟發式與組合啟發式研究外，還有一些關于自適應變量排序啟發式的研究，這類啟發式稱為超啟發式（hyper-heuristic）[30]，其根據解決方案數量、目標函數值、已運行時間等問題狀態特征，從包含多個獨立啟發式的序列中為搜索過程動態選擇啟發式。一些研究[21]包括基于機器學習[31-32]和基于演化計算[33]的超啟發式。目前，這些方法尚未在主流約束規劃求解器中實現和應用。

3 相關定義

約束滿足問題（Constraint Satisfaction Problem，CSP）[34]源于人工智能研究，多為NP-hard 問題，可定義為三元組P=＜X,D,C ＞，其中X={x1,x2,…,xn}為變量集，D={dom(x1),dom(x2),…,dom(xn)}為X 中各變量值域dom( xi)的集合，每個變量值域大小記作|dom( xi)|。為約束集，約束是各變量取值的制約關系。變量xi涉及約束的個數稱為度（degree），每個約束ci可記成( scp( ci),rel( ci))，scp( ci)={ x1,x2,…,xr} 是一個有序的變量子集，為約束ci所涉及到的變量，rel(ci)是scp(ci)內每個變量值域笛卡爾乘積D(x1)×D(x2)×…×D(xr)的一個子集，每個元組τ ∈rel(ci)是一個有序的變量取值的集合，可定義為＜(x1,a1),(x2,a2),…,(xr,ar)＞，其中aj∈dom(xj),j=1,2,…,r。

約束滿足問題的求解是依次為每個變量在其值域中選擇一個合適的值，使所有變量賦值后滿足全部約束，為變量賦值的過程稱為實例化（instantiate）。在約束規劃中常采用約束傳播與回溯搜索結合的方式對CSP進行求解。約束傳播使用相容性技術（consistency technology）在搜索前和搜索過程中從變量值域里移除不屬于任何可行解的值，進而減小搜索空間，加快搜索進程，出于時間復雜度和空間復雜度的考慮，約束求解器中最常使用的為弧相容（Arc Consistency，AC）[11]和邊界相容（Bounds Consistency，BC）[11]算法。回溯搜索用于實現對問題求解，在搜索過程中會使用變量排序啟發式選擇待實例化變量構建搜索樹，變量排序啟發式會對搜索效率產生巨大影響。在回溯搜索期間，已實例化變量稱為PastVar。相反，未實例化變量稱為FutVar。

4 基于ParetoHeu和實例化失敗統計的關聯啟發式方法PICRBS

4.1 PICRBS思想

為進一步提升和增強關聯啟發式CRBS 對問題的求解效率和通用性，本文提出了基于ParetoHeu 和實例化失敗統計的關聯啟發式PICRBS，并根據CRBS 中兩種變量選擇方式crbs-sum 和crbs-max 提出了具體方法PICS 和PICM，PICS 與PICM 的區別在于兩種方法計算CRBS啟發式得分方式不同。

PICRBS 采用基于帕累托最優（Pareto optimality）的啟發式組合策略ParetoHeu 將啟發式CRBS 與dom/wdeg 結合，在未實例化變量中選擇最可能導致搜索發生沖突的變量，加入帕累托候選變量集合中。之后使用基于實例化失敗次數的權值統計方法對帕累托候選變量集合中的變量做進一步篩選。已有研究發現變量實例化的失敗次數在一定程度上可說明該變量與已實例化變量集之間的沖突關系[22]，因此選擇實例化失敗次數最多的變量作為待實例化變量可增加搜索過程中發生沖突的可能，從而使搜索樹盡早剪枝，加快問題求解。

PICRBS通過對變量值域在搜索中改變頻率以及變量相關約束導致回溯次數的雙重衡量，從變量自身及約束兩個方面考慮選擇該變量導致搜索發生回溯的可能，使變量實例化后搜索樹可最大化剪枝。同時，雙重衡量也可防止因單啟發式對問題求解的不適用而導致問題求解時間過長甚至無法求解，增強了啟發式的通用性。在組合啟發式后使用基于實例化失敗的權值統計方法，選擇實例化后導致搜索沖突可能性相對更高的變量，可對啟發式求解問題的效率做進一步提升。

4.2 PICRBS流程

PICRBS流程圖如圖2所示。在搜索期間，PICRBS維持存儲所有變量對關聯性的對稱關聯矩陣、統計約束權值和各變量實例化失敗次數。進行變量選擇時，PICRBS遍歷未實例化變量集合FutVars，對集合中變量xi計算啟發式CRBS（crbs-sum/crbs-max）和dom/wdeg得分（兩種得分分別記作sc1 和sc2），并依次與帕累托候選變量集合ParetoFront 中的變量xj比較兩種啟發式得分，若sc1[xi]≥sc1[xj]且sc2[xi]＞sc2[xj]或sc2[xi]≥sc2[xj]且sc1[xi]＞sc1[xj]，稱變量xi支配（dominate）變量xj，PICRBS 將xi作為帕累托候選變量添加到候選變量集合ParetoFront中，同時由xi支配的變量xj都將從集合中移除。如果xi和xj的啟發式得分相同，xi被添加到ParetoFront中。對于ParetoFront中得分相同的變量，PICRBS 通過變量實例化失敗次數進行進一步篩選，選擇搜索期間實例化失敗次數最多的變量作為待實例化變量加入集合MaxInsta中，若MaxInsta中存在多個失敗次數相同的變量，則對這些變量進行隨機選擇。在變量實例化后，如果搜索未發生沖突，對關聯矩陣進行更新。反之，更新關聯矩陣同時對約束權值和變量實例化失敗次數進行加權更新。

關聯矩陣更新方式及PICRBS中CRBS啟發式得分計算規則如下：當選擇某個變量xi實例化并進行約束傳播后，若發生沖突，即有變量值域被清空，關聯矩陣按式（1）規則進行更新，其中X'=X{xi}為X 去除xi后的變量集合，為更新前的關聯值。

若無沖突發生，則按式（2）規則更新關聯矩陣，dom'(xj)為約束傳播后變量xj的值域，U 和N 分別為約束傳播后值域發生變化和沒有變化的變量集合。

圖2 PICRBS流程圖

啟發式CRBS 計算得分有兩種方式，crbs-sum 與crbs-max。PICS和PICM 分別采用這兩種計算方式，計算規則如式（3）和（4）所示。 Pc(xi)為已實例化變量與xi關聯值的和，Fc(xi)為未實例化變量與xi關聯值的和，在計算時變量xi記為未實例化變量，參數0 ≤θ ≤1用于調整Pc(xi) 與Fc(xi) 的組合關系。在計算crbssum(xi) 或crbs-max(xi) 后，crbs-sum 和crbs-max 會將crbs-sum(xi)/dom(xi) 和crbs-max(xi)/dom(xi) 作 為 最終啟發式得分。

約束權值weight[c]是啟發式dom/wdeg為每個約束c ∈C 設置的屬性值，初始為1，當變量實例化導致沖突時，權重值加1。作為變量得分。式（5）為變量權重和計算公式，其中FutScp(c)為scp(c)中的未實例化變量集合。

變量實例化失敗次數權值統計公式如式（6）所示，其中var_ fails 為變量實例化失敗次數，dom 為變量值域大小。

PICRBS關鍵部分偽代碼如下：

算法1 PICRBS(FutVars,sc1,sc2,insta)

輸入：FutVars,sc1,sc2,insta

輸出：MaxInsta

1.ParetoFront←?；

2.MaxInsta←?；

3.tempMaxInsta=?1；

4.for each variable xiin FutVars do

5. isPareto←true；

6. for each variable xjin ParetoFront do

7. if xidominates xjthen

8. ParetoFront ←ParetoFront{xj}；

9. else

10. if xjdominates xithen

11. is Pareto←false；

12. end if

13. break；

14. end if

15. end for

16. if isPareto then

17. ParetoFront←ParetoFront∪{xi}；

18. end if

19.end for

20.for each variable xiin ParetoFront do

21. if insta[xi]>tempMaxInsta then

22. tempMaxInsta=insta[xi]；

23. MaxInsta←?；

24. MaxInsta←MaxInsta∪{xi}；

25. else

26. if insta[xi]==tempMaxInsta then

27. MaxInsta←MaxInsta∪{xi}

28. end if

29. end if

30.end for

31.return MaxInsta

偽代碼中參數FutVars、sc1、sc2、insta 分別為未實例化變量集合、CRBS 啟發式得分、dom/wdeg 啟發式得分和待解決約束滿足問題中所有變量集合。方法開始時先建立兩個空集合ParetoFront 和MaxInsta 分別用于存儲帕累托候選變量以及實例化失敗次數最多變量，tempMaxInsta 記錄當前最大實例化失敗次數。在構建搜索樹時，對于未實例化變量集合FutVars 中的變量進行遍歷，選擇兩種啟發式得分都最高的變量加入集合，在遍歷過程中對ParetoFront 進行動態更新。待所有變量遍歷完畢后，通過基于變量實例化失敗次數對ParetoFront 中變量做進一步篩選，選擇以往搜索中實例化失敗次數最多的一個變量或多個變量加入MaxInsta 集合，若MaxInsta 中多于一個變量，則對變量進行隨機選取，最后返回一個變量構建搜索樹。

5 實驗及結果分析

5.1 實驗數據

本文實驗數據為國際測試通用的約束滿足問題，其中一部分為2018年約束求解器競賽基準問題。實驗中，對于每類問題分別選取了不同規模的實例，共177 個，這些實例均可在http：//xcsp.org/上下載。測試所用的基準約束滿足問題包括：SportsScheduling、StripPacking、SocialGolfers、MagicHexagon、GracefulGraph、Frb、Bibd、QueensKnights、Hanoi、Driverlogw、Eternity、ColouredQueens、Crossword。

5.2 實驗配置及說明

實驗在約束求解器Choco 4.0.8上完成。實驗環境及配置為JDK8，Windows操作系統，英特爾i5-3337U雙核處理器1.8 GHz，4 GB DDR3內存。

實驗中與PICS 和PICM 對比的啟發式方法包括：IBS[15]、ABS[16]、dom/wdeg（d/w）[13]、crbs-sum（c-s）[18]和crbsmax（c-m）[18]。在實驗中，采用geometric重啟策略，初始cutoff=10，ρ=0.1。cutoff 為最大失敗數，ρ 控制重啟之后最大失敗數增長，公式為cutoff=cutoff'+init_cutoff×ρk。 cutoff′ 為上一次失敗次數，k 為重啟次數。搜索使用二元分支深度優先搜索，求解時限為1 200 s。對 于 啟 發 式crbs-sum 和PICS，參 數θ 設 為0.1。在PICS 和PICM 中為了選取最高得分，dom/wdeg計算采用對于實驗中的隨機數，隨機種子均設為0。

實驗測評指標包括啟發式成功求解問題實例數量，所有啟發式均可求解問題的平均時間、平均搜索樹節點。在對時間指標統計時，為避免極端求解時間對實驗評估產生影響以及更準確地反映問題求解時間，實驗對每個問題實例進行5次求解，最終統計時除去最長與最短求解時間，取剩余3次求解時間的平均值。

5.3 實驗結果及分析

表1 給出了各啟發式對于測試問題實例的成功求解個數、平均時間和平均節點。問題名稱后括號內為實驗選取問題實例個數，時間和節點后括號內為該類問題啟發式均可求解實例個數。PICS 和PICM 作為本文提出的c-s 和c-m 改進啟發式分別在11/13、9/13 個問題求解上相對于后兩者搜索樹節點有所減少，在Graceful-Graph 問題上最為明顯，分別減少了99.75%和98.73%，求解時間有大幅度提升。除GracefulGraph 問題外，在其他搜索樹節點減少的問題中，兩種改進啟發式在搜索樹節點上相對于改進前平均減少46.1%和50.47%，求解時間平均降低了44.83%和29.65%。PICS和PICM分別在10、8、9和10、6、7個問題求解上優于三種主流啟發式IBS、d/w、ABS。

各啟發式總求解實例數量及總平均時間和節點數如圖3所示。從圖中可以看到，IBS、d/w、ABS、c-s、c-m、PICS和PICM在限制時間內依次成功求解了85、90、85、82、87、96、90 個問題實例，PICS 求解數量最多，c-s 最少。同時，PICS在全部求解實例中平均表現最優，在多個共同求解問題中無耗時較長的求解結果，平均時間比次優的PICM 少近9 s，平均搜索樹節點減少了三分之二。IBS 啟發式在多數問題求解中時長和節點數均大于其他啟發式。兩種主流通用啟發式ABS、d/w在個別問題求解上表現并不理想。從最終結果來看，在測試問題實例上，c-s與c-m啟發式僅優于IBS啟發式。他啟發式，PICM 啟發式在問題實例driverlogw-09 求解上與c-m相比搜索樹節點少于后者，但求解時間恰恰相

表1 各啟發式對測試問題求解個數、平均時間和平均節點

圖3 各啟發式測評指標比較

一般來說，搜索樹節點數與運行時間成正比，節點數越大求解時間越長，但由于問題特性和啟發式時間復雜度較高等原因，一些啟發式在求解某些規模較小的問題實例時，會出現搜索樹節點數少于其他啟發式而求解時間較長的情況。表2 給出了各啟發式對部分問題實例的求解時間和節點的實驗結果（TO 表示求解超時）。如表2 所示，IBS 啟發式在求解問題實例Hanoi-06 中搜索樹節點為其他啟發式的一半，但其求解時間遠大于其反。實驗中，這種情況在IBS 啟發式上體現較為明顯，但求解時間不會與Hanoi-06 實例一樣與其他啟發式相距懸殊。

表3 加入權值統計方法前后啟發式節點對比

表3給出了CRBS與d/w采用ParetoHeu結合的啟發式在加入基于權值統計方法前后部分問題實例求解的搜索樹節點數量。在多個問題實例中，加入基于權值的統計方法可以進一步減少搜索樹節點，加快問題求解。需要注意的是，在一些問題實例上加入該方法也會導致節點數增多，如表3中后兩行所示。從所有問題求解的最終結果來看，加入權值統計方法的組合啟發式效果較好。

總體而言，在多種問題實例進行測試結果顯示，采用ParetoHeu結合d/w并加入基于實例化次數權值方法的關聯啟發式方法，相對于原始啟發式有了很大性能提升，并在一些問題上與主流啟發式相比具有競爭力。

6 結束語

本文采用基于帕累托最優的啟發式組合策略ParetoHeu將啟發式CRBS與經典啟發式d/w相結合，以提高CRBS的求解速度和增強通用性，同時加入基于實例化失敗次數的權值統計方法，以進一步減小搜索樹大小，提高求解效率，提出了兩種CRBS 改進啟發式PICS與PICM。在多個國際通用測試約束滿足問題求解上，PICS 和PICM 相對與改進前平均搜索樹節點和求解時間有所減少，并與主流啟發式相比具有一定競爭力。未來將對多種變量排序啟發式及約束規劃求解問題的特征做進一步研究，以提出更為有效的獨立或組合通用啟發式。