蚁群算法的改进及应用

蚁群算法是一种通过模拟真实蚂蚁觅食原理发展起来的新颖的仿生型智能优化算法,具有正反馈、并行性和启发性搜索等特点。作为计算智能和群智能的重要分支之一,蚁群算法的研究方兴未艾,备受瞩目。本文对蚁群算法的发展背景、内容、实现方法和性能作了详细介绍,对该算法本身进行了较深入研究,针对蚁群算法本身的缺陷和待求问题的特点,提出了相应的改进方案,并进行了仿真实验。本文的主要研究成果如下: 针对AS算法求解DCMST问题收敛速度较慢和易收敛于局部最优现象,本文提出了一种新的改进算法UDA-ACS。该算法采用ACS算法的基本思想,并引入为不同长度的路径赋予不同的初始信息量、动态的负反馈机制来调节信息素的变化量、动态的适当增大能见度对蚂蚁路径选择的影响力的机制,有效的抑制了收敛于局部最优和收敛速度较慢的现象,提高了算法的搜索质量和速度。仿真实验结果表明改进的算法显现了一定的优越性。 针对解决最大团问题(MCP),本文提出了一种新的改进算法ACO-BVD。该算法在Vertex-AC的基础上,提出了基于顶点度的启发示信息协助信息素共同指导对下一顶点的选择、采用局部信息素更新机制来协助全局信息素更新机制共同完成对顶点信息素的更新、引入伪随机比例规则来调节蚂蚁“探索”更好的解和“利用”有效信息之间的平衡,该算法有效的改进了Vertex-AC算法中仅信息素指导顶点选择的机制及单一的信息素更新方式,提高了算法的运行效率及解的质量。采用MCP的基准测试实例,通过对比实验验证了该算法在性能上的优越性。