跳转至

Pareto-Grid-Guided Large Language Models for Fast and High-Quality Heuristics Design in Multi-Objective Combinatorial Optimization

会议: AAAI 2026
arXiv: 2507.20923
代码: GitHub
领域: 组合优化 / LLM 自动启发式设计
关键词: Multi-Objective Optimization, LLM, Pareto Front Grid, SEMO, 启发式生成, 语义多样性

一句话总结

提出 MPaGE 框架，将 LLM 与 Pareto Front Grid 机制和语义聚类结合，自动为多目标组合优化问题生成兼顾解质量与运行效率的启发式算法，在 Bi-TSP、Tri-TSP、Bi-CVRP、Bi-KP 上 HV 和 IGD 均显著优于 EoH、MEoH 等基线。

背景与动机

多目标组合优化问题 (MOCOP) 在车辆路径规划、生产调度等场景中普遍存在，需在冲突的多个目标间找到 Pareto 最优前沿。传统进化算法（NSGA-II、MOEA/D）依赖领域知识和参数调优，泛化能力有限。

近年来 LLM 在自动启发式设计方面展现了强大能力（EoH、FunSearch、ReEvo），利用代码生成直接产出可执行的优化算法。然而现有 LLM-based 方法主要聚焦单目标，在多目标场景存在三个关键问题：(1) 忽略运行时效率——仅优化解质量；(2) 种群中启发式逻辑高度相似——相似实现不同表达导致多样性假象；(3) 缺乏结构化的目标空间引导。

核心问题

如何系统地利用 LLM 为 MOCOP 自动设计一组 Pareto 最优的启发式算法，同时优化解质量和运行效率，并保持启发式之间的语义多样性？

方法详解

整体框架

MPaGE 在 SEMO (Simple Evolutionary Multiobjective Optimization) 范式下运行，迭代进化 heuristic 种群。每个 heuristic 编码为自然语言描述 + Python 代码，评估指标为两个目标：\(e_1\)（负 hypervolume，衡量解质量）和 \(e_2\)（运行时间）。

关键设计

Pareto Front Grid (PFG): 将目标空间 \([0,1]^2\) 划分为网格，每个 cell 内做 non-dominated sorting 保留精英个体：

\[G(h_i) = \left(\left\lfloor \frac{e_1(h_i)}{\delta_1} \right\rfloor, \left\lfloor \frac{e_2(h_i)}{\delta_2} \right\rfloor\right)\]

选择策略以概率 \(\epsilon=0.9\) 从相邻 grid cell 中选取父代（局部开发），否则从全局精英集选取（全局探索）。

Semantic Clustering: 使用 LLM（GPT-4o）分析精英 heuristic 的语义结构，将逻辑相似但实现不同的 heuristic 聚为一类：

\[\text{SemClust}(P) = \{C_1, C_2, \ldots, C_m\}, \quad \bigcup C_i = P, \quad C_i \cap C_j = \emptyset\]

变异在簇内进行（探索局部变体），交叉在簇间进行（组合不同行为），以概率 \(\gamma=0.3\) 选择变异还是交叉。

Feedback Reflection: 对每对父代 heuristic，LLM 先分析各自优缺点生成文本建议，再基于反馈指导后代生成——相当于 evolutionary operator 中嵌入了 LLM 推理。

自动生成流程

  1. LLM 初始化种群（描述 + 代码）
  2. PFG 划分目标空间，构建精英池
  3. 语义聚类 → 跨簇交叉 / 簇内变异
  4. Feedback reflection 引导后代生成
  5. Non-dominated sorting 更新种群
  6. 迭代至停止条件

实验关键数据

方法 Bi-TSP20 HV↑ Bi-TSP20 IGD↓ Tri-TSP20 HV↑ Bi-CVRP50 HV↑ Bi-KP50 HV↑
EoH 0.756 0.117 0.755 0.957 0.602
MEoH 0.724 0.067 0.884 0.322 0.748
ReEvo 0.541 0.435 0.694 0.658 0.996
MPaGE 0.911 0.010 0.936 0.980 0.932

泛化性（Bi-TSP，out-of-distribution 问题规模）： - TSP20: HV 0.629 (MPaGE best) vs 0.603 (MEoH best)，加速 165× - TSP50: HV 0.542 vs 0.480，加速 126× - TSP100: HV 0.442 vs 0.395，79×

相比传统 MOEA（如 NSGA-II, PFG-MOEA），MPaGE 生成的 heuristic 运行速度快 50-200×，HV 接近或更优。

亮点

  • 首次在标准 MOCOP benchmark 上系统评估 LLM 生成的启发式，同时优化质量和效率
  • 语义聚类解决了 AST-based 方法无法区分"逻辑相同、实现不同"heuristic 的问题
  • PFG 网格机制在目标空间上既保持多样性又引导收敛
  • 生成的 best heuristic 在 out-of-distribution 规模上仍有良好泛化
  • 实验配置轻量（M1 Mac + 8GB RAM），实用性强

局限与展望

  • 依赖 GPT-4o/4o-mini，LLM 调用成本和延迟可能成为瓶颈
  • 种群规模和迭代次数较小（10 个体、20 代），更大规模搜索空间效果未知
  • 仅考虑两个优化目标（质量+时间），更多目标（如代码复杂度、泛化性）的扩展待探索
  • 语义聚类质量依赖 LLM 的代码理解能力，对复杂 heuristic 可能不稳定
  • 评估实例规模较小（20-200），大规模实例的表现有待验证

与相关工作的对比

  • EoH/ReEvo/HSEvo: 单目标框架，仅优化解质量，无法平衡效率；MPaGE 双目标优化
  • MEoH: 同为多目标框架但用 AST 做多样性度量，无法区分语义等价的 heuristic；MPaGE 用 LLM 语义聚类替代
  • 传统 MOEA (NSGA-II/MOEA/D): 解质量更优但运行时间长 50-200×；MPaGE 在质量可比的前提下大幅加速
  • SEMO 原始框架: 随机采样邻域，MPaGE 用 LLM 指导选择和邻域探索，质量显著提升

启发与关联

  • LLM 作为"进化算子"的思路具有广泛应用前景，可推广到其他 NP-hard 问题的自动算法设计
  • PFG 网格划分 + 语义聚类的组合策略可用于任何需要平衡多目标且维持多样性的进化搜索场景
  • Feedback reflection 机制类似 self-play，利用 LLM 的推理能力引导搜索方向

评分

  • 新颖性: ⭐⭐⭐⭐⭐
  • 实验充分度: ⭐⭐⭐⭐
  • 写作质量: ⭐⭐⭐⭐
  • 价值: ⭐⭐⭐⭐

相关论文