基于可演化硬件的交通流模型自适应优化及B样条曲面拟合应用

# 基于可演化硬件的交通流模型自适应优化及B样条曲面拟合应用 ## 1. 引言 在交通流理论研究中，元胞自动机（Cellular Automata, CA）模型被广泛应用。其中，由Biham、Middleton和Levine提出的二维理想交通流模型（BML模型），成为研究城市道路网络结构中交通流特性的重要基础。不过，基于软件的交通流模拟和进化优化效率普遍较低，极大地限制了交通流模型在一些实时性和高速性要求较高场景中的实际应用能力。这主要是因为在进化算法的适应值评估阶段，元胞群体的进化采用串行处理方式，耗费大量时间。 为解决这一问题，可从元胞自动机模型的内在并行性角度出发，以可演化硬件（Evolvable Hardware, EHW）为基础，对交通流模型进行自适应优化。同时，在B样条曲面拟合方面，采用进化算法也能取得较好的效果。 ## 2. BML模型的并行进化 ### 2.1 BML模型 城市交通网络通常相互交织，存在大量交叉路口，形成特定的道路网络结构。1992年，在元胞自动机理论的指导下，Biham、Middleton和Levine提出了二维城市交通流模型（BML模型）。在该模型中，城市交通网络用一个NxN的二维方格矩阵表示，每个网格点有3种状态，用Si,j={0,1,2}表示。其中，2表示在第I行第j列的网格点有一辆从北向西行驶的车辆；1表示有一辆从西向东行驶的车辆；0表示该点没有车辆。规则要求，在每个奇数时间步，东西向行驶的车辆向前移动一个网格点；在每个偶数时间步，南北向行驶的车辆向前移动一个网格点。如果车辆前方的网格点被其他车辆占据，即使该车辆此时受阻无法前进并为其他车辆腾出空间，它也只能保持静止。 通常，元胞自动机进化的软件模拟是在整个矩阵上逐个扫描元胞，然后计算下一代元胞群体的状态值。这种串行执行方式无法充分利用元胞自动机的并行进化特性，反而限制了元胞群体的进化速度。在一些实时、高速应用中，元胞自动机应采用并行计算方法进行进化。 ### 2.2 FPGA基于BML模型的实现 BML模型规定，网格点上的元胞根据时间步的奇偶性分别进行水平和垂直进化，每个元胞取{0,1,2}三种状态，邻域半径为1。因此，二维元胞自动机的进化规则可定义如下： - **东西向交通规则**： - 如果$S_{i}^{t}=2$，则$S_{i}^{t + 1}=2$ - 如果$S_{i}^{t}=1$，则$\begin{cases}S_{i + 1}^{t}\neq0,S_{i}^{t + 1}=1\\S_{i + 1}^{t}=0,S_{i}^{t + 1}=0\end{cases}$ - 如果$S_{i}^{t}=0$，则$\begin{cases}S_{i - 1}^{t}=1,S_{i}^{t + 1}=1\\S_{i - 1}^{t}\neq1,S_{i}^{t + 1}=0\end{cases}$ - **南北向交通规则**： - 如果$S_{i}^{t}=1$，则$S_{i}^{t + 1}=1$ - 如果$S_{i}^{t}=0$，则$\begin{cases}S_{i - 1}^{t}=2,S_{i}^{t + 1}=2\\S_{i - 1}^{t}\neq2,S_{i}^{t + 1}=0\end{cases}$ - 如果$S_{i}^{t}=2$，则$\begin{cases}S_{i + 1}^{t}\neq0,S_{i}^{t + 1}=2\\S_{i + 1}^{t}=0,S_{i}^{t + 1}=0\end{cases}$ 根据上述进化规则，可将一个元胞单元设计为一个三输入输出的硬件模块，输入值为元胞的当前状态及其左右邻域的状态，输出值为元胞的下一个时间状态。由于单个元胞在奇数和偶数时间步的进化规则不同，分别应满足上述两个公式，因此这两个规则应写入两个模块。当元胞自动机开始进化时，这两个模块将在等距分配的时钟周期内依次执行。 在元胞自动机元胞群体的进化过程中，由于同时采用相同的进化规则，可设计行处理模块对每行的每个元胞进行并行处理（使用南北向规则时，即对每列的元胞进行处理）。同样，从行到行（或从列到列）也是并行进化，因此可对上层行（列）处理模块进行重新封装。这样，二维元胞自动机中的元胞群体就可以实现每个元胞状态的并行进化。 ### 2.3 实验结果与分析 采用Xilinx的Virtex - II Pro系列开发板、型号为XC2VP30 - 6ff896的FPGA芯片以及集成开发环境ISE9.1i来实现BML模型的并行进化，并使用Verilog HDL语言编写硬件功能模块。元胞群体的初始状态由外部信号输入。从逻辑上看，元胞群体排列成二维矩阵，但在实现过程中，该网格矩阵用一维向量按行表示，每个网格点有三种状态。例如，要设置一个20×20的元胞矩阵进化，使用一个800位的寄存器变量来