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)将产生的两个子代个体放入新群体中。
[
上一页 ]
[ :1.7010666e+09 ]
[
下一页 ]