基于城市权重的蚁群算法及其在TSP中的应用

Ant Colony Algorithm based on Weight of City and Its Application in TSP

蚁群算法在解决NP—C问题时展现出了较强的适用性，但收敛速度慢，容易陷入局部最优解的缺陷却没有得到较好解决。于是，提出了一种基于城市权重的蚁群算法ACAWC（Ant Colony Algorithm based on the Weight of City）。改进后的算法通过利用城市距离在整个城市网中所占比重来协调启发信息作用，同时应用双重赌盘算法和双重随机性的思想，增强了跳出局部最优解的概率，并改进了依据路径贡献度的信息素更新机制，加快了算法的收敛速度。仿真实验表明，ACAWC算法求得的最优解比基本蚁群算法提高了10％～15％，同时也一定程度地提高了收敛速度。

Ant colony algorithm usually exhibits strong applicability in solving NP complete problems, but easily falls into the defect of local optical solution for its fairly slow convergence rate. An ant colony algorithm based on the weight of city （ACAWC） is thus proposed. The modified algorithm, by using the proportion of urban distance in the whole city network, coordinates and arouses the information role, and again with double roulette algorithm and double randomness idea, enhances the probability of jumping out from the local optimal solution. By modifying the pheromone update mechanism based on path contribution, the algorithm is improved in its convergence speed. The simulation experiments indicate that the optimal solution from ACAWC algorithm could acquire an improvement of 10 % - 15 % as compared with the basic ant colony algorithm, and in addition, its convergence speed is also improved to a certain extent.