利用大型语言模型调整元启发式算法的参数

《Neurocomputing》：Tuning metaheuristic parameters with the use of Large Language Models

本研究探讨大语言模型（LLMs）能否通过参数选择优化元启发式算法（MHAs），以图着色、作业车间调度和旅行商问题为测试对象，采用两阶段流程验证LLMs的有效性，结果显示LLMs能显著提升算法性能，尤其在模拟退火和旅行商问题中效果显著，表明LLMs在优化领域具有高泛化能力和语境理解，可辅助算法设计。

　　

Alicja Martinek | Ewelina Bartuzi-Trokielewicz | Szymon ?ukasik | Amir H. Gandomi

克拉科夫AGH大学，波兰克拉科夫

摘要

自从大型语言模型（LLMs）爆红以来，它们几乎影响了生活的方方面面。本研究探讨了是否可以利用LLMs通过选择参数来调整元启发式算法。为了验证这一假设，我们使用由LLMs指导的启发式优化器（包括遗传算法、蚁群优化、粒子群优化和模拟退火）解决了三个著名的组合优化问题（图着色、作业车间调度和旅行商问题）的各十个实例。通过向几个最先进的LLMs提供问题复杂度描述符和可调参数集来生成参数值。采用了两阶段程序：首先基于问题的一般特征进行初始运行，然后根据平均适应度、方差和收敛行为等性能指标进行反馈运行。Python库Mealpy的默认设置作为比较基准。

汇总900次优化器运行结果显示，LLMs能够提出在最终目标值和收敛速度方面优于默认设置的参数配置。这种效果在模拟退火和旅行商问题中尤为明显。研究结果表明，LLMs在优化领域具有高度的泛化能力和上下文理解能力，可以成为启发式算法设计和调整的实际辅助工具。

引言

当前全球正在发生的数据革命推动了数据分析新方法的进步。这得益于新型数据集的广泛可用性，以及学术界和工业界对创新机器学习和深度学习算法发展的兴趣。

大量收集的语言数据促进了大型语言模型（LLMs）的发展。这些方法在生活的几乎所有方面找到了无数应用场景，彻底改变了计算行业。LLMs是基于Transformer的神经网络，它们在2017年引入的注意力机制中发挥了重要作用[1]。第一个广泛使用的LLM是Google的BERT[2]，一年后发布并在许多自然语言处理任务中得到应用。然而，真正的变革始于2022年，当时OpenAI发布了ChatGPT。

尽管LLMs有很多积极方面，但必须谨慎使用。当模型在某个领域缺乏知识时，它们往往会编造内容，这种现象称为“幻觉”[3]。另一个不应轻视LLM答案的原因是，它们可能会传播刻板印象、分享不道德的内容或表现出种族偏见[4]——这些都是在现代LLMs中嵌入的广泛输出过滤的理由。

大型语言模型的应用包括高级聊天机器人、内容创作、代码编写、摘要生成等[5]。对LLMs的关注程度是前所未有的。公司、研究人员甚至政府都在积极开发自己的大型语言模型。

不断增长的数据量和新的算法为开发新的元启发式算法（MHAs）提供了绝佳的舞台。许多领域的优化仍然是一个未解决的问题，因为寻找更快、计算成本更低的方法始终是科学家的研究热点。因此，元启发式算法的数量仍在增加，很难跟上所有新发展的步伐。最近的启发式优化器分类包含了超过500种不同的方法[6][7]。

每种元启发式算法都有其独特的参数值、推荐的应用场景和额外信息，这些信息定义了该算法的特点。因此，掌握和记住所有关于MHAs的细节变得非常繁琐。需要一个能够提供算法选择建议的指南，尤其是适合特定问题的参数设置，这将是一个重大突破，可以降低元启发式算法的入门难度。

这种指南的需求为大型语言模型的发展提供了机会。它们理解自然语言和代码的能力可以用于指导启发式优化器的调整。这种可能性可以比默认设置带来更大的优势，并将计算方向引向更理想的方向。

本文的研究是对[8]的扩展，通过分析更多问题及其实例来深化研究。所采用的方法论相同，但涉及三个组合问题的多个实例，并使用了扩展的大型语言模型列表和经典的参数搜索技术（包括随机搜索和网格搜索）。上述方法使用LLMs在对该问题领域知之甚少的情况下选择优化任务的参数值。在用建议的设置解决问题后，再次要求LLMs根据初始结果调整参数。然后收集并分析基于反馈的轮次的性能。此外，本研究还评估了计算成本，并寻找计算费用与所获得结果质量之间的相关性。这项工作有两个贡献：首先，通过彻底的实验验证了当前最先进的大型语言模型是否可以在组合优化的背景下调整元启发式算法的参数；其次，围绕提示工程进行了有效调整。此外，这项工作还突出了LLMs的新应用。

