发布日期：2025-12-13 19:12点击次数：192
（来源：运筹OR帷幄）
↑↑↑↑↑点击上方蓝色字关注我们！
]article_adlist-->
作者信息：张舒政，东北大学管理科学与工程系在读博士生，研究方向: 数据驱动优化、鲁棒优化
编者按
多目标组合优化问题在医疗调度等领域至关重要，传统启发式算法如NSGA-II往往依赖专家知识设计精细算子。本研究提出了一种创新方法LLM-NSGA，直接利用大语言模型（LLM）作为进化优化器，自动完成选择、交叉和变异操作。实验表明，LLM-NSGA在手术调度案例中能独立生成高质量解，且随问题规模增大，性能显著超越NSGA-II和MOEA/D，目标提升最高达80%。此外，LLM在超参数优化中也表现出色，相比贝叶斯优化和蚁群算法，运行时间平均降低23.68%。这一研究不仅表明了LLM在复杂优化任务中的潜力，也为传统算法的高效调参提供了新思路。
引言：当LLM遇见多目标组合优化
手术调度是一项典型的多目标组合优化问题。手术安排需在多约束环境中优化多个目标，例如降低医院费用、减少患者等待时间以及最大限度地提高床位利用率，且手术调度中包含大量的0-1决策变量。非支配排序遗传算法II（NSGA-II） 等进化算法可以有效解决复杂的多目标问题，但其性能在很大程度上取决于超参数设定，例如种群大小、迭代次数、交叉率和突变率。次优超参数设置可能会导致效率低下，例如计算时间增加或无法识别高质量的解。
近年来，大语言模型（LLM）展现出强大的复杂规划与推理能力，为高质高效求解优化问题提供了新思路。本研究聚焦一个核心问题：能否将LLM转化为一种进化优化器，自动、高效地处理手术调度这类复杂组合优化问题，从而降低人为设计算子的依赖？本文比较了三种方法：LLM直接生成解，NSGA-II以及将LLM与NSGA-II相结合的混合方法，以得出有效的调度解决方案。
问题介绍：符号及模型
本研究聚焦于择期手术的调度优化问题，暂未考虑不确定性因素，但仍致力于实现多目标优化。我们的模型核心在于为择期手术患者分配合适的手术室资源，其中部分患者术后需进入重症监护病房（ICU）进行康复。优化目标主要包括：减少手术室加班时间、满足患者期望的手术时间窗要求，以及最小化ICU床位需求峰值。该方法有助于合理错开患者手术日程，提升床位资源利用效率。
参数
辅助变量
决策变量
数学模型
公式（1）至（4）为四个目标函数：f1旨在最小化总成本，包括手术室的固定启用成本与加班成本；f2 和 f3分别最小化未在调度周期内接受手术的被拒绝择期患者数量及未手术患者数量；f4 则用于最小化整个规划期内所需的ICU床位峰值数量。
约束条件（5）规定了手术室的开放时长；约束（6）用于计算所有择期患者的ICU床位总需求；约束（7）确保每位择期患者在计划期内至多被安排一次手术；约束（8）描述了决策变量之间的关系；约束（9）定义了决策变量的取值范围。
方法创新：LLM-NSGA框架解析
数据示例及参数设置
本文以法国里昂一家医院的真实数据为基础，对5间手术室和200名择期患者的手术调度问题进行建模。患者详细信息见表2，包含以下5列：“No.”为患者编号；“Exe.”为患者的预计手术日期；“Sur.”为手术持续时间（单位：分钟）；“LOS”为术后住院天数；“Stay”标识术后是否需要ICU床位（1表示需要，0表示不需要）。
问题参数设置如下：调度周期为7天，每间手术室每日固定开放时长为8小时，最大可延长至10小时。每间手术室每加班1小时的费用为200，每启用一间手术室的固定费用为1000。
LLM-NSGA核心思想
本研究采用了一种混合方法（LLM-NSGA），有效结合了大型语言模型（LLM）与NSGA-II算法的优势。以下算法展示了使用LLM-NSGA进行手术调度的整体框架。该框架将LLM作为零样本学习环境中的进化算子，无需任何任务特定的额外训练即可直接调用。通过精心设计的提示词引导，LLM能够基于上下文学习执行关键遗传操作，包括父代选择、交叉和变异。与此同时，NSGA-II继续发挥其多目标优化优势，有效协调诸如降低成本、减少患者延误或拒绝、管理ICU床位使用等冲突目标，从而获得均衡且高质量的调度方案。
算法 ：用于手术调度的 LLM-NSGA
输入：种群大小 P，迭代次数 Iter，交叉率 Cr，变异率 Mr 输出：最优手术分配方案 1: 随机生成 P 个初始手术分配方案 2: For i = 1 to Iter do 3: 构造提示词：执行交叉与变异操作 4: 获得子代种群 P′ 5: 构造提示词：从合并种群 P + P′ 中选择前 P 个个体 6: End For 7: 返回帕累托前沿最优解集
下图展示了LLM-NSGA中用于手术调度问题的提示词设计结构。该方法摒弃了传统进化算法中逐步编写遗传操作的方式，转而通过自然语言提供高级指令，降低了对复杂领域专业知识的需求。
以表2中前10名择期患者为例，在随机生成的初始分配中，择期患者1未分配手术，患者2和6未在其预期日期进行手术。LLM-NSGA通过对初始方案执行交叉和变异操作，生成最终分配方案。下表详细展示了从初始到最终方案中手术分配及目标函数值的变化过程。结果表明，在恰当的提示词引导下，LLM能够有效改进解决方案，逐步逼近预期优化目标。
对比方法：LLM直接求解以及NSGA-II
LLM直接求解
该方法利用大型语言模型（LLM）的自然语言处理能力来理解并解决手术调度问题。以下概述了基于LLM的求解框架
算法 1：LLM 的手术安排方法 1：构建提示：为择期患者制定 7 天的手术计划 2：构建提示：解释约束和目标函数 3：输入：择期患者的信息表 4：LLM：分析问题和数据 5：输出：LLM 提供详细的解决方案 步骤 6：返回最佳手术分配计划
图1则展示了为此专门设计的提示词结构。该框架使模型能够充分考虑手术调度中复杂的相互依赖关系，如手术时长、患者需求与资源可用性等。通过理解这些复杂因素，LLM能够根据所提供的提示生成一系列步骤，逐步推导出解决方案。LLM处理与解析大规模数据的能力，保障了整个调度过程的全面性与优化性，从而最终实现更合理的资源分配和患者诊疗结果。
NSGA-II
NSGA-II 算法具有若著优势。它能够有效维持种群的多样性，避免过早收敛至单一解，从而确保对解空间的广泛探索。此外，NSGA-II 擅长处理多目标优化问题，可在单次运行中提供一组帕累托最优解，特别适用于目标之间存在冲突的场景，例如在最大化手术安排数量与资源利用率的同时，尽量减少患者等待时间 。该方法适用于结构化问题的求解，并能够根据约束条件的复杂程度提供精确或近似的最优解。本研究采用经典多目标优化算法 NSGA-II，以解决择期手术的手术室分配问题，其算法框架如下所示。
输入：种群大小 P，迭代次数 Iter，交叉率 Cr，变异率 Mr 输出：最优手术分配方案 随机生成 P 个初始手术分配方案； For i = 1 to Iter do For 每个个体 p = 1 to P do // r1, r2 为随机数 If r1 < Cr then // 交叉操作 交换两名患者的入院日期和/或手术室； 更新每日ICU床位安排； End If If r2 < Mr then // 变异操作 调整患者的入院日期和/或手术室； 更新每日ICU床位安排； End If End For 获得子代种群； 对合并种群（父代与子代）进行帕累托排序； 选择前 P 个个体进入下一代； End For 返回帕累托前沿最优解集；
NSGA-II 的编码方式如下图所示，患者根据手术时长随机分配至手术室。若总手术时间超过8小时，则启用新手术室。重复该过程直至所有患者或手术室均已分配完毕，旨在避免手术室加班，并最大限度减少患者手术延迟或无法安排的情况。
交叉与变异操作是优化手术室资源分配所采用的遗传算法机制，旨在确保满足择期患者时间窗约束，并提升手术室利用效率。本文中的交叉操作包括：交换同一天两名患者的手术室分配，或调整不同日期患者的入院时间及手术室。交叉操作后，因患者日程重新安排可能出现空闲手术室，为后续纳入未安排患者提供可能，从而有助于提高患者接收率和手术室整体利用率。下图展示了交叉操作过程，演示了同一天内两名患者的手术室互换。
变异操作则侧重于患者的时间窗约束，针对未在预期日期安排手术或未分配手术室的患者，在其期望日期范围内搜索可用手术室以插入该患者，具体操作如下图所示。
NSGA-II 算法中的参数已根据实验测试进行充分校准，具体设置为种群大小P=100，迭代次数Iter=200，交叉率Mr=0.1，变异率Cr=0.7。
实验结果：性能大幅超越启发式方法
主要发现1（解决方案生成）：
LLM-NSGA在解决大规模手术调度问题时展现出显著优势。当病例数超过40例后，其性能全面超越传统算法NSGA-II和MOEA/D(Evolutionary Algorithm based on Decomposition)。如下表所示，LLM-NSGA与另一LLM方法EoH(Evolution of Heuristics)的整体效果相当，但在关键目标上表现更优：相较于NSGA-II和EoH，LLM-NSGA在总成本（f1）、被拒绝患者数（f2）和最大ICU床位占用数（f4）上分别实现了平均5.39%、80%和0.42%的提升。两种对比算法原文可见文末引文。
主要发现2（超参数优化）：
为提升NSGA-II算法的性能，本研究利用大型语言模型（LLM）的自学习能力进行超参数优化，并将其结果与贝叶斯优化及进化算法等常用方法进行对比。该比较旨在验证LLM驱动的超参数优化方法在提升NSGA-II效率与效果方面的有效性，并突显其相对于传统优化技术的优势。所优化的四个关键参数包括：种群大小（P）、迭代次数（Iter）、交叉率（Cr）和变异率（Mr）。
参数“P”和“Iter”的取值范围设定为[50, 100, 150, …, 500]，“Cr”和“Mr”的取值范围为[0.1, 0.2, …, 1.0]。若采用网格搜索进行超参数优化，需评估至少10,000组参数组合，计算成本较高。因此，本研究将LLM与随机搜索相结合，以充分利用LLM的计算与模式识别能力，同时借助随机搜索的随机探索特性。首先，随机选取100组参数组合运行NSGA-II，得到“参数-目标-运行时间”解集，如下表所示。其中第2–5列为超参数取值，第6–9列为手术调度问题的四个优化目标，第10列为运行时间。随后对这四个目标及运行时间进行帕累托排序，第11–12列分别列出其前沿等级和拥挤距离。
将上述参数组合及其对应的帕累托前沿等级与拥挤距离输入LLM，利用其深度学习与自然语言处理能力，识别不同参数组合间的关联与相互作用。如下图所示，通过设计详细的指令引导LLM分析输入数据，并基于指定的优化目标与约束条件推荐最佳参数组合。
实验表明，LLM仅需分析100组初始数据，并在6秒内完成参数推荐，最终使NSGA-II的总运行时间平均缩短23.68%。采用LLM所推荐的参数组合（P=500, Iter=300, Cr=0.9, Mr=0.6）运行NSGA-II，所得解的质量优于贝叶斯优化和蚁群优化（ACO）所得结果，且总耗时（6255.23秒）显著低于贝叶斯优化（7186.20秒）和ACO（9533.61秒）。
讨论与启示：为什么LLM能做好优化？
LLM的成功可能源于其从海量文本中习得的隐含领域知识和复杂模式推理能力，使其能做出比随机算子更智能的进化决策。该方法的两大实用价值：
降低门槛：减少对特定领域专家知识设计算子的依赖。
提升效率：既可独立作为优化器，也可作为传统算法的“加速器”和“调参器”。
本研究证实了LLM在解决复杂ORMS问题上的巨大潜力，为进化计算和组合优化提供了新范式。当前研究主要针对中小规模问题，LLM的上下文窗口限制是处理更大规模问题的挑战。展望未来，如何将LLM逐步引导以解决更大规模问题？能否将其应用于其他复杂的资源调度场景？
参考文献
本文内容：Wan, F., Wang, T., Wang, K., Si, Y., Fondrevelle, J., Du, S., & Duclos, A. (2025). Surgery scheduling based on large language models. Artificial Intelligence in Medicine, 166, 103151. https://doi.org/10.1016/j.artmed.2025.103151
EOH算法：Liu F, Xialiang T, Yuan M, Lin X, Luo F, Wang Z, et al. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. 2024 [In Forty-first International Conference on Machine Learning].
MoEA/D算法：Cai X, Hu M, Gong D, Guo YN, Zhang Y, Fan Z, et al. A decomposition-based coevolutionary multiobjective local search for combinatorial multiobjective optimization. Swarm Evol Comput 2019;49:178–93.
微信公众号后台回复加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
]article_adlist-->文章须知
论文解读者：张舒政
责任编辑：蔡君洋
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
FOLLOW US
]article_adlist-->
海量资讯、精准解读，尽在新浪财经APP