二维元胞自动机

二维元胞自动机（精选7篇）

二维元胞自动机 篇1

0 引 言

研究人员提出了一些基于元胞自动机的加密算法[1,2]。建立在二维二值元胞自动机演化基础上的密码系统难以被破解,因为其可逆性是NP问题,可以抵抗密码分析的攻击[3]。本文的加密系统正是基于此,优势如下:半并行操作加快了加密速度;密钥空间大大提升;破解难度显著增加。

1 二维触发元胞自动机理论

元胞自动机最常见的是一维和二维[4]。二维元胞自动机被定义为元胞的点阵,可根据一些规则进行编码[5]。有三种相邻位配置,如图1所示。

在所有2n个规则中有一系列被称为触发规则的规则,其特性是在不改变其他相邻位的前提下,改变触发位的值将会扭转规则的运算结果。以冯诺依曼型相邻位配置为例,选择标示为“E”的元胞作为触发位,触发规则可表示为:

a${}_{i+r,j+r}^{t+1}$=ϕ(a${}_{i-r,j-r}^t$,...,a${}_{i,j}^t$,...,a${}_{i+r,j+r-1}^t$)XORa${}_{i+r,j+r}^t$ (1)

式(1)可被表示为用2n-1项确定的真值表的值,令规则运算结果为1与令其为0的触发位值模2互补(见表1)。

2 二维触发元胞自动机加密算法描述

2.1 规则设计

参考图1,摩尔型无法进行半并行编码,扩展冯诺依曼型结构过于笨重。因此本系统采用冯诺依曼型相邻位配置,在设计时采用式(1)。规则由触发规则和非触发规则组成。触发规则的加密解密路径具有唯一性,而非触发规则却不唯一,所以只能选取触发规则。本系统在设计时回避了对所选取的规则是否为触发规则的判定,即读入相邻位时少读一位,默认未读入位就是触发位。在将规则转为二进制时,原来需转成24*r位,现只需(24*r-1)位,这样所用规则就是触发规则。

2.2 加密算法

加密过程使用两个相互独立的密钥:密钥1即为上述触发规则;密钥2由一组连接位组成,数目为2×r×(X+Y),其中X和Y是信息位矩阵的边长。根据文献[1]所述,取X=Y=N=32。以3×3明文矩阵详述加密过程:将明文转换为二进制,每次读入9位填入编码矩阵,再填入连接位。加密是多轮反向编码的过程,即按照规则将t+1时刻触发位的值编码为t时刻的值。首先按序读入除触发位以外的相邻位,然后查找规则真值表,如图2中明文第一位为1,按冯诺依曼型配置以中上左下的顺序读入各相邻位是1111;查表1最后一行第二列t+1时刻触发位值与之相同,则编码为1。可对每一列各位并行编码。

①由西向东 ②由北向南 ③由东向西 ④由南向北

一轮加密由四步编码组成,如图2所示,每步编码都是将3×3矩阵周围连接位顺时针旋转90度。因连接位分布离散,只能逐行/列编码。经分析,作者提出:放弃连接位顺时针旋转,采用待加密矩阵逆时针旋转的方法。旋转后坐标计算公式如下:

顺/逆时旋转90度行/列坐标=原列/行坐标

顺/逆时90度列/行坐标=(N+1)-原行/列坐标

这样使得每一步编码操作都按式(1)进行,不需更换触发位的位置。否则不仅加大了坐标编码的复杂度,而且更换触发位使工作量增加了三倍。所以该方法对精简程序起了很大的作用。

2.3 解密算法

解密过程就是将加密四步顺序进行反置,先由南向北编码,再依次由东向西,由北向南,由西向东。需注意以下三点:第一,解密的过程将矩阵顺时针旋转90度;第二,解密操作编码时相邻位的读入顺序应与加密时一致;最后,解密是从信息位矩阵第32列编码至第1列。

3 算法实现

程序实现大致分为如下步骤:

加密算法有三重循环,最内重循环对待操作矩阵的信息位进行半并行编码,第二重是四轮编码,第三重循环按序每次对1024位明文密文进行操作。关键部分是实现单个元胞的状态编码,再通过循环完成所有元胞的状态编码。

(1) 读入各相邻位

radius为元胞自动机的半径,p_ma数组存放的是待编码矩阵,p_ruletablearray存放从矩阵中提取的相邻位。i2和i3标明待编码位的位置,j2和j3用于控制读入。将待编码位半径以内的相邻位按右下左上中的顺序读入。

(2) 转换为相应的十进制去查触发规则表

将p_ruletablearray中的各相邻位转换为十进制数,附值给变量k。

(3) 进行加密编码

查找存放触发规则的p_togglearray数组的第k位,所得结果与待编码位异或,得编码结果。

4 安全性分析

常规加密的安全性取决于密钥的安全性,而不是算法的安全性。因此,密钥空间对于安全性来说非常重要[6]。二维触发元胞自动机加密系统的密钥空间由演化半径、规则、轮数和连接位组成:规则的密钥空间为224*r;半径和轮数的密钥空间原理上为无穷大,实现时演化轮数采用long double型,密钥空间为264;连接位密钥空间为2128×r。综上,系统密钥空间为2128*r+24*r+64。

利用本文实现的密码系统对由56个单词“alex”组成的信息进行加密。令轮数为32,规则和半径均为1,加密程序自动产生128位随机位作为连接位,加密结果如图3所示。

r=1时最坏情况需尝试2208次。当r的取值大于5时,攻击者至少尝试21049280次以上,使得蛮力攻击变得不可能。

5 结 论

本文介绍了元胞自动机的相关理论,研究如何应用二维触发元胞自动机原理实现加密解密系统,编程实现时采用VC++6.0作为开发平台。与AES等加密算法相比,二维触发元胞自动机的密钥空间要大得多。而且元胞自动机具有单元的简单规则性、单元之间作用的局部互连性和信息处理的高度并行性等优点。根据文献[1]中的分析,二维触发元胞自动机只需要几步就可以使误差扩展到整个密文,避免密文中的相似性问题,从而能够抵抗蛮力攻击和差分分析方法攻击。

参考文献

[1]Maria Madiarova,Mitsugu Kakuta,Takashi Obi,et al.Opto-Electronic Block-Cipher Based on Iteration of the2-D Toggle Cellular Automata.Algorithm,1999,6(2):110-117.

[2]Gutowitz H.Cryptography with dynamical systems.In Cellular Automata and Cooperative Systems.Kluwer Academic Publishers,1993:237-274.

[3]Durand B.ArandomNP-complete problemfor inversion of2-D cellular automata.Theoretical Computer Science,1995,148:19-32.

[4]张传武,彭启琮,朱甫臣.细胞自动机置换群加密技术研究.计算机科学,2003,30(3).

[5]Jorg R Weimar.Coupling Microscopic and Macroscopic Cellular Autom-ata.Parallel Computing,2001,27:601-611.

[6]杨明,胥光辉,齐望东,译.密码编码学与网络安全:原理与实践.第二版.北京:电子工业出版社,2001.

基于元胞自动机的软件架构设计 篇2

细胞通过分裂繁殖、自我复制演进出各色庞杂的生物体征,元胞自动机理论(CA)正是受此启发而建立:通过元胞抽象构造简单模型,通过演化规则的定义搭建可循环迭代的平行算法,进而演算出复杂系统[1]。该思想现在已经成功运用于物理系统[2],经济系统[3],交通系统[4],自然灾害系统[5],历史系统[6]等各个方面。

但是关于元胞自动机在软件架构设计方面的应用却尚不多见。对于业务类型迥异的软件系统是否也能通过元胞抽象、规则定义找到一套行之有效的通用的架构设计方法呢?经过笔者多年研究,并将其应用在公司商业软件领域,构建了公司商业软件核心架构Foreversoft Soft Architecture(以下简称FSA),本文将主要介绍该套体系架构。

1元胞自动机概述

元胞自动机实质上是一种时间和空间离散的动力系统。散步在规则网格中每一元胞取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。元胞自动机不由严格定义的物理方程或函数确定,而采用一系列模型构造的规则构成,凡是满足这些规则的模型都可以认作是元胞自动机模型[7]。

元胞自动机是一类模型的总称或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,而其状态改变的规则在时间和空间上都是局部的。元胞自动机的构建没有固定的数学公式,构成方式繁杂,变种很多,行为复杂。

元胞自动机最基本的组成单位包括元胞、元胞空间、邻居及规则4个部分组成,其形式化定义如下[8]:

元胞自动机是一个四元组{n,S,N,f}其中:

n为元胞空间的维数;

S为元胞有限状态集,S={s1,s2,…,sk};

N为离散空间Zn的矢量组成的v元组,即元胞的邻居,N={x1,x2,…,xv},其中,xi是邻居元胞相对给定中心元胞的位置;