为了评估LLM引导的参数调整的有效性，本研究重点关注三个经典的组合优化问题：图着色（GCP）、作业车间调度（JSSP）和旅行商问题（TSP）。这些问题在文献中已有广泛研究，以其计算复杂性和实际应用的相关性而闻名。它们在结构和解空间上的多样性使其成为评估LLMs在不同优化场景下泛化能力的理想测试平台。

除了实验评估外，该工作还专注于开发命令工程技术，以实现LLMs在启发式优化中的有效使用。这包括创建详细的、配置好的查询，帮助语言模型生成有用的输出。

元启发式算法复杂性的不断增加使得参数调整成为一项关键但成本高昂的任务。传统的网格搜索、随机搜索或贝叶斯搜索等方法计算密集且特定于问题。相比之下，大型语言模型凭借其推理和语言理解能力，为分析算法描述和提出合适的参数配置提供了新的范式。尽管潜力巨大，但LLMs在启发式优化中的使用仍然很大程度上未被探索。

本文的结构如下：首先简要介绍和动机，第2节解释了理解研究中进行的实验所需的概念。第3节介绍了LLMs和元启发式算法（MHAs）交叉领域的相关工作。第4节详细描述了本研究采用的方法论。第5节提供了运行计算的实用细节。第6节包含了结果及其分析。最后，第7节提出了结论和进一步改进的可能性。

部分摘录

大型语言模型

大型语言模型（LLMs）是人工智能领域的一项重大进展，特别是在自然语言处理和生成方面。这些模型旨在理解和生成类似人类的文本，利用了大量数据和复杂的神经网络架构。本文研究了OpenAI的ChatGPT、Google的Gemini、Anthropic的Claude以及Mistral AI的Le Chat模型，分析了它们在调整启发式算法中的潜在用途。

文献综述

本节总结了与LLMs和元启发式优化方法相互作用相关的最重要研究。它分为两部分：第一部分讨论了将LLMs与启发式和进化算法结合的研究，第二部分回顾了构成本研究概念基础的经典参数调整方法。

提出的方法论

本研究旨在探讨使用最先进的LLMs在组合优化背景下调整元启发式算法参数的可行性。研究过程包括几个阶段，详细内容见附图（图1），包括以下步骤：

• 1.
  确定优化问题——选择了三个优化问题（GCP、JSSP、TSP）的十个基准实例，从而创建了30个案例

实验

本节描述了本研究使用的实验设置，包括基准数据集、实现细节和评估指标，以提供透明且可复制的程序，用于评估基于LLM的参数调整的准确性和有效性。

结果

实验结果表明，大型语言模型可以有效地指导组合问题的调整过程。基于LLM的元启发式算法（MHAs）运行可以表现出优于默认设置的性能，并且仅通过一次反馈迭代就能提升其性能。

图2展示了所有测试问题和MHAs的代表性实例的收敛图。每个子图显示了优化过程中目标值的变化情况。

结论

实验结果提供了大量证据，支持大型语言模型可以谨慎地指导元启发式算法（MHAs）的参数调整过程。然而，它们的性能并不总是稳定的，很大程度上取决于研究社区对特定MHAs的探索程度。问题的流行程度也起着重要作用，因为结果表明，那些已经被广泛研究的MHAs问题对大型语言模型的理解似乎更好。

CRediT作者贡献声明

Alicja Martinek：撰写——原始草稿、可视化、验证、软件、方法论、形式分析、数据整理。Ewelina Bartuzi-Trokielewicz：撰写——原始草稿、验证、软件。Szymon ?ukasik：监督、方法论、概念化。Amir H. Gandomi：监督。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能会影响本文报告的工作。

Alicja Martinek分别于2016年和2018年在波兰克拉科夫AGH大学获得了生物医学工程的学士学位和硕士学位。2017年，她还在英国坎特伯雷大学获得了高级计算机科学的硕士学位。自2021年以来，她在克拉科夫AGH大学在Szymon ?ukasik教授和Amir Gandomi教授的指导下攻读信息技术和电信博士学位。