应用遗传算法中的变异算法求解旅行商问题

Question

我正在做一个小型学术作业，用遗传算法解决旅行推销员问题。我遵循一个非常简单的经典表示，将城市和旅游存储在数组中，例如，10个城市的旅游可以表示为9-1-0-4-3-8-6-5-2-7等等。对GAs有相当基本的了解，我有点困惑你会遵循什么样的方法来将不同类型的突变应用于TSP。假设我们的路由表示为路由，突变率表示在变量m_rate中。

[1]简单插入突变

说我们有：1-2-3-4-5-6-7-8-9。然后我们随机选择一个城市，说指数5然后随机选择一个像2这样的插入指数，那么突变的染色体是：1-2-6-3-4-5-7-8-9。

现在我要做的是应用变异：

for (int i=0; i<route.length; i++) {
 if (m_rate<Math.random()) {
 // Pick a random city
 int randomCity =  0 + (int)(Math.random() * ( ((route.length-1) - 0) + 1));
 // Do the insertion and shift the array where appropriate
 }
}

换句话说，我在路线中的每个城市循环，看看突变条件是否成立（m_rate

[2] 互换突变。

在染色体中选择一个随机城市，然后选择第二个随机城市，并将两者交换。例如，在路由1-5-2-8-0-9-3-7-4-6。如果我们最终选择指数2和指数7，那么突变的染色体是：1-5-7-8-0-9-3-2-4-6。

我遵循与上述插入突变相似的方法，遍历路线中的每个城市，检查概率条件，然后直接选择一个随机城市进行交换，而不应用任何类型的突变率。上面同样的问题也适用于这里。

[3] 反转突变。

这是最棘手的一个。给定一个类似于1-2-3-4-5-6-7-8-9的染色体，我们选择一个类似于指数2到指数5的突变切割，然后反转该子序列==

但是你如何应用这个呢？你是否在路线中循环，然后根据变异率选择一个城市，然后直接选择另一个指数来确定子路线的长度？你会变异一次然后退出吗？在这种实现中，如果我们将突变切割为0-9或0-（长度-1），整个染色体或路径是否会发生突变，从而逆转整个过程？在这种情况下，突变率的实际值是多少？我有点迷路了。。。

我提前为这件事做得太长表示歉意。。但是，如果您能对这些问题发表任何意见，或者有人能告诉我详细讨论这些问题的任何资源，我将不胜感激。我看了很多研究论文，但没有多少研究过这种细节。

非常感谢。

Answer 1

反演通常是求解TSP问题的最佳变异算子。您可以下载并使用HeuristicLab进行实验，其中包括更多此类变异运算符和交叉。它允许您定义实验，您可以在其中使用每个操作符运行GA几次，并查看哪一个运行得最好。有一些视频教程可以帮助您开始学习。它是开源的，因此您还可以查看实现。

Answer 2

我认为最好的选择是对变异使用反转，对交叉使用OX（有序）。我写了一个求解TSP的遗传算法，效果非常好。在我的例子中，当应用反转时，我选择两个随机点（可能是整个字符串），但不是相同的点。最好的结果是变异率为0.2/0.3，交叉率为0.8，但这取决于你的选择机制。

Answer 3

选择突变时，您有两个选择：

• 您可以允许突变产生无效/非法的染色体，并对它们进行不良评分。这意味着GA将搜索正确性（剔除非法结果）和最佳结果。
• 您可以编写一个只产生有效/合法输出的变异函数。

第一个选项可以让你写出一个更简单、更自然的染色体突变。但是，您可能需要扩展表示（例如，为您的10个城市之旅允许12或15个时段），并且算法需要更长的时间才能收敛。如果必须评估正确性，您的分数函数可能会更昂贵。您可以灵活地解释染色体的解释方式（例如，忽略目的地的第二次出现）。

出于同样的原因，第一个选项还可以简化交叉的实现。

第二种选择通常会收敛得更快，但要避免变异函数中影响结果的细微偏差可能会更困难。

您建议的表示和突变与TSP的非GA近似类似，后者依赖于交换，然后进行改进测试。模拟退火是决定接受哪种换位的一种方法。

遗传html" target="_blank">算法的实现可能需要一种完全不同的染色体，使交叉和变异变得自然。