基于约束满足问题求解算法的改进算法研究

发布时间：2020-03-18 14:48

【摘要】：约束满足问题在人工智能领域有着广泛的应用。目前有许多求解约束满足问题的方法,本文对常用的求解约束满足问题的维持弧相容算法做了改进,对求解约束满足问题的效率起到至关重要的两个部分--弧相容和启发式分别做了改进,从两个方面整体地提高求解约束满足问题的效率。本文通过分析约束满足问题的粗粒度维持弧相容求解算法在弧相容(arc containing,AC)的执行过程,发现在对弧的修正检查算法中存在冗余的弧放回操作,并对弧的冗余放回给出了完整的证明。启发式是约束满足问题求解的一个重要组成部分,它通过一定的策略来选择并确定变量和值来搜索约束满足问题的解。目前已有许多成熟的变量启发式能够针对特定的问题属性进行搜索路径选择,但是由于针对性极强,一旦被求解问题针对的特性并不明显,则相应的启发式不能发挥选择作用,有时甚至使得问题求解效率下降极大。基于此,考虑设计一种鲁棒性强的启发式,来避免断崖式的求解效率波动。本文对约束满足问题求解的改进主要体现在以下两个方面:(1)在AC3算法的基础上提出了一种改进算法AC_AO通过保证弧的唯一性来避免冗余弧的放回队列的操作。这种通过维持弧的唯一性改进弧相容算法的模式可以形成框架并适用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文将提出的改进算法框架AC_AO应用于AC3、AC2001、AC3rm算法与原算法做实验对比,实验结果表明,应用AC_AO算法框架后的AC系列算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间,AC_AO算法通过减少弧的检查进而减少修正函数的调用次数,从而提高AC的执行效率,缩短弧相容算法的执行时间。将AC_AO算法应用在维持弧相容算法求解的过程中对求解效率提高是非常有意义的。(2)提出了一种基于遗传选择的启发式方法,能够针对问题属性进行自适应地选择合适启发式指导变量选择。本文对该方法进行了详细分析与描述,将之与最新版本的Choco求解器中最常用的默认启发式domOverWdeg启发式、activityBased启发式作对比,并且针对遗传选择的启发式算法,分别做了两组实验,一组弧相容算法选择AC3算法,另一组弧相容算法选择AC_AO算法,分别进行约束满足问题的求解,实验结果表明在约束满足问题的求解上,AC_AO算法优于AC3算法。基于遗传选择的启发式算法的求解效率最高是domOverWdeg启发式的2.35倍,activityBased启发式的2.26倍。在求解效率的鲁棒性上也优于其他启发式算法。
【图文】：

图 2.1 原始 CSP 问题示了一个约束满足问题示例，，此约束满足问题涉及 3命名，其中 =( , )、 =( , ) 、 =( , )，被 、 ，变量 的论域为{0、1、2}，变量 、 、 表示支持，如 中的值 1 与 中的值 0 互为支持。，0）；对于约束 ，支持的元组为（1，0）、（2，1）；对1，0）、（2，1）。了此 CSP 问题的一组解，即变量 取 1 值，变量 取 取 0 值。

图 2.1 原始 CSP 问题示了一个约束满足问题示例，此约束满足问题涉及 3 个 命名，其中 =( , )、 =( , ) 、 =( , )，被约 、 、 ，变量 的论域为{0、1、2}，变量 、 、 的线表示支持，如 中的值 1 与 中的值 0 互为支持。对1，0）；对于约束 ，支持的元组为（1，0）、（2，1）；对（1，0）、（2，1）。了此 CSP 问题的一组解，即变量 取 1 值，变量 取 量 取 0 值。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 陆明;;约束满足问题在题库系统中的应用[J];民营科技;2008年04期

2 王俊洁;王俊鑫;桂林斌;;人工智能中感知问题的求解技术——约束满足法[J];楚雄师范学院学报;2008年03期

3 郭平;侯睿;杨国洲;范丽;;方位关系约束满足问题的推理求解[J];计算机科学;2005年08期

4 李伟,刘光复;一类基于动态约束满足问题的产品配置方法[J];机械科学与技术;2005年04期

5 刘洋,陈英武;动态约束满足及其在资源调度问题中的应用[J];计算机工程与应用;2004年27期

6 郭宝龙,郭雷,戴冠中;约束满足神经网络[J];电子学报;2000年01期

7 孙伟,马绍汉;约束满足问题并行弧相容算法[J];计算机工程与科学;1997年01期

8 柏淑琴;;高校排课问题的约束满足优化模型与算法[J];科技视界;2012年18期

9 张泉乐;袁际军;;非二元约束满足问题的产品配置建模与求解[J];武汉理工大学学报;2010年01期

10 董存祥;王文俊;杨鹏;;基于约束满足问题的应急决策[J];计算机工程;2010年07期

相关会议论文 前3条

1 张宝;方圣恩;;基于改进约束满足问题的结构损伤评估方法[A];第23届全国结构工程学术会议论文集（第Ⅲ册）[C];2014年

2 李海晨;冯玉强;;基于模糊约束满足问题的谈判决策研究[A];第八届中国管理科学学术年会论文集[C];2006年

3 张志强;王万玉;王建平;李凡;袁刚;;多站多星任务调度优化模型研究[A];第二十三届全国空间探测学术交流会论文摘要集[C];2010年

相关博士学位论文 前9条

1 刘涛;约束满足问题：算法和复杂性[D];中国科学院研究生院（计算技术研究所）;1994年

2 王秦辉;约束满足及其分布式求解和应用研究[D];中国科学技术大学;2007年

3 冯欣;约束满足技术的研究及在生产调度中的应用[D];东北大学;2008年

4 李宏博;约束满足问题研究及其在蛋白质结构预测中的应用[D];吉林大学;2015年

5 徐周波;约束满足问题的符号算法及其在装配规划中的应用研究[D];西安电子科技大学;2012年

6 韦沙;基于分布式约束满足算法的无线信道分配研究[D];华中科技大学;2011年

7 沈静;约束满足问题的模型构造和相变现象[D];华中师范大学;2011年

8 付宏杰;求解二元约束满足问题的混合差分进化算法研究[D];吉林大学;2011年

9 袁际军;大规模定制下基于约束的产品配置方法研究[D];湖南大学;2008年

相关硕士学位论文 前10条

1 王宇星;基于多主体建模与量词约束满足的产品质量控制研究[D];西南科技大学;2019年

2 王希彤;基于MBO的约束满足问题求解算法研究[D];吉林大学;2019年

3 杨罡;基于约束满足问题求解算法的改进算法研究[D];吉林大学;2019年

4 王荪馨;基于约束满足技术的作业车间调度问题研究[D];西安理工大学;2007年

5 任雪亮;改进的置信传播算法在求解最大约束满足问题的应用[D];东北师范大学;2015年

6 赵利;基于约束满足问题的配置解释算法研究[D];吉林大学;2008年

7 李碧涛;基于约束满足神经网络的作业车间调度及应用[D];吉林大学;2006年

8 马冬梅;约束满足问题分解算法及其在配置求解中的应用[D];吉林大学;2007年

9 王旭;交互约束满足问题的冲突解释算法研究[D];吉林大学;2016年

10 徐亚男;二元约束满足问题上基于禁止模式删变量的实现及其优化研究[D];吉林大学;2016年

本文编号：2588855