第五名解决方案 - CPMP 部分
首先，我要感谢 @horeahoreastefan。如果没有他，我不确定我能否在所有样本上找到最佳分数。当我们组队时，他在样本 3 上取得了最佳分数，而我的方法似乎如果没有他的一些输入（某些单词分组），就无法找到该分数。我的方法在其他样本上效果很好：当从原始文本单词的随机洗牌开始时，它超过一半的时间都能找到最佳分数。
我将重点描述我的局部搜索以及我尝试过但无效的一些方法。我是在阅读其他团队的 writeup 之前撰写本文的，因此可能存在一些冗余。
模拟退火变体
我使用了一种模拟退火（SA）的变体。在 SA 中，人们处理问题的一个解并对其进行迭代修改。如果修改后的解分数优于之前，则保留它。如果修改后的解分数差于之前，则只有在通过某些测试时才保留它。
大多数人使用旧分数减去新分数的指数化来决定是否保留新解。有一种更高效且同样有效的方法：如果新解的分数低于某个全局上限，则保留该新解。该上限会不时降低。
与基于指数化的 SA 一样，最佳分数在整个搜索过程中保持不变。
多点搜索
为了尽可能有效地使用 GPU，我并行运行 N 个 SA，其中 N 是使用竞争指标评估 N 个文本的最大批处理大小。例如，在使用 A100 GPU 时，我对样本 5 使用了 104 的批处理大小。
该算法类似于 SA。
从 S = {原始文本的 N 个随机洗牌} 和边界 M 开始
重复直到用户停止
S1 = 空集
对于 S 中的每个解
修改 S 并添加到 S1
在一个 GPU 批次中计算 S1 中每个文本的分数
如果这些分数中有一个优于最佳分数，则更新最佳分数和最佳文本
在 S1 中保留分数小于最佳分数加 M 的解
对于其他解，与最佳解进行交叉，并将其添加到 S1交叉操作接受两个文本作为输入，并从中生成一个新文本。
交叉的使用让人想起遗传算法（GA），但这只是使用了极少部分的 GA。我们不对 S 中的所有文本应用交叉，也不从 S1 中保留 N 个最佳分数。
该方法的目的是通过尽可能并行运行它们来保持优化路径的多样性。GA 倾向于关注到目前为止最佳解周围的空间子集。
移动操作 (Moves)
使用了三种解修改器，均受 ATSP 方法启发。我们处理单词序列（python 列表），仅在计算分数时构建文本。
k-opt 单词序列被分割成 k 个段。这些段被洗牌并连接以产生新的单词序列。k 的选择是随机的，最大值为某个值（例如 10）。我们使用此方法的一些变体，例如固定某些段并置换其他段。这概括了单词子集的置换。
移除 - 插入 (remove - insert) 单词序列的一个子集被移除，然后移除的单词被重新插入。一个变体使用随机插入。另一个变体尝试每个可能的插入位置并选择最佳位置。在如何选择移除的单词方面也有变体。它可以是大小为 k 的随机子集，或者是长度为 k 的子序列。后者似乎更有效。如前所述，k 是随机选择的，直到某个最大值。
双根与茎 (double root and stem)。这来自一篇 关于 ATSP 启发式算法的论文。
在这里解释该方法太长了，最好阅读论文。让我只是说， Instead of working with a word sequence, a more complex graph structure is used, with either two cycles and a path between them, or 3 paths with same end points. (不使用单词序列，而是使用更复杂的图结构，要么是两个循环及其之间的一条路径，要么是 3 条具有相同端点的路径。) 该结构通过特定移动进行修改，然后转换回序列。为了在这里给它一个味道，这里是结构如何转换为序列的：
加速优化
瓶颈在于 GPU 使用。我们的代码非常有效地使用了 GPU，平均使用率为 98%。加速的主要方法是使用文本分数的全局缓存。它是一个 python 字典，键是文本，值是文本分数。
我们没有太多优化解移动操作的实现，因为那里花费的时间并不相关。我们更愿意确保代码易于修改。
折扣困惑度 (Discounted perplexity)
过了一会儿，很明显，修改单词序列靠近开头的部分比修改靠近结尾的部分对分数的影响要大得多。结果，局部搜索很快集中在序列的末尾，而让开头保持固定。
@horeahoreastefan 想到了将移动限制在某些前缀的想法，这迫使局部搜索探索靠近开头的移动。这在竞赛期间使我们在样本 5 上更接近最佳分数。
我探索了另一种方法。除了使用竞争指标计算分数外，我还维护每个 token 位置的 logit 值的平均值。然后，对于每个文本，我首先将其 logit 除以该位置的平均 logit 值，然后取均值并指数化，从而计算折扣分数。这样，分数修改的幅度在所有位置上都被归一化了。折扣分数用于决定是否应保留修改后的文本。这样，序列开头附近的修改变得与序列结尾附近的修改一样可能。
这就 concluded 了我所使用方法的描述。
无效的方法
我尝试了类似于 @simjeg 分享的想法。正如 Simon 的方法一样，我使用置换矩阵作为模型的第一层。我使用了每个位置的下一个 token 的 logits，限制为文本中出现的 token。这给了我一个方阵。然后我对它应用 Sinkhorn 算法。然后计算 Sinkhorn logit 矩阵和输入置换矩阵之间的 KL 散度，并反向传播以更新置换矩阵。
这在某种程度上有效，但远不如局部搜索的结果。
在另一个变体中，我使用 logit 矩阵作为成本计算 ATSP 解。然后，结果解被用作下一个文本输入。这是迭代的。
它根本不起作用。
然后我在 Sinkhorn 之前使用了下一个 token logits 的指数移动平均线，希望值会收敛到导致最优 ATSP 的东西。它工作得更好，但不如上面描述的局部搜索好。
我探索的第三个想法是训练一个模型来预测好的序列。我使用了带有强化学习（RL）的蒙特卡洛树搜索（MCTS）。它也没有起作用。也许我应该坚持一下，但局部搜索已经足够好了。