Algorithm Evolution Using Large Language Model
使用大型语言模型的算法进化

Fei Liu, Xialiang Tong, Mingxuan Yuan and Qingfu Zhang
Fei Liu、Xialiang Tong、Mingxuan Yuan 和 Qingfu ZhangFei Liu and Qingfu Zhang are with the Department of Computer Science, City University of Hong Kong, Hong Kong (e-mail: fliu36-c@my.cityu.edu.hk; qingfu.zhang@cityu.edu.hk). Xialiang Tong and Mingxuan Yuan are with Huawei Noah’s Ark Lab (e-mail: tongxialiang@huawei.com; yuan.mingxuan@huawei.com).
刘飞和张庆福就职于香港城市大学计算机科学系（电子邮箱：fliu36-c@my.cityu.edu.hk; qingfu.zhang@cityu.edu.hk）。童夏良和袁明轩就职于华为诺亚方舟实验室（电子邮箱：tongxialiang@huawei.com; yuan.mingxuan@huawei.com）。

Abstract 摘要

Optimization can be found in many real-life applications. Designing an effective algorithm for a specific optimization problem typically requires a tedious amount of effort from human experts with domain knowledge and algorithm design skills. In this paper, we propose a novel approach called Algorithm Evolution using Large Language Model (AEL). It utilizes a large language model (LLM) to automatically generate optimization algorithms via an evolutionary framework. AEL does algorithm-level evolution without model training. Human effort and requirements for domain knowledge can be significantly reduced. We take constructive methods for the traveling salesman problem as a test example, we show that the constructive algorithm obtained by AEL outperforms simple hand-crafted and LLM-generated heuristics. Compared with other domain deep learning model-based algorithms, these methods exhibit excellent scalability across different problem sizes. AEL is also very different from previous attempts that utilize LLMs as search operators in algorithms.
优化在现实生活中的许多应用中都能找到。为特定的优化问题设计有效的算法通常需要具备领域知识和算法设计技能的人类专家付出繁琐的努力。在本文中，我们提出了一种名为 "使用大型语言模型的算法进化"（AEL）的新方法。它利用大型语言模型（LLM），通过进化框架自动生成优化算法。AEL 无需模型训练即可实现算法级进化。可以大大减少人力投入和对领域知识的要求。我们以旅行推销员问题的构造方法为例进行了测试，结果表明，AEL 获得的构造算法优于简单的手工算法和LLM生成的启发式算法。与其他基于深度学习模型的领域算法相比，这些方法在不同规模的问题上都表现出卓越的可扩展性。此外，AEL 与以往在算法中使用LLMs作为搜索算子的尝试也有很大不同。

Index Terms:

Algorithm evolution, Large language model, Combinatorial optimization, Evolutionary optimization, Heuristic.
索引术语：算法进化、大型语言模型、组合优化、进化优化、启发式。

I Introduction I 引言

Optimization is everywhere. It plays a crucial role in production, planning, decision making, and resource management. Numerous research works have been carried out to develop efficient and powerful optimization algorithms. While these algorithms have proven to be valuable tools in many practical scenarios, designing them usually requires extensive manual crafting with domain knowledge [1, 2, 3].
优化无处不在。它在生产、规划、决策和资源管理中发挥着至关重要的作用。为了开发高效、强大的优化算法，人们开展了大量的研究工作。虽然这些算法已被证明是许多实际应用场景中的宝贵工具，但设计这些算法通常需要大量的手工和领域知识[1, 2, 3]。

To overcome these limitations, researchers have made much effort to automate the algorithm design process. Learning to optimize [4] involves automatically designing optimization methods based on their performance on a training set of problems. In deep learning, AutoML [5] offers promising solutions for constructing a deep learning system without human intervention. In the context of heuristic design, this is commonly referred to as hyperheuristics [6, 7] or automatic design of heuristics [8]. Moreover, reinforcement learning [9, 10, 11, 12], supervised learning [13, 14], transfer learning [15, 16, 17] and meta-learning [18, 19] have also been widely employed to enhance optimization efficiency, promote algorithm performance, and generate new algorithms. Furthermore, recent works have explored the use of end-to-end neural solvers for both continuous optimization [20, 21, 22, 23, 24] and combinatorial optimization [25, 26, 27, 28, 29]. While these progresses have significantly advanced the field of automatic algorithm design, they usually require an underlying algorithm framework or a time-consuming domain model crafting and training.
为了克服这些局限性，研究人员在算法设计过程自动化方面做出了很多努力。学习优化[4]涉及根据优化方法在训练问题集上的表现自动设计优化方法。在深度学习方面，AutoML[ 5] 为在没有人工干预的情况下构建深度学习系统提供了前景广阔的解决方案。在启发式设计中，这通常被称为超启发式[6, 7]或启发式自动设计[8]。此外，强化学习[9, 10, 11, 12]、监督学习[13, 14]、迁移学习[15, 16, 17]和元学习[18, 19]也被广泛用于提高优化效率、提升算法性能和生成新算法。此外，最近的研究还探索了在连续优化[20, 21, 22, 23, 24]和组合优化[25, 26, 27, 28, 29]中使用端到端神经求解器。虽然这些进展极大地推动了自动算法设计领域的发展，但它们通常需要一个底层算法框架或耗时的领域模型制作和训练。

In the past three years, large language models (LLMs) have demonstrated remarkable capabilities in various research domains [30, 31], such as natural language processing [32], programming [33], medicine [34, 35, 36], chemistry [37], chip design [38, 39], and optimization [40, 41, 42, 43]. Recently, several works have adopted LLMs as pre-trained black-box optimizers for optimization [44, 45, 21, 46, 47]. However, these works use LLMs to generate new solutions at the operator level. Its performance declines considerably when applied to large-scale problems, mainly due to the longer solution representation and large search space [44, 48, 47].
近三年来，大型语言模型（LLMs）在自然语言处理[32]、编程[33]、医学[34, 35, 36]、化学[37]、芯片设计[38, 39]和优化[40, 41, 42, 43]等多个研究领域展现出了卓越的能力[30, 31]。最近，有几项研究采用了LLMs作为优化的预训练黑盒优化器[ 44, 45, 21, 46, 47]。然而，这些研究使用LLMs在算子层面生成新的解决方案。当应用于大规模问题时，其性能会大幅下降，这主要是由于较长的解表示和较大的搜索空间造成的[44, 48, 47]。

In this paper, we propose a novel approach for practical automatic algorithm design called Algorithm Evolution using Large Language Model (AEL). AEL distinguishes itself from algorithm design by humans and through training domain models. It creates and modifies algorithms by interacting with large language models within an evolutionary framework. We demonstrate the effectiveness of AEL on the constructive method for the traveling salesman problem (TSP), highlighting its ability to generate novel and scalable algorithms. The contributions of this paper are summarized as follows:
在本文中，我们提出了一种实用的自动算法设计新方法，称为 "使用大型语言模型的算法进化（AEL）"。AEL 有别于人类和通过训练领域模型进行的算法设计。它通过在进化框架内与大型语言模型交互来创建和修改算法。我们展示了 AEL 在旅行推销员问题（TSP）的构造方法上的有效性，突出了其生成新颖和可扩展算法的能力。本文的贡献概述如下：

•

We introduce AEL, which treats each algorithm as an individual and utilizes an evolutionary framework to evolve new algorithms. Our approach integrates large language models at the algorithm design level, allowing for the creation and modification of existing search strategies with minimal expert knowledge and no domain model training.

- 我们引入了 AEL，它将每种算法视为独立个体，并利用进化框架来演化新算法。我们的方法在算法设计层面上集成了大型语言模型，允许创建和修改现有的搜索策略，只需最少的专家知识，无需领域模型训练。
•

We demonstrate AEL on designing the constructive heuristic for TSP, a well-known combinatorial optimization problem. The individual representation and prompt engineering strategies for TSP are designed.

- 我们在为 TSP（一个著名的组合优化问题）设计建设性启发式时演示了 AEL。我们设计了 TSP 的个体表示和提示工程策略。
•

We compare three algorithm design approaches (a) a greedy algorithm designed by humans (Human), (b) an algorithm learned by a specific model through time-consuming training (Domain Model), and (c) algorithms designed automatically by our proposed AEL (AEL). The comparison of these three approaches and a summary of results on TSP with different problem sizes are illustrated in Fig. 1. The results demonstrate that AEL outperforms the manually designed greedy heuristic for all problem sizes. Furthermore, AEL exhibits better generalization performance compared to training a domain model. We also highlight the superiority of AEL over directly instructing LLM (LLM) to generate algorithms. AEL benefits from the use of more advanced language models, such as GPT-4.

- 我们比较了三种算法设计方法：(a) 人类设计的贪婪算法（Human）；(b) 通过耗时的训练由特定模型学习的算法（Domain Model）；(c) 由我们提出的 AEL 自动设计的算法（AEL）。图 1 展示了这三种方法的比较以及不同问题规模的 TSP 结果摘要。结果表明，在所有问题规模下，AEL 都优于人工设计的贪婪启发式。此外，与训练领域模型相比，AEL 表现出更好的泛化性能。我们还强调了 AEL 比直接指示 LLMLLM）生成算法的优越性。使用更先进的语言模型（如 GPT-4）对 AEL 大有裨益。

The rest of this paper is structured as follows: In Section II, we provide an overview of related work in automatic algorithm design and the use of large language models in optimization. Section III presents the framework and methodology of our proposed AEL. In Section IV, we present the demonstration and experimental results on TSP and a discussion of findings followed by some suggested future directions. Section VI concludes the paper.
本文其余部分的结构如下：在第二节中，我们概述了自动算法设计和在优化中使用大型语言模型的相关工作。第三节介绍了我们提出的 AEL 的框架和方法。在第四节中，我们介绍了 TSP 的演示和实验结果，并对结论进行了讨论，随后提出了一些未来发展方向。第六节是本文的结论。

II Related Works II 相关作品

II-A Automatic Algorithm Design (AAD)
II-A 自动算法设计（AAD）

Automatic algorithm design (AAD) is an active and rapidly growing research area in heuristic design [49]. It is commonly referred to as hyper-heuristics [6, 7] or automatic design of heuristics [8]. A number of effective toolboxes and frameworks have been proposed, such as GGA [50], ParamILS [51], MO-ParamILS [52], irace [53], SMAC [54], and Optuna [55], which significantly facilitate researchers in the field. From the algorithm perspective, AAD can be briefly categorized into three main approaches: automatic algorithm configuration, automatic algorithm selection, and automatic algorithm composition [56]. Many recent research works in AAD focus on automatically generating improved algorithms using general heuristic components [8]. For example, AutoEMOA for multi-objective evolutionary optimization [57] and AutoGCOP for general-purpose optimization [56]. Despite these advancements, these approaches still require a backbone domain algorithm framework or a set of manually crafted algorithm components, and the designing process can be time-consuming.
自动算法设计（AAD）是启发式设计中一个活跃且发展迅速的研究领域[49]。它通常被称为超启发式[ 6, 7] 或启发式自动设计[ 8]。目前已经提出了许多有效的工具箱和框架，如 GGA [ 50]、ParamILS [ 51]、MO-ParamILS [ 52]、race [ 53]、SMAC [ 54] 和 Optuna [ 55]，为该领域的研究人员提供了极大的便利。从算法的角度来看，AAD 可以简要分为三种主要方法：自动算法配置、自动算法选择和自动算法组成[ 56]。最近的许多 AAD 研究工作都侧重于使用通用启发式组件自动生成改进算法[8]。例如，用于多目标进化优化的 AutoEMOA [ 57] 和用于通用优化的 AutoGCOP [ 56]。尽管取得了这些进步，但这些方法仍然需要一个骨干领域算法框架或一套人工制作的算法组件，而且设计过程可能非常耗时。