f为局部规则,其中: f:SN→S。

元胞自动机具有以下特征[2,9]:

(1) 同质性 在元胞自动机模型中制定的相同演化规则决定着其中各个元胞的演化过程。

(2) 离散性 在元胞自动机模型中,各个元胞的状态都是分离的,在时间和空间中具有离散性。

(3) 同步计算 在元胞自动机模型中,当前时刻各个元胞的状态演化都是相互独立的,而且演化过程多是同步进行的。

(4) 时空局部性 在元胞自动机模型中,当前时刻各个元胞的状态都是由其周围的邻居在前一时刻状态决定的,而邻居的确定主要是由半径所决定的,这也就是所谓的元胞自动机在时间和空间上的局部性。

近年来,为了逼真地模拟复杂的自然现象,出现了突破传统元胞自动机网格结构、实现方式限制的设计。譬如,每个元胞的状态更新函数可以是不同的,也可以在更新方式上是不同步的,甚至干脆引入概率机制灵活设计网络结构和作用方式,这样在模拟复杂现象时有更广泛的设计空间。我们称之为广义元胞自动机模型[10]。

2软件架构设计

现实世界中各行各业、各种领域非常之多,随着信息技术的发展和应用的不断深入,在其上的各种应用软件系统也如同自然界缤纷复杂的生物形态一般丰富庞杂。但探其究竟,我们不难发现它们也是有规可循,聚类可分,它们的内核存在着大量的一致性。

下面我们尝试将基于元胞自动机理论对其进行剖析:

2.1元胞抽象

一般而言,实用的软件系统大多具有人机交互的功能和特性(注,诸如病毒软件这样的纯后台软件系统不在本文讨论之列)。人机交互的过程本质上是通过一系列界面的交互来实现的。它一般可表现为:界面显示、界面操作和界面提交(关闭)等三个过程。

同时,交互期间还贯穿着对操作者的授权验证,即,软件系统的用户只能看自己该看的、操作自己该操作的内容。

作为元胞分析而言,上述人机交互系统是一系列界面(Form)承载,界面内的最小单元为控件(Controls),交互操作(Operate)的实质是调用后台对应的处理过程(Process),而且交互由一系列授权验证(Verify)约束。

通过抽象,我们不难得到软件架构层面的元胞自动机对应要素:

(1) 元胞 界面(Form)中的控件(Controls)可视为自动机体系内的基本构成单元,事实上软件系统正是通过它们(lable、textbox、datagrid、button)来显示信息以及实现人机交互。

(2) 状态 控件在用户交互(Operate)之后呈现的一系列状态。

(3) 元胞空间 元胞(Controls)分布于界面(Form)之上,界面自然成为自动机体系内的元胞空间。

(4) 邻居 狭义上是指界面上与当前控件近邻的其它控件,广义上是指对影响当前控件下一时刻状态的控件。

(5) 规则 控件的状态由一系列的交互(Operate)而改变,交互的实质是处理过程(Process)的调用,处理过程便是一个状态转移函数,通过元胞当前状态及其邻居状况确定下一时刻该元胞状态。

(6) 时间 软件体系的时间轴可以理解为一系列操作发生的顺序轴。

由于大多数应用软件都涉及数据库的应用,而数据库应用的实质一般而言是对记录的增、删、改、查询和统计等操作。这样我们就可以把软件系统划分为前后台两个域:前台界面展现交互;后台则为对数据库记录的处理。在完成了前台元胞分析之后,同样也可以对后台进行剖析和元胞分析。

对目前最为流行的关系型数据库而言,数据库单元主要体现为数据表(Table)和表内的字段(Field)。

对此,我们同样可以找到数据库层面的元胞自动机对应要素:

字段(Field)可视为元胞,数据表(Table)视为元胞空间。

2.2规则定义

如何能够让软件系统也像细胞通过自身复制演进出生物体征那样地实现呢?我们构建的公司商业软件核心架构FSA通过一套规则体系引导着软件元胞及相关的Form、Control、Operate、Process、Verify、Table和Field等要素随着人机交互过程自然地完成。

(1) 界面显示Form加载规则:检索对应实体类,完成实例初始化;

Verify读写控制规则: 交互授权验证,控制Controls可读写属性;

Controls数据提取规则: 检索数据源,加载显示数据;

(2) 界面交互Operate调用规则: 检索对应业务处理过程,实现Process调用;

(3) 界面提交Table记录处理规则: 自动构造SQL语句,完成精确到Field的处理;

Form卸载规则:实例化对象卸载,缓存释放,垃圾回收。

2.3架构实现

FSA通过六张数据表(Table)三个动态链接库文件(DLL)的复用,实现了公司所有商业项目、软件产品的框架搭建与开发。

3结语

基于元胞自动机思想构建的通用软件架构(FSA)与其它软件架构相比差异化优势体现在两大方面(共性之处不再赘述):

(1) 结构直观统一,简化系统设计 元胞抽象源自直观的界面展现,系统内部设计的映射逻辑简单清晰,不同业务领域的应用具有高度的一致性:UI设计一旦定型,Form、Controls、Table、Fields等要素在设计业务的实现,而软件共性单元由元胞自动机托管。

(2) 规则明晰,提高业务专注度 FSA通过抽象与业务解耦,实现基于表单、控件与数据模型的直接关联,开放式配置型的接口设计则可以普适业务逻辑扩展,从而尽最大可能的使程序员专注于自身差异化业务的实现,而软件共性单元由元胞自动机托管。

参考文献

[1]赵松年.非线性科学—它的内容、方法和意义[M].北京:科学出版社,1994:69-76.

[2]Bastien C,Michel D.Cellular Automata Modeling of Physical Systems.(物理系统的元胞自动机模拟)[M].祝玉学,赵学龙,译.北京:清华大学出版社,2003.

[3]余亮,陈荣,何宜柱.元胞自动机与经济学应用[J].系统工程,2003,21(1):90-93.

[4]Nagel K,Schreckenberg M.A cellular automaton model for freeway traf-fic[J].J Phys I,1992,2(2):221-229.

[5]宋卫国,范维澄,汪秉宏.中国森林火灾的自组织临界性[J].科学通报,2001,6(1).

[6]韩筱璞,周涛,汪秉宏.基于元胞自动机的国家演化模型研究[J].复杂系统与复杂性科学,2004,1(4):74-78.

[7]周恺卿,乐晓波,潘小海,等.基于元胞自动机的线性遗传程序设计算法[J].计算机工程,2011,37(16):161-163.

[8]贾斌,高自友,李克平,等.基于元胞自动机的交通系统建模与模拟[M].北京:科学出版社,2007:48-54.

[9]周成虎,孙站利,谢一春.地理元胞自动机研究[M].北京:科学出版社,2001.

二维元胞自动机 篇3

关键词：元胞自动机,吸引力,排斥力,疏散仿真

1 基于元胞自动机的人员疏散模型

1.1 元胞自动机简介

元胞自动机 (CA) 是最具代表性的微观离散模型, 元胞自动机的核心内容是构建元胞移动的局部规则, 凡是满足规则的模型都能够算作是元胞自动机模型。元胞自动机将建筑空间按照一定形式分割成规则格网, 规则格网由规则网格组成, 在规则格网中的每一元胞必须在有限的离散状态集中取值, 遵循构建的局部规则对元胞状态进行更新。不同于一般的动力学模型, 元胞自动机不是严格定义的物理方程和函数, 而是由一系列的演化规则构成, 即通过大量元胞简单的相互作用而构成动态系统的演化, 把连续的复杂动态过程转变为离散的相互作用。与传统的建模方法相比, 它以“自下而上”的研究思路直接反映系统各组成要素之间的相互作用, 具有利用简单的、局部规则的、离散的方法描述复杂的、全局的、连续系统的能力, 能够通过一些简单的规则模拟出许多自然现象与生命现象, 因此广泛应用于社会、经济、环境、地学、生物等众多领域。

1.2 模型的参数设计

模型首先将疏散空间按照行人的最小占用面积设计分割成规则格网, 在规则格网中的每个网格的大小为0.5 m×0.5 m, 网格也称为规则格网的基本单元。在一个单位时间步长内, 每一个网格或为空, 或被墙、服务设施等障碍物占据, 或被一个行人占据。在一个单位时间步长内, 每个人员占据一个元胞, 每个元胞对应于一个单元网格, 元胞邻域采用如图1所示的二维摩尔型分布, 这种元胞邻域体现在单位时间步长内, 疏散个体除停留在原地不动外, 可向上、下、左、右、左上、左下、右上、右下8个方向中的一个方向移动, 依次对应于k=1, 2, …, 8;k=0表示该元胞原地不动, 疏散个体的可移动方向如图2所示。人在正常情况下行走速度为1 m/s, 这样将每个时间步定为0.5 m/ (1 m/s) =0.5 s。

