2024/11/06 15:08

调研180多篇论文，这篇综述终于把大模型做算法设计理清了

AIxiv专栏是机器之心发布学术、技术内容的栏目。过去数年，机器之心AIxiv专栏接收报道了2000多篇内容，覆盖全球各大高校与企业的顶级实验室，有效促进了学术交流与传播。如果您有优秀的工作想要分享，欢迎投稿或者联系报道。投稿邮箱：liyazhou@jiqizhixin.com；zhaoyunfeng@jiqizhixin.com

本文第一作者柳斐（https://feiliu36.github.io/ ）是香港城市大学计算机科学系博士生，师从张青富教授。研究领域为计算智能，自动算法设计，组合优化等。姚一鸣，郭平，杨致远，赵哲和林熙来自香港城市大学张青富教授团队。陆智超为香港城市大学计算机科学系助理教授。王振坤为南方科技大学系统设计与智能制造学院助理教授。童夏良和袁明轩来自华为诺亚方舟实验室。

论文标题：A Systematic Survey on Large Language Models for Algorithm Design
论文地址：https://arxiv.org/abs/2410.14716

算法设计（AD）对于各个领域的问题求解至关重要。大语言模型（LLMs）的出现显著增强了算法设计的自动化和创新，提供了新的视角和有效的解决方案。在过去的三年里，LLMs 被整合到 AD（LLM4AD）中取得了显著进展，在优化、机器学习、数学推理和科学发现等各个领域获得广泛研究和应用。鉴于这一领域的快速发展和广泛应用，进行系统性的回顾和总结既及时又必要。本文对 LLM4AD 的研究进行了系统性回顾。首先，我们概述和总结了现有研究。然后，我们沿着四个维度，包括 LLMs 的作用、搜索技术、提示策略和应用，提出了一个系统性分类和现有研究的回顾，讨论了使用 LLMs 的潜力和成就。最后，我们探讨当前的挑战，并提出了几个未解问题和未来研究的方向。

1. 引言

算法在解决各个领域的问题中发挥着至关重要的作用，包括工业、经济、医疗和工程等领域。传统的手工设计算法的方法繁琐且耗时，需要广泛的专业知识和大量的努力。因此，人们越来越关注在算法设计中采用机器学习和计算智能技术以自动化和增强算法开发过程。

近年来，大型语言模型（LLMs）已经成为生成人工智能领域的重大突破。LLMs 以其庞大的模型规模、巨大的训练数据和在语言理解、数学推理、代码生成等各个研究领域中有着出色的表现。在过去的三年里，大型语言模型用于算法设计（LLM4AD）已经成为一个新兴的研究领域，有望增强甚至重塑算法的构思、优化和实施方式。LLMs 的强大功能和适应性展示了其在改进和转变算法设计过程中的潜力，包括启发式生成、代码优化，甚至创造针对特定问题的新算法。这种方法不仅减少了设计阶段所需的人力，还提高了算法设计过程的创新性和效率。

尽管 LLM4AD 领域正在受到广泛研究和应用，但在这一新兴领域仍然缺乏系统性综述。本文旨在通过提供一个最新的多维度的系统综述来填补这一空白，全面展示 LLMs 在算法设计中的应用现状、主要挑战和未来研究方向。本文有助于深入探讨 LLMs 在增强算法设计方面的潜力，并为这一令人兴奋的领域的未来创新打下坚实基础。我们希望这将成为对该领域感兴趣的研究人员的有益资源，并为经验丰富的研究者提供一个系统性的综述。本文的贡献如下：

