Fitness Landscape of Large Language Model-Assisted Automated Algorithm Search

📄 arXiv: 2504.19636v3 📥 PDF

作者: Fei Liu, Qingfu Zhang, Jialong Shi, Xialiang Tong, Kun Mao, Mingxuan Yuan

分类: cs.AI, cs.NE

发布日期: 2025-04-28 (更新: 2025-08-27)

💡 一句话要点

图分析揭示大语言模型辅助算法搜索的复杂适应度景观

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

关键词: 大语言模型 算法搜索 适应度景观 图分析 自动化算法设计

📋 核心要点

  1. 现有算法自动设计方法缺乏对大语言模型辅助搜索适应度景观的深入理解，限制了对其搜索行为的有效分析。
  2. 本文提出了一种基于图的分析方法，将算法搜索过程中的算法和转换关系建模为图，从而可视化和分析适应度景观。
  3. 通过在多个任务和LLM上的实验，揭示了LAS景观的多模态和崎岖特性，并分析了算法相似性与性能之间的关系。

📝 摘要（中文）

本文旨在探索大语言模型（LLM）辅助算法搜索（LAS）的适应度景观，该景观对于理解其搜索行为至关重要。通过图分析方法，节点代表算法，边表示算法间的转换，我们对LAS景观进行了可视化和分析。我们在六个算法设计任务和六个常用LLM上进行了广泛的评估。研究结果表明，LAS景观是高度多模态和崎岖的，尤其是在组合优化任务中，并且任务和LLM之间存在明显的结构差异。此外，我们采用了四种不同的算法相似性度量方法，并研究了它们与算法性能和算子行为的相关性。这些见解不仅加深了我们对LAS景观的理解，而且为设计更有效的LAS方法提供了实践指导。

🔬 方法详解

问题定义：论文旨在解决大语言模型（LLM）辅助算法搜索（LAS）中适应度景观（fitness landscape）未被充分探索的问题。现有方法缺乏对LAS搜索行为的深入理解，难以指导更有效的算法设计。LAS的适应度景观决定了搜索算法的效率和最终性能，因此理解其结构至关重要。

核心思路：论文的核心思路是将LAS的搜索过程建模为一个图，其中节点代表算法，边代表算法之间的转换（例如，通过变异或交叉等算子）。通过分析这个图的结构，可以揭示适应度景观的特性，例如多模态性、崎岖程度等。这种图分析方法能够提供关于算法搜索空间和搜索行为的直观理解。

技术框架：整体框架包括以下几个主要步骤：1) 使用LLM生成初始算法种群；2) 使用进化算法或其他迭代搜索方法，通过变异、交叉等算子生成新的算法；3) 使用预定义的评价指标评估算法的性能；4) 构建算法搜索的图结构，节点为算法，边为算法之间的转换关系；5) 分析图的结构特征，例如连通性、聚类系数、平均路径长度等，以揭示适应度景观的特性；6) 研究算法相似性度量与算法性能和算子行为之间的关系。

关键创新：论文的关键创新在于使用图分析方法来研究LLM辅助算法搜索的适应度景观。这种方法能够将复杂的算法搜索过程可视化，并提供关于搜索空间结构的定量分析。此外，论文还研究了不同算法相似性度量方法与算法性能之间的关系，为设计更有效的算法搜索策略提供了依据。

关键设计：论文的关键设计包括：1) 使用多种算法相似性度量方法，例如基于代码相似性、行为相似性等；2) 使用不同的图分析指标来量化适应度景观的特性，例如多模态性、崎岖程度等；3) 在多个算法设计任务和不同的LLM上进行实验，以验证方法的有效性和泛化能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LAS景观是高度多模态和崎岖的，尤其是在组合优化任务中。不同任务和LLM之间存在明显的结构差异。研究还发现，算法相似性度量与算法性能和算子行为之间存在一定的相关性。例如，某些相似性度量方法能够更好地预测算法的性能。

🎯 应用场景

该研究成果可应用于自动化算法设计、组合优化、机器学习模型选择等领域。通过理解LLM辅助算法搜索的适应度景观，可以设计更有效的搜索策略，提高算法设计的效率和质量。未来，该研究可以扩展到其他类型的算法搜索问题，例如神经网络架构搜索等。

📄 摘要（原文）

Using Large Language Models (LLMs) in an evolutionary or other iterative search framework have demonstrated significant potential in automated algorithm design. However, the underlying fitness landscape, which is critical for understanding its search behavior, remains underexplored. In this paper, we illustrate and analyze the fitness landscape of LLM-assisted Algorithm Search (LAS) using a graph-based approach, where nodes represent algorithms and edges denote transitions between them. We conduct extensive evaluations across six algorithm design tasks and six commonly-used LLMs. Our findings reveal that LAS landscapes are highly multimodal and rugged, particularly in combinatorial optimization tasks, with distinct structural variations across tasks and LLMs. Moreover, we adopt four different methods for algorithm similarity measurement and study their correlations to algorithm performance and operator behaviour. These insights not only deepen our understanding of LAS landscapes but also provide practical insights for designing more effective LAS methods.