数模笔记14-元胞自动机

这篇具有很好参考价值的文章主要介绍了数模笔记14-元胞自动机。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

元胞自动机模型

元胞自动机理论

元胞自动机(Cellular Automata,CA)是一种时空离散的局部动力学模型,是研究复杂系统的一种典型方法,特别适合用于空间复杂系统的时空动态模拟研究。

元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。

在CA模型中,散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化

CA模型的特点:时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。

元胞自动机的构成

元胞自动机最基本的组成:元胞、元胞空间、邻居及规则四部分。
简单讲,元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。

元胞自动机模型,数学建模,算法,机器学习,人工智能

元胞自动机的构成

  1. 元胞

    元胞自动机的最基本组成部分。它分布在离散的一维、二维或多维欧几里德空间的晶格点上。

  2. 状态

    状态可以是{0,1}的二进制形式,或是{s0,s1,s2,…,si}整数形式的离散集。严格意义上,元胞只能有一个状态变量,但在实际应用中,往往将其进行扩展。

  3. 元胞空间

    元胞所分布在的空间网点集合就是元胞空间

    • 元胞空间的几何划分

      任意维数的欧几里德空间规则划分。对于一维元胞自动机,元胞空间划分只有一种。而高维的元胞自动机,元胞空间的划分则可能有多种形式。对于常见的二维自动机,元胞空间通常可按三角形、四边形或六边形三种网格排列。

      元胞自动机模型,数学建模,算法,机器学习,人工智能

      • 三角网格

        拥有较少的邻居数目,这在某些时候很有用。缺点是计算机的表达与显示不方便。

      • 四边形网格

        直观简单,特别适合于计算机环境下进行表达显示。

      • 六边形网格

        能较好的模拟各向同性的现象,因此,模型能更加自然而真实。其缺点同正三角网格一样,在表达显示上较为困难和复杂。

    • 边界条件

      理论上,元胞空间在各个维向上是无限延展的。实际应用过程中,无法在计算机上实现这一理想条件。

    • 构形

      在某个时刻,在元胞空间上所有元胞状态的空间分布组合。在数学上,它通常可以表示为一个多维的整数矩阵。


    邻居、元胞和元胞空间只表示了系统的静态成分,为了将动态引入系统,必须加入演化规则。这些规则是定义在局部空间范围内的,即一个元胞下一时刻的状态决定于本身的状态和它的邻居元胞的状态。因此,在指定规则之前,必须定义一定的邻居规则,明确哪些元胞属于该元胞的邻居。

    一维元胞自动机中,通常以半径r来确定邻居,距离一个元胞r内的所有元胞都属于该元胞的邻居。

    二维元胞自动机的邻居定义较为复杂,但通常有以下几种(以正方形网格为例 )

    元胞自动机模型,数学建模,算法,机器学习,人工智能

  4. 规则

    根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数,简单讲,就是状态转移函数。这个函数构造了一种简单的离散的时间和空间范围的局部物理成分。状态的变化可以由状态转移函数表示
    f : S t t + 1 = f ( S i t , . . . , S N t ) S N t 为 t 时刻的邻居状态组合 f:S_t^{t+1}=f(S_i^t,...,S_N^t)\\ S_N^t为t时刻的邻居状态组合 f:Stt+1=f(Sit,...,SNt)SNtt时刻的邻居状态组合

  5. 时间

    元胞自动机是一个动态系统,它在时间维上的变化是离散的,即时间t是一个整数值,而且连续且等间距。在上述转换函数中,一个元胞在t+1时刻的状态只直接决定于t 时刻的该元胞及其邻居的状态。


元胞自动机特性

把一个空间划分成网络,每一个点表示一个元胞,它们的状态赋值,在网格中用颜色的变化来表示,在事先设定的规则下,元胞的演化就用网格颜色的变化来描述,这样的模型就是元胞自动机。

通过对元胞自动机这些网络中的格点的不同定义,以及初始条件的不同,可以模拟出不同的现象和过程。

元胞自动机的基本特征:

  • 离散性:元胞自动机是高度离散的。它不仅仅空间离散时间离散,而且在函数值,即元胞的状态值也是离散的。
  • 动力学演化的同步性:元胞自动机具有利用简单的,局部规则的和离散的方法,描述复杂的,全部的和连续系统的能力。
  • 相互作用的局部性:元胞自动机的规则是局部的,而动力学行为规则是全局的,在模拟的过程中,具体的演化过程也是局部的,即仅同周围的元胞有关系。

元胞自动机应用的思想

复杂系统又称为非线性系统。如城市的发展与演化、城市人流与交通流以及交通堵塞的形成、自然环境下的动物的空间分布、河网的形成、疾病的传播等。

