改进蚁群算法求解最短路径问题
改进蚁群算法求解最短路径问题
【摘要】针对蚁群算法在收敛过程中需要多次迭代和容易陷入局部最优解的问题，本文提出一种改进策略的蚁群算法——自主复制蚁群算法（Auto Copy Ant Colony Algorithm，AC-ACO）。通过蚂蚁自主复制和分泌标记信息素实现快速找到最短路径问题最优解。仿真结果显示，AC-ACO算法能降低迭代次数，增强算法的搜索能力。
【关键词】蚁群算法；自主复制；最短路径
1.引言
随着智能交通概念的发展和应用，在城市交通网中查找最短路径问题成为了一个研究热点。最短路径是指在一个权值图中找出两节点之间拥有最小权值的路径。许多学者都对最短路径问题进行了大量的研究，并取得了不小收获，如经典的Dijkstra算法。蚁群算法[1]是近年来提出的一种新型的模拟进化算法，本文将改进蚁群算法用于解决最短路径问题。
2.蚁群算法简介
2.1 基本原理
蚁群算法是通过模拟自然界蚂蚁觅食行为来求解优化组合问题的仿生算法。意大利学者M.Dorigo于1992在博士论文中第一次提出蚁群算法概念。其原理在于：自然界的蚂蚁群在寻觅食物的过程中，会在途经道路上释放信息素，并根据道路已有信息素选择路径。经过一段时间的搜索，道路信息素浓度不断更新和消散而最终收敛于某条最短路径，此过程表现出了蚂蚁群体自组织、自动学习的能力。算法本质是一种正反馈机制[2]，蚂蚁倾向于选择信息素浓度较大的路径作为自己移动方向。因此环境是否变化，蚁群总能挑选合适路径，实现选择最短路径的目的。
2.2 数学模型
设定标记[3]如下：m表示蚁群个体数量；dij表示位置i和j之间的距离；ηij（t）表示启发函数，即由位置i转移到j的启发程度；τij（t）表示t时刻边（i，j）上信息素量，τij（t）=C，C取常数；Δτij表示一组蚂蚁遍历完成后位置i到j间新产生的信息素量；Pijk表示蚂蚁k的转移概率，j是未访问的节点；tablek表示蚂蚁k下一步允许运行的节点集合。
①初始时刻t=0，各条路径信息素浓度相等，蚂蚁k在运动过正中根据各条路径信息素浓度计算转移概率
其中α是信息启发因子，β是期望启发因子，然后蚂蚁k会根据概率P选择