论文部分内容阅读
元胞自动机提供了分布并行计算系统的数学模型,它在新一代计算机结构设计中有重要意义。元胞自动机在模式识别、图像处理及人工智能中有着重要应用。斑图是元胞自动机的一个重要的组成部分,它的每一步呈现出来的状态都是由斑图来表现的。一些研究结果表明,对自我复制斑图的判定可以应用于细胞组织识别,判断染色体是否具有自我复制功能,在现在比较热门的科学——生命科学中人工生命现象,计算机的虚拟实现有非常重要的意义。
本文系统介绍了元胞自动机的模型和理论研究及应用背景,综述了国内、外元胞自动机研究的进展情况;同时又对人工生命的研究范畴、应用前景等做了较系统的介绍。对任意相邻元胞自动机中的复制斑图进行了研究,发现了几种新的复制现象。拷贝复制,这种复制是在不变的模本下对原构型的拷贝,即在原构型的对角线或水平线上出现和原始构型一样的构型。扩散复制,这种复制是原模本消失了,出现对称的两个构型。远距离复制,由于远距离的作用,出现了干扰条纹,这种条纹连同初始构型也一同被复制。接着,再现了Fredkin规则元胞自动机中的自我复制斑图,主要对二维扩展Fredkin规则和三维Fredkin规则下的自我复制斑图进行了模拟。最后,对元胞自动机中自我复制斑图进行了判定。在一维的情况下,通过定义每个元胞的特征数来判断复制片段的位置以及复制的次数。在二维的情况下,基于微分方程方法提出了一种新的算法:求出两个斑图的形心和惯性矩,对两个图形进行最小像素划分,使它们在同样的尺度上进行比较,将它们的惯性主值和主惯性方向分别重合,统一放入一个区域内比较它们的特征数,从而可以判断出这两个斑图是否一致,也就知道是否出现了复制现象。如果两个图形的每一个特征数都相等,那么称这两个图形为全同的,特征数有多数相同称为大致相同,其它的情况称为模糊的。
本文成功地对该算法用VC++进行了数值实验,取得了较好的结果,表明这种算法是可行的。同时,这种算法也可以对任意两个离散二值图形的一致性进行判定,这一点将应用于社会的各个方面,给人们的生产和生活带来便利。