「引言」大语言模型 (LLMs) 凭借强大的自然语言理解和生成能力, 能够有效地处理复杂的问题描述和约束条件，在有效解决复杂优化问题方面更蕴藏着巨大的潜力。与传统的优化算法大多依赖人工设计的特点有所不同，LLMs可以自动学习并辅助优化算法求解，从而有针对性地对不同领域的优化问题生成求解方案。例如，在LLM和演化算法（EAs）的协同优化技术设计中，一方面，LLM可以增强EA的搜索能力; 另一方面，EA也可以反过来优化LLM的学习性能。因此，正如下图所示，LLM与EA这两者的有机结合可以有效解决不同领域中的应用问题 。
研究背景
总的来说, 相比传统的优化算法大多依赖人工设计,很难适应不同问题特点等不足，LLMs为优化问题求解提供了新的思路。这主要是因为LLMs可以自动学习和生成针对性的解和算法,极大地拓展了复杂优化问题求解的应用领域。让我们一起来看看最新的相关工作吧！
论文1：Large language models as optimizers[1]
原文链接：https://arxiv.org/pdf/2309.03409
在许多现实世界的应用中，由于缺乏梯度，导数算法在解决问题时经常面临挑战。与以往复杂的方式不同，作者提出了一种名为通过提示的优化(Optimization by PROmpting,OPRO)的简单有效方法,利用大型语言模型(LLM)作为优化器,其中优化任务是用自然语言描述的。在每个优化步骤中,LLM根据包含先前生成的解决方案及其值的提示生成新的解决方案,然后新解决方案被评估并添加到提示中,用于下一步的优化。作者首先在线性回归和旅行推销员问题上展示了OPRO,然后提示优化,其目标是找到能最大化任务精度的指令。可以通过简单改变提示中的问题描述快速适应不同任务。论文表示，在小规模优化问题上，大模型作为优化器能够找到高质量的解决方案。
(a)
(b)
图1 （a）OPRO框架概述。给定元提示作为输入，大语言模型生成新的解决方案以满足目标函数，然后将这些新的解决方案及其得分添加到元提示中，用于下一步优化。元提示包含整个优化过程中获得的解决方案-得分对、任务的自然语言描述，以及（在提示优化中）一些任务示例。(b)展示了一个用于提示优化的元提示样例。
1.1 研究方法
OPRO（Optimization by Prompting） 是一种利用大型语言模型 (LLM) 进行优化的创新方法。它通过元提示（meta-prompt） 来引导 LLM 生成更优的解，突破了传统优化方法的局限性。
元提示的作用:
引导 LLM 理解优化问题的本质和目标。
提供 LLM 生成解的依据和参考。
记录 LLM 探索过程中的经验和教训。
流程详解：
LLM 担任优化器: 将 LLM 视为优化器，使其尝试生成可能的解决方案。
生成解决方案: LLM 基于给定的元提示和任务描述生成解决方案。元提示可以包含问题描述、目标函数、约束条件等信息，任务描述则定义了要解决的特定问题或目标。
目标函数评估器: 引入目标函数评估器，用来评估解决方案的质量或效果。评估器根据预设的标准对生成的解决方案进行评分，并将评分结果称为“分数”。
元提示: 元提示是整个流程的核心，它充当 LLM 的指示，引导其生成特定的输出。在每一次迭代中，元提示都会根据先前生成的解决方案和得分进行更新，帮助 LLM 了解哪些策略有效，哪些无效。
任务描述: 任务描述定义了要解决的特定问题或目标，为 LLM 生成解决方案提供明确的方向。
解决方案-分数对: 解决方案-分数对是元提示ing的关键组成部分，它包含之前生成的解决方案及其对应的分数。通过分析这些对，LLM 可以学习哪些策略更有效，并在后续的尝试中生成更好的解决方案。
返回最佳解决方案: 当流程完成时，系统会返回获得最高分数的解决方案，即最优解。
1.2 实验结果
✍ 在Linear regression上的结果
每个模型探索的(w,b)值对的数量少于穷举搜索,这表明这些模型能够进行黑盒优化:通过比较数值来提出下降方向。
text-bison和gpt-4模型在收敛速度上优于gpt-3.5-turbo:它们用更少的步骤到达最优解。gpt-4模型在用更少的探索点找到最优解方面也表现更好。
仔细观察优化轨迹,我们发现gpt-4在根据历史提出合理的下一步做出最好的表现:例如,当历史显示(w,b)=(8,7)、(8,6)和(8,5)的目标值在下降时,它有最高的概率提出评估(w,b)=(8,4)。
当真实值远离起始区域时,对所有模型来说问题变得更加困难:所有模型都需要更多的探索和更多的步骤。
从结果来看,大型语言模型确实展现出了黑盒优化的能力,能够基于有限的探索提出合理的下一步方向。其中,gpt-4模型在收敛速度、探索效率和下一步预测方面都优于其他模型。但是,当优化问题的困难程度增加时,所有模型的性能都会受到影响,需要更多的探索来찾到最优解。这凸显了目前大型语言模型在复杂优化问题上仍有提升空间。
✍在Traveling Salesman Problem (TSP)上的结果
旅行推销员问题(Traveling Salesman Problem,TSP)是一个著名的"NP难"问题。它的描述是:给定一张地图和一系列城市,任务是找到一条最短的路径,使得每个城市只访问一次,最后回到起点。对于这类问题,当涉及的城市点数量较大时,我们目前还没有可行的高效求解算法。不过,为了便于说明,Google在论文中使用了一个只有20个城市点的小规模实例。对于这种规模,我们可以尝试使用"完全搜索法"来枚举所有可能路径,并找到其中最短的那一条。
✍失败的案例和总结
数学计算的准确性问题：优化器 LLM 可能会输出虚构的数学计算结果，例如“在 (5, 3) 处函数值为 15”，即使真实值并非如此。如果能够可靠地触发外部计算工具，模型可能会得到正确的值，这一触发时机及方法仍是一个有趣的研究课题。
生成重复解：即使指示 LLM 生成“与所有现有值对不同的新 (w, b) 值对”，它也无法完全遵循指令，有时会重复输出现有解。
陷入非最优解的问题：在黑盒数学优化中，优化器经常会陷入既非全局最优解也非局部最优解的情况，特别是在复杂的损失景观中。增加每个步骤的探索量可以缓解这一问题。
复杂函数优化困难：像Rosenbrock函数这样的复杂函数，会使优化器LLM在优化时面临困难。例如，LLM 可能会陷入 (0, 0) 附近，因为从 (0, 0) 开始很难沿着狭窄的损失曲谷找到全局最优解。
论文2：Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model [2]
原文链接：https://openreview.net/pdf?id=BwAkaxqiLB
2.1 研究方法
图2 启发式设计通常(a)依赖于人类专家对思维的推理；最近在(b)代码空间的搜索方面取得了进展；而(c)我们的方法则使用大型语言模型来同时演化思维和代码。
EoH 的目标是通过同时进化思想和代码，模仿人类专家开发启发式算法的过程，从而实现高效的自动启发式算法设计。为了达到这一目标，EoH 采用了以下方法：
思想与代码的结合: EoH 为每个启发式算法维护一个自然语言描述及其对应的代码实现。在每一次试验中，它允许大型语言模型 (LLMs) 首先用自然语言生成一个启发式算法，然后生成其对应的代码。自然语言描述概述了主要思想并提供高级理解，而代码则提供实现细节和设置，以补充高级思想。
引导式提示策略: EoH 采用多种提示策略来引导 LLM 对现有思想和代码进行推理。这些策略旨在从过去的经验中学习，并有效地探索启发式算法空间。它们可以被视为结合思想和代码进行启发式搜索的细粒度情境学习方法。
候选启发式算法的进化: EoH 会不断进化一群候选启发式算法。它利用 LLM 在遗传操作（例如交叉和变异）中生成新的启发式算法。选择算子也用于指导搜索。每个启发式算法的质量都将在一系列问题实例上进行评估。与大多数进化算法不同的是，进化算法中的个体是优化问题的候选解，而 EoH 中的个体则是针对给定问题而设计的启发式算法。我们认为“思想”的进化应该是一个重要的研究方向。
EoH 将 LLM 集成到进化框架中，可以自动生成和改进启发式算法。与一些经典的自动启发式算法设计方法不同，EoH 无需任何手工制作的启发式算法组件或训练新的模型。
EoH的进化框架：
种群维护: EoH 在每一代会维持一个由 N 个启发式算法组成的种群，记为 P = {h1, ..., hN}。每个启发式算法 hi 都会针对一系列问题实例进行评估，并分配一个适应度值 f(hi)。
五种生成策略: EoH 设计了五种提示策略来生成新的启发式算法。在每一代，每种策略都会被调用 N 次以生成 N 个新的启发式算法。这些新生成的启发式算法将被评估，并且符合条件的将会被添加到当前种群中。每代最多会添加 5N 个新个体。然后，会从当前种群中选择 N 个最优的个体，组成下一代的种群。
EoH 算法流程:
选择当前种群中的父代启发式算法来构建提示信息。
要求 LLM 生成新的启发式算法及其对应的代码实现。
在一系列评估实例上评估新启发式算法以确定其适应度值。
如果新算法和代码符合要求，则将其添加到当前种群中。
初始化：使用初始化提示策略创建初始种群 P，具体细节将在 3.4 节介绍。
生成启发式算法：如果不满足终止条件，将同时使用五种进化提示策略（见 3.4 节）生成 5N 个新个体。对于每种提示策略，重复以下过程 N 次：
种群管理：从当前种群中选择 N 个最优的个体，形成下一代的种群。然后返回步骤 1。
提示策略:
初始化提示: EoH 利用 LLM 创建所有初始启发式算法，无需专家知识。提示信息会告知 LLM 启发式算法的设计任务，并指导它通过描述和 Python 代码块来实现算法。
进化提示: EoH 设计了五种提示策略用于在进化过程中创建新的启发式算法，以模拟人类的启发式算法开发过程。这些策略分为两类：探索型 (E1, E2) 和 改进型 (M1, M2, M3)。探索型策略侧重于通过对父代启发式算法执行类似交叉的操作来探索启发式算法空间。改进型策略则通过修改、调整参数和删除冗余部分来优化父代启发式算法。
2.2 实验结果
✍在Online bin packing problem上的结果
这类优化问题目标是在满足容量限制 C 的前提下，用最少的容器来容纳一系列不同尺寸的物品。
图3 在线装箱问题的启发式演化（Evolution of EoH）。我们概述了在演化过程中某些代际产生的最佳启发式算法的关键思想和相应的代码片段，列出了提示策略，并展示了最终群体中的最佳启发式算法，将其与最佳适应启发式算法以及FunSearch产生的启发式算法进行比较。
经过 20 代的迭代和 2000 次对大型语言模型的调用，EoH 设计的启发式算法的适应度值（目标值）从 0.962 显著提升到了 0.993。如图 2 所示，与现有最佳启发式算法相比，FunSearch 和 EoH 设计的启发式算法都更加精巧高效。
论文3：Large language models to enhance Bayesian optimization[3]
原文链接：https://openreview.net/pdf?id=OOxotBmGol
在机器人、实验设计、药物发现、界面设计等许多学科和应用中，昂贵的黑箱函数 (expensive black-box functions) 都很常见。机器学习中的超参数调优也是如此。黑箱函数是指难以直接计算其梯度或目标值的信息的函数，这类函数的优化往往代价高昂。贝叶斯优化 (BO) 是一种有效的基于模型的全局优化方法，适用于优化复杂的黑盒函数（难以直接计算梯度或目标值的信息）[6]。它在许多应用中发挥着重要作用，例如调优超参数。然而，贝叶斯优化的有效性取决于探索和利用的平衡。虽然 BO 方法取得了重大进展，但这种平衡仍然是一个微妙的过程。针对这一挑战，作者提出了一种名为 LLAMBO 的新颖方法，该方法将大型语言模型 (LLM) 的能力融入 BO 框架。总的来说，LLAMBO 通过自然语言描述 BO 问题，使 LLM 能够迭代地提出并评估有前景的解决方案，同时考虑历史评估结果。更具体地说，我们探索如何结合上下文理解、少量样本学习能力和 LLM 的领域知识来改进基于模型的 BO。
本文考察了扩展大型语言模型 (LLM) 能力的潜力，使其超越标准的自然语言任务，以增强基于模型的贝叶斯优化 (BO)。我们的方法着眼于使用自然语言表示 BO 的组件，并引入新颖的方法来有效地捕捉 LLM 的独特优势。这项探索提出了两个关键问题：
[Q1] 编码了丰富知识且具备少量样本学习能力的 LLM 能否增强 BO 的关键要素，例如替代模型和候选点采样器？
[Q2] 经过 LLM 增强后的 BO 组件作为一个整体的端到端流水线，其运行效果如何？
3.1 研究方法
图3 LLAMBO概述。按顺序：LLAMBO可以通过以下方式初始化贝叶斯优化：▶ 零样本预热（zero-shot warmstarting）， ▶ 根据过去的观察结果和问题描述，从高潜力区域高效地采样候选点， ▶ 通过代理模型评估这些候选点。
这项研究探索了将大型语言模型 (LLM) 的能力扩展到增强基于模型的贝叶斯优化 (BO) 之上。LLM 的以下能力使其能够显著提升 BO 的性能：
先验知识：近期研究表明，LLM 的基于上下文的学习 (ICL) [6] 过程类似于执行隐式贝叶斯推理。这为利用 ICL 挖掘 LLM 编码的知识用于 BO 开辟了有趣的可能性。在 BO 框架中，p(θ) 表示优化问题相关的先验知识和通过预训练吸收的特定领域相关性 。
基于上下文的学习 (ICL)：仅利用有限的观测数据学习可泛化的模型极具挑战性。LLM 已经证明了仅通过少量基于上下文的示例就能进行泛化学习的能力，这种能力可以直接补充 BO 对样本高效探索的需求。
上下文理解：LLM 擅长处理上下文信息，尤其是通过自然语言。这提供了一种通用接口，可以结合有关优化任务、搜索空间和辅助细节的元特征来改善搜索性能。
将这种协同作用付诸实践：尽管 LLM 具有上述优势，但在像 BO 这样的迭代优化框架中有效利用它们仍然是一项挑战。我们引入了新的方法来利用 LLM 增强 BO 的多个组件，并进行了系统的研究以了解这种集成的性能提升。具体来说，我们采用 ICL 技术来增强 BO 的三个关键组件（见图 1）：
预热启动：预热启动使用预先识别的一组点 {hi} n i=1 来初始化优化过程，这些点将首先进行评估以构建 f 的有意义表示。我们提出了一种通过零样本提示来识别潜在有效初始化的方法。
候选者采样：采样过程会提出候选点供真实的评估。我们提出了一种基于目标值进行条件采样的机制。在这里，我们通过提供优化历史记录作为少量样本示例来利用 ICL 技术。
替代模型：替代模型表示为 p(s|h; Dn)，是 f 的近似，并使用 Dn 训练得到。具体来说，我们引入两种利用优化历史记录的 ICL 方法：一种判别式方法，产生带有不确定性的回归估计；一种生成式方法，通过二分类进行评分。
该框架围绕着前面提到的两个问题 [Q1-2] 展开。
3.2 实验结果
实验设置：为了评估我们提出的方法，我们使用了来自 Bayesmark 和 HPOBench 的 74 个任务，以及 OpenAI 的 GPT-3.5 大型语言模型。需要指出的是，LLM 的选择会显著影响优化结果。然而，我们强调本文提出的总体方法和基本原理适用于各种大型语言模型，不局限于特定的模型本身。
✍在Bayesmark上的实验结果
图4 LLAMBO的端到端性能。（左图）在公开数据集上的平均遗憾，以及（右图）在Bayesmark上评估的私有和合成数据集的结果。
图 4 展示了在所有 HPT 任务上的平均后悔值，涵盖公开的 Bayesmark 数据集、私有数据集和合成数据集。可以看到，在两种设置下，LLAMBO 都取得了最佳的调优性能。此外，与之前的一些研究结果一致，LLAMBO 在搜索的早期阶段表现更加突出，尤其是在观测数据较少的情况下。
总结展望
本文梳理了近期结合LLMs和进化算法的研究为优化算法设计的三个创新性的研究，如PRO通过提示优化方法利用LLMs作为优化器；EoH提出了一种新颖的进化范式，同时对思想和代码进行演化以生成高效的启发式算法；LLAMBO将LLMs的能力融入贝叶斯优化框架，提升了黑盒函数优化的效率。这些研究不仅展示了LLMs在优化算法设计中的潜力，也为复杂优化问题的求解带来了新的思路和技术性的突破。
参考文献
[1] Yang, Chengrun, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. "Large language models as optimizers." arXiv preprint arXiv:2309.03409 (2023).
[2] Liu, Fei, Tong Xialiang, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. "Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model." In Forty-first International Conference on Machine Learning. 2024.
[3] Liu, Tennison, Nicolás Astorga, Nabeel Seedat, and Mihaela van der Schaar. "Large Language Models to Enhance Bayesian Optimization." arXiv preprint arXiv:2402.03921 (2024).
[4] Wu, Xingyu, Sheng-hao Wu, Jibin Wu, Liang Feng, and Kay Chen Tan. "Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap." arXiv preprint arXiv:2401.10034 (2024).
[5] Wang, Xilu, Yaochu Jin, Sebastian Schmitt, and Markus Olhofer. "Recent advances in Bayesian optimization." ACM Computing Surveys 55, no. 13s (2023): 1-36.
[6] Xie, Sang Michael, Aditi Raghunathan, Percy Liang, and Tengyu Ma. "An explanation of in-context learning as implicit bayesian inference." arXiv preprint arXiv:2111.02080 (2021).
END
初稿 | 王曦璐
复审 | 颜学明
终审 | 金耀初
