细胞自动机

August 14, 2017 23:03


特征

细胞自动机有三个特征:

历史

细胞自动机最早由美籍数学家 冯·诺依曼(John von Neumann) 在 1950 年为模拟生物细胞的自我复制而提出的。但是并未受到学术界重视。直到 1970 年,约翰·何顿·康威(John Horton Conway)设计了生命游戏,经马丁·葛登在《科学美国人》杂志上介绍,才吸引了科学家们的注意。此后,英国学者史蒂芬·沃尔夫勒姆(Stephen Wolfram)对初等元胞机256种规则所产生的模型进行了深入研究,并用熵来描述其演化行为,将细胞自动机分为平稳型、周期型、混沌型和复杂型。(Ref Wikipedia])

分类

按照复杂性分类,通常有如下四类:

  1. 迅速演变成一个稳定的状态。在初始模式的任何随机性会消失。
  2. 迅速演化为稳定或是振荡结构,一些随机性可能会被过滤掉,但还有一些保留。局部变化倾向于继续保持局部性。
  3. 演变成为一个伪随机或混沌的形式,任何稳定的结构很快会被周围的噪音破坏。局部变化有无限蔓延的倾向。
  4. 演变成相互作用的复杂和有趣的方式结构,并且局部结构的形成能够长时间存在。2 类的稳定或振荡结构可能是最终的结果,但需要达到这个状态的步骤数目可能是非常大的。

康威生命游戏

生命游戏中,对于任意细胞,规则如下:

  1. 每个细胞有两种状态-存活或死亡,每个细胞与以自身为中心的周围八格细胞产生互动。(如图,黑色为存活,白色为死亡)
  2. 当前细胞为存活状态时,当周围低于2个(不包含2个)存活细胞时, 该细胞变成死亡状态。(模拟生命数量稀少)
  3. 当前细胞为存活状态时,当周围有2个或3个存活细胞时, 该细胞保持原样。
  4. 当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模拟生命数量过多)
  5. 当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖)

可以把最初的细胞结构定义为种子,当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图,可以得到下一代的细胞图,周而复始。

Example

使用 Love2D 写的一个实现,包涵生命游戏及一些其它的演化规则 CellularAutomaton

References

Comments: