一个蚁群优化算法及其在CVRP问题中的应用研究

论文摘要

该文通过对蚁群优化算法发展现状的分析,着重对取得较大成功的蚁群优化算法MMAS 和基于均匀分布度的自适应蚁群算法进行研究,基于此提出一个新的蚁群优化算法NDLACO,给出了算法设计模型。通过利用适应度地形分析蚁群对解空间的搜索覆盖程度和对局部搜索方法的分析,把最近邻居选择法和3-opt 局部搜索方法融入NDLACO 算法中。通过吸纳基于均匀分布的自适应思想,有效地处理了蚁群算法中存在的蚁群加速收敛和防止算法出现早熟、停滞想象这对矛盾。本文成功地把NDLACO 算法运用于解CVRP 问题。通过对实验数据的分析发现,此算法运用于解CVRP 问题时在不影响所得解质量的前提下,对算法中参数值的设置有一定的容忍度。

论文目录

• 第一章 引言
• 1.1 课题背景
• 1.2 研究内容
• 1.3 课题意义
• 1.4 本文结构
• 第二章 蚁群算法简介及研究现状
• 2.1 组合优化问题的传统解决方案
• 2.2 蚁群算法简介
• 2.3 蚁群算法研究现状
• 2.4 对MMAS 算法的分析
• 2.4.1 信息素的刷新
• 2.4.2 信息素的限制
• 2.4.3 局部搜索策略
• 2.4.4 信息素的刷新机制与MMAS 分类
• 2.5 基于均匀分布的自适应蚁群算法的分析
• 2.5.1 自适应蚁群算法
• 2.5.2 基于分布均匀度的自适应蚁群算法
• 第三章 车辆调度问题（VRP）概述
• 3.1 VRP 问题的提出和发展
• 3.1.1 VRP 问题发展三个阶段
• 3.1.2 VRP 问题一般组合条件
• 3.2 VRP 问题的基本解法
• 3.3 蚁群算法运用于CVRP 问题的研究现状
• 第四章 CVRP 问题的适应度地形分析
• 4.1 元启发和适应度地形分析
• 4.2 蚁群优化算法解CVRP 问题的适应度地形分析
• 4.2.1 P-n101-k4 问题的适应度地形分析
• 4.2.2 P-n76-k4 与P-n76-k5 问题的适应度地形分
• 第五章 K-OPT 局部搜索方法分析
• 5.1 2-OPT局部搜索方法分析
• 5.2 2-H-OPT局部搜索方法分析
• 5.3 3-OPT局部搜索方法分析
• 5.4 运用K-OPT局部搜索方法的实验结果分析
• 5.4.1 初始化信息素阶段使用k-opt 方法的实验分析
• 5.4.2 优化完整解阶段使用k-opt 方法的实验分析
• 5.4.3 k-opt 方法运用于其他CVRP 问题的分析
• 第六章 NDLACO 算法设计与实现
• 6.1 NDLACO 算法提出背景
• 6.2 ACO 算法解CVRP 与TSP 问题研究现状
• 6.3 蚁群算法经典设计模型
• 6.3.1 蚂蚁的节点选择原则
• 6.3.2 信息素局部更新原则
• 6.3.3 信息素全局更新原则
• 6.4 NDLACO 算法设计模型
• 6.4.1 最近邻居选择原则
• 6.4.2 局部启发搜索3-opt 原则
• 6.4.3 基于均匀分布度的选择原则
• 6.4.4 信息素局部更新原则
• 6.4.5 信息素全局更新原则
• 6.5 主要数据结构
• 6.6 算法描述
• 第七章 NDLACO 算法实验分析
• 7.1 参数Α的实验数据分析
• 7.2 参数Β的实验数据分析
• 7.3 参数ρ的实验数据分析
• ANTS的实验数据分析'>7.4 参数N_ANTS的实验数据分析
• 7.5 NDLACO 解CVRP 类问题的试验分析
• 7.5.1 MMAS 与NDLACO 算法解CVRP 的实验比较
• 7.5.2 NDLACO 算法解CVRP 问题实验分析
• 7.6 实验结果综述
• 第八章 结束语
• 8.1 小结
• 8.2 进一步工作
• 附录
• REFERENCES
• 参考文献
• 攻读学位期间公开发表的论文
• 致谢
• 详细摘要