🤖 AI

LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization

本文介绍了 CoEvo-AHD，这是一个由大语言模型驱动的双种群协同进化框架，该框架通过在标准化的工具调用环境中进化相互作用的路径算子与选择算子，自动为双组件耦合的组合优化问题设计协作启发式算法，以实现具有竞争力的解质量。

原作者： Mingen Kuang, Xudong Deng, Xi Lin, Ye Fan, Jianyong Sun, Jialong Shi

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Mingen Kuang, Xudong Deng, Xi Lin, Ye Fan, Jianyong Sun, Jialong Shi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图解开一个巨大的、分为两部分的谜题，其中第一部分的规则会彻底改变第二部分的规则。

这篇论文介绍了一种名为 CoEvo-AHD（协同进化自动化启发式设计）的新方法。你可以把它想象成一个“教练”，它利用超智能 AI（大语言模型，简称 LLM）来自动发明并改进解决这些棘手谜题的规则。

以下是使用简单类比进行的详细拆解：

1. 问题所在：耦合的谜题

该论文专注于两种特定类型的难题：

旅行大盗问题 (Traveling Thief Problem, TTP)： 想象一个大盗需要访问不同的城市去偷东西。但问题在于：包里的东西越重，他走得就越慢。因此，访问城市的顺序（路径）会改变包的感觉有多重，而决定偷什么（装载）又会改变他的移动速度。
旅行采购者问题 (Traveling Purchaser Problem, TPP)： 想象一位购物者需要访问不同的市场来购买宴会的食材。但是，食材的价格和供应情况会根据他访问市场的方式以及访问顺序而发生变化。

在这些案例中，你不能仅仅分别解决“路径”部分和“购物”部分。它们是耦合在一起的——就像一场舞蹈，其中一个舞伴的动作决定了另一个舞伴的下一步。如果你在不考虑购物情况的情况下优化路径，你可能会得到一条完美的路径，但最后却发现商店里空空如也。

2. 旧的方法：独奏艺术家

以往的方法尝试使用 AI 来发明一个单一的“超级规则”（启发式算法）来解决整个问题。

类比： 这就像雇佣一位厨师来烹饪一道复杂的两道菜套餐。他们可能很擅长做前菜，但可能会毁掉主菜，因为他们没有意识到这两道菜需要不同的调味才能完美契合。AI 会尝试进化出一条通用的规则来应对一切，但这往往会导致它无法洞察到两个部分之间深层的联系。

3. 新的方法：协同进化的舞伴组合 (CoEvo-AHD)

作者提出了一个新的框架，在这个框架中，AI 不仅仅是制作一条规则，而是创建两支独立的规则团队，让它们协同进化。

A 队（路径团队）： 这些规则只专注于如何在城市之间移动。
B 队（装载/购物团队）： 这些规则只专注于挑选或购买什么。

它们是如何协作的：
与其将 A 队和 B 队分开测试，系统会让它们一起跳舞。

舞池： AI 从 A 队中挑选一条规则，从 B 队中挑选一条规则，让它们同时处理一个问题。
评分： 它们根据作为“一对”的表现获得分数。如果路径规则建议的路径让购物规则表现得很糟糕，那么它们两个都会得到低分。如果它们能够互补，则会得到高分。
进化： AI 利用这些反馈来“繁衍”出新的规则。它可能会选取最好的路径规则和最好的购物规则，并要求 AI 重写它们，使它们能更好地理解彼此。这被称为跨组件联合交叉 (Cross-Component Joint Crossover)。

4. “工具箱”优势

该论文的一个核心创新是给了 AI 一个标准化的工具箱。

类比： 想象要求一个人类编写一个计算机程序来计算城市之间的距离。他们可能会每次都从头开始写一个笨拙且易错的循环。
论文的解决方案： 系统为 AI 提供了一个可靠函数的预建“工具箱”（例如“计算距离”、“检查包是否已满”或“修复非法路径”）。AI 不需要重新发明轮子；它只需要专注于何时使用这些工具的策略。这防止了 AI 写出有 Bug 的代码，并让它能够专注于创造性的逻辑。

