本文介绍了一篇由Nathan Grinsztajn、Daniel Furelos-Blanco、Shikha Surana、Clément Bonnet和Thomas D. Barrett等人合作完成的研究论文，题为《Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization》。该论文发表于第36届神经信息处理系统会议（NeurIPS 2023），主要研究如何通过强化学习（Reinforcement Learning, RL）解决组合优化（Combinatorial Optimization, CO）问题，并提出了一种名为Poppy的训练方法，旨在通过训练一组互补的策略来提升组合优化问题的求解性能。

研究背景与动机

组合优化问题在物流、调度、资源分配等领域具有广泛的应用，但由于其通常属于NP难问题，传统的精确求解方法难以扩展到大规模问题。近年来，机器学习（尤其是强化学习）在解决组合优化问题上展现出巨大潜力，因为它不需要预先解决的实例或专家知识。然而，现有的强化学习方法通常依赖于单一的策略，难以在复杂的组合优化问题中取得理想的效果。为此，本文提出了一种基于群体（population）的强化学习方法，通过训练一组互补的策略来提升求解性能。

研究方法

本文提出的Poppy方法主要包括以下几个步骤： 1. 单代理预训练：首先，使用适合解决特定组合优化问题的架构训练一个单代理模型。这一阶段的目标是获得一个基础模型，后续可以通过克隆该模型来生成群体。 2. 群体训练：将预训练的模型克隆多次，形成一个包含多个代理的群体。在群体训练阶段，每个代理都会针对不同的问题实例进行优化，目标是最大化整个群体的性能。具体来说，Poppy通过一种新的强化学习目标函数来鼓励代理之间的互补性，而不是依赖手工设计的多样性指标。 3. 群体目标函数：Poppy的目标函数旨在最大化群体中表现最好的代理的性能。具体来说，对于每个问题实例，只有表现最好的代理会接受训练，而其他代理则不会更新。这种方法通过无监督的方式实现了代理之间的互补性，从而提升了整个群体的性能。

实验结果

本文在四个经典的组合优化问题上对Poppy进行了评估，包括旅行商问题（Traveling Salesman Problem, TSP）、带容量约束的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）、0-1背包问题（0-1 Knapsack Problem, KP）和作业车间调度问题（Job-Shop Scheduling Problem, JSSP）。实验结果表明，Poppy在所有四个问题上都取得了最先进的性能，显著优于其他基于强化学习的方法。

• TSP和CVRP：在TSP和CVRP问题上，Poppy的表现优于现有的强化学习方法，尤其是在大规模问题上表现出更强的鲁棒性。随着群体规模的增加，Poppy的性能进一步提升。
• KP和JSSP：在KP和JSSP问题上，Poppy同样表现出色，显著缩小了与最优解的差距。特别是在JSSP问题上，Poppy在相同的计算资源下，显著优于其他方法。

结论与意义

本文提出的Poppy方法通过训练一组互补的策略，显著提升了组合优化问题的求解性能。与传统的单一策略方法相比，Poppy能够在不需要手工设计多样性指标的情况下，自动实现代理之间的互补性。这一方法不仅在理论上具有创新性，还在实际应用中展现了强大的性能，尤其是在大规模组合优化问题上。

研究亮点

1. 群体训练的引入：Poppy通过训练一组互补的策略，显著提升了组合优化问题的求解性能，避免了单一策略的局限性。
2. 无监督的多样性：Poppy通过最大化群体性能的目标函数，自动实现了代理之间的互补性，而不需要依赖手工设计的多样性指标。
3. 广泛的应用性：Poppy在多个经典的组合优化问题上都取得了最先进的性能，展示了其广泛的适用性和强大的求解能力。

未来研究方向

本文的研究为未来的组合优化问题求解提供了新的思路。未来的研究可以进一步探索更大规模的群体训练、结合主动搜索方法以进一步提升性能，以及将Poppy方法应用于其他具有挑战性的强化学习任务中，如代码生成、图像生成和蛋白质设计等。

总之，Poppy方法为组合优化问题的求解提供了一种高效且通用的解决方案，具有重要的理论和应用价值。