1.3 模型的建立

设在一个时间步长内, 个体元胞所在的单元格的坐标为 (i, j) , i、j分别表示该单元格位于规则网格空间的第几行第几列。设在一个时间步长内, 元胞邻域内单元格的坐标为 (i, j) , 考虑到个体选择单元格时具有一定的目的性以及其他一些影响因素, 个体选择是综合各种因素之后吸引力概率最大的单元格。单元格的吸引力概率由单元格的可达性、静态场、动态场等属性值决定。

1) 可达性。

可达性用来表示单元格是否可达, 设为Zij, 在一个时间步长内, 个体邻域内单元格若被建筑物和其他如高温、有毒的空间区域、边界等不可逾越的障碍物占据时和其他元胞占据时, Zij=0;若单元格未被占据, Zij=1。

2) 静态场。

在疏散中, 人员总是趋向于选择邻域内离出口距离最近的单元格, 为此引入了静态场的概念, 静态场是用来描述单元格离相应出口的远近程度, 设为Rij, 单元格离出口越近, Rij越大, 出口处的单元格的Rij=+∞, Rij的计算公式为

$R{}_{ij}=\frac{\text{Μ}\text{A}\text{X}(d{}_{ij})}{d{}_{ij}}.$

式中:Rij表示单元格的静态场值; dij表示单元格距相应出口的距离; MAX (dij) 表示建筑空间内单元格距相应出口最远的距离。

3) 动态场值。

动态场值是用来描述单元格是否在人员熟悉的出口上, 人员前进方向是否堵塞, 单元格前方视野范围内人员数量的大小, 选择的单元格是否同时有其他人员选择等动态因素。将动态场值设为Dij, 动态场值又可分为习惯值Xij、堵塞值Sij、趋众值Qij、冲突值Cij。

习惯值Xij是用来表示人员对出口的熟悉程度, 其值可由调查统计得到。

堵塞值Sij用来表示人员前进方向的堵塞程度, 即前方视野中人员和障碍的密度, 假设个体当前位置到第 (i1, i2) 个出口视野范围内的空间坐标集为A, 则到出口的人数为

$p(i{}_1,i{}_2)={\displaystyle \sum _{(x,y)\in A}f}{}_1(x,y).$

其中,

