计算机科学

细胞自动机的丰富生态学

元胞自动机可以模拟各种现象,例如汽车交通和森林大火的蔓延。新的分析技术根据复杂度等级对自动机进行分类。

玛丽安(Marianne Delorme)和雅克·马佐耶(Jacques Mazoyer) 科学档案编号52
本文仅供《 对于科学》的订户使用
您前面的汽车向前移动了一段距离,然后向前移动以取代它的位置。显然,如果她不动,你就不会动。这些平庸的行为构成了交通阻塞的本质:成千上万的驾车者重复了一些机械行为,从而导致汽车行驶缓慢。

那么如何模拟插头的传播呢?轮胎胎面与道路接触的复杂物理原理与驾驶员的心理无关。一种有效的方法是将道路划分为一系列“单元”,每个单元容纳一辆汽车,然后写一些表达驾驶员可能行为的“规则”。

车辆占用的一个单元格为黑色,一个空的单元格为蓝色,并且在任何给定时间的道路占用率都将显示为以下行:

交通量的演变将由代表交通量演变的这些线的堆叠(向上发展)来表示,从一条线到另一条线的通道遵循一定数量的规则。对于单条路线,有以下所示类型的八个规则(中心单元由白盘表示)。

通过将这些规则应用于先前的条件,计算机可以计算出每种道路条件。在不到一秒钟的时间内,出现了对面的表格,其中交通拥堵的传播导致向黑带的左侧发展(这说明交通拥堵以逆行波向交通的后方传播)。

我们的循环动力学模型构成了细胞自动机的一个例子,也就是说,是一个基本细胞社会,每个基本细胞逐步地转变为根据以下方法确定的少数可能状态之一数量减少的相邻小区(此处为三个小区)的状态。为了定义细胞自动机,我们给出其细胞的排列(其空间),相邻细胞对一个细胞(其邻域)产生影响的规则以及定义其进化的规则。这些仅影响有限数量的单元邻居的局部规则具有全局影响:它们决定了整个单元社会的动态。

复杂或复杂

我们将在这里检查细胞自动机的丰富生态学,希望根据它们产生的结构按复杂程度进行分类。这个难题只有部分解决方案。但是,我们知道如何区分仅生成“复杂”结构的自动机与生成“真正复杂”结构的自动机。我们将证明,在某些情况下,自动机的所有复杂性都以一个单一的结构表示,即“本质上是通用的”自动机。

为什么掌握细胞自动机产生的复杂性很重要?与现实相比,细胞自动机似乎过于简单。但是,细胞自动机已成为模拟许多自组织现象的影响所必需的。在物理学中,伊辛模型通过将原子的复杂性降低为仅在与它们的最邻近原子相互作用的细胞中间植入的箭头来描述铁磁性。它是1925年发明的,是最早的细胞自动机之一。一家大型化妆品生产商使用“毛囊自动机”公司来模拟头发生长,并测试化妆品在卵泡周期三个阶段之一中的作用的整体效果。 2003年夏天大火在莫里斯山的蔓延是通过一些规则来模拟的,这些规则根据在后方点燃的细胞来确定在前面的森林细胞的点火。

还有一些细胞自动机可以模拟气体的行为,固体的结晶,危险面前人群的逃逸,或者等同于沙土的流动,液体中的湍流,发展城市,渗滤等在每种情况下,它们的使用将情况的复杂性降低到生成现象动态所必需的程度。这是一个悖论:现实是复杂的,而统治它的法律往往却并非如此!

实际上,元胞自动机非常适合进行数值模拟。良好的仿真需要计算能力,但是当可以同时进行计算(即并行执行)时,此必要的能力会较小。然而,细胞相互作用的局部性质使得细胞自动机的编程容易“并行化”。

在视频游戏或其他图形程序中,越来越频繁地使用“虚拟现实”的元素,即计算机内部对现实的模拟,将使我们面临越来越多的挑战。基于细胞自动机的程序。这些自动机的行为如何?如何理解它们生成的结构的复杂性?

Wolfram的课程

斯蒂芬·沃尔夫拉姆(Stephen Wolfram)是最早意识到这一问题重要性的研究人员之一。 1984年,他提议根据细胞“自动机”的“轨道”的性质来区分它们的四个“复杂性类别”。这就是图的名称,也称为时空图,它是通过堆叠自动机从初始配置连续生成的配置表示而获得的,就像我们为循环所做的那样。

我们认为,Wolfram的复杂度类别不足以说明细胞自动机的复杂度。但是,我们将使用它们来逐步探索遇到的复杂程度。为了解释它们以及我们将要采用的所有概念,我们将研究由简单类型的细胞自动机(“基本细胞自动机”)提供的轨道示例。它们的空间是一排细胞,每个细胞可以处于两种不同的状态,就像我们循环中的蓝色或黑色细胞一样。局部规则根据三个像元的八个可能的三元组之一(所考虑的像元,其邻居在右边和左边的一个)来确定一个像元的下一个状态:因为每个像元都有两种可能( 0)或(1)在下一行,有2 8,即256个我们称为基本自动机的本地规则。这些基本自动机的编号为0到255,由连续的8个0或1表示,这些连续的8个三元组始终以相同的顺序给出:11111010110001110001000。

