HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs

📄 arXiv: 2412.14995v1 📥 PDF

作者: Pham Vu Tuan Dat, Long Doan, Huynh Thi Thanh Binh

分类: cs.NE, cs.AI

发布日期: 2024-12-19

备注: 18 pages, 12 figures

💡 一句话要点

HSEvo：利用多样性驱动的和谐搜索与遗传算法提升基于LLM的自动启发式设计

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

关键词: 自动启发式设计 大型语言模型 进化程序搜索 和谐搜索算法 多样性测量 探索与利用 组合优化

📋 核心要点

  1. 现有基于LLM的进化程序搜索（LLM-EPS）方法在探索和利用的平衡上存在不足，影响了启发式搜索的效率。
  2. HSEvo通过结合多样性测量指标和和谐搜索算法，自适应地平衡探索和利用，从而优化启发式搜索。
  3. 实验结果表明，HSEvo在保持成本效益的同时，实现了高多样性指标和良好的目标分数，验证了其有效性。

📝 摘要（中文）

自动启发式设计（AHD）是一个活跃的研究领域，因为它在解决现实世界中复杂的搜索和NP-hard组合优化问题中具有实用性。大型语言模型（LLM）的最新进展通过将LLM与进化计算相结合来自动生成启发式算法，从而引入了新的可能性，这被称为基于LLM的进化程序搜索（LLM-EPS）。虽然之前的LLM-EPS研究在各种任务上取得了很好的性能，但在理解启发式搜索空间的属性以及实现探索和利用之间的平衡方面仍然存在差距，这在大规模启发式搜索空间中是一个关键因素。在本研究中，我们通过提出两个多样性测量指标，并对之前的LLM-EPS方法（包括FunSearch、EoH和ReEvo）进行分析来解决这一差距。在黑盒AHD问题上的结果表明，虽然EoH表现出比FunSearch和ReEvo更高的多样性，但其目标分数不稳定。相反，ReEvo的反射机制产生了良好的目标分数，但未能有效地优化多样性。考虑到这一发现，我们引入了HSEvo，一个自适应的LLM-EPS框架，它通过和谐搜索算法保持多样性和收敛性之间的平衡。通过实验，我们发现HSEvo实现了高多样性指标和良好的目标分数，同时保持了成本效益。这些结果强调了在LLM-EPS中设计框架时，平衡探索和利用以及理解启发式搜索空间的重要性。

🔬 方法详解

问题定义：论文旨在解决自动启发式设计（AHD）中，基于LLM的进化程序搜索（LLM-EPS）方法在探索和利用之间难以平衡的问题。现有方法，如FunSearch、EoH和ReEvo，要么多样性不足，要么目标分数不稳定，无法有效优化启发式搜索空间。

核心思路：论文的核心思路是设计一个自适应的LLM-EPS框架，该框架能够根据搜索过程中的多样性指标动态调整探索和利用的程度。通过引入多样性测量指标和和谐搜索算法，HSEvo旨在实现多样性和收敛性之间的平衡，从而更有效地搜索高质量的启发式算法。

技术框架：HSEvo框架主要包含以下几个模块：1) LLM驱动的启发式生成模块，负责利用LLM生成候选启发式算法；2) 多样性评估模块，使用论文提出的多样性测量指标评估种群的多样性；3) 和谐搜索算法模块，根据多样性评估结果调整搜索策略，平衡探索和利用；4) 目标函数评估模块，评估候选启发式算法在目标问题上的性能；5) 反馈机制，将评估结果反馈给LLM，指导后续的启发式生成。

关键创新：HSEvo的关键创新在于其自适应的探索-利用平衡机制。与现有方法相比，HSEvo能够根据搜索过程中的多样性动态调整搜索策略，避免陷入局部最优或过早收敛。此外，论文提出的多样性测量指标能够更准确地评估种群的多样性，为自适应调整提供依据。

关键设计：HSEvo的关键设计包括：1) 论文提出了两种多样性测量指标，用于评估种群的多样性；2) 采用了和谐搜索算法作为主要的搜索策略，该算法具有良好的全局搜索能力；3) 设计了自适应的参数调整机制，根据多样性指标动态调整和谐搜索算法的参数，以平衡探索和利用；4) 使用LLM生成启发式算法时，采用了适当的提示工程（prompt engineering）技术，以提高生成算法的质量。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，HSEvo在黑盒AHD问题上取得了优异的性能。HSEvo在实现高多样性指标的同时，也获得了良好的目标分数，并且保持了成本效益。与现有方法相比，HSEvo能够更有效地平衡探索和利用，从而找到更高质量的启发式算法。这些结果验证了HSEvo的有效性和优越性。

🎯 应用场景

HSEvo可应用于各种需要自动启发式设计的领域，例如组合优化、路径规划、调度问题等。通过自动生成高效的启发式算法，HSEvo可以降低人工设计成本，提高问题求解效率，并为解决复杂问题提供新的思路。未来，HSEvo有望在智能制造、物流优化、金融风控等领域发挥重要作用。

📄 摘要（原文）

Automatic Heuristic Design (AHD) is an active research area due to its utility in solving complex search and NP-hard combinatorial optimization problems in the real world. The recent advancements in Large Language Models (LLMs) introduce new possibilities by coupling LLMs with evolutionary computation to automatically generate heuristics, known as LLM-based Evolutionary Program Search (LLM-EPS). While previous LLM-EPS studies obtained great performance on various tasks, there is still a gap in understanding the properties of heuristic search spaces and achieving a balance between exploration and exploitation, which is a critical factor in large heuristic search spaces. In this study, we address this gap by proposing two diversity measurement metrics and perform an analysis on previous LLM-EPS approaches, including FunSearch, EoH, and ReEvo. Results on black-box AHD problems reveal that while EoH demonstrates higher diversity than FunSearch and ReEvo, its objective score is unstable. Conversely, ReEvo's reflection mechanism yields good objective scores but fails to optimize diversity effectively. With this finding in mind, we introduce HSEvo, an adaptive LLM-EPS framework that maintains a balance between diversity and convergence with a harmony search algorithm. Through experimentation, we find that HSEvo achieved high diversity indices and good objective scores while remaining cost-effective. These results underscore the importance of balancing exploration and exploitation and understanding heuristic search spaces in designing frameworks in LLM-EPS.