在线交互神经演化

1、在线交互神经的演化亚德里恩·阿戈吉诺()肯尼思·斯坦利()里斯托·米库莱伦()美国德克萨斯大学奥斯汀分校计算机科学系摘要在标准的神经演化过程中，一系列网络系统在任务操作的时候得到进化，其中最能解该决任务的网络系统由此被发现。该网络系统在受到改进之后被应用于解决将来出现的问题。在这种方式下演化而来的网络系统并不能很好地对实时互动进行操作。要想提前形成一种既能有效应用于未来任何环境中又能有效应用于任何互动方式中的解决方案是很难得。本文提议推进在线前馈

2、神经网络，创建能够提高他们实时互动性能的服务器。这种方法已经在一个游戏世界中得到验证；在该游戏中，人类的对手是由神经网络控制的个体。通过进化，这些个体学会了对不同对手做出反应，并会恰当考虑到互斥目标。该个体一开始是脱线进化，然后是在线进化，由此它的性能得到了很到程度的提高。该个体不但能适应对手不断改变策略的小说环境以及游戏布局，还能在曾经在脱线训练中出现的情境中提高性能。本文将描述在线进化的一个工具，并说明这是个有效地方法，其性能优于仅由脱线进化而来的性能。1. 引文遗传演算法与神经网络是一个强大的组合，该组合在过去已经成功地使用于许多应用领域中。例如，多种神经进化方法已经被应用于各种棋盘游戏

3、中，如黑白棋、围棋和西洋双陆棋（3；7；10）。同时，随机动态属性任务也成功得到了进化，如觅食，放牧，通信和捕获猎物（2；7；11）。在此以前的所有工作中，网络系统是脱线进化的。在每一代中，个体们先进行一回合游戏，然后就得到了进化。接下来的一代个体是在前一代游戏过程中表现好的个体中创造而来的。在进行了很多回合的游戏以及多次的进化之后，一些技术娴熟的个体变脱颖而出。 虽然已证实脱线神经进化在棋盘游戏以及动态属性环境中是有用的，却很少被应用于实时互动的环境中。现在的主要问题是在这些领域中，好的性能要能适应在线对手以及不断改变的环境。例如，在线进化的战术单位能让军事模拟在迅速变化及不可预测的环境中更

4、加真实。机械控制可以在线进化为一个机器人，尝试着适应新的环境以及应付突发问题，如传感失败。在线控制中最棒的一个例子就是在实时游戏中的例子。在这个例子中，对手不断地改变策略，环境不断地给出新的挑战。在游戏的每一回合中，网络系统必须在不断地评估和改变中作出调整。当进化发生在系统运转的时候，很少系统能够建立。其中我们所尝试的一个领域就是帮助机器人在迷宫中航行。在这个实验中，当机器人尝试在它从未见过的迷宫中航行的时候，网络群体得到了进化。机器人能够有效地学会在迷宫中航行需要花费很长的时间。这是很多领域所不能接受的，如在实时游戏中，运算必须要随着具体的实时对手做出调整。其他的关于由机器人所控制的进化的实

5、验也在脱线中进行了。图1：A. 游戏设计。士卒从基地出发，避开敌人寻找金矿。B. 智能行为开始的演示：士卒们向金矿前进，此金矿及其附近没有敌人防守。接下来士卒们将展示更多的复杂行为。更多关于这个过程的演示请登录此网站：/users/nn/pages/research/neuroevolution.html本文以实时游戏的典范作为平台，展示在线进化的方法。以此证明一个群体能够在线进化，该群体首先对其个体进行排名，并周期性地把排名靠后的个体淘汰，用下一代中排名靠前的个体替代。对个体在实时应用中功能的恰当评估保持了排名的及时更新。接下来，我们首先描述游戏

6、方案和评估办法，然后把在线进化与脱线进化进行详细对比。2. 游戏为了在互动环境中展开在线进化的步骤，我们首先进行一个小游戏，该游戏灵感来源于由电脑游戏软件公司暴雪娱乐所开发的流行电脑游戏魔兽争霸2。在这个小游戏中，有两个角色： 一个角色是由人脑控制的，为敌方；另一个角色是由电脑控制的，为士卒。该游戏由星球、基地、金矿、敌方以及一个士卒团组成（见图一A）。一共有30个士卒，他们的出发点全都设计在一个孤岛基地上。士卒们的目标就是尽可能快地找到其中的一个金矿，并且不被敌方杀死，而敌方的的占据地是由人脑控制的。如果士卒被敌方接触到，则死亡。一旦士卒找到了一个金矿，它就迅速返回基地，开始新的旅程。在魔兽

