期刊文献+

基于ParetoHeu和实例化失败统计的关联启发式方法

Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics
下载PDF
导出
摘要 变量排序启发式是约束规划求解约束满足问题中的一项关键技术,对求解效率有着重要影响。为进一步提高基于关联的变量排序启发式方法CRBS对问题求解的效率和能力,提出了一种基于ParetoHeu和实例化失败统计的关联启发式PICRBS。PICRBS采用源于帕累托最优的启发式组合方式ParetoHeu,将CRBS与经典的通用启发式dom/wdeg进行结合,同时加入基于实例化失败次数的权值统计方法,为问题求解选择最有可能导致搜索发生回溯的变量。实验结果显示,针对多个问题实例,该方法在问题求解效率上高于CRBS和主流变量排序启发式。 Variable ordering heuristic is a key technique of constraint programming to solve constraint satisfaction problem,which has an important influence on solving efficiency.In order to further improve the efficiency and ability of CRBS to solve the problem,a correlation heuristic based on ParetoHeu and the instantiation failure statistics,PICRBS,is proposed.PICRBS adopts ParetoHeu,the Pareto optimal heuristic combination method,combines CRBS with the classic general heuristic dom/wdeg,and uses the weight statistics method based on the number of instantiation failures to select the variables most likely to cause search backtracking for the solution of the problem.Experimental results show that the proposed method is more efficient than CRBS and popular variable ordering heuristic in solving multiple problems.
作者 肖成龙 聂紫阳 王珊珊 XIAO Chenglong;NIE Ziyang;WANG Shanshan(College of Software,Liaoning Technical University,Huludao,Liaoning 125105,China)
出处 《计算机工程与应用》 CSCD 北大核心 2020年第5期57-64,共8页 Computer Engineering and Applications
基金 国家自然科学基金(No.61404069) 辽宁省教育厅一般科研项目(No.LJYL048) 辽宁省教育厅青年基金(No.LJ2017QL033)
关键词 约束规划 变量排序启发式 帕累托最优 关联启发式 约束满足问题 constraint programming variable ordering heuristics Pareto optimality correlation heuristics constraint satisfaction problem
  • 相关文献

参考文献1

二级参考文献17

  • 1Freuder E C, Maekworth A K. Constraint satisfaction: An Emerging Paradigm [G] //Rossi F, van Beck P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam: Elsevier, 2006:13-27.
  • 2Bessiare C. Constraint propagation [C] //Rossi F, van Beck P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam: Elsevier, 2006:29-84.
  • 3van Beek P. Backtracking search algorithms [G] //Rossi F, van Beck P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam: Elsevier, 2006:85-134.
  • 4Golomb S W, Baumert L D. Backtrack programming [J]. Journal of the ACM, 1965, 12(4): 516-524.
  • 5Bessihre C, Ragin J C. MAC and combined heuristies: Two reasons to forsake FC (and CBJ?) on hard problems [C] // Proc of CP96. Berlin: Springer, 1996:61-75.
  • 6Boussemart F, Hemery F, Lecoutre C, et al. Boosting systematic search by weighting constraints [C] //Proc of ECAI2004. New York: John Wiley ga Sons, 2004: 146-150.
  • 7Frost D, Deehter R. Look ahead value ordering for constraint satisfaction problems [C] //Proc of the 14th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 1995: 572-578.
  • 8Kask K, Dechter R, Gogate V. Counting-based look-ahead schemes for constraint satisfaction [C] //Proc of CP2004. Berlin: Springer, 2004:317-331.
  • 9Lecoutre C, Sais L, Tabary S, et al. Reasoning from last conflict(s) in constraint programming [J]. Artificial Intelligence, 2009, 173(18): 1592-1614.
  • 10Grimes D, Wallace R J. Learning from failure in constraint satisfaction search [C] //Proc of the 2006 AAAI Workshop on Learning for Search. Menlo Park, CA: AAAI, 2006 :24- 31.

共引文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部