II-B Machine Learning for Optimization
II-B 机器学习促进优化

Over the past few decades, much effort has been made on the integration of machine learning techniques for optimization [58, 4, 5, 59]. Reinforcement learning techniques have been used to learn optimal algorithm configurations [9], policy for operator selection [10, 11], solution selection [12], and construction of the partial solution [60]. [61, 13, 14, 62] adopt supervised learning for solution prediction to boost heuristics and mathematical programming. Transfer learning [15, 16] and meta-learning [18, 19] have also been employed to transfer and extract knowledge from different tasks or solutions to improve optimization efficiency. Other popular directions include using surrogate models to approximate the objective functions or relations, which have been successfully applied in expensive optimization in various domains [63, 64, 65, 66, 67], and learning through genetic programming [68, 69], which is explainable and well-suited for structure representation.
在过去几十年中，人们一直致力于将机器学习技术与优化相结合[58, 4, 5, 59]。强化学习技术已被用于学习最优算法配置[9]、算子选择策略[10, 11]、解决方案选择[12]和部分解决方案的构建[60]。[61, 13, 14, 62] 采用监督学习进行解预测，以促进启发式和数学编程。转移学习[ 15, 16] 和元学习[ 18, 19] 也被用于从不同任务或解决方案中转移和提取知识，以提高优化效率。其他流行的方向包括使用代用模型来近似目标函数或关系，这种方法已成功应用于不同领域的昂贵优化[63, 64, 65, 66, 67]，以及通过遗传编程[68, 69]进行学习，这种方法可解释且非常适合结构表示。

Furthermore, recent works have explored the use of end-to-end neural solvers for both continuous optimization [20, 21, 22, 23, 24] and combinatorial optimization [25, 26, 27, 28, 29]. Some of them have been applied for EC. For example, [20, 21, 22, 23] train deep neural networks to approximate mutation, crossover, and evolutionary strategies for black-box optimization. [24] enhances evolutionary algorithms through learning from historically successful experiences. However, in spite of the promising results, they often require significant effort in designing and training the domain models.
此外，最近的研究还探索了端到端神经求解器在连续优化[20, 21, 22, 23, 24]和组合优化[25, 26, 27, 28, 29]中的应用。其中一些已应用于 EC。例如，[ 20, 21, 22, 23] 训练深度神经网络来近似黑箱优化的突变、交叉和进化策略。[ 24] 通过学习历史上的成功经验来增强进化算法。然而，尽管取得了可喜的成果，但它们往往需要花费大量精力来设计和训练领域模型。

II-C Large Language Model (LLM)
II-C 大语言模型（LLM

In the last three years, large language models (LLMs) have gained increasing power due to their exponentially growing model sizes and the availability of large training datasets. LLMs have shown remarkable performance in various research domains including natural language processing [32], programming [33], medicine [34, 35, 36], chemistry [37], chip design [38, 39], and optimization [40, 41, 42]. These LLMs excel at performing diverse tasks in a zero-shot manner [30, 31]. Despite these advancements, the practical utilization of LLMs for designing optimization algorithms is still in its early stages.
近三年来，由于大型语言模型（LLMs）的模型规模呈指数级增长，且可获得大量训练数据集，大型语言模型（LLMs）的威力与日俱增。LLMs在自然语言处理[32]、编程[33]、医学[34, 35, 36]、化学[37]、芯片设计[38, 39]和优化[40, 41, 42]等多个研究领域都表现出卓越的性能。这些LLMs擅长于以零次执行的方式完成各种任务[ 30, 31]。尽管取得了这些进展，但实际利用LLMs设计优化算法仍处于早期阶段。

II-D LLMs for Algorithm Design
II-D LLMs 算法设计

Recently, several works have demonstrated the potential of optimization solely through prompting LLM [44, 70]. [48] proposes a decomposition-based framework that integrates LLM as a black-box operator for multiobjective evolutionary optimization. In the context of single-objective evolutionary algorithms, [44, 71, 72] adopt LLM for the selection, crossover, and mutation processes. LLM has also been integrated into neural architecture design [73, 74, 46], Monte Carlo Tree Search [43] and graph-based combinatorial optimization [47]. The applications of LLM for genetic programming and open-ended tasks are discussed in [75, 45].
最近，有几项研究证明了仅通过提示LLM进行优化的潜力。[ 44, 70].[ 48]提出了一种基于分解的框架，将LLM整合为多目标进化优化的黑盒算子。在单目标进化算法中，[ 44, 71, 72] 采用LLM进行选择、交叉和突变。LLM还被集成到神经架构设计[ 73, 74, 46]、蒙特卡罗树搜索[ 43]和基于图的组合优化[ 47]中。LLM在遗传编程和开放式任务中的应用在[ 75, 45]中进行了讨论。

However, most of these works directly use LLM as optimizers, which suffers from poor generalization performance on large-scale problems. The longer solution representation and large search space, especially on combinatorial optimization problems [44, 72, 47], pose significant challenges to zero-shot generalization and in-context learning for LLM. [48] proposes to use an explainable lightweight operator to approximate the results of LLMs for better generalization in continuous optimization, which is not suitable for addressing combinatorial optimization problems.
然而，这些研究大多直接使用LLM作为优化器，在大规模问题上的泛化性能较差。较长的解表示和较大的搜索空间，尤其是在组合优化问题上[ 44, 72, 47]，给LLM的零点泛化和上下文学习带来了巨大挑战。[ 48] 提出使用可解释的轻量级算子来近似LLMs的结果，从而在连续优化中实现更好的泛化，但这并不适合解决组合优化问题。

III Algorithm Evolution using Large Language Model
III 使用大型语言模型的算法进化

III-A AEL Framework III-A AEL 框架

The proposed Algorithm Evolutionary using Large Language Model (AEL) framework embraces the common framework utilized in evolutionary computing (EC). It evolves a population of individuals and comprises fundamental components, including initialization, selection, crossover, mutation, and population management. In spite of the general evolution framework, AEL differs significantly from existing approaches.
拟议的使用大型语言模型的算法进化（AEL）框架采用了进化计算（EC）中使用的通用框架。它由初始化、选择、交叉、突变和种群管理等基本组件组成，对个体种群进行进化。尽管采用了一般的进化框架，但 AEL 与现有方法有很大不同。

•

Firstly, unlike major algorithms in EC, where individuals represent feasible solutions, each individual within our AEL framework represents an algorithm designed explicitly for a given problem. AEL evolves algorithms capable of generating novel and competitive search strategies for a target problem, rather than seeking improved solutions for specific instances.

- 首先，与 EC 中的主要算法不同（EC 中的个体代表可行的解决方案），我们的 AEL 框架中的每个个体都代表一种明确针对特定问题设计的算法。AEL 开发的算法能够为目标问题生成新颖、有竞争力的搜索策略，而不是为特定实例寻求改进的解决方案。
•

Furthermore, AEL distinguishes itself from other automatic algorithm design methods. By integrating LLMs into an evolutionary framework, the creation and refinement of algorithms occur automatically, eliminating the need for training new models or utilizing baseline algorithms. In contrast, existing automatic algorithm design methods often require expensive searches for improved algorithms or rely on specific model training.

- 此外，AEL 还有别于其他自动算法设计方法。通过将LLMs集成到进化框架中，算法的创建和改进都是自动进行的，无需训练新模型或使用基准算法。相比之下，现有的自动算法设计方法往往需要耗费巨资寻找改进算法，或依赖于特定的模型训练。

Fig. 2 illustrates the AEL flowchart and examples of algorithm crossover and algorithm mutation. AEL begins with an initialization step, where a population of $N$ individuals (algorithms), denoted as $P=\{a_{1},\dots,a_{N}\}$ , is created and evaluated. The creation of algorithms in the initializations can be either using existing algorithms or letting LLM generate algorithms. Each individual $a_{j}$ is evaluated using a fitness function, resulting in the fitness value $f(a_{j})$ . The fitness is evaluated on a branch of evaluation instances instead of on one instance.
图 2 展示了 AEL 流程图以及算法交叉和算法突变的示例。AEL 从初始化步骤开始，在初始化步骤中，一个由 $N$ 个体（算法）组成的种群被称为 $P=\{a_{1},\dots,a_{N}\}$ 。进行创建和评估。初始化中算法的创建既可以使用现有算法，也可以让LLM生成算法。每个个体 $a_{j}$ 都要使用一个适应度函数进行评估，得出适应度值 $f(a_{j})$ 。.适配度是在评估实例的分支上进行评估的，而不是在一个实例上。

The framework then proceeds with a series of iterations, for a total of $N_{g}$ generations with $N$ iterations for each generation. In each iteration, a subset of $l$ individuals $p_{j}=\{a_{1},\dots,a_{l}\}$ is selected from the population using a selection method (we select each individual with equal probability in the experiments). The selected individuals are then subjected to a crossover operation with a probability $\theta_{1}$ , resulting in a new set of $s$ individuals $o_{j}=\{a_{1},\dots,a_{s}\}$ created by LLM. The crossover operation ensures the exploration of different genetic information from the input subset $p_{j}$ .
然后，该框架进行一系列迭代，总共迭代 $N_{g}$ 代，每代迭代 $N$ 次。在每次迭代中，我们都会使用一种选择方法从种群中选出 $l$ 个个体 $p_{j}=\{a_{1},\dots,a_{l}\}$ 的子集（在实验中，我们以相等的概率选择每个个体）。然后，被选中的个体会以概率 $\theta_{1}$ 进行交叉操作，从而产生一组新的 $\theta_{1}$ 个体。产生一组新的 $s$ 个体 $o_{j}=\{a_{1},\dots,a_{s}\}$ ，由 LLM 生成。交叉操作可确保从输入子集 $p_{j}$ 中挖掘出不同的遗传信息。.

For each individual $a_{k}$ in the set $o_{j}$ , a mutation operation is applied with a probability $\theta_{2}$ . This operation modifies the input algorithm, potentially introducing a new algorithm or an algorithm with different parameters into the population. Subsequently, the fitness of each mutated individual $a_{k}$ is evaluated.
对于集合 $o_{j}$ 中的每个个体 $a_{k}$ ，以 $\theta_{2}$ 的概率进行突变操作。进行变异操作，变异概率为 $\theta_{2}$ 。.这一操作会修改输入算法，可能会在群体中引入一种新算法或参数不同的算法。随后，对每个变异个体 $a_{k}$ 的适应度进行评估。

To maintain a constant population size during the evolution process, population management is performed. The new individuals $o_{j}$ are added to the population $P$ . Afterward, the population $P$ is managed to reduce its size from $(s+1)\times N$ to $N$ by deleting the worst ones.
为了在进化过程中保持种群数量恒定，需要进行种群管理。新个体 $o_{j}$ 被加入到种群 $P$ 中。.之后，对种群 $P$ 进行管理，通过删除最差的个体，将种群数量从 $(s+1)\times N$ 减少到 $N$ 。

Ultimately, the AEL Framework aims to find the best algorithm within the given population, denoted as $a^{*}$ . By iteratively applying selection, crossover, mutation, and population management, AEL stimulates LLM to evolve a better algorithm for the optimization problem at hand.
最终，AEL 框架的目标是在给定的群体（表示为 $a^{*}$ ）中找到最佳算法。.通过迭代应用选择、交叉、变异和种群管理，AEL 可激励 LLM 针对手头的优化问题演化出更好的算法。

