基于元胞自动机的拓扑排序算法

目的 利用元胞自动机的特性,找到一种新的拓扑排序算法.方法 将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序.结果 利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法.结论 与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献.     

城市交通优化中基于对偶算法的元胞自动机

对基于换乘时间的城市交通优化问题进行了数学模型分析,根据模型的对偶原理得到了问题的对偶算法,设计了元胞自动机.在元胞自动机中,以每一个站点作为一个元胞,根据是否获得最佳乘车线路将元胞分为2种状态,将中心元胞的下一个站点作为其邻居,演化规则只作用于未获得最佳乘车线路的元胞,并只需通过对演化时间与元胞的相应权值的比较来确定状态的改变.基于对偶算法元胞自动机具有元胞状态少、邻居关系简单、演化规则简便和计算量少的特点.仿真实验说明了基于对偶算法元胞自动机的有效性和可行性.     

利用MATLAB和VC++6.0混合编程技术研究元胞自动机动态演化过程

在论述MATLAB和VC 6.0混合编程的基础上,以二维方格元胞自动机的动态演化过程为背景,对不同边界条件和邻居条件的二维方格元胞自动机在奇偶演化规则下的动态行为进行分析,并通过混合编程技术对其动态演化过程进行"可视化"再现和跟踪,得到了元胞自动机在不同条件下其演化过程具有复杂性、不确定性、平衡性、周期性以及分形性等特性的结论,为进一步发掘和揭示元胞自动机的演化规律提供了研究思路和方法.     

基于模糊元胞自动机的复杂图案、纹理生成实现

结合模糊规则和元胞自动机的机理,分析了模糊元胞自动机的基本原理,根据元胞自动机的不同构形,提出多种模糊元胞自动机演化规则,并根据这些基本规则,分别用3邻元、5邻元以及9邻元进行元胞状态更新,生成了多颜色\复杂、漂亮的图案和织物纹理,其结果在针织织物设计中意义重大.     

机器人路径规划的元胞自动机算法

采用Moore型邻居规则建立机器人路径规划的元胞自动机模型和演化规则,通过对移动机器人的路径进行演化,讨论了周围环境已知情况下的移动机器人元胞自动机路径规划问题。在演化规则中增加危险度检测,使得机器人能够避免碰撞和穿越障碍,仿真实验结果表明,利用元胞自动机可以实现复杂环境的机器人路径搜索,避免死锁和碰撞,达到快速的最优路径。     

确定的有限元胞自动机的两个性质

提出了确定的有限元胞自动机的概念,通过对演化构形的惟一性特征的分析.证明了确定的有限元胞自动机的状态演化最终处于稳定状态或者循环状态;具有相同演化结果的状态构成等价关系两个性质.利用初等元胞自动机对其进行了验证,在此基础上,对元胞自动机的四个普遍性分类进行了三个层次的探讨.     

基于多元胞模型的桥梁车流合成及荷载模拟

随机车辆荷载模拟是桥梁荷载评定和性能评估的基础和关键,目前基于Monte Carlo的车流模拟较难呈现长加载跨径内车流的微观动态演化特性,而基于元胞自动机(CA)的单元胞模拟方法在加载精度方面仍需改进.单元胞模拟法中,将每个车辆用一个元胞模拟,难以体现轴重影响,限制了模拟精度的提高.在此基础上,提出了每个元胞模拟一个车轴,多个元胞模拟一辆车的多元胞自动机(MCA)模型,并利用实测车流及其荷载数据进行模型校核.研究表明:多元胞车轴模拟方法能够准确地还原车流量、车头时距、车速、车重等系列车流以及荷载参数.以1 000m虚拟加载跨径的荷载集度、支点剪力、跨中弯矩为指标,统计模拟车流和实测数据的荷载响应特性.结果显示,MCA模型的模拟结果与实际车流误差均在5%以内,相较于传统单元胞模型17%的误差,精度显著提高.     

基于元胞自动机的深部采矿岩体变形的演化模型

根据深部采矿岩体变形的离散性特征,运用元胞自动机建模方法构建深部采矿岩体的变形演化模型;利用元胞岩石的状态变化概率和元胞状态变化的影响系数,实现深部采矿岩体的动力学模拟.在演化模型的基础上,进行了模拟实验,且运用R/S分析法对结果进行分析,得到了以离散度作为岩体稳定性的标准.     

基于元胞自动机模型的开采沉陷模拟

 开采沉陷模拟对矿区的环境治理和生态恢复具有重要意义.本文将开采沉陷理论与地理元胞自动机相结合,基于GIS平台,以VS2010为开发工具,利用面向对象的方法,构建了开采沉陷元胞空间,探讨了开采沉陷元胞自动机模型的框架结构及实现方法,构建了开采沉陷模拟对象关系图,建立了开采沉陷元胞自动机演化模型.以山西某煤矿为例,开发了开采沉陷元胞自动机原型系统,根据研究区的煤层条件和开发方法,进行了模拟实验,分析未来开采沉陷的演变过程,为土地复垦和生态修复提供依据.结果表明,采用面向对象的方法能够较好地进行开采沉陷系统分析和开发,基于GIS和CA进行开采沉陷模拟,开发方便,系统兼容性好,能够展示更多的时空信息,便于数据管理.在空间划分上,CA模型能够与传统的预计方法有机融合,较为准确地预测未来的地表塌陷损毁情况,为塌陷区治理提供依据.由于开采沉陷涉及的学科较多,未来还需进一步完善演化模型,探讨三维空间下的系统演化过程,提高模拟的真实感和实用性.     

基于元胞自动机的井巷火灾仿真

提出了一种基于元胞自动机的井巷火灾可视化仿真方法.在矿井巷道可视化的基础上,通过对火灾元胞进行表征,综合考虑可燃物类型与投放密度、井巷通风、井巷坡度等因素对井巷火源引燃效果的影响及双扩散作用、井巷通风、浮力作用和节流作用等因素对火灾烟气蔓延效果的影响,采用概率函数进行元胞自动机建模,构建了表达元胞温度的井巷火源燃烧模型和表达元胞浓度的井巷火灾烟气蔓延模型.基于火源元胞燃烧演化规则和烟气元胞蔓延演化规则,通过可视化手段展示了井巷火灾火源燃烧和有害气体浓度的时空发展变化.同时以矿山实际数据进行检验,说明了基于元胞自动机的井巷火灾仿真的可行性与有效性.