7、争霸中，士卒们只由简单的运算法则控制着，而这些运算法则很容易攻破，从而让士卒失去战斗力。无论安全还是危险，士卒们倾向于向最近的金矿前进。而在我们的游戏中，士卒们是由神经网络控制的，通过进化，它们具有更复杂的能力去寻找金矿和对敌方作出反应。在靠近但是有敌人防守的金矿和偏远但是没有敌人防守的金矿之间，士卒们能够估计两者的风险，并作出避开敌人的策略（图1B）。3. 网络构造每一个士卒都配有前馈神经网络，这个神经网络能告诉士卒在游戏中的每一步该怎么走（图2 A）。该网络并不是周期性的，这意味着士卒个体们对先前的活动和感觉并不会留下任何记忆。士卒接收到八个传感器读数的输入后生成输出，指示它想朝着纬度和经

8、度各走多远。传感器数据来自一个拥有八个眼睛的装置，该装置能够在这个游戏世界中感知士卒与金矿和敌人的距离。传感器的输入并不精确，因为士卒并不能够用它的感官器感应目标的实际角度。它只能感应目标的象限，并在此基础上作出决定。 还有可能存在解决该问题的其他方法，认识到这一点很重要。例如，可以使用增强学习法，如Q学习法和时间差分法。但是，大量实验表明在相似的领域中，进化法（特别是那些持续的、包含隐藏状态信息的进化）比增强学习法更有效。我们的目标就是把这方面的能力应用到网络系统中，证明在这些领域中，在线进化比脱线进化更有效。图2：A. 士卒神经网络的输入与输出。传感器的信息被传送到前馈网络的输入层。输出节

9、点指示士卒如何从当前位置向纬度和经度方向行进。B. 士卒眼睛的装置。其中的四个眼睛反馈每一个象限中士卒与金矿的平均距离，另外的四个眼睛反馈士卒与敌人的平均距离。4. 在线进化运算步骤在实时互动环境中，许多士卒不断诞生和死亡。进化是一个自然地学习方法。一个士卒的死亡，排位更高的发生突变的士卒将取代他的位置，也有可能被由两个高名次的士卒交配而来的士卒取代（图3 A）。突变的执行是由把高斯噪音应用到重量上实现的。交配运算是以单点交叉算子为基础的。转变而来的士卒与交配而来的士卒的比例对实验的影响不大（在我们所进行的实验中，该比例是50%/50%）。同时，精确的交配运算也并不是关键性的。士卒的排名高低是

10、以它们的生产率为基准的，建立在以下的公式上： 合适程度= （寻到的金矿数量×V-C）：年龄每寻到一处金矿，每个士卒能够获得V个单元的黄金，但是它将要被抽去C个单元的黄金作为它们出生的初始花费。这个措施意在奖励快速寻到金矿者，同时也在延长士卒的生命。因为较年长的士卒的初始花费就可以用更多的时间分期付清。本文中，V值为100，C值为1000。有了这些值，士卒的寿命就成了一个重要的标准。士卒群体们在寻找金矿的同时也在朝这方面的标准进化并躲避敌人。5. 脱线进化运算步骤为了评估在线进化的性能，我们必须要把在线进化与脱线进化进行比较。要想进行比较，标准地脱线神经进化运算步骤要进行调整，以适应进

11、化中的士卒群体的任务。原则上，脱线运算应该促进一个群体的发展，让它们能够应付游戏中出现的任何情况。因此，在促进群体进化的过程中，有必要采用较好的剧情样本。为了达到这一点，我们了制作了16中不同的情节。每一个情节中都有四个金矿和四个敌人，都是独一无二的，每个金矿由一个敌人看守。有些士卒在一些情节中表现很好，然后在另一些情节中则表现很差。脱线进化的任务就是培养总体成熟的个体，能应付各种情节。脱线运算与在线运算的尽可能地被设计成一样。一开始，有30个士卒随即产生。这30个士卒在16个场景中的表现都要受到评估。因为组员会影响到游戏的激烈情况，仅靠一个士卒是不可能贯穿整个情节的。为了解决这个问题，在情节

12、开始的时候，一个士卒将有30个副本，并一次性受到测试。士卒的原始版本的表现是基于该副本的表现的。在剧情的尾声，所有的副本将被舍弃。当所有的士卒经过所有情节的评估之后，新的士卒群体诞生了，这些士卒源于上一代士卒中表现最好的一个。在同样的方式下，死亡的士卒在在线进化策略中被替换。当士卒达到提高的极点的时候，它们就停止了进化。图3：A. 在线进化。当一个士卒死亡之后，一个优秀的士卒副本或一个由优秀士卒交配而来的士卒将取代它。这些优秀的士卒都是在随机的条件下从高名次的士卒中挑选出来的。B. 脱线进化。 每一个士卒在16个情节中都受到评估。新的群体在复制中产生，也在表现最好的士卒交配中产生在在线群体中，

