Mistral求解器扩展与应用研究

发布时间：2017-03-26 17:01

  本文关键词：Mistral求解器扩展与应用研究，，由笔耕文化传播整理发布。

【摘要】：约束满足问题(Constraint Satisfaction Problem、CSP)一直是人工智能领域的一个重要研究方向,相关技术被广泛应用到配置、调度及组合问题求解等领域。约束求解是对CSP问题研究的关键,其求解效率一直是国际人工智能领域关注的热点。目前,已经存在一些很成熟的通用约束求解器,如Ilog Solver、Gecode、Choco、Mistral等等。这些求解器在求解CSP问题上应用了大部分成熟的求解技术,因此都有不错的求解效率,同时被研究团体广泛的使用。这些主流的CSP求解器每年都参加Mini Zinc CSP求解器竞赛,并且都排在前几名。但是大部分CSP求解器的搜索机制中都不包含自适应组件,也就是说,对于大部分的CSP求解器我们只能选择一种搜索策略来进行求解,而不能自动根据问题结构选择合适的启发式或者过滤算法。大多数的CSP求解器是由三个主要组件组成:1)建模语言;2)对于指定约束的一系列过滤算法;3)搜索策略。求解器所提供的建模语言是能够对CSP问题进行表示、建模,包括定义问题变量、定义论域、表示约束等等。过滤算法是基于约束网络的理论,主要思想是删去不相容的值。搜索策略是为了找到解来通过一定的引导搜索搜索空间。对于大多数成熟的CSP求解器,已经实现了一些主要的启发式用于约束传播或者回溯搜索。对于Gecode和Choco这样的CSP求解器,已经有用户手册可以学习求解器的结构以便使用,但是同样是表现很好的Mistral求解还没有这样系统的结构分析。本文的主要工作具体如下:(1)我们主要对Mistral求解器的结构进行详细的分析。首先,我们介绍Mistral求解器的背景;然后,我们分析Mistral求解器的主要实现结构;其次,我们介绍Mistral求解器已经实现的变量排序启发式,并介绍其实现机制以及与其相关的几个重要类和函数;再次,我们介绍值排序启发式的实现机制;最后,我们详细的阐述Mistral求解器约束传播的实现机制。(2)我们主要对Mistral求解器的约束传播方法方面进行扩展。首先,我们向Mistral求解器中添加max RPC3、max RPC3rm、lmax RPC3、lmax RPC3rm等过滤技术,并详细说明添加细节;然后,我们添加参数相容性技术p-max RPC和其自适应版本apx-max RPC,之后我们提出一个对二元CSPs求解的参数化改进版本apx-max RPC-COS,测试结果表明,改进后的参数相容性算法对结构性问题求解有很好的求解效率;最后,我们向Mistral中添加基于MAB的自适应约束传播方法。(3)我们介绍对Mistral求解器搜索策略的扩展。首先,我们介绍TLBO算法;其次,我们提出一种对ETLBO的自适应改进算法,测试结果表明改进后的算法很好地提升了ETLBO的求解效率;然后,我们在改进算法的基础上提出一种离散的TLBO算法;最后,我们把该算法应用到max CSPs问题上并与现存的求解max CSPs求解器abscon-109-pfc和abscon-109-epfc进行对比,测试结果表明该算法在求解max CSPs上有很大的潜力和研究价值。
【关键词】：约束满足问题 Mistral TLBO 自适应 约束传播
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-6
• Abstract6-10
• 第1章 绪论10-14
• 1.1 研究背景10-12
• 1.2 本文结构12-14
• 第2章 约束满足问题和相关知识介绍14-24
• 2.1 约束满足问题（CSPs）14-15
• 2.2 回溯搜索算法15-16
• 2.3 约束传播：AC、maxRPC16-20
• 2.3.1 弧相容（Arc Consistency，AC）17-18
• 2.3.2 最大受限路径相容（Max Restricted Path Consistency，maxRPC）18-20
• 2.4 变量排序启发式20-21
• 2.5 值排序启发式21-22
• 2.6 分支策略和重启策略22-24
• 第3章 Mistral求解器结构分析24-46
• 3.1 Mistral求解器背景24
• 3.2 Mistral求解器主要结构24-25
• 3.3 运用Mistral建模25-35
• 3.3.1 Mistral主要数据结构：论域、变量、约束25-32
• 3.3.2 Solver类的详解32-34
• 3.3.3 一个例子：n皇后问题34-35
• 3.4 Mistral求解器变量排序启发式和值排序启发式实现机制35-40
• 3.4.1 变量排序启发式实现机制36-38
• 3.4.2 值排序启发式实现机制38-39
• 3.4.3 通用启发式封装类GenericHeuristic39-40
• 3.5 Mistral约束传播机制40-46
• 3.5.1 回溯搜索实现细节40-43
• 3.5.2 约束传播实现细节43-46
• 第4章 Mistral求解器扩展（一）46-76
• 4.1 添加maxRPC3及其变体46-57
• 4.1.1 maxRPC3及其变体算法介绍46-49
• 4.1.2 向Mistral中添加maxRPC3及其变体49-52
• 4.1.3 测试结果52-57
• 4.2 添加参数相容性技术57-68
• 4.2.1 自适应参数相容性算法57-59
• 4.2.2 修改的自适应参数相容性算法59-63
• 4.2.3 向Mistral中添加自适应参数相容性算法63-65
• 4.2.4 测试结果65-68
• 4.3 添加自适应约束传播方法68-76
• 4.3.1 MAB问题介绍69
• 4.3.2 基于MAB的自适应约束传播算法69-70
• 4.3.3 Mistral求解器中添加自适应约束传播算法70-72
• 4.3.4 测试结果72-76
• 第5章 Mistral求解器扩展（二）76-97
• 5.1 TLBO算法介绍76-79
• 5.1.1 TLBO和ETLBO算法介绍76-78
• 5.1.2 TLBO和ETLBO算法测试分析78-79
• 5.2 TLBO算法改进79-83
• 5.2.1 策略一：自适应精英个数80-82
• 5.2.2 策略二：讨论组策略82-83
• 5.3 TLBO算法求解无约束的连续非线性规划问题83-84
• 5.4 一种离散的自适应精英的TLBO算法84-87
• 5.4.1 边界检查85
• 5.4.2 编码解码技术：forward transformation and backward transformationtechnique85-86
• 5.4.3 D-AETLBO-MAB算法描述86-87
• 5.5 Mistral求解器添加TLBO算法87-89
• 5.6 D-AETLBO-MAB算法求解maxCSPs89-97
• 第6章 总结与展望97-99
• 参考文献99-103
• 作者简介103-104
• 致谢104

