0 说在之前

正常来说，一个正常的 Oier 是不会碰这种东西

但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣， 我就试着理解一下

因为也仅仅是试着理解，如有理论错误还往各位在评论区斧正

本文的代码实现可以在 https://gitee.com/yingziyu/task 看到

1 什么是遗传算法

先来搬运维基百科

遗传算法（英語：genetic algorithm (GA) ）是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等等。

Wikipedia – 遗传算法

2 使用遗传算法求得旅行商问题近似解

旅行商问题（最短路径问题）（英語：travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

Wikipedia – 旅行推销员问题

首先明确遗传算法要做什么

1. 生成数个随机生物，形成环境
2. 交配突变产生新的随机生物
3. 计算适应度，筛选掉不合适生物
4. 回到第 2 步

那么这样就会有几个变量

• 环境中初始生物个数，我们令其为 pn
• 突变概率，我们令其为 pm
• 交配概率，我们令其为 pn

在一些算法实现中会加权交配，但是这东西实在是不想写……

2.1 理论实现

如何计算适应度？

这个倒是简单，路径长度的倒数就是其适应度

那么算法就是

1. 随机生成 pn 条路径
2. 路径之间随机交叉，生成预备进入下一代环境的生物
3. 生物根据概率突变
4. 排序，去除 pn 名后的路径
5. 回到第 2 步

• 如何交叉？

随机确定第一个路径中的 $\frac{n}{2}$ 个位置，剩下位置按照第二个路径顺序合并

• 如何突变？

随机交换路径中两个点就行

2.2 代码实现

一开始是用 cpp 写的，但是把自己写吐了 — 鬼知道他是哪里泄漏的

后来就用 Rust 写了，具体可以看代码里的注释

3 结

这种算法出乎意料的稳定。除去极端情况，都可以生成一个较优的解。

随机化算法中，调参就和炼丹一样，难以知晓结果。在这个算法中也同样体现出来。

但无论如何，这个算法能在极端时间内求出一类问题的较优解是毋庸置疑的。