资源描述：
《基于蚂蚁寻径原理的最优路径选择算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第26卷第7期(总第175期)系统工程Vol.26,No.72008年7月SystemsEngineeringJuly.,2008文章编号:1001-4098(2008)07-0108-04基于蚂蚁寻径原理的最优路径选择算法1,233张毅华,郑长江,丁金学(1.东南大学经济管理学院,江苏南京210096;2.河海大学水电学院,江苏南京210098;3.河海大学交通学院,江苏南京210098)摘要:蚂蚁算法在动态路径寻优方面具有特有的优势。文章首先阐述了蚂蚁寻径原理,在长春市驾驶员调查问卷的基础上,对驾驶员的偏好
2、性进行了分析。在蚂蚁寻径原理的基础上,结合驾驶员的偏好性,提出了一种能够综合反映驾驶员偏好的最优路径选择算法。算法以调查问卷得出的驾驶员最为关心的三类因素——行程时间、行驶距离和道路等级为考虑因素,以驾驶员对路径的硬性要求为约束条件,通过对偏好性参数的标定,体现驾驶员在路径选择上的不同偏好。最后以算例进行验证,表明算法具有很好的可行性和适用性。关键词:蚂蚁寻径原理;驾驶员偏好;路径选择;优性服务因素;劣性服务因素中图分类号:U491文献标识码:A传统上,交通流诱导系统向司机提供的“最优”路径是物随时间推移会逐渐挥
3、发消失。周围蚂蚁能感知这种物质一条唯一路径,一般均是以行驶距离最短或行驶时间最短的存在及浓度,并倾向于朝信息素浓度高的方向移动。即为目标。这与实际情况并不符合,驾驶员出行前起讫点间选择该路径概率与当时这条路径上该物质的浓度成正比。最优路径的选择和确定受多种因素的影响,是多因素联合信息素浓度越高的路径,选择它的蚂蚁就越多,在该路径作用下的结果。驾驶员在出行前最优路径选择准则方面表上留下的信息素的浓度就更大,而浓度大的信息素又吸引现出多目标性以及多属性的特点。不同的驾驶员基于不同更多的蚂蚁,从而形成一种正反馈。通过这
4、种正反馈机制,的目标,会选择不同的最优出行路径,即使对于同一驾驶蚂蚁最终可以发现最佳路径。员在不同的时间段,由于不同的考虑目标,也会选择不同如图1所示,位于节点A和B的蚂蚁选择支路的概率的最优出行路径。基于此,国内许多学者先后提出了多种是相等的,假设在节点A的两只蚂蚁1和2分别选择ACB[1-4]基于驾驶员偏好的最优路径选择方法,但这些方法多和ADB向B前进,同样在节点B的两只蚂蚁3和4分别选都运用层次分析法和灰色评价理论,无论是模型的标定还择BCA和BDA向A前进。蚂蚁移动的速度相同,在蚂蚁行是模型的求解都有待
5、进一步的改善。进的过程中每个蚂蚁均留下了同样数量的信息素的痕迹,蚂蚁算法在动态路径寻优方面表现出了特有的优势,且支路ADB比ACB短,结果经过一段时间后,蚂蚁2和4[5-7]许多学者也进行了深入的研究,但是在路径选择过程经过ADB到达B和A,而蚂蚁1和3还在支路ACB的途中。中大都没考虑驾驶员的偏好性。本文旨在国内许多学很明显支路ADB上留下的信息素的痕迹浓度要高于支路[5-11]者研究成果的基础上,基于蚂蚁寻径原理,建立一种ACB上的信息素浓度;此后若再有蚂蚁到达节点A和B能够综合反映驾驶员多种偏好的最优路径选
6、择模型。时,由于受到信息素痕迹的诱导它们选择支路ADB的概率就会较大,反过来它们又不断地增加支路ADB上的信[7-8]1蚂蚁寻径原理息素痕迹的浓度,形成正反馈作用;与此同时,遗留在支路通过昆虫学家的研究和观察发现,蚂蚁在运动中会在ACB上信息素的痕迹还会因不断的挥发而进一步的减经过的路径上留下一种挥发性分泌物(信息素),这种分泌弱。这样一来,选择走支路ADB的蚂蚁就会越来越多,选收稿日期:2008-03-28基金项目:教育部博士点基金资助项目(20060286005)作者简介:张毅华(1975-),男,湖南永州
7、人,东南大学经管学院博士,河海大学水电学院教师,研究方向:复杂系统建模,综合交通运输。第7期张毅华,郑长江等:基于蚂蚁寻径原理的最优路径选择算法109择走支路ACB的蚂蚁就会越来越少,最后呈现有较强的最短路径。信息素痕迹的那些支路便会形成一条从蚁穴到食物源的(a)蚂蚁开始选路(b)蚂蚁完成选路图1蚂蚁寻径原理离、费用、道路等级和拥挤程度。在所有这些可供选择因素2基于蚂蚁寻径原理的路径选择模型中可以分为优性服务因素(指数值越大或越多,出行者的[9]满意程度就越高的因素,如路段速度、道路等级、路面质2.1驾驶员偏好性
8、分析量、熟悉程度等)和劣性服务因素(指数值越小或越少,出通常,驾驶员在出行前最优路径选择方面会表现出多行者的满意程度就越高的因素,如时间、距离,费用等)。样性,会根据个人的偏好和出行的目的选择性质和功能不为便于讨论,本文选取其中驾驶员最为关心的几类因同的路径。吉林大学对长春市各类驾驶员进行了驾驶员路素,由于耗油、收费以及拥挤程度等可以通过时间变相的径选择偏好抽样问卷调查,
