在线运行例子
https://demongodyy.github.io/GA-Robi/
代码仓库
https://github.com/demongodYY/GA-Robi
偷懒的大自然
你有没有想过，你为什么是你现在的样子？这个世界又是谁设计并构建出来的呢？达尔文的进化论给予我们看待这个世界的视角：物竞天择，适者生存。大自然有种神奇的力量，它只是简单地制定了生存的规则，而让万物自由地生长、进化，一代又一代地演变，就逐渐构建出了我们当今的世界。
写程序同样是一个“构建世界”的过程，通过每一行代码来描述出各种事物并在计算机的世界中运行。对于简单地问题，我们可以编写具体的指令来运行。但是，当问题超过一定复杂程度的时候，编写海量地代码指令来描述每一处细节，就显得比较困难了。比如说想要编写一个自动打扫屋子的机器人，所面临的情况就是千变万化的，如果要为每一种可能性都去编写指令，会显得非常复杂。我们能不能“偷下懒”，只写出一些很少的代码，让代码帮我们自动“生成”机器人最优的打扫规则呢？
遗传算法
借鉴达尔文的进化论和孟德尔的遗传学说，在计算机中我们也可以设计出一些算法，通过适者生存的方式，帮助我们慢慢找出规则中优秀的“基因”，通过“遗传”地方式保留下来，从而找寻到一些问题的最优解。
实际上，遗传算法已经有了很多有趣的应用，诸如寻路问题，8 数码问题，囚犯困境，动作控制，找圆心问题（在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心），TSP 问题，生产调度问题，人工生命模拟等。
而在这次工作坊中，我们可以建立一个小小的“清扫垃圾机器人”的游戏，来看看遗传算法的究竟。
游戏规则
假定有一个机器人叫做 Robi，它存在的世界是由一个 10x10 共 100 个的方格组成的围墙中。在这些方格中，会随机有 50%的几率有一个垃圾。而 Robi 的任务就是尽可能多的捡起这些垃圾。
游戏的规则如下：
- Robi 的动作一共有 6 种：上移、下移、左移、右移、随机移动、捡垃圾。
- Robi 每一步只能执行上述动作中的一种，一共可以走 200 步。
Robi 每次得分规则如下：
- 如果在有垃圾的地方进行了“捡垃圾”的动作，就 +10 分，如果没在没有垃圾的地方“捡垃圾”就 -1 分。
- 如果移动撞墙了，就 -5 分并弹回原地。
- 其他情况分数不变。
可以看出，在执行 200 步的情况下，最低分是 -1000 分（一直撞墙），最高分是 500 分（所有垃圾都捡到了）。
最后， Robi 可以看见上下左右以及当前总共 5 个格子的情况。情况分 3 种：有垃圾、空格子、墙。也就是说 Robi 每行动一步时所面临的情况有 3^5 = 243 种（简单起见，包括了脚底下也踩着墙这种不可能出现的情况）。
我们所要做的就是给这 243 种情况设定规则，让 Robi 能在游戏中得到尽可能高的分数。
工作坊流程
- 介绍游戏基本规则，及简单运行方式，在这可能会涉及到一些浅显地“数字化”的过程理解。
- 尝试编写自己的规则来尽可能地优化算法，获取更高的分数
- 讲解遗传算法原理，对比遗传算法生成出来的规则与人为优化的规则。
- 或许可以开下脑洞，比如自然是不是一段算法代码而已？
谁能参加
理解遗传算法本身更是不需要任何编程知识，拥有编程技能可能更能动手试验一下，对于了解游戏规则本身更有帮助，所以：
- 如果你是程序员或者能看懂 js 代码，欢迎带上电脑来亲手编写代码试验一下，这样更能感受到不一样。
- 如果你对写程序并不熟悉，也可以来思考，这个问题并不需要太高深的写代码的技巧，更重要地是讨论和思考的过程，你可以在现场 找一名程序员与 TA 结对编程
得到什么
- 你将理解如何将现实游戏的规则“数字化”到代码中进行模拟。
- 你将理解或亲手实现一个算法，它会通过遗传迭代，自动生成出符合游戏规则的最优方案。
- 或许你能在这个过程中感受到人与自然的关系？
