Dom/ddeg自主分支辅助决策约束求解

王海燕, 李 闯, 张 良， 董延华

(1.吉林师范大学 计算机学院, 吉林 四平 136000; 2.吉林大学 计算机科学与技术学院, 长春 130012)

研究快报

Dom/ddeg自主分支辅助决策约束求解

王海燕1, 李 闯2, 张 良2， 董延华1

(1.吉林师范大学 计算机学院, 吉林 四平 136000; 2.吉林大学 计算机科学与技术学院, 长春 130012)

基于自主分支约束求解方法, 提出一种新的自主分支辅助决策约束求解算法AUTOdom/ddeg, 并在标准测试库Benchmarks上进行对比实验.实验结果表明, AUTOdom/ddeg算法能显著提高求解效率.

约束求解; 自主分支; 启发式; 辅助决策

约束求解是约束满足问题(constraint satisfaction problems, CSP)[1]的核心, 寻求高效约束求解方法[2-3]是CSP的关键问题.其搜索过程基于某种分支策略, 在变量排序启发式(variable ordering heuristic, VOH)和值排序启发式(value ordering heuristic, V_O_H)引导下, 不断探索问题的解, 目前已有许多研究结果[4-7].

在CSP回溯搜索中, 搜索分支的选择有多种策略[8], 其中二分支和多分支最典型.受限的二分支[6]是二分支策略的限制版本, 它与多分支接近.不同分支策略在不同VOH下表现出不同的性能.自主分支求解算法则在搜索中根据某点实际需要选择更适合的分支策略, 与VOH及V_O_H配合约束求解.求解时运用的策略称为自主分支启发式策略, 其中最有影响力的是Hsdiff(e)和Hcadv(VOH2), 两种策略既可单独应用也可合取或析取使用.其中, Hsdiff(e)可通过调节阈值e改变策略的影响力； Hcadv(VOH2)则借助VOH2促成分支的辅助决策.

辅助决策启发式VOH2有多种选择, 如dom[9],ddeg,wdeg[10],alldel,dom/ddeg[9],dom/wdeg和dom/alldel[10]等.不同的VOH2对自主分支约束求解方法效率的影响不同, 合适的VOH2可快速引导分支定位, 进而高效求解.文献[6]中VOH和VOH2分别使用dom/wdeg和wdeg, 二者原理接近, 作出的决定易相同, 而其他高效启发式中, dom/ddeg借助动态度的信息辅助决策, 与主要VOH差异最大, 因此推测将其作为辅助决策VOH2, 配合主启发式dom/wdeg进行约束求解, 效率上会有更大提升.基于以上分析, 本文提出一种新的自主分支辅助决策约束求解算法AUTOdom/ddeg, 在自主分支选择过程中, 借助dom/ddeg辅助主要变量排序启发式分支决策.在标准测试库Benchmarks多种实例上进行对比实验, 实验结果表明AUTOdom/ddeg算法能显著提高求解效率.

1 自主分支辅助决策约束求解算法

Hcadv(VOH2)为辅助决策启发式; dom是典型的动态变量排序启发式, 按当前论域大小升序排列变量, 依次实例化; wdeg是基于最先失败原则的冲突驱动启发式, wdeg选择权重最大的变量优先实例化; dom/wdeg则将冲突和论域的信息相结合, 优先选择论域大小和冲突比值最小的变量； ddeg为动态度变量排序启发式, 按当前状态的动态度降序排列变量, 依次实例化； dom/ddeg将论域信息与动态度信息综合考虑, 掌握全局动态信息.在实验中, Hsdiff(e) 和Hcadv(VOH2)中主要VOH均选择效果突出的dom/wdeg, 设e=0.1.

自主分支辅助决策约束求解算法中主要的环节之一是变量选择, 在弧相容维持过程中, 不断选择未实例化变量赋值, 直到所有变量均被实例化.借助选择变量是当前变量还是其他变量确定分支方式.VARIABLE_SELECTION函数在整个维持弧相容过程中起到变量选择作用, 它通过Hcadv(VOH2)和Hsdiff(e)启发式的合取或析取, 确定下一个实例化变量, 满足条件, 则选择其他变量, 该函数是自主分支的具体实现.

VARIABLE_SELECTION函数描述如下.

输入： 集合Uninstant_variables, Boolean变量Limited;

输出： 下一个实例化变量;

1) 判断Limited的值；

2) 若为假, 依据dom/wdeg选择Uninstant_variables中的某个变量进行下一步实例化；

