🤖 AI

Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification

本文提出了一种神经进化框架，该框架利用遗传算法来优化神经网络权重，以自动学习有效的启发式策略，当这些策略被集成到迭代式多源束搜索中时，在解决可变间隔最长公共子序列问题方面优于现有的手工设计方法。

原作者： Marko Djukanović, Christian Blum, Aleksandar Kartelj, Saso Dzeroski, Ziga Zebec

发布于 2026-08-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Marko Djukanović, Christian Blum, Aleksandar Kartelj, Saso Dzeroski, Ziga Zebec

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名侦探，正试图通过对比一叠略有破损的旧地图来破解一个谜题。每张地图都显示了大致相同的领地，但有些地图缺少道路，有些则多了额外的绕行路线，而且墨迹在不同地方都有模糊。你的任务是找到在每一张地图上都存在的“最长路径”，即使你不得不跳过那些缺失或模糊的部分。这正是计算机科学中一个著名的难题——“最长公共子序列”（Longest Common Subsequence）问题的本质。它在数字领域相当于寻找两个人的共同 DNA，或者在不同版本的歌曲中捕捉同一段旋律。

但现实生活是混乱的。有时，地图上的“缺失部分”并不只是随机的，它们遵循一定的规则。例如，只有当绕行距离较短时，才能跳过某条路；或者，必须用一条不会延伸太远的路径来替代断掉的桥梁。这增加了一层复杂性，称为“间隙约束”（gap constraints）。当你只有两张地图时，计算机处理得很好。但如果我有十张、二十张甚至一百张地图，而且规则会随着位置的变化而改变呢？突然间，这个谜题变成了传统计算机的噩梦。它们会陷入困境、感到混乱，并往往放弃寻找最优解。这正是这篇论文所探讨的科学领域：如何帮助计算机在这些充满规则且混乱的谜题中导航，而不至于迷失方向。

论文的故事：教计算机如何“感知”最佳路径

该论文的作者 Marko Djukanović 及其团队解决了一个特别棘手的谜题版本，称为可变间隙最长公共子序列问题（VGLCSP）。简单来说，想象你正试图在一堆缠绕在一起的纱线中寻找最长的一根共同线头。规则规定你可以跳过一些结（间隙），但跳过的规模取决于该处纱线的颜色和质地。如果纱线很粗，你可以跳过一个大间隙；如果纱线很细，你只能跳过一小点。

多年来，解决这个问题的最佳方法是使用一种称为**束搜索（Beam Search）**的方法。把束搜索想象成一群在浓雾森林中探索的徒步旅行者。他们不会派一名徒步旅行者去尝试每一条路径（那会耗费太长时间），而是将小组分成固定数量的队伍（即“束”）。在每一个分叉路口，他们会使用一本“手工编写”的规则手册来决定哪些路径看起来最有希望。旧的规则手册是由人类专家编写的。它还算不错，但随着森林变得越来越大、规则变得越来越复杂，徒步旅行者开始做出错误的决策，经常错过终点的宝藏。

该论文指出，这些人类编写的规则手册过于僵化。它们缺乏“鲁棒性”（robustness），这意味着当问题变得非常困难时，它们就会失效。为了解决这个问题，团队不仅改进了规则手册，还决定教计算机如何编写它自己的规则。

“神经进化”教练

作者没有让人类编写规则，而是使用了一个神经网络（一种受人类大脑启发的计算机大脑）来充当徒步旅行者的教练。但这里有一个转折：他们并没有通过向教练展示答案来教学（因为对于这些难题，目前还没有人知道标准答案），而是使用了遗传算法，这就像是数字版的进化。

想象一下有 20 个不同的教练组成的群体，每个教练都有一个略微不同的“大脑”（神经网络中不同的权重）。

测试： 每个教练都会派遣徒步旅行者进入森林（计算机使用该教练的建议运行束搜索）。
评分： 找到最长共同线头的教练会获得高分。
进化： 最优秀的教练会被配对进行“杂交”，以产生新的教练，同时混合他们的“大脑”。表现最差的教练会被淘汰。此外，还会加入一些随机的“突变体”以保持多样性。
循环： 这个过程不断重复。教练们变得越来越擅长引导徒步旅行者，不是因为他们记住了森林，而是因为他们学会了如何根据森林周围的形状来判断哪些路径“感觉”更有希望。

