当前位置:首页-文章-行业新闻-正文

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

谷歌旗下 AI 实验室 DeepMind 的工程师团队在 Nature 官网发表了一篇论文,称使用深度强化学习发现了更快的排序算法。 排序或散列等基本算法在一天内的使用量可达数万亿次,随着计算需求的增长,让这些算法尽可能高效变得至关重要。基础排序算法在过去取得了显著的进步,但如要进一步提高

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

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

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

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

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

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

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

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

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

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

本文原创,作者:admin,其版权均为一念悟道所有。
如需转载,请注明出处:https://www.jiayezz.com/5670.html