摘要
蚁群算法作为一种启发式算法,最初是用来解决TSP(traveling salesman problem)问题,基本思想来源于自然界蚂蚁觅食的最短路径原理,目前在快递配送中已被广泛使用。但其前期信息素匮乏导致搜索速度较慢和计算最优路径时迭代次数过多的问题尚未较好地解决。针对这一问题,提出了一种改进蚁群算法。首先,通过借鉴遗传算法启发函数的思想,对蚁群算法信息素初始值引入改进启发函数进行动态更新,针对不同情况进行寻优节点选择,解决前期搜索速度较慢的问题。其次,对信息素更新公式进行改进,引入自适应计算公式,根据每个节点对应的其他节点情况进行信息素更新,使蚁群更有目的的进行路径选择,加快蚁群算法搜索速度并减少迭代次数。最后,在蚁群算法迭代中引入变异和交叉操作,避免陷入局部最优解。通过仿真实验可以看出,与传统蚁群算法相比,改进的蚁群算法具有更好的寻优能力,且在收敛速度和迭代次数计算值中有明显提升。
As a heuristic algorithm,the ant colony algorithm was originally used to solve the TSP(traveling salesman problem).The basic idea is derived from the shortest path principle of ants foraging in nature.It has been widely used in express delivery.However,the lack of pheromone in the early stage leads to slow search speed and too many iterations when calculating the optimal path,which have not been solved.Aiming at this problem,an improved ant colony algorithm is proposed.Firstly,by drawing on the idea of heuristic function of genetic algorithm,the initial value of ant colony algorithm pheromone is introduced into an improved heuristic function for dynamically updating,and the optimal node selection is carried out according to different situations to solve the problem of slow search speed in the early stage.Secondly,the pheromone update formula is improved,an adaptive calculation formula is introduced,and the pheromone is updated according to the situation of other nodes corresponding to each node,so that the ant colony can make more purposeful path selection,speed up the ant colony algorithm search and reduce the number of iterations.Finally,mutation and crossover operations are introduced in the ant colony algorithm iteration to avoid falling into the local optimal solution.Through the simulation experiment,it can be seen that compared with the traditional ant colony algorithm,the improved ant colony algorithm has better optimization,and the convergence speed and the calculated value of the number of iterations are significantly improved.
作者
陆缘缘
高华成
崔衍
LU Yuan-yuan;GAO Hua-cheng;CUI Yan(School of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)
出处
《计算机技术与发展》
2021年第11期15-20,共6页
Computer Technology and Development
基金
江苏省研究生科研与实践创新计划项目(KYCX19_0985)
中国博士后科学基金面上项目(2020M671554)。
关键词
蚁群算法
遗传算法
启发函数
最优解
信息素
ant colony algorithm
genetic algorithm
heuristic function
optimal solution
pheromone
