1701066930
复杂 [:1701064783]
1701066931
第11章 粒子计算[161]
1701066932
1701066933
1989年我偶然读到物理学家帕卡德（Norman Packard）的一篇文章， [162] 写的是用遗传算法设计元胞自动机规则。我一下就被吸引住了，想自己也试试。当时因为繁忙，无暇顾及（我在写博士论文），但这个想法一直留在我的脑海里。几年后，论文完成了，我也在圣塔菲研究所找到了职位，终于可以有时间深入研究这个问题了。有个叫赫拉贝尔（Peter Hraber）的本科生当时在研究所逗留，想找点事情做，我就把他招进来协助我研究这个课题。很快一个叫达斯（Rajarshi Das）的研究生也加入我们，他当时在独立研究类似的课题。
1701066934
1701066935
类似于帕卡德的思想，我们想用遗传算法演化出能执行所谓的“多数分类 [163] （majority classification）”任务的元胞自动机规则。这个任务很简单：元胞自动机要能区分初始状态中是开状态还是关状态占多数。如果是开状态占多数，最后所有元胞就应当都变成开状态。同样，如果是关状态占多数，最后所有元胞就应当都变成关状态。（如果初始状态中开状态和关状态的数量一样多，就没有答案，但是可以让元胞的数量为奇数来避免这种可能。）多数分类任务有点类似于选举，是在大家都只知道最近邻居的政治观点的情况下预测两个候选人谁会赢。
1701066936
1701066937
多数分类问题对冯·诺依曼结构的计算机而言是小菜一碟。CPU只需要分别对初始状态中的开状态和关状态进行计数，同时在内存中记录计数值就可以了。计数结束后，从内存中读取数值进行比较，然后根据结果将元胞状态都设成开或关。冯·诺依曼结构的计算机可以轻松实现这个工作，因为它有随机存取存储器可以存储初始状态和中间值，还有中央处理器可以计数，进行最后的比较，以及将状态重设。
1701066938
1701066939
而元胞自动机则没有CPU和内存可以用来计数。它只有一个一个的元胞，每个元胞除了自己的状态就只知道相邻元胞的状态。这种情形其实也是对许多实际系统的理想化。例如，在大脑中，神经元只与其他少数神经元有连接，而神经元必须决定是否激发，以及以何种强度激发，使得大量神经元的整体激发模式能表示特定的感知输入。类似的，第12章我们还会看到，蚂蚁必须根据与其他少量蚂蚁的交互来决定做什么事情，让蚁群整体能够受益。
1701066940
1701066941
因此，基本上很难设计出让所有元胞能协同决策的元胞自动机。赫拉贝尔和我想知道遗传算法是不是能解决这个设计问题。
1701066942
1701066943
借鉴帕卡德的工作，我们使用一维元胞自动机，每个元胞与相邻的6个元胞相连，这样元胞的邻域中就有7个元胞（包括自己）。
1701066944
1701066945
你可以先想一下如何给元胞自动机设计规则，让它能进行多数分类。
1701066946
1701066947
一个合理的想法是：“元胞应当变成邻域中当前占多数的状态。”这就好像根据你自己和邻居的多数意见来预测哪个候选人会当选。然而，这个“局部多数投票”元胞自动机并不能完成任务，图11.1说明了这一点。初始状态中黑色元胞占多数，然后根据局部多数投票规则运行了200步。可以看到元胞自动机很快变成黑白区域相间，然后就不再变化。黑白区域的边界两边的元胞邻域分别是黑白占多数。最后的状态组合中既有黑色元胞也有白色元胞，没有得到想要的结果。其中的问题是，根据这个规则，区域之间无法相互交流信息，因此它们无法得知自己是否是多数。
1701066948
1701066949
这个规则的设计并不是那么显而易见，因此依照第9章的做法，我们用遗传算法来试一下是不是能产生出有用的规则。
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