并行蚁群算法及其应用研究

论文摘要

蚁群优化（ACO）算法是一种新型的元启发式算法。蚁群优化算法具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法结合等优点,可以用于解决各种组合优化问题,并已经成功解决了包括旅行商（TSP）问题在内的许多组合优化问题。蚁群优化算法具有天然的并行特性,适合并行计算。本文对并行蚁群优化算法进行了研究,主要工作包括:研究蚁群算法的并行化,研究并行蚁群算法的应用,研究算法参数的最优组合。本文采用MPICH在机群系统上对算法进行仿真研究,并选择了适合机群系统以及蚁群优化算法特点的并行策略。针对大规模火力分配问题（WTA）的特点,提出了一种求解该问题的并行蚁群算法（ACS-WTA-MPI）。仿真实验结果表明,本文提出的算法的求解质量比求解此问题的对应的串行ACS算法好,本文提出的并行算法的加速比和并行效率也比较理想,加速比最高达到3.851（处理机个数=4）,并行效率最高达到0.963。本文对蚁群算法参数的选取进行了研究,目的是确定出参数的最优组合。蚁群算法有一系列的参数,其中主要包括蚂蚁个数、期望启发式因子、局部信息素挥发因子、全局信息素挥发因子等。本文通过一系列仿真实验,对这些参数的不同设置下ACS-WTA-MPI算法的性能进行了对比,确定出针对火力分配问题的算法参数的最优组合。最后,对全文的研究工作进行了总结,并展望了蚁群优化算法进一步还要研究的课题。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 最优化问题
• 1.2.1 定义
• 1.2.2 旅行商问题
• 1.3 本文主要研究内容
• 第2章 蚁群优化算法与并行计算概述
• 2.1 蚁群优化算法概述
• 2.1.1 起源与发展
• 2.1.2 元启发式算法
• 2.1.3 蚂蚁系统
• 2.1.4 蚁群优化算法流程
• 2.1.5 改进的蚁群算法
• 2.1.6 蚁群算法的应用
• 2.2 并行计算概述
• 2.2.1 并行计算机
• 2.2.2 并行算法
• 2.2.3 并行算法评价
• 2.2.4 并行编程的语言
• 2.2.5 MPI
• 第3章 并行蚁群算法
• 3.1 蚁群算法并行化的可行性与必要性
• 3.2 并行蚁群算法基本思想
• 3.3 并行策略
• 3.4 机群系统下并行策略的选择
• 3.4.1 子蚁群间的通信内容
• 3.4.2 子蚁群间的通信周期
• 第4章 基于并行蚁群算法的火力分配优化
• 4.1 火力分配问题的数学模型
• 4.2 分配策略
• 4.3 算法设计
• 4.3.1 算法设计基本思想
• 4.3.2 解的构建
• 4.3.3 序偶选择规则
• 4.3.4 信息素更新规则
• 4.3.5 算法的并行策略
• 4.3.6 算法框架
• 4.4 算法实现中的一些技术问题
• 4.4.1 序偶选择规则的实现
• 4.4.2 大型矩阵的实现
• 4.5 仿真实验
• 4.5.1 软硬件环境
• 4.5.2 算法参数设置
• 4.5.3 测试数据
• 4.5.4 仿真实验结果与分析
• 4.6 算法应用前景
• 第5章 并行蚁群算法参数设置研究
• 5.1 蚂蚁个数对算法的影响
• 5.2 参数q0对算法的影响
• 5.3 参数β对算法的影响
• 5.4 参数ρ对算法的影响
• 5.5 参数γ对算法的影响
• 5.6 本章小结
• 第6章 结论与展望
• 6.1 全文总结
• 6.2 未来展望
• 致谢
• 参考文献
• 攻读学位期间发表的论文