求解TSP的改进信息素二次更新与局部优化蚁群算法

摘要

Concerning the drawbacks of the Ant Colony Optimization (ACO) algorithm such as low convergence rate and being easy to fall into local optimum solutions,an ACO algorithm based on Improved Pheromones Double Updating and Local Optimization (IPDULACO) was proposed.Double updating was performed on the pheromones of subpaths whose path contribution degrees to the current global optimal solution obtained by colony were bigger than the prescribed path contribution threshold.The selected probability of the subpaths which were used to constitute the potential optimal solution was increased and the convergence rate of the proposed algorithm was accelerated.Then,when the ant colony fell into the local optimal solution in the search process,the random insertion method was utilized to change the city sequences of the current local optimal solution in order to enhance the algorithm's ability of jumping out of local optimal solution.The improved algorithm was applied to several classical Traveling Salesman Problem (TSP) instances in the simulation experiments.The experimental results show that,for small-size TSP instances,the IPDULACO can obtain the known optimal solution in less number of iterations.For relatively large-size TSP instances,the IPDULACO can obtain the optimal solution with higher accuracy in less number of iterations.Therefore,the IPDULACO has the stronger ability of searching for the global optimal solution and faster convergence rate,and it can be used for solving TSP effectively.%针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO).该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛.然后,在搜索过程中,当蚁群陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力.将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验,实验结果表明,对于小规模的TSP,IPDULACO可以在较少的迭代次数内获得已知最优解;对于较大规模的TSP,IPDULACO可以在较少的迭代次数内获得更精确的解.因此,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度,可以高效求解TSP.