源码及文章：EoH/README_CN.md at main · FeiLiu36/EoH

Evolution of Heuristic 启发式进化：

Evolutionary Computation 进化计算：

Automatic Heuristic Design 自动启发式设计

EoH 将自然语言中的启发式思维转化为可执行代码，通过优化搜索框架对思维与代码的持续演化，显著提升了高性能启发式算法的生成效率。

创新点：

双重演进：EoH 利用 LLM 不仅演进代码，更重要的是它还演进“思想”。LLM 首先根据现有的优秀启发式（包含思想和代码），生成一个改进的或全新的“思想” 。

思想指导代码：随后，LLM 再将这个新生成的“思想”作为指导，翻译成具体的“代码” 。

提示策略 (Prompt Strategies)：整个演进过程并非盲目进行，而是由一系列精心设计的提示策略来引导，分为两大类：探索（Exploration: E1, E2）和修改（Modification: M1, M2, M3），以确保生成更多样化和更有效的启发式算法。

通过构建 thought 来表征启发式算法的核心逻辑。随后借助语言模型生成代码实现。随后协同进化逐步优化思想域代码

三大贡献：

框架上提出 EoH

设计了高效的 prompt

通过组合优化问题对 EoH 进行了全面评估

与本研究最相关的是 FunSearch 框架：

**FunSearch 是由 Google DeepMind 开发的一种创新的方法，其名称是 “在函数空间中搜索”（Searching in the **Function Space）的缩写。它旨在利用大型语言模型（LLM）来解决数学和计算机科学领域的难题，甚至做出全新的科学发现。

FunSearch 的核心思想是将一个预训练的大型语言模型（LLM）的创造力与一个自动评估系统结合起来。它并不直接让 LLM 给出问题的最终答案，而是让 LLM 生成解决问题的“程序”或“函数”。这种方法的巧妙之处在于：

规避“幻觉”：LLM 常常会“一本正经地胡说八道”（产生幻觉）。但 FunSearch 生成的是代码，这些代码可以通过一个自动评估器（Evaluator）来运行和打分，从而有效过滤掉所有不正确或无效的想法。
输出可解释的知识：FunSearch 最终产出的是一个能够解决问题的程序。人类科学家可以阅读和理解这个程序，从而洞察问题是如何被解决的，而不仅仅是知道答案是什么。这有助于激发新的研究思路。

FunSearch 的工作方式可以看作是一种由 LLM 驱动的“演化算法”或“遗传编程”。其基本流程如下：

定义问题：用户首先需要用代码来描述一个问题。这通常包括一个用于评估解决方案好坏的 evaluate 函数，以及一个非常简单的初始程序作为“种子”。
演化循环：
- 选择与提示：系统从一个“程序数据库”（Program Database）中挑选出一些当前最高效的程序。
- LLM 生成新代码：将这些高效程序作为“范例”输入给 LLM（一个专门训练用于编码的 LLM，如 Codey），并提示它在此基础上进行创新，生成新的、可能更好的函数代码。
- 评估与筛选：新生成的代码会被自动评估器运行和打分。
- 更新数据库：如果新程序的表现优于现有的程序，它就会被添加到程序数据库中，用于下一轮的演化。
持续迭代：这个“生成-评估-筛选”的循环会不断重复，推动程序从一个简单的“种子”逐步“演化”成一个非常高效的解决方案。

FunSearch 已经在一些长期存在的数学开放性问题上取得了突破性的成果：

上限集问题（Cap Set Problem）：这是一个困扰了数学家几十年的组合数学难题。FunSearch 发现了比人类已知方法更大的上限集构造方案，这是首次由 LLM 在这类具有挑战性的科学问题上做出新发现。
在线装箱问题（Bin Packing Problem）：这是一个经典的组合优化问题，旨在找到最有效的方式将不同大小的物品装入有限数量的箱子。FunSearch 发现了一种比人类常用启发式算法更优的策略。

EoH 旨在通过进化思想和代码，模拟人类专家进行启发式开发的过程，从而实现高效的自动启发式设计。

1.每次实验，系统允许大语言模型以自然语言形式生成启发式算法与对应的代码实现。

2.采用五种提示策略来指导 LLM 对现有思想和代码进行推理

3.进化出一组候选启发式算法，它利用大语言模型在遗传算子（如交叉变异）种生成新的启发式算法，并通过选择机制引导搜索过程并评估

与大多数进化算法中个体是优化问题的候选解不同，我们认为“思想”的进化应该是一个重要的研究方向

进化框架：

第 0 步：初始化 (Initialization)