LLM4AD 的系统综述：我们首次对过去三年中发表的 180 多篇高度相关的研究论文进行了系统综述，探讨了使用 LLMs 进行算法设计的发展。
LLM4AD 的多维度分类：我们引入了一个多维度分类法，将 LLM4AD 的作品和功能分为四个不同的维度：1）LLMs 在算法设计中使用的四种范式，概述了这些模型如何为算法设计做出贡献或增强算法设计；2）搜索方法，探讨了 LLMs 用于导航和优化算法设计中搜索空间的各种方法；3）提示词设计，研究了如何使用不同的提示策略；以及 4）应用领域，确定 LLMs 正在应用于解决的不同领域。
LLM4AD 的挑战和未来方向：我们不仅仅是对现有文献进行总结，而是对当前关于算法设计中大型语言模型（LLMs）研究的局限性进行了批判性分析。此外，我们提出了潜在的未来研究方向，包括开发领域特定的 LLMs、探索多模态 LLMs、促进人与 LLM 的互动、使用 LLMs 进行算法评估和理解 LLM 行为、推进全自动算法设计，以及为系统评估 LLM 在算法设计中的表现进行基准测试。这一讨论旨在激发新的方法并促进该领域的进一步发展。

2. 大模型用于算法设计概览

本文旨在对新兴领域 “大语言模型用于算法设计”（LLM4AD）中现有研究工作进行系统的梳理和分类。我们并不打算涵盖所有关于大型语言模型（LLMs）和算法的文献。我们的调查范围如下所述：1）“大语言模型” 一词指的是规模足够大的语言模型。这些模型通常采用 Transformer 架构，并以自回归方式运行。使用较小模型进行算法设计的研究，如传统的基于模型和机器学习辅助的算法，不在考虑范围内。虽然精确定义 “大型” 模型具有挑战性，但大多数前沿的大型语言模型包含超过十亿个参数。使用其他大型模型缺乏语言处理能力的研究，如纯视觉模型，不在考虑范围内。然而，包括语言处理的多模态大型语言模型则在我们的调查范围之内。2）“算法” 一词指的是一组设计用来解决问题的数学指令或规则，特别是当由计算机执行时。这个广泛的定义包括传统的数学算法、大多数启发式方法，以及可以被解释为算法的某些策略。

我们介绍了论文收集和扫描的详细流程，包括四个阶段：

第一阶段数据提取和收集：我们通过谷歌学术、科学网和 Scopus 收集相关论文。我们的搜索逻辑是标题必须包含以下两组词语中至少一组的任意组合：“LLM”、“LLMs”、“大型语言模型”、“算法”、“启发式”、“搜索”、“优化”、“优化器”、“设计”、“方法”（例如，LLM 和优化，LLMs 和算法）。在移除重复的论文后，截至 2024 年 7 月 1 日，我们共收集到 850 篇论文。
第二阶段摘要筛选：我们检查每篇论文的标题和摘要，以有效排除不相关的论文。排除的标准包括这些论文不是英文的，不是用于算法设计的，没有使用大型语言模型的。扫描后，剩余 260 篇论文。
第三阶段全文筛选：我们彻底审查每篇论文，排除缺乏相关内容的论文。扫描后，剩余 160 篇论文。
第四阶段补充：根据对该领域的了解，我们手动添加了一些相关的工作，以避免遗漏任何重要的贡献。在整合了额外的论文后，我们最终得到了 180 多篇论文。我们将首先介绍 LLM4AD 论文列表的概览，然后提出一个分类法来系统地回顾进展。除了组织好的论文列表之外，我们还纳入了 2024 年 7 月 1 日之后发布的一些重要出版物。

图中展示了随时间变化的论文发表数量趋势，时间线以月份表示。图表显示，与 LLM4AD 相关的研究活动显著增加，特别是注意到大多数研究是在近一年进行的。这表明 LLM4AD 是一个新兴领域，随着来自不同领域的学者意识到其巨大潜力，我们预计在不久的将来研究产出将显著增加。

图中还显示了在 LLM4AD 出版物中领先的机构及其所在国家。美国领先，紧随其后的是中国，这两个国家单独占据了 50％的出版物。接下来的八个国家，包括新加坡、加拿大和日本，共同贡献了总出版物的三分之一。发表最多论文的研究机构包括清华大学、南洋理工大学和多伦多大学等知名大学，以及华为、微软和谷歌等大型公司。这种分布强调了研究主题的广泛兴趣和它们在现实世界中的实际应用的重大相关性。

