基于垫脚石原理的神经进化算法：为人工智能注入创造力
垫脚石原理是一种将创造力注入人工智能的方法。
（图片来自Kevin Hong，Quanta Magazine）
近年来，神经网络借鉴了生物学策略的相关理论知识，实现了大飞跃，完成了之前无法完成的任务。神经进化作为人工智能的一个研究领域，试图通过进化算法而非随机梯度下降来设计和构建神经网络。然而，神经进化存在两大难题：高昂的计算成本和不明确的目标。最近，基于垫脚石原理的神经进化算法终于成功克服这些挑战，带来了新的研究思路：忽略目标比直接追求目标能更快速实现目标。忽略目标或许是制造真正智能机器的最佳方法。
从外星人的脸到跑车，这中间发生了什么？
2007年，中佛罗里达大学（University of Central Florida）的计算机科学家 Kenneth Stanley在玩他和学生们创建的网站Picbreeder时，一个外星人图案变成了赛车图案，这个发现改变了他的生活。
在Picbreeder上，用户会看到一组15张相似的图片，它们由几何形状或漩涡形状的图案组成，这些图案都是同一主题的变种。有时，一些图案就像一个真实的物体，比如一只蝴蝶或一张脸。用户被要求选择一张图片，他们通常会点击自己觉得最有趣的东西。完成操作后，屏幕内容会根据他们的选择做出变化，出现一组新的图片。从这种游戏性的探索中，产生了许多奇特的设计。
Picbreeder （一个在线艺术创作网站，允许图片像动物一样繁殖演化）
网址：http://picbreeder.org/index.php
picbreeder官网截图
Stanley是神经进化这个人工智能领域的先驱，神经进化利用生物进化原理来设计更智能的算法。对于Picbreeder来说，每张图片都是由一个类似于神经网络的计算系统产生的。当选择一张图片，生成新的15张图片时，被选择的图片对应的神经网络会突变为15个略有不同的变种，每个变种分别产生一张新图片。Stanley并没有打算让Picbreeder做出什么特别的东西，他只是有一种预感，依靠这个发现，也许能让他学到一些和进化论或者人工智能相关的东西。
外星人的脸（左）进化成一辆跑车（右）。
（图片来自Picbreeder）
一天，Stanley在网站上发现了一张像外星人的脸的图片，并开始了以它为起点的进化：选择一张图片，再选择下一张图片，这样一直进行下去。偶然的是，外星人圆圆的眼睛开始向下移动，像一辆汽车的车轮。最后Stanley一步步进化，得出了一辆漂亮的跑车。他一直在思考这样一个事实：如果是从零开始进化一辆车，而不是从一个外星脸的图片开始，他可能永远不会得到这样的结果，因此，他想知道这个试验对于直接去寻找问题的解来说，意味着什么。“这对我的整个人生产生了巨大的影响。”他观察Picbreeder上出现的其它有趣的图片，追踪了它们的演化轨迹，意识到几乎所有图片都是通过看起来完全不同的方式进化而来的。Stanley说：“看到这些迹象，我被震惊了。”
垫脚石原理：神经进化新思路
Stanley的发现促成了他所称的“垫脚石原理”，并以此为基础设计了一种算法，该算法可以更充分地发挥生物进化的无限创造潜力。
进化算法已经存在很久了。传统上，它们被用来解决特定的问题。在进化主体的每一代中，都会依据某种度量标准（例如，控制两足机器人的能力），选取表现最佳的解决方案，然后让其产生后代。尽管这些算法取得了一定的成功，但与其它方法（如近年来广泛流行的深度学习）相比，它们所需的计算量更大。
垫脚石原理超越了传统的进化方法，它不是针对特定目标展开优化，而是对所有可能的解决方案进行创造性的探索，这促使它取得突破性的成果。今年早些时候，一个基于垫脚石原理的系统在一个视频游戏中应对自如，而两个流行机器学习方法都对此无能为力。在近期Nature杂志发表的一篇论文中，DeepMind（率先将深度学习应用于围棋等问题的一家人工智能公司）称，该系统成功地将深度学习与一组具有多样性的解决方案的进化结合起来。
论文题目：
Grandmaster level in StarCraft II usingmulti-agent reinforcement learning
论文地址：
http://doi.org/10.1038/s41586-019-1724-z
通过与生物进化进行类比，我们可以看到“垫脚石”的潜力。在自然界中，生命的进化是没有任何总体目标的，用于一个目标的特性可能会被用于完全不同的目标。例如，羽毛可能是为了保暖而进化出来的，后来才进化的便于飞行。
生物进化同时也是产生人类智能的唯一系统，实现人类水平的智能是许多人工智能研究者的终极梦想。受生物的进化历程启发，Stanley和其他人已经相信，要使算法能够像人类一样轻松地（甚至更好地）在物理世界和社交世界中穿行，需要模仿大自然的策略。他们认为，不能对推理的规则进行硬编码，或让计算机学会在特定的性能指标上获得高分，而是必须让一组解决方案蓬勃发展进化。让它们优先追求新颖性（novelty）或趣味性（interestingness），而不是像走路或说话的能力这样的具体目标。这样它们可能会发现一条间接的道路，一些垫脚石，相比直接通过进化寻求走路和说话这些技能，垫脚石算法最后能更好地完成走路和说话这样的任务。
新颖性搜索：
以新颖性为目标的神经进化算法
在Picbreeder之后，Stanley开始论证神经进化可以克服其最显著的反对意见：“如果我运行的算法具有这样高的创造力，以至于我都不确定它会产生什么，从研究的角度来看，这是非常有趣的，但从商业的角度来看，这很难找到具体的应用场景。”
他希望能证明，仅仅追寻着新奇的想法，并以此为进化方向，那么算法不仅可以产生多种多样的结果，而且可以解决问题。更大胆地讲，他的目标是证明，完全忽略某个目标比直接追求它更能让你快速达到目标。他通过一种叫做新颖性搜索的方法来做到这一点。
介绍新颖性搜索方法（novelty search）的论文：
Abandoning Objectives: Evolution Through the Search for Novelty Alone
论文地址：
https://www.mitpressjournals.org/doi/abs/10.1162/EVCO_a_00025
这个系统以一个神经网络为基础。神经网络是由多个神经元（小的计算单元）层层连接排列组成，一层神经元的输出通过具有不同权重的连接传递到下一层。举一个简单的例子，输入数据（例如图像）到神经网络中，随着图像信息的层层传递，网络提取的内容信息越来越抽象。最终，最后一层计算出最高级别的信息：图像的标签。
在神经进化中，你首先要将各层之间的权重初始化为随机值。这种随机性意味着网络不能很好的完成任务。但是，从这种令人遗憾的状态出发，你可以创造一组随机突变（random mutations），也就是权重略有不同的后代神经网络，并评估它们的能力。你保留最优秀的一个神经网络，然后重复以上过程产生更多的后代。（更高级的神经进化策略还会在神经元和连接的数量和排列方面引入突变。）神经进化是一种元算法（meta-algorithm），一种用于设计算法的算法。最终，这些算法可以有不错的表现。
为了测试这个垫脚石原理，Stanley和他的学生Joel Lehman调整了选择过程。新颖性搜索不选择那些在任务中表现最佳的网络，而是选择那些与父辈行为显著不同的网络。(在Picbreeder中，人们倾向于趣味性；而在这里，新颖性搜索倾向于新颖性。)
在一次测试中，他们将虚拟的轮式机器人放到迷宫中，不断进化用来控制它们的算法，希望它们能找到出口。他们从0开始进化了40次。在一个用来对比的程序中，控制算法是根据它们离出口的距离（直线距离）来选择的，这个对比程序进化出的机器人在40次中只成功3次。而新颖性搜索完全忽略每个机器人离出口的距离，成功39次。成功的原因是机器人设法避开了死胡同。它们没有面向出口，也没有用头撞墙，而是探索了陌生的领域，找到了解决办法，最后意外地获得成功。纽约大学的计算机科学家Julian Togelius说：“新颖性搜索很重要，因为它颠覆了一切，本质上就是在问，如果我们没有目标，会发生什么。”
Stanley提出自己的观点，追求目标可能成为实现这些目标的阻碍。后来，他找到了巧妙的方法来将新颖性搜索与特定目标结合起来。这促使他和Lehman创建了一个用以模拟自然界进化中特定生态位（niche）的系统。在这种方法中，算法只与其它类似的算法竞争。正如蠕虫不与鲸鱼竞争一样，该系统让处在独特的“算法生态位”的算法独立进化，使得从中得以涌现出各种有前景的方法。
这种带有局部竞争的进化算法已经显示出熟练处理像素、控制机械手臂以及（如Nature杂志封面所描述的）帮助六足机器人像动物一样在失去肢体后快速调整步态的能力。这些算法的一个关键因素是它们培育了垫脚石。他们不是始终优先考虑一个整体最佳解决方案，而是保持了一组多样化的充满活力的小的局部生态，其中任何一个都可能会对最终的解做出贡献。而最佳解决方案可能产生于一个在不同小生态之间跳跃的算法。
介绍带有局部竞争的进化算法的相关论文
论文题目：Evolving a diversity of virtual creaturesthrough novelty search and local competition
论文网址：https://dl.acm.org/citation.cfm?id=2001606
Nature 封面报道：Press material for "Robots that canadapt like animals"
论文网址：https://members.loria.fr/JBMouret/nature_press.html
垫脚石原理克服了神经进化的缺点
对于Stanley（现在在Uber人工智能实验室工作）来说，垫脚石原理解释了创新：如果你带着一台现代电脑回到过去，告诉研发真空管的人，放弃它们的研究，然后开始研发笔记本电脑，那么我们将不会拥有真空管，也不会拥有笔记本电脑。这也解释了进化：我们是从扁形虫进化而来的，扁形虫并不是特别聪明，但具有两侧对称性（bilateral symmetry）。Stanley说：“目前还不清楚两侧对称性与智能有什么关系，更不用说与莎士比亚有什么关系，但这之间确实是相关的。”
在过去的十年中，神经进化经历了意想不到的曲折过程。长期以来，它一直生活在其它人工智能领域的阴影之下。
德克萨斯大学奥斯汀分校（University of Texas，Austin）的计算机科学家Risto Miikkulainen（同时也是Stanley的前博士生导师）表示，神经进化这种方法最大的缺点之一就是它所需要的计算量。在传统的机器学习中，当你训练一个神经网络时，它会逐渐变得越来越好。而在神经进化中，权重随机变化，网络的性能可能会比变化之前更差。
另一个缺点也很显然，大多数人都有一个想解决的特定问题。这种针对趣味性进行优化的搜索策略可能会让你为该问题找到一个创造性的解决方案，但是也可能把你引入歧途，找不到正确的解决方案。
话又说回来，没有什么策略是完美的。在过去五年左右的时间里，人工智能不同领域的研究如深度学习和强化学习呈现爆炸式增长。在强化学习中，算法与环境相互作用（例如，机器人在现实世界中穿行，AI玩家在游戏中竞争），通过反复试验来学习哪些行为会产生期望的结果。Deepmind使用深度强化学习开发了一个程序，可以在围棋上击败世界上最好的棋手。在此之前，许多人认为这一壮举还需要几年或几十年的时间才可能实现。
但是强化学习可能会陷入困境。稀疏或不频繁的奖励不能给算法足够的反馈，无法使算法朝着目标前进。欺骗性奖励（即阻碍长期进步的短期收益）也会使算法陷入死胡同。因此，尽管强化学习可以在《Invaders》或《Pong》这些加分频繁且目标明确的游戏中击败人类，但在其它缺乏这些特性的经典游戏中，它们却表现平平。
基于垫脚石原理的神经进化算法是深度学习方法的补充
在过去的一年里，基于垫脚石原理的人工智能最终成功克服了该领域中许多长期存在的挑战。
在游戏《Montezuma’s Revenge》中，Panama Joe穿梭于地下迷宫中的各个房间，收集开门的钥匙，同时避开敌人和障碍物，如蛇和火坑。为了打赢这个游戏，Stanley、Lehman、Jeff Clune、Joost Huizinga和Adrien Ecoffet（这五个人都在Uber人工智能实验室工作）开发了一个系统，在这个系统里，Panama Joe基本上四处游荡，随机尝试各种行动。每次到达一个新的游戏状态（即到达一个新的位置，有一套新的道具），他都会把到达这个状态所采取的一系列行动归档存入记忆中。如果他后来找到一条更快的路径来到达那个状态，那么旧的记忆就会被替换掉。在训练期间，Panama Joe不断挑选一个存储状态，随机地探索一会儿，并将他发现的所有新状态添加到记忆中。
最终，这些状态中，出现了一个赢得比赛的状态。Panama Joe的记忆中记载着他为实现目标所采取的所有行动。他没有使用神经网络或强化学习（收集钥匙或接近迷宫出口时没有奖励）就实现了目标，只是通过随机探索和寻找巧妙的方法来收集和连接垫脚石。这种方法不仅击败了最好的算法，还打破了人类的世界纪录。
同样的技术，研究人员称之为Go-Explore，在《Pitfall》游戏中击败了人类专家！在这个游戏中，Pitfall Harry在丛林中穿行寻找宝藏，同时避开鳄鱼和流沙。没有用其它机器学习方法，Go-Explore得分就超过0。（Go-Explore是第一个得分超过0的算法。）
介绍Go-Explore技术论文：
论文题目：Evolving a diversity of virtual creaturesthrough novelty search and local competition
论文网址：https://dl.acm.org/citation.cfm?id=2001606
DeepMind被认为是强化学习的研发核心，现在也对神经进化越来越感兴趣。1月份时，该团队展示了AlphaStar软件，这款软件可以在复杂的视频游戏《星际争霸II》中击败顶尖的职业选手。在这个游戏中，两个对手控制着军队，通过建立殖民地来统治数字世界的领地。AlphaStar进化出了一群互相竞争、互相学习的玩家。在上周的Nature杂志上，DeepMind的研究人员宣布，最新版本的AlphaStar已经在一个流行的游戏平台上《星际争霸II》活跃玩家中排名前0.2%，成为第一个在不加入额外限制的前提下，登上流行电子竞技顶端的人工智能。
AlphaStar软件介绍：
https://deepmind.com/blog/article/alphastar-mastering-real-time-strategy-game-starcraft-ii
参与了这个项目的DeepMind的计算机科学家Max Jaderberg说：“与AlphaStar合作的很长一段时间里，它一直在进步，但它仍然可以继续被改进。你可以训练一个智能体（agent），它的平均表现非常好，但你总是可以训练出另一个智能体来对付它，然后找出它的漏洞。”
与儿童游戏剪刀布游戏一样，《星际争霸II》中没有最佳的游戏策略。因此，DeepMind鼓励它的智能体进化出多样化的策略——不是作为垫脚石，而是作为目标本身。AlphaStar将五个不同的智能体的策略结合起来，最终以五比零击败两个职业选手。选择五个智能体，是为了保证对手的任何一个策略都不会影响到所有的智能体。它们的优势在于它们的多样性。
Alphastar演示了进化算法的一个主要用途：保持大量不同的解决方案。最近另一个DeepMind项目展示了它的另一个用途：优化单个解决方案。该团队与Alphabet的自动驾驶汽车项目Waymo合作，开发识别行人的算法。为了避免陷入一种效果很好但不是最佳策略的方法，他们保留了“小生境”或亚群体，这样使得新颖的解决方案在被顶尖的解决方案淘汰之前有时间发展。
近年来，基于种群的算法（Population-based algorithms）变得越来越流行，DeepMind的科学家兼机器人负责人Raia Hadsell使用计算资源的行业标准术语解释说：“部分原因是它们与我们现在拥有的计算机类型非常匹配。”Hadsell邀请Clune、Lehman和Stanley在6月份的机器学习国际会议（International Conference on Machine Learning，ICML）上做了两个小时的演讲，介绍他们的工作。Hadsell说：“我认为这是人工智能中很重要的研究领域，因为它是和推动人工智能发展的深度学习方法具有互补性。”
POET算法：用人工智能设计人工智能
到目前为止讨论到的所有算法的创造力都是有限的。AlphaStar只能提出关于《星际争霸II》的新策略。新颖性搜索一次只能在一个领域内（解迷宫或者步行机器人）找到新颖性。
然而，生物进化产生了无穷无尽的新颖性。细菌，海藻，鸟类和人类的出现，是因为解决方案在不断更新，同时问题也在不断演变。例如，长颈鹿是对树木变高带来的问题的回应。人类的创新也是如此。我们给自己创造了问题（例如我们能把人送上月球吗？）然后解决它们。
为了重现问题和解决方案之间的这种开放式对话，今年早些时候，Stanley、Clune、Lehman和Uber的另一位同事Rui Wang发布了一个名为POET（Paired Open-Ended Trailblazer）的算法。为了测试该算法，他们开发了一群虚拟的两足机器人。他们还为机器人开发了包含许多障碍的训练场，其中包括小山、沟渠和树桩。这些机器人有时会互换位置，尝试新的地形。例如，一个机器人学会了拖着膝盖穿越平坦的地形，然后它被随机地转移到有短树桩的地方，在那里它必须学会直立行走。当它再次被转移回第一个障碍训练场时，它的完成速度要快得多。通过这种间接的途径，机器人得以从一个难题中学习技能并将其应用到另一个难题中。
POET详细介绍：
https://eng.uber.com/poet-open-ended-deep-learning/
POET可以用来设计新的艺术形式，或者通过自己提出并解决新的挑战来取得科学发现。它甚至可以走得更远，这取决于它改造世界的能力。Stanley说，他希望建立的算法在十亿年后仍然可以做一些有趣的事情。
Stanley说：“进化发明了视觉，发明了光合作用，发明了人类水平的智能，发明了一切，并且所有这些都是通过一种算法来完成的。如果能捕捉到这个过程的一点点细节，我认为可能都是非常强大的。”
在最近的一篇论文中，Clune认为，开放式发现（open-ended discovery）可能是通向通用人工智能最快的途径。这里说的人工智能是指几乎拥有人类所有能力的机器。人工智能领域的大部分研究都集中在人工设计智能机器的各个构件上，比如不同类型的神经网络结构和学习过程。但目前还不清楚如何将它们捆绑在一起形成一个通用的智能系统。
开放式发现与通用人工智能相关介绍pdf文档链接：
https://arxiv.org/pdf/1905.10985.pdf
相反，Clune认为应该更多地关注设计人工智能的人工智能。算法将使用类似POET这样的方法来设计或进化神经网络和它们的学习环境。这种开放式的探索可能通过我们从未预料到的途径（或者各种不同的智能）来实现人类水平的智能。Clune说：“数十年的研究教会我们，这些算法总能让我们感到惊讶，并在智力上超过它的设计者。因此，随着这些算法变得更加强大和开放，我们不能自大地以为我们能够知道它们的结果。”
对研究人员施加过多的控制也可能是自大的表现。讽刺的是：Stanley最初向美国国家科学基金会提出Picbreeder项目时，该基金会拒绝了他的资助申请，称其目标不明确。但是，这个项目带来了大量论文和访谈、一本书和一家初创公司（Geometric Intelligence，被Uber收购，成为Uber人工智能实验室的核心）。Stanley说：“对我来说，有一件事真的很惊人，也很疯狂。那就是我如何走到这一步的故事，本质上和让我走到这一步的算法洞见是一样的。引导我产生见解的东西，实际上就是见解本身。”
原文地址：
https://www.quantamagazine.org/computers-evolve-a-new-path-toward-human-intelligence-20191106/
翻译：王佳纯
审校：郭瑞东
编辑：张希妍
推荐阅读
社交网络中的幂律分布：为什么有的人微信好友5000而你只有500？
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！