基于元胞自动机的启发式算法的改进

将元胞自动机应用于机器人路径规划,对移动机器人及其周围环境建立元胞自动机模型。机器人环境空间完全已知时,利用启发式算法与元胞自动机模型结合的方法,通过反复遍历具有最低耗费值的一系列元胞生成最优路径。并利用多层次的交互式元胞自动机,在方向有约束和地形耗费不同的环境中实现机器人的路径规划。     

基于改进元胞蚁群算法的铁路取送车问题研究

为了有效并且快速地解决树枝型专用线取送车问题,文章提出了一种基于元胞自动机(cellular automata,CA)模型的改进蚁群算法,即改进元胞蚁群算法(improved cellular ant colony algorithm,ICACA)。通过对蚁群算法中的转移概率以及信息更新策略加以改进,同时将元胞的演化规则和蚁群的信息素更新规则结合,提高了蚁群的全局优化能力;为了防止陷入局部最优,算法中设计了交换策略。仿真结果表明,文中提出的ICACA能够有效提高取送车作业问题的效率。     

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

利用元胞自动机模型解决移动机器人的运动路径规划问题。该算法环境空间已知且被分解成规则的方形元胞网格,机器人根据转换规则由当前元胞向邻居元胞移动最终形成最优路径。最后在实验环境中进行仿真,结果显示在机器人起点和终点的运动方向有约束的情况下也能迅速规划出最优路径,表明了该算法的可行性和有效性。     

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

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

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

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

涌现计算概述

通过4个实例：蚁群最短路径算法、粒子群优化算法、一维元胞自动机和粘茵的涌现计算,阐述了涌现计算的基本思想和方法,并对涌现计算中的一些问题进行了总结与展望．     

基于蚁群算法的多智能体模拟城市用地扩张

本文把蚁群算法引入到多智能体（Multi Agents,MAS）模型中来模拟城市演变过程。智能体(Agent)在元胞自动机（Cellular automata ,CA）确定城市发展概率的基础上,通过蚁群算法来寻找最大效用值的元胞地块,建立一个能模拟多个自然因素以及不同决策者共同影响的城市用地扩张模拟系统。实验表明,引入蚁群算法的模型能更好地模拟了城市演变过程。     

基于元胞自动机的单源点最短路求解算法

针对图的单源点最短路问题,提出一种改进的基于元胞自动机模型的求解算法并分析了其算法复杂度.该算法定义了一个元胞自动机模型,通过元胞空间上元胞状态的变化,能够获得某设定结点到其他结点的最短路.在实验阶段,分别用经典Dijkstra算法和提出的算法对随机生成的不完全无向图进行分析.结果表明,相比于经典的Dijkstra算法,该算法不但能够获得与之相同的仿真结果,并且具有规则简单、易于实现、效率高等特点,具有明显的优越性.     

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

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

元胞蚁群算法的城市楼宇间无人机航路规划

近年来,城市环境中小型无人机越来越多,然而传统的航路规划算法通常将威胁简化,并不能很好地解决无人机在城市环境的航路规划问题。因此引入"元胞"定义飞行区间,对"数字元胞地图"以及"航路罚函数"进行定义,并利用蚁群算法进行航路规划,使其可以对任意不规则威胁进行规避。仿真对比实验表明,所提的基于元胞蚁群的算法可以在不对障碍模型进行简化的情况下进行合理规避,为无人机在城市环境中规划出一条安全可飞的航路。