Input: The number of population:

N_{g}

; Population size

N

; Probability of crossover

\sigma_{1}

; Probability of mutation

\sigma_{2}

; The number of parents

l

for crossover; The number of new individuals

s

for crossover; A given LLM.
输入：种群数量：

N_{g}

；种群数量

N

；交叉概率

\sigma_{1}

；变异概率

\sigma_{2}

；交叉的亲本数量

l

；交叉的新个体数量

s

；给定的 LLM.

Output: Best algorithm

a^{*}

.
输出：最佳算法

a^{*}

Initialization: for $j=1,\dots,N$ do
初始化： for

j=1,\dots,N

Algorithm Creation: create new individual

a_{j}

given the target problem using LLM; Evaluate

a_{j}

and get fitness value

f(a_{j})

;
算法创建：使用 LLM 给定目标问题，创建新个体

a_{j}

；评估

a_{j}

并获取适应度值

f(a_{j})

；

Construct initial population

P=\{a_{1},\dots,a_{N}\}

; for $i=1,\dots,N_{g}$ do
构建初始种群

P=\{a_{1},\dots,a_{N}\}

；对于

i=1,\dots,N_{g}

做

for $j=1,\dots,N$ do 对于

j=1,\dots,N

做

Selection: select a subset of input individuals

p_{j}=\{a_{1},\dots,a_{l}\}

; Algorithm Crossover with probability

\theta_{1}

: create individual

o_{j}=\{a_{1},...,a_{s}\}

using LLM given the target problem and input subset

p_{j}

; for $k=1,\dots,s$ do
选择：选择一个输入个体子集

p_{j}=\{a_{1},\dots,a_{l}\}

；算法交叉概率

\theta_{1}

：使用 LLM 创建个体

o_{j}=\{a_{1},...,a_{s}\}

，给定目标问题和输入子集

p_{j}

；对于

k=1,\dots,s

执行

Algorithm Mutation with probability

\theta_{2}

: modify individual

a_{k}

using LLM; Evaluate

a_{k}

and get fitness value

f(a_{k})

;
算法突变概率

\theta_{2}

：使用LLM修改个体

a_{k}

；评估{{2}，得到适应度值

f(a_{k})

；

Population management:

P=P\cup\{o_{1},...,o_{N}\}

, manage population

P

to reduce the size from

(s+1)\dot{N}

N

.
人口管理：

P=P\cup\{o_{1},...,o_{N}\}

，管理{{1}种群，将其数量从

(s+1)\dot{N}

减少到

N

。.

Algorithm 1 AEL Framework
算法 1 AEL 框架

III-B Individual Representation
III-B 个人代表

Unlike previous works, our proposed AEL approach represents each individual as an algorithm tailored to the specific problem. Each individual consists of three components: 1) a description of the algorithm in natural language, 2) a code block in a pre-defined format, and 3) a fitness value.
与以往的研究不同，我们提出的 AEL 方法将每个个体都视为针对特定问题量身定制的算法。每个个体由三个部分组成：1) 算法的自然语言描述；2) 预定义格式的代码块；3) 适应度值。

The algorithm description comprises a few sentences in natural language that can be easily processed by LLM. The code block should follow a predefined format so that it can be identified and seamlessly integrated into our AEL framework. We introduce the four basic components that should be included in the prompt engineering to format the code block:
算法描述由几句自然语言组成，便于 LLM 处理。代码块应遵循预定义格式，以便识别并无缝集成到我们的 AEL 框架中。我们将介绍提示工程中应包含的四个基本组件，以便对代码块进行格式化：

•

Name of class or function: The name of the class or function must be standardized to ensure easy identification by the main program.

- 类或函数的名称：类或函数的名称必须标准化，以确保主程序易于识别。
•

Input: The number and names of input variables need to be provided, along with their types and their characters in the program. This information helps LLM understand the available information and design a viable algorithm based on it.

- 输入：需要提供输入变量的数量和名称，以及它们在程序中的类型和字符。这些信息有助于 LLM 理解可用信息，并据此设计可行的算法。
•

Output: The number and names of output variables should also be defined, along with their types and their utilization.

- 输出：还应定义输出变量的数量和名称，以及它们的类型和用途。
•

Other hints: we expect the response to be innovative, and want to avoid too many explanations and code comments, which might lead to failure identification and increase the response time and cost. Any other problem-specific hints should also be included in the prompt.

- 其他提示：我们希望回复具有创新性，并希望避免过多的解释和代码注释，因为这可能会导致故障识别，并增加回复时间和成本。任何其他针对具体问题的提示也应包含在提示中。

The evaluation of individuals in AEL involves running the algorithms on an evaluation instance set of the target problem. This evaluation process differs from traditional evolutionary computing, which typically evaluates the objective function for a single instance, but is closer to AAD methods [51, 53, 54].
AEL 中的个体评估包括在目标问题的评估实例集上运行算法。这一评估过程不同于传统的进化计算，传统的进化计算通常只对单个实例的目标函数进行评估，但这一评估过程更接近于 AAD 方法[51, 53, 54]。

III-C Initilization III-C 启动

The initial population can be either constructed by using existing manually crafted algorithms or created using LLM. In our experiments, we choose to let LLM create all the initial algorithms to eliminate the use of expert knowledge. We provide the following guidelines for prompt engineering for algorithm creation using LLMs. The prompt should include the following three parts:
初始算法群既可以使用现有的人工算法构建，也可以使用LLM创建。在实验中，我们选择让LLM创建所有初始算法，以避免使用专家知识。我们为使用LLMs创建算法的提示工程提供了以下指导。提示应包括以下三个部分：

•

A description of the task: A description of the optimization task. The description should be a concise but comprehensive introduction to the target problem.

- 任务描述：对优化任务的描述。描述应简明而全面地介绍目标问题。
•

An expected output: A description of the expected responses that we want. We desire both a description of the new algorithm and a corresponding code block with pre-defined inputs and outputs. The responses should be provided in a specific format.

- 预期输出：描述我们想要的预期响应。我们既希望得到新算法的描述，也希望得到相应的代码块，并预设输入和输出。响应应该以特定格式提供。
•

Initialization-specific hints: We prioritize the inclusion of diverse algorithms during the initialization process, thus emphasizing the development of a novel algorithm that distinguishes itself from those in the literature. We may also encourage more randomness and diversity by explicitly instructing the LLM to be creative.

- 针对初始化的提示：在初始化过程中，我们优先考虑纳入各种算法，从而强调开发一种有别于文献中的新颖算法。我们还可以通过明确指示LLM发挥创造力，鼓励更多的随机性和多样性。

We run the prompting procedure for $N$ times to generate $N$ initial algorithms.
我们运行提示程序 $N$ 次，生成 $N$ 个初始算法。

III-D Selection III-D 选择

We simply select input $l$ algorithms randomly from the population $P$ . This selection strategy aligns with the conventional EC. The difference is that The number of selected individuals in our framework is scalable, as the LLM takes prompt in a flexible manner. This scalability is only limited by the maximum input token size depending on the adopted LLM.
我们只需从群体 $P$ 中随机选择输入 $l$ 算法。.这种选择策略与传统的 EC 相一致。不同之处在于，在我们的框架中，由于LLM会以灵活的方式进行提示，因此所选个体的数量是可扩展的。这种可扩展性仅受到最大输入标记大小的限制，具体取决于所采用的LLM。

III-E Crossover III-E 交叉装置

For the $j$ -th iteration, the input of crossover consists of a set of $l$ selected individuals, denoted as $p_{j}=\{a_{1},\dots,a_{l}\}$ , and the output is a new set of $s$ individuals, denoted as $o_{j}=\{a_{1},\dots,a_{s}\}$ . The process of prompt engineering for crossover involves using the target problem and the selected individuals to generate a prompt for LLM, which in turn creates new algorithms. The prompt itself is a combination of natural language and code and is structured into four parts:
对于 $j$ 对于 $j$ -次迭代，交叉的输入是一组 $l$ 选中的个体，记为 $p_{j}=\{a_{1},\dots,a_{l}\}$ ，输出是一组新的 $s$ 个体，记为 $o_{j}=\{a_{1},\dots,a_{s}\}$ 。输出是一组新的 $s$ 个体，记为 $o_{j}=\{a_{1},\dots,a_{s}\}$ 。.交叉的提示工程包括利用目标问题和所选个体生成LLM的提示，进而创建新的算法。提示本身是自然语言和代码的结合，分为四个部分：

•

A description of the task: It is identical to that used during initialization.

- 任务描述：与初始化时使用的描述相同。
•

Parent algorithms: It comprises a set of $l$ input parent individuals. For each individual, both the algorithm description and code are provided.

- 父代算法：它由一组 $l$ 输入父个体组成。每个个体都有算法描述和代码。
•

An expected output: It includes a description of the desired responses in a specific format.

- 预期输出：它包括以特定格式描述所需的回复。
•

Crossover-specific hints: It emphasizes the need for the new algorithm to draw motivation from the parent algorithms while still being distinct from them.

- 交叉特定提示：它强调新算法需要从父代算法中汲取动力，同时又要与父代算法有所区别。

III-F Mutation III-F 突变

In mutation, the input algorithm is modified using LLM to create a new algorithm. The engineering approach for mutation involves using the target problem and one input individual to generate a prompt that allows for the modification of the input algorithm with LLM. The prompt consists of a combination of natural language and code, and it includes the following four components:
在突变过程中，输入算法会被LLM修改，从而产生新的算法。突变的工程方法包括使用目标问题和一个输入个体生成一个提示，允许使用LLM修改输入算法。提示由自然语言和代码组合而成，包括以下四个部分：

•

A description of the task: It is identical to that used during initialization.

- 任务描述：与初始化时使用的描述相同。
•

A parent algorithm: Only one input parent individual. Both the algorithm description and code are provided.

- 父代算法只有一个输入的父个体。提供算法描述和代码。
•

An expected output: A description of the expected responses we want. The responses should be given in a specific format.

- 预期输出：描述我们希望得到的预期响应。这些回复应以特定格式给出。
•

Mutation-specific hints: It emphasizes that the new algorithm should be a revision of the input algorithm.

- 针对突变的提示：它强调新算法应是对输入算法的修正。

III-G Population Management
III-G 人口管理

In population management, we remove the worst individuals in terms of fitness value to reduce the population size from $(s+1)N$ to $N$ .
在种群管理中，我们会剔除健康值最差的个体，从而将种群数量从 $(s+1)N$ 减少到 $N$ 。.

IV Demonstration on TSP
IV TSP 演示

The traveling salesman problem (TSP) is one of the most important combinatorial optimization problems. The problem is to find the shortest route to visit all the given locations once and return to the starting location. It is recognized as NP-hard and is usually solved using heuristic algorithms. Among different heuristics [76], constructive heuristics are flexible and easy to implement. In constructive heuristics, the solution is constructed step-by-step by choosing the next node given the current node and the destination node. This autoregressive manner is also used by many recent works on learning a domain neural model for combinatorial optimization [25, 77].
旅行推销员问题（TSP）是最重要的组合优化问题之一。问题是找到一条最短的路线，访问所有给定地点一次，然后返回起始地点。该问题被公认为 NP 难，通常采用启发式算法求解。在不同的启发式算法中[76]，构造式启发式算法灵活且易于实现。在构造启发式算法中，解法是通过给定当前节点和目的地节点，选择下一个节点来逐步构建的。这种自回归方式也被最近许多关于组合优化领域神经模型学习的研究成果所采用[25, 77]。