5. 结果：更好的舞蹈

作者在“旅行大盗”和“旅行采购者”问题上测试了该方法。

结果： “舞伴组合”方法 (CoEvo-AHD) 始终比那些尝试将部分分开解决的传统方法或旧的 AI 技术找到了更好的解决方案。
为什么有效： 通过强制两个规则团队进行协同进化，并根据它们的协作能力进行评判，系统发现了那些单一规则或分离式方法永远无法发现的策略。它学到了：有时，走一段稍长的路径是值得的，如果这能让你买到更便宜的物品；或者，减轻负重可以让你可以访问更多的城市。

总结

简而言之，这篇论文教会了 AI 如何停止尝试成为一名“独奏乐手”，转而开始扮演一个爵士乐团。它创建了两组音乐家（一组负责路径，一组负责选择），让他们一起演奏，并使用一位聪明的指挥家（LLM）根据他们的和谐程度来重写乐谱。其结果是一种更高效、更有创意的解决复杂且相互关联的现实世界问题的方法。

技术摘要：面向双组件耦合组合优化的 CoEvo-AHD

1. 问题定义

本文研究了双组件耦合组合优化 (CO) 问题，其中解由两个语义不同但相互依赖的决策组件组成。核心挑战在于，修改其中一个组件的可行性或目标值完全取决于另一个组件的状态。因此，算子的效用是关系型的而非本质性的；一个在孤立状态下表现良好的算子，在与第二个组件的次优状态耦合时，可能会降低全局解的质量。

作者在两个代表性问题上实例化了这一框架：

窃贼旅行问题 (TTP)： 将路径规划（旅行商问题）与装载（0-1 背包问题）耦合。旅行顺序会根据携带的载荷影响行驶速度，而装载计划则决定了每一步携带的重量。
旅行采购商问题 (TPP)： 将市场选择/路径规划与采购决策耦合。访问顺序和市场选择决定了可行的采购选项和成本，而采购决策则会影响访问特定市场的价值。

现有的由大语言模型 (LLM) 驱动的自动化启发式设计 (AHD) 方法通常将启发式算法作为孤立的算法单元或搜索策略（例如构造型 vs. 修复型）进行演化。这些方法无法捕捉双组件耦合问题所要求的问题结构诱导的互补性，在这种问题中，算子必须进行协同演化，以便在异构的解组件之间实现协同工作。

2. 方法论：CoEvo-AHD

作者提出了 CoEvo-AHD，这是一个由 LLM 驱动的双种群协同演化框架，旨在自动发现并精炼配对的组件算子。该框架通过四个阶段运行：

2.1 双种群初始化

维护两个独立的算子种群：用于组件 A（如路径算子）的 $P_A$ 和用于组件 B（如装载算子）的 $P_B$ 。

初始化： 种群从混合了手动指定的种子算子和 LLM 生成的算子开始。
验证： 所有生成的算子在进入种群前，必须经过语法、接口、边界执行和组件可行性的验证。
接口： 算子仅返回其特定组件的候选更新，依赖于共享的信息记忆和外部工具来获取全局上下文。

2.2 协作评估

不同于传统方法在孤立状态下对算子进行评分，CoEvo-AHD 通过在完整解上的配对执行来评估算子。

选择： 每次搜索重启时，采用局部汤普森采样 (Thompson Sampling) 策略为每个搜索过程选择一个来自 $P_A$ 的算子和一个来自 $P_B$ 的算子。
交替优化： 被选中的算子对在搜索轨迹中交替调用。例如，一个路径算子提出一个城市排列，然后将其传递给装载算子（或反之）。
修复与重构： 由于组件是耦合的，中间候选解可能不可行。框架利用工具增强的问题环境来进行可行性修复、重构和全目标函数评估。
共享信息： 一个可变的字典 (shared_info) 允许算子交换软搜索信号（例如，载荷分布、候选插入线索），而不会直接覆盖另一个组件的逻辑。

