APG算法在TSP优化中的应用

Application of APG Algorithm in TSP Optimization

为解决蚁群算法(ACO)求解TSP收敛速度缓慢、易陷入局部最优的问题,提出一种基于蚁群的融合算法(APG)。首先在ACO的初始种群中引入精英策略,获得精英路径并构建精英可行解空间;其次引入PSO模型,令精英可行解作为PSO的初始种群,加入GA中的进化策略,使粒子与Gbest进行交叉操作,再使交叉操作后的粒子发生变异,得到第二次优化的可行解空间;最后更新ACO信息素,完成一次ACO优化迭代过程。通过APG在TSPLIB中不同实例的验证,结果表明,APG算法较其它路径优化算法能够得到更优路径。

In order to solve the problem that ACO is of slow convergence and easy to fall into the local optimal when solving TSP problem,an ant colony based fusion algorithm （APG） is proposed.First of all,the elite strategy is introduced into the initial population of ACO to obtain the elite path and build the elite feasible solution space; secondly,the PSO model is introduced to make the elitist feasible solution as the initial population of PSO.The evolutionary strategy of GA is added to cross operation between particles and Gbest,and then the variation of particles after cross operation is achieved,and the second feasible solution space is obtained; finally,the ACO pheromone is updated to complete a ACO optimization iteration process.The verification results of different instances of APG in TSPLIB show that the proposed APG algorithm can get a better path than other path optimization algorithms.