蚁群优化算法及其应用研究

论文摘要

蚁群是一种十分常见的群居昆虫群体。尽管其单个个体都很简单，但是整体仍表现出来了高度结构化的组织社会性，能完成很多复杂的、其个体不能完成的任务。 蚁群算法的诞生是从对自然界中真正的蚂蚁群体的觅食行为中观察而得来的。当蚂蚁们在食物源和巢穴间爬行的时候，它们在地面上释放一种称为信息素的物质，同时形成了一条信息素轨迹。蚂蚁可以嗅到路径上的信息素。当它们在选择路径的时候，会按照概率选择信息素浓度大的路径。通过遗留在地面上的信息素轨迹，蚂蚁就可以发现觅食时的归途；同时也可以引导它的同伴去发现食物。实验已经表明，蚂蚁们跟踪信息素路径的行为确实导致了最短路径的发现。换言之就是当食物源和巢穴之间存在多条路径时，一群蚂蚁通过跟踪由个体留下的信息素轨迹从而最终发现了巢穴和食物之间的最短路径。 自从蚁群算法由Maurco Dorigo和他的同事首先提出以来，作为一种多agent的方法，已很好地解决了一些复杂的组合优化问题，如旅行商问题和指派问题。目前已经有很多种基于蚁群算法或其改进算法应用于各种不同的离散优化问题，这些研究已经涵盖了车辆路径规划，顺序订货问题，地图着色问题以及网络中的路由通信问题等等。 国内针对蚁群算法的研究也如火如荼地进行着，其研究大致可分为理论研究和应用研究两种类型：理论研究主要包含两部分，一是针对算法本身进行改进，提出新的算法；二是针对蚁群算法理论本身进行研究，如收敛性的研究等。诸如：针对信息素释放修改进行改进、针对概率选择方式进行改进、与其它方法进行结合。目前算法理论研究开展得仍不是很充分，大部分的工作和算法的收敛性研究相关。应用研究则是将成熟的方法应用于各自不同的特定领域，诸如：电力系统优化、数据挖掘、图像处理等，并在各自的领域的应用取得了很大进展。 本文较为系统地研究了基于时间模型的蚁群算法等及其应用。 一．提出了基于时间模型的蚁群算法。与传统的算法相比，该算法从蚁群寻径的正反馈过程出发，以一个新的角度，更加真实地再现了蚁群的活动过程，忠实于蚁群算法的生物学原理。实验表明该算法解的质量较传统的基本蚁群算法更优。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 蚁群优化算法
• 1.2.1 蚁群算法的诞生
• 1.2.2 蚁群算法和真实蚂蚁之间的异同点
• 1.2.3 几种典型的蚁群算法
• 1.2.3.1 TSP问题的描述
• 1.2.3.2 蚂蚁系统（Ant System,AS）
• 1.2.3.3 天才蚂蚁系统（Elitist Ant System,EAS）
• 1.2.3.4 排序蚂蚁系统（Rank-Based Ant System）
• 1.2.3.5 最小最大蚂蚁系统（MIN-MAX Ant System）
• 1.2.3.6 蚁群系统（Ant Colony System,ACS）
• 1.3 蚁群算法的应用
• 1.3.1 旅行商问题
• 1.3.1.1 问题描述
• 1.3.1.2 解决方法
• 1.3.2 作业调度问题
• 1.3.2.1 问题描述
• 1.3.2.2 解决方法
• 1.3.3 二次分配问题
• 1.3.4 车辆路径问题
• 1.3.4.1 问题描述
• 1.3.4.2 解决方法
• 1.3.5 多选择背包问题
• 1.3.5.1 问题描述
• 1.3.5.2 解决方法
• 1.3.6 网络路由问题
• 1.4 国内的研究现状
• 1.4.1 发展历史
• 1.4.2 研究现状
• 1.4.2.1 理论研究
• 1.4.2.2 应用研究
• 1.5 论文内容的安排
• 第二章 基于时间模型的蚁群算法
• 2.1 蚁群算法产生的基础
• 2.2 基于时间模型的蚁群算法
• 2.2.1 算法流程
• 2.2.2 性质
• 2.2.2.1 算法复杂度分析
• 2.2.2.2 关于收敛性的说明
• 2.2.2.3 关于参数的说明
• 2.2.3 关于收敛性的证明
• 2.2.4 实验数据
• 2.3 小结
• 第三章 时间蚁群算法的改进
• 3.1 天才时间蚁群算法
• 3.1.1 算法流程
• 3.1.2 收敛性证明
• 3.1.3 实验数据
• 3.2 分组时间蚁群算法
• 3.2.1 算法流程
• 3.2.2 实验数据
• 3.3 基于遗传算法的时间蚁群算法
• 3.3.1 遗传算法介绍
• 3.3.2 算法流程
• 3.3.3 实验数据
• 3.4 小结
• 第四章 蚁群算法仿真研究平台
• 4.1 蚁群算法仿真平台
• 4.1.1 平台结构及功能简介
• 4.1.2 平台实现的数据结构
• 4.2 原理性仿真
• 4.2.1 双桥不等支实验
• 4.2.2 双桥等支实验
• 4.3 时间蚁群算法参数的研究
• 4.4 小结
• 第五章 蚁群算法在植物拓扑结构参数获取上的应用
• 5.1 植物学背景知识
• 5.1.1 植物的轴结构
• 5.1.2 其它将用到的植物学概念
• 5.2 双尺度自动机模型原理
• 5.2.1 微状态（Microstate）
• 5.2.2 宏状态（Macrostate）
• 5.2.3 用双尺度自动机模型生成植物拓扑结构
• 5.3 二十三种植物构造模型
• 5.3.1 Holtum构造模型的模拟
• 5.3.2 Corner构造模型的模拟
• 5.3.3 Tomlinson构造模型的模拟
• 5.3.4 Leeuwenberg构造模型的模拟
• 5.4 参数获取
• 5.4.1 拓扑结构库的构建
• 5.4.2 库生成的算法流程
• 5.4.3 拓扑结构参数的获取
• 5.5 小结
• 第六章 总结展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 读博期间发表的论文
• 附录
• 附录一 CHN144城市坐标
• 附录二 CHN150城市坐标
• 附录三 GR666城市坐标
• 致谢