通过特定的“初始化提示”（Initialization prompt）来请求大型语言模型（LLM），生成一个包含 N 个初始启发式算法的种群 P。
每个生成的启发式算法都会被评估其性能，并被赋予一个适应度值（fitness value）。

第 1 步：生成新的启发式算法 (Generation of Heuristics)

只要未达到停止条件（例如，预设的代数），系统就会同时使用五种不同的“演化提示策略”（Evolution prompt strategies）来生成总共 5N 个新的启发式算法。
对于这五种策略中的每一种，都会重复执行 N 次以下子流程：
- 第 1.1 步：选择父辈：从当前种群中选择一个或多个父辈启发式算法来构建提示。父辈的选择是基于其适应度排名，排名越高的个体被选中的概率越低（公式为 pi∝1/(ri+N)，其中 ri 是排名），这鼓励了对种群中更多样化个体的探索。
- 第 1.2 步：生成新个体：请求 LLM 根据提示生成一个新的启发式算法，包括其“思想”（自然语言描述）和对应的“代码”实现。
- 第 1.3 步：评估：在指定的评估实例集上运行新生成的启发式算法，以确定其适应度值。
- 第 1.4 步：加入种群：如果新生成的启发式算法及其代码是可行的（例如，没有语法错误），就将其添加到当前种群中。

第 2 步：种群管理 (Population Management)

在生成了多达 5N 个新个体后，将它们与原有的 N 个个体合并。
从这个扩大的种群中，选择出适应度值最高的 N 个启发式算法，形成下一代的种群。
之后，返回第 1 步，开始新一轮的演化。

步骤 0: 初始化 (Initialization)

目标：创建初始种群。
过程：框架首先会创建一个包含 N 个启发式算法的初始种群 P 。这些初始算法并非由人类专家提供，而是通过向 LLM 发送“初始化提示”（Initialization prompt）自动生成的，从而减少了对专家知识的依赖。这个过程会重复
N 次，以获得 N 个初始启发式算法。

步骤 1: 新启发式算法的生成 (Generation of Heuristics)

目标：通过进化操作产生新的、可能更优的启发式算法。
过程：只要未达到停止条件（例如，预设的代数），框架就会利用五种不同的“进化提示策略”（Evolution prompt strategies）来生成新的启发式算法。这些策略分为两大类：
- 探索 (Exploration)：如 E1 和 E2 策略，旨在通过类似交叉的操作探索启发式算法空间，产生与父代差异较大的新想法。
- 修改 (Modification)：如 M1, M2, M3 策略，旨在通过微调、修改参数或简化冗余部分来优化某个父代启发式算法。
**在每一代中，这五种策略会同时被使用，每个策略均被调用 **
N 次，从而生成最多 5N 个新的启发式算法。
生成每一个新算法的具体流程如下：
1. 选择父代 (Parent Selection)：从当前种群中选择一个或多个父代启发式算法。选择过程可以基于适应度排名，适应度高的个体有更高的被选中概率。
2. 生成新个体 (Generation)：将选定的父代（包括其“思想”和“代码”）和相应的策略指令构建成一个提示，请求 LLM 生成一个新的启发式算法（包括新的“思想”和“代码”）。
3. 评估 (Evaluation)：在新生成代码可行的情况下，将其在一组评估实例上运行，以计算出其适应度值。
4. 加入种群 (Addition)：将这个经过评估且可行的新启发式算法添加到当前种群中。

步骤 2: 种群管理 (Population Management)

目标：为下一代选择优胜者。
过程：在 5N 个新个体生成并加入后，种群规模会临时扩大。此时，框架会从扩大的种群中选择适应度最高的 N 个启发式算法，形成下一代的种群。
之后，算法返回****步骤 1，开始新一代的进化。
Heuristic Representation：

自然语言描述 (Natural Language Description)
- 这部分由几句自然语言组成，被称作“思想”（thought）。
- 它由大型语言模型（LLM）创建，用于呈现启发式算法的高级思想和核心逻辑。
代码块 (Code Block)
- 这是对上述“思想”的具体编程实现。
- 代码必须遵循预定义的格式，以便 EoH 框架能够自动识别和无缝集成。在实验中，这通常实现为一个 Python 函数。
- 为了格式化代码块，需要明确指定三个基本组成部分：函数名称、输入变量和输出变量。
适应度值 (Fitness Value)
- 每个启发式算法都会被赋予一个适应度值。
- 这个值是通过在指定问题的一组实例上运行该启发式算法，并评估其性能而获得的。

提示词

初始化提示在我们的实验中，我们使用语言模型（LLMs）生成所有初始启发式算法，无需依赖专家知识。

探索策略 (Exploration Strategies)

