旅行家问题和遗传算法
旅行家问题 旅行家问题（Travelling salesman problem 以下简称TSP）是一个NP难题，其内容为给定一系列城市，每个城市只访问一遍，然后回到起点城市，在所有可能的路径中长度求解最短的一条。
可以看出旅行家问题是组合问题与最短路径问题的结合，最短路径问题的求解算法有很多，常规的有“迪杰斯特拉算法”和“弗洛伊德算法“。但这些算法都无法完美的应用于旅行家问题，针对此问题较为有效的算法有”遗传算法“、”粒子群算法“、”蚁群算法“这类智能群算法。
本文将用”遗传算法”来求解旅行家问题。
遗传算法 遗传算法的发展 1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。
1967年，Bagley在他的论文中首次提出了遗传算法这一 术语，并讨论了遗传算法在自动博弈中的应用。
1970年，Cavicchio把遗传算法应用于模式识别中。第 一个把遗传算法应用于函数优化的是Hollstien。
1975年是遗传算法研究的历史上十分重要的一年。这一 年，Holland出版了他的著名专著《自然系统和人工系 统的适应性》该书系统地阐述了遗传算法的基本理论和 方法，并提出了对遗传算法的理论研究和发展极为重要 的模式理论(schemata theory)，该理论首次确认了 结构重组遗传操作对于获得隐并行性的重要性。
遗传算法的基本思想 遗传算法的基本思想是将问题的解编码为染色体，这是十分重要的环节，在算法中便是一个按照特定方式编码的串。
将问题的解编码之后，按照自然进化论的观点，生成一定数目的个体（染色体），然后按照自然选择，染色体交叉，染色体变异的流程不断地繁衍迭代。
种群经过不断地繁衍发展，最终最适应环境的一些个体会保留下来，这些最适应环境地个体也将是在遗传算法背景下待求解问题的最优解。
遗传算法的要素 通过上述对遗传算法的思想的阐述，可以得知遗传算法包含许多要素，其中最重要的便是染色体即问题的解。
染色体：编码之后的问题的解 种群：一定数目个体（染色体）组成的集合 自然选择算子：对种群中适应度较高的个体筛选的算法 染色体交叉算子：染色体之间进行交叉的方式 染色体变异算子：染色体变异的方式 PM：代表种群中染色体变异的概率 PC：代表种群中染色体之间交叉的概率 N：种群的规模，在不断迭代中种群的规模一般保持不变 在用遗传算法求解问题时，这些要是都是必备的。但是针对于不同的问题要素的表现形式有所不同。例如染色体的编码方式就有二进制编码和真值编码两类，对于不同的问题要选择合适的要素形式。
遗传算法对TSP的建模 染色体编码方式 针对TSP的描述，需要先将城市编号，如1, 2, ... n。TSP的解途径各个城市的顺序也就是路径可以表示为：1 -> 3 -> ... n，因此可以采用真值编码的方式对路径进行编码。
染色体表示为：1.3.2.5.6.4其中.为分隔符。
除此之外也可以选择二进制编码，将城市编号转变为特定长度的二进制数字。这种编码方式在染色体交叉和变异中会比较方便，但是针对于问题规模，编码的长度需要改变，同时染色体交叉过程中容易产生不合理的解（交叉过程中产生了一个不存在的城市编号）。
染色体交叉算子定义 交叉算子多种多样，分别适用于不同的问题。其中常见的算子有：
Partial Mapped Crossover （PMC） Order Crossover （OX) Position Based Crossover（PBC） Order Based Crossover （OBX） Cycle Crossover（CX） Subtour Exchange Crossover 除此之外，还有针对于TSP优化的交叉算子”贪心交叉算子“等等，本文采用Order Crossover作为交叉算子。