结合自主搜索机制的约束求解方法研究

Nowadays, Constraint Satisfaction Problems have played an important role in the field of Artificial Intelligence. Over the past five years, the Constraint Solving methods entered a rapid development stage, all kinds of different variables/value selection heuristics, Constraint Propagation techniques, Search framework, Branching strategies were constantly emerging,therefore the efficient constraint solving algorithm(or algorithm portfolio) selection for one class of problems becomes a new challenge for Constraint Programming researchers. As one of the new-proposed methods with wide attention, the Autonomous Search mechanism has provided new ideas for solving the above difficult problem. The proposal is based on the early research results on the Constraint Propagation and Constraint Solving methods made by our research group.It plans to investigate the probing and reasoning methods for the structural feathers of CSP such as clique and symmetry, and to establish the parametric solving framework based on backtrack search. The proposal suggests to formulate autonomous selection and control strategies of combining algorithms for a specific class of problems, with the aid of the machine learning methods. Finally it will develop efficient algorithms, with autonomous search mechanism, for problems of specific structures. The results will be further applied in solving larger scale real life problems from fields like Scheduling and Configuration areas, which is useful in evaluating the proposed theory and methods.

当前，约束满足问题在人工智能领域发挥了重要的作用。近五年来，约束求解方法的发展极为迅速，各种不同的变量、值选择启发式、约束传播技术、搜索框架、分支策略不断涌现，选择求解一类问题的高效算法（或算法组合）成为约束程序研究者面对的新抉择。而新近提出并广受重视的自主搜索机制的出现为破解以上难题提供了新思路。本课题申请基于研究组对约束传播和约束求解方法的前期研究，主要研究约束满足问题的团、对称等结构化特征的探查及推理方法，拟确立基于回溯搜索的约束求解算法的参数化框架，并利用机器学习方法建立针对特定问题类的算法组合的自主选择策略和算法调控策略，最终建立面向具体问题结构的结合自主搜索机制的高效的求解方法，并尝试将其应用于调度、配置领域等稍大规模具体问题的求解，探索所提出的理论和方法的实际应用价值。

当前，约束满足问题在人工智能领域发挥了重要的作用。本项目基于研究组对约束传播和约束求解方法的前期研究，主要研究约束满足问题的团、对称等结构化特征的探查及推理方法，拟确立基于回溯搜索的约束求解算法的参数化框架，并利用机器学习方法建立针对特定问题类的算法组合的自主选择策略和算法调控策略，最终建立面向具体问题结构的结合自主搜索机制的高效的求解方法，并尝试将其应用于调度、配置领域等稍大规模具体问题的求解，探索所提出的理论和方法的实际应用价值。具体包括:研究了约束满足问题适应自主搜索的结构特性；研究约束求解中的相容性技术，并提出多种改进的高效求解算法；提出了基于启发式搜索的自适应改进算法，包括蚁群优化、教与学算法、差分进化算法，并将这些自适应算法与经典算法相结合;对Mistral求解器的搜索策略的进行多方面扩展，提高了求解能力;研究了著名的Mistral和Choco约束求解工具，并在约束表示和约束求解方法方面拓展了两个平台，建立了基于二者的约束组合求解框架；将约束组合求解框架应用于求解城市布局和医院人力资源调度问题，取得了较好的效果。