第三名解决方案

撰写由 @asalhi 完成，由于他发帖遇到问题，故由我代发。

“排序后的停用词、排序后的动词和排序后的其他词”就是你所需的一切！

首先，我们要感谢 Kaggle 举办了这场精彩的竞赛，我们非常享受这个过程，既有趣又富有信息量。
此外，我要深深感谢我的队友们，这是一次美妙的实验 🙏

关于我们的解决方案，我们使用了模拟退火（Simulated Annealing, SA），并对候选生成进行了修改。

我们将分享两种方法（一种在样本 0 到 4 上表现最好，并在样本 5 上达到 30.x；另一种帮助我们达到了 28.5x），两种方法的示例代码也将共享。

第一种方法概述：

带有自定义加权候选生成器的模拟退火：

第一种方法的示例代码可以在这里找到：https://www.kaggle.com/code/asalhi/3rd-place-sa-weighted-candidate-generator-sol1

批量指标 (Batched Metric)：
我们使用了批量指标来加速分数计算过程。

自定义候选生成器 (Custom Candidate Generator)：
我们创建了一个具有以下功能的自定义候选生成器：

1- 我们定义了不同的操作（文本转换操作）：

operations = ["swap","reverse","removeinsert","removeinsertn","rotate","shift","swap_adjacent","circular_shift","reverse_all","scramble_except_first","block_shift","block_swap",]

2- 操作的选择不是纯随机的，我们创建了一个权重系统，根据操作产生的分数赋予其重要性。

以下是用于给候选项赋予权重的主要方法：

def compute_word_importance(self, words):
    """
    基于困惑度分数计算单词重要性。
    """
    importance_scores = {}
    for word in words:
        # 获取每个单词的困惑度
        perplexity = self.scorer.get_perplexity([word], batch_size=self.batch_size)
        importance_scores[word] = 1 / perplexity[0]  # 困惑度越高 -> 重要性越低
    self.word_importance = importance_scores

def update_weights(self, operation_scores):
    """
    根据操作性能更新操作权重。
    :param operation_scores: 映射操作及其分数的字典。
    """
    scores = operation_scores.values()
    min_score = min(scores)
    max_score = max(scores)

    # 奖励 - 惩罚机制
    for i, operation in enumerate(self.operations):
        score = operation_scores.get(operation, max_score)
        if score == min_score:
            self.operation_weights[i] *= 1.2  # 对最佳操作给予强奖励
        else:
            penalty = 0.9 + (0.1 * (score - min_score) / (max_score - min_score + 1e-6))
            self.operation_weights[i] *= penalty

    # 归一化权重以避免极端偏差
    total_weight = sum(self.operation_weights)
    if total_weight <= 0 or not math.isfinite(total_weight):
        # 如果归一化失败，重置权重为均匀分布
        self.operation_weights = [1.0] * len(self.operation_weights)
    else:
        self.operation_weights = [w / total_weight for w in self.operation_weights]

增强型模拟退火 (Enhanced Simulated Annealing)：
我们使用了具有以下增强功能的模拟退火算法：

1. 跟踪操作（文本转换操作分数），并使用该分数更新候选项的选择。
2. 考虑具有“同等最佳分数”的文本，这有助于逃脱死胡同路径。
   注意： 至少在 A100 GPU 上会发生这种情况，其中两个或多个文本可能具有相同的分数。
3. 无改进时：当没有改进发生时，我们重新选择一个文本并从它开始（基本上是一些洗牌或回到最佳文本），这是基于实验得出的。

初始文本“起点” (Initial Text"Starting Point")：
我们在开始时使用的初始文本对获得更好的分数起到了很好的作用。经过不同的实验，我们发现以下方法效果最好（样本 ID 从 0 到 5）：

1. 按字母顺序排序文本：在样本 2 上效果最好。
2. 停用词排序，然后按字母顺序排序其他单词：为样本 3 和 4 提供了良好的起点。
3. 随机起点（并行多次运行代码）：给出了更快的收敛速度，并在样本 3 上获得了更好的结果。
4. 排序后的停用词、排序后的动词、排序后的其他词：为样本 3 和 4 以及最重要的样本 5 提供了最佳起点（即使起始分数不如所有文本排序后那么低）。

第二种方法概述：

第二种方法的示例代码可以在这里找到：https://www.kaggle.com/code/siavrez/3rd-place-sa-weighted-candidate-generator-sol2

对于第二种路径，我们从一个简单的模拟退火模型开始，只交换 2 个单词，并根据不同的实验添加了不同的想法：

1. 添加更多操作：BlockMoveOperation, BlockSwapOperation, ReverseBlockOperation, ShuffleBlockOperation, CyclicShiftOperation, ShiftOneOperation, TripleMoveOperation, QuadMoveOperation, InterleaveOperation, SplitMergeOperation, PivotRotateOperation, WindowSlideOperation, CrossBridgeOperation, RotateBlockOperation, MultiSwapOperation。
2. 循环冷却 (Cyclic cooling down)。
3. 限制下一次迭代中可接受的能量范围。
4. 测试不同的起始序列策略（聚类、排序、分割排序）。我认为这对样本 5 最重要，对我们来说最好的组合是：排序后的停用词 + 排序后的动词 + 排序后的其他词。
5. 使用一次运行中的最佳序列，并将其输入到模型的另一个变体中，通过随机选择仅操作的一个子集。
6. 使用 Top-k 选择下一个文本，并随机选择一个或基于与最佳能量的距离进行加权（而不是仅考虑最佳分数）。
7. 探索 Top-k 能量并行路径，并在此基础上选择下一个最佳文本（而不是选择最佳探索路径用于所有 Top-k）。
8. 使用基于第一种方法的操作权重。