我们从所有审查过的论文的标题和摘要中生成了词云，每个词至少出现五次。它展示了前 80 个关键词，这些词被组织成四个颜色编码的簇，分别是 “语言”、“GPT”、“搜索和优化” 以及 “科学发现”。还突出显示了几个关键词，如 “进化”、“策略”、“优化器” 和 “代理”。

3. 大模型用于算法设计的四种范式

LLM4AD 论文按照大模型的结合方法可以分为四个范式：1）大模型作为优化算子（LLMaO）、2）大模型用于结果预测（LLMaP）、3）大模型用以特征提取（LLMaE）、4）大模型用来算法设计（LLMaD）。

LLMaO 把 LLMs 用作算法框架内的黑盒优化器。将 LLMs 整合到优化任务中，充分利用它们理解和生成复杂模式和解决方案的能力，以及在提示工程中的良好灵活性。然而，由于它们的黑盒性质，它们通常缺乏可解释性，并在面对大规模问题时面临挑战。
LLMaP 使用 LLMs 作为代理模型，预测结果或响应，功能上大体可以分为分类或回归两类。与其他基于模型的预测器（如高斯过程和传统神经网络）相比，1) LLMs 能够基于其在庞大数据集上接受的训练，处理和生成类人响应。这种能力使它们能够理解和解释数据中的复杂模式，适用于传统建模技术可能因数据的复杂性和复杂表示而难以应对的任务。2) 预训练的 LLMs 可以显著减少与训练高保真模型相比所需的计算负载和时间。
LLMaE 利用 LLMs 挖掘和提取目标问题和（或）算法中的嵌入特征或特定知识，然后在解决新问题中利用这些特征。这一过程利用了 LLMs 的独特和强大的能力，如文本和代码理解，使它们能够识别数据中可能通过传统特征提取方法无法处理或理解的模式和关系。
LLMaD 直接创建算法或特定组件。这种范式充分利用了 LLMs 的语言处理、代码生成和推理能力。LLMs 通过生成启发式算法、编写代码片段或设计函数，进一步推动了算法设计自动化，显著加速算法设计过程，减少人力劳动，并可能为算法开发带来创造性和更好的设计。这是单靠传统算法设计方法难以实现的。

4. 大模型用于算法设计中的搜索方法

目前的经验表明，单独采用大模型来进行算法设计往往难以应对特定的复杂算法设计任务。通过搜索方法的框架下调用大模型能够显著提升算法设计效率和效果。我们综述了目前在 LLM4AD 中采用的搜索方法，并将其大致分为四类：1）基于采样的方法，2）单点迭代的搜索方法，3）基于种群的搜索方法和 4）基于不确定性的搜索方法。详细的介绍和讨论可以在原文中查看。

5. 大模型用于算法设计中的提示词设计

图中展示了文献中使用的领域或预训练语言模型（LLMs）的百分比。其中，超过 80％的研究选择使用未经特定微调的预训练模型，大约 10％的研究在领域数据集上对预训练模型进行了微调，其中只有 4.4％的模型是在特定问题上从头开始训练的。图中还展示了最常使用的 LLMs。在 LLM4AD 的论文中，GPT-4 和 GPT-3.5 是使用最多的 LLMs，总共占了大约 50％。Llama-2 是最常用的开源 LLM。一旦我们拥有了预训练的 LLMs，提示工程对于有效整合 LLMs 到算法设计中非常重要。我们讨论了 LLM4AD 论文中使用的主要提示工程方法的应用情况，包括零样本、少样本、思维链、一致性和反思。

6. 大模型用于算法设计的应用领域

我们整理了四个主要的应用领域：1）优化，2）机器学习，3）科学发现，4）工业。其主要工作按照应用类别、方法、大模型结合范式、提示词策略和具体应用问题进行了分类罗列。具体介绍可以在全文中查看。

7. 未来发展方向

