数字建筑与增强打印技术中的CA算法及应用

（1）CA算法分析思想

①CA 算法模型

A.I.Adamashii 在《Identificationof fuzzy Cellular Automata》中认为：CA模型是可以被多维的具有可选整型变量值的格子，其中每个单元可以选取一个特定的集合中的某个状态，并且这些状态均 可以根据一个本地的转换功能函数作出改变，而此功能函数是由附近的其他单元的状态作为输入的因素。这个定义也就是说一个CA模型是由一系列的单元所组成的格子状系统，其中，每一个单元的值均属于某一个集合，而且，每一个单元的值由其附近的单元的前一个状态决定目前状态，依次类推，整个系统就按照此功能函数作线性或非线性状态变化。

例如：在日常生活中，有些棋类就是给出一种初始状态和一系列规则，然后，由不同的对弈者选择不同的规则根据当前棋局状态做出下一个棋局状态的预测，再作决定。当然对弈的结果只有两种可能，一方胜出或和局。

在上面的例子中，提到两个内容：一方面是系统的初始状态，一方面是系统的规则。

首先分析一下初始状态：在例子中，给出的初始状态只是不同的棋子布局，这种布局将是影响以后布局的源泉。假使在开始时给出另一种布局状态。那么，整个结局将是完全不同的。这即说明，初始状态是影响一个系统状态的因素。但是又发现即使初始状态不变，每一棋子按这些规则运行下去后，整个棋局仍是极其微妙。

接下来分析以下规则：规则是事先给出的，用来约束系统状态的条件 集合。在分析一个较为复杂的系统时，一般先选取一个有代表性的较小 的，不是太复杂的系统来分析，通过实验等方法来确定一系列有用的关系网 （规则）。一般可以认为这种分析是正确的。然后将这种规则应用于那些较复杂的系统，这样分析复杂系统时就较为容易同时可以发现将一个规则应用于一些系统中时，通常系统状态有几种结果：系统状态趋于稳态；系统状态逐渐膨胀；系统状态渐渐收缩；系统状态周期变化。

②CA算法模型的构造

a.系统分析

首先系统分析是对一个系统进行仿真分析的第一环节，只 有处理好系统分析才能有一个较好的建模，同时在建模时主要应用CA思想。在进行系统综合分析时，首先按系统的状态受影响的复杂程度将系统分为：简单系统，主要指系统内部较为稳定，同时所有输入只有内部本 地交互响应，而无外部输入响应的系统；复杂系统，一般指包括外部复合条件的响应系统，而这类系统又可以划分为多个简单系统，而这些简单系统又可以按另一种CA规则规划的系统，这里仅论述一下简单系统。

接下来的工作是对系统进行格状分割，这个过程的关键是将整个系统看作无数个小单元，而每个小单元又具有可选状态，当取一初始状态进行分析时，一定要注意，每个小单元与别的单元发生的影响作用应该是本地的，即相邻近的，同时影响单元的数目或者说决定某一单元状态的其他单元数一定要远远小于整个CA系统的单元总数，可以通过一些方法进行这个范围的调整，如实验法，主要目的是保证算法应用的独立性。

b. 初始状态的确定

初始状态指经过划分的各单元的初始值，这些状态可以是布尔值或者一段连续变量值，这里关键是注意初态要具有代表性和一般性全面性，当然，对于已经简化了的CA单元，对其进行全面分析并不十分困难，所以应尽量考虑到初始状态本身以及其受影响后，响应的种种状态变化，否则还要进行细分，或对其状态进行分段整合。(www.xing528.com)

c.规则构造

在经过以上两个步骤以后，就可以来确定整个系统的规则。在确定CA规则时要考虑以下内容：

系统单元维数，维数是确定规则的基本要素，只有确定系统细分后的维数才能考虑从什么样的基本规则入手，才能考虑某一个单元是受线性影响还是受 非线性或复合影响。

单元响应半径，一般在用CA算法分析时都要确定单元响应半径，也就是单元对那些相邻单元状态的刺激进行响应，它们的范围怎样，例如一维系统半径就是影响其单元状态的前几个和后几个单元所在的范围，而二维可以确定圆形或方形半径范围。

响应的重数及各重属性，在一个本地响应范围内，有可能某个单元是几重状态响应叠加下做出的响应，这时就将每一种响应关系进行综合。注意在进行分析时必须要全面而准确。

规则的时间和空间处理，CA算法处理系统并做出系统状态预测时都要考虑到时间和空间段的处理，因为单元响应都是时空相关的，所以确定的系统状态也是时间，空间相关的。

规则的构造源，规则如何得出是整个规则构造的核心，同时，此规则确定的正确与否直接关系到系统状态预测的成功与否，规则确定是一个总结和完善的过程，有很多手段可以用来确定规则，如实验观察法等。

（2）当前CA思想应用的范围

早先J.von Neumann将CA系统看作一个由许多单元格所组成的可以自我进化和配置的整体其中每个单元格拥有5个相邻的单元格，并且每个单元格的状态可以取2种。这是CA系统最先应用的雏形，随后CA思想的理论和应用逐渐扩展到许多分散的领域，例如：图像识别，生物建模，以及各种物理系统，计算机并行处理，等等。

近年，通过对常规CA系统的体系研究，已经较为清晰的将CA系统划分为引人注目的几种类型。应用于本地相邻的一维CA系统的静态机制最早是由 Wolfiam在他的经典文章里提出的。接着Martinetal应用代数多项式将一维CA 系统的特点表达出来。更为通用的基于代数矩阵的工具是由Dasetal在刻画附加CA系统的行为特性时提出的。

在最近20年来，基于CA思想的更为广阔和多样的应用被提出来，主要的应用可以归类为17种：物理系统的仿真，如一些对生长过程的模型化进行仿真，裂变反应系统的仿真，流体力学的仿真和类孤立系统的行为仿真；生物的模型化，包括可自我再生模型，生物体系及其处理，脱氧核糖核酸（DNA）序列；图像处理；语音识别；分类计算及素数生成的计算；仿真机；计算机体系结构；自测安装（BIST，Build-In-Self-Test）结构用于伪随机性，伪彻底性，确定性图案生成和信号处理；简单可测试性有限状态机（FSM）的综合；编码校错；伪相连存储器；通用及完善的哈希函数生成；波段失效诊断；P模式乘法器；块状和流线型密码系统；断裂学；混沌学。