| 【中文题名】 | 并行遗传算法及其在组合优化问题上的分布式应用 |
| 【英文题名】 | Parallel Genetic Algorithm and Its Distributed Application on the Combination Optimum Problem |
| 【学科专业】 | 计算机科学与技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2003-5-9 |
| 【中关键词】 | 并行计算,遗传算法,并行遗传算法,并行虚拟机,2opt,动态种群模型 |
| 【英关键词】 | Parallel Computing, Genetic Algorithm, Parallel Genetic Algorithm, PVM, 2opt, DDs, combination optimum problem , TSP, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
基于网络计算的并行计算技术已成为当前计算机科学研究的主要课题，它受到了研究人员的高度重视。利用现有的计算资源实现可用并行计算系统的研究已经取得了令人瞩目的进展。遗传算法是一种高效智能搜索方法，并行遗传算法是遗传算法研究中的一个重要方向。利用基于网络环境下的集群计算机，并行遗传算法能够提供各种大型计算问题的解决方案。本文系统地综述了各种并行遗传算法的构成原理，介绍了其典型应用，并指出了需进一步研究的课题。最后介绍了作者开发的一种混合分布式并行遗传算法，以及用其求解组合优化问题的实例。
本文在第一章中主要介绍了并行计算的内容和意义，还介绍了大规模并行计算解决复杂问题的成功案例。
第二章介绍了并行计算的基本理论和定义。
遗传算法和并行遗传算法主要在第三章中介绍，并讨论了影响并行遗传算法性能的各种因素。
第四章主要提出了一种混合分布式并行遗传算法，应用于求解货郎担(TSP)问题。这种混合算法主要由动态种群并行模型和20pt算法组成。程序由C编制，运行环境是并行虚拟机(PVM)。在这种混合并行遗传算法中，20pt算法取代变异操作，它逆转TSP个体的基因片段... |
| 【论文题纲】 |
|
中文摘要 |
5-6 |
|
英文摘要 |
6-8 |
|
第一章 绪论 |
8-12 |
|
1．1 研究背景与意义 |
8-10 |
|
1．2 并行遗传算法 |
10-11 |
|
1．2．1 并行 |
10 |
|
1．2．2 并行遗传算法 |
10-11 |
|
1．3 本文的组织 |
11-12 |
|
第二章 并行计算 |
12-33 |
|
2．1 并行平台 |
12-13 |
|
2．2 并行程序 |
13-18 |
|
2．2．1 开发并行程序的策略 |
13-14 |
|
2．2．2 并行加速比、粒度和可扩展性 |
14-16 |
|
2．2．3 并行编程模型 |
16-17 |
|
2．2．4 并行算法的分类 |
17-18 |
|
2．3 消息传递并行编程 |
18-33 |
|
2．3．1 消息传递方式 |
19-21 |
|
2．3．2 MPI消息传递接口 |
21-25 |
|
2．3．3 PVM并行虚拟机 |
25-33 |
|
第三章 并行遗传算法 |
33-49 |
|
3．1 GA遗传算法 |
33-42 |
|
3．1．1 编码 |
33-35 |
|
3．1．2 群体设定 |
35-36 |
|
3．1．3 适应值函数 |
36-37 |
|
3．1．4 遗传操作 |
37-42 |
|
3．2 PGA并行遗传算法 |
42-49 |
|
3．2．1 全局并行 |
42-43 |
|
3．2．2 粗粒度 |
43-45 |
|
3．2．3 粗粒度模型的生物学依据 |
45-46 |
|
3．2．4 细粒度 |
46-47 |
|
3．2．5 细粒度模型的理论基础 |
47-49 |
|
第四章 混合并行遗传算法的实现 |
49-63 |
|
4．1 遗传算法和组合优化 |
49-55 |
|
4．1．1 基于遗传算法的组合优化方法 |
49-51 |
|
4．1．2 TSP货郎担问题 |
51-55 |
|
4．2 动态种群并行模型的TSP问题实现 |
55-63 |
|
4．2．1 DDs动态种群模型 |
55-56 |
|
4．2．2 20PT算法 |
56-57 |
|
4．2．3 DDs在PVM环境下求解TSP问题的算法描述 |
57-59 |
|
4．2．4 DDs理论分析 |
59-60 |
|
4．2．5 实现结果及分析 |
60-61 |
|
4．2．6 结论 |
61-63 |
|
参考文献 |
63-67 |
|
致谢 |
67-68 |
|
作者在攻读硕士学位期间发表的学术论文 |
68 |
|
| 【DOI】 | LunWen.ID:2.2008.386701 |
