基于LLM的双组件耦合组合优化协同进化自动启发式设计

# LLM驱动的双组分耦合组合优化协同进化自动启发式设计

**来源:** https://arxiv.org/html/2606.00718

**作者:**

Mingen Kuang  
西安交通大学  
kuangme@stu\.xjtu\.edu\.cn

&Xudong Deng¹¹footnotemark:1  
西安交通大学  
dxd3125307059@stu\.xjtu\.edu\.cn

&Xi Lin  
西安交通大学  
xi\.lin@xjtu\.edu\.cn

Ye Fan  
西北工业大学  
fanye@nwpu\.edu\.cn

&Jianyong Sun  
西安交通大学  
jy\.sun@xjtu\.edu\.cn

&Jialong Shi  
西安交通大学  
jialong\.shi@xjtu\.edu\.cn

###### 摘要

尽管大语言模型（LLMs）近期在自动启发式设计（AHD）中显示出潜力，但现有方法通常将启发式作为单一算子或搜索策略进行生成和演化，限制了其建模旅行窃贼问题（TTP）和旅行购买者问题（TPP）等多决策子结构之间强耦合的能力。本文提出CoEvo-AHD，一种LLM驱动的双种群协同进化框架，用于耦合组合优化中的自动启发式设计。与以往孤立演化单个启发式的方法不同，CoEvo-AHD利用LLM协同进化两个紧密相关的算子种群。一种协作评估机制显式捕获路径算子和选择算子之间的交互，同时配对评分和协同联合交叉有助于发现互补的算子逻辑，从而在耦合决策子空间内实现联合改进。我们进一步设计了一个工具调用环境库，将常用的核心操作（如局部搜索增量计算）封装为可调用函数，使得LLM生成的算子能够使用标准化接口，而无需重新实现低效且易出错的问题特定循环。在TTP和TPP上的实验表明，CoEvo-AHD能够自动发现协作启发式组合，并达到与经典启发式相竞争的解质量。

## 1 引言

