丁哲航
2015年01月09日（第一版）
PDF格式的本文、演示视频、极其糟糕的源代码可以从百度云下载
http://pan.baidu.com/s/1eQtOcsq(人人网的文章排版功能真令人恶心，建议看PDF版)
前言
本文将要介绍的是我自己编写的一个虚拟生物程序。程序中，一个由人工神经网络控制的虚拟生物在一个存在障碍物的平面中运动，捡拾散落的物体。这确实是个听起来很平淡的的场景，但是这里控制虚拟生物的神经网络不是特意设计出来的，而是通过遗传算法从零开始进化得来的。也就是说，最开始这个神经网络完全是一团随机数，随着不同个体间的竞争——捡拾物体的能力——不断淘汰能力弱小的个体，最终使得种群内的个体越来越强。
我第一次接触遗传算法和神经网络是2013年年初，当时买了两本书，一本是Mitchell T.M.的《
机器学习》，另一本是Melanie Mitchell的《
复杂》，这两本书事后证明都非常有价值。《机器学习》中有关于神经网络章节（同样有遗传算法，但是当时还没看到）。作为教科书，里面有很详细的讨论，我也试过自己用matlab和C写过几个框架，不过一直没有真正用过。《复杂》是一本科普书，里面有作者给出的一个遗传算法的应用例子，本文的程序就是那个例子的升级版本。这个例子会在下一个章节做介绍。顺便一提的是，当时购买《复杂》是因为自己对分形和混沌现象相当有兴趣（意思就是学术水平其实是民科级），在读完书后，我才明白自己的感兴趣的这类奇奇怪怪的东西叫做复杂性科学（
Complexity）。虽然现阶段我对这类东西完全停留在“觉得有趣好玩”的阶段，纯粹用来自娱自乐，不过谁知道以后会发生什么呢。
背景知识
遗传算法
遗传算法是进化算法的一种。它模拟达尔文进化论的物竞天择原理，不断从种群中筛选最优个体，淘汰不良个体，使得系统不断自我改进。在系统中，每个个体具有一串遗传信息，这串信息代表了我们所要优化对象的全部特征。算法维持一个由一定数量个体组成的种群，每一轮，算法需要计算每个个体的适应度，然后根据适应度选出一定数量存活的个体，同时淘汰掉剩余落后的个体。随后，幸存的个体将进行“繁殖”，填补因为淘汰机制造成的空缺。所谓的繁殖，就是个体创造出和自己相同的副本。然而为了实现进化，必须要有模仿基因突变的机制。因此在复制副本的时候也应当使得遗传信息产生微小的改变。选择-繁殖-进化这样的过程反复进行，就能实现种群的进化。
数学上，这也可以被理解为在高维空间中寻找最优解的问题。如果个体的“基因”用两个数字（x，y）表示，而其输出的“表现型”也用一个数字（z）表示的话，那么遗传算法的过程就等同于在一个二维曲面（F (x，y，z) = 0）上寻找一个特定解——比如最大值。初始的时候，种群的各个个体随机分布在曲面的各个地方。每一轮，筛选出这些个体中输出值z较高的个体，然后拷贝出若干个副本，令其沿着曲面的不同方向随机挪动一小段。这样，向高处移动的个体将被保留，向低处移动的个体会被淘汰。并且总的趋势是所有个体都在往高处移动。但是，这样的机制完全有可能使得个体收敛到局部最优，而不是全局最优。克服这个问题的直接办法就是使种群的规模尽可能大，提高初始个体出生在全局最优附近的概率。在现实中，遗传算法处理的问题通常是复杂的、无法用简单算法优化的非线性问题。
上一节中，我提到了《复杂》一书展示过一个虚拟生物的例子。那个例子同样是一个捡拾物品的虚拟机器人，但是生物在一个离散的空间（棋盘格）上运动，同时也没有障碍物阻拦。一个数字串被用来作为机器人的基因。机器人通过周身的九个格子的状态编码出一个序号，然后从数字串中找到对应的“基因”，通过数字找到对应的操作。我在读完那一章节后也亲自编程尝试实现了这个实验。经过百代的进化，机器人成功进化出出色的捡拾罐子的能力（考虑到其只有一格的视野）。但是这还不够令人满意，因为对于在离散棋盘格上运动捡拾的机器人，靠手工设计的人工智能也能工作得非常好，没法体现出遗传算法的强大能力。我希望能够看到一个更加复杂和绚丽的系统。
人工神经网络
人工神经网络，顾名思义是对大脑神经系统的模拟。一个神经网络由大量互相连接的神经元组成，一个神经元可以向相连的神经元传递信号。经典的人工神经网络由三层神经元组成，分别称为输入层、隐藏层和输出层。每一层都包含了若干数量的神经元，每一个神经元都和下一次的所有神经元相连。输入层和输出层的神经元数量由系统需要的输入和输出值个数决定，隐藏层神经元的数量则决定了神经网络运算能力。
神经网络进行运算时，首先输出信号被加载的输入层的各个神经元。随后，每个输入层的神经元将信号按一定权值传递给下一层（隐藏层），而随后隐藏层在响应了来自输入层的信号后再以同样的方式将信号传递给输出层。输出层响应了来自隐藏层的信号后，得到最终的输出。神经网络的输出依赖于复杂网络之间的信号传递。就如同人脑一样，通常很难直接解释神经网络内在的逻辑。
神经元的连接是单向的，每一条连接都有一个权值，此外接收信号的神经元自身也有固有的偏置值。当信号传递时，神经元得到的信号是偏置值加上各个输入神经元信号和相应连接的权值相乘的总和。但是这个和值依然不是最终的信号值，还需要通过一个函数变换，通常被称为激活函数（activation function），不过我更喜欢称为“响应”。这个响应函数是一个非线性函数，其中一个常用的选择是反正切函数。非线性的响应函数是人工神经网络工作的关键，否则这种三层式的经典神经网络的结构就只能进行线性变换（可以直接等效成若干个矩阵的相加和相乘）。这种非线性的响应使得整个神经网络可以拟合复杂的空间。需要注意的是，通常这些非线性函数会在正负两个方向迅速收敛至两个极值，这使得神经网络的每次响应输出其实都是布尔值（也就是代表“是”和“否”的二值，对反正切函数作为响应函数的情形来说，可以用值的正负来判断）。因此，尽管输出的值是浮点数，但通常不把输出作为模拟信号来理解，而视为二值数字信号。比如说，输出值可以用来选择自动驾驶的汽车向左或者向右转弯，但是不宜用来控制速度的大小。量值的控制可以用编码的方式实现。
实验系统设计
环境和虚拟生物
本程序中，虚拟生物活动的空间是一块平面区域。在这块区域中，随机分布着若干块以线段形态存在的路障，以及若干质点形态的物品。此外，平面的四周也被围上了路障以防越界。虚拟生物出生在区域中的随机位置，具有位置和朝向两个属性。生物可以在平面区域自由移动。生物具有一个以自身为中心的圆形区域，当这个区域和物品相接触时，视为生物拾取到物品（分数奖励），当生物和障碍、边界相接触时，生物的运动会被阻碍。
每一刻（运算周期）生物可以得知如下信息。第一个信息是离个体最近的物品的相对坐标，以个体当前朝向为纵坐标，其垂直方向为横坐标。第二个信息是通过个体和最近物品间的线段是否和任何路障相交。第三个信息是生物上一次的行动是否撞到了路障。这三个信息的配置是合理的，没有给出太多信息使得神经网络失去智能的意义，也不至于要求神经网络做出过于复杂而不切实际的计算。而且这样的配置也很符合现实的生物特性。这三个信息可以类比为生物的听觉、视觉和触觉——听觉可以感知物体相对自己朝向的位置、视觉可以判断自身和目标间障碍、触觉可以实际感知面前的路障。生物可以在每一刻选择是否执行下面两项动作：前进一步和改变朝向。一步前进的距离是固定的，生物要么决定前进这个距离，要么决定不前进。生物的转向可以是向左或者向右一定区间内的任意值。
神经网络
采用的神经网络使用10个输入神经元、16个隐藏神经元和9个输出神经元。其中有6个输入和输出神经元相互连接。剩下的四个输入和三个输出则有固定意义。输入内容为前述的三个输入信息，其中坐标需要用两个神经元。第一个输出值用来控制是否前进，第二和第三个值同时决定生物的转向程度。程序采用差分——两个输出值的差值来决定生物的转向。采用这种方法的原因是，如果只用一个值来决定转向角度的话，由于响应函数的特性，结果几乎必然是只能向左或者向右转动固定的角度，而不能维持直线运动。如果采用差分的情况，则可以实现这样的效果（当两个值接近相同则不转向）。将其中6个输入输出相连的目的是将反馈机制引入网络，模拟了生物的记忆能力。
进化
实验中，遗传算法的种群规模被设定为40，即每代有40个互不相同的个体进行竞争。每个个体将单独在虚拟环境中进行24轮游戏，在每轮8000步的限制中，个体被要求尽可能多的捡拾物体。每触碰到一个物体可以获得1分。最后每轮的平均得分作为生物的适应度被记录。进化时，筛选出其中最优秀的10个幸存个体。每个幸存的个体可以繁衍三个后代。幸存的个体和繁衍的后代一起加入下一代的种群。繁衍包括复制和变异两个环节。复制是将原有个体的神经网络原模原样拷贝一份到新个体，随后变异环节会随机选择神经网络中某个权值或偏置值，修改为一个随机数。
实验结果
行为
进化开始时，每个个体都是完全随机产生的。然而此时已经有了优劣之分。绝大多数个体的平均分都接近零分。它们要么在原地打转，要么冲向一个障碍物就此僵死。初代最好的个体能够获得鹤立鸡群的11分平均分，相比之下，排名随后的几个个体分数都不到它的一半。这个个体能够表现出向物品移动的倾向（尽量使得切向坐标减小、同时保持不断移动），但基本的运动模式只是在平面上绕圈圈，偶尔会走走直线。基本上，拾到物品是凭运气。下一代种群的个体里，前一代一分不得的个体已经被淘汰了，每个个体或多或少能够拿到个位数的平均分，上一代的冠军个体到这一代依然名列前茅，它的后代也基本能拿到和它差不多的分数。我在程序中给每个个体加入了特定的标记，使得能够追寻不同“家族”的演化路线。但是这个功能只有前几代有用，因为用不了多久整个种群就会被单一家族所统治。到了第四代，整个种群只剩下三个家系在互相竞争，其中最衰微的一家在下一代就被彻底淘汰。在初代鹤立鸡群的个体的后代在第五代也差点被另一个家族的后起之秀驱逐殆尽，但因为第六代时的一个基因突变重新夺回了优势地位，而它的竞争对手在第九代被完全灭绝。
此时我们种群中的冠军个体以及能拿到接近30分的成绩了。我们的生物现在已经懂得主动寻找食物了。它基本上表现出两种运动策略。第一种是瞄准目标猛冲，但由于对神经的控制依然没有进化完全，路线总是歪歪扭扭的，有时还瞄不准目标。生物在吃到物体后往往会继续前行，直到一头扎进边界障碍，然后才调整方向对准下一个目标。另一种策略有趣的多，在猛冲的过程中，生物有时候会突然往奇怪的方向转弯，划出一个圆圈然后吃到和转弯方向相反位置的物体。在特定的情况下，它甚至能在画弧线的过程中吃到好几个排成线的目标。
进化的初期速度是飞快的，每隔几代就会出现一个特别的个体。随着它将基因散播给它的后代，那个特别的性状就会迅速进化，使得种群的分数直线上升。第十代时就出现了这样的情况，第九代的冠军个体的一个后代产生了一个特别的突变，获得了54分的高分。要知道在当时，前一代的得分普遍还在30分浮动，即使是那一代的冠军个体——突变个体的父亲，也只拿到了38分。这个54分的个体与它的后代迅速占领了种群。到第十三代时，那个突变体的孙子将分数改进到了63分，将其祖父辈的平均分翻了倍。这一代的个体已经不会在像过去那样横冲直撞了，“反向旋转”的奇怪捡拾策略成为了主导。这个奇怪的策略很可能是为了减小和环境中障碍的碰撞几率而演化出的。到了这一代，个体已经不太被障碍拌住而无法脱身了。因此，提升脱离障碍的技巧也成为了重要的进化驱动需求。
在这次突变之后，种群的冠军得分基本上呈快速的线性增长。到第30代的时候，冠军个体的分数已经达到了120分。那种旋转进食的奇怪策略到这一代已经完全消失了，取而代之的是沿着连人类都会赞叹不已的优雅曲线在一个个物体间穿梭。生物对障碍的规避能力也大大提升，一旦触碰到障碍，就会立即侧向一边，绕着圈离开。
到了这一步，物种的神经网络已经接近于成熟，进化开始放缓，行为的变化也变得十分细微。种群在100代的时候触碰到了180的分数线，随后以非常非常缓慢而挣扎的方式慢慢做着细微的改善。它们在六七白代的演化后最终停留在了200分这样的高分。从120分到200分具有很大的能力差距，但是他们的运动表现差异并不是那么明显。我们只知道他的失误概率小了，挣脱障碍更快了，然而基本的运行模式改变并不大。这也和现实是一样的，一个表现型成熟之后，自然不会再有质的改变。如果环境并不改变，那么剩下的工作就只是修修补补。，本质上毫无智能、只能得到有限信息的虚拟生物，已经运行得远远比开着上帝视角的人类玩家更加强大了。
进化
并不是每一次进化都能达到如此高的水准。每次运行进化的程序都会得到不同种群。这些不同的进化产物有着类似但又不同的生存策略，比如一些种群碰到障碍会沿着边缘划开，一些种群则选择绕一个半圆离开。不同的进化实例产生不同的种群，最终也收敛到了不同的分数。前一节描述的进化轨迹是我同时进行的五次实验中最好的一次结果。其余的四次进化收敛到了不到200的分数。最差的仅仅只有100分的成绩。
进化系统的局部收敛问题的确是遗传算法的一个难点所在。尽管很多时候局部最优已经十分出色，但是能收敛到全局最优自然是最好。我应对这个问题最简单方法就是：多进化几个版本，然后取最好的。
分数估计
进化系统的成功与否，和能否有效精确地估计个体适应度有很大关系。在本系统中，每个个体被放到虚拟空间中进行模拟计算，通过多次和长期测试力求获得精确的结果。但是实验的结果表明，即使如此每个个体多次进行适应度估计得到的偏差依然很大。右图是对一个初期个体进行500次测试后得到的分数分布。可以看到，得分分布在一个很大区间中。总体来说，得分大致呈正态分布，同时在低分段有较多的次数。这些结果很容易理解。生物因为不同场景会遇到不同的阻碍，突破这些阻碍的时间各不相同，同时有些阻碍是生物无法突破的。如此造就了图中的分布形状。可以料想，随着个体进化的成熟，被障碍卡住致死的情形越来越少，这个分布将越来越接近于正态分布，并且方差会越来越小。但是每次测试的平均值总是会有一定浮动。由于后期所有个体的基因都相当接近，分数也大体相同。相对巨大的方差波动必然使得任何个体都会在若干轮后爆出冷门淘汰。因此，即使到了最后的收敛期，也往往没有一个个体能够在种群中存活超过四轮的——即使理论上他们是永生的。
记忆
在编写这个程序之前，我猜测有记忆的生物和无记忆的生物可能会表现出很大的区别。在早先一些小规模的测试中，无记忆的种群也确实没有出现如有记忆个体那样复杂的行为——通常是一圆弧的形式一段一段地捡拾物品，并且只有很少很简陋的避障策略。然而，随着程序的改进和运算规模的增加，无记忆个体的表现并不明显比有记忆个体差。很多此前认为只有有记忆个体才能实现的策略，无记忆个体也实现了——如方向控制、避障等等。不过关于有无记忆的比较，现在还不充分，因此不适合得出很确定的结论。
展望
本系统实现的是几年来一直想做的神经网络和遗传算法的结合。虚拟生物当前运行在一个虚拟的（而且其实并不精确的）运动学模型中。事实上这些工作在几十年前就已经被研究过了，而且内容要丰富的多。Youtube上有很多Virtual Creature的设计，其中大部分都采用了物理引擎来模拟力学相关的环境。比如要求虚拟生物稳定站立、行走乃至跳高、游泳等。
当前的设计总的来说是很简单的试验品，不过已经展现出遗传算法和神经网络强大的智能行为。未来我想到的改进方向有这样几种。
更现实的输入。本系统中，为了简化系统，个体最重要的输入是最近物品的坐标。这确实有些“作弊”的嫌疑。这之后我想改进这部分设计，引入更加真实的输入。比如单纯给出距离信号，需要生物移动来判断位置（如无线电侧向——事实上当前这个虚拟环境的设计就是受到无线电测向的启发）；或者也可以生物提供双目视觉，让生物主动去寻找和判断目标。
个体间的交互。复杂性科学研究的本质是多个简单元素交互产生的复杂现象，这不单单体现在神经网络通过神经元互联产生的复杂信号模式或者遗传算法通过大量简单变异累计出奇妙的基因，还体现在个体生物之间的交互上。我希望之后能建立起一些生物交互的系统，观察不同独立的虚拟生物个体能否进化出协作和对抗的机制。
更复杂的记忆机制。当前的记忆实现仅仅是将输入和输出连接。从数字电路的思想出发，这已经是时序电路的全部了。但在实际操作过程中，这样的反馈机制只能带来瞬时的记忆，而无法形成长期记忆。我猜让生物自行进化出如内存这样的机制需要很多很多神经元以及很长很复杂的演化路线，但是回报可能也是巨大的。试想一个能侦查并记住一张地图的生物是怎么样的，一定比只能记住三步前撞到墙这种短期事件的生物更加有趣。
自更新的神经网络。当前的进化模式是随机地修改神经网络，也就是达尔文的自然突变模式。但是如果我们把用进废退也加入模型中会怎么样，比如一个神经网络可以产生一些输出来修改自身，会不会产生更有趣的结果？
未来还有很多路要走，尽管这些内容可能几十年前就已经被人玩剩了。但不管怎么说，有趣的东西总是值得一玩的。
