第27卷第2期
2005年6月南昌大学学报・工科版
Journal of Nanchang University (Engineering &Technol ogy ) Vol . 27No . 2
Jun . 2005
文章编号:1006-0456(2005) 02-0024-04
一种用于微观组织模拟的
三维元胞自动机模型
许林, 郭洪民, a
b
a
(南昌大学a . 机电工程学院, 江西南昌330029; b . )
摘要:, 问题, 如材料微观组织的演变模拟. C ++计算机语言, 运用OpenG L 图形函数. , 因此可以根据需要进行扩展. 由于运用了OpenG L , 并可以从多角度进行观察. 文中运用该模型进行了简化的枝晶生长模拟, 验证了该模拟的正确性.
关键词:; 三维建模; OpenG L 中图分类号:TP39119 文献标识码:A
元胞自动机(CA ) 是建立于细胞发育演化基础
[1]
上的时空离散、状态离散的并行数学模型. 从历史角度看, 元胞自动机最早是由数学家、物理学家John Von Neu mann 和Stanisla w U la m 在1940年提出[2]
的. 从应用角度看, 直到John Hort on Con way 在1960年运用元胞自动机建立了一种“生命游戏”[3～5]后, 元胞自动机才得到了广泛的运用. 80年代, 由于元胞自动机这类简单模型能十分方便地复制出复杂的现象或动态演变过程中的吸引子、自组织和混沌现象, 从而引起了物理学家、计算机科学家的极大兴趣, 并在许多领域得到了应用, 如混沌、分形的
[6][7][8][1]
产生, 模式分类, 智能材料, 复杂现象等, 并提出了许多变形的元胞自动机, 如以凝固理论为
[9][10]
演化规则的元胞自动机, 模糊元胞自动机, 神
[11]
经元胞自动机等. 根据元胞自动机中元胞的空间展布, 可将元胞自动机分为一维和多维(二维、三维等) 的.
OpenG L 是在SGI 、M icr os oft 、DEC 等著名计算机公司的倡导下, 基于SGI 的G L 图形标准制定的一
[12]
个通用共享的开发式三维图形标准库. 它是一种过程性而不是描述性的图形AP I . 它与操作系统无关, 用OpenG L 编写的应用程序可以很容易移植到支持OpenG L 的操作系统, 例如UN I X . 由于它出色的3D 功能使得其在实现实时三维、科学计算可视化等方面得到了广泛的应用. 本文的目的是建立一种用于微观组织模拟的三维元胞自动机模型并使其
能够根据需要进行扩展.
1 模型描述
111 元胞自动机的定义
1) 计算定义(Computati onal Definiti on )
[13]
用元胞自动机进行模拟计算时, 通常将其视为一类算法. 因此可将其作为计算机程序代码按照如下步骤在计算机上运行:
①定义存储元胞状态的元胞数组, 这里元胞数组对应于元胞空间, 数组元素对应于元胞, 数组元素的值对应于元胞的状态;
②定义一系列根据局部规则改变元胞数组元素值的函数;
③在每个时间步内, 运用函数同步更新元胞数组元素的值.
2) 物理学定义(Scientific Definiti on ) 元胞自动机最基本的组成部分包括元胞(cell ) 、元胞空间(lattice ) 、邻居(neighbor ) 及演变规则(rule ) . 它是定义在一个具有离散、有限状态的元胞组成的元胞空间上, 并按照一定局部规则, 在离散的时间维上演化的动力学系统. 具有如下属性:
①构成元胞自动机的部件被称为“元胞”, 每个元胞的状态是离散有限的;
②元胞规则地排列在被称为“元胞空间”的空间网格上;
③元胞的状态随着时间变化, 根据一个“局部
收稿日期:2004-09-03
基金项目:江西省自然科学基金资助项目(0250006) ; 江西省科技厅资助项目作者简介:许林(1980-) , 男, 硕士研究生.
第2期 许林等:
一种用于微观组织模拟的三维元胞自动机模型・25・
规则”进行更新, 也就是说, 一个元胞在某个时刻的状态值取决于且仅仅取决于上一个时刻该元胞的状态以及该元胞所有邻居元胞的状态;
④元胞空间内的元胞按局部规则进行同步状态更新, 整个元胞空间则表现为在离散的时间维上的变化.
112 三维元胞自动机在计算机上的实现
邻居) ;
4) 假定元胞凝固后始终保持固相, 即不考虑固相的重熔;
5) 演变规则:元胞状态由元胞本身的状态值与邻居元胞的状态值之和决定. 即:
t +1t S i =f (σi )
σt i =S t j
j ∈NN
本文程序中定义了节点类、元胞类用于空间元胞的产生, 的邻居, 改变. 程序实现顺序如下:
1) 在X 、Y 、Z , 包括节点坐标、2) (立方体和球) , 包括元胞号、包含的节点等;
3) 定义这些元胞对象的邻居元胞, 根据不同的邻居类型定义;
4) 局部规则函数可以根据具体模拟情况进行定义, 在本模拟中定义了一种简化的枝晶生长规则函数.
113 计算机上运用OpenG L 实现三维环境的关键
式中, f 值域为0或1, m 为
.
211 模拟结果
本文按上述三维枝状构型元胞自动机模型中提出的规则进行了模拟. 当在模拟空间内设一个元胞的状态值为1时, 可能出现四种生长行为:
1) 无生长现象:f (σ) =0, σ∈[0, m ];2) 生长成平面板状(三维立方体) 结构:f (σ) =1, σ∈[0, m ];
3) 生长成非晶态:f (σ) =1, σ=2; 4) 呈枝状结构生长, f (σ) =1, σ=2. 本文中按照第4种规则进行模拟, 结果如图1, 图2, 图3所示
:
技术
1) 重新设置窗口象素格式, 使其符合OpenG L
对象素的需要, 并按OpenG L 的要求设置好窗口的属性和风格;
2) 先获得W indows 设备描述表, 然后将其与事先设置好的OpenG L 绘制描述表联系起来;
3) 调用OpenG L 命令进行图形绘制和坐标变化实现三维效果;
4) 退出程序, 释放OpenG L 绘制描述表和W in 2dows 设备描述表.
114 三维枝状构型元胞自动机
枝晶生长是非平衡态结构模式形成的典型实例. 由于自身动力学的不稳定性, 微观层面的简单行为可导致宏观上非常丰富和复杂的结构. 最简单地表述过冷熔体中枝晶形貌演变的确定性三维元胞自动机模型可表述为:
1) 元胞形状:立方体;
2) 元胞状态:0代表液相(未凝固) , 1代表固相(已凝固) ;
3) 邻居结构:6邻居(最近邻, 类似与二维中的Von_numann邻居) , 18邻居(最近邻和次近邻, 类似
图1 二维的Von -nu mann 邻居与三维6邻居模拟的对比
212 讨论
与二维中的Moor 邻居) , 26邻居(元胞的最近一层
模拟结果中产生的枝状结构具有典型的自相似
n
性. 每2时间步后, 生长结构为立方体, 之后在各个顶角方向生出枝状臂, 然后所有分枝生长到彼此内
・26・南昌大学学报・工科版2005年
自动机. 由于C ++语言良好的可移植性以及Open 2
G L 图形函数库的与系统无关性, 所以该模型可以根据需要很容易的进行扩展和移植. 运用简化的枝晶生长规则对不同邻居情况下三维枝晶生长进行了模拟并与二维的模拟情况进行了对比, 验证了该模型的正确性.
:
[1]-、方法和意义[M].北
, 1994. 69-76.
[2mann, J Burks, A W. Theory of Self -Rep r odu 2
cing Aut omata [M].U rbana:University of Illinois Press, 1966.
[3] Martin Gardner . The Fantastic Combinati ons of John Con 2
way’s Ne w Solitaire Ga me of "L ife" [J ].Scientific Ameri 2can, 1970, 223(4) :120-123.
[4] De wdney A K . A cellular Universe of Debris, D r op lets,
Defects and De mons[J ].Scientific American, 1989, 261(2) :102-106.
图2 二维的Moor 邻居与三维18
邻居模拟的对比
[5] De wdney A K . The Cellular Aut omata Pr ogra m s That Cre 2
ate W ire world, Rug world and O ther D iversi ons [J ].Sci 2entific American, 1990, 262(1) :146-149.
[6] Karel Culik, Si m ant Dube . Fractal and recurrent behavi or
of cellular aut omata [J ].Computing and I nfor mati on, 1989, (3) :253-267.
[7] Tzi onas P G, Tsalides P G, Thanilakis A. A New Cellular
Aut omata -based Nearest Pattern Classifier and its VLSI I m p le mentati on [J ].I EEE Trans Very Large Scale I ntegr (VLSI ) syst, 1994, 2(3) :343-347.
[8] Ame m iya Yoshihit o . I nf or mati on Pr ocessing U sing I ntelli 2
gentM aterials -inf or mati on -p r ocessing A rchitectures f or Material Pr ocess ors [J ].Journal of I ntelligent M aterial Syste m s and Structures, 1994, 5(3) :418-423. [9] 郭洪民, 刘旭波, 杨湘杰. 元胞自动机法模拟微观组
图3 三维的26邻居模拟循环14次
部, 又形成立方体, 如此反复. 从图3中可以明显看出这种现象.
从模拟结构可以看出, 演变规则4简单的局部作用可产生整体上的复杂枝晶结构. 由于模拟没有考虑金属凝固的物理意义, 如凝固过程中的热传导、随机形核、结晶潜热的释放等因素, 所以与实际金属凝固枝晶组织存在比较大的差异. 但本文的目的是建立一种模型框架, 可以根据具体研究内容, 加入相应的物理意义, 将此模型框架进行扩展.
织演变的建模框架[J ].材料工程, 2003, (8) :23-27.
[10]姚国正. 神经形态发生的一种细胞自动机(CA ) 模型
[J ].科学通报, 1991, 19:1496-1499.
[11]郭燕利, 胡建军. 利用OpenG L 三维图形库进行三维实
体造型[J ].微型电脑应用1998, (6) :93-96.
[12]凌云, 储林波. 用V isual C ++中的M FC 和OpenG L 建
立三维图形应用环境[J ].微型机与应用, 1998, (4) :8
-10.
[13]郭洪民. 元胞自动机法模拟铝合金凝固组织形态演变
[D].南昌:南昌大学, 2003.
3 结论
本文建立了一种用于微观组织模拟的三维元胞
第2期 许林等:
一种用于微观组织模拟的三维元胞自动机模型・27・
A Three -D i m ensi onal Cellul ar Auto maton M odel
for M i crostructure Si m ul ati on
XU L in , G UO Hong -m in , Y ANG Xiang -jie
a
b
a
(a . School of M echanical and Electrical Engineering, N anchang U niversity, N anchang ; b . School of M aterial Science and Egineering, N anchang U niversity, N anchang )
Abstract:The cellular aut omat on is an ideal model f or a lex m; the p r oble m about the comp lex dyna m ic syste m , such as the si m ulati on f or m of materials .
It is als o
easy t o be used in the computer . I n the paper, we a three -di m ensi onal cellular aut omat on model by C ++.This model which the classic cellular aut omat on has . So this model can be expanded ments . Because we use the 3D technol ogy of OpenG L, the si m ulati on it can be watched fr om different angles . idate the validity of .
Key W ords:cellular aut omat on; three -di m ensi onal model; OpenG L
I n the paper, we use the
model t o si m ulate of branch model . W e compare the 3D results with the 2D results, which val 2
(上接第23页)
并应用其解决一种新型微小机器人设计中遇到的困难, 即获得了对复合球副的方案设计和对柔性铰链的技
术设计, 但该理论还处于发展阶段, 40条发明原理, 39个通用工程参数、冲突矩阵还有待于进一步的完善, 紧密跟踪T R I Z 理论的发展动态, 能为我们的创新设计工作提供更强大的支持.
参考文献:
[1] 檀润华. 创新设计-T R I Z:发明问题解决理论[M].北京:机械工业出版社, 2002.
[2] 乐万德, 王可, 吴通, 等. 基于TR I Z 的产品概念设计研究[J ].机械科学与技术, 2003, 22(4) :531-534.
[3] 蒙运红, 吴昌林, 黎星. 创新思维的程式化方法-TR I Z 之一:解决矛盾的理论[J ].机械设计与研究, 2002(增刊) :45-46.
[4] 薛实福, 李庆祥. 精密仪器设计[M].北京:清华大学出版社, 1991.
The Appli cati on of Theory of I nventi ve Proble m Solvi n g i n
a New M i cro -Parallel Robot Desi gn
ZHOU Yan -hui, LUO Yu -feng, T ANG Man -hua, SH I Zhi -xin
(School of M echanical and E lectrical Engineering, N anchang U niversity, N anchang 330029, China )
Abstract:This paper intr oduces one theory within T R I Z, the p r ogra m method of s olving conflict . It includes for 2ty inventi on p rinci p les, thirty nine general engineering para meters, the separate p rinci p le, the conflict matrix and its app licati on . Then, the theory is used t o s olve the technol ogy conflict in a ne w m icr o -parallel r obot and the usage of the conflict matrix, and a ne w kind of compound s pherical j oint is designed . Finally, the analysis of physics conflict of the flexible j oint structure in a ne w m icr o -parallel r obot carried on, the usage of the separate p rinci p le dra ws a conclusi on corres pondingly .
Key W ords:theory of inventive p r oble m s olving; conflict; r obot; ne w compound s pherical j oint; flexible j oint