蚁群算法的研究及在网络路由优化上的应用

蚁群算法是一种新型的用于求解组合优化或函数优化问题的元启发式算法，其基本思想是借用生物界的蚂蚁群体觅食机理，将每个蚂蚁看作一个智能体，作为智能群体的蚁群，其觅食过程显现出高度的并行性、正反馈性和鲁棒性，以此为基础的蚁群算法也具有这样一些特点。因此，蚁群算法的研究无论从理论上还是实用上，都具有较高的价值。 本文首先分析了蚁群算法的原理与模型，介绍了算法的特点和研究现状，通过实验分析了算法中几个关键参数的选择。针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优等问题，将用于求解组合优化问题的基本蚁群算法进行了改进。首先，在概率选择上采用了确定性与随机性相结合的选择原则；其次，由于基本蚁群算法初期时各条路径上的信息素数量相同，导致算法的初期求解速度缓慢，因此提出了分区搜索的思想，使各条路径上的信息素在初期有所差别，加速算法的收敛；第三，结合局部与全局信息素调整策略对路径上的信息素进行动态更新；第四，对与信息素相关的一些参数进行了自适应改变；最后，引入遗传算法中的变异思想，以扩大解的搜索空间。针对蚁群算法在求解连续优化问题上相对较弱的特点，提出了基于网格划分的蚁群算法，将传统的用于求解离散空间优化问题的蚁群算法进行了扩展。在应用研究上，分析了网络路由优化问题，研究了基于蚁群算法的IP网络QoS单播路由；讨论了基于蚁群算法的一些其它应用。 通过算例对所提出的改进的蚁群算法进行了仿真验证，实验结果表明，本文提出的改进算法是有效和可行的；在连续函数优化上和基于蚁群算法的网络路由优化等应用上也进行了实验仿真。本课题旨在为推进蚁群算法的理论研究和应用研究起到一定的作用。