传统的自顶向下的分析方法是把系统分割成几个部分,对每一个部分逐个进行研究。而目前提出来的分析复杂动态系统的思想:自底向上的研究方法。

基于个体的自底向上的研究方法:
程序的行为完全由它的内部机制决定,通常将个体与程序相连,所模拟的复杂现象包括许多个体。在计算机里生成一个与真实世界对等的虚拟的人工世界,通常这个虚拟的世界包括许多个体,而这许多个体的行为呈现为复杂性。以此来探讨微观的个体行为和宏观复杂性之间的关系

初等元胞自动机

初等元胞自动机是状态集S只有两个元素{s1,s2},即状态个数k=2,邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要,它可取 {0,1},{-1,1},{静止,运动} 等等,重要的是S所含的符号个数,通常我们将其记为 {0,1}。
此时,邻居集 N 的个数 2 ⋅ r = 2 ,局部映射 f : S 3 − > S 可记为: S i t + 1 = f ( S i − 1 t , S i t , S i + 1 t ) 此时,邻居集N的个数2·r=2,局部映射f:S_3->S可记为:S_i^{t+1}=f(S_{i-1}^t,S_i^t,S_{i+1}^t) 此时,邻居集N的个数2r=2,局部映射f:S3>S可记为:Sit+1=f(Si1t,Sit,Si+1t)

二维元胞自动机

  • J. Conway和生命游戏

    下面介绍生命游戏的构成及规则:

    1. 元胞分布在规则划分的网格上;

    2. 元胞具有0,1两种状态,0代表“死”,1代表“生”;

    3. 元胞以相邻的8个元胞为邻居。即Moore邻居形式;

    4. 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定:

      在当前时刻,如果一个元胞状态为“”,且八个相邻元胞中有两个或三个的状态为“生”,则在下一时刻该元胞继续保持为“生”,否则“死”去;

      在当前时刻,如果一个元胞状态为“”,且八个相邻元胞中正好有三个为“生”,则该元胞在下一时刻 “复活”。否则保持为"死"。

    元胞自动机模型,数学建模,算法,机器学习,人工智能

    从数学模型的角度看,该模型将平面划分成方格棋盘,每个方格代表一个元胞。

    元胞状态: 0- 死亡,1- 活着

    领域半径: 1

    领域类型:Moore型

    元胞自动机模型,数学建模,算法,机器学习,人工智能

    元胞自动机是一个不可逆的离散动力系统

  • 元胞自动机的演化行为的统计特征

    Wolfram将元胞自动机的演化行为归纳为四大类:

    1. 平稳型(homogeneous):自任何初始状态开始,经过一定时间演化后,经过若干步运算便停留在一个固定的状态。
    2. 周期型(periodic):经过一定时间演化后,在几种状态之间周期循环。
    3. 混沌型(chaos):自任何初始状态开始,经过一定时间演化后,处于一种完全无序随机的状态,几乎找不到任何规律。
    4. 复杂型(edge of chaos):在演化的过程中可能产生复杂的结构,这种结构既不是完全的随机混乱,又没有固定的周期和状态。

    固定点—>周期—>复杂—>混沌

  • 森林火灾

    规则:
    元胞有3个不同的状态。状态为 0是树木,状态= 1是空地,状态= 5是燃烧着的树木。
    如果4个邻居中有一个或一个以上的是燃烧着的并且自身是树木,那么该元胞下一时刻的状态是燃烧。
    森林元胞(状态为 0 )以一个低概率(例如0.000005 )开始烧(因为闪电)。
    一个燃烧着的元胞(状态为 5 )在下一时刻(时间步长可以控制)变成空位的(状态为0 ) 。
    空元胞以一个低概率(例如0.01 )变为森林以模拟生长

  • 元胞自动机交通流模型

    特别注意:第184号规则

    车辆行驶规则为:黑色元胞表示被一辆车占据,白色表示无车,若前方格子有车,则停止。若前方为空,则前进一格。

    元胞自动机模型,数学建模,算法,机器学习,人工智能

    1992年,德国学者Nagel和Schreckenberg在第184号规则的基础上提出了一维交通流CA模型,即,NS 模型(或NaSch模型)

    NS模型是一个随机CA交通流模型,每辆车的状态都由它的速度和位置所表示,其状态按照以下演化规则并行更新 :

    • 加速过程:元胞自动机模型,数学建模,算法,机器学习,人工智能

    • 安全刹车过程: 元胞自动机模型,数学建模,算法,机器学习,人工智能

    • 随机慢化过程:(以随机慢化概率p)元胞自动机模型,数学建模,算法,机器学习,人工智能

    • 位置更新:元胞自动机模型,数学建模,算法,机器学习,人工智能

    d n = x n + 1 − x n − L 其中: L ——车辆长度  7.5 m d_n=x_{n+1}-x_n-L\\ 其中:L——车辆长度 ~ 7.5m dn=xn+1xnL其中:L——车辆长度 7.5m

    NS模型的演化规则:

    1. 加速: 司机总是期望以最大的速度行驶
    2. 安全刹车: 为避免与前车碰撞
    3. 随机慢化(以随机慢化概率p):由于不确定因素
      • 过度刹车
      • 道路条件变化
      • 心理因素
      • 延迟加速
    4. 位置更新:车辆前进

    元胞自动机模型,数学建模,算法,机器学习,人工智能文章来源地址https://www.toymoban.com/news/detail-700380.html

