并行遗传算法及其在组合优化问题上的分布式应用

摘要

利用基于网络环境下的集群计算机,并行遗传算法能够提供各种大型计算问题的解决方案.该文系统地综述了各种并行遗传算法的构成原理,介绍了其典型应用,并指出了需进一步研究的课题.最后介绍了作者开发的一种混合分布式并行遗传算法,以及用其求解组合优化问题的实例.该文在第一章中主要介绍了并行计算的内容和意义,还介绍了大规模并行计算解决复杂问题的成功案例.第二章介绍了并行计算的基本理论和定义.遗传算法和并行遗传算法主要在第三章中介绍,并讨论了影响并行遗传算法竹能的各种因素.第四章主要提出了一种混合分布式并行遗传算法,应用于求解货郎担(TSP)问题.

目录

文摘

英文文摘

第一章绪论

1.1研究背景与意义

1.2并行遗传算法

1.2.1并行

1.2.2并行遗传算法

1.3本文的组织

第二章并行计算

2.1并行平台

2.2并行程序

2.2.1开发并行程序的策略

2.2.2并行加速比、粒度和可扩展性

2.2.3并行编程模型

2.2.4并行算法的分类

2.3消息传递并行编程

2.3.1消息传递方式

2.3.2 MPI消息传递接口

2.3.3 PVM并行虚拟机

第三章并行遗传算法

3.1 GA 遗传算法

3.1.1编码

3.1.2群体设定

3.1.3适应值函数

3.1.4遗传操作

3.2 PGA并行遗传算法

3.2.1全局并行

3.2.2粗粒度

3.2.3粗粒度模型的生物学依据

3.2.3细粒度

3.2.4细粒度模型的理论基础

第四章混合并行遗传算法的实现

4.1遗传算法和组合优化

4.1.1基于遗传算法的组合优化方法

4.1.2 TSP货郎担问题

4.2动态种群并行模型的TSP问题实现

4.2.1 DDs动态种群模型

4.2.2 20PT算法

4.2.3 DDs在PVM环境下求解TSP问题的算法描述

4.2.4 DDs理论分析

4.2.5实现结果及分析

4.2.6结论

参考文献

致谢

作者在攻读硕士学位期间发表的学术论文