We adopt the same constructive framework to iteratively choose the next node. The task for AEL in this case is to create a novel and competitive algorithm to choose the next node.
我们采用相同的构造框架来迭代选择下一个节点。在这种情况下，AEL 的任务是创建一种新颖、有竞争力的算法来选择下一个节点。

IV-A AEL Implementation IV-A AEL 的实施

AEL is a general framework for algorithm design. For a target problem like TSP, we only need to implement the problem-specific parts. i.e., the individual representation and the prompting engineering for initialization, crossover, and mutation.
AEL 是算法设计的通用框架。对于像 TSP 这样的目标问题，我们只需要实现特定问题的部分，即个体表示和初始化、交叉和突变的提示工程。

IV-A1 Individual Representation
IV-A1 个人代表

The objective of AEL is to evolve an algorithm that identifies the next node based on problem information and the current state. As mentioned previously, each individual in AEL comprises three components: 1) an algorithm description, 2) a code block, and 3) a fitness value. Fig 3 presents an example of the individual representation of the greedy algorithm, which selects the next node that is the nearest one to the current node.
AEL 的目标是发展一种算法，根据问题信息和当前状态确定下一个节点。如前所述，AEL 中的每个个体都由三个部分组成：1) 算法描述；2) 代码块；3) 适应度值。图 3 展示了贪婪算法的个体表示示例，该算法选择离当前节点最近的下一个节点。

The algorithm description is presented in a natural language format. To avoid a noisy long response, we explicitly inform the LLM that the algorithm description should not exceed two sentences. It is important to note that, in more complex tasks, a longer sentence limitation can be adopted. In addition to it, we pose no additional limitations.
算法描述以自然语言格式呈现。为避免冗长的回复造成干扰，我们明确告知LLM，算法描述不应超过两句话。值得注意的是，在更复杂的任务中，可以采用更长的句子限制。除此之外，我们没有其他限制。

The code is a Python function named ”select_next_node”, which takes inputs including the current node, destination node, unvisited nodes, and distance matrix, and outputs the next selected node.
代码是一个名为 "select_next_node "的 Python 函数，它接受的输入包括当前节点、目的地节点、未访问节点和距离矩阵，并输出下一个选定的节点。

The fitness value is evaluated using a set of 64 randomly generated TSP instances of size 50. The fitness is calculated as the average gap to the commercial solver Gurobi. Smaller values indicate better fitness.
适配度值使用一组随机生成的 64 个 TSP 实例（大小为 50）进行评估。适配度按与商业解算器 Gurobi 的平均差距计算。数值越小，表示适应度越高。

IV-A2 Prompt Engineering for Initialization, Crossover, and Mutation
IV-A2 初始化、交叉和突变提示工程

The details are illustrated in Fig. 4. The five different colors represent five different components including A description of task, Parent algorithm(s), Prompt-specific hints, An expected output, and Other hints.
详情如图 4 所示。五种不同的颜色代表五个不同的组成部分，包括任务描述、父算法、特定提示、预期输出和其他提示。

The task involves developing a new strategy for selecting the next node at each step, which remains consistent across all three prompts. Only crossover and mutation include parent algorithms in the prompts. Regarding prompt-specific hints, we instruct the LLM to create a completely new algorithm during initialization, while in crossover and mutation, the algorithm should be inspired by and modified from the parent algorithm(s). This description aligns with the respective functions of each component in the evolutionary framework: the desire for diverse algorithms in the initial population and the expectation that newly created algorithms during evolution will inherit certain aspects from their parents. The format of the expected output remains almost identical for all three prompts. We explicitly define the name, input, and output of the code block for easy identification by the AEL framework. Additionally, we include other hints to emphasize innovation and discourage the need for extra explanations for efficiency and robustness.
任务包括开发一种新策略，用于在每一步选择下一个节点，该策略在所有三个提示中都保持一致。只有交叉和变异在提示中包含了父算法。关于特定提示，我们指示LLM在初始化过程中创建一个全新的算法，而在交叉和突变中，算法应受到父算法的启发并对其进行修改。这种描述符合进化框架中每个组件的各自功能：希望初始种群中的算法多样化，并期望在进化过程中新生成的算法能继承父代算法的某些方面。这三个提示的预期输出格式几乎完全相同。我们明确定义了代码块的名称、输入和输出，以便 AEL 框架轻松识别。此外，我们还加入了其他提示，以强调创新性，并抑制对效率和稳健性的额外解释。

IV-B Experiments IV-B 实验

IV-B1 Experimental Settings
IV-B1 实验设置

The experiments are carried out on 64 randomly generated TSP50 instances, i.e., each algorithm is evaluated on 64 TSP50 instances and the fitness value is the average gap to the optimal solution generated by Gurobi. The experimental settings for AEL are as follows:
实验在 64 个随机生成的 TSP50 实例上进行，即每种算法在 64 个 TSP50 实例上进行评估，适应度值是与 Gurobi 生成的最优解的平均差距。AEL 的实验设置如下：

•

Population size $N$ : 10

- 人口数量 $N$ : 10
•

Number of population $N_{g}$ : 10

- 人口数量 $N_{g}$ : 10
•

Probability for crossover $\sigma_{1}$ : 1.0

- 交叉概率 $\sigma_{1}$ : 1.0
•

Probability for mutation $\sigma_{2}$ : 0.2

- 突变概率 $\sigma_{2}$ : 0.2
•

Number of parent individuals $l$ : 2

- 父个体的数量 $l$ : 2
•

Number of offspring individuals $s$ : 1

- 后代个体数量 $s$ : 1
•

LLM: GPT-3.5-turbo and GPT-4

- LLM:GPT-3.5-涡轮增压和 GPT-4

We compared our AEL method to three kinds of existing algorithm design approaches. Note that there are countless works using other frameworks. We compare the methods that follow the same step-by-step constructive framework as that used for AEL. We are able to further promote the performance by applying AEL in other advanced frameworks.
我们将 AEL 方法与现有的三种算法设计方法进行了比较。请注意，使用其他框架的作品数不胜数。我们比较了与 AEL 采用相同的逐步构造框架的方法。通过在其他先进框架中应用 AEL，我们能够进一步提高性能。

The three compared approaches as well as the methods are:
比较的三种方式和方法是

•

Algorithm design by humans: Greedy search (Greedy), which selects the nearest node as the next node.

- 人工设计算法：贪婪搜索（Greedy），选择最近的节点作为下一个节点。
•

Algorithm design using domain model: Neural combinatorial optimization (Domain model), which trains a neural network to learn the heuristic for selecting the next node. In this study, we adopt POMO [77], a widely employed neural solver baseline. We train it on TSP50 using exactly the same settings as in the original paper [77]. The training costs about four days.

- 利用领域模型进行算法设计：神经组合优化（领域模型），通过训练神经网络来学习选择下一个节点的启发式。在本研究中，我们采用了 POMO [ 77]，这是一种广泛使用的神经求解器基线。我们使用与原论文[ 77] 完全相同的设置在 TSP50 上对其进行训练。训练耗时约四天。
•

Algorithm design using LLM: LLM with prompt engineering (LLM). We directly generate a novel algorithm by instructing LLM. The prompt is the same as that used in the initialization stage of AEL.

- 使用 LLM 进行算法设计：LLM与提示工程（LLM）。我们通过 LLM 直接生成新算法。该提示与 AEL 初始化阶段使用的提示相同。
•

AEL: Our proposed AEL.

- AEL：我们建议的 AEL。

IV-B2 Experimental Results
IV-B2 实验结果

Fig 5 illustrates the convergence process of the proposed AEL using GPT-4 on the TSP50 dataset. The y-axis represents the gap (%) to the optimal solution and the x-axis represents the number of generations. Each blue data point represents an algorithm created by AEL during the evolution. The orange and red lines depict the convergence curves of the mean and best objective values, respectively, in each population. The black line represents the greedy algorithm designed by humans.
图 5 展示了在 TSP50 数据集上使用 GPT-4 的拟议 AEL 的收敛过程。y 轴表示与最优解的差距（%），x 轴表示代数。每个蓝色数据点代表 AEL 在演化过程中创建的算法。橙线和红线分别描述了每个种群中平均目标值和最佳目标值的收敛曲线。黑线代表人类设计的贪婪算法。

It can be observed that there is a clear convergence in terms of both the mean and best objective values as the evolution progresses. AEL nearly converges in 10 generations, and the optimal gap is reduced from 20% to around 12%. The best algorithm generated by GPT-4 in the first population is close to the greedy algorithm, while AEL clearly beats the greedy algorithm towards the end of evolution.
可以看出，随着进化的进行，平均值和最佳目标值都有明显的收敛。AEL 在 10 代内几乎收敛，最佳差距从 20% 缩小到 12% 左右。GPT-4 在第一个群体中产生的最佳算法与贪婪算法接近，而 AEL 在进化末期明显优于贪婪算法。

As illustrated in Fig. 6, the best algorithm created by AEL is significantly more complicated than the greedy algorithm. It selects the next node considering various factors such as its distance to other unvisited nodes, mean distance, and standard deviation of these distances. The algorithm assigns a higher weight to close clusters of nodes by incorporating the standard deviation into the scoring system. Additionally, the algorithm includes a conditional statement that ensures nodes far from the rest are not chosen prematurely by selecting the closest node when the minimum calculated score exceeds a specified threshold. The created Python code block employs the NumPy library for calculations. The code starts with defining the select_next_node function, which takes the current_node, destination_node, unvisited_nodes, distance_matrix, and an optional threshold parameter. Inside the function, a dictionary called scores is created to store the scores for each unvisited node. The algorithm iterates through each node in the unvisited_nodes list and calculates the score based on the provided formula. The minimum score is then compared to the specified threshold, and based on the result, the next_node is determined. Finally, the function returns the selected next_node.
如图 6 所示，AEL 创建的最佳算法比贪婪算法复杂得多。它在选择下一个节点时会考虑各种因素，如节点与其他未访问节点的距离、平均距离以及这些距离的标准偏差。该算法通过将标准偏差纳入评分系统，为距离较近的节点群赋予更高的权重。此外，该算法还包含一个条件语句，当计算出的最小得分超过指定阈值时，通过选择最近的节点，确保不会过早选择远离其他节点的节点。创建的 Python 代码块使用 NumPy 库进行计算。代码首先定义了 select_next_node 函数，该函数接受 current_node、destination_node、unvisited_nodes、distance_matrix 和一个可选的阈值参数。函数内部创建了一个名为 scores 的字典，用于存储每个未访问节点的分数。算法会遍历未访问节点列表中的每个节点，并根据提供的公式计算得分。然后将最小得分与指定阈值进行比较，并根据结果确定下一个节点。最后，函数返回选定的 next_node。

The automatically designed best algorithm by AEL presents a sophisticated strategy incorporating an additional threshold parameter (not explicitly given in the prompt) and a complex scoring function. The scoring function integrates multiple factors along with four hyperparameters, which presents a challenge, even for an expert, without substantial trial-and-error testing. In contrast, AEL automatically develops the algorithm through an iterative process involving 100 interactions with LLM.
AEL 自动设计的最佳算法提出了一个复杂的策略，其中包含一个额外的阈值参数（提示中没有明确给出）和一个复杂的评分函数。评分函数综合了多个因素和四个超参数，即使是专家，在没有大量试错测试的情况下也会面临挑战。相比之下，AEL 通过与 LLM 进行 100 次交互的迭代过程自动开发算法。

