Dom/ddeg自主分支輔助決策約束求解

王海燕, 李 闖, 張 良， 董延華

(1.吉林師范大學 計算機學院, 吉林 四平 136000; 2.吉林大學 計算機科學與技術學院, 長春 130012)

研究快報

Dom/ddeg自主分支輔助決策約束求解

王海燕1, 李 闖2, 張 良2， 董延華1

(1.吉林師范大學 計算機學院, 吉林 四平 136000; 2.吉林大學 計算機科學與技術學院, 長春 130012)

基于自主分支約束求解方法, 提出一種新的自主分支輔助決策約束求解算法AUTOdom/ddeg, 并在標準測試庫Benchmarks上進行對比實驗.實驗結果表明, AUTOdom/ddeg算法能顯著提高求解效率.

約束求解; 自主分支; 啟發(fā)式; 輔助決策

約束求解是約束滿足問題(constraint satisfaction problems, CSP)[1]的核心, 尋求高效約束求解方法[2-3]是CSP的關鍵問題.其搜索過程基于某種分支策略, 在變量排序啟發(fā)式(variable ordering heuristic, VOH)和值排序啟發(fā)式(value ordering heuristic, V_O_H)引導下, 不斷探索問題的解, 目前已有許多研究結果[4-7].

在CSP回溯搜索中, 搜索分支的選擇有多種策略[8], 其中二分支和多分支最典型.受限的二分支[6]是二分支策略的限制版本, 它與多分支接近.不同分支策略在不同VOH下表現(xiàn)出不同的性能.自主分支求解算法則在搜索中根據(jù)某點實際需要選擇更適合的分支策略, 與VOH及V_O_H配合約束求解.求解時運用的策略稱為自主分支啟發(fā)式策略, 其中最有影響力的是Hsdiff(e)和Hcadv(VOH2), 兩種策略既可單獨應用也可合取或析取使用.其中, Hsdiff(e)可通過調節(jié)閾值e改變策略的影響力； Hcadv(VOH2)則借助VOH2促成分支的輔助決策.

輔助決策啟發(fā)式VOH2有多種選擇, 如dom[9],ddeg,wdeg[10],alldel,dom/ddeg[9],dom/wdeg和dom/alldel[10]等.不同的VOH2對自主分支約束求解方法效率的影響不同, 合適的VOH2可快速引導分支定位, 進而高效求解.文獻[6]中VOH和VOH2分別使用dom/wdeg和wdeg, 二者原理接近, 作出的決定易相同, 而其他高效啟發(fā)式中, dom/ddeg借助動態(tài)度的信息輔助決策, 與主要VOH差異最大, 因此推測將其作為輔助決策VOH2, 配合主啟發(fā)式dom/wdeg進行約束求解, 效率上會有更大提升.基于以上分析, 本文提出一種新的自主分支輔助決策約束求解算法AUTOdom/ddeg, 在自主分支選擇過程中, 借助dom/ddeg輔助主要變量排序啟發(fā)式分支決策.在標準測試庫Benchmarks多種實例上進行對比實驗, 實驗結果表明AUTOdom/ddeg算法能顯著提高求解效率.

1 自主分支輔助決策約束求解算法

Hcadv(VOH2)為輔助決策啟發(fā)式; dom是典型的動態(tài)變量排序啟發(fā)式, 按當前論域大小升序排列變量, 依次實例化; wdeg是基于最先失敗原則的沖突驅動啟發(fā)式, wdeg選擇權重最大的變量優(yōu)先實例化; dom/wdeg則將沖突和論域的信息相結合, 優(yōu)先選擇論域大小和沖突比值最小的變量； ddeg為動態(tài)度變量排序啟發(fā)式, 按當前狀態(tài)的動態(tài)度降序排列變量, 依次實例化； dom/ddeg將論域信息與動態(tài)度信息綜合考慮, 掌握全局動態(tài)信息.在實驗中, Hsdiff(e) 和Hcadv(VOH2)中主要VOH均選擇效果突出的dom/wdeg, 設e=0.1.

自主分支輔助決策約束求解算法中主要的環(huán)節(jié)之一是變量選擇, 在弧相容維持過程中, 不斷選擇未實例化變量賦值, 直到所有變量均被實例化.借助選擇變量是當前變量還是其他變量確定分支方式.VARIABLE_SELECTION函數(shù)在整個維持弧相容過程中起到變量選擇作用, 它通過Hcadv(VOH2)和Hsdiff(e)啟發(fā)式的合取或析取, 確定下一個實例化變量, 滿足條件, 則選擇其他變量, 該函數(shù)是自主分支的具體實現(xiàn).

VARIABLE_SELECTION函數(shù)描述如下.