大语言模型（LLMs）近期为自动启发式设计开辟了新方向，使得可执行启发式能够在有限人工干预下生成、评估和优化。现有的LLM驱动方法通过迭代的生成、评估、反馈和再生成循环，在生成启发式函数、构造规则或局部搜索算子方面取得了令人鼓舞的成果[24 (https://arxiv.org/html/2606.00718#bib.bib1), 28 (https://arxiv.org/html/2606.00718#bib.bib39), 15 (https://arxiv.org/html/2606.00718#bib.bib2), 30 (https://arxiv.org/html/2606.00718#bib.bib3)]。然而，这些方法大多仍将生成的启发式视为孤立的算法单元。这一假设在许多现实世界组合优化（CO）问题中具有局限性，因为此类问题的解由多个相互依赖的决策组件构成，单个局部移动的效果无法仅在一个组件内评估。

我们用“双组分耦合CO”指代那些解可分解为两个语义不同组件的问题，且修改任一组件的可行性或目标效果取决于另一组件的状态。在此类问题中，组件算子的效用本质上是关系性的而非内在的：它不仅取决于算子如何修改自身组件，还取决于这一修改如何与另一组件交互。因此，独立设计或评估两个组件的算子可能导致局部可行但与联合目标不一致的移动。旅行窃贼问题（TTP）[3 (https://arxiv.org/html/2606.00718#bib.bib43), 21 (https://arxiv.org/html/2606.00718#bib.bib44)]和旅行购买者问题（TPP）[16 (https://arxiv.org/html/2606.00718#bib.bib14)]是此类设定的代表性示例。它们之间的耦合方式不同：TTP将路径规划与负载相关的旅行成本耦合，其中旅行顺序影响携带所选物品的成本，而打包方案又改变路径移动的评估；TPP将路径规划与市场相关的采购可行性和成本耦合，其中市场选择、访问顺序、价格、供应和需求满足共同决定解质量。这些问题揭示了一个共同挑战：高质量搜索不仅需要强大的组件级算子，还需要在完整耦合目标下行为协调的算子对。

尽管近期基于LLM的研究已开始探索启发式集合和多算子协作[14 (https://arxiv.org/html/2606.00718#bib.bib42), 32 (https://arxiv.org/html/2606.00718#bib.bib40), 22 (https://arxiv.org/html/2606.00718#bib.bib41), 11 (https://arxiv.org/html/2606.00718#bib.bib7)]，但其关注点主要在于通用搜索框架内算法角色之间的互补性，例如构造策略、破坏-修复算子或搜索策略组合。相比之下，双组分耦合CO需要建模解本身决策组件之间的互补性。因此，关键问题不仅仅是LLM能否生成更强的单个启发式，而是它们能否生成并优化成对的组件算子，其有效性需在完整耦合目标下进行联合评估。

为解决这一问题，我们提出CoEvo-AHD，一种LLM驱动的协同进化自动启发式设计框架，用于双组分耦合CO。CoEvo-AHD维护两个特定组件的算子种群，并利用LLM生成、重写和重组可执行组件算子。CoEvo-AHD不是孤立地对算子打分，而是将选定的算子对嵌入完整解上的搜索轨迹中，在必要时应用可行性修复或组件重构，并在完整耦合目标下评估生成的解。所获得的奖励同时更新单个算子得分和配对协同得分，使进化选择压力与算子效用的关系性本质保持一致。除了组件内变异和交叉，CoEvo-AHD还对高性能算子对执行跨组件联合交叉，鼓励新生成的算子共享兼容的通信协议和互补的搜索假设。

CoEvo-AHD进一步引入了结构化的组件间通信和工具增强的问题环境。通信协议指定可以交换的信息类型，例如搜索状态、候选修改建议和局部评估信号，而不直接指定利用这些信号的启发式逻辑。这些信号被视为可验证的搜索建议，仅在候选构造、修复或重构以及完整目标评估之后才能被接受。工具增强的问题环境暴露了用于目标评估、可行性修复、组件重构、边际分析和增量评估的可靠原语，使得LLM生成的代码能够专注于邻域设计和跨组件搜索决策，而非容易出错的低级实现。

本文的贡献有三方面。首先，我们形式化了双组分耦合CO的LLM驱动自动启发式设计问题，其中算子效用是关系性的，必须通过两个异构解组件之间的交互来评估。其次，我们提出CoEvo-AHD，一种协同进化框架，包含特定组件的算子种群、基于配对执行的评估以及用于选择互补算子对的配对协同得分。第三，我们设计了结构化组件通信、跨组件联合交叉和工具增强的问题环境，并在两个代表性问题TTP和TPP上实例化该框架，评估其有效性。

## 2 相关工作

### 2.1 LLM驱动的自动启发式设计

启发式算法在组合优化中广泛使用，但其设计通常依赖于解表示、邻域结构和修复策略的手工设定。大语言模型（LLMs）的近期进展使得LLM驱动的自动启发式设计（LLM-AHD）成为可能，即可执行的启发式代码可以通过程序搜索进行生成和优化。FunSearch将LLM与自动评估器结合，搜索可执行函数[24 (https://arxiv.org/html/2606.00718#bib.bib1)]。EoH将启发式设计表述为自然语言思想和可执行代码的联合进化[15 (https://arxiv.org/html/2606.00718#bib.bib2)]，而ReEvo引入反思进化，将历史搜索性能转化为语言反馈[30 (https://arxiv.org/html/2606.00718#bib.bib3)]。HSEvo、MCTS-AHD和MEoH进一步将LLM-AHD扩展到种群多样性、树搜索探索和多目标启发式进化等方面[4 (https://arxiv.org/html/2606.00718#bib.bib4), 33 (https://arxiv.org/html/2606.00718#bib.bib5), 29 (https://arxiv.org/html/2606.00718#bib.bib6)]。这些研究表明LLM-AHD能够处理比单个启发式更复杂的算法结构，但算子互补性主要发生在算法角色层面。相比之下，我们的工作将算子绑定到完整解的异构组件上，其效用取决于组件间交互而非算法工作流，从而在问题结构层面建模互补性。

### 2.2 多算子协作与本工作的定位

近期研究已将LLM-AHD扩展到多算子协作。EoH-S生成互补启发式集合以改善跨实例泛化能力[14 (https://arxiv.org/html/2606.00718#bib.bib42)]。G-LNS在大邻域搜索框架内协同进化破坏算子和修复算子，并通过协作评估建模其互补性[32 (https://arxiv.org/html/2606.00718#bib.bib40)]。E2OC将多目标进化算法中的相互依赖算子形式化为序贯决策问题[22 (https://arxiv.org/html/2606.00718#bib.bib41)]。MOTIF从多策略和多智能体角度扩展了自动求解器设计[11 (https://arxiv.org/html/2606.00718#bib.bib7)]。这些研究表明LLM-AHD能够处理比单个启发式更复杂的算法结构，但算子互补性仍主要局限于搜索框架内的算法角色。相比之下，我们的工作聚焦于问题本身结构所引发的互补性。CoEvo-AHD中的算子与解的异构组件绑定，其有效性取决于跨组件交互而非工作流角色。这一定位使我们能够通过特定组件的种群、基于配对执行的评估、配对协同得分和跨组件联合交叉来建模问题结构引发的互补性。

### 2.3 双组分耦合CO：TTP和TPP

许多现实世界的组合优化问题涉及多个相互依赖的子问题。我们使用旅行窃贼问题（TTP）和旅行购买者问题（TPP）作为代表性的双组分耦合CO基准。TTP将旅行商问题与0-1背包问题耦合：路径决策决定访问顺序和收集的物品，而物品选择影响旅行速度和成本[3 (https://arxiv.org/html/2606.00718#bib.bib43), 21 (https://arxiv.org/html/2606.00718#bib.bib44)]。TPP联合涉及市场选择、购买决策和路线优化，以最小化旅行和购买成本之和[16 (https://arxiv.org/html/2606.00718#bib.bib14)]。针对TTP和TPP的现有算法包括分阶段启发式、模因算法、蚁群优化、禁忌搜索、分支定界和ALNS变体等[7 (https://arxiv.org/html/2606.00718#bib.bib8), 17 (https://arxiv.org/html/2606.00718#bib.bib10), 5 (https://arxiv.org/html/2606.00718#bib.bib9), 26 (https://arxiv.org/html/2606.00718#bib.bib11), 27 (https://arxiv.org/html/2606.00718#bib.bib12), 9 (https://arxiv.org/html/2606.00718#bib.bib15), 19 (https://arxiv.org/html/2606.00718#bib.bib16), 20 (https://arxiv.org/html/2606.00718#bib.bib17), 1 (https://arxiv.org/html/2606.00718#bib.bib18), 25 (https://arxiv.org/html/2606.00718#bib.bib19), 2 (https://arxiv.org/html/2606.00718#bib.bib21), 8 (https://arxiv.org/html/2606.00718#bib.bib22), 13 (https://arxiv.org/html/2606.00718#bib.bib20), 31 (https://arxiv.org/html/2606.00718#bib.bib23), 10 (https://arxiv.org/html/2606.00718#bib.bib25), 12 (https://arxiv.org/html/2606.00718#bib.bib24)]。CoCo明确强调了TTP中路径规划和打包之间的协调[18 (https://arxiv.org/html/2606.00718#bib.bib13)]。然而，大多数传统方法依赖手工设计的跨组件协调机制，这些机制问题特定、难以迁移且需要大量调参。相比之下，CoEvo-AHD利用LLM自动生成组件级算子，并通过基于配对执行的评估和协同进化选择互补的算子对，减少了对手工规则和专家干预的依赖。这一定位凸显了CoEvo-AHD的新颖之处不仅在于利用LLM生成启发式，还在于显式建模并利用“问题结构引发的算子互补性”来解决双组分耦合组合优化问题。

## 3 方法

### 3.1 框架概述

CoEvo-AHD包含四个阶段：初始化、协作评估、种群管理和LLM驱动的进化。在初始化阶段，为两个决策组件分别构建算子种群。在协作评估阶段，在训练实例上联合评估组件算子对。种群管理阶段修剪低性能算子，而LLM驱动的进化阶段通过组件内变异、组件内同质交叉和跨组件协作联合交叉生成新算子。这些阶段共同形成一个生成、评估、反馈和再生成的闭环，使得LLM产生的启发式逻辑能够在真实优化反馈下不断改进。

图1: CoEvo-AHD框架概述。该框架包括四个阶段：初始化、协作评估、种群管理和LLM驱动的进化。维护两个特定组件的算子种群，并通过配对评估、分数更新、修剪、变异、同质交叉和跨组件联合交叉进行协同进化。

### 3.2 初始化

对于一个双组分耦合优化问题，我们将完整解表示为 \(x=(x^A, x^B)\)，其中 \(x^A\) 和 \(x^B\) 对应于两个异构但相互依赖的决策组件。CoEvo-AHD初始化两个特定组件的算子种群：

\[
\mathcal{P}^A = \{o^A_1, o^A_2, \ldots, o^A_N\}, \quad \mathcal{P}^B = \{o^B_1, o^B_2, \ldots, o^B_N\}.
\]

对于TTP，两个种群分别对应路径算子和打包算子。对于TPP，它们对应旅行算子和购买算子。初始种群来自两个来源。首先，我们包含少量手工指定的种子算子，以提供有效的可执行起点和基本搜索行为。其次，我们使用LLM在以下条件下生成额外的算子：