蚁群算法求解TSP问题.doc

HUNAN UNIVERSITY课 程 作 业课程题目 智能优化算法 学生姓名 李小燕学生学号 S专业班级 计算机科学与技术学院名称 信息科学与工程学院指导老师 杨圣洪2014 年6月 8日蚁群算法求解TSP问题摘要：蚁群算法是一种分布式内在并行算法。单个蚂蚁的搜索过程是彼此独立的，易于局部最优，通过个体间不断的信息交流和传递有利于发现较好解；并且该算法是一种正反馈算法。路径上的信息素浓度较高，将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的进化过程。本文通过求解TSP问题，通过在特定情况下对路径进行逐步遍历比较来降低陷入局部最优解的可能性, 找出最优解。关键词：蚁群算法；TSP；信息素；遍历1. 引言 TSP问题又称最短路径问题，还称为旅行商问题，是一种比较经典的 NP 难题，问题描述较简单，而获得最优解却十分困难。求解 TSP 问题不仅为其他算