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

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

(1.吉林師范大學(xué) 計(jì)算機(jī)學(xué)院, 吉林 四平 136000; 2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130012)

研究快報(bào)

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

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

(1.吉林師范大學(xué) 計(jì)算機(jī)學(xué)院, 吉林 四平 136000; 2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130012)

基于自主分支約束求解方法, 提出一種新的自主分支輔助決策約束求解算法AUTOdom/ddeg, 并在標(biāo)準(zhǔn)測試庫Benchmarks上進(jìn)行對比實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明, AUTOdom/ddeg算法能顯著提高求解效率.

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

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

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

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

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

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

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

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

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

輸出： 下一個(gè)實(shí)例化變量;

1) 判斷Limited的值；

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

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

4) 判斷假設(shè)實(shí)例化變量與當(dāng)前實(shí)例化變量是否一致；

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

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

7) 輔助決策和dom/wdeg一致, 選擇假設(shè)實(shí)例化變量進(jìn)行下一步實(shí)例化；

8) 輔助決策和dom/wdeg不一致, 選擇當(dāng)前實(shí)例化變量進(jìn)行下一步實(shí)例化.

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

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

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

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

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

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

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

綜上所述, 本文在自主分支輔助決策框架基礎(chǔ)上, 提出了一種新的AUTOdom/ddeg算法.為驗(yàn)證AUTOdom/ddeg求解效率的優(yōu)勢, 在標(biāo)準(zhǔn)測試庫Benchmarks中的rlfapGraphs,rlfapModGraphs,QWH-20和QCPp-20等多類問題類上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明, 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ìn)展 [J].軟件學(xué)報(bào), 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)化技術(shù)的結(jié)合 [J].計(jì)算機(jī)學(xué)報(bào), 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.

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

TP31

A

1671-5489(2014)06-1289-04

10.13413/j.cnki.jdxblxb.2014.06.34

韓 嘯)