Large Language Models as Hyper-Heuristics for Combinatorial Optimization

NP-hard组合优化问题的无处不在迫使领域专家参与试错式启发式设计。设计自动化的长期努力随着大型语言模型（LLM）的兴起而得到新的动力。本文介绍了一种新兴的超启发式变体——语言超启发式（LHHs），它利用LLMs进行启发式生成，具有最小的人工干预和开放式的启发式空间。为了赋予LHHs更强的能力，我们提出了一种新颖的反思演化（ReEvo），它将进化搜索与LLM反思相结合，以在空间内提供语言梯度。在五种异构算法类型、六种不同的COPs以及COPs的白盒和黑盒视图中，ReEvo提供了最先进和有竞争力的元启发式、进化算法、启发式和神经求解器，同时比之前的LHHs更加高效。我们的代码可在https://github.com/ai4co/LLM-as-HH上获得。

论文旨在介绍Language Hyper-Heuristics (LHHs)这一新兴的超启发式算法，并探索如何利用大型语言模型（LLMs）来生成启发式算法，以解决NP-hard组合优化问题（COPs）。

论文提出了Reflective Evolution (ReEvo)这一新的算法，将进化搜索和LLM反射相结合，以有效地探索启发式空间，并提供空间内的语言梯度，从而生成更加开放和高效的启发式算法。

通过在五种异构算法类型、六种不同的COP和白盒、黑盒视图下进行实验，ReEvo生成的超启发式算法、进化算法、启发式算法和神经求解器均达到了最先进和有竞争力的水平，并且比之前的LHHs更加高效。论文提供了开源代码。

在这个领域中，最近的相关研究包括：'A survey of hyper-heuristics'，'Hyper-heuristics: a survey of the state of the art'，以及'Large-scale optimization of hierarchical place recognition with semantics and noise-aware metric learning'。