其结果是一个神经进化启发式算法（neuro-evolved heuristic）。这是一个不再仅仅遵循静态规则（如“总是跳过小间隙”）的指南。相反，它会观察全局情况——徒步旅行者进展到哪里了、还剩多少张地图，以及当前的规则有多大的灵活性——并做出智能且直觉性的判断，决定下一步该走哪条路。

团队协作的力量

研究人员发现，虽然 AI 教练很出色，但它并非完美。有时，旧的人类规则手册实际上表现更好，尤其是在处理较简单的谜题时。因此，他们创建了一个混合团队。他们将 AI 教练的直觉与人类规则手册的逻辑结合在一起。他们不仅仅是简单地相加分数，而是根据双方的意见对路径进行排名，并让排名最高的路径胜出。这种“集成”（ensemble）方法起到了安全网的作用，确保如果一个向导犯了错，另一个可以及时补救。

他们的发现

团队在两种类型的挑战上测试了他们的新方法：

合成森林： 具有不同地图数量（从 2 到 10 张）和不同规则复杂度的计算机生成谜题。
真实世界的森林： 基于实际生物数据（DNA 序列）的谜题，其规则源自真实分子的行为方式。

结果非常明确。在合成谜题中，新的 Limsbs-ensemble 方法在 32 个案例中的 20 个中找到了更好的解决方案，并在另外 8 个案例中持平。它仅在 4 个案例中落败。作者进行的统计检验表明，这种改进是显著的，这意味着它并非偶然。

在真实世界的生物学谜题中，新方法的表现更加令人印象深刻。它在 20 个案例中的 12 个中胜出，7 个持平，仅输掉了 1 个。论文指出，改进在那些旧方法最难应付的最复杂、最困难的谜题上最为明显。

核心结论

该论文并未声称已经永久“解决”了这个问题。这些谜题仍然很难，且解决方案仍然是近似值（最佳猜测）。然而，这项研究表明，基于学习的引导是一个强大的工具。通过让计算机进化出自己思考问题的方式，而不是强迫它遵循僵化的人类规则，我们可以用更短的时间找到更好的答案。

作者总结道，这种方法在问题变得混乱和复杂时特别有用。他们还引入了一套全新的、基于生物学的“真实世界”测试案例，希望能帮助其他研究人员测试他们自己的想法。他们暗示，未来的方向可能是教这些 AI 教练去应对更广阔的森林和更复杂的生物学奥秘。

技术摘要：用于可变间隙公共子序列识别的神经进化启发式算法

问题定义

本研究针对**可变间隙最长公共子序列问题（VGLCSP）**进行了探讨，这是经典最长公共子序列问题（LCSP）的一种组合优化变体。与标准的 LCSP 不同，VGLCSP 在连续符号之间的间隙约束上引入了灵活性。形式上，对于一组输入序列 $S = \{s_1, \dots, s_m\}$ ，间隙函数 $G_{s_i}$ 定义了结果中连续符号与其在输入序列 $s_i$ 中位置之间的最大允许距离。只有当这些约束在所有输入序列中均成立时，该子序列才被视为可行。

该问题在生物序列分析（例如具有可变结构距离的 DNA 和蛋白质对齐）以及时间序列分析领域具有应用前景。虽然两序列情况（ $m=2$ ）可以通过动态规划求解，但广义的多序列版本是 NP 难问题。目前的先进可扩展方法是迭代多源束搜索（IMSBS）。然而，IMSBS 依赖于手工设计的启发式算法，当序列数量（ $m$ ）增加或字母表大小（ $|\Sigma|$ ）减小时，其性能往往会下降，尤其是在复杂的间隙约束下。此外，现有的评估局限于合成基准测试，缺乏具有现实意义的数据驱动间隙约束。

方法论

作者提出了一种基于学习的框架，旨在自动设计数据驱动的启发式算法来引导 IMSBS 过程，而非直接构建解。其核心方法论是一种神经进化方法：

神经网络架构： 启发式算法被建模为一个全连接多层感知器（MLP）。该网络接收一个固定长度的特征向量作为输入，该向量描述了当前的搜索状态（部分解）。特征包括：
- 各序列的归一化位置向量。
- 当前子序列长度的统计数据。
- 剩余位置的间隙相关统计数据（最小值、最大值、平均值、标准差）。
- 全局参数（字母表大小 $|\Sigma|$ 和序列数量 $m$ ）。
  输出是一个估计节点对于进一步扩展之“潜力”的分数。
