谷歌使用深度强化学习发现了更快的排序算法

出品|开源中国

谷歌旗下 AI 实验室 DeepMind 的工程师团队在 Nature 官网发表了一篇论文，称使用深度强化学习发现了更快的排序算法。

排序或散列等基本算法在一天内的使用量可达数万亿次，随着计算需求的增长，让这些算法尽可能高效变得至关重要。基础排序算法在过去取得了显著的进步，但如要进一步提高这些算法例程的效率，对人类科学家和已知的计算方法都具有挑战性。

而 DeepMind 通过将 “寻找更好的排序程序” 任务制定成一个名为 AssemblyGame 的单人游戏。在这个游戏中，玩家需要选择一系列低级 CPU 指令（汇编指令），然后将其组合起来产生一种新的高效排序算法。

然后 DeepMind 训练了一个新的深度强化学习代理 ”AlphaDev“来玩这个游戏，AlphaDev 的主要学习算法是 AlphaZero 代理的扩展，并使用深度神经网络指导蒙特卡洛树搜索 (MCTS) 规划过程。

（完整的训练过程和细节分析可以在deepmind 的论文中细细阅读）

最终，AlphaDev 从零开始地发现了几项新的小型排序算法，分别可用于对大小为 3、4 和 5 的列表进行排序，且均优于已知的人类基准。

目前这些算法已经集成到 LLVM 标准C++ 排序库中，使用强化学习的新算法替换掉了原有的 LLVM libc++ 标准排序 3、排序 4 和排序 5 算法，这些基础算法是 C++ 排序库的基本组件，通常被较大的排序算法多次调用。

值得一提的是，DeepMind 的提交是十多年来对 LLVM libc+ 排序算法子程序的首次更改。