基于大语言模型的组合优化

摘要：组合优化（Combinatorial Optimization, CO）对于提高工程应用的效率和性能至关重要。随着问题规模的增大和依赖关系的复杂化，找到最优解变得极具挑战性。在处理现实世界的工程问题时，基于纯数学推理的算法存在局限性，无法捕捉到优化所需的上下文细微差别。本研究探索了大型语言模型（Large Language Models, LLMs）在解决工程组合优化问题中的潜力，利用其推理能力和上下文知识。我们提出了一种基于LLM的新框架，该框架结合了网络拓扑和领域知识，以优化设计结构矩阵（Design Structure Matrix, DSM）的排序——这是一个常见的组合优化问题。我们在多个DSM案例上的实验表明，所提出的方法比基准方法具有更快的收敛速度和更高的解质量。此外，结果表明，尽管LLM的选择不同，融入上下文领域知识显著提高了性能。这些发现凸显了LLMs通过结合语义和数学推理来解决复杂现实世界组合优化问题的潜力。这一方法为现实世界中的组合优化开辟了新的范式。

组合优化现行解决方案

传统上，工程中的组合优化问题通常通过以下过程来解决：首先将问题建模为数学模型，然后使用特定的算法或启发式方法进行求解，最后在实际工程背景下进行解释[4]。这种问题求解和解释阶段的分离存在局限性，无法捕捉到现实世界问题优化所需的上下文细微差别。

LLM决策理论支持

1、近年来，大型语言模型（Large Language Models, LLMs）在自然语言生成、语义理解、指令跟随（instruction following）和复杂推理方面展示了强大的能力
2、研究表明，LLMs可以用于连续和具体的优化问题[7, 8, 9]。例如，DeepMind的研究人员利用LLMs作为优化器，并在经典的组合优化问题（如旅行商问题，TSP）上评估了其有效性
3、融入上下文领域知识可以通过语义洞察支持数学推理，从而提升LLMs的性能。先前的研究还强调，LLMs通过预训练获得了广泛的工程相关领域的知识，这增强了它们在工程领域的适用性。

创新点

在此基础上，我们提出了一种基于LLM的新框架，将网络拓扑和领域上下文整合到优化过程中。该框架首先从整个解空间中随机采样一个初始解。每个解都会根据预定义的标准由评估器进行评估，评估器量化了解的质量。基于这一评估，框架通过少样本学习（few-shot learning）和生成新的候选解来迭代更新解库，整个过程由精心设计的提示（prompts）引导，这些提示包括数学形式的网络信息和自然语言描述的领域知识。新生成的解及其评估结果会被添加到解库中。当达到迭代次数时，解库会返回最佳解作为最终输出。接下来，我们以DSM排序这一常见的组合优化问题为例，说明该框架的工作流程。框架的示意图如图2所示。

1、Initialization and solution sampling。初始化过程涉及从整个解空间中随机采样生成一个初始解。在DSM排序任务中，一个解表示一个完整且不重复的节点序列（见图2）。这个初始解随后会被评估并添加到解库中以供后续使用。在后续的迭代中，我们设计了一个采样规则，该规则从解库中选择 Kp 个表现最优的解，并从剩余的 Kn - Kp 个解中随机采样 Kq 个解，形成一个解集，其中 Kn 是解库中解的总数。Kp 和 Kq 是可调整的参数。获得的解集会被进一步优化并转化为提示（prompts）。

解库（Solution Base） 是一个核心模块，其功能包括：
(1) 存储已探索的解及其评估结果，
(2) 为后端LLM提供历史解以进行少样本学习（few-shot learning），
(3) 在迭代结束时返回表现最优的解。

2、LLM-driven optimization using network information and domain knowledge。在优化过程的每次迭代中，我们向后端LLM提供以下信息：

• (i) 拓扑信息：这两个元素完成了DSM的数学描述。值得注意的是，描述网络的数学表示有多种等价形式，例如边列表（edge list）、根据节点序列的依赖关系列表或邻接矩阵。在本研究中，我们选择边列表作为网络拓扑的表示形式，并对所有边进行随机打乱以避免可能的偏差。
• (ii) 上下文领域知识：这包括每个节点的名称和网络的整体描述，这些信息将DSM数学结构背后的领域知识传递给LLM。例如，在活动DSM中，每个节点代表整个设计过程中的一个活动名称。
• (iii) 元指令：我们采用了一些常用的提示工程策略[20]，包括角色扮演、任务规范和输出格式规范。这些策略使LLM能够根据指导进行推理，并以特定格式生成解。
• (iv) 选定的历史解：如上一节所述，我们通过从解库中采样获得最多 Kp + Kq 个解，供LLM在少样本学习中使用。

一旦接收到上述输入，后端LLM会结合网络拓扑信息和领域知识进行推理，并提出新的解。生成的解必须通过检查器（checker）的验证，检查器会确保序列中的所有节点都恰好出现一次。一旦验证通过，该解会被评估并添加到解库中。详细的输入提示（prompts）见附录1。

3、Evaluation of DSM sequencing solutions。评估器（evaluator）用于量化每个新生成的解。对于DSM排序任务，目标是通过重新排列DSM的行和列来最小化反馈循环。为了实现这一目标，评估器会计算对应序列中的反向依赖数量。

数值试验

以设计结构矩阵（Design Structure Matrix, DSM）排序任务为例，作为组合优化问题的一个实例。DSM是工程设计中的一种建模工具，用于表示系统中任务或组件之间的依赖关系[14]。重新排序DSM的节点序列可以显著减少反馈循环并提高模块化[15, 16]。DSM排序问题也是一个NP难问题，传统方法通常使用基于启发式的算法来解决[17, 18]。图1展示了一个设计活动DSM在排序前和排序后的对比[19]。在本文中，我们在多个DSM案例上进行了广泛的实验，以证明我们基于LLM的方法在收敛速度和解质量上优于基准方法。