介绍
最近在看一本有趣的书，书名叫《复杂》，书中介绍了一种“遗传算法” （genetic algorithm）让我产生了极大兴趣，刚读到一半就迫不及待的想要自己亲自试一试，然后熬了几个晚上终于把它实现了，在这里分享一下其中的乐趣。
这是一个模拟生物遗传进化的程序，假设机器人罗比的世界是一个10*10的网格，网格四周是墙，网格中间随机分布着一些易拉罐（每个格子最多有1个易拉罐）， 罗比的工作就是清理这些易拉罐。
每次清扫任务罗比可以执行若干个动作，动作可以是以下7种：向北移动，向南移动，向西移动，向东移动，不动，捡拾罐子，随机移动。 每个动作都会受到奖励或惩罚，如果撞墙则扣5分并弹回原来的格子，如果执行捡拾罐子的动作但是地上却没有罐子则扣1分， 如果成功捡到一个罐子加10分，最后的得分称作罗比本次任务的适应度，执行若干次任务后会得到一个平均的适应度，记为当前个体的适应度， 适应度越高说明罗比越聪明。
罗比想要获得高的得分，就必须尽可能多的收集罐子，别撞墙，没罐子的时候别去捡。
这个问题很简单，人工为罗比设计一个好策略不是很难，但是我们没有这么做，而是使用遗传算法，让计算机替我们进化出来一个好策略。
首先，可以点击下面“执行任务”按钮，看看罗比是如何执行任务的，有个感性认识，这是我手工定制的一个策略，不是很聪明，也不是太笨，至少不会撞墙和瞎捡罐子。
任务模拟
当前罗比的策略
| 情形ID | 情形 | 执行动作 |
|---|---|---|
| 北,南,东,西,中 | ||
当前罗比的基因
动画演示
第 步， 适应度：， 情形ID（基因序号）：
动作： ()， 结果：
|
|
算法原理
- 第一步：制定策略
-
策略是一组规则，规则给出了在各种情形下应当采取的行动。对于罗比，它面对的情形就是它所看到的：当前格子以及东、南、西、北四个格子中的情况。 在各种情形下怎么做呢？罗比有7种选择：向北移动、向南移动、向西移动、向东移动、不动、捡拾罐子、随机移动。因此，罗比的策略可以写成它可能 遇到的所有情形以及面对每种情形应当采取的行动。
有多少种情形呢？罗比看到5个格子（东、西、南、北、中），每个格子可以是空，罐和墙，这样就有 3^5 = 243种可能（其实没有这么多，因为有 许多不可能的情形，比如四面都是墙，不过，我们不想费劲找出所有不可能情形，只要知道其中一些永远也不可能遇到就行了）。
要知道下一步怎么做，罗比只需查看策略表（参考上面的例子），查到对应的行动是往西移动，就往西移动（有可能撞墙），查到对应的行动是捡罐子 ，就执行捡罐子（有可能什么都捡不到）。遗传算法的目的就是让计算机自己进化出一个好的策略。
- 第二步，生成初始群体
- 先生成初始群体，群体里面有200个（参数可调）随机个体，每个个体代表一种策略，每种策略有243个“基因”，每个基因是介于0-6之间的数字， 代表一次动作（0=北移，1=南移，2=东移，3=西移，4=不动，5=捡拾罐子，6=随机移动），可以用一个数组表示，在初始群体中，基因都是用伪随机数发生器来随机设定。
PS:接下来我们就要利用初始群体进行进化，每一次进化生成新的后代群体，后代群体会继承上一代群体中的优秀基因，不断循环往复，使罗比变得越来越聪明。
- 第三步，计算群体中每个个体的适应度。
-
我们让罗比执行100次（参数可调）不同的清扫任务，每执行一次任务会得出一个本次任务的适应度，100次任务完成后会得出一个平均适应度，记为 这个个体（策略）的适应度。
每次任务开始时，我们将罗比至于位置（0,0），随机撒一些易拉罐（每个格子之多1个罐子，格子有易拉罐的概率是50%）。然后让罗比根据策略在每次任务 中执行200个（参数可调）动作，计算出本次任务的适应度，适应度最高可能是500左右（50个左右的罐子全部捡起），最低是-1000，意味着不停的撞墙 （撞了200次也是醉了）。
- 第四步，进化
-
让当前群体进化，产生下一代群体，即重复以下步骤，直到新群体有200个个体：
- 根据适应度随机选择出一对个体A和B作为父母。策略的适应度越高，被选中的概率越大。
- 父母交配产生两个子代个体。随机选择一个位置将两个父代的基因截断；将A的前段与B的后段合在一起生成一个子代个体，将A的后段与B的前段合在一起 形成另一个子代个体。
- 让子代个体以很小的概率产生变异。以小概率选出1个或几个数，用0到6之间的随机数替换。
- 将产生的两个子代个体放入新群体中。
- 第五步，新一代种群继续进化。
-
新群体产生200个个体后，回到第三步，对新一代种群进行处理。
算法演示
以下就是遗传算法的演示，需要注意的是，想要得出满意结果，必须有足够的个体数，要进化足够多代，所以计算量非常大， 相当消耗浏览器资源，长时间运行以后浏览器可能卡死，大家把数值调小一点，理解一下整个过程就行了。
《复杂》的作者在书中说她用C语言实现的这个算法，她的程序采用200个个体为一个群体，计算平均适应度要执行200次 任务，每次任务走200步，这样连续进化1000代得出的结果，最聪明的罗比适应度能够达到480多，比她人工为罗比设计的 策略的得分（440多）还要高，说明遗传算法经常能够解决人类依靠正常逻辑无法解决的问题，是的，虽然很多依靠遗传算法 得到的结果让人无法理解，但它就是管用。
我粗略算了一下，如果我用作者在书中的参数在浏览器上跑这个程序的话，在不死机不间断的情况下，我这个小破笔记本 至少要230多天的时间（也可能是算法优化的不到位）才能进化完成，所以我修改了一些参数让运算量小一些，至少可以看到每一代的罗比都是进步的。
进度
进度信息
进度细节 （适应度后面跟着的是被选中的概率）
第代种群基因：
- [],
最终进化基因
最后，说两句编程中总结的小经验，一个是最初实现算法时不论是循环每一代还是计算平均适应度之类，我用的都是for循环， 结果一运行就发现页面处于卡死状态，DOM不能实时更新显示结果，必须要等所有运算结束才一次性输出结果，我才恍然大悟这 种方式是同步阻塞模式的，必须一件事干完才能干另一件事，效率很低，应该使用JS擅长的异步非阻塞模式才对（一定是最近PHP写多了 把这一点都忘了），于是我把这些for循环都改成了window.setInterval()，用一个简单的事件触发机制进行消息通知，程序 执行速度瞬间提升，DOM也可以实时更新了。接下来我又遇到了新问题，因为我开始用的都是window.setInterval(fn, 0), 注意那个0 - 也就是说执行每个fn之间没有任何时间间隔，再加上是多层嵌套使用setInterval，如果运算量一大，浏览器依然会卡死， 这就好比一个生产线能同时生产100件产品，但是如果你硬让它同时生产1000件，那带来的后果就是每一件产品的生产时间都 是原来的10倍，随着后续的任务不断添加进来，执行队列会越积越多，程序执行时间也就无限延长了，这就叫欲速则不达。 所以我的解决办法就是增加延迟时间，越是外围的循环间隔时间就应该越长，最长的是生成一个种群所有新个体的循环（几秒到几分钟执行一次）， 其次是循环每一个个体，得到2个子代（零点几秒到1秒执行一次），最里面是一个个体执行所有任务计算平均适应度的循环（我依旧设置为0--同时启动）， 其实具体设置多少合适我没有找到准确的答案，只是凭经验设置，时间设的短了会导致任务不断堆积卡死，时间 设的长了又觉得浪费资源不甘心，感觉这还是门学问。
后来因为懒得写DOM的相关更新的代码，我又包了一层angularJs的皮，setInterval也改为$interval，因为主要目的是实现算法， 所以作用域控制器啥的设置的比较乱，请见谅。
第二点，我最初实现遗传时采用了一个偷懒的办法，每次就把得分最高的两个个体作为下一代的父母，乍一看没啥问题，选取最优秀的 个体进行繁殖嘛，那些劣等的个体基因就丢掉不要了，而且这样做头几代适应度增长的特快，但是再往后几代适应度就不再增长了， 出现了停滞甚至倒退，开始很困惑，后来从下一代的基因当中我发现了问题，原因是什么呢？我卖个关子，大家可以自己想一下。 反正最终的结果是我老老实实的改为按照概率来选取个体作为下一代的父母，优秀的个体不一定能被选中，而是被选中的概率比较大。
能看到这里不容易，最后，非常感谢你的关注！