【WORD可复制可编辑】元胞自动机之蚂蚁规则的编程实现
元胞自动机之蚂蚁规则的编程实现
王李斌，邵长金，杨振清
中国石油大学数理系～102249
Email: binrice@hotmail.com
摘 要:本文应用元胞自动机的思想对蚂蚁规则进行了编程实现。从文中可以发现微观上极 其简单的运行规则可以产生复杂的宏观规律。
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
明元胞自动机方法是一种对于复杂物理问题 研究极有潜力的手段。
关键词:元胞自动机, 蚂蚁规则～数值模拟
1. 引言
元胞自动机(cellular automata 或 cellular automaton, CA)是一种时间、空间、状态都离散 的动力学模型，是非线性科学的一种重要研究方法，特别适合于复杂系统时空演化过程的动 态模拟研究。
蚂蚁规则是 Chris Langton 和 Greg Turk 发现的元胞自动机[2]，该规则通过执行极简单 的运动算法来模拟假想的动物(蚂蚁)行为，蚂蚁在方形网格上运动，格位为白色或灰色， 当蚂蚁进入白色元胞时，它向左转 90?并把该元胞涂成灰色。类似的，如果蚂蚁进入灰色元 胞，它向右转 90?并将该元胞涂成白色。
2. 编程实现
这里，用 VC 程序设计语言对以上元胞自动机规则进行了实现。
2.1 程序功能
程序能自定义空间尺寸，即网格数目，每个网格的宽度。能够在网格空间中加入任意个 指定方向的蚂蚁。并且能以一定时间间隔一步步行走，并实时显示行走结果。此外，还能直 接运行到指定的时步然后停止。在步进或者直接运行的过程中，能够中途暂停或者继续。
-1-
2.2 程序结构
程序总体
框架
财政支出绩效评价指标框架幼儿园园本课程框架学校德育工作框架世界古代史知识框架质量保证体系框架图
采用了 VC6.0 MFC 的文档视图结构。通过应用程序向导自动生成程序的 总体框架。此外，再新增了一个类，用以实现蚂蚁规则相关的数据结构和操作。这样整个程 序由五个类组成:应用类，主框架类，文档类，视图类及蚂蚁规则核心类。各个类之间的关 系见图 1。
应用类
主框架类 视图类 文档类
蚂蚁规则类 图 1 程序结构图
2.3 蚂蚁规则类的设计
现在详细介绍一下蚂蚁规则类数据结构、数据成员和相关方法。另外的四个类由 VC 应 用程序向导自动生成，本项目只是在其基础上作了一些小的修改，因此不做过多的说明了。
定义数据结构:
网格单元，CCell: 用以描述网格单元的各种信息，包括此网格的水平位置，竖直 a)
位置，状态信息(有无标记)，边界信息(是否是边界)。定义如下:
typedef struct tagCell { 水平位置 int x; // 竖直位置 int y; // 状态,0--无标记 白色,1-有标志 灰色 // int status;
int isBorder; // 1—是, 0—不是
}CCell;
蚂蚁结构，CAnt: 用以描述每个蚂蚁的各种相关信息，包括当前的位置，当前的运 b)
行方向及当前已经行走的时步数。定义如下:
typedef struct tagAnt {
CPoint curPos;// 当前位置
-2-
当前运行方向 int direction; // 当前的步数 int curStep; //
}CAnt;
数据成员:
网格:m_cells, 存放整个离散空间数据，定义:CCell** m_cells a) 蚂蚁:m_aAnts, 存放所有加入的蚂蚁数据，定义:CArray
m_aAnts b) 运动范围:m_oSize, 存放离散空间(即空间网格)的大小，定义:CSize m_oSize c)
相关方法:
初始化, Init(): 实现模型的初始化，清除原有数据开始新的
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
a) 设置空间尺寸，建立模型, SetRange():开始一个新的分析，设置空间尺寸 b) 加入蚂蚁, AddAnt():在空间加入一个蚂蚁 c) 向前迭代一步, StepIn():进行一次迭代操作，更新空间及蚂蚁的状态 d)
程序运行流程 2.3
这里介绍一下程序的运行流程。
程序启动后的运行界面如图 2。
首先进行网格设置，在界面左边的―网
格设置‖栏中输入相应的数据，点击产生网
格，将会在右边生成相应的网格。
然后，在―引入蚂蚁‖栏中输入要加入蚂
蚁的位置和方向，点击加入蚂蚁，完成一个 指定位置和方向的蚂蚁的加入。还可以在右
边的网格中双击鼠标左键实现加入一个蚂
蚁。 最后，如果顺利完成上面两步设置，现
在就可以进行具体的模拟了。在―行走设置‖
栏中输入步进运行的时间间隔，单位毫秒， 及
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
行走的步数。这些设置好后，点击―动
画步进‖，程序将每迭代一个时步就显示一
下运动后的空间状态。点击―走到最终‖，程 图 2 程序初始界面 序将会直接运行到上面设定的步数后显示
―继 最终运行结果。这中间可以按―暂停‖或
-3-
续‖以暂停运行或恢复运行。
3. 模拟结果
下面将使用此程序分别对空间只有一个蚂蚁的情况或同时拥有多个蚂蚁的情况运行进 行进行模拟。
3.1 一个蚂蚁的情况
这里先在网格中只加入了一个蚂蚁进行模拟。结果发现，这个蚂蚁表现出很复杂的行为。 蚂蚁开始时是从完全白色的空间出发，经连续的约 400 时步后，它实质上又回到了原来的位 置(见图 3)，这之后进入混沌阶段，这期间的运动不可预测(见图 4)。然后，这个极不规 则的运动经约 10000 时步后，蚂蚁突然又表现出极规则的动作，这使它开始远离起始位置(见 图 5)。
在蚂蚁运动的最后一个阶段，蚂蚁为逃出这个混沌的初始区而开辟的路叫公路[3]。这条 公路与网格方向呈 45?角，蚂蚁按照缝纫机方式行进。如果没有边界，蚂蚁将远离中心。
图 3 第 391 步，一个蚂蚁 图 4 第 7000 步，一个蚂蚁 图 5 第 10500 步，一个蚂蚁
3.2 多个蚂蚁的情况
这里对在网格中加入多个蚂蚁的情况进行了模拟。图 6 是在网格中加入 9 个蚂蚁的初始 情况。图 7 是这 9 个蚂蚁运行到 250 个时步时的情况，表现出一种混沌状态。图 8 是这 9 个蚂蚁运行到 1250 个时步时的情况，从图中可以看到，左边已经有两个蚂蚁开辟出了自己 的公路，并不断远离初始位置。多个蚂蚁相互作用，使开辟公路的时间明显减少。
-4-
图 6 第 0 步，9 个蚂蚁 图 7 第 250 步，9 个蚂蚁 图 8 第 1250 步，9 个蚂蚁
3.3 蚂蚁可访问区域无界性
Langton 蚂蚁规则的一般结果是，在蚂蚁的运动过程中，无论初始空间结构怎样(灰色 或白色元胞的构形)，蚂蚁访问的是无边界的空间区域。Bunimovitch 和 Truobetkoy 发现的 定理证明了这一观察结果。
证明如下:假设蚂蚁访问的区域是有界的，那么这个区域包含有限数量的元胞。因为迭 代次数是元限的，所有往往有一个可无限次访问的元胞区，也可垂直地进入(称之为 V 元 胞)元胞区。因为蚂蚁在每一时步之后都呈 90?转行，故 H 元胞由 4 个 V 元胞包围，反之 亦然。因此 H 和 V 元胞处在固定棋盘图形的网格上。现在，考察区域的最右上元胞，它的 上和右邻居不能衩访问，如果蚂蚁轨道有定界，则这个元胞存在。如果这个元胞为 H 元胞 (且永远如此)，则进入这个元胞必然从左侧水平方向并垂直向下退出这个元胞，因此这个 元胞必然是灰色的。然而，蚂蚁离开后，元胞为白色，存在矛盾。如果元胞为 V 元胞，则 也存在同样的问题。所以蚂蚁轨道无定界[1]。
4. 结论展望
这里应用元胞自动机的思想对蚂蚁规则进行了编程实现。从文中可以发现微观上极其简 单的运行规则可以产生复杂的宏观规律。表明元胞自动机方法是一种对于复杂物理问题研究 极有潜力的手段。
Langton 蚂蚁元胞自动机的规则虽然极简单，却能产生超乎想像的复杂行为。不知何故， 这实乃典型的元胞自动机方法:虽然我们知道所有有关控制系统的基本法则(因为是我们自 己制订的规则)，但往往不能解释其宏观行为。与平常的科学方法不同的是:一般地，物理 学家只理解(通过试验)系统的总体性质，根据这些性质，试图寻找出普遍的法则。元胞自
-5-
动机例子表明，从哲学的观点看，基本法则是非常重要的，但并不完备，物理过程的完整知
识需要微观和宏观水平认识[1]。
参考文献
[1] Bastien Chopard, Michel Droz 著, 祝玉学, 赵学龙译. 物理系统的元胞自动机模拟. 北京: 清华大学出
版社, 2003.
[2] I. Stewart. The ultimate in anty-particle. Scientific American, pp.88-91, July 1994. [3] J. Propp. Trajectory of generalized ants. Math. Intelligencer, 16(1):37-42,1994.
The Implementation of a Cellular Automata –-Ant Rule with a
Programming Language
Wang Libin, Shao Changjin, Yang Zhengqing
The Department of Math and Physics, China University of Pertroleum, Bei Jing, 102249
Abstract
In this paper, a cellular automata –ants rule has been implemented with a programming language. It can be seen that very simple motion rules in micro scale can make very much difficult law in macro scale.
It seems that celluar automata method can be a method of great potential in the study of complicated
physical problems.
Keywords: cellular automata, ant rule, numerical simulation
-6-
浙公网安备 33021202002483