文档介绍：分类号:TP39
10710-2009124029
硕士学位论文
Linux 机群环境下并行蚁群优化算法的
设计与实现
张志明
导师姓名职称安毅生副教授
申请学位级别硕士学科专业名称计算机软件与理论
论文提交日期 2012 年 5 月 21 日论文答辩日期 2012 年 6 月 3 日
学位授予单位长安大学
Design and Implementation of Parallel Ant Colony
Optimization based on Linux Cluster
A Dissertation Submitted for the Degree of Master
Candidate:Zhang Zhiming
Supervisor:. An Yisheng
Chang’an University, Xi’an, China
摘要
蚁群优化算法是一种新的模拟进化算法,具有正反馈、元启发式与分布式计算相结
合的特点,其中正反馈有助于算法更快地发现较好解,元启发式特征有助于算法更容易
地发现较好解,分布式计算则是有利于实现蚂蚁种群的并行寻优。此外,近年来随着计
算机技术尤其是高性能微型计算机和高速网络的出现,一种廉价且高性能的并行机群环
境逐渐成为并行计算领域的研究热点,这类计算机可以为用户提供低价高效的高性能计
算环境和快速、灵活、可靠的计算服务。鉴于蚁群优化算法的分布式特性,本文在构建
Linux 机群环境下设计并实现了并行蚁群优化算法,并将该算法应用于旅行商问题。
本文的主要工作和研究成果如下:
(1)在研究分析现有蚁群优化算法和邻域搜索算法的基础上,利用邻域搜索算法对
蚁群优化算法产生的初始解进行二次寻优,既能够发挥蚁群优化算法较强收敛性的特
征,又能够使邻域搜索算法提高初始解的质量,从而指导后续蚂蚁的寻优过程。
(2)通过对现有机群软硬件环境的调研和分析,确定了机群系统的选型,研究并
分析了多种并行编程环境,建立了基于 Linux 的机群系统和基于 MPICH 的并行编程环
境。
(3)在 Linux 机群环境下,按照蚂蚁个体在多个处理器上均匀分布的思想,设计
并实现了并行蚁群优化算法,对蚂蚁系统优化算法和蚁群系统优化算法,以及添加邻域
搜索的蚂蚁系统优化算法和蚁群系统优化算法进行对比测试,并对加速比等性能指标进
行了实例分析。
关键词:蚁群优化算法,邻域搜索,机群,Linux,MPICH
I
Abstract
Ant Colony Optimization(ACO),as a new simulated evolution algorithm, has the
characteristics as bination of positive feedback, meta heuristic and distributed
computing. Positive feedback helps ACO to find better solutions faster, metaheuristic features
contribute to ACO easier to find better solutions, and puting is conducive to
realize the puting of ant colony in order to find the optimization route.
In addition, in recent years, with the development puter technology, especially the
emergence of high-puters and high-works, an inexpensive,
high-performance puter cluster environment gradually es a research topic
in the field of puting. This type puters can provide users with low-cost,
high efficient puting environment