二元元胞自动机中涌现出自复制层级结构

导语

马克吐温曾说：历史不会重演，但总有惊人的相似。能够自复制，无疑是复杂系统的必要特征之一。近日的 arXiv 论文“Self-Replicating Hierarchical Structures Emerge in a Binary Cellular Automaton”，通过一个简单环境下涌现出的自复制现象，首次发现了能够在二元元胞自动机（binary cellular automata）上自复制的规则集合。这一发现通过对人工生命的研究，揭示了复杂系统中自适应、自复制等现象涌现的规律。

研究领域：元胞自动机，自复制，自适应，层级机构，涌现

郭瑞东 | 作者

苑明理 | 审校

论文题目：

Self-Replicating Hierarchical Structures Emerge in a Binary Cellular Automaton

论文地址：

https://arxiv.org/abs/2305.19504

1. 元胞自动机的起源

元胞自动机的研究起源于冯·诺伊曼，他于上世纪40年代的手稿《自复制自动机理论》，指出复杂科学中经久不息的关键问题，即自适应、自复制的模式背后，有着怎样的物质与信息基础？回答该问题，将有助于基于最简规则去构建一个复杂系统。

集智俱乐部资深粉丝“东方和尚”将冯·诺伊曼的《自复制自动机理论》全书第一部分翻译成中文，张江做了详细点评。我们将其整理成“冯·诺依曼自动机器理论”系列文章。

冯·诺依曼的遗产：寻找人工生命的理论根源

探寻计算的“原力”

神经网络与图灵机的复杂度博弈

　　人工智能如何掷骰子——三种概率理论

　　大数之道——人脑与电脑的对比

　　复杂度阈值与概率论中“漏洞”

自指机器的奥秘

基于元胞自动机，1970年康威提出生命游戏，成为了研究人工生命的典型工具。生命游戏在二维网格上展开，演化基于九宫格中的局部信息。只需遵循简单规则，却可在宏观产生或周期变化、或随机出现的图案。更有趣的是，有些图案会呈现自相似等复杂特征。由于生命游戏的规则简单，普通人无需复杂编程，即可给定规则与初始状态，之后扮演这个二维格子宇宙中的上帝，观察系统能否演化出有趣的模式。

自动化迭代进行上述的模拟过程，就是前文所述研究者做的事。当规则得以组合，规则组合的指数级增长使得穷举法变得不可行。通过遗传算法，可以在给定的优化函数下，让规则集合通过随机改变，实现有方向性地探索。而在此过程中，研究者意外发现了自朗顿于1986年发现具有自复制特征的“蚂蚁”后，第二个具有自复制特征的规则。该规则被称为“异常者”（outlier）。

图1：朗顿的蚂蚁前200步演化动图

2. 自复制元胞自动机

在遗传算法中，适应性函数制定了搜索目标。该研究给出的目标，是让演化过程尽可能地开放，即奖励那些产生与之前出现的时空模式不同的新模式的规则。尽管开放性与自复制常常被视为复杂系统中联系紧密的两个特征，但在该研究中，自复制从没有作为一个明确的目标，只是在寻找具有开放演化的规则中偶然间涌现。

该研究发现的规则，其产生的自复制能力具有层次性，既包含局部特征，也包含更大尺度上的模式。图2a中是自复制的模式本身，图2b展示了演化后，网格中出现多个自复制的模块，而在图2c中展示的更大尺度上，近似随机的图案边缘，出现了多个图2b这样自相似的图案，缩放后可以看到更小尺度的自复制模式。图3展示了“异常者”这一规则的具体表现，其中黑框里及黑框270°旋转后的情况下，九宫格中间的点会呈现活的状态。

图2：在初始条件稀疏时，异常者规则演化的步骤

图3：异常者规则示意图

3. 什么决定了二维网格中的演化进程

除了演化规则，决定二维宇宙命运的，还有初始条件，其中最开始有多少比例的方格被点亮（密度）是一个关键因素。当初始环境中小于2%的格子点亮时，基于“异常者”规则演化的结果，大多是一个空荡荡的二维空间；而当初始环境中点亮的格子比例超过15%时，演化的结果大多是近似随机的图案，见图4。只有在初始密度处于2%~15%之间时，才可能产生自复制现象。

图4：在初始密度较大时，演化产生的近似随机图案。

图5展示了演化过程的动力学，其中C2的模式可以看成是种子，之后每隔143步，就会再次出现，例如第145、288、391等步中，都出现了一个或多个这样的模式。这在动力学中被称为吸引子。该图中的种子模式不具备左右对称性，但可以通过旋转重现，即具备旋转对称性。

图5：演化过程示意图

在更宏观尺度上，演化过程中会出现聚集现象，即处于活状态的点聚在一起，并按照固定间隔，呈现相似的模式，如图6所示，每隔1556步会呈现相似的模式。从视觉上看，近似一个手臂（图6c中的模式）在每一次之后的演化中出现，同时慢慢地脱离原来的位置产生一个新复制。这一复制尽管不能看出是作为一个整体自复制，但演化过程中涌现出近似的自复制因子。这一现象是巧合还是具有必然性，需要进一步研究。

图6：每隔1556步出现的相似宏观模式

4. 自复制规则何以涌现

该实验揭示了离散元胞自动机中，一个具有自复制特征的规则集合。该规则是在搜索了几十万条规则后偶然发现的，而这几十万条规则组合，仅仅是可能规则中的沧海一粟。于是新的问题出现了，是否还有更多具有自复制的规则。自复制规则之所以能够涌现，在于其对外部的冲击具有鲁棒性，即自适应能力，这意味着新信息在演化过程中涌现，并存储于重复出现的模式中。而层次化的自相似，则与复杂系统的分形及跨层次涌现有关。

相关研究表明，连续空间上具有演化特征的元胞自动机，演化过程中出现了自复制、分工、个体性等复杂系统特有的现象。

对应的 python 包：

https://github.com/Chakazul/Lenia

因果涌现读书会第三季启动

涌现无疑是复杂系统诸多现象中最神秘莫测的一个。从鸟群聚集、萤火虫同步、蜜蜂舞蹈，到宇宙起源、生命演化、意识产生，我们生活在一个“涌现”的世界中。所谓的涌现，是指复杂系统在宏观所展现出来的，无法归约到微观的特性或规律。新兴的因果涌现理论有望为量化多尺度复杂系统中的涌现现象提供强大工具。

由北京师范大学教授、集智俱乐部创始人张江等人发起的「因果涌现」系列读书会第三季，将组织对本话题感兴趣的朋友，深入探讨因果涌现的核心理论，详细梳理领域发展脉络，并发掘因果涌现在生物网络和脑网络、涌现探测等方面的应用。读书会自7月11日开始，每周二晚19:00-21:00，预计持续时间8～10周。欢迎感兴趣的朋友报名参与。