輸入： 集合Uninstant_variables, Boolean變量Limited;

輸出： 下一個實例化變量;

1) 判斷Limited的值；

2) 若為假, 依據(jù)dom/wdeg選擇Uninstant_variables中的某個變量進行下一步實例化；

3) 若為真, 先依據(jù)dom/wdeg選擇Uninstant_variables中的某個變量為假設實例化變量;

4) 判斷假設實例化變量與當前實例化變量是否一致；

5) 一致, 則返回此變量；

6) 不一致, 借助Hcadv(VOH2)和Hsdiff(e)兩個啟發(fā)式的單獨或結合使用輔助決策；

7) 輔助決策和dom/wdeg一致, 選擇假設實例化變量進行下一步實例化；

8) 輔助決策和dom/wdeg不一致, 選擇當前實例化變量進行下一步實例化.

Uninstant_variables是所有未實例化變量集合.在自主分支定位過程中需要區(qū)分普通的二分支和受限的二分支策略, 區(qū)別在于是否將下一實例化變量限定為當前變量.為適應性決定下一次是否需要判斷限定分支, 設定Boolean變量Limited為標志變量, 值真表示需要判斷, 否則不需要.具體選擇哪種分支, 由啟發(fā)式視情況決定, 如果與主要變量排序啟發(fā)式dom/wdeg決定一致, 則采用普通的二分支策略; 反之, 選擇受限的二分支策略.

2 自主分支輔助決策約束求解算法AUTOdom/ddeg

基于上述分析可見, 原輔助顧問啟發(fā)式wdeg與主要變量排序啟發(fā)式dom/wdeg關系密切, 同屬沖突驅動啟發(fā)式, 在預測失敗可能性時, 均利用實際失敗次數(shù), 這將導致如果dom/wdeg在判斷分支時產(chǎn)生錯誤, 則wdeg作出同樣錯誤決定的可能性會很高.而啟發(fā)式dom/ddeg與dom/wdeg在衡量標準上不同, 依據(jù)當前論域與動態(tài)度的比值判定分支走向, 如果作出決定一致, 則說明兩種衡量標準得出結論一致, 必然增加正確分支選擇的可能性, 二者配合, 會推進自主分支適應合理化.

