搜索
兰州交通大学（大作业）第一页2014-2015学年第2学期计算机科学与技术专业︽专业技术信息检索︾大作业专业：计算机科学与技术班级：1302班学号：201310620姓名：齐廉浩成绩：兰州交通大学（大作业）第二页第I部分一、检索课题：TSP（旅行商问题）的解决算法二、查阅的图书：图书1：书名：《迷茫的旅行商》作者：WilliamJ.Cook出版社：人民邮电出版社出版年份：2013—10—1图书2：书名：《遗传算法及其应用》作者：陈国良、王煦发、庄镇泉等出版社：人民邮电出版社出版年份：1996—6图书3：书名：《神经计算智能基础》作者：靳蕃出版社：人民邮电出版社出版年份：2000—1—1图书4：书名：《遗传算法与工程设计》作者：玄光男出版社：科学出版社出版年份：1999—12图书5：书名：《进化计算》作者：王正志、薄涛出版社：国防科技大学出版社出版年份：2000图书6：书名：《最优化理论与方法》作者：陈宝林出版社：清华大学出版社出版年份：2005—10兰州交通大学（大作业）第三页三、查阅的期刊：期刊1：题名：求解旅行商问题的几种算法的比较研究刊名：《重庆邮电大学学报(自然科学版)》作者：李敏、吴浪、张开碧出版年份：2005年卷号（期号）：第五期期刊2：题名：遗传算法和模拟退火算法求解TSP的性能分析刊名：《计算机技术与发展》作者：汪松泉、程家兴；出版年份：2009年卷号（期号）：第11期期刊3：题名：改进遗传算法求解TSP问题刊名：《数学的实践与认识》作者：文杰、倪勤；出版年份：2009年卷号（期号）：第11期期刊4：题名：求解一类线性规划问题的原始贪婪算法和对偶贪婪算法及其相互关系刊名：《兰州交通大学学报》作者：黄辉，梁国宏等出版年份：2007年卷号（期号）：第26期兰州交通大学（大作业）第四页四、查阅的网站：网站1：网址：（兰州交通大学图书馆）网站2：网址：（IEL（电气电子工程师协会）数据库）五、信息阅读分析5.1TSP定义：即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。5.2解决TSP的算法：2.1贪婪算法贪婪算法[2]（Greedyalgorithm）是求解大规模TSP问题的常用算法之一，是一种求解优化问题的简单、迅速的求解办法。贪婪法有限考虑当前情况兰州交通大学（大作业）第五页下最优的优化测度，自顶向下，逐步迭代，具有算法简单，耗时短的特点。但贪婪算法的求解结果往往不是最优的，甚至可能与全局最优解间有不小的差距。2.2模拟退火算法模拟退火（SimulatedAnnealing，SA）算法是求解TSP问题的有效方法之一，容易编程实现，求解速度快。模拟退火是一种全局优化算法，加入了随机状态模型，使算法以概率选择的方式逼近最优状态，其收敛性可以得到严格的理论证明。模拟退火算法具有一整套完整的退火搜索计划，包括足够高的初始温度、缓慢的退火速度、大量的迭代次数及足够的概率扰动[3]。2.3遗传算法遗传算法（GeneticAlgorithm，GA）是一种常用的智能算法，具有全局搜索能力，对TSP问题有良好的效果。遗传算法是由Michigan大学的J.Holland教授于1975年提出，算法通常由编码、个体适应度评估和遗传运算三部分构成，其中遗传运算包括染色体复制、交叉、变异和倒位等[4]。2.4粒子群算法粒子群算法（ParticleSwarmOptimization，PSO）是依据鸟类觅食的群体性模型而发明的新型智能算法，是由美国电气工程师Eberhart和社会心理学家Kennedy于1995年提出，具有通用性强，参数少，容易实现，收敛速度快等优点，也是解决TSP问题的有效算法之一[5]。2.5蚁群算法蚁群算法（AntColonyOptimization，ACO）是根据蚂蚁发现路径的行兰州交通大学（大作业）第六页为的而发明的用于寻求优化路径的机率型算法，由MarcoDorigo于1992年在他的博士论文中提出。蚁群算法是一种模拟进化算法，具有包括较强的鲁棒性在内的许多优良性质，在本质上是一种并行的分布式算法，容易实现，可以较好地求解TSP问题[6]。除了以上介绍的算法以外,还有[17]禁忌搜索法TS(TobuSearch,简称TS)[18～20]、r2opt算法、LK(LinKer2nighan,简称LK)算法[21]、人工免疫AIS(ArtificialImmuneSystem,简称AIS)算法[22]和粒子群优化PSO(ParticleSwarmOptimization,简称PSO)算法[23]等5.3研究TSP的实际意义：可以应用到生活中的各个方面，它的研究会大大影响我们在旅游，快递，出行，工作等等各方面的效率，节省大量的时间，减少不必要的开支，为公司可以提高业绩，为科研则可以尽可能的避免走弯路。六、信息利用总结：TSP问题有着很大的求解难度，但并不意味着无法进行有效的求解，使用一些比较成熟的智能化算法进行求解，可以获得较好的解答。当然各种近似求解算法还有着一些固有的缺陷，在不同情况下有着不同的性能表现，需要在使用时加以选择。TSP是由生活中的问题演化而来，随之而来的是对于该问题的各种深入探讨与研究，解决该问题的算法也应运而生，这些算法虽然都不能对TSP兰州交通大学（大作业）第七页进行尽善尽美的解决，但它们还是从各个角度对这个问题进行了解释，俗话说，结果不重要，重要的是过程，这句话对于学术研究这个方面的人来说很是恰当，我们也应该具备“结果不重要，重要的是过程”的认知，这个会帮助我们正确面对生活中的事情。当然除了TSP，生活中，研究中还有其他的NP问题，像经典的还有子集和问题、Hamilton回路问题、最大团问题，我们作为计算机专业的学生，应该借用各种资源，加强对于这些经典问题的认知与认识，提高自己的学术修养，扩展自己的眼界，从专业的角度审视生活中的小问题。