第一名解决方案及路径可视化

2023/01/19 更新：添加了最优（？）路径的可视化路线图。
2023/01/23 更新：公开了我们的 GitHub 仓库。

我们（ @kibuna 和 @cnumber）感谢主办方举办这一年度优化挑战赛，并提供了非常有趣的问题。

概述

这个问题主要可以分为两个步骤。首先是在图像上获取具有颜色成本和最小重置成本的最小成本路径（定义在此），其次是构建具有最小额外成本的有效机械臂配置。我们通过使用“使用边组装交叉的遗传算法（GA-EAX）”解决带有附加约束的 TSP 问题来处理前一部分，对于后一部分，则使用了束搜索。

两个重要的点是：

1. 由于机械臂配置的原因，存在不可能（或成本极高）的路线，在解决 TSP 时需要将其排除。
2. 一旦获得了合理的路径，即使存在复杂的移动（例如连续的长步进），获得机械臂配置也相对容易，因为有大量的机械臂组合可以恢复到相同的位置。

具有路径依赖约束的 TSP：

解决此问题的基本方法是搜索从点 (0, 0) 出发，遍历图像所有像素，并返回点 (0, 0) 的最小成本路径。这听起来像是一个标准的 TSP，但机械臂的约束限制了可能的路线。我们通过添加路径依赖成本将这些约束纳入标准 TSP 中；当违反以下每个约束时，增加额外的成本。

1. 在 y 轴方向移动大于或等于 64 步之前，不要进入 \(x < 0\) 区域。
   • 这是因为需要将 64-臂旋转至少 64 次才能进入 \(x < 0\) 区域。
2. \( 2 \times x < \) y 轴方向总移动距离
   • 这是因为需要旋转 32、16……1-臂。
3. 不要用直线连接 (-127, -127)、(-127, 127)、(127, -127)、(127, 127) 中的任意两点。
   • 可以确认的是，除非增加额外的重置成本，否则不存在有效的机械臂配置。
4. 当机械臂从 (1, -4) 移动到 (0, -4) 或从 (1, -5) 移动到 (0, -5)，然后经过图像的第 4、3、2 和第 1 象限时，机械臂在进入第 1 象限之前必须在 y 正方向移动超过 128 次。
   • 我们真正想做的是检查当机械臂穿过象限时是否有足够的移动来旋转 64-臂。然而，这大大增加了计算成本。我们在研究了由条件 1、2 和 3 生成的典型路径后，提取了上述条件。最终，这 4 个条件足以排除不理想的路径。

上述所有约束都具有路径依赖性，因此将它们纳入局部搜索算法的成本函数中非常耗时，因为每次生成新的候选路径时都需要检查这些约束，这也是我们选择遗传算法（GA）的原因之一。在实现方面，我们没有排除所有违反约束的路径，而是在违反条件时施加惩罚成本，以便随着 GA 的进行，种群中违反约束的路径数量逐渐减少。

我们还利用可视化工具（见附录 1）来考虑这些限制。

GA-EAX-restart

GA-EAX 被用于搜索最小成本路径。该实现基于 GA-EAX-restart 并进行了一些修改。代码可在此处 [chettub/santa2022] 获取。

GA-EAX 是一种基于 GA 的 TSP 近似算法，使用一种称为边组装交叉（EAX）的快速高效交叉算子，已知该算法已更新了许多 TSP 实例的已知最佳解决方案，特别是对于

同比赛其他方案