3) 若为真, 先依据dom/wdeg选择Uninstant_variables中的某个变量为假设实例化变量;

4) 判断假设实例化变量与当前实例化变量是否一致；

5) 一致, 则返回此变量；

6) 不一致, 借助Hcadv(VOH2)和Hsdiff(e)两个启发式的单独或结合使用辅助决策；

7) 辅助决策和dom/wdeg一致, 选择假设实例化变量进行下一步实例化；

8) 辅助决策和dom/wdeg不一致, 选择当前实例化变量进行下一步实例化.

Uninstant_variables是所有未实例化变量集合.在自主分支定位过程中需要区分普通的二分支和受限的二分支策略, 区别在于是否将下一实例化变量限定为当前变量.为适应性决定下一次是否需要判断限定分支, 设定Boolean变量Limited为标志变量, 值真表示需要判断, 否则不需要.具体选择哪种分支, 由启发式视情况决定, 如果与主要变量排序启发式dom/wdeg决定一致, 则采用普通的二分支策略; 反之, 选择受限的二分支策略.

2 自主分支辅助决策约束求解算法AUTOdom/ddeg

基于上述分析可见, 原辅助顾问启发式wdeg与主要变量排序启发式dom/wdeg关系密切, 同属冲突驱动启发式, 在预测失败可能性时, 均利用实际失败次数, 这将导致如果dom/wdeg在判断分支时产生错误, 则wdeg作出同样错误决定的可能性会很高.而启发式dom/ddeg与dom/wdeg在衡量标准上不同, 依据当前论域与动态度的比值判定分支走向, 如果作出决定一致, 则说明两种衡量标准得出结论一致, 必然增加正确分支选择的可能性, 二者配合, 会推进自主分支适应合理化.

实验环境建立在双核处理器的DELL机上, 主频1.90 GHz.比较CPU运行时间(t/ms)、约束检查次数(#ccks)和搜索树生成节点数(#nodes).

表1 AUTOdom/ddeg算法优势对比Table 1 AUTOdom/ddeg advantages

由于t是效率的最直接体现, 因此主要比较该项标准.由表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.实验数据表明, 算法AUTOdom/ddeg作出的决定更贴切体现分支切换动态信息.

对#ccks和#nodes, 本文算法也有较大优势.如实例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算法优势明显.这主要是因为wdeg和dom/wdeg均通过从失败中学习的信息去管理变量选择和分配的VOH所致.当用于分支选择中时, 两者判定的依据近似, 产生分歧的可能性降低, 进而选择合适分支的可能性降低； 而dom/ddeg除了依据论域大小信息外, 参考的是约束图中当前动态度信息, 本质上不属于基于冲突启发式, 在dom/wdeg考虑失败信息后, dom/ddeg会从其他方面综合建议, 选择适合分支的可能性提高, 进而提高了自适应分支启发式的准确性.

综上所述, 本文在自主分支辅助决策框架基础上, 提出了一种新的AUTOdom/ddeg算法.为验证AUTOdom/ddeg求解效率的优势, 在标准测试库Benchmarks中的rlfapGraphs,rlfapModGraphs,QWH-20和QCPp-20等多类问题类上进行实验.实验结果表明, AUTOdom/ddeg较借助wdeg辅助决策的自主分支辅助决策算法有绝对优势, 效率提升幅度较大.

[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]季晓慧, 黄拙, 张健.约束求解与优化技术的结合 [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—), 女, 汉族, 博士, 讲师, 从事约束求解与约束优化的研究, E-mail： jlsdwhy_0820@sina.cn.通信作者： 董延华(1971—), 男, 汉族, 博士, 教授, 从事信息处理的研究, E-mail: computerdyp@jlnu.edu.cn.

国家自然科学基金(批准号: 61373052; 61100090; 61170314; 41172294)、吉林省自然科学基金(批准号: 201115220)、吉林省教育厅“十二五”科学技术研究项目(批准号: [2011]第415号; [2014]第490号)、吉林省科技发展计划项目(批准号: 20140101206JC)、吉林省计算中心公共计算平台资助项目(批准号: 20140101206JC )、吉林师范大学博士启动基金(批准号: 2013018)、吉林师范大学硕士启动基金(批准号: 2009035)和四平市科技发展计划项目(批准号: 2012042; 2013058).

TP31

A

1671-5489(2014)06-1289-04

10.13413/j.cnki.jdxblxb.2014.06.34

韩 啸)