-
摘 要：旅行商问题是一个典型的NP问题. 本文将对旅行商问题的概念、历史、以及数学模型等做简单的介绍. 在此基础上将会对解决此类问题的几种算法做简单的分析，比如动态规划法、退火算法、分支定界法，蚁族算法等. 最后着重介绍一下遗传算法解决旅行商问题并完成编码的实现.9794
- 上一篇：基于安全首要的一类含消费效用最大化问题的实证分析
- 下一篇：基于VaR方法的投资风险管理研究初探
关键词：旅行商问题 遗传算法 编码
Abstract： Traveling salesman problem is a typical NP problem. Concept, history, and mathematical models, such as the traveling salesman problem in this article will make a brief introduction. Based on this simple analysis will be done on several algorithms to solve such problems, such as dynamic programming, annealing, branch and bound method, ant algorithms. Finally focuses on what genetic algorithms to solve the traveling salesman problem and complete coding implementations.
Key words：TSP Genetic Operators Coded
1. 引言
旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题. 经典TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有的城市后，回到出发地. 应该如何选择行进路线，以使得总的行程最短. 由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题. 由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究.早期的研究者使用精确算法求解该问题，常用的方法包括：分支定界法、线性规划法和动态规划法等. 但是，随着问题规模的增加，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络算法等. 本文从介绍TSP模型入手，概要介绍几种常用算法，并重点介绍遗传算法及其应用.
遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望. 尽管在遗传算法的研究和应用过程中出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的工作实践中[1].
遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态. 由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理策略等领域得到了广泛应用. 遗传算法给我们呈现出的是一类通用的算法框架，该框架不依赖于问题的种类. 遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能. 隐含并行性和全局搜索特性是遗传算法的两大显著特征.
2. TSP问题简介
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一. 假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市. 路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难题.
2.1 TSP问题的研究历史起源