本研究的主要作者为Fei Liu、Xialiang Tong、Mingxuan Yuan、Xi Lin、Fu Luo、Zhenkun Wang、Zhichao Lu和Qingfu Zhang。他们分别来自香港城市大学计算机科学系、华为诺亚方舟实验室以及南方科技大学系统设计与智能制造学院。这项研究发表于2024年的第41届国际机器学习会议（International Conference on Machine Learning, ICML）论文集。

这项研究的学术背景集中在计算机科学，特别是自动算法设计与组合优化领域。在过去的几十年里，启发式方法（Heuristics）被广泛应用于解决复杂的搜索和优化问题。然而，手动设计高效启发式规则通常费时费力，且高度依赖专家的经验和知识。自动启发式设计（Automatic Heuristic Design, AHD）应运而生，旨在通过自动化过程为特定问题类别选择、调整或构造有效的启发式方法。传统方法如遗传编程（Genetic Programming, GP）虽然取得了一定成功，但通常需要精心设计一组允许的算子或操作，这在实践中往往很困难。近年来，大语言模型（Large Language Models, LLMs）展现出强大的代码和思想生成能力，但单独使用LLM通过提示工程生成新颖有效的算法思想仍显不足。先前的研究，例如FunSearch，通过将LLM与进化计算（Evolutionary Computation, EC）结合，在函数空间进行搜索以改进启发式代码，取得了显著成果，但其机制效率不高，需要海量的计算资源（如数百万次LLM查询）才能生成高质量的启发式规则。因此，本研究旨在解决现有AHD方法在效率和设计过程模拟方面的不足，提出一种更高效、更接近人类专家设计思维的自动化范式。该研究的目标是开发一种新的进化范式——启发式进化（Evolution of Heuristic, EoH），它能够协同演化启发式的“思想”（用自然语言描述的高层逻辑）和“代码”（可执行的实现），从而以更少的计算成本自动设计出高性能的启发式算法。

本研究详细的工作流程可分为以下几个核心部分：1. EoH框架设计；2. 启发式表示方法；3. 演化策略；4. 实验评估与消融分析。首先，EoH框架是一个迭代的进化搜索过程。它维护一个包含N个启发式规则的种群，每个启发式规则是一个个体。与大多数进化算法以问题的候选解为个体不同，EoH的个体是一个用于解决问题的启发式规则本身。框架主要包括初始化、启发式生成和种群管理三个步骤。在初始化阶段，研究者通过特定的“初始化提示”直接要求LLM生成N个全新的启发式规则及其代码，无需任何专家知识。在每一代演化中，系统会并行使用五种精心设计的提示策略来生成新的启发式规则。这五种策略分为两类：探索类（E1, E2）和修改类（M1, M2, M3）。E1旨在生成与所选父代启发式尽可能不同的新启发式以探索新思路；E2则先识别多个父代启发式的共同思想，并基于此思想设计结构上不同的新启发式。M1要求LLM直接修改一个选定的启发式以提高其性能；M2专注于调整选定启发式中的参数；M3则尝试简化启发式，移除冗余组件。在每一代中，每种策略会被调用N次，总共生成最多5N个新启发式。每个新生成的启发式都会在一组问题实例上进行评估，并获得一个适应度值。随后，所有新生成的可行启发式会加入当前种群，然后从当前种群中选择适应度最高的N个个体构成下一代种群。这一过程循环进行，直至达到设定的代数（实验中通常为20代）。

其次，关于启发式的表示方法，这是EoH的核心创新之一。每个启发式个体由三个部分组成：1) 用自然语言描述的“思想”，用于概括启发式的高层逻辑；2) 符合预定义格式的代码块（实验中为Python函数），是可执行的具体实现；3) 基于问题实例评估得到的适应度值。这种“思想-代码”的双重表示使得演化过程能够同时在高层的概念空间和底层的实现空间进行搜索，更贴近人类专家“先有想法，再实现代码”的设计过程。这也与FunSearch等仅演化代码的方法形成了鲜明对比。

第三，在具体的实验处理上，研究者选择了三个广泛研究的组合优化基准问题来验证EoH的有效性：在线装箱问题（Online Bin Packing）、旅行商问题（Traveling Salesman Problem, TSP）和流水车间调度问题（Flow Shop Scheduling Problem, FSSP）。对于每个问题，他们定义了EoH需要设计的启发式组件的具体形式。例如，在在线装箱问题中，EoH的目标是设计一个评分函数，根据物品大小和箱子的剩余容量为箱子分配分数；在TSP和FSSP中，EoH被用于设计引导式局部搜索（Guided Local Search, GLS）中更新目标函数“景观”的启发式规则。在演化过程中，每个启发式的适应度是通过在预先设定的一组训练实例上运行其代码实现的算法来评估的。例如，装箱问题使用5个大小为5k、容量为100的Weibull分布实例进行评估，适应度为平均装箱数与理论下界的接近程度。实验使用了GPT-3.5-turbo作为LLM，并在单个CPU上执行。在评估阶段，研究者将EoH生成的最佳启发式与多种基线方法进行了比较，包括人工设计的经典启发式（如装箱问题的首次适应、最佳适应；TSP的最近插入、最远插入；FSSP的NEH等）、以及当前先进的AHD方法（如FunSearch）和基于学习的神经网络求解器（如TSP的Attention Model, POMO, LEHD；FSSP的PFSPNet）。

