旅行家问题和遗传算法

旅行家问题

旅行家问题（Travelling salesman problem 以下简称TSP）是一个NP难题，其内容为给定一系列城市，每个城市只访问一遍，然后回到起点城市，在所有可能的路径中长度求解最短的一条。

可以看出旅行家问题是组合问题与最短路径问题的结合，最短路径问题的求解算法有很多，常规的有“迪杰斯特拉算法”和“弗洛伊德算法“。但这些算法都无法完美的应用于旅行家问题，针对此问题较为有效的算法有”遗传算法“、”粒子群算法“、”蚁群算法“这类智能群算法。

本文将用”遗传算法”来求解旅行家问题。

遗传算法

遗传算法的发展

1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。

1967年，Bagley在他的论文中首次提出了遗传算法这一 术语，并讨论了遗传算法在自动博弈中的应用。

1970年，Cavicchio把遗传算法应用于模式识别中。第 一个把遗传算法应用于函数优化的是Hollstien。

1975年是遗传算法研究的历史上十分重要的一年。这一 年，Holland出版了他的著名专著《自然系统和人工系 统的适应性》该书系统地阐述了遗传算法的基本理论和 方法，并提出了对遗传算法的理论研究和发展极为重要 的模式理论(schemata theory)，该理论首次确认了 结构重组遗传操作对于获得隐并行性的重要性。

遗传算法的基本思想

遗传算法的基本思想是将问题的解编码为染色体，这是十分重要的环节，在算法中便是一个按照特定方式编码的串。

将问题的解编码之后，按照自然进化论的观点，生成一定数目的个体（染色体），然后按照自然选择，染色体交叉，染色体变异的流程不断地繁衍迭代。

种群经过不断地繁衍发展，最终最适应环境的一些个体会保留下来，这些最适应环境地个体也将是在遗传算法背景下待求解问题的最优解。

遗传算法的要素

通过上述对遗传算法的思想的阐述，可以得知遗传算法包含许多要素，其中最重要的便是染色体即问题的解。

1. 染色体：编码之后的问题的解
2. 种群：一定数目个体（染色体）组成的集合
3. 自然选择算子：对种群中适应度较高的个体筛选的算法
4. 染色体交叉算子：染色体之间进行交叉的方式
5. 染色体变异算子：染色体变异的方式
6. PM：代表种群中染色体变异的概率
7. PC：代表种群中染色体之间交叉的概率
8. N：种群的规模，在不断迭代中种群的规模一般保持不变

在用遗传算法求解问题时，这些要是都是必备的。但是针对于不同的问题要素的表现形式有所不同。例如染色体的编码方式就有二进制编码和真值编码两类，对于不同的问题要选择合适的要素形式。

遗传算法对TSP的建模

染色体编码方式

针对TSP的描述，需要先将城市编号，如1, 2, ... n。TSP的解途径各个城市的顺序也就是路径可以表示为：1 -> 3 -> ... n，因此可以采用真值编码的方式对路径进行编码。

染色体表示为：1.3.2.5.6.4其中.为分隔符。

除此之外也可以选择二进制编码，将城市编号转变为特定长度的二进制数字。这种编码方式在染色体交叉和变异中会比较方便，但是针对于问题规模，编码的长度需要改变，同时染色体交叉过程中容易产生不合理的解（交叉过程中产生了一个不存在的城市编号）。

染色体交叉算子定义

交叉算子多种多样，分别适用于不同的问题。其中常见的算子有：

1. Partial Mapped Crossover （PMC）
2. Order Crossover （OX)
3. Position Based Crossover（PBC）
4. Order Based Crossover （OBX）
5. Cycle Crossover（CX）
6. Subtour Exchange Crossover

除此之外，还有针对于TSP优化的交叉算子”贪心交叉算子“等等，本文采用Order Crossover作为交叉算子。

Order Crossover是一种顺序交叉的算子，其大致思路为：

• 从父代1中选取一段基因
• 作为子代1的基因（位置与父代对应）
• 将子代1在父代2中的基因片段剔除
• 剩余的基因按位置先后顺序移动至子代1的基因片段中
• 子代2的生成算法与子代1相同

染色体变异算子定义

本文中染色体变异算子采用特定点交换的算法，在一条染色体中随机选择两个位点，然后将这两个位点的基因进行交换。

选择算子定义

选择算子在求解中也十分重要，目前常用的选择算子有“轮盘赌算法”，“锦标赛算法”，“最优保存策略算法”，“确定式采样算法”等。

本文所用的算子为“最优保存策略算法”，其思路十分简洁，只选取特定个数的最优个体保存至下一代种群，保存下来的个体会按照概率进行染色体的交叉和变异。

这种选择算子在设计上十分简洁，且在效果上容易达到收敛，但是这种算子容易陷入局部最优解。

结果展示与总结

最终在对于31个城市规模下的旅行商问题求解中，种群规模N设置为120，变异概率PM设置为0.10， 交叉概率PC设置为0.75，迭代次数设置为300。遗传算法结果最终缀收敛到16917，与该问题规模下的最优解15377还有一定差距。

从每一代最优解的变化图中可以看出，算法最终在170代左右趋于收敛。在采用最优保存策略算法作为选择算子的情况下，问题容易较快收敛而达不到最优的解。但在不断地实验中，可以看出问题不会发散，即问题的解总是趋于收敛的。

除了算子的选择之外，还需考虑在给定算子搭配使用的情况下，如何确定种群规模，变异概率，交叉概率等参数也十分关键。