一种改进的蚁群算法在TSP问题中的应用研究

蚁群算法是近几年发展起来的一种新型的拟生态启发式算法,它已经被成功地应用在旅行商(TSP)问题上.由于基本蚁群算法存在过早陷入局部最优解和收敛性较差等缺点,文中对基本蚁群算法在基于蚁群系统的基础上进行了改进,在信息素的更新和解的搜索过程中更多地关注了局部最优解的信息,以使算法尽可能地跳出局部最优,并且改进后的算法对一些关键参数更容易控制.多次实验表明改进的蚁群算法在解决TSP问题上与基本蚁群算法相比有较好的寻优能力和收敛能力.这种算法可以应用在其它组合优化问题上,有一定的工程应用价值.

An Improved ant Colony Optimization Algorithm and Its Application in Solving TSP

The Ant Colony Optimization(ACO) algorithm is a new meta-heuristic algorithm and has been successfully used to solve Traveling Salesman Problem(TSP).Because the classical ACO easily traps in the local best solution and has worse performance in convergence,the paper improves the classical ACO based on the Ant Colony System.The information of local best solution is focused on updating the pheromone and searching best solution,and the key parameters are controlled easily in improved algorithm.The results have shown that the performance of this algorithm can be improved in finding optimal solution and quick convergence of TSP.It would be interesting to apply this algorithm to other combinatorial optimization problems.