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

Solving Traveling Salesman Problem by An Improved Colony Optimization algorithm

作　　者：汤可宗[1] 江新姿[1] 张磊[1] 高尚[1] 

机构地区：[1]江苏科技大学电子信息学院

出　　处：《东华理工学院学报》2007年第4期387-391,共5页Journal of East China Institute of Technology

基　　金：江苏省计算机信息处理技术重点实验室开放课题基金(KJS0601)

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

关 键 词：蚁群算法 旅行商问题 信息素 最优解 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]