旅行推销员 - 遗传算法
4.88/5 (98投票s)
本文介绍了一种遗传算法，该算法搜索访问多个地点并返回原点的最短路径。
部分代码现已整合到此项目中： https://github.com/ms-iot/plotmyface
引言
我最近发表了文章 遗传和进化算法的另一种介绍，其中我介绍了一种能够找到某些数学公式的进化算法。
那里重要的特征是种群的创建、当我们没有令人满意的结果时选择最佳结果以及带有变异的繁殖。这些都是遗传算法使用的特征，但我的示例不是遗传算法，因为它没有使用染色体和基因。
好了，这次我将介绍一个真正的遗传算法，目的是解决旅行商问题（通常简称为 TSP）。
基因和染色体
也许拥有遗传算法的最重要特征是与生物学的类比，这需要使用染色体，因此需要使用基因。
许多文档说染色体通常表示为字符串，而字符串的各个部分是基因。这些文档中的示例实际上使用了string数据类型，因此字符串中的每个字符都被解释为基因。
在旅行商示例中，我没有使用string数据类型。每个基因是一个必须访问的Location，而染色体是这些Location的数组，有效地告诉旅行计划（首先去那里，然后去那里......）。这些染色体的大小是必须访问的地点数量，并且为了有一个有效的染色体，所有地点都必须恰好访问一次。
需要注意的是，使用arrays并没有违反“字符串”的理念，因为它不是数据类型名称，它只是表明我们需要一个基因序列，而数组可以很好地完成这项工作。
基本算法
在拥有一个必须访问的地点列表之后，就需要生成染色体（旅行计划）的初始种群。要做到这一点，只需随机排列这些地点（此处可以使用其他算法）。
创建了初始种群后，代码进入一个循环，在其中：
- 选择最佳染色体（旅行计划）；
- 显示迄今为止的最佳解决方案；
- 繁殖它们并继续下一代的循环。
特定于问题的是
- 它如何决定哪些染色体是最佳的？
- 它如何决定何时停止？
- 在繁殖期间，它会使用交叉、变异还是其他什么来进化？
我为制作示例所做的答案是：
- 它只是计算在访问地点顺序下行驶的总距离。起点（也是终点，并且始终位于左上角）不编码在染色体中，以避免浪费时间在起点错误的地方，但它用于计算行驶距离；
- 它不决定何时停止。算法将继续永远运行。是应用程序的用户可以认为找到了一个好的解决方案（或者只是厌倦了等待）并关闭应用程序，或者尝试新的目的地；
- 进行交叉和随机变异肯定会产生访问同一地点两次的染色体。它最终可能会进化到好的解决方案，但会浪费大量时间在这些错误的解决方案上。这个问题很大，所以我将更详细地解释它。
排列
请看下图。
红圈代表起点和终点。所有其他圆圈代表必须访问的地点。
染色体实际上将由Location引用的数组构成，在本文中，这些将用字母表示。如前所示，根据给出的目的地，它们可以被视为基本染色体ABCDE。
在繁殖它时，我们不希望出现像 ABCBE 这样的情况，因为我们会访问 B 两次，而我们永远不会访问 D。图形上可以表示为：
我们也不希望出现 ABCDF 这样的情况，因为 F 地点根本不存在。我们只想改变访问地点的顺序，生成类似
ABECD
或者
EBCDA
这就是为什么在繁殖期间，我让代码使用“交换”之类的变异，而不是简单的随机位更改。
当然，我之前的例子并没有给出正确的结果，但通过进行这些交换，我们期望在某个时刻，它会达到这个结果
ABDCE
更复杂的情况
移动
现在想象一下我们有以下情况
E 项目的顺序不正确。我们可以将此旅行计划表示为 EABDC，并且我们必须将其变为 ABDCE 来解决这个问题，这意味着我们需要将第一个项目“移动”到最后一个位置，同时将所有其他项目向前移动一个位置。这不能通过单次交换来实现，所以我决定将这种“移动”操作作为一种可能的变异。在这种情况下，通过将第一个项目移动到最后一个项目，我们将 EABDC 转换为 ABDCE，从而有效地改变了这种情况
变成这样
反转范围
现在，看看这个问题
我们可以将这种情况表示为 AEFCBDG，并且与前一种情况类似，这些交叉线意味着我们没有使用最快的路径。我们只需要避免这些交叉线，但要做到这一点，与前一个示例不同，需要按相反的顺序访问项目 EFCB，这无法通过单次交换或移动来实现。
即使我们认为会有两次正确的交换，但情况很糟，因为一次交换可能会将结果更改为 AECFBDG，导致这种情况
整个解决方案将被视为更差，可能会在没有任何繁殖机会的情况下死亡。因此，为了让代码能够一步解决这个问题，我还增加了对范围内的项目进行反转的支持。当然，这种情况会随机发生，并且可能会将 AEFCBDG 变为 CEFABDG
……但也有可能它会纠正染色体，生成 ABCFEDG 解决方案，而不会产生更差的中间解决方案，看起来像这样
关于变异的结论
因此，交换、移动和反转范围是我在示例应用程序中用于一步生成更好解决方案的三种变异。当然，这些更改是随机发生的，很多时候会产生更差的结果，但总有可能通过在正确的位置进行一次变异来生成更好的结果，而无需中间结果被视为更差。
精英主义
精英主义是指在不同代之间保持一些最佳解决方案不变。在示例应用程序中我使用了它，但不是保持一些最佳解决方案，而是只保持最佳的一个。
保持多样性
与精英主义相反，始终保持种群多样性是一个好主意。我没有设置任何特殊的规则来“拯救”不同的个体免于死亡，但我创建了一种方法来强制对重复结果进行变异。实际上，当不使用交叉时，这种变异更有用。
示例
现在，我真的相信最好的做法是运行示例。
它允许您增加或减少目的地数量，重置最佳路径搜索，并创建新的随机目的地。它还允许您配置是否使用交叉以及其他影响“繁殖”的参数。
它不允许您绘制目的地，但，目的地如何生成并不改变搜索算法，所以如果您决定更改代码以允许用户绘制目的地，搜索算法将不会改变。
交叉 - 另一种问题
大多数文档说我们必须有高比例的交叉，只有少量的变异。但是，在使用交叉时，我们如何避免重复访问同一个地方？
例如，看看这种情况
ABCDE
和 EDCBA
这两种选择同样好（或者同样坏，如果你愿意），因为它们只是以相反的方向进行相同的旅行，并且可以选择它们进行交叉。进行交叉时，我们会重复访问地点（因此其他地点未被访问）。
那么，旅行商问题可以使用交叉吗？
答案介于两者之间。所以，解释一下，是的，它可以用于交叉，只要有一些东西可以纠正那些重复的地点。
关于纠正重复的地点，即使我们接受随机变异，也可以使用这种方法。为了说清楚，访问ABCDE的基因实际上可以说AAAAA。这可以解释为“访问第一个可用地点”五次。
显然，一旦一个地点被访问，它就不再在可用地点列表中了，所以这种读取值的方式将访问那些被命名为ABCDE的地点。如果给出的第一个选项是F，那么当只有 5 个可用地点时，第六个项目可以解释为与第一个项目相同（这意味着我们将可用地点列表视为“循环”）。然后当有 4 个可用地点时，F 将成为第二个项目。我想你明白了。所以，我们可以认为任何值都是有效的，只需“读取”染色体的方式不同。这仍然会导致糟糕的路径，但我们永远不会读取“不存在”或“重复”的地点，因为我们将以不同的方式解释字符串。
在示例中
好了，我的算法不使用字符来解析它们。在文章中，我说地点A，但代码将有一个指向实际Location实例的引用。所以，我们用文本表示的AAAAA实际上是指向同一个地点 5 次。
我的解决方案是让基因在执行交叉后变得有效。为此，我创建一个包含所有可用地点的哈希集，然后遍历染色体中的所有Location，从列表中删除它们，或者，如果不可能，则注册该基因必须被一个可用的基因替换。我先完成该循环，然后，如果需要替换的基因，我只需按顺序用仍然可用的基因替换它们。也许我按顺序执行此操作不是最佳解决方案，但我避免创建访问某些地点两次而忘记访问其他地点的“旅行路径”。
选择配偶
独立于旅行商问题中重复基因的问题，交叉需要两个个体进行交配。在这里我们看不到个体，只看到染色体，但我们可以认为每个染色体都有一个对应的个体。那么，如何选择个体进行交配呢？
这是一个有许多不同算法的领域。在一些解决方案中，所有“个体”都有机会，其机会的大小取决于它们的“适应度分数”。这通常会使最好的个体拥有更多的后代，而最差的个体则没有后代，但有时最好的个体没有一个后代，而最差的一些却有……这真的取决于运气。
在我的算法中，我简单地忽略了这一点。我使用了与我之前文章中做的事情非常相似的方法。我选择了排名前一半的染色体进行两次繁殖。然后，如果它们需要交叉，它们将选择这些排名前一半的染色体（呃……个体）中的任何一个进行繁殖。事实上，我的算法在这方面非常糟糕，以至于一个染色体可能最终与自身交配……创建一个完美的克隆后代，因为交叉中没有任何东西可以改变。
我为什么不使用其他技术？仅仅是因为我认为这对于让这个示例工作是不必要的。事实上，即使没有交叉，示例已经可以工作了。那么，为什么还要复杂化已经奏效的事情呢？嗯，如果目的是拥有一个真正完整的算法，我可能会考虑根据请求的数量来更改应用程序。
结论
我的结论是，我们不需要应用甚至了解遗传算法的“基础知识”来创建一个功能性的遗传算法。示例应用程序可以通过仅使用变异来工作并找到结果，完全忽略交叉。当然，理解其他概念是很好的，它们对于专业应用程序可能是必需的，但我相信通过构建最基本（且更简单）的算法，我们已经可以看到算法在工作，并且当我们看到算法找不到最佳解决方案（或找到它的速度太慢）时，我们可以看到所有其他“细节”的重要性，并且通过探索主算法的许多部分的各种解决方案，我们可以更好地理解它们。
这些许多细节包括如何创建第一个种群，如何选择将从一代传到下一代的染色体（如果有的话），哪些将能够繁殖，变异如何真正工作（我在示例中使用了 3 种变异），是否将使用交叉，这些交叉究竟如何工作，因为我选择从一个染色体复制一个基因块到另一个染色体，但我们可以从两个（或更多）参与的染色体中随机选择每个基因，如何计算染色体的适应度（它们有多好）等等。
因此，我希望这篇文章及其示例能帮助想要学习遗传算法基础知识的新开发人员。我真的希望您尝试这个示例，甚至进行一些修改，如果这有助于您更好地理解概念。