遗传算法解决旅行商问题

1 问题描述

旅行商问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

本文章中，城市数据为 127 个城市的 x 和 y 坐标。数据地址见文末。

2 流程图

3 实现细节解释

3.1 路线个体的表示

采用整数编码的方式，将 n 个城市依次编码为 0 到 n-1。对于所给数据而言，将127个城市依次编码为0至126。因此，一条路线可以由一个127维的向量进行表示。

由于路线需要频繁更改，但不会增加或减少城市，这里采用 numpy 作为存储结构。

在实际编码中，为了提高运行效率，所有路线被编码成一个2维 numpy 数组，每一行表示一条路线。如，2 条 10 个城市的路线可以表示为：

\(\begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
\end{bmatrix}\)

在代码中，我将路线种群的数量设置为 100，而城市个数为 127，故所有路线可以表示为一个 (100, 127) 的 numpy 数组。

3.2 距离与适应度函数

路线距离和适应度是衡量路线优良的指标，必须好好理解。

距离定义比较简单，两个城市m和n之间的距离定义为二维空间欧氏距离：

\(d_{mn}=\sqrt{{(x_m-x_n)}^2 + {(y_m-y_n)}^2}\)

则某一路线的总距离定义为：

\(D=\sum_{j=1}^{n}l_j\)

其中，\(l_j\) 为路线中第 \(j\) 个城市到第 \(j+1\) 个城市的距离（ 1 为起始城市），\(l_n\) 为路线中最后一个城市到第一个城市的距离。

例如，对于路线： 1 0 3 2

其路线总距离

\(D=l_1+l_2+l_3+l_4=d_{10}+d_{03} + d_{32} + d_{21}\)

在实际编码中，我们预先计算出了一个城市距离矩阵（对称矩阵），第 i 行 j 列的元素表示城市 i 到城市j之间的距离。

这样预先处理的好处是，避免在后面迭代的过程中进行无意义的重复计算。

例如，4 个城市的城市距离矩阵为：

\(\begin{bmatrix}
d_{00} & d_{01} & d_{02} & d_{03} \\
d_{10} & d_{11} & d_{12} & d_{13} \\
d_{20} & d_{21} & d_{22} & d_{23} \\
d_{30} & d_{31} & d_{32} & d_{33}
\end{bmatrix}\)

适应度函数 f 取距离的倒数：

\(f=\frac{1}{D}\)

3.3 路线初始化

这里初始种群为随机生成的 100 条路线。 使用 np.random.choice 生成 0 至 n-1 的不重复的长度为 n 的 numpy 数组。

3.4 选择

个体路线适应度越高，其被选择的机会就越多。故此处采用与适应度成比例的概率方法进行选择。

具体地说，就是首先计算群体中所有个体适应度的总和，再计算每个个体的适应度所占的比例，并以此作为相应的选择概率。然后采用轮盘赌方法进行 100 次带概率的随机选择。

3.5 交叉

交配操作是遗传算法中最主要的遗传操作。这里可能是相对比较难理解的，我理解的时候也是花了一些时间，我这里会用例子进行详细解释。

这里采用基于部分映射的交配法：

产生一个随机数，确定交叉的起始位置，对起始位置及之后的位置进行交换，并放在首位，然后再从各自的路径中按顺序填充未出现过的数字。

例如，当随机数为 4 时，起始位置取 4，交叉结果如下（以10个城市为例）：

对所有路线两两进行交叉操作。如路线 0 和路线 1，路线 2 和路线 3，以此类推。

3.6 变异

变异操作是按向量维度进行的，即把某一维的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率都取得较小，这里概率取0.01，采取对于一个路线个体随机选取两个城市进行交换的策略。如下：

父代路径: 0 8 6 5 1 7 2 9 3 4 0

子代路径: 0 8 6 9 1 7 2 5 3 4 0

3.7 最优路线的保存

我设置的最大迭代次数是 100000，每一次迭代之后，都会保存最优的路线。如果连续2000次迭代之后，最优路线都没有改变，就停止迭代。输出最优的路线。

4 运行结果展示

（每个城市编号加一后即为原来数据城市编号）

5 代码与数据

6 代码使用方法

只需修改数据导入方式，将数据导入 cities 变量，即可运行。当然最好也相应修改一下main函数中的参数。