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

📄 arXiv: 2507.20923v3 📥 PDF

作者: Minh Hieu Ha, Hung Phan, Tung Duy Doan, Tung Dao, Dao Tran, Huynh Thi Thanh Binh

分类: cs.NE, cs.AI

发布日期: 2025-07-28 (更新: 2026-01-15)

备注: Accepted at AAAI-26

🔗 代码/项目: GITHUB

💡 一句话要点

提出基于Pareto网格引导的大语言模型进化算法，用于快速高质量的多目标组合优化启发式设计。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 多目标优化 组合优化 大语言模型 启发式搜索 进化算法

📋 核心要点

  1. 现有基于LLM的启发式搜索方法主要集中于单目标优化，忽略了多目标优化中运行时效率和启发式多样性的关键问题。
  2. 论文提出MPaGE框架，利用Pareto前沿网格(PFG)引导LLM进化，优先生成语义不同的启发式，从而提升多样性并减少冗余。
  3. 实验结果表明，MPaGE在多目标组合优化问题上优于现有LLM方法，并以更快的速度达到与传统MOEA相当的性能。

📝 摘要（中文）

多目标组合优化问题(MOCOP)在实际应用中频繁出现，需要同时优化多个冲突的目标。传统的进化算法虽然有效，但通常依赖领域知识和重复的参数调整，限制了其在未见过的MOCOP实例中的灵活性。最近，将大型语言模型(LLM)集成到进化计算中，利用其先进的语言理解和代码合成能力，为自动启发式生成开辟了新途径。然而，大多数现有方法主要关注单目标任务，常常忽略了多目标设置中的运行时效率和启发式多样性等关键考虑因素。为了弥合这一差距，我们引入了Multi-heuristics for MOCOP via Pareto-Grid-guided Evolution of LLMs (MPaGE)，这是一种对简单进化多目标优化(SEMO)框架的新颖增强，它利用LLM和Pareto Front Grid (PFG)技术。通过将目标空间划分为网格并保留表现最佳的候选者来指导启发式生成，MPaGE利用LLM在变异期间优先考虑具有语义上不同逻辑结构的启发式，从而促进种群内的多样性并减少冗余。通过广泛的评估，MPaGE证明了其优于现有的基于LLM的框架，并实现了与传统多目标进化算法(MOEA)相比具有竞争力的结果，且运行时明显更快。我们的代码可在https://github.com/langkhachhoha/MPaGE 获得。

🔬 方法详解

问题定义：论文旨在解决多目标组合优化问题（MOCOP）中，利用大语言模型（LLM）自动生成高效且多样化的启发式算法的问题。现有基于LLM的方法主要集中于单目标优化，忽略了多目标优化中运行时效率和启发式多样性的关键问题，并且生成的启发式可能存在冗余。

核心思路：论文的核心思路是利用Pareto前沿网格（PFG）引导LLM的进化过程。通过将目标空间划分为网格，并保留每个网格中表现最佳的候选解，从而引导LLM生成具有不同语义结构的启发式算法。这种方法旨在提高种群的多样性，并减少冗余的启发式。

技术框架：MPaGE框架基于简单进化多目标优化（SEMO）算法。其主要流程包括：1）初始化种群，种群中的每个个体代表一个启发式算法；2）使用LLM对种群进行变异操作，生成新的启发式算法；3）使用PFG评估每个启发式算法的性能，并更新Pareto前沿；4）根据PFG选择优秀的个体，用于指导下一代LLM的变异过程。重复步骤2-4，直到满足停止条件。

关键创新：论文的关键创新在于使用Pareto前沿网格（PFG）来引导LLM的进化过程。与传统的MOEA相比，MPaGE能够利用LLM的语义理解和代码生成能力，自动生成启发式算法，无需人工设计。与现有的基于LLM的方法相比，MPaGE能够更好地平衡运行时效率和启发式多样性，并减少冗余。

关键设计：论文的关键设计包括：1）PFG的网格划分策略，需要平衡网格的数量和每个网格中的个体数量；2）LLM的prompt设计，需要引导LLM生成具有不同语义结构的启发式算法；3）变异操作的设计，需要保证生成的新启发式算法具有一定的探索性和利用性；4）选择策略的设计，需要选择具有代表性的个体，用于指导下一代LLM的变异过程。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，MPaGE在多个多目标组合优化问题上优于现有的基于LLM的框架。例如，在旅行商问题（TSP）上，MPaGE能够以更快的速度达到与传统MOEA相当的性能。此外，MPaGE还能够生成具有不同语义结构的启发式算法，从而提高种群的多样性。

🎯 应用场景

该研究成果可应用于各种需要同时优化多个冲突目标的组合优化问题，例如：车辆路径规划、资源调度、生产计划等。通过自动生成高效且多样化的启发式算法，可以显著提高问题求解的效率和质量，降低人工干预的成本，并为实际应用带来更大的灵活性。

📄 摘要（原文）

Multi-objective combinatorial optimization problems (MOCOP) frequently arise in practical applications that require the simultaneous optimization of conflicting objectives. Although traditional evolutionary algorithms can be effective, they typically depend on domain knowledge and repeated parameter tuning, limiting flexibility when applied to unseen MOCOP instances. Recently, integration of Large Language Models (LLMs) into evolutionary computation has opened new avenues for automatic heuristic generation, using their advanced language understanding and code synthesis capabilities. Nevertheless, most existing approaches predominantly focus on single-objective tasks, often neglecting key considerations such as runtime efficiency and heuristic diversity in multi-objective settings. To bridge this gap, we introduce Multi-heuristics for MOCOP via Pareto-Grid-guided Evolution of LLMs (MPaGE), a novel enhancement of the Simple Evolutionary Multiobjective Optimization (SEMO) framework that leverages LLMs and Pareto Front Grid (PFG) technique. By partitioning the objective space into grids and retaining top-performing candidates to guide heuristic generation, MPaGE utilizes LLMs to prioritize heuristics with semantically distinct logical structures during variation, thus promoting diversity and mitigating redundancy within the population. Through extensive evaluations, MPaGE demonstrates superior performance over existing LLM-based frameworks, and achieves competitive results to traditional Multi-objective evolutionary algorithms (MOEAs), with significantly faster runtime. Our code is available at: https://github.com/langkhachhoha/MPaGE.