【《元胞自动机理论概述》3500字】

我国中小企业的技术创新研究元胞自动机理论概述元胞自动机(CellularAutomata，CA)理论是指在离散的时空环境下，系统内部各个单元按照一定的规则自组织地形成系统当前或未来状态的思想学说，主要有一系列规则模型组成，凡是涉及时空演变规则的模型都可以看做是元胞自动机模型（黎夏等，2007）。20世纪40年代，学者Ulam首次提出元胞自动机思想，20世纪50年代，享有“计算机之父”美誉的vonNcumann设计出了自繁殖自动机(self—ReproducingAutomata)，并应用到自我繁殖系统的实例中，从而进一步明确了元胞自动机的理论基础；20世纪60年代，英国学者Conway对元胞自动机进一步发展完善，开发出了“生命游戏”(GameofLife)模型，通过设计局部转换规则来模拟复杂系统的演化过程，将元胞自动机应用到现实系统的动态模拟中。20世纪80年代，学者Wblfram将元胞自动机融入到系统动力学中进行研究，指出了元胞自动机的五个特征，证实了元胞自动机可以作为其他相关理论的动态演变研究的技术工具（WblframS，1984)；20世纪80年代后，伴随着复杂系统理论和信息论以及多媒体技术的发展，元胞自动机已经成功应用到多个学科中，在城市系统、生态系统、社会系统、军事领域和土地利用变化等多个研究领域展现出了技术优势。因此，将元胞自动机理论作为城镇用地增长空间模拟以及城镇开发边界划定的基础方法论。（1）元胞自动机（CA）的定义通过上述细胞自动化进化历程可以看出，细胞自动机是由不同学科（物理专业、数学学科、计算机专业等）的学者在前人研究的基础上逐步发展完善的产物。不同的学科基于本学科的特点对细胞自动化机有不同的定义（段晓东等，2012），简述如下：元胞自动机的数学定义：美利坚合众国数学家Culik和Hurd等人（CulikK，1990)基于数学的语言采用代数和几何的思维分别定义了细胞自动化机：①元胞自动机的集合论定义：假设表示元胞范围维数，表示元胞情况，且的取值属于一个有限集合，表示元胞邻居长度，表示一维范围情况下的集合集，表示time。将一维细胞自动化当作例子，认为集合集上的情况集的分布为，细胞自动化就是在离散时间维度上元胞状态的动态演变：（3-2）元胞单元的微观转变状态法则决定着元胞状态是否变化，将一维细胞自动化当作解说模板，中心元胞及其邻居元胞记为，微观转变状态法则可以采用如下所示：（3-3）微观转变状态法则的输入和输出都是有固定个数的组合。元胞空间内单个元胞按照微观转变状态法则就能获得整个系统的动态演变：（3-4）式中，为时刻处于位置的元胞单元。上述便可以获取一维的细胞自动化机模型。②元胞自动机的拓扑学定义，将一维细胞自动化当作解说模板，假设个状态值的有限集为，表示整数组合，代表到的对应的结构空间，代表结构空间中的小点，以代表中随便两小点和的距离，即：（3-5）公式中，当时，有，当时，有。此时，便可在中建立几何定义。在中规定移动算子为。若不间断映射与可交换，或对任意有，那么就是细胞自动化机。当在实际环境中，变换对应的属性，将记为，记为，便可将上述一维细胞自动化机变换为各种维度细胞自动化机。（2）元胞自动机（CA）基本构成标准一般细胞自动化机（CA）模型包含5个基本组成要素：细胞(Cell)和其属性情况(state)、细胞范围(Lattice)、邻居(Neighborhood)、转变状态法则(TransferFunction)和离散时间(Temporal)（周成虎等，1999）。如图3-4所示。图3-SEQ图\*ARABIC\s14细胞自动化机结构示意图标准一般元胞自动机（CA）各组成要素部分用数学语言表示为：（3-6）其中，表示元胞范围，表示元胞范围的维数；表示细胞属性组合；表示转变状态法则；为离散时间；表示细胞的邻居组合。标准一般细胞自动化机的操作过程是：某个元胞单元在时刻的属性情况将受到该元胞单元时刻的属性情况及其邻居范围内邻域细胞属性情况的影响，即，时刻元胞范围空间内的元胞将依据规划好的元胞转变状态法则达到细胞属性情况的改变。元胞范围内的元胞属性情况表现为在离散时间维度上的不断变化。即：（3-7）公式中，表示元胞在时刻的状态；表示元胞在时刻的属性情况；表示元胞在时刻邻居元胞的属性情况；表示元胞转变状态法则。细胞及其属性情况(Cell&CellStates)。元胞(Cell)或者叫做元胞单元（CellUnit），是细胞自动化机模型中最基本的不可再分的单元，分布在一、二、三、或高维欧式空间网点内。元胞的外在属性情况即是细胞状态（CellState），可以用整数形式，也能用二进制{0,1}的形式来表示其状态值。通常来讲，一般的细胞自动化机模型，元胞通常只有一种情况来表示其外在属性，而复杂的元胞自动机模型可以再定义元胞状态特征，使元胞单元同时可以有多个属性情况。元胞范围(Lattice)。元胞范围就是元胞单元所处的欧式空间网格组合，它能变化到多维的欧式空间，维数越多，模型越复杂。在实际应用中主要是一维和二维的元胞范围。将一维细胞自动化当作解说模板，全部的细胞单元都只能有前后变化，元胞范围类型很简单，都是一样的。但是二维或更高维数的元胞范围来说，基于元胞固有属性的差异可以划分出不同类型的元胞空间。将二维细胞自动化当作解说模板，二维细胞自动化机模型的元胞范围可以按照三角网格、四角网格和六角网格三种类型，如图3-5所示。（a）三角网格（b）四角网格（c）六角网格图3-SEQ图\*ARABIC\s15二维元胞空间结构示意图元胞网格在学术讨论中可以是任意变化的，细胞范围学术讨论时能在所用维度上任意扩展变化，可以从一、二、三、四延伸到更高维度，这样考虑是便于理论分析研究。但是在现实环境下，由于当前的技术还不能达到学术讨论设想的需求，所以，必须划出范围边界。目前，实际中主要有固定型、波动型和回弹型三种范围边界类型（段晓东等，2012）。邻域(Neighbors)。元胞邻居(Neighbors)是指中心元胞单元四周的邻居元胞依据某种样式组成的邻居元胞组合，它在一定程度上影响中心元胞单元在下一时刻是否发生状态转换的概率，是元胞自动机模型中重要的组成部分。空间维度不同的细胞自动化机模型，其邻居空间范围是不一样的。将一维细胞自动化当作解说模板，以中心元胞为原点以为半径画圈，落在圈内的所有元胞都是邻居元胞。二维或更高维度的细胞自动化机，其邻域定义则复杂的多，将二维细胞自动化四角网格当作解说模板，包括Neumann型、Moore型、扩展Moore型和Margolus型等邻域划分类型（李学伟等，2013），详见图3-6所示：图3-SEQ图\*ARABIC\s16四方网格元胞空间的邻域划分类型①冯·诺依曼(VenNeumann)型。冯·诺依曼(VenNeumann)型是最简单的邻域空间类型，假设，以半径来确定邻居，那么，中心元胞单元(图3-6（a）中的黑色元胞)的前、后、左、右四个方向上靠近的四个细胞为中心细胞单元的邻居空间，此邻居空间的数学表达式为：（3-8）公式中，表示邻居细胞的坐标值，表示受作用的细胞的坐标值。②摩尔(Moore)型。摩尔(Moore)型是最常用的邻域空间类型，假设，以半径来确定邻居，那么，一个中心元胞单元(图3-6（b）中的黑色元胞)的前、后、左、右、左前、右前、右后、左后八个方向上依靠的八个元胞为该中心元胞单元的邻域空间，该邻居空间的数学表达式为：（3-9）公式中，表示邻居元胞的坐标值，表示中心点的坐标值。③扩展摩尔(Moore)型。扩展摩尔(Moore)型是基于摩尔(Moore)型发展来的，扩展摩尔(Moore)型是以半径来确定邻居空间，这样可以获得更多的邻域元胞(图3-6（c）)，该邻居空间的数学表达式为：（3-10）④马哥勒斯(Margolus)型。马哥勒斯(Margolus)型与冯·诺依曼(VenNeumann)型、摩尔(Moore)型、扩展摩尔(Moore)型等三种邻域划分类型差异明显，马哥勒斯(Margolus)型是统一处理一个的元胞组块，而不是单独分别处理每一个元胞单元，这样可以减少计算耗时，更快完成工作。其结构如图3-6（d）所示。转变状态法则(TransferFunction)。元胞自动化机的转变状态法则(TransferFunction)是自身最重要的组成部分，细胞自动化机的主要功能就是通过转变状态法则来展现元胞单元未来的变化过程，倘若没有这部分内容，细胞自动化机的应用范围将变的很窄，只能反映过去和现在的变化特征。有了转变状态法则，才能发挥细胞自动化机的全部功能。一般标准元胞自动化机元胞转变状态法则是指基于中心元胞单元时刻的外在属性情况和邻居元胞状态判定时刻该元胞外在属性情况的函数方程，数学表达式为：（3-11）式中，表示元胞单元时刻的属性情况；表示邻居元胞时刻的属性情况组合；表示细胞自动化机的转变状态法则。复杂的细胞自动化机是在一般标准细胞自动化机基础上改进来的，主要是对转变状态法则进行改进，主要是在转变状态法则中加入约束参数和动力参数等。中心元胞时刻的外在属性情况不仅受到中央细胞单元时刻的属性及其邻居元胞属性的影响，还受到中央元胞自身的约束参数和动力