第 13 名解题报告

首先，感谢组织者每年创建如此有趣的问题。特别是今年，同样的分数恰好是金牌的分数线。我认为这是一个难度恰到好处的问题。（虽然我们可能没有拿到金牌 :D）
感谢所有参与比赛的选手。公开的讨论和代码非常有启发性，也很公平。
感谢我所有的队友。我们是来自日本电气通信大学的一个团队。hoxosh( @cashfeg ) 和 yukari17( @yukari17 ) 是教职员，Prgckwb( @prgckwb ) 是硕士研究生，kumanomi( @kkkggg ) 是数据科学扩展项目的校友。

Santa Master 是我经常使用的名字，但今年被占用了，所以我决定称自己为 本家 Santa Master（本家在日语中意为extended family 中的本家/主家）。

概述

我们，尤其是我 (hoxosh)，尝试了很多方法，我们一起改进了那些有效的方法。Prgckwb 管理 GPU 资源，我们在 WandB 上检查进度。最后，kumanomi 的模拟退火 (SA)、prgckwb 的遗传算法 (GA) 和 yukari17 的带扰动的局部搜索变体 (Sano 武器) 效果很好。
虽然花了很长时间，但我们能够在 ID 0, 1, 2, 4 上获得与发布的最高分数相同的分数，但我们在 ID 3 和 5 上卡住了。
对于 ID3，经过多次尝试跳出局部最优后，我们想到了固定第一个单词的主意，我们使用 SA 固定第一个单词为 magi 得到了 195 分，并且我们能够使用 GA 得到 191.73 分 (1/23)。
至于 ID5，我们卡在 32 分很长一段时间（直到 1/29）。即使在阅读了意外发布的代码后，我们也不能立即理解它。直到我们试用该代码一天并得到 31.5 分后，我们才终于理解了它（截止日期前 49.5 小时）。从那里开始，Sano 武器迅速提高了分数，然后 SA 和 GA converge 在几小时内达到了 246.82532。在那里又卡了半天之后，并被一个团队超越，SA 做出了最后的修饰（截止日期前 25.5 小时）。

模拟退火

(kumanomi 部分)

• 模拟退火基础：开发了一种减少陷入局部最优可能性的方法， specifically targeting 针对 ID3 问题的 197.5 局部最优。

• 初始设置：

  • 基础参数：
    • 初始温度：10
    • 终止温度：0.5, 0.1
    • 冷却类型：指数
    • 总步数：100,000
  • 邻域操作：
    • 通用：word_insert, words_swap, words_swap_3 等。
    • 借鉴 TSP：2-opt, 3-opt, Or-opt 等。

• 性能与策略 (ID3)：

  • 达到了 197.5 的初始分数，但达到 195 分花费了大量时间。
  • 实施了截止策略：如果在 60,000 步内分数未达到 220，则重启进程。
  • 强调快速退火和高数量的试验以改善结果。
  • 每次试验在首选机器上持续约 30 分钟。

• 结果：成功达到 195 分，并将任务传递给 @Prgckwb 进行进一步开发。

遗传算法

( @Prgckwb 部分)
我通过使用遗传算法contributed to 后期改进，在 id=3 实现了 195.0→191.7，在 id=5 实现了 28.8→28.5。该算法遵循以下原则：

• 使用多个不同的现有局部解作为初始个体
• 通过双亲交叉创建子代文本，如下图所示
• 通过重新排列文本进行变异，类似于 Kumanomi ( @kkkggg ) 的 SA
• 如果设定迭代次数后无改进则切换到 SA
  

带扰动的迭代局部搜索

( @yukari17 部分)
主要帮助将分数从 31.5 提高到 28.8 (id=5)。

1. 局部搜索
   • 将句子分为 3 部分并重排 (所有模式): O(N^2)
   • 交换单词
   • 相邻两个交换 (所有模式): O(N)
   • 间隔 n 交换：O(N)
   • 单词插入 (所有模式): O(N^2)
     允许分数恶化差异 X 的搜索，而不是转移概率 (接受概率)。
     X 逐渐降低 (它在低温下彻底降低)。
     目的是逃离局部解
2. Sano 武器 Kick ("Sano"是 yukari17 的名字)
   武器不会破坏太多，但会破坏一定程度
   实际上，它是在头部和尾部执行的
   
   3. 相同分数不通过两次
   过去通过的分数从候选邻域中排除