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

发布时间：2018-10-17 21:27

【摘要】：针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛。然后,在搜索过程中,当蚁群陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验,实验结果表明,对于小规模的TSP,IPDULACO可以在较少的迭代次数内获得已知最优解;对于较大规模的TSP,IPDULACO可以在较少的迭代次数内获得更精确的解。因此,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度,可以高效求解TSP。
[Abstract]:Aiming at the shortcomings of ant colony (ACO) algorithm, which is slow in convergence speed and easy to fall into local optimum, an improved pheromone quadratic update local optimization ant colony algorithm (IPDULACO). Is proposed. The algorithm renews the subpath pheromone whose path contribution degree is greater than the given path contribution threshold in the current global optimal solution searched by ant colony in order to improve the probability of subpath selection which constitutes the potential optimal solution. Thus speeding up the convergence of the algorithm. Then, in the search process, when the ant colony falls into the local optimum, the random insertion method is used to adjust the order of the cities in the local optimal solution to enhance the ability of the algorithm to jump out of the local optimal solution. The improved algorithm is applied to some classical (TSP) simulation experiments. The experimental results show that the known optimal solution can be obtained for small scale TSP,IPDULACO in less iterations. For a larger TSP,IPDULACO, a more accurate solution can be obtained in a smaller number of iterations. Therefore, IPDULACO has stronger ability to search global optimal solution and faster convergence speed, and can efficiently solve TSP..
【作者单位】：江南大学理学院;
【基金】：国家自然科学基金资助项目(11371174) 中央高校基本科研业务费专项资金资助项目(1142050205135260,JUSRP51317B)~~
【分类号】：TP18

【相似文献】