Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbo

📄 arXiv: 2405.01997v1 📥 PDF

作者: Mahmoud Masoud, Ahmed Abdelhay, Mohammed Elhenawy

分类: cs.CL, cs.AI

发布日期: 2024-05-03

💡 一句话要点

探索大型语言模型在组合优化问题中的应用：以GPT-3.5 Turbo求解旅行商问题为例

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

关键词: 大型语言模型 旅行商问题 组合优化 GPT-3.5 Turbo 上下文学习

📋 核心要点

  1. 现有方法在组合优化问题上存在局限性，缺乏对大型语言模型潜力的充分挖掘。
  2. 本文探索利用GPT-3.5 Turbo解决旅行商问题，通过上下文学习和微调等策略提升性能。
  3. 实验表明，微调后的模型在特定规模问题上表现出色，并能泛化到更大规模问题。

📝 摘要（中文）

本文研究了大型语言模型（LLMs）在解决组合优化问题中的潜力，以旅行商问题（TSP）为例。利用GPT-3.5 Turbo，我们进行了包括零样本上下文学习、少样本上下文学习和思维链（CoT）等多种方法的实验。此外，我们还对GPT-3.5 Turbo进行了微调，使其能够解决特定规模的问题，并使用不同规模的实例对其进行了测试。微调后的模型在与训练实例大小相同的问题上表现出良好的性能，并且能够很好地泛化到更大的问题。为了在不增加额外训练成本的情况下提高微调模型的性能，我们采用了一种自集成方法来提高解决方案的质量。

🔬 方法详解

问题定义：论文旨在探索大型语言模型（LLMs）解决组合优化问题的能力，具体选择旅行商问题（TSP）作为案例。现有方法在解决TSP问题时，通常依赖于专门设计的算法，缺乏通用性和灵活性，并且难以利用LLMs强大的语言理解和生成能力。

核心思路：论文的核心思路是利用LLMs的上下文学习能力和微调能力，使其能够理解和解决TSP问题。通过上下文学习，LLM可以从少量示例中学习TSP问题的求解方法；通过微调，LLM可以针对特定规模的TSP问题进行优化，提高求解效率和准确性。

技术框架：论文的技术框架主要包括以下几个阶段：1) 使用GPT-3.5 Turbo进行零样本上下文学习、少样本上下文学习和思维链（CoT）实验，探索LLM解决TSP问题的初步能力；2) 针对特定规模的TSP问题，对GPT-3.5 Turbo进行微调，提高模型在该规模问题上的求解性能；3) 使用不同规模的TSP实例对微调后的模型进行测试，评估模型的泛化能力；4) 采用自集成方法，通过组合多个模型的预测结果，进一步提高解决方案的质量。

关键创新：论文的关键创新在于探索了LLMs在组合优化问题中的应用潜力，并提出了一种基于上下文学习和微调的解决方案。与传统方法相比，该方法具有更强的通用性和灵活性，并且能够利用LLMs强大的语言理解和生成能力。此外，论文还提出了一种自集成方法，可以在不增加额外训练成本的情况下提高解决方案的质量。

关键设计：论文中，微调过程的关键设计包括：选择合适的训练数据集（特定规模的TSP实例），设计合适的损失函数（例如，最小化路径长度），以及调整模型的超参数（例如，学习率、batch size）。自集成方法中，关键设计在于如何选择合适的集成策略（例如，多数投票、加权平均），以及如何评估不同模型的预测结果的可靠性。

📊 实验亮点

实验结果表明，微调后的GPT-3.5 Turbo在与训练实例大小相同的问题上表现出良好的性能，并且能够很好地泛化到更大的问题。此外，自集成方法能够进一步提高解决方案的质量，在不增加额外训练成本的情况下，提升模型性能。具体性能数据未知，但论文强调了微调和自集成策略的有效性。

🎯 应用场景

该研究成果可应用于物流优化、路线规划、资源调度等领域。通过利用大型语言模型解决组合优化问题，可以提高效率、降低成本，并为实际应用提供更灵活的解决方案。未来，该方法有望扩展到其他组合优化问题，例如车辆路径问题、调度问题等，具有广阔的应用前景。

📄 摘要（原文）

Large Language Models (LLMs) are deep learning models designed to generate text based on textual input. Although researchers have been developing these models for more complex tasks such as code generation and general reasoning, few efforts have explored how LLMs can be applied to combinatorial problems. In this research, we investigate the potential of LLMs to solve the Travelling Salesman Problem (TSP). Utilizing GPT-3.5 Turbo, we conducted experiments employing various approaches, including zero-shot in-context learning, few-shot in-context learning, and chain-of-thoughts (CoT). Consequently, we fine-tuned GPT-3.5 Turbo to solve a specific problem size and tested it using a set of various instance sizes. The fine-tuned models demonstrated promising performance on problems identical in size to the training instances and generalized well to larger problems. Furthermore, to improve the performance of the fine-tuned model without incurring additional training costs, we adopted a self-ensemble approach to improve the quality of the solutions.