到了这里,关于数模笔记14-元胞自动机的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【元胞自动机】元胞自动机3D森林火灾模型【含Matlab源码 656期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年04月29日
    浏览(33)
  • 元胞自动机( Cellular Automata)研究 (Python代码实现)

     👨‍🎓 个人主页: 研学社的博客   💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🌈

    2024年02月09日
    浏览(37)
  • AC 自动机学习笔记

    AC自动机( (Aho Corasick Atomaton) )有着一种 (KMP) 的思想,所以在学习之前建议先学一下 (KMP) 。同时还需要了解一下 (Trie) 树(建议去看一下 oi-wiki 上的字典树) 给定一个字符串 (S) 和 (n) 模式串,问有多少个模式串在 (S) 中出现过。 首先我们把 (n) 个模式串组成一

    2024年02月11日
    浏览(38)
  • 「学习笔记」AC 自动机

    点击查看目录 目录 「学习笔记」AC 自动机 算法 问题 思路 代码 例题 Keywords Search 玄武密码 单词 病毒 最短母串 文本生成器 背单词 密码 禁忌 前置:「学习笔记」字符串基础:Hash,KMP与Trie。 好像对例题的讲解越来越抽象了? 求 (n) 个单词在一个长度为 (m) 的文章里出现

    2024年02月02日
    浏览(39)
  • 正规文法、正规表达式、有限自动机及其之间的转换(笔记)

    The Equivalent Transforming among RG, RE and FA A Grammar G is a quadruple (四元组):G = (V N , V T , S, P ) Where, V N is a finite set of nonterminals. V T is a finite set of terminals. S is the start symbol, S ∈ in ∈ V N . P is a finite set of productions (产生式). Regular Grammar (RG) (正规文法): α∈V N and β ∈V T ∪V T V N Regular Exp

    2024年02月08日
    浏览(39)
  • AC自动机 模板

    核心思路是kmp的拓展,只是i++、j++什么的转换成了树的形式,初始化用bfs,每一点的初始化都是借助于该层以前的层进行的。 trie图优化: ne[t]是回溯一次,tr[ne[t]][i]直接记录好了它下一个点的位置,存在儿子就到儿子,没有儿子就是记录的回溯好的点。 每个点的ne都被计算

    2024年01月21日
    浏览(33)
  • KMP算法 - 确定有限状态自动机

    子串匹配问题,拍脑袋一下子想出来的暴力解法大抵都是两重for循环,不断重复扫描主串,与子串进行匹配,重复换句话讲就是冗余,会有很高的时间复杂度 我先前博客大作业发的 模糊查找算法 就是如此,我那里是在计算一个匹配度的问题,通过相同定位到相同字母判定开

    2024年02月09日
    浏览(45)
  • 【NLP】有限自动机的KMP算法

    目录 一、说明 二、无策略直接匹配法 2.1  简单粗暴的无脑匹配: 2.2 跳过外循环的思路

    2024年02月08日
    浏览(39)
  • 不确定有穷自动机NFA的确定化

    从文件读入一个非确定有穷状态自动机(NFA),用子集法将其确定化,并输出一个确定化的有穷状态自动机(DFA)。 原理: 流程图如下: 具体代码实现: 这里为了实现图形可视化,使用了graphviz,下载完成Graphviz工具后,需将其添加至系统环境变量中,且需将其上移至Matl

    2024年02月07日
    浏览(36)
  • 100行python代码实现细胞自动机(康威生命游戏)

     英国数学家约翰·何顿·康威在1970年发明了细胞自动机,它属于一种仿真程序,通过设定一些基本的规则来模拟和显示的图像的自我进化,看起来颇似生命的出生和繁衍过程,故称为“生命游戏”。 完成效果 用到的第三方库 pygame 基本规则 康威生命游戏在网格上进行,有填

    2023年04月08日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包