1701066640
1701066641
3.进化。让当前群体进化，产生出下一代群体。即重复以下步骤，直到新群体有200个个体。
1701066642
1701066643
（a）根据适应度随机选择出一对个体A和B作为父母。策略的适应度越高，被选中的概率则越大。
1701066644
1701066645
（b）父母交配产生两个子代个体。随机选择一个位置将两个数字串截断；将A的前段与B的后段合在一起形成一个子代个体，将A的后段与B的前段个体合在一起形成另一个子代个体。
1701066646
1701066647
（c）让子代个体以很小的概率产生变异。以小概率选出1个或几个数，用0到6的随机数替换。
1701066648
1701066649
（d）将产生的两个子代个体放入新群体中。
1701066650
1701066651
4.新群体产生200个个体后，回到第2步，对新一代群体进行处理。
1701066652
1701066653
神奇的是，从200个随机的策略出发，遗传算法就能产生出让罗比顺利执行任务的策略。
1701066654
1701066655
种群规模（200）、迭代次数（1000）、罗比在一次任务中的动作数量（200）以及计算适应度的任务数量（200）都是我设定的，有些随意。用其他参数也能产生出好的策略。
1701066656
1701066657
你现在肯定很想知道遗传算法得出的结果。不过，我得向你坦白，在运行程序之前我还是克服了懒惰，自己设计了一个“聪明的”策略，这样我就能知道GA和我比起来谁干得更好。我为罗比设计的策略是：“如果当前位置有罐子，就捡起来。否则，如果旁边格子有罐子，就移过去。（如果有几个罐子，预先设定罗比向哪个移动。）否则，随机选择一个方向移动。”
1701066658
1701066659
这个策略其实不是很聪明，罗比有可能会围着空格子绕圈子，总也找不到易拉罐。
1701066660
1701066661
我用10000个清扫任务测试了这个策略，结果（每个任务的）平均分约为346。每个任务最初有大约50%的格子有罐子，也就是50个易拉罐，因此最高可能的分数约为500，这样看我的策略还不是很接近最优。
1701066662
1701066663
GA能有这么好的成绩吗？会不会更好？运行一下就知道了。取最后一代中适应度最高的个体，也用10000个不同的任务进行测试。结果平均分约为483——几乎是最优了！
1701066664
1701066665
复杂 [:1701064774]
1701066666
GA演化的策略是如何解决这个问题的
1701066667
1701066668
问题是这个策略是如何做到的？它为什么能比我的策略做得更好？GA又是如何将它演化出来的？
1701066669
1701066670
将我的策略记为M, GA生成的策略记为G。下面是这两个策略的基因组。
1701066671
1701066672
M：6563536562523532526563536561513531512523532521513 53151656353656252353252656353656050353050252353252050 3530501513531512523532521513531510503530502523532520503 5305065635356252353252656353656151353151252353252151353 151656353656252353252656353454
1701066673
1701066674
G：254355153256235251056355461151336154151034156110550 1500520302562561322523503251120523330540552312550513361 541506652641502665060122644536056315202564310543546324 0435033415325025325135235204515013015621343625235322313 5051260513356201524514343432
1701066675
1701066676
仅仅从策略的基因组看不出其中的运作。我们可以知道其中一些基因的意义，例如当前位置有罐子的情形，对第2种情形（“空空空空罐”），两个策略的动作都是5（清扫罐子）。M对这种情形总是动作5，但G并不总是这样。例如下面这种情形：
1701066677
1701066678
1701066679
1701066680
1701066681
动作就是3（往西移动），罗比在这种情形下不会捡罐子。这不太好，不过G总体上还是比M好。
1701066682
1701066683
关键之处不在于单个的基因，而在于各个基因之间的相互作用，就像真正的基因一样。而且同真正的基因一样，很难确定各种相互作用是如何影响整体上的行为或适应度。
1701066684
1701066685
相较于观察一个策略的基因，观察其具体的行为——也就是它们的表型——会更有意义。我编了一个程序来演示罗比在采用某个给定策略时的行动，然后对罗比在采用策略M和策略G时的行为进行观察。我发现这两个策略在许多情形中的行为类似，但策略G有两个小技巧，让它比策略M表现得更好。
1701066686
1701066687
首先来看看当前位置和四周都没有罐子的情形。如果罗比采用策略M，它就会随机选择一个方向移动。但如果它采用的是策略G，它就会往东移动，直到遇到墙为止。然后它会往北移动，就这样逆时针围着格子边缘移动，直到发现罐子。图9.4可以看到罗比的轨迹（虚线）。
1701066688
1701066689
这种围着绕圈的策略不仅让罗比不会撞墙（如果用策略M，随机移动时有可能会撞墙），而且搜索罐子的效率也比随机移动要高。