| 【中文题名】 | 演化计算在组合优化与数据挖掘中的应用 |
| 【英文题名】 | The Application of Evolutionary Computation in Combination Optimization & Data Mining |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-11-2 |
| 【中关键词】 | 演化计算,组合优化,数据挖掘,TSP,SAT,GEP |
| 【英关键词】 | Evolutionary computation,Combination optimization,Data mining,TSP,SAT,GEP,DCA, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
演化计算是计算机模拟大自然的演化过程，特别是生物的进化过程，来求解复杂问题的一类计算模型。由于演化计算具有自组织、自学习、自适应的智能特征和简单、通用、鲁棒性强、适于并行处理等优点，因此在组合优化、数据挖掘、工程优化等领域得到了广泛的应用。
基于近年来逐渐丰富和完善的演化计算理论，本文对组和学中的两类经典组合优化问题TSP问题和SAT问题的求解进行了一定的探索，设计出性能更好的新算法用于求解这两类NP难问题。此外，本文还分别探讨了演化计算在数据挖掘领域用来搜索分类规则和在卫星通信领域用来解决信道分配与优化问题，通过提出一些新思想，新方法，使用演化算法有效地解决了这两个问题，从而展示了演化计算强大的搜索与优化能力。
关于TSP问题，本文设计了新的演化算子，并通过增加一些控制策略，提出一种改进的郭涛算法(IGT)，加速了郭涛算法的收敛速度。继而基于IGT算法提出一种分布式演化算法，能对大规模TSP问题进行有效求解，此外，还提出了演化算法的一种新的并行机制，并进行了有效性分析。数值实验表明，IGT算法能有效求解中小规模的TSP问题，分布式IGT算法采用一定数量的并行进程以后能对大规模TSP... |
| 【论文题纲】 |
|
摘要 |
6-7 |
|
ABSTRACT |
7-12 |
|
第一章 绪论 |
12-15 |
|
1.1 引言 |
12 |
|
1.2 组合优化与数据挖掘概述 |
12-13 |
|
1.2.1 组合优化问题概述 |
12-13 |
|
1.2.2 数据挖掘概述 |
13 |
|
1.3 演化计算在组合优化及数据挖掘中的应用 |
13-14 |
|
1.4 本文的主要工作与内容安排 |
14-15 |
|
第二章 演化计算基本理论 |
15-21 |
|
2.1 演化计算概述 |
15-16 |
|
2.1.1 演化计算基本原理 |
15 |
|
2.1.2 演化计算的主要分支 |
15-16 |
|
2.1.3 演化计算的主要特点 |
16 |
|
2.2 演化算法的设计 |
16-19 |
|
2.2.1 演化算法的基本结构 |
17 |
|
2.2.2 设计演化算法的基本步骤 |
17-19 |
|
2.3 演化计算的基本定理 |
19-21 |
|
2.3.1 模式定理 |
19-20 |
|
2.3.2 内含并行性定理 |
20-21 |
|
第三章 基于演化算法求解TSP问题 |
21-32 |
|
3.1 TSP问题概述 |
21-22 |
|
3.1.1 研究现状及本章的研究思路 |
21-22 |
|
3.1.2 TSP问题的数学描述 |
22 |
|
3.2 求解TSP问题的改进的演化算法 |
22-25 |
|
3.2.1 TSP问题中演化算法的相关概念 |
22 |
|
3.2.2 求解TSP问题的郭涛算法(GT) |
22-23 |
|
3.2.3 对GT算法的改进及改进的GT算法(IGT) |
23-25 |
|
3.3 基于分布式演化算法求解大规模TSP问题 |
25-29 |
|
3.3.1 基于IGT的分布式演化算法 |
25-27 |
|
3.3.2 一种新的分布式演化算法并行机制探讨 |
27-29 |
|
3.4 实验 |
29-31 |
|
3.4.1 IGT算法实验 |
29-30 |
|
3.4.2 分布式IGT算法实验 |
30-31 |
|
3.5 本章小结 |
31-32 |
|
第四章 基于演化算法求解SAT问题 |
32-41 |
|
4.1 SAT问题概述 |
32-33 |
|
4.1.1 研究现状及本章的研究思路 |
32-33 |
|
4.1.2 SAT问题的基本要素及其定义 |
33 |
|
4.2 用演化算法求解SAT问题 |
33-35 |
|
4.2.1 SAT问题中演化算法的相关概念 |
33-34 |
|
4.2.2 求解SAT问题的演化算法 |
34-35 |
|
4.3 求解SAT问题的改进的演化算法 |
35-38 |
|
4.3.1 拟人策略 |
35-36 |
|
4.3.2 对演化算法所作的其他改进 |
36-37 |
|
4.3.3 改进的演化算法描述 |
37-38 |
|
4.4 实验 |
38-40 |
|
4.5 本章小结 |
40-41 |
|
第五章 基于演化算法挖掘分类规则 |
41-49 |
|
5.1 数据挖掘中的分类问题概述 |
41-42 |
|
5.1.1 分类问题描述 |
41 |
|
5.1.2 研究现状及本章的研究思路 |
41-42 |
|
5.2 基因表达式程序设计概述 |
42-44 |
|
5.2.1 个体的表示方法 |
42-43 |
|
5.2.2 遗传算子的设计 |
43-44 |
|
5.3 基于基因表达式程序设计的分类规则挖掘算法 |
44-47 |
|
5.3.1 算法分类原理 |
44 |
|
5.3.2 算法的设计 |
44-46 |
|
5.3.3 算法的改进与优化 |
46 |
|
5.3.4 算法描述 |
46-47 |
|
5.4 实验 |
47-48 |
|
5.5 本章小结 |
48-49 |
|
第六章 用演化算法求解动态信道分配问题 |
49-64 |
|
6.1 动态信道分配问题(DCA)概述 |
49-50 |
|
6.1.1 背景 |
49 |
|
6.1.2 研究现状 |
49-50 |
|
6.2 动态信道分配问题的提出及其分析 |
50-54 |
|
6.2.1 问题的提出 |
50-51 |
|
6.2.2 问题的分析与建模 |
51-54 |
|
6.3 动态信道分配问题的求解 |
54-59 |
|
6.3.1 求解DCA问题的演化算法 |
55-57 |
|
6.3.2 求解DCA问题的确定算法 |
57-58 |
|
6.3.3 求解DCA问题的混合算法 |
58-59 |
|
6.4 实验 |
59-63 |
|
6.4.1 关于测试样本及实验平台的说明 |
59-60 |
|
6.4.2 演化算法实验结果 |
60-61 |
|
6.4.3 确定算法实验结果 |
61-62 |
|
6.4.4 混合算法实验结果 |
62-63 |
|
6.5 本章小结 |
63-64 |
|
第七章 结论与展望 |
64-66 |
|
7.1 本文的主要研究成果与创新 |
64 |
|
7.2 进一步的工作与展望 |
64-66 |
|
致谢 |
66-67 |
|
参考文献 |
67-69 |
|
| 【DOI】 | LunWen.ID:2.2008.389153 |
