元胞自动机理论及其在登机问题研究中的运用

　　第二章 元胞自动机理论及其在登机问题研究中的运用

　　2.1 元胞自动机基本理论。

　　冯·诺依曼（Von Neumann）作为 20 世纪最伟大的数学家之一，由于他本人在计算机和博弈论等方面的诸多成就为人们所熟知。20 世纪中叶，他通过对复杂系统的逻辑抽象研究，提出了元胞自动机这一系统。随着计算机技术的逐步发展成熟，元胞自动机理论也不断丰富。1970 年，数学家约翰·康威（John Conway）提出了生命游戏机的概念，使元胞自动机开始可以模拟复杂系统。上世纪 80 年代，史蒂芬·沃尔弗拉姆（StephenWolfram）从动力学角度对元胞自动机进行研究，打开了元胞自动机应用的另一扇大门。

　　2.1.1 元胞自动机的概念。

　　元胞自动机（CellularAutomata,简称 CA）是一个时间和空间都离散的动力系统。

　　散布在规则网格中的每一个元胞取有限的离散状态，遵循同样的规则同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的方程或函数确定，而是用一系列的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的名称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

　　2.1.2 元胞自动机的构成。

　　元胞自动机最基本的元胞、元胞空间、邻居及规则四部分（如图 2-1）。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。

　　1、元胞。

　　元胞是元胞自动机最基础的构成部分，元胞的位置在元胞空间的格点上，不同的元胞具有不同的状态和形状。元胞的状态可以是二进制{0,1}形式，也可以是{S1,S2,S3,…Sj,…Sk}整数形式的离散集。

　　2、元胞空间。

　　元胞所在的空间网点数的集合就是元胞空间。研究中经常涉及的元胞空间有一维空间和二维空间。一维空间只有一种划分方式，二维元胞自动机通常有三种方式，三角形、正方形和六边形。

　　3、邻居。

　　邻居指的是元胞更新时可以影响的空间范围。不同维度的元胞空间元胞的邻居情况有所差别。一维空间中，元胞邻居的情况较为简单，由该元胞可影响的半径决定，但是对于二维元胞自动机而言，就有较多的划分方式，其中主要有 Von Neumann 型、Moore型和扩展 Moore 型 3 种形式，如图 2-3 所示。边界元胞的邻居不同于内部元胞，因此主要有周期型边界、固定边界、绝热边界和映射边界几种边界处理方式。

　　4、演化规则。

　　空间中的元胞根据自身以及邻域中元胞的状态确定下一状态的变换函数就是元胞的演化规则，这个规则本质上是一种状态转移函数，也是利用元胞自动机理论建模的核心。基于一定的演化规则，系统不断在时间和空间上进行迭代应用到所有的元胞中，从而推动整个元胞系统的不断演变，如果在迭代的过程中没有出现随机变量，则为确定性模型，否则为非确定性模型。

　　2.1.3 元胞自动机的原理及特征。

　　元胞自动机是大量简单相同的个体通过局部之间的相互关系组成的离散、空间可以扩张的系统，这种具有时间、空间状态均离散的动力学系统大致可以分为四大类：平稳型、复杂型、混沌型、周期型[38-40].

　　元胞自动机模型具有以下性质[41]:

　　1、同质性和齐性。

　　同质性是指元胞空间上每个元胞的演化都遵循相同的规则，即特定的转移函数来决定下一时刻元胞的状态。齐性是指形状、大小相同的元胞空间分布规则整齐。

　　2、离散性。

　　元胞自动机模型的离散性主要体现在元胞的空间离散性和时间离散性。

　　3、时空局部性。

　　周围邻居规则所定下的邻域中元胞的当前时刻 t 状态是决定每个元胞的下一时刻t+1 状态的位移因素，正因如此，元胞自动机才具有时间和空间的局部性。

　　4、同步性。

　　元胞的状态变化同步进行却又相互独立，相互没有任何影响，适合并行运算，这种算法要优于其他模型的工作方式，可以大大提高模拟的速度。

　　5、维数高。

　　维数是指元胞自动机所组成的动力系统中变量的个数。如果将区间映射生成的动力系统称为一级动力系统；将平面映射生成的动力系统称为二维动力系统；而对于偏微分方程描述的动力系统则称为无穷维动力系统[42].从这个角度上，元胞自动机属于一类无穷维动力系统，但在实际应用中，即使使用计算机模拟也不可能计算无穷个变量，便有了元胞自动机的简化。

　　通过上述元胞自动机的同质性、离散性、局部性等特点的简单介绍，可以得知不具备这些特点就不能称为元胞自动机，但在实际的应用中，学者根据自己研究的实际需要，对模型进行简化和扩展是可以实施的。

　　2.2 元胞自动机在旅客登机过程中的运用。

　　2.2.1 旅客登机过程。

　　登机效率的提升有赖于登机时间的缩短。如果想以更短的时间完成登机过程，我们首先需要了解登机过程中的影响因素，并对某些重要因素进行分析。对于某个航班，具体登机过程。

　　1、预登机区和登机口。

