盖世汽车讯 从包裹递送路线、工厂生产计划到医院值班表，许多现实世界的规划任务都需要满足众多运营约束的解决方案。据外媒报道，由韩国科学技术院（KAIST）计算机学院Min-Soo Kim教授领导的研究团队开发了一种名为RL-SPH（基于强化学习的起始原始启发式算法）的强化学习技术，该技术训练人工智能独立生成可行的方案，而无需依赖外部求解器。该研究成果已发表在arXiv预印本服务器上。

图片来源：KAIST

这项技术的关键特性在于它能够学习如何生成满足优化问题中多个约束条件的解决方案。研究团队期望该方法能够为物流、制造、半导体生产和劳动力管理等领域的AI决策奠定重要基础。

包裹递送路线规划、车辆路线规划、工厂生产调度和医院员工排班都是典型的规划问题，都可以使用整数线性规划（ILP）进行建模。ILP是一种数学优化技术，用于在满足一组线性约束条件且部分或全部决策变量取整数值的前提下，寻找最优解。

当快速答案无法使用时

例如，包裹递送计划不仅要尽可能缩短递送时间，还必须满足车辆容量限制和司机工作时间要求，同时确保每个目的地都能被访问。即使路线看起来多么短或便宜，只要违反了其中任何一项条件，在实践中都无法使用。

现有的基于学习的方法可以快速生成近似解或部分解，但这些预测结果经常违反约束条件。因此，许多方法会将输出传递给专门的整数线性规划（ILP）求解器，例如Gurobi或SCIP，由这些求解器负责获得可行解。该轮文指出，现有的端到端基于学习的原始启发式算法通常难以独立生成可行解。

优化前的可行性分析

RL-SPH通过迭代修正候选解而非试图一步预测最终答案来解决这一局限性。在每个阶段，它都会选择多个可能提高可行性的决策变量，并确定它们的值应该增加、减少还是保持不变。然后，模型会从约束违反情况和解质量的变化中学习。

值得注意的是，该团队设计的AI首先会找到一个实际可用的方案，而不是单一的最佳方案。整个过程分为两个阶段。在第一阶段，AI优先寻找满足所有约束的初始可行解。在第二阶段，它会在保持可行性的前提下，通过降低目标值（例如成本或处理时间）来寻求更高质量的解。

例如，在工厂生产计划问题中，该方法首先会确定一个满足交货期限、设备产能和可用劳动力等要求的生产计划。然后，它会在不违反这些条件的前提下，尝试降低生产成本和缩短生产时间。因此，该研究优先考虑找到一个切实可行的计划，然后再进行进一步的优化。

该团队还引入了ILP-GT，这是一种新的AI模型，能够学习变量和约束之间的关系，并采用了一种可行性感知搜索策略，优先修改对解决问题最有效的变量，从而显著提高计算效率。

基准测试结果有利于找到可用的方案

在五个具有代表性的基准测试中，RL-SPH的可行性率达到了100%，成功为每个问题找到了一个可用的方案。即使在涉及一般（非二进制）整数变量的更复杂问题上，它也能保持相同的性能。

与现有技术相比，RL-SPH将原始差距（方法解与已知最优解之间的差距）缩小了28.6倍，并将原始积分（衡量搜索过程速度和质量的指标）提高了2.6倍。此外，找到第一个可行方案所需的时间平均也提高了2.5倍。

图片来源：KAIST

在近期涌现的人工智能技术中，例如PAS、DDIM和DiffILO，RL-SPH是唯一在所比较的三个基准测试（SC、CA 和 IS）中均达到100%可行性率的方法。其训练平均耗时仅为30分钟，比现有技术快14.7倍，比最新的基于无监督学习的技术快约34倍。无监督学习是一种人工智能训练方法，它无需预先提供正确答案即可在数据中发现模式。

该技术在MIPLIB上进一步展现了其泛化能力。MIPLIB是一个国际混合整数规划基准测试库，广泛应用于学术界和工业界。它不仅能够可靠地找到比训练集规模大67倍的问题的可行方案，还能找到训练过程中从未遇到过的全新问题类型的可行方案。

Kim表示：“在实际应用中，一个真正可执行的方案往往比一个理论上最优但违反实际约束的方案更为重要。这项研究表明，人工智能无需依赖专门的优化求解器来强制执行可行性，就能学习生成可行的解决方案。我们期望这项技术能够为物流、制造、半导体生产、劳动力管理和其他工业领域的人工智能决策提供重要的基础。”