382 讀數

揭示学习本地搜索启发式方法的局限性：你是最强大的吗？

经过 Aiding in the focused exploration of potential solutions.4m2024/04/12

太長; 讀書

本摘要概述了在评估组合优化的神经网络-局部搜索启发式混合算法时遇到的挑战。它讨论了算法性能评估的局限性、通用性以及实例选择偏差的影响，并提出了挑战该领域普遍假设的见解。

featured image - 揭示学习本地搜索启发式方法的局限性：你是最强大的吗？

‘neural networks’ Image created by HackerNoon AI Image Generator

作者：

（1） Ankur Nath，德克萨斯 A&M 大学计算机科学与工程系；

（2）艾伦·库恩勒（Alan Kuhnle），德克萨斯 A&M 大学计算机科学与工程系。

链接表

摘要与引言

抽象的

近年来，将神经网络与局部搜索启发式相结合已成为组合优化领域的流行趋势。尽管这种方法需要大量的计算，但它已经显示出了令人鼓舞的结果，并且手动工程量极小。然而，我们在对这些集成尝试进行实证评估时发现了三个关键的局限性。首先，中等复杂度和弱基线的实例对准确评估基于学习的方法的有效性构成了挑战。其次，由于缺乏消融研究，很难量化改进并将其准确归因于深度学习架构。最后，学习启发式在不同分布中的泛化仍未得到充分探索。在本研究中，我们对这些已发现的局限性进行了全面调查。令人惊讶的是，我们证明了基于禁忌搜索的简单学习启发式在性能和泛化方面超越了最先进的 (SOTA) 学习启发式。我们的研究结果挑战了普遍的假设，并为组合优化的未来研究和创新开辟了令人兴奋的途径。

1 引言

为 NP 难组合优化 (CO) 问题设计有效的启发式或近似算法是一项具有挑战性的任务，通常需要领域知识和大量的反复试验。因此，通过机器学习来学习利用问题固有结构的算法，从而自动化这一要求高且繁琐的设计过程的想法引起了研究人员的极大兴趣 (Bello 等人，2016 年；Khalil 等人，2017 年；Bengio 等人，2021 年；Dong 等人，2021 年)。特别是，这些工作中的相当一部分 (Khalil 等人，2017 年；Barrett 等人，2020 年；Yolcu 和 P'oczos，2019 年) 集中在使用图神经网络 (GNN) 解决 CO 问题。尽管计算需求很大，但这些基于 GNN 的方法与针对特定问题量身定制的 SOTA 启发式方法相比表现出了竞争力。

虽然这些潜在的进步带来了巨大的希望，但仍然存在一些问题。学习启发式方法的卓越性能可以归因于特定实例和基线的选择。具体来说，如果基线较弱，学习启发式方法很容易胜过它们。如果没有困难实例和适当的基线选择，学习启发式方法很容易表现出与 SOTA 启发式方法相当的性能，这可能导致对学习启发式方法的实际能力的估计过高。此外，由于深度学习架构的可扩展性挑战，与 SOTA 启发式方法的比较有时会被忽略。

基于学习的方法子集（Khalil 等人，2017 年；Yolcu 和 P'oczos，2019 年；Barrett 等人，2020 年，2022 年）结合了传统启发式方法的功能或行为，通过将启发式原理与机器学习组件相结合，有可能提供改进或增强的性能。如果缺乏与集成启发式方法的全面比较和对深度学习架构的消融研究，则很难确定深度学习架构的具体贡献。因此，如果集成启发式方法稳健，则学习到的启发式方法可以无缝地超越基线启发式方法，而深度学习架构则起着很小的作用。

学习启发式方法的另一项重大成就（Khalil 等人，2017 年；Barrett 等人，2020 年；Toenshof 等人，2019 年）最初在特定分布的较小和特定实例上进行训练，在对来自不同分布的较大实例进行测试时表现出令人印象深刻的性能。这一成就是一项重大成就，符合采用基于学习的方法的核心目标：减轻启发式方法通常需要的大量定制和领域特定知识的必要性。虽然具有超参数的经典启发式方法如果针对特定分布进行微调也可能会遇到挑战，但它们也可以在不同的分布中推广。主要研究围绕学习启发式方法是否确实比经典启发式方法表现出更好的通用性。对学习启发式方法与经典启发式方法进行全面而有见地的比较，可以为学习启发式方法的通用性提供宝贵的见解。

学习启发式方法通常缺乏理论保证，因此实证评估是理解所提出方法的优势和局限性的唯一方法。我们认为，在对这些作品进行实证评估时，仍有几个基本但关键的问题尚未探索。虽然这些问题与所有类型的学习启发式方法都有关，但我们通过分析被高度引用和最近同行评审的专注于学习本地搜索启发式方法的出版物来提出和回答这些问题。我们的目标不是为我们的工作中讨论的 CO 问题提供详尽的基准，而是帮助未来的研究人员评估他们的研究。

具体来说，我们提出并回答以下问题：

1. 学习到的启发式方法是否会过度参数化？当然。我们用线性回归替换 ECO-DQN 中的 GNN，并利用 ECO-DQN（Barrett 等人，2020 年）中与禁忌搜索（Glover，1990 年）相关的特征子集，引入了 ECO-DQN 的修剪版本，称为 SoftTabu。我们的研究表明，与 ECO-DQN 相比，SoftTabu 在 NPhard 最大切割（Max-Cut）问题上表现出卓越的性能和通用性。

2. 基线偏差是否可以归因于学习启发式方法的卓越性能？是的，我们证明了 SoftTabu（一种原始学习启发式方法）在 Max-Cut 问题上的表现优于 S2V-DQN（Khalil 等人，2017 年），在布尔可满足性 (SAT) 问题上的表现优于 GNNSAT（Yolcu 和 P´oczos，2019 年）。

*3. 由于实例选择偏差，学习到的启发式方法能否表现出优越的泛化能力？*是的，我们证明了 ECO-DQN 在较难的实例上表现出较差的泛化能力，并且很容易陷入搜索空间。