實驗環(huán)境建立在雙核處理器的DELL機上, 主頻1.90 GHz.比較CPU運行時間(t/ms)、約束檢查次數(shù)(#ccks)和搜索樹生成節(jié)點數(shù)(#nodes).

表1 AUTOdom/ddeg算法優(yōu)勢對比Table 1 AUTOdom/ddeg advantages

由于t是效率的最直接體現(xiàn), 因此主要比較該項標準.由表1可見, AUTOdom/ddeg效率明顯高于原算法.如graph14中, 析取策略配合dom/ddeg的t=1 141 ms, 而其配合wdeg則達到5 813 ms, 高了近4倍.有些實例中效率變化顯著, 如qwh-order20-holes166-balanced-18-QWH-20, 3種策略配合dom/ddeg的效率較相應策略配合wdeg提高了4～7倍, 而在qwh-order20-holes166-balanced-20-QWH-20中, 效率提升達到38～70倍.尤其是QCPp-20這類問題, 效率提高顯著.實例qcp-order20-holes187-balanced-14-QWH-20尤為明顯, 析取配合dom/ddeg的t=247 078 ms, 而配合wdeg時則達到了39 265 657 ms, 效率比是1∶159, H2配合wdeg的t=48 509 234 ms, 而其配合dom/ddeg卻提升到了26 485 ms.實驗數(shù)據(jù)表明, 算法AUTOdom/ddeg作出的決定更貼切體現(xiàn)分支切換動態(tài)信息.

對#ccks和#nodes, 本文算法也有較大優(yōu)勢.如實例qwh-order20-holes166-balanced-20-QWH-20中合取策略的#ccks對比, 原算法的值是AUTOdom/ddeg算法的40多倍, 而實例qcp-order20-holes187-balanced-14-QWH-20的H2策略中#ccks值則比本文算法高了近800倍, #nodes對比值超過了900倍.綜合3項衡量標準, AUTOdom/ddeg算法優(yōu)勢明顯.這主要是因為wdeg和dom/wdeg均通過從失敗中學習的信息去管理變量選擇和分配的VOH所致.當用于分支選擇中時, 兩者判定的依據(jù)近似, 產(chǎn)生分歧的可能性降低, 進而選擇合適分支的可能性降低； 而dom/ddeg除了依據(jù)論域大小信息外, 參考的是約束圖中當前動態(tài)度信息, 本質上不屬于基于沖突啟發(fā)式, 在dom/wdeg考慮失敗信息后, dom/ddeg會從其他方面綜合建議, 選擇適合分支的可能性提高, 進而提高了自適應分支啟發(fā)式的準確性.

綜上所述, 本文在自主分支輔助決策框架基礎上, 提出了一種新的AUTOdom/ddeg算法.為驗證AUTOdom/ddeg求解效率的優(yōu)勢, 在標準測試庫Benchmarks中的rlfapGraphs,rlfapModGraphs,QWH-20和QCPp-20等多類問題類上進行實驗.實驗結果表明, AUTOdom/ddeg較借助wdeg輔助決策的自主分支輔助決策算法有絕對優(yōu)勢, 效率提升幅度較大.

[1]Francois Rossi, Peter Beek, van, Toby Walsh, et al.Handbook of Constraint Programming [M].Amsterdam: Elsevier, 2006.

[2]王秦輝, 陳恩紅, 王煦法.分布式約束滿足問題研究及其進展 [J].軟件學報, 2006, 17(10): 2029-2039.(WANG Qinhui, CHEN Enhong, WANG Xufa.Research and Development of Distributed Constraint Satisfaction Problems [J].Journal of Software, 2006, 17(10): 2029-2039.)

[3]季曉慧, 黃拙, 張健.約束求解與優(yōu)化技術的結合 [J].計算機學報, 2005, 28(11): 1790-1797.(JI Xiaohui, HUANG Zhuo, ZHANG Jian.On the Integration of Constraint Programming and Optimization [J].Chinese Journal of Computers, 2005, 28(11): 1790-1797.)

[4]Stergiou K.Heuristics for Dynamically Adapting Propagation [C]//Proceeding of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence.Amsterdam: IOS Press, 2008: 485-489.

[5]Hutter F, Hoos H H, Leyton-Brown K, et al.ParamILS: An Automatic Algorithm Configuration Framework [J].Journal of Artificial Intelligence Research, 2009, 36: 267-306.

[6]Balafoutis T, Stergiou K.Adaptive Branching for Constraint Satisfaction Problems [C]//Proceeding of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence.Amsterdam: IOS Press, 2010: 855-860.

[7]Hamadi Y, Monfroy E, Saubion F.Autonomous Search [M].Berlin: Springer, 2012.

[8]Balafoutis T, Paparrizou A, Stergiou K.Experimental Evaluation of Branching Schemes for the CSP [EB/OL].2010-09-02.http://arxiv.org/abs/1009.0407.

[9]Bessière C, Chmeiss A, Sais L.Neighborhood-Based Variable Ordering Heuristics for the Constraint Satisfaction Problem [C]//7th International Conference, Cp2001.Berlin: Springer, 2001: 565-569.

[10]Grimes D, Wallace R J.Sampling Strategies and Variable Selection in Weighted Degree Heuristics [C]//13th International Conference, Cp2007.Berlin: Springer, 2007: 831-838.

Autonomous-BranchingConstraintSolvingAidedbyDom/ddegDecisionMaking

WANG Haiyan1, LI Chuang2, ZHANG Liang2, DONG Yanhua1
(1.CollegeofComputer,JilinNormalUniversity,Siping136000,JilinProvince,China;
2.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)

The authors proposed a new autonomous-branching constraint solving algorithm AUTOdom/ddegaided by decision making on the basis of the current autonomous-branching constraint solving methods.To verify the efficiency of AUTOdom/ddeg, abundant comparison experiments on Benchmarks were carried out.The experimental results show that AUTOdom/ddegcan significantly improve the efficiency of constraint solving.

constraint solving; autonomous-branching; heuristics; aid decision making

2014-08-11.

王海燕(1980—), 女, 漢族, 博士, 講師, 從事約束求解與約束優(yōu)化的研究, E-mail： jlsdwhy_0820@sina.cn.通信作者： 董延華(1971—), 男, 漢族, 博士, 教授, 從事信息處理的研究, E-mail: computerdyp@jlnu.edu.cn.

國家自然科學基金(批準號: 61373052; 61100090; 61170314; 41172294)、吉林省自然科學基金(批準號: 201115220)、吉林省教育廳“十二五”科學技術研究項目(批準號: [2011]第415號; [2014]第490號)、吉林省科技發(fā)展計劃項目(批準號: 20140101206JC)、吉林省計算中心公共計算平臺資助項目(批準號: 20140101206JC )、吉林師范大學博士啟動基金(批準號: 2013018)、吉林師范大學碩士啟動基金(批準號: 2009035)和四平市科技發(fā)展計劃項目(批準號: 2012042; 2013058).

TP31

A

1671-5489(2014)06-1289-04

10.13413/j.cnki.jdxblxb.2014.06.34

韓 嘯)