| 【中文题名】 | 用遗传算法解决3-SAT问题 |
| 【英文题名】 | |
| 【学科专业】 | 软件工程 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-10-12 |
| 【中关键词】 | SAT问题,3-SAT问题,完备性算法,局部搜索算法,遗传算法,遗传算子 |
| 【英关键词】 | SAT problem,3-SAT problem,complete algorithm,local search algotithm,Genetic Algorithm,genetic operator,crosser operator,mutation operator, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 3-SAT问题是基本的NP—Complere问题之一，可以从很多实际问题抽象出来，很多问题可以表示成约束满足问题，其在逻辑推理、人工智能的专家系统、数据库维护和检索、VLSI设计及检测等领域有广泛的应用，它的广泛的应用背景促使人们对它进行深入细致的研究。
求解SAT问题的经典算法是求解可满足性问题的经典算法是完备性算法和局部搜索算法(Local Search)。由于分枝回溯算法和局部搜索算法各有千秋，为了取长补短，Crawford(1993)、Bu和Bai(1997)等分别提出了将局部搜索算法和分枝回溯算法结合的思路，并得到了良好的结果。
我们主要从快速求解算法的角度来研究3-SAT问题，运用演化计算的思想来解决3-SAT问题，具体使用遗传算法来解决3-SAT问题，其目的主要寻求好的遗传算子来提高算法的效率，尽快尽可能找到解或极优解(使3-SAT的子句尽可能多的为真值)，主要工作如下：
1．对3—SAT问题进行合理的编码设计，用一维数组表示解的二进制编码串，使用二维数组对句子进行编码，m个子句的编码对应m个有6个元素的一维数组。
2．针对具体的数... |
| 【论文题纲】 |
|
摘要 |
4-6 |
|
Abstraet |
6-8 |
|
第一章 前言 |
8-10 |
|
1.1 NP—Complete问题和SAT(Satisfiability)问题 |
8 |
|
1.2 SAT问题的算法现状及背景 |
8-9 |
|
1.3 论文选题的依据及意义 |
9 |
|
1.4 使用的方法和结论 |
9-10 |
|
第二章 SAT问题概述及传统算法简介 |
10-17 |
|
2.1 可满足问题的表示 |
10-11 |
|
2.2 求解SAT问题的传统算法 |
11-17 |
|
2.2.1 完备性算法 |
11-13 |
|
2.2.2 局部搜索算法(Local Search) |
13-17 |
|
第三章 遗传算法的基本思路及相关概念 |
17-20 |
|
3.1 基本思路 |
17 |
|
3.2 相关概念 |
17-18 |
|
3.3 基本算法及流程图 |
18-20 |
|
3.3.1 基本算法 |
18-19 |
|
3.3.2 流程图 |
19-20 |
|
第四章 3-SAT问题的遗传算法设计 |
20-25 |
|
4.1 编码设计 |
20-21 |
|
4.1.1 解的编码 |
20 |
|
4.1.2 句子的编码 |
20-21 |
|
4.1.3 初始种群 |
21 |
|
4.2 适应度函数 |
21 |
|
4.3 遗传算子 |
21-22 |
|
4.3.1 变异算子 |
21 |
|
4.3.2 杂交算子 |
21-22 |
|
4.4 程序主要模块 |
22-25 |
|
4.4.1 主控模块 |
22-23 |
|
4.4.2 评估模块 |
23 |
|
4.4.3 杂交模块 |
23-24 |
|
4.4.4 变异模块 |
24 |
|
4.4.5 输出模块 |
24-25 |
|
第五章 实验数据及结论 |
25-27 |
|
第六章 存在的问题及后续工作 |
27-28 |
|
6.1 存在的问题 |
27 |
|
6.2 后续工作 |
27-28 |
|
致谢 |
28-29 |
|
参考文献 |
29-31 |
|
附录一：硕士期间发表的论文及参加的科研项目 |
31-32 |
|
附录二：源代码 |
32-43 |
|
原创性声明 |
43 |
|
关于学位论文使用授权的声明 |
43 |
|
| 【DOI】 | LunWen.ID:2.2008.387983 |
