基于蚁群算法的并行性能分析及优化方法研究

摘要

蚁群算法(Ant Colony Algorithm，ACA)最早被成功用于解决旅行商问题(Traveling Salesman Problem，TSP)，后来因为鲁棒性强、易于与其他方法结合、天然并行性的特点，被广泛应用于解决作业调度问题、航迹规划问题、车辆路径问题等，同时也在机器人领域、数据挖掘与分类等其他实用领域取得了一定的成果。蚁群算法中每次迭代循环结束后，都需要对路径中的信息素浓度进行更新，但是基本蚁群算法执行完更新过程后会导致其易陷入局部最优解进入停滞状态，同时伴随着收敛速度慢等问题，如何优化解决存在的问题，并提高算法在数据规模不断增大时的执行速度和可扩展性，成为本领域的热点问题。
　　针对上述基本蚁群算法易陷入局部最优解和收敛速度慢的问题，在现有研究的基础上，本文采用强化信息素更新机制，通过对其解集信息矩阵进行处理，判断算法是否接近停滞状态;若算法接近停滞状态，再采用新型信息素平滑机制处理信息矩阵，减少或消除算法停滞，提出了一种基于信息素优化机制的算法——蚁群优化提升算法(Ant Colony Optimization Improvement，简称ACOI)。该算法使得基本蚁群算法继续沿着求解全局最优解的目标执行搜索过程。对ACOI算法进行可并行化分析，结合目前常用的并行性框架，针对串行ACOI算法在单机上执行时间长的问题，提出了基于OpenMP的ACOI算法并行化方法，缩短了算法执行时间;针对ACOI算法数据规模增大时在高性能集群上的扩展性问题，利用MPI节点间可并行性的特点，提出了基于MPI的ACOI算法并行化方法，有效解决了扩展性问题;针对纯MPI并行方法在集群上出现的通信代价过高、利用率过低的问题，在OpenMP+MPI混合模型的基础上提出了基于混合编程模型的ACOI算法并行化方法。实验证明，改进后的ACOI算法有效减少了其陷入局部最优解导致算法停滞的概率，同时加快了算法的收敛速度、稳定性增强;基于ACOI算法的并行化方法能够更加充分地利用高性能集群的现有资源，减少了算法的执行时间。

目录

声明

摘要

第1章绪论

1．1研究背景及意义

1．2国内外研究现状

1．2．1蚁群算法研究现状

1．2．2并行计算研究现状

1．2．3蚁群算法并行化研究现状

1．3论文主要研究内容

1．4论文组织结构

第2章相关工作与理论基础

2．1蚁群算法介绍

2．1．1蚁群算法思想起源

2．1．2蚁群算法基本原理

2．1．3蚁群算法数学模型及分析

2．1．4蚁群算法特征

2．2并行编程环境介绍

2．2．1 OpenMP介绍

2．2．2 MPI介绍

2．2．3混合并行编程模型介绍

2．3本章小结

第3章面向TSP问题的ACOI算法

3．1 TSP问题概述

3．2基于信息素优化机制白,0ACOI算法

3．2．1信息素扩散及挥发机制

3．2．2强化信息素更新机制

3．2．3新型信息素平滑机制

3．2．4应用ACOI算法解决TSP问题

3．3本章小结

第4章基于ACOI算法的并行化方法

4．1 ACOI算法在曙光高性能集群环境下可并行性分析

4．1．1曙光高性能集群介绍

4．1．2 ACOI算法可并行性分析

4．2基于OpeMP的ACOI算法并行方法

4．3基于MPI的ACOI算法并行方法

4．4基于混合编程模型的ACOI算法并行化方法

4．5本章小结

第5章实验结果及其分析

5．1实验环境简介

5．2算法性能评价标准

5．3基于信息素优化机制的ACOI算法实验分析

5．4．1 OpenMP的ACOI算法并行方法实验分析

5．4．2基于MPI的ACOI算法并行化方法实验分析

5．4．3基于混合编程模型的ACOI算法并行化方法实验分析

5．5本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