一种改进的并行蚁群算法及其在QoS组播路由优化问题中的应用

摘要

随着如今网络的快速发展，互联网展现出越来越多的多媒体应用，因此对网络性能的要求越来越高。传统网络的那种“尽力而为”的传输方式已经逐渐无法满足如此高的对数据传输性能的需求。在这种条件下，服务质量(QoS)路由被业界提出并逐渐演化为互联网发展的核心技术之一。而互联网应用非常复杂，存在多种约束，在这样的前提下QoS路由问题成为了一种NP-Complete问题，这很难使用传统方法进行求解。
　　蚁群算法又称作蚂蚁算法，是一种来源于自然生物界的群体智能的仿生优化算法，拥有自组织性、并行性和灵活性等特点。虽然相比其他智能算法出现较晚，但在求解复杂优化问题，特别是离散和多维动态优化问题显示了该算法的优势。
　　本文首先介绍了QoS问题的基本概念，对其建立了数学模型，并给出了本文的求解策略。然后具体讲解了蚁群算法的基本原理和特点、流程、在参数设置方面的研究等。通过对国内外学者对蚁群算法进行改进的想法和操作的总结，提出了本文的全新的改进策略，以求更好地求解此类较为复杂的QoS路由优化问题。主要有以下几个方面:1.对蚁群算法采用了并行的思想，将蚁群分成两组独立子群分别进行寻优。2.对两组蚁群分别采用不同的信息素更新方式，保证在加快收敛速度以及防止陷入局部最优之间取得一个较好的平衡状态。3.使用了精英策略，间隔一段周期将最好蚂蚁的作为精英留下并给予奖励，以达到更好的优化效果。文中给出了改进后并行蚁群算法的算法流程和实现步骤，并首先将其用于TSP问题以验证其有效性，继而用于QoS问题中，通过随机生成Waxman-Salama模型网络拓扑实验并进一步验证了本文所改进的算法在QoS组播路由优化之中的性能和作用。结果表明，提出的算法能够有效的找出最优组播树，相比基本蚁群算法，各项指标达到的效果令人满意。
　　通过本文的相关工作表明，本文所提算法应用于QoS组播路由优化问题是有效的，获得了较好的求解效果。同时本文所提算法也是一个通用的算法，可为其他的工程领域提供借鉴，具有一定的理论意义和应用价值。

目录

声明

摘要

第1章 绪论

1．1 课题的工程背景和研究意义

1．1．1 课题的工程背景和问题的提出

1．1．2 课题的研究意义

1．2 国内外研究现状

1．3 本文研究的主要内容及其组织结构

第2章 QoS组播路由优化问题及其数学模型

2．1 QoS问题的概念描述

2．2 QoS的问题分类

2．2．1 单播路由

2．2．2 组播路由

2．3 QoS路由的数学模型的建立

第3章 蚁群算法

3．1 蚁群算法概述

3．1．1 蚁群觅食的特·陛

3．1．2 人工蚂蚁与真实蚂蚁的异同

3．2 基本蚁群算法

3．2．1 基本蚁群算法的原理

3．2．2 基本蚁群算法的数学模型

3．2．3 基本蚁群算法的具体实现

3．2．4 参数选择对蚁群算法性能的影响

3．3 改进的并行蚁群算法

3．3．1 并行策略

3．3．2 精英蚂蚁策略

3．3．3 并行蚁群算法的实现

3．4 数据试验和分析

第4章 并行蚁群算法在QoS组播路由问题中的应用与分析

4．1 算法应用的说明

4．2 随机网络拓扑结构生成

4．3 实验及其结果分析

4．3．1 小规模问题(25节点)

4．3．2 中等规模问题(50节点)

4．3．3 大规模问题(100节点)

第5章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