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

doi:10.3778/j.issn.1002-8331.1902-0195

计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (5): 57-64.DOI: 10.3778/j.issn.1002-8331.1902-0195

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

肖成龙，聂紫阳，王珊珊

辽宁工程技术大学软件学院，辽宁葫芦岛 125105

出版日期:2020-03-01 发布日期:2020-03-06

Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics

XIAO Chenglong, NIE Ziyang, WANG Shanshan

College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China

Online:2020-03-01 Published:2020-03-06

摘要/Abstract

摘要：

变量排序启发式是约束规划求解约束满足问题中的一项关键技术，对求解效率有着重要影响。为进一步提高基于关联的变量排序启发式方法CRBS对问题求解的效率和能力，提出了一种基于ParetoHeu和实例化失败统计的关联启发式PICRBS。PICRBS采用源于帕累托最优的启发式组合方式ParetoHeu，将CRBS与经典的通用启发式dom/wdeg进行结合，同时加入基于实例化失败次数的权值统计方法，为问题求解选择最有可能导致搜索发生回溯的变量。实验结果显示，针对多个问题实例，该方法在问题求解效率上高于CRBS和主流变量排序启发式。

关键词: 约束规划, 变量排序启发式, 帕累托最优, 关联启发式, 约束满足问题

Abstract:

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.

Key words: constraint programming, variable ordering heuristics, Pareto optimality, correlation heuristics, constraint satisfaction problem

肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.

XIAO Chenglong, NIE Ziyang, WANG Shanshan. Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics[J]. Computer Engineering and Applications, 2020, 56(5): 57-64.

[1]	张波，徐黎明，黄志伟，要小鹏. 梯度策略的多目标GANs帕累托最优解算法[J]. 计算机工程与应用, 2021, 57(9): 89-95.
[2]	杨晓华，郭健全. 新零售下生鲜产品闭环物流网络模糊规划[J]. 计算机工程与应用, 2019, 55(2): 198-205.
[3]	李建勋，王婉琳，张永进，佟瑞. 多边匹配决策模型及其帕累托有效解[J]. 计算机工程与应用, 2017, 53(19): 157-163.
[4]	李锐，孙福明. 正态分布处理时间下的4PL多到多网络设计[J]. 计算机工程与应用, 2017, 53(1): 239-243.
[5]	崔文正. RCC8的一致分割及其算法[J]. 计算机工程与应用, 2015, 51(1): 143-150.
[6]	沈静，梅丹. 可满足实例的归结复杂度[J]. 计算机工程与应用, 2014, 50(22): 69-72.
[7]	边根庆，张文敬，邵必林，龚培娇. 基于帕累托最优的云资源调度研究[J]. 计算机工程与应用, 2014, 50(19): 70-73.
[8]	李成严1，2，林英丽2，赵绍航2. 供应链库存的模糊机会约束规划模型[J]. 计算机工程与应用, 2014, 50(17): 241-244.
[9]	朱臻1，高永明2，王斌2. 灵活准则地面测控资源约束满足模型研究[J]. 计算机工程与应用, 2014, 50(10): 260-265.
[10]	袁际军1，黄敏镁2. 基于UML与CCSP的产品配置方法[J]. 计算机工程与应用, 2013, 49(14): 1-9.
[11]	张旭君，吕志民. 基于约束规划的一类排序问题通用求解方法[J]. 计算机工程与应用, 2012, 48(26): 219-224.
[12]	肖宁. 求解随机机会约束规划的混合智能算法[J]. 计算机工程与应用, 2010, 46(22): 43-46.
[13]	付宏杰^1，2，3，欧阳丹彤^1，2，孙吉贵^1，2. 一种求解二元约束满足问题自适应粒子群算法[J]. 计算机工程与应用, 2009, 45(29): 10-13.
[14]	万静，何月娇，易军凯. 面向任务的软件过程控制模型[J]. 计算机工程与应用, 2009, 45(22): 56-58.
[15]	谢小良^1,2,符卓¹. 模糊机会约束规划下的物流配送路径优化[J]. 计算机工程与应用, 2009, 45(18): 215-218.

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

Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics