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次任务的平均得分，每次的罐子分布都不一样。
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）将产生的两个子代个体放入新群体中。