1701066590
显然，罗比尽可能地多收集罐子，别撞墙，没罐子的时候别去捡，得到的分数就最高。
1701066591
1701066592
这个问题很简单，人工为罗比设计一个好策略可能也不是很难。不过，有了遗传算法我们就可以什么也不用干，我们只需要等着计算机替我们进化出来。下面我们用遗传算法来为罗比进化出一个好策略。
1701066593
1701066594
第1步是搞清楚我们想要进化的到底是什么。也就是说，策略具体指的是什么？一般来说，策略指的是一组规则，规则给出了在各种情形下你应当采取的行动。对于罗比，它面对的“情形”就是它看到的：当前格子以及东南西北四个格子中的情况。对于“在各种情形下怎么做”的问题，罗比有7种可能选择：北移、南移、东移、西移、随机移动、不动、收集罐子。因此，罗比的策略可以写成它可能遇到的所有情形以及面对每种情形应当采取的行动。
1701066595
1701066596
有多少种可能的情形呢？罗比可以看到5个格子（当前格子、东、南、西、北），每个格子可以标为空、罐和墙。这样就有243种可能情形。 [142] 其实还没有这么多，因为有许多不可能的情形，例如当前位置不可能是墙，也不可能四面都是墙，等等。不过，因为我们很懒，不想费劲找出所有不可能的情形，因此我们会列出所有243种情形，只要知道其中一些永远也不会遇到就行了。
1701066597
1701066598
表9-1是一个策略的例子——只是策略的局部，完整策略太长了，不方便列出来。
1701066599
1701066600
表9 1一个策略的例子
1701066601
1701066602
1701066603
1701066604
1701066605
罗比在图9.2中的情形是：
1701066606
1701066607
1701066608
1701066609
1701066610
要知道下一步怎么做，罗比只需要查看策略表，查到对应的行动是往西移动。因此它往西移动一格，结果一头撞到墙上。
1701066611
1701066612
我没说这是一个好策略。寻找好策略不关我的事；这事归遗传算法管。
1701066613
1701066614
我写了一个遗传算法程序来进化罗比的策略。算法中，群体中每个个体都是一个策略——与各种可能情形相对应的行动列表。也就是说，对于表9—1中的策略，GA用来演化的个体就是最右侧243个行动依次列出的列表：
1701066615
1701066616
1701066617
1701066618
1701066619
字符串中第1个行动（这里是向北移动）对应第1种情形（“空空空空空”），第2个行动（这里是向东移动）对应第2种情形（“空空空空罐”），依次往后。这样就不用明确列出与动作对应的情形；GA记得各情形的排列顺序。例如，假设罗比观察到情形如下：
1701066620
1701066621
1701066622
1701066623
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次任务的平均得分，每次的罐子分布都不一样。