用遗传算法求解旅行商问题_计算机科学与技术.rar

摘要：TSP问题是组合优化领域一个经典的问题，有关的研究有几百年的时间。TSP问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。

　　　遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。近年来世界范围形成的进化计算热潮、计算智能已作为人工智能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广泛的关注。

　　　本文首先对TSP 问题进行了概述；接着介绍了遗传算法的基本原理、遗传算法的特点，遗传算法的发展方向和它的主要应用领域；最后论述了遗传算法在TSP问题上的编码表示和遗传算子（选择算子，交叉算子，变异算子）等应用情况。

关键字：遗传算法; 旅行商问题; 选择算子; 交叉算子; 变异算子

Abstract：TSP is a typical problem in the field of combinatorial optimization problems and it has been researched for hundreds of years. TSP is a kind of typical NP-complete problem, and genetic algorithm is a more desirable method to solve NP problems.

　　　Developing on natural selection and evolutionary of biological mechanisms, genetic algorithm is a highly parallel, randomized and adaptive search algorithm. Formed in recent years around the world, boom of evolutionary computation and computational intelligence have become one of the major directions of artificial intelligence research, as well as the subsequent rise of artificial life research, that genetic algorithms is concerned broad.

　　　Paper first describes the problem of TSP, and then paper introduces the characteristics, development direction and major applications of basic genetic algorithms; At last, paper discusses the TSP problem of genetic algorithms and genetic coding that operator (including the selection operator, crossover operator,     mutation operator of these three operators) and other aspects of the application.

Keywords：Genetic Algorithm；Traveling Salesman Problem；Reproduction Operator；Genetic Operator；Mutation Operator

　　　许多关于TSP的工作并不是由应用直接推动的，而是因为TSP为其他一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。TSP大量的直接应用给研究领域带来了生机，并指导了未来的工作。例如：在校区内如何安排校车路线接送学生的问题，因为它对M.UFlood(20世纪40年代初一位研究TSP的先驱者)的研究提供了源动力，所以这个运输应用对TSP有着重要的历史意义。更多新近的应用包括电报公司中呼叫服务的时序安排，货舱中栈式起重机的路线安排，收邮包的卡车行车路线安排等等。虽然运输问题是TSP最自然的应用，但由于其模型的简单性，使得TSP在其他领域都有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间，虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在制造业的过程中占据显著的地位，TSP在减少费用上就扮演了一个非常重要的角色。