1701066624
GA根据内建知识知道是情形2。通过查询策略表可以得知位置2上的行动是往东移动。罗比往东移动一格，然后又观察周围情形；GA再次查询表上的相应行动，反复进行。
1701066625
1701066626
我的GA是用C语言写的。这里我不写出具体程序，只解释其工作原理。
1701066627
1701066628
1.生成初始群体。初始群体有200个随机个体（策略）。
1701066629
1701066630
图9.3是一个随机群体示意图。每个个体策略有243个“基因”。每个基因是一个介于0和6之间的数字，代表一次动作（0=向北移动，1=向南移动，2=向东移动，3=向西移动，4=不动，5=捡拾罐子， ；6=随机移动）。在初始群体中，基因都随机设定。程序中用一个伪随机数发生器来进行各种随机选择。
1701066631
1701066632
重复后面的步骤1000次。
1701066633
1701066634
1701066635
1701066636
1701066637
▲图9.3 随机初始群体。每个个体由243个数字组成，取值介于0到6之间，每个数字编码一个动作。数字的位置决定它对应哪种情形
1701066638
1701066639
2.计算群体中每个个体的适应度。在我的程序中，是通过让罗比执行100次不同的清扫任务来确定策略的适应度。每次将罗比置于位置（0，0），随机撒一些易拉罐（每个格子至多1个易拉罐，格子有易拉罐的概率是50%）。然后让罗比根据策略在每次任务中执行200个动作。罗比的得分就是策略执行各任务的分数。策略的适应度是执行100次任务的平均得分，每次的罐子分布都不一样。
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