　　从整个登机过程来看，通常情况下，旅客听到登机通知后，会向对应的登机口聚集，这样很容易造成登机口附近区域的拥挤，从而使旅客进入登机口的速度下降。因此，在登机口附近设置预登机区[24],对登机口附近的旅客数量进行控制，从而使旅客更快的进入登机口以缩短登机时间；另外，多个登机口也可以加快登机速度[24].不仅如此，登机口的放行速度[14][24][43]与旅客进入机舱的速度相协调，这样可以避免放行速度过快导致旅客在廊桥中的拥堵或因放行速度过慢导致的登机效率下降，从而有效地减少登机时间。

　　2、廊桥。

　　旅客通过登机口后，进入廊桥。由于廊桥空间较小，很难在机舱口组织旅客，因此机场会在登机口处要求旅客以某种顺序排队并通过，以保证旅客也以相同的顺序进入机舱。通过登机口后，旅客就会进入廊桥，由于旅客个体之间存在一定差异，因此旅客在廊桥中的步行速度也会有所不同，会使旅客的排列顺序有所改变，从而影响登机时间。

　　现有大多数的登机策略研究没有考虑这里提到的在廊桥中旅客排列顺序有所改变的情况，而更多的是是直接对旅客进入机舱后的过程进行研究。

　　3、登机舱门。

　　旅客通过廊桥后会达到机舱门口，而登机舱门的开放数量[6]、登机舱门的使用[44]对于登机时间也有着很大的影响，尤其是空客 A380 等宽体客机，搭载旅客数量较多，影响会更加明显。

　　4、机舱。

　　对于旅客进入机舱后的登机过程则是影响登机效率的重要环节。旅客进入机舱的速度对于登机时间的影响也很大[14][45],合理的速度可以充分利用过道的空间，减少登机时间。旅客进入机舱的顺序是对登机时间产生影响最大的因素，因为旅客进入机舱的顺序不同，旅客在就坐过程中被其他旅客阻挡的程度（即干扰）就有所不同，现有的大部分研 究 侧 重 于 旅 客 进 入 机 舱 顺 序 对 登 机 时 间 影 响 这 一 方 面[6][8][12][13][14][17][18][19][20][26][23][29][46][47][48][49][50][51].在研究中，用干扰次数及时间来进行分析。干扰主要分为两种，一种是座位干扰，另一种是过道干扰[12].干扰最少，登机时间则最短。干扰受很多因素的影响，旅客进入机舱的顺序、旅客携带行李的数量[19][48][50]
等影响干扰数量，旅客摆放单件行李花费的时间、旅客在机舱中的行进速度等行为特征[13] [23][26]影响单个干扰时间。

　　2.2.2 元胞自动机与旅客登机过程的结合。

　　本章的第一节和第二节分别对元胞自动机的基本理论和旅客登机过程进行了介绍，本文对登机问题的研究是从第一名旅客到达登机舱门处到所有旅客就坐的整个过程，将元胞自动机与该登机过程结合，通过仿真，就可以得出使用不同机舱门、采用不同旅客放行速度以及不同登机次序的旅客登机时间。

　　旅客是旅客登机过程中的最基本实体，通过描述旅客在登机过程中的行进状态，从而对总登机时间进行计算。旅客在机舱中的行进行为是非常复杂的，本文将旅客在机舱内的行进行为简单划分为行进、主动停止和被动停止三种，这样的行进行为可以使用元胞自动机的 184 号规则来描述。下面对元胞自动机的 184 规则进行简要介绍。

　　Wolfram 在上世纪年代利用计算机模拟对一维元胞自动机的种规则做了详细研究。

　　（1）对于初等元胞自动机，其中变量有三个，每个变量取两个状态值，就有 2*2*2=8 种组合，只要给出在这八个自变量组合上的值，f 就完全确定了。例如一下映射便是其中一个规则：以上八个组合分别对应 0 或 1,所以这样的组合共有82 = 256种。184 号规则就是这256 种规则的一种，演示规则如图 2-5 所示，模型中代表有车的黑色块 1 用表示，代表无车的白色块用 0 表示。t 时刻，如果第 n 辆车的前方为空，则该车前进一格；如果第 n辆车的前方被第 n+1 辆车所占，则该车原地不动，即使本时间步里第 n+1 辆车离开前方元胞，该车也保持不动。

　　元胞自动机的 184 规则起初用于研究交通运输问题，在本文中对于描述机舱中旅客行进、主动停止和被动停止三种状态是一种切实可行的方法，因此本文采取元胞自动机的 184 号规则来编写仿真程序，以实现整个登机过程的模拟。

　　2.3 本章小结
　　
　　本章对元胞自动机理论进行了概括性的描述，从概念、构成和原理等方面对元胞自动机理论进行阐释，并详细介绍了本文采用的元胞自动机 184 号模型的基本原理。同时着重对旅客登机过程进行了分析，以旅客登机过程中的位置变化为参考，详尽梳理了对旅客登机过程产生影响的因素，并讨论了元胞自动机方法在登机过程中的运用，为下一章中宽体客机旅客登机模型的建立提供理论基础。