Santa 2024 - 困惑度排列谜题

特别感谢组织者举办 Santa 优化竞赛，感谢我的队友 @solverworld 和 @zaburo。他们将发布他们自己的解决方案。

概述

我们的解决方案都归结为两个步骤：

1. 定义解决方案周围的排列局部邻域，以搜索更低的困惑度
2. 确定一种方法，在没有更好的探索方向时跳出局部最小值。

问题 ID 0 是通过暴力搜索找到的并且是公开已知的，所以我不会再进一步讨论。

搜索的局部邻域

这因问题而异，但我使用了三个邻域：

(1) 删除一个单词并将其插入到另一个位置。这是一个受限的 3-opt，对我们发现的困惑度影响最小，因为它保留了单词的大部分相对位置。

驯鹿 槲寄生 精灵 *斯克鲁奇* 姜饼 家庭 降临节 烟囱 壁炉 装饰品

变为

驯鹿 槲寄生 精灵 姜饼 家庭 降临节 *斯克鲁奇* 烟囱 壁炉 装饰品

(2) 删除一个短语（多个相邻的单词）并将其插入到另一个位置。这涵盖了除反转片段外的所有 3-opt。

驯鹿 槲寄生 精灵 *降临节 斯克鲁奇* 姜饼 家庭 烟囱 壁炉 装饰品

变为

驯鹿 槲寄生 精灵 姜饼 家庭 *降临节 斯克鲁奇* 烟囱 壁炉 装饰品

(3) 交换两个短语。这在 TSP 文献中被称为双桥跳出（double-bridge kick）。

驯鹿 *降临节 斯克鲁奇* 槲寄生 精灵 *姜饼 家庭* 烟囱 壁炉 装饰品

变为

驯鹿 *姜饼 家庭* 槲寄生 精灵 *降临节 斯克鲁奇* 烟囱 壁炉 装饰品

我们没有包含其中一个片段的反转，因为这会对困惑度产生巨大变化。

对于问题 1、2 和 3，在 RTX A6000 上运行，我们能够使用邻域 3 作为局部搜索空间。对于问题 4，我们主要使用邻域 2，偶尔使用邻域 3，对于问题 5，主要使用邻域 1，偶尔使用邻域 2。

跳出操作 (Kick operations)

如果我们搜索了一段时间并找到了局部最小值，我们会打乱解决方案的某些部分并重新开始搜索。对于这些，@zaburo 拥有最好的跳出操作，但对于问题 1、2 和 4 的解决方案，要么应用子集单词的小规模打乱，将一些单词从解决方案的前面移到后面，或使用我们的局部邻域进行几次排列操作并重试，就足够了。

完整算法

这是我使用的算法，@solverworld 有一个更系统化的算法。

1. 给定一个初始解决方案，搜索局部定义的邻域以寻找更好的解决方案。
   1. 如果找到，设置新解决方案，将局部搜索邻域和分数添加到历史列表，并重复
   2. 如果未找到，将解决方案添加到局部最小值集合，跳回搜索历史中的随机步数，选择一个不在局部最小值集合中的好解决方案，并重复。
2. 如果一段时间后未找到解决方案，应用跳出操作。

这具有缓慢逆转路径上升到局部最小值并寻找新的下降方向的效果。如果我们发现当前的搜索盆地非常大，那么我们尝试应用跳出来寻找新的搜索盆地。

例如，参见 santabasinclimberv7-final

问题 3 和问题 5 的细节

对于问题 3 和 5，找到的最小值位于非常大的空间中，即使有跳出操作，我们也很难找到更好的方法来搜索空间。因此，使用了一些额外的方法来生成起始点。

问题 3

对于问题 3，@zaburo 想到固定最后一个单词并生成最小值。这似乎覆盖了空间，允许我们从 197.5 的最小值跳到 191.5 的最小值。

问题 5

我们花了很多时间在从 (停用词) (排序后的剩余单词) 开始的解决方案上，但卡在 32.5 很长时间。随后我们意识到问题 5 是由问题 1、3 和 4 的单词组成的，因此开始基于这些问题解决方案的组合生成起始解决方案。这允许我们跳出这个最小值。最后，@zaburo 实现了一个基于我们局部最小值的自定义跳出，将我们带到了 28.5 的解决方案。

对我们无效的方法

1. 模拟退火或其稳健的变体，延迟接受爬山法。看来它们在跳出盆地和采样更大搜索空间方面不够系统化。
2. 尝试将问题分解为短语并对这些短语进行暴力搜索，或固定一些短语并应用我们类似 TSP 的方法。
3. 分支定界。它在消除部分搜索空间方面不够好，因此不允许搜索适当收敛。
4. 使用随机排列的多臂老虎机类型解决方案。