一种求解旅行商问题的改进蚁群算法

Solving Traveling Salesman Problem by An Improved Colony Optimization algorithm

蚁群算法作为一种新型的优化算法,具有很强的适应性和鲁棒性,已广泛的应用于系统控制、人工智能、模式识别等工程领域。由于蚁群算法在搜索过程中易于陷入局部最优解,存在着加速收敛和早熟停滞现象的矛盾。文章针对这些问题,在基本蚁群算法的基础上,从参数的动态调整、信息量的更新规则、局部搜索策略进行相应的改进,引入信息素平滑机制,以求在加快收敛和防止早熟停滞之间取得较好的平衡。旅行商问题的仿真表明:改进后的蚁群算法具有较好的收敛性和稳定性,能够克服算法中早熟和停滞现象的过早出现。

Ant colony algorithm has become a important method in investigation of many fields as novel optimiza- tion algorithms with robust and adaptable merits, especially systematic control、artificial intelligence 、pattern recog- nition. However, Ant Colony algorithm has some disadvantages such as easily relapsing into local best, and existing contradictory between convergence speed and precocity and stagnation. Aimed at this existed problem, A new algo- rithm based on ant colony system is provided in this paper, which is improved by dynamically adjusting parame- ters, information modification and local search strategy, and pheromone trail smoothing is added in the algorithm. The algorithm can obtain good balance between accelerating convergence speed and averting precocity and stagna- tion. Experimental results for TSP problem shows that the improved algorithm have much better convergence and stability, and overcome the precocity and stagnation in advance.