因此,举例来说,规则184被记为10111000,它是我们用来描述流量规则的规则,其解释如下:

11111010110001110001000

限于256个居民的宇宙似乎很差,但是我们将看到,减少的规则数量和对初始配置的选择(起点)足以产生无限数量的复杂度不同的轨道,涵盖了Wolfram的四类。另外,这些自动机的优点是通过堆叠连续的行可以很容易地在一张纸上看到。

Wolfram的1类自动机的行为是单调的:它们向一个永不离开的统一场收敛(见图2a)。 2类自动机的通用性要少一些:它们产生的轨道在时间上是周期性的(见图2b)。如果在时空图中观察到的周期性通常仅反映初始配置的周期性,则存在2类细胞自动机,它们会产生周期性的轨道而没有其初始配置。

这些类的自动机看起来很简单,这具有误导性:从Gödel的角度来看,确定自动机是否属于一个自动机是一个无法确定的问题:没有一种算法可以将“自动”作为输入这样的自动机在“输出”中赋予其成员资格,或者不赋予该成员资格。

错综复杂的行为

3类和4类自动机的行为从其开发的开始到结束就显得“复杂”,甚至是千丝万缕的复杂(见图2c和2d)。

定义细胞自动机的局部规则没有考虑其能力,这种能力以其配置变化(它们的动力学)表示。所谓复杂的细胞自动机,而不是过于复杂的细胞,是指我们可以在数学上构造构型空间并描述其进化的某些特性的细胞自动机。从某种角度来看,我们将看到3类细胞自动机只是“复杂的”。另一方面,在所有第4类自动机中,以不可预测的方式出现的惊人的局部秩序形式,不仅比“复杂”得多:迄今为止,这种形式在数学上还没有得到描述。

3类自动机通常被称为混沌,因为它们的轨道看起来是不规则的。为了理解这一术语,必须确定观察到的不规则的原因。某些3类自动机的行为表示对初始条件非常敏感:对初始配置的轻微修改会强烈改变轨道,或导致对某些轨道产生非常遥远的影响。这种行为引起了物理学家所定义的混乱,并引起了对所有构造的研究,因此我们可以比较初始直线的轨道。

我们该怎么做呢?所有配置都提供有“拓扑”,换句话说,配置之间具有邻域的概念。为此,我们定义了两个构形之间的距离,最自然的是德国数学家Georg Cantor(1845-1918)所说的,他表示加上两个构形(两条线)在原点附近重合(它们有较大的处于相同状态的单元数),它们是“更接近的”。借助Cantor距离,可以定义配置的重要属性,从而可以定义PLC的重要属性。如果在进化过程中由紧密配置产生的轨道保持紧密,则配置为“等连续”。当自动机的所有配置都是等连续的时,它被称为等连续的。当自动机对每个配置都存在一个紧密的配置,且该配置的轨道偏离其自身时,自动机被认为是敏感的。当在自动机的进化过程中所有相似构象对之间的差异被放大时,自动机被认为是可扩展的。

