arXiv:2606.00718cs.AImath.OC2026-06被引 1

用大模型协同进化双类启发式,提升耦合组合优化求解质量。

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

论文配图:LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization
图 1 · 摘自论文原文
  • 通过双种群协同进化,让两类算子互相配合
  • 在旅行商采购问题上达到传统启发式水平
  • 自动生成可调用算子,避免重复编码错误

尽管大型语言模型(LLMs)在自动启发式设计(AHD)中展现出潜力,但现有方法通常将启发式作为单一算子或搜索策略进行演化,难以建模如旅行商问题(TTP)和旅行采购问题(TPP)中多个决策子结构间的强耦合关系。本文提出CoEvo-AHD,一种基于大模型的双种群协同进化框架,用于耦合组合优化中的自动启发式设计。与以往独立演化单个启发式的做法不同,CoEvo-AHD利用大模型协同演化两组紧密相关的算子群体。通过合作评估机制显式捕捉路径与选择算子之间的交互关系,结合成对评分与协同交叉操作,发现互补的算子逻辑,实现耦合决策空间的联合优化。我们还设计了一个工具调用环境库,封装了局部搜索增量计算等常用核心操作,使大模型生成的算子可通过标准化接口调用,而非重复编写低效且易错的问题特定循环。在TTP和TPP上的实验表明,CoEvo-AHD能自动发现协作性启发式组合,并达到与传统启发式相当的求解质量。

原文摘要 · Abstract (English)

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing methods typically generate and evolve heuristics as a single operator or search strategy, limiting their ability to model strong coupling among multiple decision substructures in problems such as the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP). In this work, we propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated heuristic design in coupled combinatorial optimization. Unlike prior methods that evolve individual heuristics in isolation, CoEvo-AHD leverages LLMs to co-evolve two closely related operator populations. A cooperative evaluation mechanism explicitly captures interactions between route and selection operators, while pairwise scoring and synergistic joint crossover help discover complementary operator logic for joint improvement across coupled decision subspaces. We further design a tool-invocation environment library that encapsulates frequently used core operations, such as local-search delta computation, into callable functions, enabling LLM-generated operators to use standardized interfaces instead of reimplementing inefficient and error-prone problem-specific loops. Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics.

启发式设计大模型组合优化协同进化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。