探索策略专注于通过对父代启发式算法进行类似交叉的操作来探索更广阔的算法空间。

E1: 差异化探索
目标: 生成与父代尽可能不同的新启发式算法。
过程: 首先，从当前种群中选择 p 个父代启发式算法。然后，提示大型语言模型（LLM）设计一个在思想上与这些父代尽可能不同的新算法，以探索全新的思路。
E2: 共同思想探索
目标: 探索与父代共享相同核心思想但实现方式不同的新启发式算法。
过程: 首先，从当前种群中选择 p 个父代。然后，指令 LLM 识别这些算法背后的共同思想。接着，要求 LLM 在这些共同思想的基础上，通过引入新元素来设计一个尽可能与父代不同的新算法。

修改策略 (Modification Strategies)

修改策略专注于通过调整、修改参数或简化来优化单个父代启发式算法。

M1: 性能改进
目标: 修改一个启发式算法以获得更好的性能。
过程: 从种群中选择一个启发式算法。然后，提示 LLM 对其进行修改，以产生一个新的版本。
M2: 参数调整
目标: 修改一个已选启发式算法的参数。
过程: 从种群中选择一个启发式算法。然后，提示 LLM 尝试在该算法中调整参数，而不是设计一个全新的算法。
M3: 简化与去冗余
目标: 通过移除冗余组件来简化启发式算法。
过程: 从种群中选择一个启发式算法。然后，提示 LLM 分析并识别其主要组成部分，并判断是否存在冗余。最后，要求 LLM 根据其分析结果来简化该算法的代码实现。

选择机制：

排序与排名

把种群中的所有启发式算法按****适应度从好到坏排序。
排名 r_i 是启发式算法 i 的位置（最好的是 1，最差是 N）。

选择的概率公式：p_i∝1/(r_i+N)

概率与排名与 N 的和成反比

也就是排名越好，概率越大

排名越差，值越小，但永远不会是零（所以最差的启发式也有机会被选中）。

加上 N 可以让概率差距变小，保证****探索性，防止过早陷入局部最优。

实验

在线装箱问题：

**这个问题的目标是将一系列不同大小的物品，放入尽可能少的、具有固定容量 **

C 的箱子中。实验重点关注的是“在线场景”，即物品是依次到达的，每当一个物品到达时，必须立即决定将其放入哪个箱子，而不能等待后续物品的信息。

评估实例: 在启发式算法的进化过程中，其性能是在五个大小为 5k（即 5000 个物品）、容量为 100 的 Weibull 实例上进行评估的。

Weibull 实例是指物品大小遵循 Weibull 分布的装箱问题实例，这种分布常用于模拟实际应用中的物品大小。

适应度计算: 一个启发式算法的适应度值被设定为在这五个实例上 lb/n 的平均值。

其中， lb ** 代表理论上最优解（即最少箱子数）的下限。比如直接总容量除以单个容量**
n 是被评估的启发式算法完成所有物品装箱后，实际使用的箱子总数。
这个比率越高，说明算法使用的箱子数越接近理论最优值，性能也就越好。

比较方法即人工 +funsearch

tsp

目标 (Objective)

旅行商问题（TSP）的目标是找到一条最短的路线，这条路线需要访问所有给定的地点各一次，并最终返回到出发点。它是一个被广泛研究的组合优化问题，也是一个常用的启发式算法测试平台。

评估设置 (Evaluation Setup)

评估实例: 启发式算法的进化（训练）过程是在一组 64 个 TSP100（即 100 个地点）的实例上进行的。这些实例中的地点位置是从一个 [0, 1]² 的二维空间中随机抽样生成的。

也就是六十四个场景。边长为 1 的正方形区域，100 个地点的位置（即 X, Y 坐标）都是在这个 1x1 的正方形地图上****随机生成的

适应度计算: 一个启发式算法的适应度值，是根据其解法与最优解之间的“平均差距”（average gap）来确定的。这个用于计算差距的最优解是由一个名为“Concorde”的精确求解器生成的。

最优解 (Optimal Solution): 对于每一个 TSP 问题，理论上都存在一个唯一的最短路径。研究人员使用一个叫做 Concorde 的顶尖求解器，它非常强大，可以计算出这 100 个地点问题的精确最优解

差距 (Gap): 当一个待评估的启发式算法对某个问题给出一个解（一条路径）后，研究人员会计算这个解的长度与“标准答案”的长度之间的百分比差异。这个差异就是“差距（Gap）”。例如，如果标准答案是 100 公里，算法算出来是 102 公里，那么差距就是 2%。

平均差距 (Average Gap): 算法会在全部 64 个实例上运行，得到 64 个“差距”值。最后，计算这 64 个值的平均数。

