遗传算法（二）—进化的罗比

拆书《复杂》

易拉罐清扫机器人的遗传算法。

工作原理，基础内容同遗传算法（一），这里具体实例的工作原理。

1.生成初始群体。初始群体有200个随机个体（策略）。

每个个体策略有243个“基因”。每个基因是一个介于0和6之间的数字，代表一次动作（0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子，6=随机移动）。在初始群体中，基因都随机设定。程序中用一个伪随机数发生器来进行各种随机选择。

重复后面的步骤1000次。

2.计算群体中每个个体的适应度。在程序中，是通过让罗比执行100次不同的清扫任务来确定策略的适应度。每次将罗比置于位置（0，0），随机撒一些易拉罐（每个格子至多1个易拉罐，格子有易拉罐的概率是50%）。然后让罗比根据策略在每次任务中执行200个动作。罗比的得分就是策略执行各任务的分数。策略的适应度是执行100次任务的平均得分，每次的罐子分部都不一样。

3.进化。让当前群体进化，产生下一代群体。即重复以下步骤，直到新群体有200个个体。

（a）根据适应度随机选择出一对A和B作为父母。策略的适应度越高，被选中的概率则越大。

（b）父母交配产生两个子代个体。随机选择一个位置将两个数字串截断；将A的前段和B的后段合在一起形成一个子代个体，将A的后段与B的前段个体合在一起形成另一个子代个体。

（c）让子代个体以很小的概率产生变异。以小概率选出1个或几个数，用0到6之间的随机数替换。

（d）将产生的两个子代个体放入新群体中。

4.新群体产生200个个体后，回到第2步，对新一代群体进行处理。

神奇的是，从200个随机的策略出发，遗传算法就能产生出让罗比顺利执行任务的策略。

种群规模（200）、迭代次数（1000）、罗比在一次任务中的动作数量（200）以及计算适应度的任务数量(200)都是随意设定的。用其他参数也能产生出好的策略。