- 飞行中
- 到达目标
- 坠毁
- 上一代的最佳飞行
- 到达目标
- 坠毁
遗传算法演练场
遗传算法解决问题的方式,就像进化塑造生物一样:尝试许多随机答案,保留较好的那些,把它们混合,再随机改动几处,然后不断重复。在这里,答案就是火箭。每枚火箭只按照一串随机推力飞行,别无其他,所以一开始它们漫无目的地乱翻乱滚。按下“运行”,看种群一代又一代地进步,直到大多数火箭绕过墙壁飞到目标,而从来没有人告诉它们该往哪里飞。 按下“运行”,看一群火箭努力飞向绿色目标。每枚火箭只按照自己的基因飞行,基因是一串小小的推力,飞行中的每个时刻对应一个。每次飞行结束后,飞得最近的火箭,尤其是已经到达的火箭,最有可能成为下一代的父母;它们的基因被混合,其中少数会被随机改变。“下一代”会跳过本次飞行的剩余部分。在场地上拖动可以画墙,点击墙可以将其删除。
它是如何运作的
- 选择障碍,或在场地上拖动画出你自己的墙,并设置种群规模、变异率和寿命。
- 按下“运行”,观看每一代的飞行;“下一代”会跳过本次飞行的剩余部分。
- 通过数据卡片和图表追踪到达目标的比例,并尝试其他变异率和选择方式。
火箭如何进化
每枚火箭都携带基因:飞行中的每个时刻对应一个小推力。第一代的基因是随机的。飞行结束后,每枚火箭都会得到一个适应度分数:越早到达分数越高;其次,最终位置离目标越近分数越高;如果坠毁,分数除以十。下一代的父母是随机挑选的,但适应度越高的火箭越有可能被选中。每个子代的前一部分基因来自一个亲本,其余部分来自另一个亲本,还有少数基因会被随机推力替换:这就是变异。经过一代又一代,好的飞行方案不断传播并改进。
各项设置的作用
种群越大,一次就能探索越多的飞行方案,也越不容易陷入困境,但每一代所需的时间更长。变异率在探索与保留有效方案之间取得平衡:没有变异,种群很快就会耗尽新点子;变异太多,它遗忘好飞行的速度会比找到它们还快。轮盘赌选择按适应度的比例挑选父母,而锦标赛则从三枚随机火箭中挑出最好的一枚,这种方式对适应度如何缩放不那么敏感。精英保留会把最佳火箭原封不动地复制到下一代,因此最佳结果永远不会变差。
常见问题
为什么火箭会卡在交错的墙壁后面?
它们的适应度衡量的是到目标的直线距离,所以一枚撞上目标下方那堵墙的火箭,得分反而比一枚飞离目标去寻找缺口的火箭更高。种群于是堆积在这条死胡同里,也就是局部最优。更大的种群、更多的变异或锦标赛选择可以帮助它逃脱;如果适应度衡量的是绕过墙壁的真实路线,就能避开这个陷阱。选择一个好的适应度函数,是使用遗传算法时最难的部分。
自然界中的进化就是这样运作的吗?
大体上是:由变异和重组带来的差异、基因的遗传以及对最适者的选择,正是达尔文理论的要素。不过两者的差别也很大。自然界没有目标,也没有适应度公式,只有生存和繁殖;而且真实的基因组是通过发育构建身体,而不是列出一串动作。
遗传算法有什么用途?
适用于可能答案的空间极其庞大、而给候选答案打分又很容易的问题:设计天线、机翼和汽车零件的形状,安排时间表,调整其他算法的参数,设计神经网络,以及创作艺术和游戏策略。NASA 于 2006 年用在 ST5 卫星上的进化天线就是一个著名的例子。
为什么最佳火箭在下一代有时会飞得更差?
没有精英保留时,最佳火箭不会被复制:它的基因只能与其他基因混合、并可能发生变异后才得以保留,因此下一代可能会失去它那条完全相同的飞行路线。开启精英保留后,最佳火箭会原封不动地保留下来,最佳结果永远不会变差。
会有任何数据发送到服务器吗?
不会。火箭在你的浏览器中飞行和进化,你画的墙保存在这个浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器