初等元胞自动机的界面设计及稳定性分析

　　1　引言

　　元胞自动机[1, 2](CellularAutomata,简称CA)是由大量简单一致的元素,通过简单的局部规则,组成的时间、空间和状态变量都离散的动力学系统。它最早由Von Neumann等人于20世纪40年代末最先提出, SWolfram对其进行了详细的研究[3],并对元胞自动机的演化结果进行分类。在此基础上,许多学者从理论的角度研究了不同规则时的元胞自动机演化过程及其稳定性分析。H. Lee,Y.Kawahara研究了满足线性60规则的一维元胞自动机[4];T. Sato讨论了27规则非线性元胞自动机[5]; S. Inokuchi分析了156规则元胞自动机[6],B.Martin研究了54规则元胞自动机[7],邓婷等研究了232规则一维CA的行为[8];江志松等研究了规则数为122的初等元胞自动机的复杂性[9, 10]。

　　从理论的角度推导元胞自动机的稳定性是一个复杂的过程,通常局限于某一种特定的规则。为此,本文从计算机模拟的角度,以MATLAB为开发工具,建立了所有规则下的初等元胞自动机稳定性判断模型,设计了相应的界面,并分析了不同元胞数m,不同初始状态值,不同规则数R及不同边界条件下各规则元胞自动机的稳定性,为复杂的理论推导过程提供参考及验证工具。

　　2　基本理论及概念

　　元胞自动机是一个空间、时间以及状态都离散化的动力学系统,由元胞、元胞的状态、邻居及局部规则四部分组成。一维元胞自动机中的元胞呈线性排列,元胞的状态只有两种选择,或者为“0”,代表元胞为“死”,或者为“1”,代表元胞为“生”。其邻居通常以邻域半径r确定,距离一个元胞r距离内的所有元胞均被认为是该元胞的邻居,称为一个邻域。r=1的一维元胞自动机,是最简单的元胞自动机,又称为初等元胞自动机。

　　初等元胞自动机的局部规则可表示为:

　　3　模型的建立

　　3.1　界面设计

　　在设计初等元胞自动机时采用一个m行,n列的二维数组State存储数据,m为元胞数,n为时间步。在Matlab的figure窗口中把轴划分为m×n个方格,每个格子对应数组State的一个元素。第i(1≤i≤m)个元胞在t(1≤t≤n)时间步的状态用State(i, t)来表示。元胞状态为“活”时,State(i, t) =1,显示为黑色的点;元胞状态为“死”时,State(i, t) =0,不显示。根据模型所要实现的功能,设计界面如图1所示。

　　界面包括三个初始条件输入框,一个弹出菜单框,两个控制按钮及图形输出区。用户根据需要,在输入框中输入元胞数m,需要计算的时间步n,规则数R,通过弹出菜单选择边界条件。可供选择的边界条件有4种:周期型边界条件;对称型边界条件;固定值都为0的边界条件;固定值都为1的边界条件。点击“Plot”按钮,运行程序,在Matlab工作空间输出计算结果,同时,在左侧绘图区输出计算得到的图形。点击“Close”按钮关闭界面。