有关基于自适应蚁群算法在急救车辆调度上的应用毕业论文写作资料-论文写作网

简介:适合算法路径论文写作的大学硕士及相关本科毕业论文，相关算法路径开题报告范文和学术职称论文参考文献下载。

算法路径论文范文

摘要：针对基本型蚁群算法迭代次数多,搜素时间较长,收敛速度慢的缺陷,采用改进的自适应蚁群算法,根据全局最优解的分布情况自适应地进行信息素范围的更新,从而动态地调整各路径上的信息素强度,同时,建立数学模型,给出求解TSP问题的改进算法,仿真出通过改进的自适应蚁群算法得到的最优路径,应用到患者位置与急救调度站之间最优路径的选择.结果表明,该模型和算法在收敛速度和迭代次数上均优于基本型蚁群算法.

关键词：自适应蚁群算法；迭代次数；收敛速度；最优路径

中图分类号：TP312 文献标识码：A

1. 引言(Introduction)

120急救指挥系统在城市应急指挥体系中具有非常关键的作用,当患者拨入急救电话或者遇到重大事故和突发事件时,指挥中心需要根据患者位置或者事故位置选择最优路径快速将患者送往医院进行急救[1].最优路径的选择需要考虑起点和终点之间的总里程数,人流量及客流量等外界因素.基本蚁群算法搜索时间较长,而且容易出现停滞,易陷入局部最优解等缺陷[2].此次设计的自适应蚁群算法主要根据全局最优解的分布情况,通过计算得出迭代次数不断增加的同时,自适应地减小蚁群觅食过程中的视野范围,提高获取最优解的速度,从而动态地获取各路径上的信息量强度,提高了全局搜索能力,避免了局部收敛和早熟现象.在模拟寻找最优路径过程中,设置多个节点模拟起点和终点之间的障碍物,以类似蚂蚁觅食的方式在求解复杂组合优化的问题上取得了良好的仿真效果,能够对急救车辆到达患者位置之间的多条路径进行模拟和优化.

2. 基本蚁群算法(The basic ant colony algorithm )

基本蚁群算法是20世纪90年代由意大利学者M.Dorigo等人首先提出来的一种新型的模拟进化算法,称之为蚁群系统[3].基本蚁群算法主要解决TSP(Tr论文范文eling Sale论文范文an Problem)旅行商问题,QAP(quadratic Assignment Problem)分配问题、JSP(Job-shop Scheduling Problem)调度问题等,取得了一系列较好的实验结果.基本型蚁群算法分为正反馈以及分布式计算.正反馈过程的优势是能较快的找到问题的较好解；分布式的优势是易于并行实现,同时与启发式算法相结合,能使该方法易于找到更好的解,最后达到最优解[4].基本蚁群算法的原理图如图1所示.

其中A是起点(蚂蚁所在位置)、E是终点(食物源)、HC为障碍物,从起点到终点的选择路径有两条,ABHDE或ABCDE,其中ABCDE路径最短,经过时间的推移,更多蚂蚁会选择ABCDE路径,直到最终选择ABCDE路径,实现寻优过程[5].基本蚁群算法描述如下：

(1)觅食行为：设蚁群当前的状态为Sa,在信息素对应的范围内随机选择一个状态Sb,则

其中,函数Random()产生0到1之间的随机数,Vision为信息素范围.如果食物浓度Ca>,Cb,则向该方向前进一步,为

其中,step为蚂蚁每次移动步长.每移动一次,判断是否里信息素更近,反之,再重新随机选择状态Sa,重新判断是否满足前进条件,试探一定次数后,如果仍探测不到有效的信息素,则执行其他行为,如随机移动行为

最短路径算法:[第17集] 最短路径算法：Dijkstra算法，广度优先搜索

(2)聚群行为：设蚁群的当前状态为Sa,探测其邻近的伙伴数目nf,如果表明伙伴中心有较多的实物且不太拥挤,并且Ca>,Cb,则向中心位置Sa前进一步,为

否则,执行其他区域的觅食行为.

(3)随机行为：蚁群在一定的视野范围内随机选择一个方向,然后向该方向移动,为

)

3 改进的自适应蚁群算法模型(Improved adaptive ant colony algorithm model)

从基本蚁群算法中发现,参数视野值对最优解的影响比较大,经过多次实验发现,在视野范围不变的情况下,算法后期的收敛速度较慢,迭代次数逐渐增加,并且当起点与终点之间节点越多,越容易陷入局部最优,无法达到全局最优；但是如果给定视野范围过小,收敛速度会有适当加快,但是更容易陷入局部最优.经过多次论证,当参数视野值为原始视野值60%时,收敛速度最快,且迭代次数最少,最接近全局最优解值.算法表达式为

改进的蚁群算法求解最短路径的步骤如图2所示.

算法实现的流程图如图2所示.其中,输入原始数据后会获取路网节点数、各节点的具体坐标位置,节点的权值矩阵、自适应蚁群的群体规模、最大迭代次数、蚁群的最大移动步长、拥挤度因子等参数.

4. 算法的仿真(The simulation algorithm)

现将改进的自适应蚁群算法与基本蚁群算法求解最优路径进行仿真,并将两者结果进行对比,仿真工具为MATLAB 2010a,蚁群规模n等于50,留在每个节点上的信息受重视程度α等于0.1,启发式信息受重视程度β等于0.5,蚂蚁数目20个,最大迭代次数100次.图3为起点与终点之间有七个信息节点,利用自适应蚁群算法得到的最优路径仿真示意图,得出的路径为1—2—3—5—9—8—4—6—7,其中最短路径为1—2—3—5—9.图4为自适应算法与基本型蚁群算法在寻优过程中的对比,两种算法分别在第二次和第五次迭代后搜索到全局最优解.

5. 结论(Conclusion)

针对基本蚁群算法收敛速度慢,运算量大,陷入局部最优的缺陷,本文提出一种自适应蚁群算法,使其随着全局最优解的变化而适当的改变视野范围的值.实验结果表明,改进的自适应蚁群算法在收敛速度、迭代次数、计算量,寻优精度均优于基本型蚁群算法,适用于在急救车辆调度过程中实现最优路径的规划,为急救车选择最优路径到达患者位置提供了有利依据.

参考文献(References)

[1] 杨丽锦.浅析蚁群算法的原理及应用方向[J].电脑知识与技

术,2009(6):12-14.

[2] 杨琼.具有感知觉特征的蚁群算法在连续函数优化中的应用[D].四川师范大学,2009.

[3] 马宪民,刘妮.自适应视野的人工鱼群算法求解最短路径问题

[J].通信学报,2014(1):16-17.

[4] 蒋艳玲,张军.蚁群算法的参数分析[J].计算机工程与应用,2007(20):34-35.

[5] 王晔,吴晓军.基于改进人工蚁群算法的RBF网络及其在人脸表情识别中的应用[J].计算机应用研究,2008(9):28-30.

作者简介：

周桂宇(1986-),女,硕士,助教.研究领域：网络环境下智能信息处理与自动化数据采集.

张桐(1980-),男,硕士,讲师.研究领域：现代物流装备及自动化.

总结：本论文主要论述了算法路径论文范文相关的参考文献,对您的论文写作有参考作用。