IV-B3 Evaluation of Optimized Algorithm
IV-B3 优化算法评估

We evaluate the best algorithm designed by AEL on various TSP instances with multiple problem sizes and compared the results to other algorithm design approaches. Table I shows the performance of algorithms designed using different approaches on TSP20 to TSP1000. The results are averaged on 64 randomly generated instances. Apart from the total distance, we also measured the average gap in relation to the baseline solver LKH3. Fig. 1 provides a more intuitive comparison of the average gap vs. the problem size of different algorithm design approaches.
我们在多种问题规模的 TSP 实例上评估了 AEL 设计的最佳算法，并将结果与其他算法设计方法进行了比较。表 I 显示了使用不同方法设计的算法在 TSP20 到 TSP1000 上的性能。结果是 64 个随机生成实例的平均值。除了总距离，我们还测量了与基准求解器 LKH3 的平均差距。图 1 提供了不同算法设计方法的平均差距与问题规模的更直观比较。

TABLE I: Evaluation of algorithms designed by different approaches on TSP20-TSP1000.
表 I：在 TSP20-TSP1000 上对不同方法设计的算法进行的评估。

Algorithms 算法		20		50		100		200		500		1000
Algorithms 算法		Dis.	Gap. 差距。	Dis.	Gap. 差距。	Dis.	Gap. 差距。	Dis.	Gap. 差距。	Dis.	Gap. 差距。	Dis.	Gap. 差距。
Baseline (SOTA Solver LKH3) 基线（SOTA 解算器 LKH3）		3.84	/	5.69	/	7.77	/	10.73	/	16.56	/	23.08	/
Human (Greedy) 人类（贪婪）		4.49	17.0%	7.01	23.1%	9.84	26.6%	13.50	25.8%	20.87	26.0%	28.90	25.2%
Domain Model 领域模型		3.86	0.6%	5.71	0.4%	8.01	3.0%	13.02	21.3%	24.34	47.0%	36.53	58.3%
LLM (Average) LLM(平均值）	GPT-3.5-turbo GPT-3.5 涡轮增压发动机	5.04	31.3%	7.56	32.8%	10.62	36.7%	14.35	33.7%	22.04	33.1%	30.05	30.2%
	GPT-4	7.45	94.2%	14.97	162.9%	24.87	220.1%	37.36	248.0%	61.73	272.8%	86.26	273.8%
LLM (Best) LLM(最佳)	GPT-3.5-turbo GPT-3.5 涡轮增压发动机	4.61	20.3%	6.71	17.9%	10.01	28.9%	13.31	24.0%	20.83	25.8%	28.98	25.6%
	GPT-4	4.36	13.6%	6.82	19.7%	9.95	28.1%	13.94	29.9%	22.07	33.3%	30.36	31.6%
AEL (Ours) AEL （我们的）	GPT-3.5-turbo GPT-3.5 涡轮增压发动机	4.26	11.2%	6.65	16.8%	9.32	20.0%	13.07	21.8%	20.38	23.1%	28.34	22.8%
AEL (Ours) AEL （我们的）	GPT-4	4.07	6.2%	6.33	11.1%	8.58	10.5%	11.94	11.2%	18.67	12.8%	26.03	12.8%

•

AEL outperforms the simple Greedy algorithm designed by humans in all problem sizes. The average gap is reduced by half from 17.0% to 6.2% and from 25.2% to 12.8% for TSP20 and TSP1000, respectively.

- 在所有大小的问题中，AEL 都优于人类设计的简单 Greedy 算法。在 TSP20 和 TSP1000 中，平均差距缩小了一半，分别从 17.0% 降至 6.2%，从 25.2% 降至 12.8%。
•

AEL demonstrates significantly better generalization performance across various problem sizes when compared to the domain model. The domain model is trained and overfitted on TSP50, whereas AEL presents a much more robust solution. Although the domain model surpasses AEL in problem sizes close to the training data, its performance rapidly deteriorates on large-scale problems. The average gap increases dramatically from less than 1% to over 50%.

- 与领域模型相比，AEL 在不同大小的问题上都表现出明显更好的泛化性能。在 TSP50 问题上，领域模型经过了训练和过度拟合，而 AEL 则提供了更稳健的解决方案。虽然领域模型在接近训练数据的问题规模上超越了 AEL，但在大规模问题上，其性能迅速下降。平均差距从不到 1%急剧增加到超过 50%。
•

AEL also outperforms directly instructing LLM to design algorithms. LLM (Average) and LLM (Best) represent the average and best of ten algorithms directly generated by instructing LLM. The best LLM algorithm is competitive to the greedy algorithm but evidently inferior to AEL. Interestingly, the best gap achieved by LLM with GPT-4 is inferior to GPT-3.5-turbo. An explanation for this is that GPT-4 is more powerful but can also be overly innovative with excessive randomness. Consequently, the algorithms directly generated by GPT-4 could be considerably worse.

- AEL 还优于直接指导 LLM 设计算法。LLM(平均）和 LLM （最佳(最佳）分别代表通过指导LLM直接生成的十种算法的平均值和最佳值。最佳LLM算法与贪心算法相比具有竞争力，但显然不如 AEL 算法。有趣的是，LLM 使用 GPT-4 算法取得的最佳差距不如 GPT-3.5-turbo。对此的一种解释是，GPT-4 功能更强大，但也可能因随机性过强而过于创新。因此，由 GPT-4 直接生成的算法可能会差很多。
•

We also want to note that the demonstration is conducted based on a basic constructive heuristic framework. Our comparison involves the algorithm created by AEL, a greedy algorithm, and a domain model, all using the same step-by-step constructive framework. However, there are numerous other complex algorithms capable of generating near-optimal solutions for TSP [78]. Additionally, recent neural solvers specifically designed for large-scale TSP have also demonstrated good generalization performance [27, 79, 28]. Advanced frameworks can be integrated to promote performance in the future.

- 我们还想指出，演示是基于一个基本的构造性启发式框架进行的。我们的比较涉及 AEL 创建的算法、贪婪算法和领域模型，它们都使用了相同的逐步构造框架。然而，还有许多其他复杂算法能够为 TSP 生成接近最优的解决方案[78]。此外，最近专为大规模 TSP 设计的神经求解器也表现出良好的泛化性能[27, 79, 28]。未来可以集成先进的框架来提高性能。

Fig 7 compares the routes generated using the greedy algorithm and algorithms developed by AEL, utilizing GPT-3.5-turbo and GPT-4, on TSP100, TSP500, and TSP1000 instances. The scatter plot nodes represent locations, with the blue lines indicating the routes generated by different algorithms. The numbers displayed above the scatter plot indicate the sequence in which the locations appear in the route. The starting and ending locations are marked in red. The results demonstrate that the algorithms designed by AEL produce superior routes with fewer intersections than the greedy algorithm, resulting in shorter total distances. Additionally, the starting and ending nodes are closer together compared to the greedy algorithm. AEL using GPT-4 outperforms AEL using GPT-3.5-turbo.
图 7 比较了在 TSP100、TSP500 和 TSP1000 实例上使用贪婪算法和 AEL 开发的算法（利用 GPT-3.5-turbo 和 GPT-4）生成的路线。散点图节点表示位置，蓝线表示不同算法生成的路线。散点图上方显示的数字表示位置在路线中出现的顺序。起点和终点位置用红色标出。结果表明，与贪婪算法相比，AEL 设计的算法生成的路线具有更少的交叉点，从而缩短了总距离。此外，与贪婪算法相比，起点和终点节点的距离更近。使用 GPT-4 的 AEL 优于使用 GPT-3.5-turbo 的 AEL。

IV-C Created Algorithms or Spliced Algorithms
IV-C 创建算法或拼接算法

It is debatable whether the LLM can genuinely comprehend and generate new knowledge or if it simply searches and combines various existing information [80]. As the TSP is a well-studied combinatorial optimization problem with numerous publicly available resources and research papers, it is possible that the LLM merely selects or splices existing algorithms [81]. However, the majority of the algorithms created in our AEL framework cannot be found on the web or in publications. The comparison between AEL algorithms and LLM algorithms also demonstrates that AEL stimulates the creation of novel algorithms to a noteworthy extent by combining evolutionary computing and LLM.
LLM能否真正理解并产生新知识，还是仅仅搜索并组合各种现有信息，这一点尚存争议[ 80]。由于TSP是一个经过深入研究的组合优化问题，拥有大量公开资源和研究论文，因此LLM有可能只是选择或拼接了现有算法[ 81]。然而，在我们的 AEL 框架中创建的大多数算法都无法在网络或出版物中找到。AEL算法与LLM算法之间的比较也表明，AEL通过将进化计算与LLM相结合，在很大程度上激发了新算法的创造。

IV-D Less/No Expert Knowledge
IV-D 缺乏/没有专家知识

AEL requires minimal expert knowledge about the target problem. For designers using our AEL framework, the primary workload lies in designing the prompt engineering for each component for the target problem. The prompt engineering is presented in a natural language format, making it accessible to algorithm designers from diverse backgrounds.
AEL 对目标问题的专家知识要求极低。对于使用我们的 AEL 框架的设计人员来说，主要的工作量在于为目标问题的每个组件设计提示工程。提示工程以自然语言格式呈现，使来自不同背景的算法设计人员都能使用。

V Future Works V 未来作品

•

AEL with tools: Equipping LLMs with external tools significantly enhances the capabilities of the model [82, 83, 84]. There are numerous well-crafted existing optimization algorithms, which can be integrated as effective tools. This approach provides a more flexible and robust framework as opposed to relying solely on LLM for algorithm evolution. We can also integrate other heuristic frameworks into AEL. For example, landscape updating for guided local search [85], improve large neighborhood search [86], and Tabu search [87].

- 带有工具的 AEL：为LLMs配备外部工具可大大增强模型的功能[82, 83, 84]。目前有许多精心设计的优化算法，可以将其整合为有效的工具。与单纯依赖LLM进行算法演化相比，这种方法提供了一个更加灵活和稳健的框架。我们还可以将其他启发式框架整合到 AEL 中。例如，用于引导局部搜索的景观更新[85]、改进大邻域搜索[86]和塔布搜索[87]。
•

AEL with additional information: Another interesting direction is to provide additional information as the input for LLM during the optimization process. The information can be in the form of history search trajectories, external archives, and rewards obtained during optimization [88, 89]. With more available information, AEL is able to evolve more powerful algorithms.

- AEL 的附加信息：另一个有趣的方向是在优化过程中提供额外信息作为 LLM 的输入。这些信息可以是历史搜索轨迹、外部档案以及优化过程中获得的奖励[88, 89]。有了更多可用信息，AEL 就能发展出更强大的算法。
•

AEL for complex optimization problems: Complex problems pose challenges for AEL as they are difficult for LLMs to comprehend, which is even challenging for humans. In such cases, it is possible to decompose the problem into simpler tasks and adopt LLMs for each task [90]. A possible solution is to separate the algorithm description and coding and evolve in a hierarchical way, i.e., evolve on the algorithm and then generate code for each algorithm. Refinement techniques [91, 92, 93] can be applied to reduce the failure rate.

- 针对复杂优化问题的 AEL：复杂问题给 AEL 带来了挑战，因为LLMs 很难理解这些问题，这甚至对人类也是挑战。在这种情况下，可以将问题分解为更简单的任务，并对每个任务采用LLMs[ 90]。一种可行的解决方案是将算法描述和编码分开，以分层的方式进行演化，即先演化算法，然后为每种算法生成代码。精炼技术[91, 92, 93]可用于降低失败率。
•

Multi-objective AEL: The current focus of AEL is mainly on single-objective optimization problems. However, many real-world problems are multi-objective in nature, where multiple conflicting objectives need to be simultaneously considered. As AEL is algorithm-agnostic, we can easily extend AEL to handle multi-objective optimization problems using multi-objective optimization algorithms [94]. Multi-objective AEL finds trade-off algorithms that satisfy multiple objectives, which can be particularly useful in real-world decision-making scenarios [57].

- 多目标 AEL：AEL 目前主要关注单目标优化问题。然而，现实世界中的许多问题本质上都是多目标问题，需要同时考虑多个相互冲突的目标。由于 AEL 与算法无关，我们可以使用多目标优化算法轻松扩展 AEL 以处理多目标优化问题[94]。多目标 AEL 可以找到满足多个目标的权衡算法，这在现实世界的决策场景中特别有用[57]。

VI Conclusion VI 结束语

This paper introduces a novel approach called Algorithm Evolution with Large Language Model (AEL) for automatic algorithm design. By utilizing a large language model (LLM), AEL automates the generation of optimization algorithms using an evolutionary framework. It significantly reduces the need for expertise knowledge and domain model training.
本文介绍了一种名为 "大语言模型算法进化"（AEL）的自动算法设计新方法。通过利用大型语言模型（LLM），AEL 利用进化框架自动生成优化算法。它大大减少了对专业知识和领域模型训练的需求。

We have demonstrated the effectiveness of AEL on the constructive method for TSP. Results on TSP instances with problem sizes ranging from 20 to 1000 show that the algorithm generated by AEL outperforms the simple hand-crafted greedy algorithm and the algorithms generated by directly instructing LLMs. It also exhibits excellent scalability across different problem sizes compared to training a domain neural model. Future works on the integration of AEL with more advanced algorithm frameworks could lead to even more powerful algorithms.
我们证明了 AEL 在 TSP 的构造方法上的有效性。在问题规模为 20 到 1000 的 TSP 实例上的结果表明，AEL 生成的算法优于简单的手工贪婪算法和直接指示 LLMs 生成的算法。与训练领域神经模型相比，它还在不同问题规模下表现出出色的可扩展性。未来，将 AEL 与更先进的算法框架进行整合的工作可能会产生更强大的算法。

References 参考资料

[1] J. Nocedal and S. J. Wright, Numerical optimization. Springer, 1999.
J. Nocedal 和 S. J. Wright，《数值优化》。Springer, 1999.
[2] F. W. Glover and G. A. Kochenberger, Handbook of metaheuristics. Springer Science & Business Media, 2006, vol. 57.
F. W. Glover 和 G. A. Kochenberger，《元启发式计算手册》。Springer Science & Business Media, 2006, vol. 57.
[3] K. Deb, Optimization for engineering design: Algorithms and examples. PHI Learning Pvt. Ltd., 2012.
K. Deb, Optimization for engineering design：算法与实例》。PHI Learning Pvt. Ltd., 2012.
[4] T. Chen, X. Chen, W. Chen, Z. Wang, H. Heaton, J. Liu, and W. Yin, “Learning to optimize: A primer and a benchmark,” The Journal of Machine Learning Research, vol. 23, no. 1, pp. 8562–8620, 2022.
T. Chen, X. Chen, W. Chen, Z. Wang, H. Heaton, J. Liu, and W. Yin, "Learning to optimize：机器学习研究》，第 23 卷第 1 期，第 8562-8620 页，2022 年。
[5] X. He, K. Zhao, and X. Chu, “Automl: A survey of the state-of-the-art,” Knowledge-Based Systems, vol. 212, p. 106622, 2021.
X. He, K. Zhao, and X. Chu, "Automl：基于知识的系统》，第 212 卷，第 106622 页，2021 年。
[6] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, vol. 64, pp. 1695–1724, 2013.
E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu, "Hyper-heuristics：A survey of the state of the art," Journal of the Operational Research Society, vol. 64, pp.
[7] E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward, “A classification of hyper-heuristic approaches: revisited,” Handbook of metaheuristics, pp. 453–477, 2019.
E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward, "A classification of hyper-heuristic approaches: revisited," Handbook of metaheuristics, pp.
[8] T. Stützle and M. López-Ibáñez, “Automated design of metaheuristic algorithms,” Handbook of metaheuristics, pp. 541–579, 2019.
T. Stützle and M. López-Ibáñez, "Automated design of metaheuristic algorithms," Handbook of metaheuristics, pp.
[9] L. Ma, N. Li, Y. Guo, X. Wang, S. Yang, M. Huang, and H. Zhang, “Learning to optimize: reference vector reinforcement learning adaption to constrained many-objective optimization of industrial copper burdening system,” IEEE Transactions on Cybernetics, 2021.
L. Ma, N. Li, Y. Guo, X. Wang, S. Yang, M. Huang, and H. Zhang, "Learning to optimize: Reference vector reinforcement learning adaption to constrained many-objective optimization of industrial copper burdening system," IEEE Transactions on Cybernetics, 2021.
[10] Y. Tian, X. Li, H. Ma, X. Zhang, K. C. Tan, and Y. Jin, “Deep reinforcement learning based adaptive operator selection for evolutionary multi-objective optimization,” IEEE Transactions on Emerging Topics in Computational Intelligence, 2022.
Y. Tian, X. Li, H. Ma, X. Zhang, K. C. Tan, and Y. Jin, "Deep reinforcement learning based adaptive operator selection for evolutionary multi-objective optimization," IEEE Transactions on Emerging Topics in Computational Intelligence, 2022.
[11] Z. Zhang, Q. Tang, M. Chica, and Z. Li, “Reinforcement learning-based multiobjective evolutionary algorithm for mixed-model multimanned assembly line balancing under uncertain demand,” IEEE Transactions on Cybernetics, 2023.
Z. Zhang, Q. Tang, M. Chica, and Z. Li, "Reinforcement learning-based multiobjective evolutionary algorithm for mixed-model multimanned assembly line balancing under uncertain demand," IEEE Transactions on Cybernetics, 2023.
[12] Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim, “Learning improvement heuristics for solving routing problems,” IEEE transactions on neural networks and learning systems, vol. 33, no. 9, pp. 5057–5069, 2021.
Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim, "Learning improvement heuristics for solving routing problems," IEEE transactions on neural networks and learning systems, vol. 33, no. 9, pp.
[13] Y. Shen, Y. Sun, X. Li, A. Eberhard, and A. Ernst, “Adaptive solution prediction for combinatorial optimization,” European Journal of Operational Research, vol. 309, no. 3, pp. 1392–1408, 2023.
Y. Shen, Y. Sun, X. Li, A. Eberhard, and A. Ernst, "Adaptive solution prediction for combinatorial optimization," European Journal of Operational Research, vol. 309, no.3, pp.
[14] Y. Sun, S. Wang, Y. Shen, X. Li, A. T. Ernst, and M. Kirley, “Boosting ant colony optimization via solution prediction and machine learning,” Computers & Operations Research, vol. 143, p. 105769, 2022.
Y. Sun, S. Wang, Y. Shen, X. Li, A. T. Ernst, and M. Kirley, "Boosting ant colony optimization via solution prediction and machine learning," Computers & Operations Research, vol. 143, p. 105769, 2022.
[15] K. C. Tan, L. Feng, and M. Jiang, “Evolutionary transfer optimization-a new frontier in evolutionary computation research,” IEEE Computational Intelligence Magazine, vol. 16, no. 1, pp. 22–33, 2021.
K. C. Tan, L. Feng, and M. Jiang, "Evolutionary transfer optimization-a new frontier in evolutionary computation research," IEEE Computational Intelligence Magazine, vol. 16, no. 1, pp.
[16] L. Zhou, L. Feng, K. C. Tan, J. Zhong, Z. Zhu, K. Liu, and C. Chen, “Toward adaptive knowledge transfer in multifactorial evolutionary computation,” IEEE transactions on cybernetics, vol. 51, no. 5, pp. 2563–2576, 2020.
L. Zhou, L. Feng, K. C. Tan, J. Zhong, Z. Zhu, K. Liu, and C. Chen, "Toward adaptive knowledge transfer in multifactorial evolutionary computation," IEEE transactions on cybernetics, vol. 51, no.5, pp.
[17] K. Li, R. Chen, and X. Yao, “A data-driven evolutionary transfer optimization for expensive problems in dynamic environments,” IEEE Transactions on Evolutionary Computation, 2023.
K. Li, R. Chen, and X. Yao, "A data-driven evolutionary transfer optimization for expensive problems in dynamic environments," IEEE Transactions on Evolutionary Computation, 2023.
[18] F.-Y. Liu and C. Qian, “Prediction guided meta-learning for multi-objective reinforcement learning,” in 2021 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2021, pp. 2171–2178.
F.-Y. Liu and C. Qian, "Prediction guided meta-learning for multi-objective reinforcement learning," in 2021 IEEE Congress Evolutionary Computation (CEC).Liu and C. Qian, "Prediction guided meta-learning for multi-objective reinforcement learning," in 2021 IEEE Congress on Evolutionary Computation (CEC).IEEE, 2021, pp.
[19] Z. Zhang, Z. Wu, H. Zhang, and J. Wang, “Meta-learning-based deep reinforcement learning for multiobjective optimization problems,” IEEE Transactions on Neural Networks and Learning Systems, 2022.
Z. Zhang, Z. Wu, H. Zhang, and J. Wang, "Meta-learning-based deep reinforcement learning for multiobjective optimization problems," IEEE Transactions on Neural Networks and Learning Systems, 2022.
[20] Y. Cao, T. Chen, Z. Wang, and Y. Shen, “Learning to optimize in swarms,” Advances in neural information processing systems, vol. 32, 2019.
Y. Cao, T. Chen, Z. Wang, and Y. Shen, "Learning to optimize in swarms," Advances in neural information processing systems, vol. 32, 2019.
[21] R. Lange, T. Schaul, Y. Chen, T. Zahavy, V. Dalibard, C. Lu, S. Singh, and S. Flennerhag, “Discovering evolution strategies via meta-black-box optimization,” in Proceedings of the Companion Conference on Genetic and Evolutionary Computation, 2023, pp. 29–30.
R. Lange、T. Schaul、Y. Chen、T. Zahavy、V. Dalibard、C. Lu、S. Singh 和 S. Flennerhag，"通过元黑箱优化发现进化策略"，《遗传与进化计算同行会议论文集》，2023 年，第 29-30 页。
[22] L. Penghui, K. Wu, and J. Liu, “Decn: Evolution inspired deep convolution network for black-box optimization,” 2022.
L.Penghui, K. Wu, and J. Liu, "Decn：用于黑盒优化的进化启发深度卷积网络"，2022 年。
[23] X. Li, K. Wu, X. Zhang, H. Wang, and J. Liu, “Optformer: Beyond transformer for black-box optimization,” 2022.
X.Li, K. Wu, X. Zhang, H. Wang, and J. Liu, "Optformer：超越黑盒优化的变压器"，2022 年。
[24] Y. Jiang, Z.-H. Zhan, K. C. Tan, and J. Zhang, “Knowledge learning for evolutionary computation,” IEEE Transactions on Evolutionary Computation, 2023.
Y. Jiang, Z.-H. Zhan, K. C. Tan, and J. Zhang, "Knowledge learning for evolutionary computation," IEEE Transactions of Evolutionary Computation, 2023.Zhan, K. C. Tan, and J. Zhang, "Knowledge Learning for evolutionary computation," IEEE Transactions on Evolutionary Computation, 2023.
[25] W. Kool, H. Van Hoof, and M. Welling, “Attention, learn to solve routing problems!” arXiv preprint arXiv:1803.08475, 2018.
W. Kool、H. Van Hoof 和 M. Welling，"注意，学会解决路由问题！"arXiv 预印本 arXiv:1803.08475, 2018。
[26] X. Lin, Z. Yang, and Q. Zhang, “Pareto set learning for neural multi-objective combinatorial optimization,” 2022.
X.Lin, Z. Yang, and Q. Zhang, "Pareto set learning for neural multi-objective combinatorial optimization," 2022.
[27] J. Zhou, Y. Wu, W. Song, Z. Cao, and J. Zhang, “Towards omni-generalizable neural methods for vehicle routing problems,” arXiv preprint arXiv:2305.19587, 2023.
J. Zhou, Y. Wu, W. Song, Z. Cao, and J. Zhang, "Towards omni-generalizable neural methods for vehicle routing problems," arXiv preprint arXiv:2305.19587, 2023.
[28] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, “Neural combinatorial optimization with heavy decoder: Toward large scale generalization,” arXiv preprint arXiv:2310.07985, 2023.
F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang, "Neural combinatorial optimization with heavy decoder：Toward large scale generalization," arXiv preprint arXiv:2310.07985, 2023.
[29] Z. Wang, S. Yao, G. Li, and Q. Zhang, “Multiobjective combinatorial optimization using a single deep reinforcement learning model,” IEEE Transactions on Cybernetics, 2023.
Z. Wang, S. Yao, G. Li, and Q. Zhang, "Multiobjective combinatorial optimization using a single deep reinforcement learning model," IEEE Transactions on Cybernetics, 2023.
[30] W. X. Zhao, K. Zhou, J. Li, T. Tang, X. Wang, Y. Hou, Y. Min, B. Zhang, J. Zhang, Z. Dong et al., “A survey of large language models,” arXiv preprint arXiv:2303.18223, 2023.
W. X. Zhao、K. Zhou、J. Li、T. Tang、X. Wang、Y. Hou、Y. Min、B. Zhang、J. Zhang、Z. Dong 等：《大型语言模型概览》，arXiv 预印本 arXiv:2303.18223, 2023。
[31] E. Kasneci, K. Seßler, S. Küchemann, M. Bannert, D. Dementieva, F. Fischer, U. Gasser, G. Groh, S. Günnemann, E. Hüllermeier et al., “Chatgpt for good? on opportunities and challenges of large language models for education,” Learning and individual differences, vol. 103, p. 102274, 2023.
E. Kasneci, K. Seßler, S. Küchemann, M. Bannert, D. Dementieva, F. Fischer, U. Gasser, G. Groh, S. Günnemann, E. Hüllermeier et al., "Chatgpt for good? on opportunities and challenges of large language models for education," Learning and individual differences, vol. 103, p. 102274, 2023.
[32] B. Min, H. Ross, E. Sulem, A. P. B. Veyseh, T. H. Nguyen, O. Sainz, E. Agirre, I. Heintz, and D. Roth, “Recent advances in natural language processing via large pre-trained language models: A survey,” ACM Computing Surveys, 2021.
B. Min、H. Ross、E. Sulem、A. P. B. Veyseh、T. H. Nguyen、O. Sainz、E. Agirre、I. Heintz 和 D. Roth，"通过大型预训练语言模型进行自然语言处理的最新进展：A survey," ACM Computing Surveys, 2021.
[33] H. Tian, W. Lu, T. O. Li, X. Tang, S.-C. Cheung, J. Klein, and T. F. Bissyandé, “Is chatgpt the ultimate programming assistant–how far is it?” arXiv preprint arXiv:2304.11938, 2023.
H. Tian, W. Lu, T. O. Li, X. Tang, S.-C. Cheung, J. Klein, and T. F. Bissyandé, "Is chatgpt ultimate programming assistant-how far is it?Cheung, J. Klein, and T. F. Bissyandé, "Is chatgpt the ultimate programming assistant-how far is it?" arXiv preprint arXiv:2304.11938, 2023.
[34] P. Lee, S. Bubeck, and J. Petro, “Benefits, limits, and risks of gpt-4 as an ai chatbot for medicine,” New England Journal of Medicine, vol. 388, no. 13, pp. 1233–1239, 2023.
P. Lee, S. Bubeck, and J. Petro, "Benefits, limits, and risks of gpt-4 as an ai chatbot for medicine," New England Journal of Medicine, vol. 388, no. 13, pp.
[35] H. Nori, N. King, S. M. McKinney, D. Carignan, and E. Horvitz, “Capabilities of gpt-4 on medical challenge problems,” arXiv preprint arXiv:2303.13375, 2023.
H. Nori, N. King, S. M. McKinney, D. Carignan, and E. Horvitz, "Capabilities of gpt-4 on medical challenge problems," arXiv preprint arXiv:2303.13375, 2023.
[36] K. Cheng, Q. Guo, Y. He, Y. Lu, S. Gu, and H. Wu, “Exploring the potential of gpt-4 in biomedical engineering: the dawn of a new era,” Annals of Biomedical Engineering, pp. 1–9, 2023.
K. Cheng, Q. Guo, Y. He, Y. Lu, S. Gu, and H. Wu, "Exploring potential of gpt-4 in biomedical engineering: the dawn of a new era," Annals of Biomedical Engineering, pp.
[37] K. M. Jablonka, P. Schwaller, A. Ortega-Guerrero, and B. Smit, “Is gpt-3 all you need for low-data discovery in chemistry?” 2023.
K.Jablonka, P. Schwaller, A. Ortega-Guerrero, and B. Smit, "Is gpt-3 all you need for low-data discovery in chemistry?"2023.
[38] J. Blocklove, S. Garg, R. Karri, and H. Pearce, “Chip-chat: Challenges and opportunities in conversational hardware design,” arXiv preprint arXiv:2305.13243, 2023.
J. Blocklove、S. Garg、R. Karri 和 H. Pearce，"Chip-chat：对话式硬件设计的挑战与机遇》，arXiv 预印本 arXiv:2305.13243, 2023。
[39] Z. He, H. Wu, X. Zhang, X. Yao, S. Zheng, H. Zheng, and B. Yu, “Chateda: A large language model powered autonomous agent for eda,” arXiv preprint arXiv:2308.10204, 2023.
Z. He, H. Wu, X. Zhang, X. Yao, S. Zheng, H. Zheng, and B. Yu, "Chateda：A large language model powered autonomous agent for eda," arXiv preprint arXiv:2308.10204, 2023.
[40] C. Yu, X. Liu, C. Tang, W. Feng, and J. Lv, “Gpt-nas: Neural architecture search with the generative pre-trained model,” arXiv preprint arXiv:2305.05351, 2023.
C. Yu, X. Liu, C. Tang, W. Feng, and J. Lv, "Gpt-nas：使用生成预训练模型的神经架构搜索"，arXiv 预印本 arXiv:2305.05351, 2023.
[41] M. Zheng, X. Su, S. You, F. Wang, C. Qian, C. Xu, and S. Albanie, “Can gpt-4 perform neural architecture search?” arXiv preprint arXiv:2304.10970, 2023.
M. Zheng, X. Su, S. You, F. Wang, C. Qian, C. Xu, and S. Albanie, "Can gpt-4 perform neural architecture search?" arXiv preprint arXiv:2304.10970, 2023.
[42] S. Zhang, C. Gong, L. Wu, X. Liu, and M. Zhou, “Automl-gpt: Automatic machine learning with gpt,” arXiv preprint arXiv:2305.02499, 2023.
S. Zhang, C. Gong, L. Wu, X. Liu, and M. Zhou, "Automl-gpt：Automl-gpt: Automatic machine learning with gpt," arXiv preprint arXiv:2305.02499, 2023.
[43] Z. Zhao, W. S. Lee, and D. Hsu, “Large language models as commonsense knowledge for large-scale task planning,” arXiv preprint arXiv:2305.14078, 2023.
Z. Zhao, W. S. Lee, and D. Hsu, "Large language models as commonsense knowledge for large-scale task planning," arXiv preprint arXiv:2305.14078, 2023.
[44] C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen, “Large language models as optimizers,” arXiv preprint arXiv:2309.03409, 2023.
C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen, "Large language models as optimizers," arXiv preprint arXiv:2309.03409, 2023.
[45] E. Meyerson, M. J. Nelson, H. Bradley, A. Moradi, A. K. Hoover, and J. Lehman, “Language model crossover: Variation through few-shot prompting,” arXiv preprint arXiv:2302.12170, 2023.
E. Meyerson、M. J. Nelson、H. Bradley、A. Moradi、A. K. Hoover 和 J. Lehman，"语言模型交叉：Variation through few-shot prompting," arXiv preprint arXiv:2302.12170, 2023.
[46] A. Chen, D. M. Dohan, and D. R. So, “Evoprompting: Language models for code-level neural architecture search,” arXiv preprint arXiv:2302.14838, 2023.
A. Chen, D. M. Dohan, and D. R. So, "Evoprompting：用于代码级神经架构搜索的语言模型"，arXiv preprint arXiv:2302.14838, 2023.
[47] H. Wang, S. Feng, T. He, Z. Tan, X. Han, and Y. Tsvetkov, “Can language models solve graph problems in natural language?” arXiv preprint arXiv:2305.10037, 2023.
H. Wang, S. Feng, T. He, Z. Tan, X. Han, and Y. Tsvetkov, "Can language models solve graph problems in natural language?" arXiv preprint arXiv:2305.10037, 2023.
[48] F. Liu, X. Lin, Z. Wang, S. Yao, X. Tong, M. Yuan, and Q. Zhang, “Large language model for multi-objective evolutionary optimization,” arXiv preprint arXiv:2310.12541, 2023.
F. Liu, X. Lin, Z. Wang, S. Yao, X. Tong, M. Yuan, and Q. Zhang, "Large language model for multi-objective evolutionary optimization," arXiv preprint arXiv:2310.12541, 2023.
[49] M. Gendreau, J.-Y. Potvin et al., Handbook of metaheuristics. Springer, 2010, vol. 2.
M. Gendreau, J.-Y. Potvin et al.Potvin 等人，《元启发式计算手册》。Springer, 2010, vol. 2.
[50] C. Ansótegui, M. Sellmann, and K. Tierney, “A gender-based genetic algorithm for the automatic configuration of algorithms,” in International Conference on Principles and Practice of Constraint Programming. Springer, 2009, pp. 142–157.
C. Ansótegui, M. Sellmann, and K. Tierney, "A gender-based genetic algorithm for the automatic configuration of algorithms," in International Conference on Principles and Practice of Constraint Programming. Springer, 2009, pp.Springer, 2009, pp.
[51] F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle, “Paramils: an automatic algorithm configuration framework,” Journal of artificial intelligence research, vol. 36, pp. 267–306, 2009.
F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle, "Paramils: an automatic algorithm configuration framework," Journal of artificial intelligence research, vol. 36, pp.
[52] A. Blot, H. H. Hoos, L. Jourdan, M.-É. Kessaci-Marmion, and H. Trautmann, “Mo-paramils: A multi-objective automatic algorithm configuration framework,” in Learning and Intelligent Optimization: 10th International Conference, LION 10, Ischia, Italy, May 29–June 1, 2016, Revised Selected Papers 10. Springer, 2016, pp. 32–47.
A. Blot、H. H. Hoos、L. Jourdan、M.-É.Kessaci-Marmion 和 H. Trautmann，"Mo-paramils：多目标自动算法配置框架"，第 10 届国际学习与智能优化大会，LION 10：10th International Conference, LION 10, Ischia, Italy, May 29-June 1, 2016, Revised Selected Papers 10.Springer, 2016, pp.
[53] M. López-Ibáñez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Stützle, “The irace package: Iterated racing for automatic algorithm configuration,” Operations Research Perspectives, vol. 3, pp. 43–58, 2016.
M. López-Ibáñez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Stützle, "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, vol. 3, pp.
[54] F. Hutter, H. H. Hoos, and K. Leyton-Brown, “Sequential model-based optimization for general algorithm configuration,” in Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5. Springer, 2011, pp. 507–523.
F. Hutter, H. H. Hoos, and K. Leyton-Brown, "Sequential model-based optimization for general algorithm configuration," in Learning and Intelligent Optimization：第五届国际会议，LION 5，意大利罗马，2011 年 1 月 17-21 日。Selected Papers 5.Springer, 2011, pp.
[55] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, “Optuna: A next-generation hyperparameter optimization framework,” in Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 2623–2631.
T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, "Optuna：下一代超参数优化框架"，《第 25 届 ACM SIGKDD 知识发现与数据挖掘国际会议论文集》，2019 年，第 2623-2631 页。
[56] W. Meng and R. Qu, “Automated design of search algorithms: Learning on algorithmic components,” Expert Systems with Applications, vol. 185, p. 115493, 2021.
W. Meng and R. Qu, "Automated design of search algorithms：Learning on algorithmic components," Expert Systems with Applications, vol. 185, p. 115493, 2021.
[57] L. C. Bezerra, M. López-Ibánez, and T. Stützle, “Automatic component-wise design of multiobjective evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 3, pp. 403–417, 2015.
L. C. Bezerra, M. López-Ibánez, and T. Stützle, "Automatic component-wwise design of multiobjective evolutionary algorithms," IEEE Transactions on Evolutionary Computation, vol. 20, no.3, pp.
[58] Y. Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: a methodological tour d’horizon,” European Journal of Operational Research, vol. 290, no. 2, pp. 405–421, 2021.
Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d'horizon," European Journal of Operational Research, vol. 290, no. 2, pp.
[59] N. Li, L. Ma, G. Yu, B. Xue, M. Zhang, and Y. Jin, “Survey on evolutionary deep learning: Principles, algorithms, applications, and open issues,” ACM Computing Surveys, vol. 56, no. 2, pp. 1–34, 2023.
N. Li, L. Ma, G. Yu, B. Xue, M. Zhang, and Y. Jin, "Survey on evolutionary deep learning：原理、算法、应用和开放问题》，《ACM 计算概览》，第 56 卷，第 2 期，第 1-34 页，2023 年。
[60] W. Liu, R. Wang, T. Zhang, K. Li, W. Li, and H. Ishibuchi, “Hybridization of evolutionary algorithm and deep reinforcement learning for multi-objective orienteering optimization,” IEEE Transactions on Evolutionary Computation, 2022.
W. Liu, R. Wang, T. Zhang, K. Li, W. Li, and H. Ishibuchi, "Hybridization of evolutionary algorithm and deep reinforcement learning for multi-objective orienteering optimization," IEEE Transactions on Evolutionary Computation, 2022.
[61] W. Dong and M. Zhou, “A supervised learning and control method to improve particle swarm optimization algorithms,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 7, pp. 1135–1148, 2016.
W. Dong and M. Zhou, "A supervised learning and control method to improve particle swarm optimization algorithms," IEEE Transactions on Systems, Man, and Cybernetics：系统》，第 47 卷第 7 期，第 1135-1148 页，2016 年。
[62] Y. Sun, A. T. Ernst, X. Li, and J. Weiner, “Learning to generate columns with application to vertex coloring,” in The Eleventh International Conference on Learning Representations, 2022.
Y. Sun, A. T. Ernst, X. Li, and J. Weiner, "Learning to generate columns with application to vertex coloring," in The Eleventh International Conference on Learning Representations, 2022.
[63] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas, “Taking the human out of the loop: A review of bayesian optimization,” Proceedings of the IEEE, vol. 104, no. 1, pp. 148–175, 2015.
[64] Q. Zhang, W. Liu, E. Tsang, and B. Virginas, “Expensive multiobjective optimization by MOEA/D with gaussian process model,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456–474, 2009.
[65] Y. Jin, H. Wang, T. Chugh, D. Guo, and K. Miettinen, “Data-driven evolutionary optimization: An overview and case studies,” IEEE Transactions on Evolutionary Computation, vol. 23, no. 3, pp. 442–458, 2018.
[66] Z. Song, H. Wang, C. He, and Y. Jin, “A kriging-assisted two-archive evolutionary algorithm for expensive many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 25, no. 6, pp. 1013–1027, 2021.
[67] H. Hao, A. Zhou, H. Qian, and H. Zhang, “Expensive multiobjective optimization by relation learning and prediction,” IEEE Transactions on Evolutionary Computation, vol. 26, no. 5, pp. 1157–1170, 2022.
[68] Y. Mei, Q. Chen, A. Lensen, B. Xue, and M. Zhang, “Explainable artificial intelligence by genetic programming: A survey,” IEEE Transactions on Evolutionary Computation, 2022.
[69] Y.-H. Jia, Y. Mei, and M. Zhang, “Learning heuristics with different representations for stochastic routing,” IEEE Transactions on Cybernetics, 2022.
[70] P.-F. Guo, Y.-H. Chen, Y.-D. Tsai, and S.-D. Lin, “Towards optimizing with large language models,” arXiv preprint arXiv:2310.05204, 2023.
[71] A. E. Brownlee, J. Callan, K. Even-Mendoza, A. Geiger, C. Hanna, J. Petke, F. Sarro, and D. Sobania, “Enhancing genetic improvement mutations using large language models,” arXiv preprint arXiv:2310.19813, 2023.
[72] S. Liu, C. Chen, X. Qu, K. Tang, and Y.-S. Ong, “Large language models as evolutionary optimizers,” arXiv preprint arXiv:2310.19046, 2023.
[73] M. U. Nasir, S. Earle, J. Togelius, S. James, and C. Cleghorn, “Llmatic: Neural architecture search via large language models and quality-diversity optimization,” arXiv preprint arXiv:2306.01102, 2023.
[74] G. Jawahar, M. Abdul-Mageed, L. V. Lakshmanan, and D. Ding, “Llm performance predictors are good initializers for architecture search,” arXiv preprint arXiv:2310.16712, 2023.
[75] J. Lehman, J. Gordon, S. Jain, K. Ndousse, C. Yeh, and K. O. Stanley, “Evolution through large models,” in Handbook of Evolutionary Machine Learning. Springer, 2023, pp. 331–366.
[76] G. Reinelt, The traveling salesman: computational solutions for TSP applications. Springer, 2003, vol. 840.
[77] Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min, “Pomo: Policy optimization with multiple optima for reinforcement learning,” Advances in Neural Information Processing Systems, vol. 33, pp. 21 188–21 198, 2020.
[78] X. Pan, Y. Jin, Y. Ding, M. Feng, L. Zhao, L. Song, and J. Bian, “H-tsp: Hierarchically solving the large-scale travelling salesman problem,” arXiv preprint arXiv:2304.09395, 2023.
[79] H. Cheng, H. Zheng, Y. Cong, W. Jiang, and S. Pu, “Select and optimize: Learning to aolve large-scale tsp instances,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 1219–1231.
[80] S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg et al., “Sparks of artificial general intelligence: Early experiments with gpt-4,” arXiv preprint arXiv:2303.12712, 2023.
[81] W. J. Cook, D. L. Applegate, R. E. Bixby, and V. Chvatal, The traveling salesman problem: a computational study. Princeton university press, 2011.
[82] G. Mialon, R. Dessì, M. Lomeli, C. Nalmpantis, R. Pasunuru, R. Raileanu, B. Rozière, T. Schick, J. Dwivedi-Yu, A. Celikyilmaz et al., “Augmented language models: a survey,” arXiv preprint arXiv:2302.07842, 2023.
[83] T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and T. Scialom, “Toolformer: Language models can teach themselves to use tools,” arXiv preprint arXiv:2302.04761, 2023.
[84] B. Paranjape, S. Lundberg, S. Singh, H. Hajishirzi, L. Zettlemoyer, and M. T. Ribeiro, “Art: Automatic multi-step reasoning and tool-use for large language models,” arXiv preprint arXiv:2303.09014, 2023.
[85] B. Hudson, Q. Li, M. Malencia, and A. Prorok, “Graph neural network guided local search for the traveling salesperson problem,” arXiv preprint arXiv:2110.05291, 2021.
[86] A. Hottung and K. Tierney, “Neural large neighborhood search for the capacitated vehicle routing problem,” arXiv preprint arXiv:1911.09539, 2019.
[87] N. T. Nguyen and K. Lee, “Deep learning-aided tabu search detection for large mimo systems,” IEEE Transactions on Wireless Communications, vol. 19, no. 6, pp. 4262–4275, 2020.
[88] S. Jiang, J. Zou, S. Yang, and X. Yao, “Evolutionary dynamic multi-objective optimisation: A survey,” ACM Computing Surveys, vol. 55, no. 4, pp. 1–47, 2022.
[89] H. Ishibuchi, L. M. Pang, and K. Shang, “A new framework of evolutionary multi-objective algorithms with an unbounded external archive,” Authorea Preprints, 2023.
[90] T. Khot, H. Trivedi, M. Finlayson, Y. Fu, K. Richardson, P. Clark, and A. Sabharwal, “Decomposed prompting: A modular approach for solving complex tasks,” arXiv preprint arXiv:2210.02406, 2022.
[91] X. Chen, M. Lin, N. Schärli, and D. Zhou, “Teaching large language models to self-debug,” arXiv preprint arXiv:2304.05128, 2023.
[92] O. Press, M. Zhang, S. Min, L. Schmidt, N. A. Smith, and M. Lewis, “Measuring and narrowing the compositionality gap in language models,” arXiv preprint arXiv:2210.03350, 2022.
[93] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou, “Self-consistency improves chain of thought reasoning in language models,” arXiv preprint arXiv:2203.11171, 2022.
[94] A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P. N. Suganthan, and Q. Zhang, “Multiobjective evolutionary algorithms: A survey of the state of the art,” Swarm and evolutionary computation, vol. 1, no. 1, pp. 32–49, 2011.

Algorithm Evolution Using Large Language Model 使用大型语言模型的算法进化

Abstract 摘要

Index Terms:

I Introduction I 引言

II Related Works II 相关作品

II-A Automatic Algorithm Design (AAD)II-A 自动算法设计（AAD）

II-B Machine Learning for OptimizationII-B 机器学习促进优化

II-C Large Language Model (LLM)II-C 大语言模型（LLM

II-D LLMs for Algorithm DesignII-D LLMs 算法设计

III Algorithm Evolution using Large Language ModelIII 使用大型语言模型的算法进化