由于这些概念,我们将细胞自动机分为四个“ K°urka类”:等连续自动机的类,不是连续但具有等连续配置的类,敏感自动机的类。扩展的和扩展的自动机。因此,产生非常不规则的时空图的自动机是混乱的:敏感的或膨胀的。让我们注意-这是S.Wolfram复杂度类别不足的例证之一-S.Wolfram的第3类自动机在K°urka的意义上并不是混沌的(实验在S. Wolfram仅使用初始的周期性配置(具有较小的周期)的计算机上,一些混沌现象仅在非周期性的配置中出现,或者出现的时间非常长,甚至非常少。

请注意,还有K°urka类的替代品,以描述由细胞自动机产生的混沌类型。所有这些都像K°urka一样,融合了对初始条件敏感的想法。因此,从多个角度来看,没有细胞自动机产生的混沌的内在定义。但是,即使混沌轨道的不规则性令人印象深刻,我们仍会保留,但是面对混乱,我们并非无能为力。有一些方法可以比较混沌轨道并将产生它们的自动机分类为几个类。这表明产生不规则时空图的自动机仅是“复杂的”,而不是“超越复杂的”,即真正的复杂。对我们来说,第4类是“真正的复杂性”。

这更加正确,因为我们不知道仅在上述数学意义上很复杂的4类自动机。 S. Wolfram的4类自动机的时空图表现出了显着的特点:经过一定的稳定或自组织时间后,出现了结构,种类的粒子。著名的生命游戏(最著名的细胞自动机之一)中的“滑块”就是这种情况,但由于生命游戏是第二个维度,因此并未包含在我们的研究中。在我们的示例中,粒子或滑块似乎是由它们自己的动态设置的:在这些冲击期间它们是否部署,碰撞,变形或不变形,并分离出我们认为是背景的统一区域(参见图2d ,4、5和8)。

分组

为了了解粒子的动力学,我们通过技术,分组来区分它们,这使它们的运动从时空图中显现出来。由于粒子在其上移动的背景的图案彼此相似并且仅在位置上有所不同,因此可以通过自动方式将它们表示出来,而不必理会它们的形状。这是不同类型分组的本质,我们将举一个简单的示例:在此分组中,我们将自动机A的时空图划分为带有四个边单元的正方形(参见图4)。这样的正方形分组包含背景图案。每个正方形都减少到其下一行,这不会造成任何信息丢失:从通过分组获得的四元组细胞中,我们知道如何重构整个细胞自动机。

从这些规则推论出将初始自动机的时空图缩减为新的时空图的过程(可以自动化)。这些新轨道是新自动机的轨道:在考虑为正方形分组的意义上的“ A群”。在图5中,我们给出了从规则54(00110110)获得的轨道中出现的结构的其他几个示例。在第一个示例中,我们观察到两个“背景”之间的中断,这可以解释为接口向右的传播。分组自动机的对应图是两个同质区域的并置。它也是自动机170(10101010)产生的时空图之一。还可以通过自动机54获得显示接口向右传播的自动机240和提供固定接口的自动机204的时空图。

通过这些分组技术,可以定义复杂程度。如果通过某种分组获得的自动机A的轨道组包含在B分组自动机的轨道的基础结构中,则自动机A的声明比自动机B的复杂度要低。不管首行是什么)。如果是这样,那是因为A的分组图包含的信息少于B的分组图:它们的复杂度较低。

例如,规则240的基本自动机比规则54的基本自动机复杂,因为其时空图包含在由规则54生成的图中。元胞自动机由其图集表示时空,我们得出结论说A的复杂度不如B.如果A的复杂度不如B,并且B的复杂度不如A,则我们可以识别A和B.如此确定的所有自动机都确定了一个集合,称为类(d '等价”,其中特别包含其每个元素的所有分组。然后,我们可以将两个类相互比较:如果A的任何自动机的复杂度都小于B的任何自动机,则A类小于B。因此,一个定义了部分顺序的关系(仅部分的关系,因为根据该技术,两个类A和B可能不具有可比性)。

复杂度量表

就分组而言,一组类可能具有更大的元素。因此,虽然由正方形分组引起的阶数没有较大的元素,但矩形分组导致具有最大阶数的阶:本征通用自动机的类别。

因此,我们已经成功地区分了细胞自动机人群中给定分组的不同复杂程度。这种偏序的存在暗示了复杂性上的距离的概念:自动机与另一自动机之间的距离越远,它在复杂性范围内的条形数量就越多。请注意,如果比例尺包含无限条,则自动机B可以与自动机A无限远(复杂度)。

只有某些分组(例如矩形分组)会产生(无限)复杂度标度,并具有较高的梯级:此最大复杂度对应于本质上通用的自动机的类别。值得注意的是,我们可以通过具有六个状态的简单自动机来表示此类。

让我们坚持认为:通过选择矩形分组的参数的不同值,我们从这个本质上通用的自动机的轨道中再现所有细胞自动机的所有轨道!为了实现性能,让我们指定在复制的自动机中,特别是所有通过“清洁生命”(传播的局部顺序)动画的粒子遍历其轨道的细胞自动机,以及“图灵”自动机。通用”(该术语表示自动机的类别,其图轨重现了计算机执行的所有可能的计算,图灵机也是如此)。我们在图8中显示了一个自动机的轨道之一,它结合了结构和算法复杂性的这些形式:规则110(01101110)。

总是可以将任何形式的复杂性的产生都简化为计算总和,换句话说,就是某种图灵通用自动机或多或少地需要较长时间的工作这一想法已经广为流传。正如我们已经表达的那样,对我们来说似乎是错误的。通过矩形分组获得的分类揭示了一类图灵通用细胞自动机,它与由内在通用自动机组成的最大值无限远。图7中固有的通用自动机的简单性与它所再现的极端形式的复杂性之间的对比令人惊讶。我们知道如何建造它,只是看起来很复杂,事实是它的某些轨道确实是密不可分的,这使它变得复杂!

令人惊讶的是,最简单的细胞自动机的简单性和能够创建“生命形式”或执行所有可能的计算的自动机的复杂性都包含在同一结构中。

订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

我们的最新出版物

回到顶部

已经有帐号了?

身份证明

标识自己可以访问您的内容

看到

还没有帐户 ?

注册

注册以激活您的订阅或订单问题。

创建我的账户