适应度值 (Fitness Value): 这个最终的平均差距就被用作该算法的适应度值。这个值越小，说明算法的解越接近最优解，性能就越好。

比较方法是最近插入法和最远插入法，加上 ORtools

AI 方面

实验细节

感觉就是人类定了大方向与框架，然后 llm 负责实现与迭代

结果：

X 轴 代表“进化代数”（Number of generations），从第 1 代到第 20 代。

Y 轴 代表“性能”（Performance），这个值越高，说明算法的效果越好。

红色的折线 显示了在每一代中发现的最佳启发式算法的性能。您可以看到，性能从最初的 0.9620，经过 20 代的持续优化，最终达到了 0.9932。

折线上的每个红点都代表一个性能上的“飞跃”，即发现了一个更好的启发式算法。

**旁边的标注（如 **E1, E2, M1）指明了这是由哪一种“提示策略”实现的突破。

**标注的文字（如 **E2, utilization of cubic root）则是对这个新算法核心思想的简要描述，也就是“思想”（Thought）。

人类想到的，算出一个物品大小和容量，然后做差，差最大的说明放完东西后，箱子剩下的空间最小

AI 想到的，comb1 项通过 (bins - max_bin)**2 惩罚那些容量较大（较空）的箱子，鼓励利用已部分填充的箱子。

comb2 和 comb3 项则包含了物品大小和箱子容量的二次方和三次方关系。

但是物理意义不直观

EoH，显式地融合了多种启发式思想：

利用率 (ulti): 衡量放入物品后箱子有多满。
动态调整 (adjust): 使用 where 条件语句，根据剩余空间和物品大小的关系，采取不同的策略，实现了“惩罚大箱子”的逻辑。
混合分数 (hybrid_exp, adjust): 将多个不同来源的启发式思想（如指数衰减、利用率、条件惩罚）组合成最终的得分。

消融研究指的是，为了理解一个复杂模型或系统的各个组成部分的重要性，而系统性地“移除”或“简化”其中一个或多个组件，然后观察整个系统性能变化的一种实验方法。

根据论文 4.3 节的描述，作者进行消融研究的目的是“为了更好地理解 EoH 中主要组成部分的贡献” 。

具体做法是，他们创建了几个“被削弱”的 EoH 版本，并与完整的 EoH 模型进行性能比较：

移除了“思想”部分: 他们创建了一个名为 EoC (Evolution of Codes) 的版本。这个版本只进化代码，完全没有自然语言的“思想”部分，以此来验证“思想”这个组件的价值。

移除了部分“提示策略”: 他们还创建了 EoH-e1 和 EoH-e2 版本。这些版本虽然保留了“思想”，但只使用了五种提示策略中的一种或两种。

讨论

为了证明 EoH 中“思想”（自然语言描述）和“代码”共同进化是其核心优势，研究者进行了对比实验。

实验设置: 他们将完整的 EoH 与几个变体进行了比较：

C2C: 只进化代码，没有“思想”部分。

T2T2C: 只在进化中使用“思想”表示，需要时再由 LLM 生成代码用于评估。

T&C2T2C: 进化时同时使用“思想”和“代码”作为输入，但只让 LLM 输出新的“思想”

结论: 实验结果（表 6）明确表明，只进化代码（C2C）或只进化思想（T2T2C）的效果远不如完整的 EoH 。这有力地证明了**“思想”和“代码”的共同进化对 EoH 的成功做出了重大贡献** 。

不同大型语言模型的影响 (Different LLMs)

研究者测试了 EoH 在使用不同 LLM 时的性能，包括 GPT-3.5、Gemini Pro、CodeLlama 和 Deepseek 。

结论:
- EoH 在使用这些不同的 LLM 时，都能够生成性能良好的启发式算法。
- 即使只进行 2000 次查询，其性能也优于随机查询 GPT-3.5 一万次的结果。
- 尽管如此，实验结果也显示，使用更强大的 LLM（如 GPT-3.5 和 Gemini Pro）能带来更好的性能。

利用专家启发式算法 (Use of Expert Heuristic)

研究者探究了将一个已知的、由人类专家或其它 AI 系统设计的优秀算法（专家启发式算法）放入 EoH 的初始种群中会产生什么影响。

实验设置: 他们将 FunSearch 论文中提供的优秀启发式算法放入 EoH 的初始种群，并将这个版本称为 EoH expert 。

结论: 结果显示，EoH expert 的性能明显超过了原始的 EoH 和 FunSearch 。这表明，EoH 框架可以有效地继承和进化已有的专家知识，从而产生更优秀的下一代算法 。