$f{}_1(x,y)=\{\begin{array}{l}1,\text{位}\text{置}\text{坐}\text{标}(x,y)\text{被}\text{个}\text{体}\text{所}\text{占}\text{据}‚\\ 0,\text{位}\text{置}\text{坐}\text{标}(x,y)\text{未}\text{被}\text{个}\text{体}\text{所}\text{占}\text{据}。\end{array}$

同理, 到出口的障碍数为

$w(i{}_1,i{}_2)={\displaystyle \sum _{(x,y)\in A}f}{}_2(x,y).$

其中,

$f{}_2(x,y)=\{\begin{array}{l}1,\text{位}\text{置}\text{坐}\text{标}(x,y)\text{被}\text{障}\text{碍}\text{物}\text{所}\text{占}\text{据}‚\\ 0,\text{位}\text{置}\text{坐}\text{标}(x,y)\text{未}\text{被}\text{障}\text{碍}\text{物}\text{所}\text{占}\text{据}.\end{array}$

假设个体当前位置到第 (i1, i2) 个出口视野范围内空间网格个数为N, 以及每个空间网格的面积为S, 则到各出口的人数和障碍的密度分别为

$\begin{array}{l}rp(i{}_1‚i{}_2)=\frac{p(i{}_1,i{}_2)}{{\rm N}\cdot S},\\ rw(i{}_1‚i{}_2)=\frac{w(i{}_1,i{}_2)}{{\rm N}\cdot S}.\end{array}$

则堵塞值Sij的计算公式

$S{}_{ij}=\alpha [rp(i{}_1,i{}_2)+rw(i{}_1,i{}_2)].$

其中, α为概率系数。

趋众值Qij表示单元格前方视野范围内人员的密度, 即

$Q{}_{ij}=\beta \cdot rp(i{}_1,i{}_2).$

其中, β为概率系数。

冲突值Cij表示单元格被多个人员意图占据出现的争夺概率, 冲突产生的前提是在此单元格未被人员和障碍物占据, 假设在一个时间步长内该单元格有M个人员有占据意图 (0≤M≤8) , 则有占据意图的个体占据此单元格的概率为

$C{}_{ij}=\frac{1}{{\rm M}}.$

由于建筑空间内的人员组成较为复杂, 不同人员针对这四种动态场值的选择可能有所不同, 比如老人、儿童、中青年女性趋众的概率更大, 更愿意随着大众一起前进, 在堵塞面前相对被动, 主动地绕行或寻找其他出口或与其他人员产生冲突争夺单元格的概率较小, 而身体强壮的中青男性在面对堵塞时更缺乏耐性, 寄希望于加塞与其他人员争夺单元格或者寻找其他出口, 某些对建筑环境较为熟悉的人群比如管理人员更愿意选择自己熟悉的出口。因此, 考虑这些因素, 本文分别对习惯值Xij、堵塞值Sij、趋众值Qij、冲突值Cij赋予不同的权重W1、W2、W3、W4, 见表1。

因此, 动态场值Dij的计算公式为

$\begin{array}{l}D{}_{ij}=X{}_{ij}\cdot W{}_1+S{}_{ij}\cdot W{}_2+\\ Q{}_{ij}\cdot W{}_3+C{}_{ij}\cdot W{}_4.\end{array}$

在分别计算单元格的可达性、静态场值、动态场值后, 单元格的吸引力概率计算公式为

$F{}_{ij}=\eta \cdot D{}_{ij}\cdot {\rm Z}{}_{ij}\cdot R{}_{ij}.$

式中:η表示使邻域内所有单元格吸引力概率总和为1的系数。

2 仿真结果及分析

2.1 仿真条件

考虑如下的仿真场景:大小为50×50个网格的封闭空间 (不包括四周围成一圈的墙壁) , 在最右侧居中位置和最左侧居中位置有两个安全出口, 坐标位置分别为 (50, 20～30) 、 (0, 20～30) , 出口宽度为5 m, 即十个网格。初始状态下, 人员在区域随机分布, 在发生灾难以后, 人群都向出口的方向进行疏散。模拟中时间步设置为0.5 s, 逃生人员的总数量和人员的视野范围由人为设定, 该场景的初始化情形如图3所示。

2.2 仿真结果及分析

图3 (a) ～ (d) 分别显示了人员疏散初始情形、两个中间情形以及临近结束情形, 其中每个元胞的视野领域为5个网格。从第一个中间情形可以看出, 人员在疏散过程中开始朝着出口的方向有效疏散, 并且接近出口的人群形成了一柱形结构, 这是明显的动力学特征图;第二个中间情形表明, 人群为了尽快疏散, 自发地朝出口方向堆积, 形成了拱形或半圆形, 这表明当人群急于逃生在出口处形成拥挤的人群时, 就会使人群的疏散速度减慢, 产生“快即是慢”现象。

图4反映了疏散时间与四种权重W1、W2、W3、W4之间有直接关系, 仿真结果显示当熟悉值权重W1较大时, 疏散较快, 表现在人员对出口的熟悉程度较高, 疏散效率也随之提高, 当W1达到一定值时, 疏散时间趋于平稳;当堵塞值权重W2增大时, 疏散时间随之降低, 但当W2达到一定值时, 疏散时间开始增加, 这表明人群寄希望于寻找堵塞程度较小出口时, 有时反而会造成停滞不前, 使疏散速度降低, 这与实际情况也是相符的;当趋众值权重W3增大时, 人群的疏散时间降低, 在W3达到一定值后, 疏散时间趋于平稳, 这表明人群的趋众效应在一定程度上是有利于疏散的;当冲突值权重W4增大时, 人群的疏散放慢甚至产生停滞, 这表明在人群疏散时, 过多的冲突只会使疏散的速度放慢, 甚至造成人员伤亡使疏散陷于停滞。

3 结束语

本文基于元胞自动机建模思想, 提出了一种人员疏散的微观模型。模型能够模拟疏散人群在出口处形成拱形或半圆形、快即是慢现象, 人群疏散时间与人群对建筑环境的熟悉程度、人群的堵塞程度、人群的趋众值、人群疏散冲突之间的关系, 仿真结果表明, 模型具有很强的现实描述能力, 能够再现和解释现实的疏散情形。

参考文献

[1]马俊驰.火灾中人群疏散的仿真研究[D].上海:同济大学, 2007.

[2]方正, 卢兆明.建筑物避难疏散的网格模型[J].中国安全科学学报, 2001, 11 (4) :10-13.

[3]G.Keith Still Crowd Dynamics.PhD Thesis, Universi-tyof Warwick, 2000.

[4]Helbing D, FarkasI, Vicsek T, Si mulating dynamical fea-tures ofescape panic[J].Nature, 2000, 407:487-490.

[5]Muramatsu M, Nagatani T.Jamming transition of pedes-trian traffic at a crossing with open boundaries[J].Physi-ca A, 2000, 286:377-390.

[6]杨立中, 方伟峰, 黄锐, 等.基于元胞自动机的火灾中人员逃生的模型[J].科学通报, 2002, 47 (12) :1484-1489.

[7]宋卫国, 于彦飞, 范维澄, 等.一种考虑摩擦与排斥的人员疏散元胞自动机模型[J].中国科学, E辑:技术科学, 2005, 35 (7) :725-736.

[8]翁文国, 袁宏永, 范维澄, 等.一种基于移动机器人行为的人员疏散的元胞自动机模型[J].科学通报, 2006, 51 (23) :2818-2822.

[9]张培红, 陈宝智.火灾时人员疏散行为规律[J].东北大学学报, 2001, 22 (1) :54-56.

一维五邻居元胞自动机的演化行为 篇4

元胞自动机作为21世纪科学研究中一个异常活跃的前沿领域,是复杂性科学的核心技术之一。元胞自动机是一种时间、空间、状态均离散,具有时空计算特征的网格动力学模型[1,2],是一个集数学、物理学、计算机科学、生物学、系统科学等多学科交叉的边缘领域,有广泛应用前景的研究方法。当前其应用领域广泛涉及到社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理学、环境学、军事学等,并取得了丰硕的成果,如用于人工生命[3]、地震波模拟[4]、交通系统的仿真与优化[5]、国家间通过战争彼此兼并的预测[6]、地理信息系统的开发[7]等。但是,元胞自动机作为一种全新的方法,目前的研究仍不完整。无论是对元胞自动机本身的演化行为及相关理论的研究,还是应用元胞自动机机理来研究其它学科,都成为研究的前沿和热点。近年来,国内也有一些相关理论的研究,但理论研究的焦点多集中于初等元胞自动机,因为其演化规则简单,数目较少,处理起来相对容易。

本文首先将初等元胞自动机拓展到一维五邻居元胞自动机,接着依据一维五邻居元胞自动机的演化特点,对演化规则系统命名;其次借助于卡诺图[8],给出其演化规则的函数形式;最后对演化规则(e0efe0e0)hex的演化行为进行分析和研究。本文从不同视角得到的结果有助于对元胞自动机的演化行为进行更深入、细致的研究。

1 元胞自动机概述

元胞自动机的构形可以用一个双侧无穷的符号序列来表示, 在时刻t构形记为:xt={xt-n,xt-n+1,…,xt0,…,xtn-1,xtn},其中n→∞,每一个符号,即一个元胞xti都取布尔变量,即0或1两个状态,则在下一个时刻构形演化为:xt+1={xt+1-n,xt+1-n+1,…,xt+10,…,xt+1n-1,xt+1n},其中,每一个元胞xt+1i由上一时刻的相应元胞按法则xt+1i=f(xti-1,xti,xti+1)决定。这里的f称为元胞自动机的局部规则[1]。 对整个构形而言,就有F,使得F(xt)=xt+1,这里F称为元胞自动机的全部规则。

为了研究规则的特点及演化性质, S.Wolfram以逻辑运算方式给出了一维三邻居元胞自动机演化规则f的形式,如90号规则为:x${}_i^{t+1}$=xti-1♁xti+1(♁表示异或运算)。这种表示方法对256种规则来说不容易求出,且不便于分析。

文献[9]利用待定系数法,给出了一维三邻居元胞自动机32种合法演化规则的函数形式,若借助于此方法将其推广至一维五邻居元胞自动机较为困难,因为其中涉及的变量多达32个,同时若将二进制数所对应的十进制数作为此类元胞自动机的规则代码,表示起来相当麻烦,演化规则多达232种。

2 演化规则的函数形式

首先依据一维五邻居元胞自动机演化规律引入八位十六进制数来表示其规则代码。为了书写方便,本文中用A表示xti-2,B表示xti-1,C表示xti,D表示xti+1,E表示xti+2,Y表示xt+1i.例如:

此一维五邻居元胞自动机的规则代码,若采用与一维三邻居元胞自动机相同的命名法比较困难,因为数目相当庞大,故采用八位十六进制数将其表示为:(e0efe0e0)hex.

为了给出此规则演化的函数形式,我们引入数字逻辑电路中经常使用的卡诺图对其化简,收到了意想不到的的效果。

首先列出规则(e0efe0e0)hex的真值表,此规则的映像表,如表1所示,恰好是一天然的真值表;其次根据真值表画出卡诺图, 如图1所示;最后化简结果如下式:

$\text{Y}=\text{A}\overline{\text{B}}\overline{\text{C}}+\text{C}\text{D}+\text{C}\overline{\text{D}}\text{E}(1)$

3 规则(e0efe0e0)hex的演化性质分析

考虑一个一维两状态元胞自动机,用xti表示时刻t位置i的状态,若xti=1,表示存在粒子;反之xti=0,表示不存在粒子。

性质1 (e0efe0e0)hex是粒子数时刻保持守恒的元胞自动机。

证明 将式(1)改写为:

$x{}_i^{t+1}=x{}_{i-2}^t\overline{x}{}_{i-1}^t\overline{x}{}_i^t+x{}_i^{t}x{}_{i+1}^t+x{}_i^t\overline{x}{}_{i+1}^{t}x{}_{i+2}^t(2)$

采用周期性边界条件, 从左到右格点编号依次为:0～N,将式(1)对i从2～N-2求和,

$\begin{array}{l}{\displaystyle \sum _2^{{\rm N}-2}x}{}_i^{t+1}={\displaystyle \sum _2^{{\rm N}-2}x}{}_{i-2}^t-{\displaystyle \sum _2^{{\rm N}-2}x}{}_{i-2}^{t}x{}_{i-1}^t-{\displaystyle \sum _2^{{\rm N}-2}x}{}_{i-2}^{t}x{}_i^t\\ +{\displaystyle \sum _2^{{\rm N}-2}x}{}_{i-2}^{t}x{}_{i-1}^{t}x{}_i^t+{\displaystyle \sum _2^{{\rm N}-2}x}{}_i^{t}x{}_{i+1}^t\\ +{\displaystyle \sum _2^{{\rm N}-2}x}{}_i^{t}x{}_{i+2}^t-{\displaystyle \sum _2^{{\rm N}-2}x}{}_i^{t}x{}_{i+1}^{t}x{}_{i+2}^t(3)\end{array}$

考虑到左边界两元胞的演化,

$\begin{array}{l}x{}_0^{t+1}=x{}_{{\rm N}-1}^t-x{}_{{\rm N}-1}^{t}x{}_{{\rm N}}^t-x{}_{{\rm N}-1}^{t}x{}_0^t+x{}_{{\rm N}-1}^{t}x{}_{{\rm N}}^{t}x{}_0^t\\ +x{}_0^{t}x{}_1^t+x{}_0^{t}x{}_2^t-x{}_0^{t}x{}_1^{t}x{}_2^t(4)\\ x{}_1^{t+1}=x{}_{{\rm N}}^t-x{}_{{\rm N}}^{t}x{}_0^t-x{}_{{\rm N}}^{t}x{}_1^t+x{}_{{\rm N}}^{t}x{}_0^{t}x{}_1^t\\ +x{}_1^{t}x{}_2^t+x{}_1^{t}x{}_3^t-x{}_1^{t}x{}_2^{t}x{}_3^t(5)\end{array}$

再考虑到右边界两元胞的演化,

$\begin{array}{l}x{}_{{\rm N}}^{t+1}=x{}_{{\rm N}-2}^t-x{}_{{\rm N}-2}^{t}x{}_{{\rm N}-1}^t-x{}_{{\rm N}-2}^{t}x{}_{{\rm N}}^t+x{}_{{\rm N}-2}^{t}x{}_{{\rm N}-1}^{t}x{}_{{\rm N}}^t\\ +x{}_{{\rm N}}^{t}x{}_0^t+x{}_{{\rm N}}^{t}x{}_1^t-x{}_{{\rm N}}^{t}x{}_0^{t}x{}_1^t(6)\\ x{}_{{\rm N}-1}^{t+1}=x{}_{{\rm N}-3}^t-x{}_{{\rm N}-3}^{t}x{}_{{\rm N}-2}^t-x{}_{{\rm N}-3}^{t}x{}_{{\rm N}-1}^t+x{}_{{\rm N}-3}^{t}x{}_{{\rm N}-2}^{t}x{}_{{\rm N}-1}^t\\ +x{}_{{\rm N}-1}^{t}x{}_{{\rm N}}^t+x{}_{{\rm N}-1}^{t}x{}_0^t-x{}_{{\rm N}-1}^{t}x{}_{{\rm N}}^{t}x{}_0^t(7)\end{array}$

综合式(3)～式(7),得:

${\displaystyle \sum _0^{{\rm N}}x}{}_i^{t+1}={\displaystyle \sum _0^{{\rm N}}x}{}_i^t(8)$

由此可见,粒子数确实与演化时间无关,本性质得证。

性质2 (e0efe0e0)hex的演化行为呈现多样性。

20世纪80年代, S.Wolfram把元胞自动机分成以下4类[2]:①趋于一个空间平稳构形,这里的空间平稳是指每一个元胞处于同一个状态;②趋于一系列简单的稳定结构或周期结构;③表现出混沌的非周期行为;④出现复杂的局部结构,或者说是局部混沌,其中有些会不规则地传播。文献[10]证明了确定的有限元胞自动机的状态演化最终处于稳定状态或者循环状态。我们进一步研究发现:上述4 类分法并不十分严格,少数元胞自动机演化行为兼有多种类型。

数值模拟时采用周期性边界条件,模拟的时空尺寸为:200时步×200格点,图中的每一黑点代表一粒子。

观察图2、图3、图4发现,系统的演化与粒子初始密度及初态分布密切相关,图4(a)对应于平稳型;图2、3(a)对应于周期型;图3(b)、4(b)对应于复杂型。

通过前面对一维元胞自动机机理的分析,可见元胞自动机是通过简单的规则进行演化,产生复杂的行为,并在大量的计算机仿真基础上,将所有元胞自动机的演化行为归纳为平稳型、周期型、混沌型和复杂型四大类。

一维元胞自动机的分类尚且如此困难,而二维以至三维的规则更多,演化行为更为复杂,对二维或三维元胞自动机进行系统分类就更是难以进行。目前,国内外尚没有相关的较好的研究成果。

4 结束语

本文利用卡诺图导出了一维五邻居元胞自动机演化规则的函数形式。其优点在于:①对于单一规则的演化,很容易设计出程序进行计算机模拟;②从规则的函数形式中可直接获得一些演化的性质及定理;③借助于规则的函数形式, 可对一些规则进行解析研究以获得精确的理论值;④规则的函数形式可以渗透到其它相关领域, 如交通流,计算机图形学, 流体力学以及随机扩散过程,生物学中的艾滋病毒H IV 的感染过程等, 进一步拓展元胞自动机的应用范畴[11,12,13,14,15,16,17]。

本文采用卡诺图研究元胞自动机的演化具有很强的实效性,不但丰富了研究元胞自动机的技巧, 而且为研究元胞自动机的演化性质提供了可靠的理论依据。

二维元胞自动机 篇5

关键词：元胞自动机,MATLAB,热传导,浴缸水温

随着人们生活条件的提高, 越来越多的人开始使用温水泡澡。泡澡可以清除疲劳、提高睡眠质量、缓解全身酸痛, 对促进肌肤的新陈代谢及改善肥胖体质具有很好的效果[1]。不幸的是, 浴缸是一个简单的水容器, 随着时间的推移, 水温逐渐下降。所以需要加一个持续进水的水龙头来加热洗浴用水。文章以传热学为基础[2]从空间和时间的角度开发一个浴缸的水的温度模型, 以确定在浴缸的人可以采取保持温度的最佳策略, 使整个浴缸在没有浪费太多水的情况下尽可能接近初始温度。模型需要考虑注入热水的水温和流速, 浴缸的体积, 注入热水的水龙头位置是否会影响模型的结果。

1 假设与方法

1.1 问题假设

为了简化问题研究, 在模型建立之前我们进行了以下假设:

(1) 浴缸的各壁均由同一种材料构成———陶瓷。

(2) 浴缸的外界环境温度恒定不变。

(3) 文章提到的各种水均慢速流动, 不考虑它们的动能转化为热能。

(4) 不同温度的水在混合过程中不考虑热能的损失。

(5) 不考虑进入或流出浴缸的水由于进出口高度的不同而产生的势能转化为热能。

(6) 水面和浴缸壁向大气中辐射的能量忽略不计。

1.2 使用方法

运用元胞机模型, 根据Ralf Nasilowski的研究[3], 我们将浴缸中的水离散化并结合元胞自动机模型, 模拟随着热水流的注入, 浴缸中的水随时间的温度分布状态[4]。将浴缸内部纵向剖面热分布的二维空间网格化热量的传导可以看成是在不同的网格之间热量的传导[5]。通过改变进水口位置, 热水流温度及流速等条件来观察水温分布的情况, 从而确定各条件对水温的影响。本模型对水温分布的模拟, 是通过对一个 (m+2) × (n+2) 的矩阵进行一系列的操作, 其中m、n分别对应于、浴缸纵剖面的长和高, 矩阵边界为空气层和浴缸壁。出水口设置为左上角, 如图1 所示。矩阵中的元素 (除边界外) 代表在此位置的水的温度大小。由于水之间的热对流, 水面散热以及水与浴缸壁之间的换热存在不同的换热系数, 我们额外定义了一个 (m+2) × (n+2) 的权重矩阵来表示水与水、空气和浴缸壁之间的换热关系[6]。

2 运用元胞机研究浴缸中的水温温度分布图并分析

2.1 改变热水流温度

控制热水流温度, 执行50 步, 观察浴缸内水的温度情况。图2为热水流温度设置为322K和325K的温度分布图, 发现温度越高, 热量扩散越快。

2.2 改变热水流速

改变热水流速通过改变热源大小实现, 当改变热源大小为前一热源大小的两倍时, 运行25 次的温度分布图如图3, 发现热水流速即热源较小时比较, 发现流速越大, 热量扩散越快。

2.3 改变进水口位置

文章中只考虑热水从水面之上流入, 不考虑进水口在下面的情况。分别改变进水口位置为左上角, 水面中间, 运行50 次, 温度分布图如图4, 我们发现, 当进水口距离出水口位置最近即在左上角时, 我们可以看出出水口处的水温是热水流的温度, 这样会使同等情况下流出更多的热水, 热量散失最多。当进水口与出水口距离最远即在右上角时, 可以知道出水口流出的水的温度相对较低, 热量散失少。

2.4 改变浴缸体积

通过改变浴缸的长度来观察浴缸体积改变对温度分布图的影响。经过分析发现浴缸体积的改变对热量的传导没有太大影响。图5 为设置长度为130 和200 时的温度分布。

3 结束语

注入热水的水温越高, 温度传导越快, 整个浴缸水温越容易保持。

注入热水流速越快, 热量扩散越快, 越有利于保持水温。

当进水口与出水口位置相差最远时, 热量散失越少。

浴缸的体积对热传导没有太多影响。

参考文献

[1]泡澡好处多[J].Health, 2014, 10:4-5.

[2]杨世铭.传热学[M].

[3]Ralf Nasilowski.A cellular-automaton fluid model with simple rules in arbitrarily many dimensions[J].Journal of Statistical Physics, 1991, 651:.

[4]BRUCE B.LOWEKAMP.THE CELLULAR AUTOMATA PARAD IGM FORTHE PARALLEL SOLUTION OF HEAT TRANSFER PROBLEMS.

[5]C.Marcel o F.Bonetto o A.Clausse.Simulation of boiling heat transfer in small heaters by a coupled cellular and geometrical automata.

二维元胞自动机 篇6

国内的疏散研究取得了大量的研究成果,如杨立中等建立了参考社会力模型和基于总危险度的人员疏散微观离散模型;宋卫国等在Helbing工作的基础上,利用社会力模型进一步研究了建筑结构,包括门的宽度与墙的厚度等对人员疏散的影响;翁文国等建立了基于移动机器人行为的人员疏散元胞自动机模型等。上述研究工作成功地将元胞自动机从交通流模型应用到行人流模型,但行人比车辆运动更加复杂,在紧急情况下的人员疏散应注重人的个体行为研究。从这些研究中可以看出,未来的疏散模型将包含更多的行为细节。

笔者在经典元胞自动机理论中加入吸引力、摩擦力和排斥力的规则和参数,并且在考虑人与人之间相互作用的基础上,引入人与环境(如建筑)之间的相互作用力,并将疏散人员的心理因素和火灾的影响纳入考虑范围,构造出一个新的元胞自动机模型,该模型既拥有社会力连续模型可以较好描述人员疏散中出现的各种现象的特点,又具有元胞自动机模型较高的计算效率。利用该模型对一个拥有三个子房间和一条走廊的建筑结构进行模拟,同时与社会力模型和经典元胞自动机模型进行对比,仿真结果表明了新模型的优越性。

1 仿真模型建立

1.1 元胞自动机模型

采用二维元胞自动机模型模拟疏散过程。其优点在于省去了用微分方程作为过渡而直接通过制定规则来模拟非线性物理现象。模型的基本框架是将建筑物平面进行均匀的网格划分,每一网格有几种可能的状态:为障碍物(起火点)占据,或者为空,或者为一人占据,三种状态必居其一。模型中每个元胞对应0.4m×0.4m(按人员肩宽为0.40m考虑)的空间,每个疏散人员占据一个格点(元胞)。行人在一般情况下的行走速度为1.00 m/s左右,则单个时间步为0.4/1.00=0.4s。每个时间步人员只能移动一格,所有人员可以根据自身和邻域的状态以一定的概率向上、下、左、右、左上、左下、右上、右下8个方向中的一个移动,或原地不动。模型中网格状态的更新是并行的,每个时间步更新一次元胞的状态,仿真便往前递进一步。

1.2 人员行走算法

模型中人员的运动遵循一定的行走规则,其行为会随周围环境的变化相应调整。模型局部的运动规则在每个时间步有两个基本问题需要解决,包括路线的选择问题(吸引强度设计)以及如何解决多于一人同时竞争一个空格点时产生的冲突问题(冲突避让原则)。在分析人员选择路线时,引入元胞吸引强度的概念,并假设所有人员选择周围某一元胞作为运动方向的概率同该元胞的吸引强度成正比。新模型认为出口位置的吸引力,人与人(或障碍物)之间的排斥力、摩擦力,从众吸引力,起火点排斥力五种因素共同作用影响人员的路线选择,通过对五种因素的量化加权求取某元胞的吸引强度。

紧急情况下人员疏散的运动目标为安全出口,在没有障碍物阻挡时疏散人员会选择离出口最近的疏散路线,以最快的速度撤离。因此,离出口越近的元胞吸引强度越大,元胞(i,j)出口位置的吸引强度pdecide根据人员对所处建筑物安全出口的选择来确定,则出口位置的吸引强度如式(1)所示。

式中:(a2+b2)1/2为元胞空间对角线长度;(iminexit,jminexit)为距离最近的出口坐标。

在人员疏散过程中,排斥力体现在人们总是尽可能避免与周围的人员或墙壁等障碍物过于接近,因为这样会使运动速度下降,甚至导致碰撞受伤。令pr表示排斥力产生的吸引强度,反映人员试图避免由于冲突而导致的潜在伤害。Song等人已经提出一种计算冲突各方均静止不动的概率的计算方法,本模型借鉴该方法,如式(2)所示。

式中:ζ∈[0,∝]为排斥的硬度,疏散人员密度越大,对碰撞的恐惧越大,则排斥的硬度越大;v为人员运动速率。

摩擦力产生于运动的人和静止的人之间以及运动的人与墙壁等障碍物之间。由排斥力引起的伤害总是要大于摩擦作用导致的伤害,所以由摩擦力产生的吸引强度pf如式(3)所示。

除了以上三种社会力对人员选择路线起到了影响外,从众心理、起火点的位置也会影响人员对路线的选择判断。pfollow为从众吸引强度,与各区域的人员密度成正比。pfire为元胞火灾排斥力,模拟时先确定火灾最危险的区域,并认为离该位置越近的地方火灾引起的排斥力越大,如式(4)所示。

式中:(ifire,jfire)为起火点处的中心坐标;(imaxfire,jmaxfire)为建筑室内离起火点最远的位置坐标。

基于以上五种因素,元胞的吸引强度pi,j可以通过式(5)计算得出。

式中:k1、k2、k3、k4、k5分别为各个因素的影响系数。其中k1、k2≥0;k3、k4、k5≤0。各影响系数的大小是决定在疏散过程中哪些作用力占主导地位的关键,不同疏散场景影响系数的大小也不同。

1.3 冲突避让原则

在同一时间步一个元胞最多只能由一个人员占据,当两个或更多的人员试图移动到同一个目标元胞时,冲突就发生了。只能有一个人员留下,其他人员将选择其他元胞作为移动目标,模型中每个人员的机会是均等的。

1.4 火灾对人员疏散的影响

火灾主要影响人员的行进速度和可视范围,造成人员的心理恐慌以及影响人员对疏散路线的选择等。其影响范围根据火灾的位置和蔓延的情况来确定。通常火灾发展和蔓延符合一定的扩散和衰减规律,如式(6)所示。

式中:E为所考察格点受火灾影响的程度;α为扩散系数;β为衰减系数;ΔE为所考察格点与周围格点受火灾影响程度之差。可以通过人员所处的格点受火灾影响程度来判断人员的速度、可视范围以及心理状况等是否受火灾的影响以及可能的影响程度。

1.5 更新流程

在每个时间步的元胞更新流程,如图1所示。每一次移动,对所有人员都需进行一次判断。模拟时,在每个时间步,所有人员按以下规则进行同步更新:

(1)获取模拟地图,计算建筑面积及待疏散人数;

(2)确定每个人员所有邻居元胞的吸引强度大小,根据计算结果选择相应的元胞作为下一个时间步的目标格点,当元胞的吸引强度相当时,以均等概率选择目标;

(3)当超过1人选择同一目标时,根据冲突避让规则解决;

(4)更新每个人员的状态,重算元胞的吸引强度;

(5)回到第二步直到所有人员都疏散出建筑物为止。

2 算例分析

2.1 模拟算例

如图2所示,对一个拥有3个子房间和一条走廊的建筑结构进行火灾时的人员疏散模拟。每个网格大小为0.4m×0.4m,建筑物的建筑面积为10m×12m,则该房间的几何尺寸为25×30(格点);出口A、B、C宽度为1.2m,即3个格点,出口D宽度为1.6m,即4个格点。初始模拟状态随机分布150人,平均密度为0.8m2/人。人员移动速度为1.0m/s,时间步为0.4s,即每0.4s人员可以移动一个格点。在模拟初始时刻,火灾发生于格点(18,2)处(左上角为格点(0,0))。假设火灾房间中的燃料为木材,可查其燃烧热释放速度为500kW/m2。通过10次模拟计算,得到的期望疏散时间为152时间步,即60.8s。

2.2 分析结果

第40时步、90时步、130时步末的人员疏散分布情况,如图3~图5所示。由于初始状态人员分布较均匀,空位多,故大部分人员都能自由移动找到自己的最近目标网格。疏散时间取决于房间门口和走廊处的排队等待时间以及疏散路径上的行走时间。所以,疏散初期影响疏散时间的主因是疏散路径上的行走时间。图3为第40时间步时刻的人员实时分布情况,可以观察到疏散中典型的门口集结现象,各房间出口和走廊处人员局部密度较大,出口B处达到人员最大滞留。在图上起火点附近留下大片空白,体现了火灾发生处的排斥力。图中显示起火点位于图中安全出口上方,所以正对出口的中间两排人员由于近距离疏散路线只能是正下方,故人员互相阻挡,停留时间长,人员密集,人员之间空隙很少。

从第40时步末到第90时步末,如图4所示。当疏散人数较多,走廊较长,但其宽度不够大时,开始发生堵塞的地方不在出口处,而在走廊中间。由于人员密度的增加、近距离目标格受阻,人员基本停滞不前。人员疏散分布图形状规则,变化缓慢,尖端突显。第130时步末如图5所示,较多人员在门口集结,并成拱形分布。且只有出口附近的人员能先出去,尖端处人员处于长期停留状态。但总体上,人员疏散的发展趋势是向出口中心聚集,这是由于出口吸引强度作用的结果,模型充分体现了这种吸引力的特点。随着火势的蔓延,人员会变换疏散路径,放弃最短疏散路线,相应的出口利用率降低,而这一过程会使疏散时间大大延长。导致疏散过程中在房间门口和走廊处的人员集结和堵塞现象越来越严重,疏散时间受排队等候的影响更加明显。

新模型较好地描述了发生火灾时人员疏散中的典型现象:在门口处的集结、在走廊中间的堵塞、在门口处出现的拱形排队结构等,与Helbing等提出的社会力模型的模拟结果一致。表1为社会力模型、经典元胞自动机模型和新模型的运算速度的对比情况,其中的运算速度是三种模型在同样计算机硬件条件,同样的建筑结构(10m见方的房间、一个疏散出口)和人员密度(0.5m2/人)的条件下比较得到的。结果表明,新模型不仅具有与社会力模型同等的描述人员疏散的能力,解决了经典元胞自动机只能模拟简单拥挤现象的问题,而且具有较高的运算效率。其运算速度远远低于社会力模型,与经典元胞自动机模型速度相近。

3 总结

结合物理学中的粒子场概念,社会力模型中的力本质,群体流动的整体特征和个体行为特点,提出了一种基于元胞自动机原理,不仅考虑人与人之间相互作用,而且考虑人与环境(火灾场景和建筑)之间相互作用的人员疏散模型。该模型比较全面地考虑了紧急情况对人产生的影响,将人与人、人与建筑之间的摩擦力与排斥力,出口位置的吸引力,从众的吸引力,起火点排斥力分别加以分析量化。模型模拟情况与实际情况相符,可以作为发生火灾时对人员疏散预测的一个有效工具。

新模型能够较好地模拟发生火灾时的人员疏散现象,不仅具有与社会力模型同等的描述人员疏散的能力,解决了经典元胞自动机模型只能模拟简单拥挤现象的问题,而且具有较高的运算效率。其运算速度远远低于社会力模型,与经典元胞自动机速度相近。

摘要：基于元胞自动机理论,量化确定了吸引力、摩擦力和排斥力的运算规则,且将疏散人员的心理因素和火灾的影响纳入考虑范围,提出了一种新的室内建筑火灾人员疏散模型,并编制了相应的数值仿真计算程序。模拟结果表明,该模型能够较好地模拟发生火灾时的人员疏散现象,并可以找到不利于人员疏散的瓶颈位置。

二维元胞自动机 篇7

近年来,国内外电力系统发生了多次连锁故障导致的大停电事故,给当今高度依赖电力的社会带来了巨大损失[1,2,3,4,5,6]。连锁故障机理研究表明,虽然各类连锁故障表现形式各异,但多数故障都是从系统个别元件发生故障开始,继而事故扩大引发多个元件过载并被切除,此时若不及时采取措施,将会导致局部甚至全网功率不平衡、潮流大范围转移,引发大量线路跳闸,系统发生振荡甚至解列,从而发生大停电事故[7,8,9,10]。

一般大停电事故可分为起始、扩大和崩溃3个阶段,从以上连锁故障的发展过程来看,如果要避免大停电的发生,对事故扩大阶段的控制最为关键。在此阶段,如果能够采取诸如通过稳控装置来切机、切负荷限制输电断面潮流等措施,就可以将事故限制在有限区域内,避免全网崩溃。《电力系统安全稳定控制技术导则》[11]给出了在电网紧急情况下的切除发电机、汽轮机快速控制汽门、切负荷、并联电容器强行补偿等控制手段,但这些手段实施的时机在《电力系统安全稳定控制技术导则》中并没有明确给出。文献[12]主要研究切负荷地点和切负荷量一定的条件下,切负荷时刻对系统稳定性的影响及最佳切负荷时刻的计算问题,并根据实际算例进行验证;文献[13]建立了基于贝叶斯网络的连锁反应故障概率分析模型,根据系统故障发展过程中连锁故障搜索和分析情况,提出以连锁故障风险最小为目标的预防控制方法;文献[14]将博弈思想应用于连锁故障的预防,将电网扰动作为对弈的进攻方,系统调整作为被动的防御方,计及不同类型的电网扰动作用,提出切负荷量最小的连锁故障预防控制策略,上述文献虽然都在不同方面就切机、切负荷控制措施展开了深入研究,但是并没有全面考虑控制措施使用时刻、位置及调整量这些重要因素。

考虑到在连锁故障的发展过程中,电网从正常状态转变为警戒、紧急等状态时的界限并不明显,本文首先将模糊理论引入电网故障元胞自动机(CA-power failure)模型中[15],建立了基于模糊元胞自动机的电网故障FCA(Fuzzy-CA-power failure)模型,并给出了无功补偿、集中切负荷预防控制措施使用时间、位置及调整量的相关规则;最后通过在IEEE 39节点系统进行事故演化过程仿真,验证了电网的自组织临界特性[16,17,18],并对控制措施加入前后的仿真结果进行对比,进一步验证了控制措施的有效性和可行性。

1 基于模糊元胞自动机的电网故障模型

1.1 电网元胞自动机

元胞自动机[19,20]是定义于一个离散元胞空间之上并且遵循相关的局部更新规律、随着时间的变化不断演变的一种系统。本文构造的电网故障元胞自动机模型如图1所示。

图1所示模型将电网进行抽象化,每个元胞代表1个电网元件(如线路、变压器等),与其直接相连的元胞即为其邻居元胞,所有元胞的集合组成一个元胞空间(所有的电网元件)。通过给每个元胞赋予一定的初始过载能力来模拟整个电网的原始情况,在电网故障的演化过程中,用元胞破裂来模拟元件发生故障,并用一定的数学函数来表示元件对故障的传递,即故障元件对非故障元件的影响。

1.2 模糊规则库的建立

模糊规则库[21]的建立应首先结合研究对象的特点选择适当个数的关键量作为输入变量,然后确定论域并分割模糊输入量的子集以及分布函数类型(按照实际情况选取符合认识和判断事物习惯的隶属函数,本文采用三角形分布隶属度函数),进而得到模糊输出量。

对电网故障演化过程进行仿真,本文主要考虑3个因素:电网元件(元胞)状态、电网(元胞机)状态和故障传递程度值。

a.电网元胞的状态模糊化。

在仿真实验中,一个电网元胞是否功能失效或产生故障,取决于其负载率的大小。定义电网元胞i在t时刻的负载率为:

其中,Pi为在t时刻流过电网元胞i的有功潮流绝对值;Pi,max为电网元胞i的最大允许传输容量。

为了更加精确地描述电网元胞状态,引入元胞状态L这一模糊变量,并根据负载率大小将L进行更精确的划分。负载率l的基本论域为[0,∞),根据已有的电网元件过载理论将连续的l分别取论域为l1={0,1.1}、l2={1.1,1.3}、l3={1.3,∞},那么l的模糊子集定义为l={l1,l2,l3},对应模糊输出量L={L1,L2,L3}={正常,紧急,故障},简记为{N,U,F},则元胞状态L在负载率l取值范围内的隶属度函数曲线及其分布如图2所示。

b.电网元胞机状态的模糊化。

《电力系统安全稳定控制技术导则》中,将电力系统的运行状态分为正常、警戒、紧急、极端紧急和崩溃等几种。参照这一划分方法及“随着扰动增加,元件负载率分布曲线斜率绝对值越来越大,当斜率增加到一定程度时,任何微小扰动都会导致停电事故的发生,此时系统处在自组织临界状态”的结论[22],记负载率分布曲线经线性拟合后的斜率为k,电网元胞机状态为S,k的基本论域为(-∞,0],参考多次仿真所得结果将连续的k分别取论域k1={-∞,0.3}、k2={-0.3,-0.2}、k3={-0.2,0},那么k的模糊子集定义为k={k1,k2,k3},对应模糊输出量S={S1,S2,S3}={正常,紧急,极端紧急},简记为{N,U,VU},则电网状态S在负载率分布曲线斜率绝对值k取值范围内的隶属函数曲线及其分布如图3所示。

c.邻居元胞故障传递模糊化。

一个元胞破裂以后,势必会对其邻居元胞产生影响,本文定义其影响为:一个元胞破裂后影响其邻居的容量传输极限,使其减小,减小的值取决于此时电网状态S及破裂元胞在故障前一刻所处状态L,为了准确描述故障元胞对其邻居的影响,引入故障传递程度值R这一模糊变量,并根据此时电网元胞机状态S及破裂元胞故障前一刻的状态L将R分为5个模糊子集合:R={VS,S,M,B,VB}={很小,小,中,大,很大}。R的模糊推理规则如表1所示。

d.线路过负荷保护动作模型。

电力系统继电保护中测量值和触发值误差会导致保护动作的不确定性,该不确定性使得恒定的故障率模型无法准确描述当前运行条件对电力设备的影响,于是本文引入基于传输潮流的线路停运概率模型,对电网元件运行状态的转换进行判断。

线路停运概率模型将线路过负荷保护动作模型简化成折线模型,如图4所示,纵坐标p表示线路j断开的概率,横坐标li表示元件i的负载率。

2 预防控制措施及其应用

2.1 预防控制措施

电力系统事故发展过程中电网逐渐趋于不稳定,整个过程中伴随着个别电网元件负载率的增加及传输无功功率的增大,在大停电之前(即紧急状态)采取有效的控制措施,将突然变化的量在电网正常运行的前提下最大限度地调节到变化前一状态,能有效减少电网连锁故障的发生。以此为基本思路,结合FCA模型,本文基于IEEE 39节点系统在元胞机状态紧急的情况下对无功潮流突变的元胞进行无功补偿,且对紧急状态元胞潮流流入方向所在母线节点采取集中切负荷的控制措施,以减少大停电发生的次数及规模。

a.切负荷规则。

对于单一的电网元胞(主要考虑线路),随着故障的演化个别元胞传输潮流急剧增大,由正常逐渐向紧急和故障状态演化,故障元胞又会对其邻居元胞进行故障传递,依次演化,最终导致元胞机大范围停运,即电网连锁故障发生。为了减小元胞潮流增大对元胞机正常运行的影响,本文对上述元胞潮流流入方向所在节点采取集中切负荷的控制措施。线路有功潮流传输如图5所示。

对元胞i,传输的有功功率为Pi,则li=Pi/Pmax。设元胞i在状态演化过程中,传输功率由Pi1(正常)增大到Pi2(紧急)(故障状态时线路断开,不做考虑)。为了减小元胞i传输的功率,在元胞机处于紧急状态时对潮流流入方向的母线节点BT采取集中切负荷的控制措施,切除的负荷量为ΔP,切除负荷后,元胞尽可能回到正常状态,即负载率li(0.7,1)。

其中,li 0为元胞i的期望负载率;Pi 0为传输功率期望值;li2为元胞i在紧急状态时的负载率。

b.无功补偿规则。

电网事故传播过程中潮流重新分配,无功潮流分布逐渐趋于不平衡,个别元胞(主要考虑线路)所传输的无功潮流突然发生大幅变化,该变化将会导致节点电压不稳定甚至元胞机停运、电网崩溃。为了减小无功潮流突变对元胞机正常运行的影响,本文在检测到元胞i所传输的无功潮流变化较大时即对该元胞采取无功补偿的预防控制措施。线路无功补偿如图6所示。

一次事故演化过程中若元胞i传输的感性无功功率Qi突然增大(此处认为大于初始值的1.5倍为突然增大,具体数值可根据实际情况进行调整),为了减小无功突变对元胞机稳定运行的影响,当元胞机处于紧急状态时在元胞i无功潮流流入方向的母线节点BT处利用电容器进行无功调整,补偿量为QC(见式(3))。反之,若元胞i传输的感性无功功率Qi突然变为容性无功,为了减小该变化对元胞机稳定运行的影响,当元胞机处于紧急状态时在元胞i无功潮流流出方向的母线节点BF处利用电抗器进行无功调整,补偿量为QL(见式(3))。

若系统中所有容性补偿量用完后仍存在无功缺额,并且节点电压低于额定允许电压的下限,则此时将会因为无功不足引起电压崩溃问题,此时应选择重载的元胞进行主动切负荷处理,并确认系统发生了事故。

2.2 结合预防控制措施的元胞自动机转换规则

将以上预防控制措施的基本思路应用到基于模糊元胞自动机的电网故障模型中,即元胞机处于紧急状态时对其所在母线节点采取切负荷的控制措施,且对无功潮流突变的元胞采取无功补偿的控制措施;同时利用线路停运概率模型和故障传递模型决定元胞下一时刻的状态及故障元胞对其邻居的影响。根据这种思路,本文设定了元胞的演化更新规则如下。

a.t时刻:根据线路停运概率模型(图4)及元胞负载率隶属度函数(图2)确定各元胞状态(正常、紧急、故障),若元胞处于故障状态,则根据故障传递模糊控制规则库进行故障传递。

b.t+1时刻:根据当前元胞机状态及各元胞潮流相应采取切负荷(式(2))和无功补偿(式(3))控制措施,再次进行潮流计算,根据线路停运概率模型及元胞负载率隶属度函数完成元胞状态的更新。

3 基于电网故障模型的仿真实验

3.1 仿真流程

为了验证上述预防控制措施的有效性,搭建基于模糊元胞自动机的电网故障模型,并结合控制措施进行电网故障仿真。仿真实验采用MATLAB R2011b软件编程实现。仿真过程如下。

a.获得各元胞的潮流传输极限Pmax及初始无功潮流。

b.随机选择一个节点,增加负荷扰动ΔD,通过牛顿法求解电网潮流。

c.根据电网潮流得各线路负载率,按上述电网状态模糊控制规则库判断电网状态。

CaseⅠ:电网状态为正常,对电网中所有元胞进行扫描式检测。若各元胞经停运概率模型检测后仍正常运行,则不采取任何控制措施;否则元胞为故障状态,转步骤d。

CaseⅡ:电网状态为紧急,首先根据无功补偿控制措施调整个别元胞的无功,然后对电网中所有元胞进行扫描式检测。若各元胞经停运概率模型检测后仍正常运行,则判断该元胞状态,若元胞为正常状态,则不采取任何控制措施,若元胞为紧急状态,则采取集中切负荷的控制措施;否则元胞故障,转步骤d。

CaseⅢ:电网为极端紧急状态,系统解列,转步骤f。

d.切除故障元胞并根据故障传递模糊控制规则库进行故障传递。

e.判断电网是否因元胞失效而有负荷点被切除进而形成孤岛或系统解列,如有则转步骤f;否则转步骤b。

f.统计损失负荷,一次故障演化结束。

重复以上步骤100次,其实验流程图如图7所示。

3.2 一次故障演化过程仿真

利用上述构造模型在IEEE 39节点系统上进行仿真,在仿真过程中,每增加一次扰动,计算出各元件负载率后按由大到小排序,在双对数坐标图中绘出其分布曲线,观察随着扰动的增加负载率分布曲线的变化情况。根据已有理论基础及仿真经验,假设电网中各元件初始负载率在区间[0.55,0.95]内随机分布,一次事故演化过程中,负载率分布曲线如图8所示(图中横轴取值为元胞序列号的双对数值),其一次事故演化的仿真过程如图9所示(图中虚线表示在不同时间内断开的线路)。

初始状态下,元件负载率在给定区间内随机分布,其分布曲线的斜率k为-0.156 6,如图8(a)所示;持续随机选择负荷节点增加负荷扰动,部分线路元件的负载率增大,则元件负载率分布曲线斜率绝对值增大,直到电网由正常状态演化为紧急状态,如图8(b)所示,此时k=-0.1702;继续增加扰动,当演化达到一定程度(图8(c)),线路4-5所传输的感性无功突变为容性无功,则利用电抗器进行无功调整,QL=2.06 p.u.,此时k=-0.173 1;随着扰动的增加,处于紧急状态的电网进一步演化,当k=-0.1781(如图8(d)所示)时,线路15-16由正常状态转换为紧急状态,此时对节点15采取切负荷的控制措施,ΔP=0.828 p.u.;然后,电网演化为图8(e)的状态,此时k=-0.187 6,线路14-15过载断开,线路13-14、23-24所传输无功功率大幅度增大,则利用电容器进行无功调整,分别取QC=14.186 p.u.、QC=1.621 p.u.,同时线路17-27由正常状态转换为紧急状态,此时对节点27采取切负荷的控制措施,ΔP=15.267 p.u.;持续增加扰动,电网进入极端紧急状态,如图8(f)所示,此时k=-0.3593,线路8-9、9-39相继过载断开,电网解列为两部分(图9),一次故障演化结束。

3.3 仿真结果分析

为了验证上述控制措施在电网演化过程中的作用,基于IEEE 39节点系统,对上述FCA模型分别进行不添加控制措施及添加控制措施后的电网故障仿真模拟各100次,得到故障发生时损失负荷的故障时间序列及损失负荷的标度频度幂律曲线。

2种情况下的故障时间对比如图10所示。

由图10可知,按照上述控制规则添加控制措施后,电网模型发生100次故障时所承担的扰动次数大约为7000次,远大于不添加控制措施时模型所承担的扰动次数。假设以上扰动在电网中每天发生一次,即电网发生100次大停电事故的天数由4 300 d(图10(a))延长至7 000 d(图10(b)),极大地提高了电网的稳定性。

添加控制措施前后的损失负荷幂律曲线如图11所示。由图11可知,添加控制措施后,拟合曲线斜率绝对值明显增大,电网更加稳定;且同等故障次数中,产生较大损失负荷的故障次数较控制措施使用前明显降低(标度>3区域);同时,损失负荷规模较控制措施使用前维持在同等水平。

综上所述,控制措施的增加,一方面使电网故障发生的时间间隔大幅度延长,降低了电网事故发生的频率;另一方面故障规模较控制措施使用前没有上升,且损失负荷幂律曲线斜率绝对值增大,产生较大规模损失负荷的故障次数明显减少,极大地提高了电网的稳定性,验证了上述控制措施的有效性。文献[12,13,14]虽然都在不同方面就切机切负荷控制措施展开了深入研究,但是并没有全面考虑控制措施使用时刻、位置及调整量这些重要因素,本文基于模糊元胞自动机的电网控制措施的使用,在考虑上述重要因素的基础上达到了减小电网故障发生规模及频率的目的。

4 结论