通过神经进化进行优化： 由于对于大规模 NP 难实例无法获得监督学习的目标值，网络权重使用**偏置随机键遗传算法（BRKGA）**进行优化。
- 适应度评估： 每个候选权重向量通过在训练集实例上运行带有诱导神经启发式的 IMSBS 来进行评估。适应度是所找到的最长公共子序列长度的平均质量。
- 训练循环： 该过程在进化优化（选择、偏置交叉、变异）与 IMSBS 内部的评估之间交替进行。为了防止过拟合，采用了使用独立验证集的早停机制。
集成启发式算法： 为了增强鲁棒性，作者引入了一种集成策略，将学习到的神经启发式算法（ $h_{w^*}$ ）与文献中表现最佳的手工设计上界启发式算法（$UB$）相结合。该方法并非通过平均原始分数，而是使用秩聚合（rank aggregation）：
- 节点分别由神经分数和手工设计分数进行独立排名。
- 最终排名分数计算为加权组合： $r(v) = \alpha \cdot r_{h_{w^*}}(v) + (1-\alpha) \cdot r_{UB}(v)$ 。
- 参数 $\alpha$ 通过网格搜索进行调优。

主要贡献

本文概述了四个主要贡献：

一个神经进化框架： 一个专门为 VGLCSP 背景设计的学习启发式引导系统，通过在迭代束搜索循环中利用遗传算法优化神经网络权重。
一种集成启发式算法： 一种结合了学习型和分析型（手工设计）引导机制的新颖组合方式，利用基于秩的聚合来减轻规模不一致性并提高搜索稳定性。
一种增强的 IMSBS 算法： 将所提出的集成启发式算法集成到最先进的 IMSBS 框架中，从而形成一种混合搜索算法。
新的基准实例： 引入了一个源自生物学动机数据集（大鼠和病毒）的“真实（Real）”基准集，并基于热力学稳定性模型增加了数据驱动的间隙约束，填补了现实评估数据的空白。

实验结果

所提出的方法 Limsbs-ensemble 在两个数据集上针对基准方法 Imsbs（仅使用手工设计启发式算法）进行了评估：

合成基准（随机）： 包含 320 个实例，其序列长度（ $n$ ）、序列数量（ $m$ ）和字母表大小（ $|\Sigma|$ ）各不相同。
- 性能： 在 32 个实例中，Limsbs-ensemble 在 20 个实例中表现优于 Imsbs，8 个实例持平，4 个实例落后。
- 统计显著性： 单侧 Wilcoxon 符号秩检验确认了显著的改进（对于小规模实例 $p < 0.01$ ，对于大规模实例 $p < 0.05$ ）。
- 观察结论： 当 $m$ 较大且 $|\Sigma|$ 较小时，改进尤为显著，而在这些情况下，手工设计启发式算法通常表现不佳。
真实世界基准（真实）： 包含来自大鼠和病毒数据集的 20 个实例， $m$ 的范围从 10 到 200。
- 性能： Limsbs-ensemble 在 20 个实例中的 12 个中取得了更好的解质量，7 个持平，1 个落后。
- 运行时间： 两种方法之间的计算成本相当，Imsbs 平均而言略快，但 Limsbs-ensemble 仍保持竞争力。
- 间隙约束： 结果强调，与无约束的 LCS 相比，间隙约束显著降低了可实现的子序列长度，尤其是在 $m$ 较大时。

重要性与主张

本文声称，所提出的混合神经进化方法相对于现有的手工设计方法，在 VGLCSP 问题上提供了持续且具有统计显著性的解质量提升。作者强调，学习型启发式算法能有效地引导搜索过程进入复杂的、高维的状态空间，而传统的启发式算法在这些空间中往往失效。

该工作的意义在于：

证明了**神经进化超启发式算法（neuro-evolutionary hyper-heuristics）**在指导 NP 难问题组合搜索中的可行性，特别是在无法进行梯度下降训练的情况下。
展示了结合学习型和分析型引导的集成方法比单一方法更具鲁棒性。
提供了现实的基准测试，带有数据驱动的间隙约束，超越了合成评估，更好地反映了生物学和时间序列分析中的挑战。

作者总结道，尽管该方法行之有效，但未来的工作应侧重于将其扩展到蛋白质序列数据集，验证生成的间隙约束在生物学背景下的有效性，并探索其他的学习策略以进一步控制过拟合并提高可扩展性。