论文部分内容阅读
约束规划是人工智能领域的重要分支,它为解决组合优化问题提出一整套从建模到求解的解决方案。回溯搜索算法是求解约束规划的完备方法,它的特点是在不限制时间及空间的前提下一定能给出问题的解或证明它没有解。回溯搜索算法不断选择变量进行实例化,并通过约束传播将实例化传播出去。约束传播通过执行相容性算法过滤变量值。合理的约束传播方法调度过滤算法以达成某种程度的相容性状态,可以有效地帮助搜索算法减小搜索空间。从而达到提高求解效率的目的。当前,主要的串行约束传播方法有面向弧、约束和变量等传播模式。而受制于复杂的同步问题,有关并行约束传播的研究难度较高,研究成果较少。相容性技术经过严谨的推理删除一些不会出现在解中的变量取值。与其它组合优化问题求解技术相比,相容性技术是约束规划方向的一大特色技术。目前,主流相容性技术有:（广义）弧相容（（Generalized）Arc Consistency,（G）AC）,最大限定路径相容（Max-restricted Path Consistency,Max RPC）和单值弧相容（Singleton Arc Consistency,SAC）等;主流高阶相容性技术有成对相容（Pairwise Consistency,PWC）和完全成对相容（full Pairwise Consistency,f PWC）等。不同的相容性的删值能力各有不同。我们用相容性的“强与弱”来区别这种能力。往往相容性越强,计算或达成这种相容性的所需的时间就越长。反之,所需时间就越短。因此,提出高效的相容性及相容性算法一直是该方向的研究热点。此外,问题建模方案的选择、变量实例化顺序启发式,以及对约束网络的划分与编码也是提高求解效率时所需考虑的重要问题。本文从优化约束传播入手,对约束传播的调度机制、相容性概念及算法进行了深入的研究。通过引入新的理论和数据结构改进现有约束传播方案,进而提出新的相容性概念及算法。本文研究旨在提高约束传播及相容性算法的执行效率,从而总体提升约束规划问题的求解效率,主要研究内容如下:1.改进面向变量的约束传播算法。面向弧、面向变量及面向约束的传播方案是三种经典的约束传播方案。减少冗余传播及过滤算法的调用次数是优化约束传播的重要手段,本文改进了常用的时间戳机制并采用两阶段传播的方式优化了面向变量的传播方案,该方案能识别和排除更多的冗余传播,减少过滤算法的调用次数。实验表明:改进算法进一步提高约束传播的算法效率。2.提出两种并行化约束传播的方案——静态提交（static submission）和动态提交（dynamic submission）算法。当前,由于复杂数据结构的同步问题,有关并行约束传播和并行相容性研究较少。本文基于多核心CPU的计算架构,提出了新的并行相容性的概念及算法。在不改变当前计算设备的前提下,利用多核处理器潜在的并行计算能力,并发地进行约束传播。大量实验表明:并行相容性保证了并行约束传播算法的正确性,与串行约束传播相比,并行约束传播提高了原算法的执行效率。3.提出适用于因子分解编码（Factor-decomposition Encoding,FDE）的约束网络的并行传播算子。并行传播算法的实验表明,动态提交约束传播算法在较大规模问题实例上具有更好的表现。而FDE通过向原约束网络添加额外的约束和变量,使原问题变的更易求解。因此,本文尝试在问题规模更大的FDE网络上,采用并行传播算法加速其求解过程。达成这一目标的挑战是如何将现有的串行算法安全地改写成为并行算法。本文采用分而治之的思想,为不同的类型的表约束设计了不同的并行传播算子。最后的实验结果也展示了该算法是求解FDE模型最为高效的算法。4.用位表示方法（即“位集”）优化向前检查相容性（Forward Checking Consistency,FCC）并在此基础上提出一种新的相容性——增强型向前检查相容性（Enhanced Forward Checking Consistency,EFCC）。多年来,有关相容性研究从未停止,平衡相容性的删值能力和执行时间是该类研究的主要目标。本文采用位集改进了现有的向前检查相容性算法,并且在此基础上提出增强型向前检查相容性。实验表明:,与FCC相比,EFCC删值能力更强,与主流的弧相容（AC）相比,其执行效率更高。5.采用位集模型Word Ram优化alldifferent约束的GAC算法——All Diffbit。目前,关于alldifferent约束的GAC算法都是在Régin算法的框架上改进的。相关的改进技术点有:增量匹配、分阶段传播、优先队列、赋值优化、自由顶点传播、SCC分裂计算、早期检测和位表示与位运算。All Diffbit算法整合了以上所有优化技术并进一步改进了部分技术。实验结果表明:与其它相关算法相比,All Diffbit算法优化效果稳定,在大部分的测试实例上表现较好。综上所述,本文对约束传播与相容性进行了理论与算法上的深入研究。具体工作包括改进了现有串行约束传播方案,提出新的并行约束方案,并提出新的相容性与优化相容性算法。这些研究最终提高了约束规划问题的求解效率。