蚁群算法在网络路由上的应用

论文摘要

蚁群算法(Ant Colony Algorithm,ACA)源于自然界中生物群体的仿生类算法,是一种新型的用于求解组合优化或函数优化问题的元启发式算法。该算法吸收了昆虫王国中蚂蚁的行为特性,其内在的搜索机制在一系列困难的组合优化问题求解中取得了很好的成效。蚁群算法的主要特征是并行性、正反馈性和鲁棒性。蚁群算法不仅在著名的旅行商问题(TSP)和工件排序问题上取得成效,目前已陆续渗透到其它问题领域中,如:图着色问题、大规模集成电路设计、通讯网络中的负载平衡问题、车辆调度问题等等,在许多方面表现出了相当好的性能。本文主要介绍了蚁群算法的原理与模型,介绍了算法的特点和研究现状,并通过实验分析了算法中几个关键参数的选择。针对蚁群算法的主要缺陷,如收敛速度慢和易于陷入局部最优等问题,将用于求解组合优化问题的基本蚁群算法进行了改进。通过算例对所提出的改进的蚁群算法进行了仿真验证,实验结果表明,本文提出的改进算法是有效和可行的;在连续函数优化上和基于蚁群算法的网络路由优化等应用上进行了实验仿真。本课题旨在为推进蚁群算法的理论研究和应用研究起到一定的作用。

论文目录

• 内容提要
• 绪论
• 第1章 多播路由问题
• 1.1 IP 网络路由简介
• 1.2 多点路由
• 1.3 多播路由
• 1.4 QOS 路由
• 第2章 智能计算
• 2.1 智能计算简介
• 2.2 启发式算法
• 2.2.1 遗传算法
• 2.2.2 模拟退火算法
• 2.3 人工神经网络
• 第3章 群智能
• 3.1 蚁群算法
• 3.2 粒子群优化算法
• 第4章 蚁群算法
• 4.1 蚁群优化算法
• 4.2 蚁群算法产生
• 4.3 基本蚁群算法的实现
• 4.4 蚁群算法的分析
• 4.5 蚁群算法的应用
• 4.5.1 网络路由——通讯问题
• 4.5.2 电力系统优化问题
• 4.5.3 机器人路径规划问题
• 第5章 蚁群算法在组合优化问题上的应用
• 5.1 组合最优化问题
• 5.2 NP 问题
• 5.3 具有代表性的组合优化问题
• 5.3.1 0-1 背包问题
• 5.3.2 旅行商问题
• 5.3.3 生产调度——多目标分配问题
• 5.3.4 多回路运输问题
• 第6章 改进的蚁群算法到多播问题的实现
• 6.1 背景
• 6.2 QOS 多点路由模型
• 6.3 改进的蚁群算法
• 6.4 实验及结论
• 6.4.1 参数的设定
• 6.4.2 改进算法与基本算法的比较
• 6.5 小结
• 参考文献
• 摘要
• ABSTRACT
• 致谢