第 11 名解决方案

引言

感谢组织者举办了如此激动人心的比赛。我也想向其他参与者表达谢意。在比赛的最后阶段，大家一起争夺金牌的过程非常刺激，也是一段愉快的经历。我从 Notebooks 和讨论区中学到了很多，这对取得这个结果有很大的帮助。非常感谢。

总结

我的改进始于一个公开分享的提交文件，其得分为 250.10105，分享于此笔记本。因此，ID=0,1,2 已经在排行榜上达到了最优解，我只需要处理 ID=3,4,5。这让我能够节省计算资源用于探索。感谢 @veniaminnelin 分享了这个笔记本。我也想对这个笔记本所引用的笔记本作者表示感谢。

我所有的解决方案完全依赖于模拟退火（Simulated Annealing），而如何生成邻域解是一个关键因素。我将在下面详细描述。

生成邻域解

由于使用“交换（swap）”会相对破坏原始解，因此选择“插入（insert）”作为生成邻域解的方法是改进的起点。
我使用的方法如下：

1. 随机插入 (random insert)

• 随机选择 i 和 j (0 ≤ i, j < len(words))，然后将位置 i 的单词插入到位置 j。
• 用于 ID-3, 5。

2. 基于距离的概率插入 (distance-based probabilistic insert)

• 随机选择 i (0 ≤ i < len(words))。然后，基于与 i 的距离，概率性地选择 j 作为插入位置，并将位置 i 的单词插入到位置 j。
• 公式：
d_j = |i - j|,   p(j) = (1/d_j) / ∑_j(1/d_j)
• 用于 ID-4, 5。

3. 变长随机插入 (variable-length random insert)

• 一种将随机插入修改为变长方法的方法。
• 长度值根据以下概率分布确定：
  • p(L=1) = 0.4, p(L=2) = 0.3, p(L=3) = 0.2, p(L=4) = 0.1
• 用于 ID-5。

4. 字母顺序插入 (alphabetical insert)

• 随机选择 i (0 ≤ i < len(words))。然后，从首字母与单词 i 相同的单词组中随机选择一个，并将单词 i 插入到所选单词之前或之后。
• 用于 ID-5。

5. 部分排列 (partial permutation)

• 随机选择 i (0 ≤ i < len(words) - L + 1)，并将起始于 i 的长度 L(=4) 的单词序列进行排列作为邻域解。
• 用于 ID-5。

细节

ID-3

• 对于 ID-3，我没有使用公开笔记本中的解作为初始解，而是从随机顺序初始化的序列开始。
• 通过使用上述的随机插入方法，经过几次运行后，我达到了 197.5 的分数。
• 然而，正如讨论区所指出的，这是一个已知的局部最优解，很难跳出。
• 为了跳出局部最优，我尝试固定第一个单词并应用随机插入。通过将"magi"作为第一个单词，我成功跳出了局部最优，达到了 191.7 分。
• 参数：
  • 每次运行迭代次数 (n_iterations)：100,000
  • 冷却计划 (Cooling Schedule)：线性递减 (Linear Decrease)
  • 初始温度 (start_temp)：10
  • 结束温度 (end_temp)：0.1
  • 批大小 (batch_size)：8, 16, 32

ID-4

• 在这三个 ID 中，ID-4 相对容易。通过使用公开笔记本分享的解作为初始解，并应用基于距离的概率插入，我能够在一次运行中达到 67.54 分。
• 参数：
  • 每次运行迭代次数 (n_iterations)：100,000
  • 冷却计划 (Cooling Schedule)：线性递减 (Linear Decrease)
  • 初始温度 (start_temp)：2
  • 结束温度 (end_temp)：0.1
  • 批大小 (batch_size)：32

ID-5

• 与 ID-4 一样，我使用公开笔记本中的解作为初始解，并尝试基于距离的概率插入，将分数提高到了 31.66。
• 接下来，使用 31.66 的解作为初始解，我运行了几次搜索，结合了随机插入、基于距离的概率插入、字母顺序插入和部分排列，最终将分数提高到了 30.70。
• 在检查此时的解时，我观察到有三个按字母顺序排列的块。因此，我修改了初始解（源自当时的最佳解），使这些块的数量 ranging 从一到四，然后执行与之前相同的搜索。结果发现，拥有两个块时性能最佳，将分数提高到了 28.57。
• 最后，我将随机插入改为变长随机插入。在 28.57 的解中，我注意到一些不符合字母顺序的序列（例如"card game"和"wrapping paper"）。我认为如果最优解中存在由三个或更多单词组成的单个语义单元，仅靠随机插入将无法处理它们。通过这一更改，我能够达到 28.52 分。（事实上，似乎停用词部分中的"and and and"需要放在块之间。）
• 参数：
  • 每次运行迭代次数 (n_iterations)：50,000~100,000
  • 冷却计划 (Cooling Schedule)：线性递减 (Linear Decrease)
  • 初始温度 (start_temp)：0.1~1
  • 结束温度 (end_temp)：0.01~0.1
  • 批大小 (batch_size)：16, 24

计算资源

• 在达到排行榜最优解之前，我在云端租用了 A100 显卡 10 天。
• 前五天，我使用了一张 A100；后五天，一旦开始有改进，我使用了 3 张 A100 (A100×3)。