Simulation-guided Beam Search for Neural Combinatorial Optimization 2023-05-04 组合优化 暂无评论 75 次阅读 >Choo J, Kwon Y D, Kim J, et al. Simulation-guided Beam Search for Neural Combinatorial Optimization[C]//Advances in Neural Information Processing Systems.  --- ## 摘要 + ==提出了新的波束搜索方法 SGBS，将 MCTS 与波束搜索相结合== + ==提供了一种使用 SGBS 和 EAS 的混合方案== ## 1. Introduction + RL应用于CO问题 + 常见的搜索策略beam search盲目跟随神经网络的预测，无论好坏。MCTS时间长。 + 提出了模拟引导波束搜索 (SGBS)，它将 MCTS 与波束搜索相结合，专门用于解决 CO 问题。 + SGBS 可以进一步与高效主动搜索 (EAS) [1] 合作，以在更长的时间跨度内实现更好的性能。 + 在旅行销售员问题 (TSP)、有能力的车辆路径问题 (CVRP) 和灵活的流水车间问题 (FFSP)表现好。 ## 2. Related work + 神经网络求解组合优化问题 + 神经 CO 方法使用的事后树搜索 + 其它与本文相似的工作 ## 3. SGBS算法 ### 3.1 预设 定义了一下，强化学习解决CO问题的状态、动作、奖励等。 ### 3.2 算法及其三个阶段 + 扩张 Expansion (pre-pruning) + beam width (β)、expansion factor (γ) + 对于 beam 中包含的每个节点 sd，选择其子节点中具有最大 πθ(·|sd) 的top γ 个 + 模拟 Simulation + 每个扩展的子节点的潜力是通过 rollout 来衡量的(类似MCTS的simulation阶段) + 使用 greedy rollouts 创建 β × γ 不同的 CO 解决方案，并将奖励标记到相应的子节点。 + 剪枝 Pruning + 选择具有最高simulation score的 β 节点并将它们注册为新的波束前沿。   ### 3.3 优势 这里作者讨论了在三种不同的假设环境下，SGBS的优势，附带相应实验说明。 + 默认设置（预训练到目标分布） + 即使我们假设方程式中规定的完美训练，目标分布 P 和单个问题实例 R 之间的差距会导致神经网络不时建议错误的决策。当部分解决方案 sd 的子节点被策略网络赋予相对较低的分数 πθ(ad|sd) 但实际上是一个理想的选择时，SGBS 的模拟步骤可以防止该子节点的过早剪枝。 + 以CVRP100为例，实验结果SGBS好于处EAS之外的推理方法，Fingure2 (a)。 + 精度低的模型（分布偏移） + 使用在CVRP100训练的网络模型解决CVRP200实例，Fingure2 (b)。 + beam search表现的比greedy还差，自适应搜索方法（Active Search、EAS、MCTS 和 SGBS）表现好，SGBS表现最好。 + 微调模型（陷入局部最大值） + 神经网络在进行搜索之前针对每个目标问题进行了微调，效果更好了，但经过微调的模型对其第一选择过于自信，并且模型的良好探索行为已经丢失，因为陷入了局部最优。SGBS受影响小。Fingure2 (c).  ## 4. SGBS + EAS **Efficient Active Search for Combinatorial Optimization Problems** --- >[1] Andr ́ e Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations , 2022. Bello et al. (2016)提出主动搜索，它使用强化学习在测试时针对单个实例调整（训练的）模型的权重。主动搜索是一种迭代搜索方法，它在每次迭代中使用给定模型对单个测试实例的解决方案进行采样，然后调整该模型的参数，目的是增加在未来迭代中生成高质量解决方案的可能性。虽然主动搜索易于实现，但它无法与最先进的方法相媲美，因为为每个测试实例调整所有模型权重非常耗费时间和内存。这篇文章没有更新所有模型权重，而是提出并评估了三种有效的主动搜索策略，这些策略仅在搜索过程中更新参数的子集。  给定一个已经训练好的模型，我们研究调整 + （1）由编码器模型生成的问题实例的正常静态嵌入， + 更新A subset of the embeddings $\hat{\omega } \in \omega$ + 损失 $L_{RL}$ 基于 REINFORCE (Williams, 1992)，是生成的解决方案 E[C(π)] 的预期成本。我们的目标是调整嵌入参数以增加生成成本更低的解决方案的可能性（例如，TSP 的游览长度更短）。损失 $L_{IL}$ 是对（重新）生成迄今为止所见最佳解决方案的对数概率的否定。我们调整embedding参数来增加这个概率。   + （2）添加到解码器的额外实例特定残差层的权重， + 将特定于实例的残差层添加到经过训练的模型中。在搜索过程中，更新添加层中的权重，而所有其他原始层的权重保持固定。  + （3）直接影响模型返回的概率分布的查找表的参数。 + 使用一个简单的查找表来修改给定模型的策略。对于给定状态下的每个动作，该表提供了有关如何更改其概率的指南，以便采样的解决方案更有可能与过去找到的最佳解决方案相似。 + redefine the probability of selecting action at in the state st as $q_{φ}(a|s_{t}, ω)^{α} · Q_{g}(s_{t},a_{t})$ + 这里，α 是超参数，g 是将每个可能的状态和动作对映射到表 Q 中的函数。  --- EAS由两个分量组成的损失函数调整插入原始神经网络（具有预训练参数 θ）的额外层中的一小组新参数 ψ。第一个，JRL，旨在降低生成解决方案的预期成本，而第二个损失，JIL，鼓励模型以更高的概率输出现有解决方案。我们通过交替运行两种方法（参见算法 2）将 SGBS 与 EAS 结合起来  ## 5. 实验 ### TSP&CVRP  (使用 n = 100 和来自 Kool 等人的 10,000 个实例。还使用 n = 150、来自 Hottung 等人的 1,000 个实例的 200 个测试集执行泛化实验。) (在运行时的两个不同点报告 SGBS+EAS（和单独的 EAS）的结果；一个在中间点，另一个在算法似乎收敛时。) 总体而言，SGBS+EAS 明显优于所有学习的启发式方法。在三个 TSP 实例集上，SGBS+EAS 分别比 EAS 降低了 45%、33% 和 35% 的最优性差距。在 CVRP 实例上，SGBS+EAS 不仅优于 EAS（差距缩小了 52%、56% 和 59%），而且大大优于著名的启发式求解器 LKH3。在 n = 100 的 CVRP 实例上，与 HGS 的差距仅为 0.11%，我们进一步观察到，SGBS+EAS 在质量方面与最先进的手工技术相比具有竞争力，尽管在运行时间上不是这样。 ### FFSP 灵活流水车间问题 : 在 FFSP 中，作业由多个串联阶段处理，其中每个阶段由一组执行相同任务但可能以不同速度执行的机器组成。每台机器一次只能处理一项工作，因此需要一种调度方法来决定在什么时间在哪台机器上处理哪些工作，以实现尽可能短的制造时间。  标签: 组合优化 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