深度学习不是万能的,进化算法在游戏中表现更佳

编者按:深度学习的如日中天遮掩了进化算法的光芒,但进化算法也有望重归大众视野,毕竟在某些领域它可比深度学习领先得多。本文译自MIT Technology Review中原标题为"EVOLUTIONARY ALGORITHM OUTPERFORMS DEEP-LEARNING MACHINES AT VIDEO GAMES"的文章。

基于目前人类在神经网络算法和机器深度学习取得的成就,很容易让人产生计算机科学只包含这两部分的错觉。毕竟神经网络算法在人脸识别、棋类和各类街机游戏竞技中的表现已经开始超越人类了。

因为这些网络算法都是基于人类的思考模式进行的,好像没什么比这个更有潜力了。但事实果真如此吗?

答案是:不完全是。一种全新的算法甚至比深度学习和神经网络有更明显的优势:这种算法是基于创造人类大脑的方式——进化来进行的。

深度学习不是万能的,进化算法在游戏中表现更佳

换句话说,人类是在一系列迭代和择优中产生的,由此诞生了眼睛、耳朵、大脑等精密的工具,足以可见进化的力量。

这也就是计算机科学家一直试图掌控这种能力的原因,况且这种所谓的进化算法在自首次被投入企业生产线优化中的30年里已经创造了巨大的奇迹。

然而近几年由于深度学习技术的如日中天,这种算法也只能屈居其后。

如今,在Dennis Wilson和法国图卢兹大学其他同事的共同努力下这种局面似乎有所逆转,他们在2013年的一次标志性任务的完成中证明了进化算法甚至能够与深度学习相匹敌——在Pong、Breakout和Space invader等街机游戏的表现中均完胜人类,直接显示出无限的潜力。

进化算法的工作原理完全不同于神经网络,其以一种看起来反直觉的方式来创建解决特定问题的计算机代码。

之所以这么说是因为传统的代码创建都是考虑到特定目标依照基本原理进行编译的,而进化算法则不同,它始于完全随机生成的代码,且不止有一个版本,而是诸多版本甚至数十万个代码片段组装而成。

每一个代码都会经过测试看是否符合目标要求,当然由于随机组合结果也可能不理想。

但一旦发现某些代码优于其他代码就会在新一代代码中再现这些片段,其中会延展出优质代码的更多副本。

但是下一代代码不能完全是上一代的复制品,必须有所改变,这就涉及切换代码中的两个部分——即点突变,也可能涉及两个代码被各切一半相互交换——就像有性重组一样。

接着在新一代中继续测试,选择优质代码出现在下一代中,以此类推。

通过这种方法,代码就进化了。随着时间的推移,这些代码会变得越来越优异,如果没有偏离正确的方向,那么它们最终会比任何人为设计出的代码都要完美。

计算机科学家也已成功地将进化算法应用在各种问题中,小到制造机器人,大到制造航空仪器,到处都有它的身影。

但就是由于深度学习算法的热潮,使得它失宠了。所以这就出现了一个值得深思的问题:到底进化算法能不能和深度学习匹敌?为了搞清事实,Wilson和他的同事们使用这种方法来进化能控制20世纪80到90年代街机游戏的代码。

这些街机游戏可以在Arcade Learning Environment数据库中进行使用,目前该数据库也越来越多地被用来测试各种算法的学习能力。该数据库中有61款雅达利游戏,其中包括Pong,Breakout和Space invader等。

该种方法的任务是创建一种仅通过观察屏幕显示就能玩像Pong这种游戏的代码,就和正常人打游戏一样。为此,算法必须能认真分析游戏位置,通过最优化移动力争高分。

当然,对任何游戏的控制都是如此。首先对应地要控制八个方向的按钮(上、下、左、右和四个对角线方向),接着要与不同的攻击按钮组合,但不是所有游戏都有18种组合方式,有些只有四种。

为了完成这项研究首先必须创建代码。 进化算法需要一个可以连接起来形成计算机代码的指令集,这些指令的范围从简单的指令(如ADD(x + y)/ 2)到更复杂的指令,例如“如果x是标量,则返回1元素x向量”,每个指令即进化算法中的算子或基因。

当然这个指令集中的指令选择非常重要,Wilson和同事们选用的是为笛卡尔遗传规划制定的集合。

该程序从随机创建包含40个指令的代码开始,即该计划的“基因组”,根据基因组在游戏中的测试得分判断其表现能力。后根据基因组的执行情况对其进行突变再造加入下一次测试中。研究团队以这种方法测试了10000个基因组。

测试结果十分耐人寻味:起初基因组在游戏中的表现都很糟糕,随着不断的再生能力直线上升,最后甚至比正常人类的表现更优秀。

尽管大多基因组都在做一些全新的复杂游戏的游戏攻略,但它们有时也会发现一些人类很容易忽略的问题。

例如在玩《功夫大师》时,进化算法发现最有效率的动作是蹲伏拳,因为在蹲伏中是最安全的:既可以抵挡一半的子弹,也能对附近发起攻击,游刃有余。于是该算法会在没有其他动作的情况下重复蹲伏拳。事实也证明这确实是有效的。

Wilson等研究人员均对此发现感到惊讶:“这种策略比正常玩得分更高,但一般人玩游戏只会在特殊情况下才发动蹲伏拳。”

当然这种进化算法在其他游戏中的表现也相当漂亮,甚至赶超了深度学习算法。此外还有一个优点,因为进化算法比较小量,所以很容易探测它是如何工作的;而众所周知,深度学习算法很难搞清楚为什么产生了特定结果,有时候很容易产生法律纠纷。

总之,这项研究不仅有趣,也为计算机科学家提了个醒:进化算法是个强大的替代算法,应用场景很多元化,错过它可能会很可惜。毕竟有些研究人员已经用它来迭代深度学习了,不得不说潜力巨大啊。

本文转载自:36kr
本文翻译自 www.technologyreview.com原文链接

最新文章