QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution

📄 arXiv: 2412.20694v4 📥 PDF

作者: Zijie Chen, Zhanchao Zhou, Yu Lu, Renjun Xu, Lili Pan, Zhenzhong Lan

分类: cs.NE, cs.AI, cs.CL

发布日期: 2024-12-30 (更新: 2025-02-21)

🔗 代码/项目: GITHUB

💡 一句话要点

QUBE：通过质量-不确定性平衡进化增强自动启发式设计

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 启发式设计 进化算法 大型语言模型 质量-不确定性权衡 NP-hard问题

📋 核心要点

  1. 现有方法在利用LLM进行启发式设计时，难以平衡探索和利用，导致搜索效率降低。
  2. QUBE提出质量-不确定性权衡标准（QUTC），指导进化过程，从而更好地平衡探索和利用。
  3. 实验表明，QUBE在NP完全问题上显著优于FunSearch等基线方法，提升了启发式设计的性能。

📝 摘要（中文）

解决NP-hard问题传统上依赖于启发式算法，但为复杂问题手动设计有效的启发式算法仍然是一个重大挑战。最近像FunSearch这样的进展表明，大型语言模型（LLMs）可以集成到进化算法（EAs）中用于启发式设计，但它们在平衡利用和探索方面的潜力受到限制。我们介绍了一种新颖的方法，即质量-不确定性平衡进化（QUBE），通过重新定义FunSearch框架内的优先级标准来增强LLM+EA方法。QUBE采用基于我们提出的不确定性包含质量度量的质量-不确定性权衡标准（QUTC）来评估和指导进化过程。通过对具有挑战性的NP完全问题进行的大量实验，QUBE证明了相对于FunSearch和基线方法的显著性能改进。我们的代码可在https://github.com/zzjchen/QUBE_code获得。

🔬 方法详解

问题定义：论文旨在解决使用大型语言模型（LLM）和进化算法（EA）自动设计启发式算法时，探索和利用之间的平衡问题。现有方法，如FunSearch，在复杂问题上难以有效地探索搜索空间，导致生成的启发式算法质量不高。痛点在于如何更有效地利用LLM的生成能力，同时避免陷入局部最优解。

核心思路：QUBE的核心思路是引入“质量-不确定性权衡标准”（QUTC），该标准不仅考虑了启发式算法的质量（例如，在问题上的性能），还考虑了其不确定性（例如，对不同输入的鲁棒性）。通过优先选择具有较高质量和较高不确定性的启发式算法，QUBE鼓励探索更广阔的搜索空间，并避免过早收敛。

技术框架：QUBE沿用了FunSearch的整体框架，包括一个LLM生成代码片段的模块和一个评估这些代码片段性能的模块。关键区别在于QUBE修改了FunSearch的优先级队列，使用QUTC来决定哪些代码片段应该被保留并用于后续的进化。具体流程如下：1) LLM生成新的代码片段；2) 使用提出的不确定性包含质量度量评估代码片段；3) 根据QUTC选择优秀的片段加入代码库；4) LLM基于代码库中的片段进行变异，生成新的片段，重复上述过程。

关键创新：QUBE最重要的技术创新点在于提出了“不确定性包含质量”度量和“质量-不确定性权衡标准”（QUTC）。与传统的只关注质量的评估方法不同，QUBE同时考虑了质量和不确定性，从而更好地平衡了探索和利用。这种方法鼓励算法探索那些可能具有更高潜力，但当前性能不确定的启发式算法。

关键设计：QUBE的关键设计在于如何定义和计算启发式算法的不确定性。论文提出了一种基于多个样本的方差来估计不确定性的方法。具体来说，对于每个启发式算法，QUBE会使用一组不同的输入样本来评估其性能，并计算这些性能值的方差。方差越大，表示该启发式算法的不确定性越高。QUTC则是一个加权平均，将质量和不确定性结合起来，用于排序和选择代码片段。权重的具体数值需要根据具体问题进行调整。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，QUBE在解决NP完全问题（如最大割问题和集合覆盖问题）时，显著优于FunSearch和其他基线方法。例如，在最大割问题上，QUBE找到的解的质量平均提高了5%以上。此外，QUBE还能够更快地找到高质量的解，表明其在探索搜索空间方面的效率更高。

🎯 应用场景

QUBE具有广泛的应用前景，可用于自动设计解决各种NP-hard问题的启发式算法，例如旅行商问题、车辆路径问题、调度问题等。该方法可以降低启发式算法设计的门槛，使非专家也能为特定问题定制高效的解决方案。此外，QUBE还可以应用于其他需要平衡探索和利用的优化问题，例如强化学习和超参数优化。

📄 摘要（原文）

Solving NP-hard problems traditionally relies on heuristics, yet manually designing effective heuristics for complex problems remains a significant challenge. While recent advancements like FunSearch have shown that large language models (LLMs) can be integrated into evolutionary algorithms (EAs) for heuristic design, their potential is hindered by limitations in balancing exploitation and exploration. We introduce Quality-Uncertainty Balanced Evolution (QUBE), a novel approach that enhances LLM+EA methods by redefining the priority criterion within the FunSearch framework. QUBE employs the Quality-Uncertainty Trade-off Criterion (QUTC), based on our proposed Uncertainty-Inclusive Quality metric, to evaluate and guide the evolutionary process. Through extensive experiments on challenging NP-complete problems, QUBE demonstrates significant performance improvements over FunSearch and baseline methods. Our code are available at https://github.com/zzjchen/QUBE_code.