Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows
本文提出了 SI-GP，一种求解器知情的遗传编程超启发式算法，该算法通过从高质量参考解中提取并选择特定实例的启发式特征，增强了针对带时间窗的随机团队定向问题（STOW）的可解释调度规则，从而在保持规则可读性和稳定性的同时，性能优于现有基准算法。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一支车队正与时间赛跑，前往访问一系列分散的地点，每个地点都提供不同的奖励。目标很简单：在时间耗尽之前收集尽可能多的价值。但现实世界并非电子表格。完成任何地点任务所需的时间具有不确定性；一阵突如其来的阵风可能会延迟无人机，或者汹涌的海浪可能会减慢船只的速度。此外，每个地点仅在特定的时间窗口内可用。如果车辆到达得太早，它必须等待；如果到达得太晚，机会将永远消失。这就是被称为“带时间窗的团队定向问题”（team orienteering problem with time windows）的一种复杂的物流挑战。在现实世界中，当消防员试图控制山火、溢油清理小组赶在油污触及海岸前进行拦截，或医疗团队必须在关键时间范围内探视患者时，这种场景便会发生。其难点在于，如何在不知道当前任务究竟会持续多久的情况下，立即做出下一步决策，且无法利用超级计算机每秒重新计算整个计划。
多年来，研究人员一直试图通过教计算机进化出简单的决策规则来解决这个问题。这些规则充当着交通控制器的角色，观察当前情况并立即决定下一个要访问的客户。目前最成功的方法被称为 NS-GP，它依赖于一组由十一个基本特征（例如客户距离多远或剩余时间多少）组成的固定集合来做出选择。虽然这种方法很有效，但它存在一个天花板。它使用一套有限的词汇来描述世界，就像试图仅用一百个单词来写一部小说一样。由巴西大学的 Augusto Mendonça 及其团队领导的这项新研究背后的研究人员提出了一个大胆的问题：如果计算机可以通过观察专家如何离线解决问题，从而学习到更丰富的词汇，结果会怎样？他们想看看是否可以从高质量的解决方案中提取隐藏的逻辑，并将这些洞察转化为可在实时环境中运行的简单、可读的规则。
该团队开发了一种名为 SI-GP 的新方法，即“求解器启发式遗传编程”（Solver-Informed Genetic Programming）。这一过程并非始于计算机的猜测，而是始于计算机的观察。首先，研究人员使用强大的高速求解器，在假设一切完美运行的前提下，为四十个不同的测试问题找到了最佳路径。然后，他们将这些完美的路径在模拟现实中随机延迟的世界里进行了重演。通过对比完美计划与实际发生的情况，团队识别出了完美计划执行了但标准规则却遗漏了的特定操作。例如，他们注意到最佳计划通常会向后看数步，以观察仍有哪些奖励是可触达的，或者会计算如果投入当前任务可能会损失未来机会的风险。
基于这些观察，研究人员构建了一个包含十八个决策特征的新库。其中十六个基于既有的调度概念，另外两个则是旨在权衡决策成本与潜在收益的新型组合。这个新词汇库让计算机拥有了更细致入微的方式来理解问题。然而，拥有更多选项并不自动意味着更好的结果；有时，过多的选择会让系统感到困惑。为了解决这个问题，团队使用了第二层智能来为每个特定问题选择最佳的特征子集。他们将选择过程视为一场锦标赛，进化出不同的特征组合并进行严格测试。这得益于一个基于图形处理器的定制引擎，它允许他们在过去测试一个组合所需的时间内，测试数千个组合。
结果令人瞩目。在四十个基准测试问题中，新方法从未表现得比旧标准差。在三十八个案例中，该系统进化的新规则超越了之前的最佳水平。平均而言，新规则在所有测试中将收集的总奖励提高了 1.0%，在仍有提升空间的题目中提高了 1.3%。在十个特定案例中，这种提升在统计学上是显著的，且足以被视为针对该特定场景的重大突破。或许最重要的一点是，新规则保持了简洁性和可读性。它们不是无人能懂的“黑箱”算法，而是人类可以阅读并验证的紧凑数学表达式。在许多情况下，新规则也更加稳定，即使在随机延迟变化时也能产生一致的结果，而旧规则有时会在好坏之间剧烈波动。
研究还揭示了改进发生的原因。新规则在基准系统难以访问所有可能客户的情况下表现尤为出色。在这些“非饱和”场景中，新词汇库使系统能够处理复杂的权衡，例如即便意味着跳过附近的低价值客户，也要去访问一个遥远的、高价值的客户。研究人员发现，新特征有助于系统实现搜索正则化，这意味着它不太容易陷入局部陷阱，而是更有可能找到稳健的前进路径。该方法通过学习高质量解决方案的结构而非单纯模仿来实现。它并非试图复制专家规划者的精确路线，而是学习了使那些路线成功的原则，并将其应用于新的不确定环境。
这项工作证明了弥合复杂离线优化与快速在线决策之间差距的可能性。通过利用高质量求解器的见解来构建更好的词汇，并为每个特定任务仔细选择合适的工具，研究人员创建了一个既强大又透明的系统。最终产品是一套可以直接嵌入车辆或无人机的决策规则，使其能够在微秒内做出智能选择，而无需连接中央计算机或运行复杂的模拟。这种方法为物流领域的人工智能指明了一条新路径：一条重视可解释性和适应性的路径，确保做出关键决策的机器能够被依赖它们的开发者所理解。研究人员已将其代码、数据以及发现的具体规则向公众开放，邀请他人在此基础上应对未来的挑战。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。