遗传算法 - 加权图中的最短路径

Question

我想制作一个遗传算法来解决加权连通图中的最短路径问题。与旅行推销员类似，但它只是连接而不是完全连接的图形。

我的想法是以二进制形式为每个染色体随机生成一个由n-1个节点组成的路径，其中数字表示路径中的节点。然后我会根据权重的总和选择最好的（如果不能从A到B我会给它惩罚）和交叉/变异位。它会起作用吗？感觉有点像较小版本的暴力。有没有更好的办法？

谢谢！

Answer 1

遗传算法几乎是“bruteforce的较小版本”。它只是一种元启发式，而不是一种具有良好收敛保证的优化方法。它基本上取决于随机性来提供新的解决方案，因此它是“稍好的随机搜索”。

所以“它会起作用吗？”是的，它会做一些事情，只要你有足够的突变随机性，它甚至会（最终）收敛到最佳状态。它会比随机搜索更好吗？很难说，这取决于许多因素，不仅是你的编码，而且所有的超参数在一般的遗传算法中都是关于试验和错误的。特别是没有丢失任何信息的染色体表示（你的没有）并不重要，这意味着一切都取决于巧妙地实现交叉和变异（只要染色体不丢失任何信息，它们都是等价的）。

Answer 2

编辑。

您可以使用置换编码GA。在置换编码中，您应该给出起点和终点。 GA通过您的健身功能搜索最佳染色体。候选解决方案（染色体）将类似于2-5-4-3-1或2-3-1-4-5或1-2-5-4-3等。因此，您的解决方案取决于您的健身功能。 （查看R的GA包以轻松应用置换GA。）

连接是您的问题的约束。我最好的建议是创建一个像这样的约束矩阵：

FirstPoint SecondPoint Connected
A          B           true
A          C           true
A          E           false
...        ...         ...

在标准TSP中，只考虑距离。在您的适应度函数中，您必须考虑此矩阵并为每个错误的返回值添加惩罚。

Example chromosome: A-B-E-D-C
A-B: 1
B-E: 1
E-D: 4
D-C: 3

Fitness value: 9

.

Example chromosome: A-E-B-C-D
A-E: penalty
E-B: 1
B-C: 6
C-D: 3

Fitness value: 10 + penalty value.

因为约束是一个硬约束，所以可以使用最大整数值作为惩罚。 GA将找到最佳解决方案。 :)