2.3 种群管理与演化

框架采用协同演化循环来精炼种群：

评分： 基于完整耦合解的改进程度计算奖励。这些奖励会更新三个统计量： $o_A$ 和 $o_B$ 的个体得分，以及特定算子对的成对协同得分 ( $S_{ij}$ )。
剪枝： 从各自的种群中移除表现较差的算子。
LLM 驱动的演化： 通过三种演化操作填补空缺：
1. 组件内变异： 精炼单个父代算子。
2. 组件内同质交叉： 重组来自同一种群的两个算子。
3. 跨组件联合交叉： 根据协同得分选择表现最好的算子对 $(o_A^*, o_B^*)$ ，并提示 LLM 将它们重写为一个统一的、协调的实体。这鼓励生成具有兼容通信协议和互补搜索假设的算子。

2.4 工具增强环境

为了防止 LLM 生成低效或易错的底层代码，框架将核心操作（如局部搜索增量计算、贪婪重构、可行性检查）封装进标准化的可调用工具中。这使得 LLM 生成的算子能够专注于高层级的邻域设计和跨组件协调。

3. 核心贡献

问题建模： 本文专门针对双组件耦合组合优化制定了 LLM 驱动的 AHD 形式，将算子效用定义为关系型的，并需要跨异构决策组件进行联合评估。
CoEvo-AHD 框架： 一种新型的协同演化架构，其特点包括：
- 组件特定的算子种群。
- 基于配对执行的评估方式，以捕捉跨组件交互。
- 用于引导互补算子对选择的成对协同评分。
- 跨组件联合交叉，以演化出相互兼容的算子。
结构化通信与工具化： 引入了结构化的组件间通信协议和工具增强环境，使问题特定的操作标准化，从而使 LLM 能够生成鲁棒的高层启发式逻辑。

4. 实验结果

该框架在 TTP 和 TPP 基准测试上针对最先进的传统启发式算法和近期的基于 LLM 的基准方法进行了评估。

窃贼旅行问题 (TTP)：
- CoEvo-AHD 在中小规模实例（TTP20, TTP50）上取得了最佳结果，超越了 MATLS、S5 和 CoCo 等基准方法。
- 在大规模实例（TTP100, TTP200）上，它取得了第二优的整体平均值，仅次于 CoCo，但显著优于 MATLS 和 S5。
- 这表明该框架能有效捕捉较小搜索空间中的耦合，但在极大规模实例中面临搜索深度的挑战。
旅行采购商问题 (TPP)：
- CoEvo-AHD 展示了显著的整体优势，在五个实例规模（包括 150×100 和 150×150 等大规模规模）上取得了最佳结果，并在另外三个规模上取得了第二优的结果。
- 与第二优的基准方法 (TA) 相比，它降低了约 2.76% 的平均目标函数值；与 ALNS 相比，降幅高达 11.42%。
- 结果表明，该框架在利用 TPP 中路径规划与采购决策之间的协同效应方面特别有效。
消融实验：
- 移除双种群协同演化（仅演化其中一个组件）会导致性能显著下降（例如在 TPP 上下降约 11%），证实了孤立优化组件是不充分的。
- 移除工具增强环境也会导致性能下降（在 TTP 上下降约 5.5%），强调了标准化接口对于可靠性和效率的重要性。

5. 重要性与主张

本文主张，CoEvo-AHD 代表了 LLM 驱动的 AHD 从生成孤立的算法角色向建模问题结构诱导的算子互补性的转变。通过显式地协同演化异构算子种群并通过联合执行进行评估，该框架解决了现有方法无法处理强耦合决策子结构的问题。

作者认为，这项工作是迈向更通用的自动化启发式设计的一步，旨在解决现实世界中复杂的、组件间深度相互依赖的优化问题。作者也谦虚地指出，虽然该框架具有很强的竞争力，但在超大规模实例的搜索深度和鲁棒性方面仍有提升空间，未来的工作将致力于将该框架扩展到具有两个以上耦合组件的问题中。