本研究的主要结果如下：1. 在线装箱问题：EoH在仅使用2000次LLM查询（远少于Funsearch报告的约百万次）的情况下，成功演化出了高性能的启发式规则。可视化演化过程显示，启发式的适应度从0.962逐步提升至0.993。最终生成的启发式是一个包含剩余容量、指数项、平方根项及其组合的复杂混合函数。在多个不同规模和容量的测试实例集上，EoH生成的启发式在大多数情况下都优于人工设计的启发式和Funsearch生成的启发式。例如，在1k容量500的测试集上，EoH的过剩箱子比例（gap）为2.13%，而Funsearch为6.75%，且EoH的表现超过了所有人工基准。这证明了EoH的高效性和良好的泛化能力。2. 旅行商问题：EoH设计的GLS启发式在TSPLIB标准测试集上表现优异，在多个实例上（如pr124, kroa150, u159）找到了已知最优解（gap=0%）。尽管神经网络求解器在训练分布相同的实例上表现良好，但在TSPLIB这类分布外实例上性能下降，而EoH设计的启发式则表现稳健， consistently优于其他对比方法。3. 流水车间调度问题：在Taillard标准测试集上，EoH生成的启发式在所有测试集（不同工件数和机器数组合）上都取得了最佳的平均相对makespan，显著优于经典的NEH等启发式以及PFSPNet等深度学习求解器。这些结果共同表明，EoH能够在较低计算成本下，为不同类型的组合优化问题自动设计出超越人工设计和现有自动方法的高性能启发式。

此外，研究还进行了深入的消融分析，以验证EoH各组件的重要性。他们比较了多个变体：EoC（仅演化代码，无思想部分）、EoH-E1（仅使用E1策略）、EoH-E2（使用E1和E2策略）以及完整的EoH。实验结果显示，在在线装箱问题上，完整EoH性能最佳，EoH-E2次之，而EoC（仅演化代码）表现最差或第二差。这明确证实了“思想”表示和多种提示策略（特别是修改类策略M1-M3和探索策略E2）对提升EoH性能的积极作用。另一项实验对比了不同LLM（GPT-3.5, Gemini Pro, CodeLlama, DeepSeek）的效果，发现EoH框架在不同LLM下都能生成良好性能的启发式，但更强大的LLM（如GPT-3.5和Gemini Pro）能带来更好的结果。研究者还探讨了在初始种群中引入专家启发式（如Funsearch已生成的优秀启发式）的影响，结果表明，融入专家知识可以进一步提升最终启发式的性能。

本研究的结论是：作者成功提出并验证了“启发式进化”这一新颖范式，它将大语言模型与进化计算深度融合，通过协同演化启发式的自然语言思想和可执行代码，实现了高效的自动算法设计。EoH通过五种精心设计的提示策略模拟了人类专家设计启发式的推理过程。在三个经典组合优化问题上的实验证明，EoH能够以显著更少的LLM查询（数千次对比百万次），设计出超越人工基准和当前先进AHD方法（如FunSearch）性能的启发式算法。这不仅展示了LLM与EC结合在自动算法设计领域的巨大潜力，也为后续研究提供了新的方向，例如训练针对算法设计领域的专用LLM、深入研究启发式搜索空间的理论特性，以及探索EoH与人类专家更高效的交互模式。该研究的意义和价值在于：科学上，它提出了一种创新的“思想-代码”协同演化框架，推动了自动算法设计方法论的发展；应用上，它提供了一种高效、低成本生成定制化高性能启发式的工具，有望降低算法设计门槛，加速优化算法在实际复杂问题中的应用。研究的源代码已在GitHub上公开，促进了该领域的可重复性研究和进一步发展。

本研究的亮点主要体现在以下几个方面：首先，核心创新新颖：首次明确提出了同时演化启发式“思想”（高层逻辑）和“代码”（底层实现）的范式，这是对现有仅演化代码方法的实质性突破，更贴近人类的创造性设计过程。其次，方法高效实用：设计的五种提示策略（E1, E2, M1, M2, M3）简单而有效，能够系统性地引导LLM进行探索和精修，使得整个演化过程在极少的LLM查询次数（数千次）下就能收敛到高性能启发式，计算效率远超前人工作。第三，实验验证全面有力：在三个不同领域的经典组合优化问题上进行了系统测试，不仅与人工启发式、FunSearch对比，还涵盖了最新的神经网络求解器，结果一致证明了EoH的优越性、高效性和良好的泛化能力。第四，分析深入透彻：通过详尽的消融研究、不同LLM对比、专家知识引入实验等，清晰揭示了各个组件（思想表示、多种提示策略）的贡献，为理解和改进该方法提供了坚实基础。最后，开源促进发展：公开了完整的源代码，有利于学术社区验证结果、复现工作并在此基础上进行创新。