基于自适应约束传播的约束求解方法研究

针对物流、电力、通讯、交通和人力资源管理等领域广泛存在的大规模约束满足问题，建立高效而又具有自适应特性的约束求解方法是人工智能领域中的前沿课题。本课题在对约束传播和约束求解已有多年研究工作基础上，充分考虑问题本身固有特性，采用静态探查和动态探查两种方式，获取单个约束在应用多种不同约束传播方法后发生变量论域值删除以及论域清空等有用信息，提出约束传播级别的启发式策略，进而形成以自适应约束传播为主要特征的一系列约束求解方法。由于我们将建立的求解方法是以适应问题固有特性为基本原则，基于此，尝试把这一系列方法应用于时间表调度等实际应用比较广泛而又公认难解的问题，设计面向具体问题的全局约束，探索求解具有较大规模应用领域问题的高效算法。

针对物流、电力、通讯、交通和人力资源管理等领域广泛存在的大规模约束满足问题，建立高效而又具有自适应特性的约束求解方法是人工智能领域中的前沿课题。.本课题在对约束传播和约束求解已有多年研究工作基础上，充分考虑问题本身固有特性，采用静态探查和动态探查两种方式，获取单个约束在应用多种不同约束传播方法后发生变量论域值删除以及论域清空等有用信息，提出约束传播级别的启发式策略，进而构建了以自适应约束传播为主要特征的一系列约束求解方法。.主要研究成果包括：.1.在现有约束传播算法研究的基础上，提出了基于比特位操作的自适应约束传播算法AC_MaxRPC_Bitwise及ADAPTAC-LmaxRPC，实验结果表明，算法在总体性能上明显优于AC及原自适应约束传播算法；.2.结合look-ahead值启发式，提出一种新的约束求解算法AdaptBranchLVO，实验结果表明，新提出算法在效率上明显优于已有的自适应分支求解算法;.3.提出算法AdaptBranchsurv，实验结果表明，算法AdaptBranchsurv能显著提高约束求解的效率;.4.提出一种更加轻便的、更适合用于搜索的maxRPC算法及其轻量版本，实验结果表明，新提出的maxRPC算法非常具有竞争力；.5.提出了基于启发式搜索的不完备性算法，主要在蚁群优化元启发式约束求解算法的基础上提出了改进，实验结果表明，改进后的算法求解效率得到大幅度提高..在此算法研究基础上，深入分析了约束求解器Choco, Mistral 的结构,并对其进行扩展，进而构造出两个具有较高性能的通用算法测试平台，为下一步把这一系列方法应用于时间表调度等实际应用比较广泛而又公认难解的问题奠定基础，对于探索求解具有较大规模应用领域问题的高效算法具有重要意义。