It is often very tedious for human experts to design efficient algorithms.
Recently, we have proposed a novel Algorithm Evolution using Large Language
Model (AEL) framework for automatic algorithm design. AEL combines the power of
a large language model and the paradigm of evolutionary computation to design,
combine, and modify algorithms automatically. In this paper, we use AEL to
design the guide algorithm for guided local search (GLS) to solve the
well-known traveling salesman problem (TSP). AEL automatically evolves elite
GLS algorithms in two days, with minimal human effort and no model training.
Experimental results on 1,000 TSP20-TSP100 instances and TSPLib instances show
that AEL-designed GLS outperforms state-of-the-art human-designed GLS with the
same iteration budget. It achieves a 0% gap on TSP20 and TSP50 and a 0.032% gap
on TSP100 in 1,000 iterations. Our findings mark the emergence of a new era in
automatic algorithm design.

我们用大型语言模型结合进化计算范式提出了一种新的算法进化（AEL）框架，用于自动算法设计，并在旅行商问题中使用 AEL 设计了引导算法。实验证明，AEL 设计的引导算法在相同迭代预算下优于人工设计的引导算法，标志着自动算法设计的新纪元的出现。

高效引导局部搜索的设计：进化计算与大型语言模型超越人类的实例

An Example of Evolutionary Computation + Large Language Model Beating  Human: Design of Efficient Guided Local Search

Solutions to the Traveling Salesperson Problem (TSP) have practical
applications to processes in transportation, logistics, and automation, yet
must be computed with minimal delay to satisfy the real-time nature of the
underlying tasks. However, solving large TSP instances quickly without
sacrificing solution quality remains challenging for current approximate
algorithms. To close this gap, we present a hybrid data-driven approach for
solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search
(GLS). Our model predicts the regret of including each edge of the problem
graph in the solution; GLS uses these predictions in conjunction with the
original problem graph to find solutions. Our experiments demonstrate that this
approach converges to optimal solutions at a faster rate than three recent
learning based approaches for the TSP. Notably, we reduce the mean optimality
gap on the 100-node problem set from 1.534% to 0.705%, a 2x improvement. When
generalizing from 20-node instances to the 100-node problem set, we reduce the
optimality gap from 18.845% to 2.622%, a 7x improvement.

提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。