13、新的士卒就是在这种方式下被挑选出来，以替换死亡的士卒。6. 结果要比较在线进化与脱线进化的表现，首先要让一个脱线群体进化。然后复制两个这样的群体。一个群体副本被标上“脱线”，如图4和5，这个群体在测试中没有进化。另一群体副本被标上“脱线+在线”，是在线进化的开端。在每一个情节中它能得到进化并且能实时进行调整。 如果在线进化真的更胜一筹，进化后的群体就应该在情节中迅速提高其表现。要强调的重要一点就是，这样的提高是没有保证的。实时进化很容易导致群体能力的降低。例如，当一个群体在与一种类型的敌人抵抗而得到进化后，它有可能丧失了与其它类型的敌人对抗的能力，也有可能在总体上丧失了其智能性。脱线群体的进化

14、不会受这样问题的困扰，因为它不是在短期的表现中得到进化的。这样的问题会不会导致在线进化不可取呢？本文将作出解答。我们用性能测量仪对这两个群体作了比较，测试结果差不多。我们主要测量的是士卒的存活率。随着时间的转移，这个数据将成为衡量士卒群体在个体游戏中性能提高以及下降多少的标准。6.1. 平均性能脱线与脱线+在线的群体的平均性能在图4A中已被标出。这些性能每250仿真时间步测一次，相当于在实时游戏中大概每两秒钟测一次。这些策略结果是平均每16个情节展开超过100个游戏。 整个实验进行了四次，每次都是用不同随机数量的士卒进化成不同的脱线群体，而每次试验的结果都相似。结果清晰表明：在线进化明显地提高

15、了游戏性能。第三测量点以99%的肯定性表明了其在数据上的差异具有重要意义。在进化的过程中，脱线的群体已经接触了所有的场景，而实验结果表明在同样的环境中，当脱线进化已达到极点的时候，在线进化依能继续提高其性能。一定要以脱线进化作为始点吗？这个问题很重要。结果表明即使在线群体是从随机重量开始的，无论处于任何场景中，它最终依然会超越脱线群体。这个结果表明在线进化能够应用在一些脱线群体难以被训练的领域中。6.2 推展到新的情境和变迁的环境中 为了测试在线和脱线进化在情景中的表现，第17号情景出现了。在这个情景中，金矿的位置安排比较独特，而敌人也因训练而有不同的表现。在新的情境中，脱线群体崩溃：它不再进

16、化，而它在之前的进化中所学到的方法也更适用于它曾经遇过的环境。与此相反，在线群体能够迅速适用新的环境（图5B）。这些结果表明在线进化在具有非常强的适应环境的能力。这在实时应用中是一个非常重要的优势，时刻让人感到惊讶。概况地说脱线群体不能很好地处理这些情景，但是在线进化却能够适应它们。这个结果也表明在线群体能够对环境的 忽然转变作出反应。对于早先遇到的环境，它能够很好地适应，对于新的环境，它同样能迅速适应，无论这个新环境是（图5A）不是（图5B）属于脱线训练中的一部分。这个结果表明在线进化是解决实时任务有力方法，因为在很多领域中，环境的忽然转变时非常重要的。图4：A. 在在线进化与脱线进化的比较

17、中，一个群体在所有情境中的平均表现。经历几个时间步之后，在线群体能够提高性能，而静态的脱线群体在整个游戏中基本相同（每个时间步相当于通过250个游戏程序的主要环节：从第三个时间步开始，数据上的差异尤为重要）。 B. 如果时间充足的话，由随机重量开始在线进化而来的群体将超越脱线进化而来的群体。在0,120和220,280时间段数据上的差异具有重要意义。图5：A. 即使群体已经适应了场景5，当突然转变到场景11的时候，也不会产生任何问题。图表中表示的数据平均为100圈。在6,14和17,28的时间段里的差异具有非常重要的数据意义。B. 当新情景是情景17的时候，这个提升甚至更加明显。图中显示的平均

18、数据为100圈， 从时间6开始，其中的差异在数据上具有非常重要的意义。7. 讨论与未来工作实验表明在实习互动环境中，在线进化比脱线进化更好，这具有很重要的意义。如果环境因素能够被预测的话，脱线进化确实是一个合理的策略，虽然在这种情况下，在线进化能够进一步提高性能。在一些情境中，当群体还没有完全发展成熟的时候，在线进化能够让策略得到完善。然而在现实生活中，未来的因素是不可预测的，而且会产生新的因素。能够对环境作出反应的能力是智能行为很重要的一方面。在线进化正好展示了这种适应新环境的能力，如17号场景中所分析的那样（图5B）。在线进化的这种性质是此次试验非常关键的结果。在应付不可预测的环境的时候，在线进化是一个非常有用的工具。在未来的系统中充分应用在线进化具有很大的潜能。随着微处理机和图解服务器性能的不断提高，复杂的实时仿真和虚拟环境正变得可行。可把在线进化应用到这种新的环境中与使用它的人互动。本文所展示的结果能够马上运用到游戏行业当中。原则上，这项技术能运用到任何游戏群体当中。很多游戏应用了不合适的运算法则，而实时进化能够让这些游戏更加有趣。在其他领域中，大量的研究是可能的。我们可以在机器人控制，交通管理和军事运用等领域上进行在线进化的测试。例如，机器人控制系统能够在在线进化中得到发展。这种