第 9 名解决方案
我真诚地感谢组织者策划了如此有趣的比赛。
我使用了基于边组装交叉的遗传算法 (GA-EAX) 来搜索所有六个测试用例的解决方案。
（对于 ID=0,1,2，最终解决方案是通过最初测试的 SA（模拟退火）达成的）
GA 流程概述
- 使用模拟退火 (SA) 创建第一代
- 使用边组装交叉 (EAX) 生成子代
- 对子代应用局部搜索和 SA，生成具有低困惑度的个体（培育后的子代）
- 从父代个体和培育后的子代中选择下一代
- 重复步骤 2-4
初始个体与邻域操作
- 直到 ID=3，使用随机初始个体，并使用随机 3-opt 进行邻域搜索。
- 对于 ID=4，使用句首为停用词的个体（[停用词] - [非停用词]），并使用随机 3-opt 进行邻域搜索。
- 对于 ID=5，停用词放在第一个块，其他词随机分为两组，排序后放在第二和第三个块。此类句子用作初始个体（[停用词] - [非停用词] - [非停用词]）。对于邻域操作，优先处理在保持字母顺序的同时在组之间移动单词的操作。
- 在 EAX 中，允许打破组的交叉操作。
使用 EAX 生成与选择子代
- 参考 [1]，应用了ATSP（非对称旅行商问题）的 GA-EAX 方法。
- 对于 AB 循环的选择，应用了参考 [1] 中的 "EAX-1AB"。
- 对于排列的重建，使用 Gemma 模型输出的父代个体的 logits 来选择边，以估计降低困惑度。
- 由于句子的困惑度是根据 logits 计算的，通过保留句子中单词的 logits，可以大致估计当不同单词放置在某个单词旁边时的困惑度。
- 对于选择，参考 [1] 中的 "SEL1"，将父代个体与接近父代的子代进行比较，如果子代个体优于父代个体，则进行替换。
- 我添加了一些其他小的改进。
- 在选择过程中评估分数时，我们对彼此相似的个体施加惩罚，以保持多样性。
- 曾经被淘汰的个体根据其分数再次被用作父代。
- 我尝试了其他交叉方法，但几乎只有 EAX 有效。
讨论
- 使用语言模型可输出的 logits 的 GA-EAX 在搜索解决方案方面非常有效。
- 参考 [1] 中提出的方法似乎在维持和优化种群多样性方面有效。