| 【中文题名】 | 遗传算法效率研究 |
| 【英文题名】 | |
| 【学科专业】 | 计算机组织与结构 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-12-29 |
| 【中关键词】 | 进化算法,遗传算法,局部搜索算法,（火商）,GA隐含并行性,模式 |
| 【英关键词】 | Evolutionary Algorithms,Genetic Algorithms（GA）,Local Search,Entropy,Implicit Parallelism,Schema, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 遗传算法(GA)是基于自然选择的一种搜索、优化策略，被广泛应用于各种领域，如搜索、优化、以及机器学习等。它适用于求解著名的TSP问题，调度问题，优化Steiner树，以及建立神经网络的初始节点等。在实际应用中，它已被成功地运用于VLSI电路设计中的门阵列分布设计，标准元放置，以及信号格式图压缩，从更广泛意义上说，它可应用到计算机、工程、经济、政治、心理学、语言学、免疫学、生物学、以及数学等各种领域。它从本质上讲是一种随机策略，由于其通用，简单且有效，以及其潜在并行性，使之越来越引人注目，目前已形成了一个研究GA的高潮。
本文介绍和分析了遗传算法的基本特性及其历史和现状。本文着重围绕如何提高遗传算法性能方面作了大量讨论及研究，并从几个层次入手进行研究。首先，从改进遗传算法本身入手，分析了加入带启发性信息操作的作用及其必要性，并结合3-SAT问题，提出Ncrossover与Nmutation操作，结合TSP问题提出三种适用于有序排列问题的三种新型操作，最后提出一种通用化，带有普遍适用性的平行于杂交和突变的两个新操作VOTE与NVOTE，并结合实例证明其有效性；在总体层次上讨论了将GA与其它局部搜索... |
| 【论文题纲】 |
|
致谢 |
3-4 |
|
摘要 |
4-5 |
|
ABSTRACT |
5-11 |
|
第一章 引言 |
11-19 |
|
§1.1 进化算法的研究背景 |
11-12 |
|
§1.2 进化算法的研究现状 |
12-13 |
|
§1.3 遗传算法(GA)研究现状及未来发展 |
13-17 |
|
§1.4 本文组织与贡献 |
17-19 |
|
第二章 遗传算法的遗传操作研究 |
19-48 |
|
§2.1 遗传算法的遗传操作分析 |
19-28 |
|
§2.2 增加与问题领域有关的约束操作 |
28-44 |
|
§2.2.1 对于求解可满足性问题的两种带启发信息新操作 |
28-32 |
|
§2.2.1.1 3-SAT问题表达 |
29 |
|
§2.2.1.2 加入Ncrossover和Nmutation操作 |
29-32 |
|
§2.2.1.3 Ncrossover与Nmutation的进一步改进 |
32 |
|
§2.2.2 对于求解有序排列问题的三种新型打开操作 |
32-44 |
|
§2.2.2.1 新的带启发信息操作介绍 |
33-35 |
|
§2.2.2.2 实验与性能比较分析 |
35-44 |
|
§2.3 新型通用类遗传操作VOTE与NVOTE |
44-48 |
|
§2.3.1 VOTE与NVOTE介绍 |
44 |
|
§2.3.2 VOTE与NVOTE进一步说明 |
44-45 |
|
§2.3.3 实验与性能比较分析 |
45-48 |
|
第三章 混合遗传算法(HGA) |
48-75 |
|
§3.1 几种局部搜索策略简介 |
48-54 |
|
§3.2 求解可满足性问题中的个体进化策略与遗传算法的结合 |
54-59 |
|
§3.2.1 SAT中的个体进化策略 |
54-55 |
|
§3.2.2 SAT中个体进化策略与遗传算法的结合 |
55-56 |
|
§3.2.3 实验分析与性能比较 |
56-59 |
|
§3.3 优化问题中遗传算法与个体进化策略的结合 |
59-71 |
|
§3.3.1 TSP中用到的个体进化策略 |
59-60 |
|
§3.3.1.1 模拟退火(SA) |
59-60 |
|
§3.3.1.2 禁忌算法(TABU) |
60 |
|
§3.3.1.3 局部搜索存在的问题 |
60 |
|
§3.3.2 新的控制个体进化的策略 |
60-61 |
|
§3.3.3 实验及性能分析 |
61-71 |
|
§3.4 何时遗传算法超过爬山法性能? |
71-75 |
|
第四章 遗传算法的并行化 |
75-85 |
|
§4.1 遗传算法的隐含并行性 |
75-77 |
|
§4.2 遗传算法并行实现策略 |
77-83 |
|
§4.3 遗传算法的并行实现 |
83-85 |
|
第五章 结束语 |
85-86 |
|
附录 测试问题例 |
86-92 |
|
参考文献 |
92-101 |
|
| 【DOI】 | LunWen.ID:2.2008.388281 |
