1701066950
1701066951
在遗传算法中元胞自动机规则被编码成0/1序列。每一位对应一种可能的邻域状态组合（图11.2）。
1701066952
1701066953
遗传算法的初始群体为随机产生的元胞自动机规则。为了计算规则的适应度，遗传算法用各种初始状态组合进行测试。遗传算法的适应度为产生出的最终状态正确的比例——正确指的是如果初始开状态占多数，元胞就都为开，初始关状态占多数，元胞就都为关（图11.3）。我们将遗传算法运行了许多代，最终算法设计出了一些表现得相当好的规则。
1701066954
1701066955
1701066956
1701066957
1701066958
▲图11.1 “局部多数投票”元胞自动机的时空图，初始状态为黑色占多数（图片引自米歇尔、克鲁奇菲尔德和达斯的文章《演化执行计算的元胞自动机：最近的研究综述》，收录在《第一届进化计算及其应用国际会议文集》，俄罗斯科学院，1996年）
1701066959
1701066960
1701066961
1701066962
1701066963
▲图11.2 元胞自动机编码为遗传算法个体的方法图示。128种可能的邻域状态组合按固定顺序排列。各邻域状态组合对应的中心元胞更新状态编码为0（关）和1（开）。遗传算法中每个个体有128位，以固定顺序编码更新状态
1701066964
1701066965
1701066966
1701066967
1701066968
▲图11.3 为了计算适应度，用各种随机初始状态对规则进行测试。适应度为规则在运行一定步数后产生出正确答案的比例
1701066969
1701066970
我们通过机器人罗比已经看到，遗传算法演化得出的结果往往无法在其“基因组”层面进行理解。我们在这里演化出的用于多数分类的元胞自动机也是一样。下面是遗传算法演化出的表现最好的基因组之一：
1701066971
1701066972
00000101000001100001010110000111000001110000010000010101010 10111011001000111011100000101000000010111110111111111101101 1101111111
1701066973
1701066974
第1位是邻域全为0时中间元胞的更新状态，第2位是邻域为0000001时中间元胞的更新状态，依次往后。由于邻域状态有128种可能，因此基因组有128位。但光看这些数位是看不出这个规则如何运作，也无法知道为何它进行多数分类时适应度很高。
1701066975
1701066976
图11.4给出了这个规则在两种不同初始状态下的行为：分别为（a）黑色元胞占多数，（b）白色元胞占多数。可以看到在两种情形下最终行为都是正确的——（a）变成了全黑，（b）变成了全白。在得到最终状态组合的过程中，元胞之间似乎在协同处理信息，以达到正确的最终状态。在这个过程中的图样很有意思，它们到底意味着什么呢？
1701066977
1701066978
1701066979
1701066980
1701066981
▲图11.4 演化出的表现最好的元胞自动机规则之一执行多数分类任务时的时空行为。在图（a）中，初始状态中黑色元胞占多数，元胞自动机迭代运行后全部变成了黑色。在图（b）中，初始状态中白色元胞占多数，元胞自动机迭代运行后全部变成了白色（图片引自米歇尔、克鲁奇菲尔德和达斯的文章《演化执行计算的元胞自动机：最近的研究综述》，收录在《第一届进化计算及其应用国际会议文集》，俄罗斯科学院，1996年）
1701066982
1701066983
我们花了很多时间盯着图11.4这样的图看，想知道到底发生了什么。幸运的是，伯克利的物理学家克鲁奇菲尔德碰巧访问了圣塔菲研究所，并对此产生了兴趣。他和他的同事正好发展了合适的概念能帮助我们理解这些图样是如何完成计算的。
1701066984
1701066985
图11.4中有三种类型的图样：全黑、全白以及类似于棋盘格的黑白交替（图11.4分辨率较低，所以看上去像灰色）。正是这种棋盘格图样传递了局部区域黑白元胞密度的信息。
1701066986
1701066987
同遗传算法为机器人罗比演化的策略一样，这个元胞自动机的策略也相当聪明。图11.5是我对图11.4（a）做的标记。大部分为黑色和大部分为白色的区域很快就变成了全黑和全白。注意当黑色区域在左边而白色区域在右边时，中间的分界线总是垂直的。但如果白色区域在左边而黑色区域在右边，则会形成由黑白元胞相间组成的棋盘格图样三角形。如果把元胞自动机的两头回绕连在一起，就能看到三角形的环绕效果。
1701066988
1701066989
棋盘格区域的A边和B边以同样的速度扩展（即向两边覆盖同样的宽度）。A线向西南延伸，直到碰到垂直界线。B线则刚好避开了从另一边与这条垂直界线相撞。这表明A线的延伸长度要短一些，也就是说，A线左边的白色区域要小于B线右边的黑色区域。碰撞后，A线消失了，而黑色区域则得以继续扩展。在三角形底部的角上，B线和C线消失了，全部元胞格子都变成了黑色，从而得到了正确的状态组合。
1701066990
1701066991
1701066992
1701066993
1701066994
▲图11.5 标记了重要特征后的图11.4（a）
1701066995
1701066996
如果我们将这些图样当作是进行计算，那么垂直界线和棋盘格区域就可以视为信号。这些信号通过元胞的局部互动而产生和传播。信号使得元胞自动机能作为一个整体判断相邻的大片黑白区域哪个更大，截去较小的区域，并使较大的区域得以扩展。
1701066997
1701066998
这些信号就是图11.1中的局部多数投票元胞自动机与图11.5中的元胞自动机的主要区别。前面提到，前者的黑色和白色区域之间没有信息沟通，因而也无法得知两者谁占多数。而对于后者，棋盘格和垂直边界产生的信号则可以进行这样的信息传递，通过信号之间的相互作用对传递的信息进行处理，从而得出答案。
1701066999