基于蚁群算法车辆导航系统路由选择问题的研究.pdf

《基于蚁群算法车辆导航系统路由选择问题的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学术探讨基金项目2015年第11期基于蚁群算法车辆导航系统路由选择问题的研究*车高峰陆月然谭军（百色学院信息工程学院，广西百色533000）[摘要]利用蚁群运动的遍历性、随机性和规律性特点，分析了车辆导航系统路由选择问题的蚁群优化算法，仿真结果表明该方法是一种简单有效的算法。[关键词]蚁群优化算法；车辆导航系统；路由选择问题中图分类号：TP301文献标识码：A文章编号：1008-6609(2015)11-0046-02信息量决定转移方向，ps(t)表示在车辆s由点i转移到地点jij1引言的概率。在智

2、能交通系统中车辆导航系统占据重要地位，通过地αβìτij(t)∙ηij(t)图查询、路线规划、自动导航来确定车辆最优行驶路线，为出sïïαηifj∈allowedspij(t)=í∑τik(t)∙ηik(t)（1）k∈allowed行旅游者提供最优路线。车辆导航技术是多学科交叉的结ïïsî0otherwise晶，结合了导航卫星以及目标定位技术等。为了解决动态路其中alloweds={0，１…，n-1}-tabus表示车辆s下一步允由问题，学者提出了很多算法，如Dijkstra算法、A*算法等。许选择

3、的交通地点，tabus(s=1，2，…，m)用于记录车辆s当前上世纪90年代蚁群优化（AntColonyOptimization）算法由意所走过的地点，集合tabus随着进化过程做动态调整。ηij表大利学者M.Dorigo等人最早提出。由于蚁群算法有较强的1自适应性、鲁棒性，在寻优路径中取得了一系列较好的实验示路段(i，j)的能见度，利用启发式算法算出，一般取ηij=d,ij结果。本文基于蚁群算法对路由选择进行研究，同时避免在dij表示地点i与地点j之间的距离。α表示轨迹的相对重要路由选择过程中陷入

4、局部极值。性，β表示能见度的相对重要性。2路由选择问题的蚁群优化算法2.2信息更新规则路由选择问题是运筹学、组合优化等领域中一个著名的设ρ表示信息的持久性。1-ρ理解为信息衰减度。随着难题，由于其NP难题性质，迄今尚未能彻底解决。目前求解时间的推移，以前留下的信息逐渐消失，用参数1-ρ表示轨迹这类问题的主要方法有模拟退火算法[1-2]、遗传算法[3]、启发式信息消逝度，经过n个时刻，车辆完成一次循环，各路径上信搜索法、Hopfield神经网络算法[4]等。下面简单介绍蚁群基本息量要根据以下公式调整：

5、算法。τij(t+n)=ρ∙τij(t)+△τij（2）设某交通网络中有m辆车，每辆车有以下特征：车辆根m△τ=△τs（3）ij∑ij据以地点距离和路段上外激素的数量为变量的概率函数选s=1△τs表示第s辆车在本次路由中留在路段上ij的信息择下一个地点（设τ(t)为t时刻路段e(i，j)上外激素的强度）。ij规定车辆不允许转到刚刚到过的地点，有禁忌表控制（设ta-量，∆τij表示本次路由路段ij上的信息量增量,Ls表示第s辆bus表示第s辆车的禁忌表，tabus(k)表示禁忌表中第k个元车路由路径的

6、长度，Q常数。素）。它完成周游后，车辆在它每一条访问的路段留下外激ìQï若第s辆车在路由中经过ij△τs=L（4）素。ijísï2.1导航系统选择下一路段规则î0否则初始时刻，各条路段上的信息激素相等，设τij(0)=C（C为2.3车辆导航系统路由蚁群算法的基本步骤常数）。车辆s(s=1,2,…,m)在运动过程中，根据各条路段上（1）初始化迭代步数nc←0以及τij和∆τij的值,将m辆车——————————————作者简介：车高峰，男，山东烟台人，硕士，讲师，研究方向：现场总线技术、蚁群算法；*通

7、讯作者：陆月然，男，广西天等人，硕士，副教授，研究方向：物联网。基金项目：百色学院一般科研项目，项目编号：2014KB06；广西高校科学技术研究项目，项目编号：KY2015LX388；三亚市院地科技合作项目，项目编号：2013YD56。-46-基金项目学术探讨2015年第11期随机置于n个地点上；12，13，11，23，16，5，6，7，2，4，8，9，10，3，18，17，19，24，25，（2）将各辆车的初始出发点置于当前解集中,对每辆车s20，21，22，26，28，27，30，31，29。从

8、上图可以看出当算法迭(s=1,2,...,m),按概率pk移至下一地点j,将地点j置于当前代次数超过75次后，最优路径长度已经基本保持不变了，求ij得为1.5590e+004。解集；（3）计算各车辆行驶的路径长度Ls(s=1,2,...,m），记录当前的最好解；（4）按更新方程修改轨迹强度；（5）nc←nc+1；（6）nc<预定的迭代次数且无退化行为(即找到的都是相同解)则转（2）；（7）目前最好解。3实验仿真参数设置：迭代步数nc200；假设从出发地到目的地途经3