引入梯度下降的蚁群算法求解多约束服务质量路由

摘要

针对目前多数改进蚁群算法求解多约束服务质量路由(QoSR)存在收敛速度慢、易陷入局部最优从而效率不高的问题,提出一种引入梯度下降的蚁群算法(ACAGD).该算法将梯度下降法引入到蚁群的局部搜索中,结合残余信息素,综合决定蚂蚁的下一跳选择策略.蚁群不仅以一定概率按照信息素浓度搜索下一跳,还将以一定概率按照梯度下降法搜索下一跳,从而降低传统蚁群算法容易陷入局部最优的可能性.利用Waxman网络模型随机生成不同路由节点数量的网络拓扑进行仿真实验.实验结果表明,ACAGD相比其他改进蚁群算法,能够在收敛速度不受影响的情况下,取得综合代价相对较低的路由,且算法的稳定性较好.%To solve the problem that many improved ant colony algorithms are not efficient to solve the problem of multiconstrained Quality of Service Routing (QoSR),such as slow convergence and local optimization,an Ant Colony Algorithm with Gradient Descent (ACAGD) was proposed.The gradient descent method was introduced into the local search of ant colony,and combined with residual pheromone,the next-hop selection strategy of ants was synthetically determined.Ant colony not only search for the next hop according to the pheromone concentration with certain probability,but also search for the next hop according to the gradient descent method with certain probability,which reduced the possibility that the traditional ant colony algorithm was easy to fall into the local optimum.The Waxman network model was used to randomly generate the network topology with different number of routing nodes.The experimental results show that compared with other improved ACO algorithms,the ACAGD can obtain the route with relatively low comprehensive cost while the convergence rate is not affected,and the stability of the algorithm is better.