编者按:笛卡尔遗传规划(Cartesian Genetic Programming)在图像处理任务中已经发挥了不小的作用,这一方法同样可以应用到雅达利游戏中。说起雅达利游戏,我们首先会想到深度学习在其中做过的努力,但是本项目的研究人员们却用另一种有效的方法——演化算法,控制雅达利游戏的进行,结果显示,演化算法的性能并不比深度学习差。以下是论智带来的编译。
随着神经网络和深度学习技术的发展,计算机科学领域几乎被这些新技术占据。特别是神经网络,已经在某些任务上达到甚至超过了人类水平,例如目标和人脸识别、棋类游戏和多种街机游戏比赛。
这些网络都是根据人类大脑的工作原理建立的,因为人类大脑能产生最多的可能性,对吗?
答案不尽然。现在有一种全新的计算方式能比神经网络和深度学习拥有更强大的计算力。这行技术是基于人脑形成的过程——演化。换句话说,一些列迭代变化和选择生成了最复杂的机器——人类。演化的力量可以看成是奇迹。
自从30年前第一次应用于对生产线的优化后,进化计算就取得了令人瞩目的成果。但是最近几年,由于深度学习的发展和它取得的巨大成功,进化计算淡出了人们的视线。
今天,来自法国图卢兹大学的研究人员Dennis Wilson等人的一项研究让人们注意到了演化计算能达到和深度学习机器同样的性能。在街机游戏,例如雅达利游戏中的《乓》、《打砖块》、《太空侵略者》中表现出了超越人类的水平。这项工作表明,人们在重视深度学习方法的同时,也要给予演化算法相当的关注。
演化计算和神经网络完全不同,它的目标是创建能用反直觉式的方法解决特殊问题的代码。通常代码创建的一般方法是有了特定目标后按第一原理开始书写。
而演化计算用的是另一种方法,它完全是随机生成代码,并且不只有一个版本,而是多个版本,有的时候甚至由成百上千个片段随机拼凑起来形成代码。
但是很多情况下,这些代码片段的效果并不是很好。接着它们会再次重新生成,其中会加入更多的代码片段。然而,第二次训练和第一次的代码不会完全相同,一定有某些改动。这些改变可能会导致某种计算点突变。
之后生成的新代码会经过测试,看它们表现的如何。表现最好的代码会优先进入下一批代码生成,以此类推。
这一过程就是代码演化的过程。随着时间的推移,代码表现得越来越好,多次迭代后,如果条件合适,它的表现会比人类设计的代码更好。
计算机科学家们已经成功地将演化计算应用到很多问题上,包括机器人设计和建造航天器部件。
但是,深度学习的巨大成功让演化计算“失宠”了。所以,一个很重要的问题是,演化计算能够达到和深度学习同样的水平。为了弄清楚这一点,Wilson和他的同事们用演化计算创建出了能玩雅达利游戏的代码。
这些游戏目前在Arcade Learning Environment数据集中可用,该数据集经常被用来测试不同类型游戏的学习行为。数据集含有61种雅达利游戏,例如《乓》、《太空侵略者》、《打砖块》和《功夫大师》等等。
任务的目的是创建一套算法,只需要看屏幕上输出的效果,就能熟练地玩雅达利游戏,和人类玩游戏的方式一样。所以算法必须分析每次游戏动作的位置,然后决定如何移动才能得到最多分数。
对所有游戏的控制方法都是相同的,它对应着八个不同的移动方向:上、下、左、右、以及左上、左下、右上、右下。另外还有一个可以和八个方向结合的按钮,可以随意进行组合。并不是所有游戏都能用到18个可能的结合,一些游戏只能用到四种。
首先,代码创造出来之后,演化方法需要一系列术语来生成计算代码,其中包括简单的“ADD(x+y)/2”到更复杂的“return the 1-element x-vector if x is a scalar”。
同时,选择何种术语来组成这一系列词典是非常重要的,Wilson和他的同事们使用的是已经被称为笛卡尔遗传规划(Cartesian Genetic Programming)的集合。
在这一过程的开始,系统随机创建包含40个术语的代码,这可以看作是该项目的“基因组”。之后,这些代码经过游戏测试,看最终能得到多少分。根据它们的表现,“基因组”会不断改变进行重复生成,再进行测试。最后,该研究小组用这种方法测试了10000个“基因组”。
结果很有趣。最初,代码玩游戏的水平很差,但是经过一段时间的迭代,代码的表现越来越好。经过多次代码生成后,它们已经表现得很好了,甚至有时还超过了人类。
代码在很多情况下都会生成全新的游戏策略,通常都很复杂。但是有时也会找到被人们忽略的简单游戏方法。
例如,当计算机在玩《功夫大师》时,演化算法发现,最有价值的攻击是下蹲拳。下蹲更加安全,因为它能躲避一半的子弹并且进行近身攻击。算法最初的策略是重复使用这一技巧,不添加其他动作,事后想来这样做也是有道理的。
这样研究人员非常吃惊,他们表示:“运用这种策略比正常玩这种游戏得到的分数更好,而且现在代码在这个游戏中只使用下蹲拳。”
总的来说,演化出的算法能很好地掌握多种游戏,甚至超过人类水平。更重要的是,这些算法能和深度学习相媲美。它同样还有另一种结果:“虽然这一项目体积相对较小,很多控制器在这种方法上就非常有竞争力,所需的训练时间就更少。”
生成的代码还有另一个优点。由于它很小,就很容易观察它的工作过程。相反,深度学习技术众所周知的问题就是有时我们不知道它为什么会做出某种决策,这就会导致很多现实和法律问题。
总的来说,这项有趣的工作也许能提醒那些只关注深度学习的科学家们,还有演化算法这样的替代性技术。
Keras缔造者、深度学习研究人员François Chollet在推特上表示:“这项研究很了不起,通常用深度学习总会经历多次微小迭代,而这项工作是不同类型的尝试。通常,如果你能在老生常谈的问题上得到小有竞争力的结果,那么最终一定有所作为。”
原文地址:www.technologyreview.com/s/611568/evolutionary-algorithm-outperforms-deep-learning-machines-at-video-games/
论文地址:arxiv.org/abs/1806.05695