Self-Guiding Exploration for Combinatorial Problems

📄 arXiv: 2405.17950v1 📥 PDF

作者: Zangir Iklassov, Yali Du, Farkhad Akimov, Martin Takac

分类: cs.AI

发布日期: 2024-05-28

备注: 22 pages

💡 一句话要点

提出自引导探索(SGE)方法，利用LLM解决组合优化问题

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

关键词: 大型语言模型 组合优化问题 自引导探索 提示工程 推理任务

📋 核心要点

  1. 现有方法在利用LLM解决组合优化问题方面存在不足，缺乏有效的提示策略。
  2. 提出自引导探索(SGE)方法，通过自主生成、分解和细化思维轨迹来优化LLM的解题能力。
  3. 实验表明，SGE在组合优化问题上优于现有方法27.84%，并在其他推理任务上提升了2.46%的准确率。

📝 摘要（中文）

大型语言模型(LLM)在算术、常识和符号推理等领域的问题解决中发挥着关键作用。它们利用思维探索、分解和细化等提示技术来有效地解决复杂任务。然而，LLM在组合问题(CPs)中的应用仍未得到充分探索，而CPs因其NP难度以及在物流和资源管理中的关键作用而备受关注。为了填补这一空白，我们提出了一种新的提示策略：自引导探索(SGE)，旨在提高解决CPs的性能。SGE自主运行，为每个CP任务生成多个思维轨迹。然后，它将这些轨迹分解为可操作的子任务，依次执行它们，并细化结果以确保最佳结果。我们的研究首次将LLM应用于广泛的CPs，并证明SGE在CP优化性能方面优于现有的提示策略超过27.84%。此外，SGE在其他推理任务（算术、常识和符号推理）中实现了比现有最佳结果高2.46%的准确率。

🔬 方法详解

问题定义：论文旨在解决组合优化问题（CPs），这类问题因其NP难度而在物流和资源管理等领域具有重要意义。现有方法，特别是传统的LLM提示策略，在解决这类问题时效果不佳，无法充分利用LLM的推理能力。现有方法的痛点在于缺乏有效的探索和优化机制，难以在庞大的解空间中找到最优解或近似最优解。

核心思路：论文的核心思路是让LLM通过“自引导”的方式进行探索。具体来说，就是让LLM自主生成多个可能的解题思路（思维轨迹），然后将每个思路分解为一系列可执行的子任务，并逐步执行这些子任务。在执行过程中，LLM可以根据中间结果进行自我评估和调整，从而不断优化解题策略。这种“自引导”的探索方式能够更有效地利用LLM的推理能力，并在解空间中进行更全面的搜索。

技术框架：SGE的技术框架主要包含以下几个阶段：1) 轨迹生成：LLM根据问题描述生成多个不同的思维轨迹，每个轨迹代表一种可能的解题思路。2) 子任务分解：将每个思维轨迹分解为一系列可执行的子任务，例如，对于旅行商问题，子任务可以是“选择下一个要访问的城市”。3) 子任务执行：LLM依次执行每个子任务，并记录中间结果。4) 结果细化：根据中间结果和问题约束，对最终结果进行细化和优化，例如，通过局部搜索或遗传算法等方法。

关键创新：SGE最重要的技术创新点在于其“自引导”的探索机制。与传统的提示策略不同，SGE不需要人工设计复杂的提示语，而是让LLM自主生成和优化解题策略。这种方法能够更充分地利用LLM的推理能力，并在解空间中进行更有效的搜索。此外，SGE还通过子任务分解和结果细化等技术，进一步提高了LLM的解题效率和准确率。

关键设计：论文中没有详细描述关键的参数设置、损失函数或网络结构等技术细节。但是，可以推测，轨迹生成的数量、子任务分解的粒度、以及结果细化的方法等都可能对SGE的性能产生重要影响。未来的研究可以进一步探索这些参数的优化方法，以提高SGE的性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，SGE在组合优化问题上优于现有的提示策略超过27.84%。此外，SGE在算术、常识和符号推理等其他推理任务中也取得了显著的提升，实现了比现有最佳结果高2.46%的准确率。这些结果表明，SGE是一种有效的、通用的LLM提示策略，可以显著提高LLM在各种推理任务中的性能。

🎯 应用场景

该研究成果可广泛应用于物流、资源管理、调度优化等领域，例如车辆路径规划、任务调度、资源分配等。通过利用LLM的强大推理能力，可以更有效地解决这些领域的复杂组合优化问题，从而提高效率、降低成本。未来，该方法有望应用于更广泛的实际场景，并为相关领域带来显著的经济和社会效益。

📄 摘要（原文）

Large Language Models (LLMs) have become pivotal in addressing reasoning tasks across diverse domains, including arithmetic, commonsense, and symbolic reasoning. They utilize prompting techniques such as Exploration-of-Thought, Decomposition, and Refinement to effectively navigate and solve intricate tasks. Despite these advancements, the application of LLMs to Combinatorial Problems (CPs), known for their NP-hardness and critical roles in logistics and resource management remains underexplored. To address this gap, we introduce a novel prompting strategy: Self-Guiding Exploration (SGE), designed to enhance the performance of solving CPs. SGE operates autonomously, generating multiple thought trajectories for each CP task. It then breaks these trajectories down into actionable subtasks, executes them sequentially, and refines the results to ensure optimal outcomes. We present our research as the first to apply LLMs to a broad range of CPs and demonstrate that SGE outperforms existing prompting strategies by over 27.84% in CP optimization performance. Additionally, SGE achieves a 2.46% higher accuracy over the best existing results in other reasoning tasks (arithmetic, commonsense, and symbolic).