结余分配策略蚁群算法

论文摘要

Ant System （AS）算法和Max-Min Ant System （MMAS）算法是蚁群算法的两种算法模型,它们都包含信息量更新准则.在更新信息量时,AS算法通常使用Ant-Cycle模型对信息量进行更新,而MMAS算法则用限制最大最小信息量的方式对信息量进行更新.两种算法在实际中有广泛的应用.结合AS算法和MMAS算法更新方式,并考虑到Ant-Cycle模型采取的是“平均”原则更新信息量,即对同一条路径上的各弧段（无论弧段优劣）一律补充等量的信息量；MMAS算法采取的是“一刀切”标准更新信息量,即对信息量小于τmin或大于τmax的弧段,一律将其信息量强制取为τmin或τmax,两者在更新信息量时都没有全面准确地反映弧段的优劣性这一关键信息,本文提出基于弧段优劣性的按比例分配全局更新方式,以及基于此的结余分配策略,给出了结余分配策略蚁群算法.新算法在全局更新过程中,一改“平均”原则为“比例”原则,二改“一刀切”标准为“结余分配”策略,使得“优弧”能减少信息量,“劣弧”能补充信息量,且能充分体现弧段的优劣性.证明了新算法依概率收敛,从理论上保证了新算法的可行性.实验仿真结果很好,与“蚁群算法实验室”所得结果以及目前公布的最好结果比较,优于前者且很接近于后者,说明新算法有实效.

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 蚁群算法产生的背景
• 1.2 蚁群算法的发展历程及其在我国的发展状况
• 1.3 蚁群算法的应用
• 1.4 本文主要工作
• 第2章 蚁群算法
• 2.1 基本蚁群算法
• 2.1.1 蚁群行为描述
• 2.1.2 原理
• 2.1.3 基本算法
• 2.2 蚁群算法的三个算法模型
• 2.2.1 Ant System（AS）
• 2.2.2 Max-Min Ant System（MMAS）
• 2.2.3 Ant Colony System（ACS）
• 第3章 结余分配策略蚁群算法
• 3.1 全局更新
• 3.2 算法
• 3.3 收敛性
• 第4章 仿真
• 4.1 仿真实验
• 4.2 结果分析
• 第5章 总结
• 参考文献
• 致谢
• 附录