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函数中的参数。
文章评论
Невелика деталь, яка здатна повністю змінити образ – це якісні <a href=https://ukrbeautystyle.com.ua/category/Remen>ремені</a>. Вони підкреслюють силует та додають завершеності будь-якому вбранню.
Щоб зрозуміти термін «<a href=https://www.komplaens-audit.top/internal-audit/>комплаенс это</a>», довелося перечитати кілька джерел. Виявилося, що все простіше, ніж я думав.
Регулярно сравниваю и заметил, что автобус в Польшу из Украины цена <a href=https://www.infobus.top/>infobus.top</a> зависит от сезона и перевозчика. Выгоднее всего планировать поездки заранее.
Нещодавно спробував замовити квиток на автобус до Польщі <a href=https://www.infobus.top/ru/buy-bus-tickets-poland-from-rovno/>infobus.top</a> через інтернет. Виявилось, що це дуже швидко, без зайвих черг та очікування.
Наш новий співробітник попросив показати <a href=https://www.komplaens-audit.top/audit/obyazatelnyj-audit-finansovoj-otchetnosti.html>звіт внутрішнього аудиту приклад</a>, щоб швидше зорієнтуватися в роботі. Це допомогло йому краще зрозуміти процес.
Активний спосіб життя потребує особливої уваги до деталей, тому якісна функціональна білизна <a href=https://ukrbeautystyle.com.ua/category/FunktsonalnaBlizna>ukrbeautystyle.com.ua</a> стає незамінною. Вона забезпечує комфорт і підтримку під час тренувань.
Для бронирования тура всегда захожу на <a href=https://pegas-touristik-2025.ru/>официальный сайт пегас туристик p-tour.ru</a>. Работает стабильно, никаких сбоев.
Уже несколько лет летаем по <a href=https://pegas-turkey-tury.ru/>Турция путевки</a>, особенно весной и осенью. Удобно, тепло и недорого.
При поиске качественных ссылок часто используется <a href=https://www.olx.ua/d/uk/obyavlenie/progon-hrumerom-dr-50-po-ahrefs-uvelichu-reyting-domena-IDXnHrG.html>база трастовых сайтов для хрумера</a>.
Решили спонтанно <a href=https://pegas-turkey-tury.ru/>купить тур в Турцию p-tour.ru</a>, оформили за день и полетели на выходные. Очень удобно и быстро.
Мы выбрали компанию, которая предлагает продвижение сайтов Петербург <a href=https://prodvijenie-saytov-78.ru/>https://stokrat.org/</a> с понятной стратегией и адекватными сроками. В Петербурге такие исполнители — редкость.
https://renewablenergy-world.com/teleskop.html
https://crimeabest.com/kollimator/
https://xtgamers.com/page-id-18999.html
https://stomatologist.org/opticheskiy-pritsel/
https://designstil.info/opticheskij-pricel/
https://chernigiv.name/uk/articles-2534-teplovizor
https://www.dress-code.com.ua/content/view/25060/