【相似文献】

中国期刊全文数据库 前10条

1 刘敏;刘传领;;一种基于网络的分布式计算求解器的研究[J];河南科学;2008年05期

2 王海燕;欧阳丹彤;张永刚;杨明明;;基于C++的小型约束求解器[J];吉林师范大学学报(自然科学版);2013年03期

3 李立,陈平,张长青;一种提高现有有限元求解器速度的方法[J];长安大学学报(自然科学版);2003年01期

4 何伟;孔梦荣;车战斌;;基于Web Services的开放式分布计算求解器的设计与实现[J];郑州轻工业学院学报;2006年04期

5 李婧;刘万伟;;SMT求解器理论组合技术研究[J];计算机工程与科学;2011年10期

6 赵玉昌;SAP5程序的静力求解器[J];电站系统工程;1990年03期

7 ;LMS推出3D仿真解决方案新版本[J];计算机辅助工程;2013年04期

8 李昕;刘伟信;;关于开放逻辑与ATMS的关系研究[J];仪器仪表用户;2007年02期

9 张秀珍，刘椿年;CLP系统中推理机与约束求解器的协调技术[J];软件学报;1996年07期

10 ;革命性CFD产品 iconCFD V3.0隆重登场——CFD真正助力自主研发[J];计算机辅助工程;2013年06期

中国重要会议论文全文数据库 前2条

1 叶康生;袁驷;;旋转梁振动分析的ODE求解器法[A];第五届全国结构工程学术会议论文集（第一卷）[C];1996年

2 ;LMS推出3D仿真解决方案新版本[A];计算机辅助工程及其理论研讨会2013(CAETS2013)论文集[C];2013年

中国重要报纸全文数据库 前2条

1 顾淑霞;不“精益求精”不出手[N];科技日报;2004年

2 顾淑霞;“精品”，用什么铸就？[N];中国教育报;2004年

中国硕士学位论文全文数据库 前10条

1 钟英;基于PETSc的CFD并行JFNK求解器[D];国防科学技术大学;2013年

2 王启配;基于模拟器的多求解器仿真平台关键技术研究[D];吉林大学;2016年

3 崔佳旭;Mistral求解器扩展与应用研究[D];吉林大学;2016年

4 张英男;冲压成型分析求解器新算法研究及工程应用[D];吉林大学;2008年

5 梁曰涛;一阶带函词限定理论求解器的研究与实现[D];中山大学;2014年

6 李婧;SMT求解器技术对比分析及其能力扩展研究[D];国防科学技术大学;2010年

7 岳学友;基于Web服务的分布式计算求解器的研究[D];电子科技大学;2010年

8 孔梦荣;基于Web Service的开放式分布计算求解器的研究[D];郑州大学;2003年

9 霍翔;SMT求解器增强技术的研究[D];北京交通大学;2011年

10 陈德泉;Choco求解器的结构分析及应用研究[D];吉林大学;2015年

  本文关键词：Mistral求解器扩展与应用研究，由笔耕文化传播整理发布。

本文编号：269069