算法设计大模型与使用通用的预训练 LLMs 不同，研究如何专门训练 LLM 以自动设计算法是值得的。在开发领域特定 LLM 时可以探索以下几个方面：1）训练领域 LLM 成本高且资源消耗大。借助领域数据和知识可以减小特定应用的算法 LLM 的规模。2）算法设计生成和收集领域数据存在挑战。与通用代码生成或语言处理任务不同，没有专门用于算法设计的大型且格式化的数据。3）与其学习一个文本和代码生成模型，如何学习算法开发思想和算法推理能力仍是一个未探索的问题。
多模态 LLM 现有的 LLM4AD 工作主要集中在利用 LLM 的文本理解和生成能力，无论是在语言、代码还是统计方面。与传统的基于模型的优化相比，LLM 的一个优势是它们能像人类一样处理多模态信息，这一点很少被研究。已经有一些尝试展示了在算法设计中融入多模态信息的优势，预计将开发更多利用多模态 LLM 的方法和应用。
人类 - 大模型交互需要进一步研究 LLM 与人类专家在算法设计中的互动。例如，在 LLMaD 工作中，LLM 可以被视为智能代理，使人类专家可以介入并接管生成、修改和评估算法等任务。研究如何促进 LLM 与人类专家之间高效且富有成效的合作将是有价值的。可以为此目的使用群体智能中的思想和技术。
基于 LLM 的算法评估 LLM 在算法评估中可能是有帮助的。已经进行了一些尝试来自动评估算法和评估算法设计。例如，已有工作利用基础模型自动生成定义下一个可学习任务的代码，通过生成环境和奖励函数，能够为算法评估创建各种模拟学习任务。我们期待更多关于基于 LLM 的算法评估的研究。
理解 LLM 的行为在大多数研究中，LLM 作为一个黑盒模型运作。解释 LLM 的行为不仅能丰富我们对 LLM 行为的理解，还有助于那些直接请求 LLM 困难或成本高昂的情况。已经有一些尝试来近似和理解 LLM 在解决方案生成中的上下文学习行为。例如，已有人设计了一个白盒线性算子来近似 LLM 在多目标进化优化中的结果。尽管有这些初步尝试，如何解释 LLM 的行为在许多算法设计案例中仍是一个开放的问题，包括启发式生成和想法探索。
全自动算法设计全自动算法设计面临两个主要挑战：1) 生成新的算法思想；2) 创建复杂、冗长的代码。虽然一些研究已经探讨了新思想的生成，但完整的算法设计（而不仅是启发式组件），包括启发式组件和详细的代码实现，仍然是一个挑战。现有应用通常专注于自动化预定义算法框架内的组件，而不是从头开始创建新算法。未来的研究需要解决这些复杂性，以推进全自动算法设计领域的发展。
LLM4AD 的标准测试集和平台标准测试集能促进进行公平、标准化和便捷的比较。虽然我们很高兴见证了多样化的研究工作和应用的出现，但仍然缺乏对基于 LLM 的算法设计的系统和科学的标准评估手段。未来，预计会有更多的基准测试出现，它们将在推进 LLM4AD 方面发挥关键作用。

8. 总结

本文提供了一份最新的关于大语言模型在算法设计中应用（LLM4AD）的系统性综述。通过系统回顾这一新兴研究领域的主要贡献文献，本文不仅突出了 LLM 在算法设计中的当前状态和发展，还引入了一个全新的多维分类体系，分类了 LLM 的结合范式、搜索方法、提示词方法和应用场景。这一分类体系为学术界和工业界的研究人员提供了一个框架，帮助他们理解和使用 LLM 进行算法设计。我们还讨论了该领域当前面临的限制和挑战并提出和探讨未来研究方向来激发和指引后续研究。

展望未来， LLM 与算法设计的交叉具有革命性地改变算法设计和应用方式的巨大潜力。LLM 在算法设计过程中的应用有助于极大的提高自动化程度并可能促进产生更高效、更有效和更具创造性的算法，以更好解决各个领域的复杂问题。我们希望本文能够有助于理解这一潜力，并促进 LLM4AD 这一有前景的研究领域的发展。

理论算法设计