元胞自动机和康威生命游戏

2019-05-25 本文已影响0人 Cloud_J

简介

发展和应用

元胞自动机(Cellular Automata, 简称CA)，是冯·诺依曼在20世纪50年代初为模拟生物发育中细胞的自我复制而提出的，但当时并未引起关注和重视。

1970年，剑桥大学的康威(J.H.Conway)设计了“生命游戏”，它是具有产生动态图案和动态结构能力的元胞自动机模型，吸引了众多科学家的兴趣，推动了元胞自动机研究的迅速发展。

之后，Stephen Wolfram对初等元胞自动机的256种规则产生的所有模型进行了详细而深入的研究。他还用熵来描述其演化行为，把元胞自动机分为：平稳型、周期型、混沌型、复杂型四类

现在，元胞自动机在交通流模型、火灾模拟模型、肿瘤细胞的增长机理模拟、股票投资心理模型、计算机的并行计算等很多领域都有应用

元胞自动机的构成

标准元胞自动机是一个由「元胞、元胞状态、邻域和状态更新规则」构成的四元组，用数学符号可以表示为A=(L,d,S,N,f)

A代表一个元胞自动机系统
L表示元胞空间
d表示元胞自动机内元胞空间的维数，是一正整数
S是元胞有限的、离散的状态集合
N表示某个邻域内所有元胞的集合
f表示局部映射或局部规则。

元胞空间

元胞是构成元胞自动机的基本单元，而元胞空间是元胞所分布的空间网点集合。
说白了就是所有元胞可以存在的位置的集合
理论上，元胞空间是在各维向上无限延展的，但实际中无法在计算机上实现。因此，需要定义不同的边界条件。
元胞空间的边界条件主要有三种类型：周期型、反射型和定值型。

周期型。在一维上表示为首尾相连；在二维上则是左右相连，上下相连的一个拓扑圆环面（类似甜甜圈）。周期型与无限空间最为接近，因此在理论研究时常用作试验。
反射型。在边界外邻居的元胞状态是以边界为轴的镜面反射。
定值型。边界外的元胞均取某一固定值。

元胞状态

在一般情况下，某一时刻一个元胞只能有一个状态，取自一个有限集合，比如{0,1}，{生,死}，{a1,a2,...,an}等等
在不同的应用模型中，这种状态也可以用来表示不同的特征，比如在社会科学中常用来表示个体所持的态度或行为等。

邻域

在空间位置上与元胞相邻的位置称为邻元，所有邻元组成的区域就是元胞的邻域。
在一维情形中，常用半径r来确定邻域，距离元胞距离为r的所有元胞都是他的邻域。
如下图中灰色的位置就是黑色元胞的邻域。

邻域.png

在二维的情况下，通常有以下几种类型的邻域：

冯诺依曼型。以上下左右四个相邻元胞为邻域，如图a
摩尔型。以周围八个相邻元胞为领域，如图b。（生命游戏就是以用摩尔型邻域的）
扩展摩尔型。将半径扩大，如图c
马格勒斯型。与上面两种不同，马哥勒斯型是一种元胞分块技术，每次统一处理2×2格子的元胞块，元胞的演化只有元胞块内部的元胞状态决定

二维邻域类型.png

马哥勒斯型.png

状态更新规则

是指根据元胞当前状态及其邻域中元胞的状态决定下一时刻该元胞状态的状态转移函数。
状态更新规则可以写为
$f:S^{t+1} = f(S^{t},S_N^{t})$
其中， $S_N^t$ 表示t时刻的邻域状态集合

标准元胞自动机的特征

离散性
同质性
并行性
局部性
维数高

一维双色元胞自动机

概念简介

一维双色元胞自动机是一种最简单的元胞自动机
一维，指的是这个元胞自动机是在一个维度为1的元胞空间内进行演变的
双色，指的是每个元胞的元胞状态只有2种，如，0 或 1
在邻域半径 r=1 的情况下，一维元胞自动机的状态更新函数可以这样表示
$f:S^{t+1}_i = f(S^t_{i-1},S^{t}_i,S_{i+1}^{t})$
即在下一个时刻的元胞状态仅和左右两个元胞状态和自身的元胞状态有关