基于蚁群算法的公交路线走向模型
第6卷第2期2007年4月 江南大学学报(自然科学版)Journal of Southern Yangtze U niversity(N atural Science Edition)
Vol.6 No.2Apr. 2007 文章编号:1671-7147(2007)02-0239-04
收稿日期:2005-11-23; 修订日期:2006-01-12. 基金项目:浙江省自然科学基金项目(601119).
作者简介:金孟合(1982-),男,浙江温州人,系统工程专业硕士研究生.
3通讯联系人:王慧(1959-),女,江苏无锡人,教授,硕士生导师.主要从事复杂过程模型化及优化,智能控制与
计算智能研究.Email :hwang @https://www.wendangku.net/doc/4f4866769.html,
基于蚁群算法的公交路线走向模型及其求解
金孟合, 王慧3
(浙江大学系统工程研究所,浙江杭州310027)
摘 要:建立了新的公交路线走向的数学模型.该模型以动态直达人数为目标,路线的非直线系数
为限制条件,并结合蚁群算法给出了求解路线优化设计模型的相应步骤.通过对案例的仿真,证明了该模型及求解算法的可行性和有效性.
关键词:公交网络;路线走向;动态直达人数;蚁群算法中图分类号:O 224文献标识码:A
A N e w Bus Routing Problem Model and Its Solution
Algorithm B ased on Ant Colony
J IN Meng 2he , WAN G Hui 3
(Institute of Systems Engineering ,Zhejiang University ,Hangzhou 310027,China )
Abstract :Bus routing problem is an important part of p ublic traffic network design.In t his paper ,t he mat hematic model of bus routing problem ,which takes t he maximum sum of dynamic nonstop passengers wit h bending modulus restricted ,is established and t he solution algorit hm based on ant colony algorit hm is developed.The feasibility and efficiency of t he algorit hm are verified by applying it to a sample system.
K ey w ords :p ublic t raffic network design ;bus routing p roblem ;dynamic arrived people ;ant colony algorit hm
公交网络设计中路线走向问题是指在公交网络优化设计过程中,在确定起讫点以后,以某一优化指标(如直达人数最多、路线最短等)为目标函数,选出一个最佳的公交路线走向方案.但在现实生活中,一条公交路线除了起点及终点外,中途所经过的站点和路段也很重要,因为公交路线的走向选择会受到各种限制,如最好避开拥挤路段、非直
线系数(指公交路线的实际长度与空间直线距离之
比)不能太大等等,所以必须考虑公交路线的走向问题.
目前,许多研究者将这一问题简单处理,即起讫点A 和B 一旦配对,A B 间的路线直接按最短路线法则确定[123],这样做虽然简单,但却不太符合实际,也可能不符合优化目标.因为在不是以路程长
度为单一优化目标的情况下,最短路线不一定是最优路线.针对这种情况,文中提出了一种基于蚁群算法求解的公交网络设计中路线走向问题模型,设计了相应的求解算法及程序,并用该算法对文献[1]中的一个算例进行了仿真.结果表明,文中提出的优化方法是可行、有效的.如果将文中模型和交通出行矩阵(OD)流量分配算法相结合,还可以依次生成多条路线,进而形成公交路网.
1 模型的建立
在公交网络设计中,一条路线所确定的直达人数是一个重要的优化目标.大多数文献都是将起讫点之间的OD量视为一个不会随着路线改变而变化的固定值.然而,由于出行手段的多样化,人们外出有了更多的选择.例如一条公交路线的非直线系数必然会对这条路线的吸引人数产生一定影响,即若这条公交路线绕弯太多,使乘客出行的时间成本过高,那么乘客就会减少,该条路线的直达人数随之减少.一般要求非直线系数k≤115[3].因此,为了兼顾直达人数和路线非直线系数,考虑到路线非直线系数对直达人数的影响,文中提出了动态直达人数概念,因为设计的公交路线可能是非最短路径,有部分乘客可能会选择其他的出行方式,导致直达人数存在一定的变化,故将动态直达人数定义为直达人数除以路线的非直线系数.以规定的起讫点之间动态直达人数最多为目标函数,非直线系数为约束条件,建立了设计公交路线走向的数学模型
max F=c ij
k ij
(1)
其中k ij=S ij
D ij
s.t. k
ij
≤k′
式中:k′为k ij所能取的最大值,是一个设定的常数; F为起讫点i,j配对后整条线路上动态直达人数;c ij 为起讫点i,j配对后整条线路上的直达人数;S ij为起讫点i,j配对后整条线路的长度;D ij为起讫点i,j 在地理上的直线距离.
2 蚁群算法原理及在公交路线走向问题模型中的应用
根据公交路线走向设计的优化命题,作者选择了蚁群算法.这是由意大利Dorigo M等首先提出的一种模拟蚂蚁外出觅食时在所经过路径上留下一种“外激素”行为的启发式优化算法[4],其主要特点是整个蚂蚁群的行为形成了正反馈、分布式计算以及富于建设性贪婪启发式搜索[426].
在运用蚁群算法时,首先将公交路线规划区内的所有n条路段从1到n编号,每一条路段的初始信息量都是相等的.设τx=C(x=1,2,…,n),C是一个常数.寻优过程中,其信息量τx会随着蚁群经过后所留下的外激素量的变化而变化.
在运动过程中,蚂蚁k在路口根据路线x上信息量的转换概率决定选择哪一条路线,转换概率P k x(t)表述为
P k x(t)=
τα
x
(t)ηβx
∑
l∈A
τα
x
(t)ηβx
(2)
式中:A为蚂蚁在路口能够选择路段的集合,不包括已经过的路段;α,β为蚂蚁在运动过程中所积累的信息及启发因子在蚂蚁选择路段时所起的不同作用;η为选择路段i的期望程度,如路段交通太拥挤,希望能避开,那η的数值就可以取路段流量的倒数.
在蚂蚁k到达终点以后,所有路段的信息量都需要更新
τ
x
(k)=ρτx(k-1)+Δτx(k-1,k)
x=1,2,…,n
(3)式中:ρ为设定的一个系数,指路段上的信息量会随着时间的增加而减少;1-ρ为信息量的蒸发系数;
Δτ
x
(k-1,k)为在蚂蚁k到达终点以后路段i上信息量的改变量,表达式为
Δτ
x
(k-1,k)=
F(k)
Q
若蚂蚁k经过x
0若蚂蚁k未经过x
(4)式中:Q为一常数;F(k)为蚂蚁k所得规划方案的目标函数值,可由式(1)计算而得.
基于蚁群算法的公交路线走向优化计算步骤如下:
1)指定起讫点,计算循环次数为N max,N=0;
2)设所有路段的初始信息量τx(0)=C x= 1,2,…,n,共有m只蚂蚁,F=0,k=1;
3)N=N+1,若N>N max,退出计算;
4)蚂蚁k从起点出发,根据可选路线x上信息量的转换概率P k x(t)决定选择哪一条路线,一直到到达终点,若还没有达到终点就没有可选路线,说明寻路失败,重复步骤4;
5)到达终点,计算S ij,D ij,k ij,若k ij>k′,则重复步骤4;
6)k ij≤k′,计算F(k),由式(3)、式(4)重新计算所有路段的信息量τx(k) x=1,2,…,n,若F(k)≥F,则F=F(k),画出蚂蚁k所经过的路线;
7)k=k+1,若k=m+1,则重复步骤2,反之,
042 江南大学学报(自然科学版) 第6卷
则重复步骤4.
3 仿真结果
利用文献[1]例子,图1为某区域的交通分区及交通网络,该区域的乘客OD 量见表1.
蚁群算法参数设置为:C =018,α=1,β=1,ρ=018,η=1,Q =10000,m =50,N max =50,反复计算表明优化结果对初值并不敏感
.
图1 某区域的交通分区及交通网络
Fig.1 R egion traff ic netw ork
表1 公交乘客OD 量表
T ab.1 P assengers OD table
O D
A
B
C
D
E
F
G
H
I
J
K
L
A 0347501763347201439112311422359
B 3570491801377108516739802877
C 5115010691401111627362963341
D 75879970107012311281417212139103
E 3503814716840111384762584180
F 2021081232411280413216813458
G 41505213403902813162160
H 1087067150413627014182830
I 38406161581814150212829
J 15070101128787915192002941
K 28
302342394120282528021
L
51
80
39
113
29
50
51
25
27
39
24
现以A 为起点,C 为终点,求解.当非直线系数
限制k ′取不同值时,所对应不同的最优路线.仿真结果如图2所示.
(a )k ′=114
(b )k ′=116
(c )k ′=117
图2 仿真结果
Fig.2 Simulation result
1)图2(a )中,当k ′=114时,F max =3982195,输出道路是A a FD KL C.
2)图2(b )中,当k ′=116时,F max =410115,
输出道路是A a Eb FD KL C.
3)图2(c )中,当k ′=117时,F max =4216190,
输出道路是A GEb FD KL C.
仿真结果显示,当非直线系数限制k ′=114,此时的最佳路线就是最短路线;而当非直线系数限制
k ′=116或k ′=117时,程序所得起讫点之间路线
1
42 第2期金孟合等:基于蚁群算法的公交路线走向模型及其求解
的优化目标函数值都要大于最短路线的优化目标函数值.
上述计算结果表明:在k ′=114时,最短路线就不是最优路线,这时使用最短路法则所确定的路线不符合优化目标.
4 结 语
为解决公交网络设计中的如何确定起讫点配
对问题,文中提出动态直达人数的概念,据此概念
建立了一个确定公交路线走向的模型,应用蚁群算法给出了求解路线走向的具体步骤,并进行了算例的仿真.
运用文中的模型可以很容易地求解任意两点配对所能够得到的最大直达人数,为优化配对提供数据;如与OD 流量分配算法相结合,还可以依次生成多条优化的公交路线,进而形成更趋合理的公交路网.
参考文献:
[1]王炜.数学规划方法在公交网络优化中的应用[J ].系统工程,1990,8(3):44251.
WAN G Wei.Application of mathematical programming method in optimization of public traffic network[J ].Systems En 2
gineering ,1990,8(3):44251(in Chinese ).
[2]王炜.一种简便实用的公交网络优化方法[J ].交通与计算机,1990(3):40247.
WAN G Wei.A simple optimal method in public transportation network[J ].Computer and Communications ,1990(3):402
47(in Chinese ).
[3]杨超,李彬.城市公共交通线网优化的图论模型与算法[J ].同济大学学报:自然科学版,1998,26(3):2942298.
YAN G Chao ,L I Bin.Graph theory model and algorithm of urban public transport network ’s optimization [J ].Journal of
Tongji University :Natural Science ,1998,26(3):2942298(in Chinese ).
[4]Dorigo M ,Manifzzo V ,Colorni A.The ant system :optimization by a clony of coperating aents[J ].IEEE Translation on
Systems ,Man and Cybernetics Part B :Cybernetics ,1996,26(1):29241.
[5]刘闯,韩印,江丽炜.智能化城市公共交通网络优化和设计模型研究[J ].佳木斯大学学报:自然科学板,2003,21(3):2472
251.
L IU Chuang ,HAN Y in ,J IAN G Li 2wei.Study on the optimization and design about intelligent public transport network[J ].
Journal of Jiamusi University :Natural Science Edition ,2003,21(3):2472251(in Chinese ).[6]张纪会,徐心和.一种新的进化算法———蚁群算法[J ].系统工程理论与实践,1999(3):84287.
ZHAN G Ji 2hui ,XU Xin 2he.A new evolutionary algorithm ant colony algorithm[J ].Systems Engineering 2Theory &Prac 2
tice ,1999(3):84287(in Chinese ).
(责任编辑:邢宝妹)
2
42 江南大学学报(自然科学版) 第6卷
1、公交线网优化
1、公交线网优化 公交优先项目提出了成都市中心城区公交线网优化方案、骨干线网优化方案，同时对天府新区公交线网进行优化和规划。 成都市常规公交目前已初步形成“环形+放射状”的“快、干、支、微”四级线网体系。 城市公交骨架线路是在公交网络体系中起支架作用的线路，它衔接区域内公交客流需求较大的枢纽点，主要满足直达客流的需要，以实现乘客快速、便捷的转移。公交骨架线路效率的高低直接影响整个网络运行效率。 成都市公交线网概念骨架图 按照城市任何两个公交服务区之间均应提供快速公交服务的理念，构筑抽象的理想快线网络。通过网络拟合，筛选可行网络，考虑对策略发展区快线支持，补充得到近期快线实施网络。以实施网络为基础，对现有线网进行改造，得到近期快线方案，如下图。
成都市近期公交快线网络规划图 线网优化实例图 随着2014年四川天府新区正式成立，天府新区成都直管区与中心城区形成双核发展；成都市第十三次党代会报告提出：“推动天府新区产城融合，突出国际化服务和创新型引领，突出天府国际空港新城的国际门户功能和龙泉山现代化
产业基地的集聚优势，把天府新区打造成为新兴增长极核。”因此，将天府新区成都直管区与中心城区的快捷连通作为公交快线布设的重要因素，同时兼顾天府新区内部各核心组团（天府新城、成都科学城、南部特色优势产业功能区）的连通性，规划布局多条公交干线。 天府新区新增/调整快线布局
天府新区公交干线布局 2、交通集成模型数据库 交通模型数据库项目的开展形成了多个预测模型和各项交通指标数据库，使得成都在机动化快速发展中的交通模式向智慧出行、绿色出行和可持续发展方向转变。 数据库建设一览表
蚁群算法的数学模型
蚁群算法的数学模型 蚂蚁),2,1(k m k ???=在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用),,2,1(t m k abu k ???=来记录第 k 只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。 设 m 表示蚂蚁总数量，用)1,,1,0,(d -???=n j i ij 表示节点 i 和节点 j 之间的距离，)(ij t τ表示在 t 时刻ij 连线上的信息素浓度。 在初始时刻，m 只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在 t 时刻，蚂蚁 k 从节点i 转移到节点 j 的状态转移概率为 ??? ????=∈=∑∈other p allowed t t t t k ij k allowed k ij ij ij ij k ij ,0j ,) ()()()(p k βαβαητητ ()1-2 其中，{}k k tabu c allowed -=表示蚂蚁 k 下一步可以选择的所有节 点，C 为全部节点集合；α为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；β可称为期望启发式因子，在算法中代表能见度的相对重要性。ij η是启发函数，在算法中表示由节点i 转移到节点 j 的期望程度，通常可取ij ij d /1=η。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。 在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发
一种自适应蚁群算法及其仿真研究
一种自适应蚁群算法及其仿真研究 作者：王颖， 谢剑英 作者单位：上海交通大学自动化研究所,上海,200030 刊名： 系统仿真学报 英文刊名：JOURNAL OF SYSTEM SIMULATION 年，卷(期)：2002,14(1) 被引用次数：191次 参考文献(3条) 1.Dorigo M;Maniezzo Vittorio;Colorni Alberto The Ant System: Optimization by a colony of cooperating agents 1996(01) 2.Dorigo M;Gambardella L M Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[外文期刊] 1997(01) 3.Schoonderwoerd R;Holland O;Bruten J;Rothkrantz L Ant-based Load Balancing in Telecommunications Networks 1997(02) 本文读者也读过(2条) 1.陈崚.沈洁.秦玲.陈宏建基于分布均匀度的自适应蚁群算法[期刊论文]-软件学报2003,14(8) 2.张纪会.高齐圣.徐心和.ZHANG Jihui.GAO Qisheng.XU Xinhe自适应蚁群算法[期刊论文]-控制理论与应用2000,17(1) 引证文献(194条) 1.颜晨阳前馈神经网络连续二元蚁群训练模型[期刊论文]-软件导刊 2011(6) 2.马军.王岩改进的蚁群算法求解旅行Agent问题[期刊论文]-计算机工程与应用 2010(11) 3.楼小明一种改进的自适应蚁群算法求解TSP问题[期刊论文]-黑龙江科技信息 2009(24) 4.闵亨峰供应链节点间配送线路规划蚁群算法[期刊论文]-天津科技大学学报 2006(3) 5.卢正鼎.刘会明基于蚁群算法的理性自适应路由研究[期刊论文]-计算机工程与科学 2006(12) 6.方崇.黄伟军南宁市内河水质的投影寻踪回归分析[期刊论文]-人民长江 2010(8) 7.唐连生.程文明.梁剑.张则强基于行程时间可靠性的车辆路径问题研究[期刊论文]-统计与决策 2008(10) 8.刘学辉P2P网络架构下蚁群算法的应用研究[期刊论文]-无线电通信技术 2007(3) 9.许鹏动态车间调度算法[期刊论文]-航空制造技术 2007(z1) 10.李卓君改进的蚁群算法在VRP中的应用研究[期刊论文]-武汉商业服务学院学报 2006(1) 11.李少辉.刘弘.王静莲蚁群算法在P2P网络架构下的Web服务中的应用[期刊论文]-计算机工程与应用 2006(20) 12.梁栋.霍红卫自适应蚁群算法在序列比对中的应用[期刊论文]-计算机仿真 2005(1) 13.许志红.张培铭基于蚁群算法的智能交流接触器优化设计[期刊论文]-电工电能新技术 2005(3) 14.刘鹏.姜伟.刘新妹.殷俊龄基于蚂蚁算法的PCB板路径优化研究[期刊论文]-电子世界 2012(2) 15.徐滨.张亦改进的蚂蚁算法车辆运行调度算法研究[期刊论文]-计算机仿真 2011(10) 16.陆克芬.方崇.张春乐基于人工鱼群算法的投影寻踪评价方法研究[期刊论文]-安徽农业科学 2009(23) 17.付永强.王启志一种快速收敛的蚁群算法[期刊论文]-福建电脑 2009(9) 18.方崇.李慧颋PMA-PP分析模型在内河水质科学评价中的应用[期刊论文]-地球与环境 2009(4) 19.马洪伟.赵志刚.吕慧显.李京基于蚁群聚类和裁剪方法的RBF神经网络优化算法[期刊论文]-青岛大学学报（工
城市公交线网优化的非线性模型_姚本伦
《交通标准化》２００６年第１０期 ＣＯＭＭＵＮＩＣＡＴＩＯＮＳＳＴＡＮＤＡＲＤＩＺＡＴＩＯＮ．Ｎｏ．１０，２００６ 报告认为该段路堑处于古滑坡前缘，最大开挖坡高为１３ｍ左右。根据勘探地质资料，路堑开挖后可能诱发古滑坡复活，故在滑体中部设１４根抗滑桩。由于对该路段土性的误判，即将残坡积层下伏厚层河流阶地沉积物判为上部滑坡堆积物，滑动面为基岩面，人为增加了滑体厚度及滑坡规模。当施工第一根抗滑桩挖到设计标高处时，设计人员到现场验槽，发现下部挖桩废渣为卵石土，主要成分为砂岩、花岗岩、 石英岩等，成分杂乱，砂质充填，不是残坡积成因堆积物；但二级坡开挖面仍为残坡积物，为谨慎起见，施工方暂停抗滑桩施工，局部开挖一级坡断面，开挖后发现下部卵石层为河流堆积物，卵石排列韵律明显，且无变形迹象。根据揭露地层情况，滑坡残坡积堆积物厚度薄，上部山体基岩出露，后缘残留物较少，重新分析路堑开挖后稳定性，认为不可能复活，因而取消原抗滑桩措施及有关附属工程措施，只 进行一般边坡防护，为工程建设挽回直接经济损失２００多万元。 ４结语 ４．１公路工程设计是一系统性 工程，边坡工程是公路工程中重要的组成部分，同时受建设区域自然地质环境、路线设计、施工等多因素的影响，不确定因素较多，需认真分析研究。 ４．２山区公路工程病害的发生， 主要受坡体地质条件（时代成因、物力力学性质等）控制，而人工切坡、降水等外在条件为诱发因 城市公交线网优化的 非线性模型 姚本伦１，张卫华２ （１．合肥城市规划设计研究院，安徽合肥２３０００１；２．合肥工业大学交通研究所，安徽合肥２３０００９） 摘要：通过对城市公交线网优化的整体研究，给出其优化的主要内容、优化原则以及线网优化的主要因素，提出公交线 网优化的约束条件和三大优化目标，并给出相应的数学表达式使约束条件和优化目标定量化，同时建立公交线网整体优化的模式，并对其进行讨论和评价，有助于提高城市公交线网的优化效率，同时可使约束条件和优化目标定量化。 关键词：公共交通；线网优化；整体模式；中图分类号：Ｕ２２ 文献标识码：Ａ 文章编号：１００２－４７８６（２００６）１０－００９４－０４ ＡＮｏｎ－ｌｉｎｅＯｐｔｉｍｕｍＭｏｄｅｌｏｆＵｒｂａｎＰｕｂｌｉｃＴｒａｆｆｉｃＮｅｔｗｏｒｋ ＹＡＯＢｅｎ－ｌｕｎ１，ＺＨＡＮＧＷｅｉ－ｈｕａ２ （１．ＨｅｆｅｉＵｒｂａｎＰｌａｎｎｉｎｇ＆ＤｅｓｉｇｎＩｎｓｔｉｔｕｔｅ，Ｈｅｆｅｉ２３００１，Ｃｈｉｎａ；２．ＴｒａｆｆｉｃＩｎｓｔｉｔｕｔｅ，ＨｅｆｅｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ， Ｈｅｆｅｉ２３０００９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂａｓｅｄｏｎｔｈｅｓｔｕｄｙｏｆｕｒｂａｎｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎａｎｄｔｈｅｄｉｓｃｕｓｓｉｏｎｏｎｔｈｅ ｃｏｎｔｅｎｔ，ｐｒｉｎｃｉｐｌｅａｎｄｍａｉｎｆａｃｔｏｒｓｆｏｒｏｐｔｉｍｉｚａｔｉｏｎｗｉｔｈｒｅｌａｔｉｖｅｍａｔｈｅｍａｔｉｃａｌｅｘｐｒｅｓｓｉｏｎｓｆｏｒｄｉｓｔｉｎｃｔｏｐｔｉ－ｍｕｍｏｂｊｅｃｔｓｆｕｎｃｔｉｏｎｆｏｒｍａｎｄｒｅｓｔｒｉｃｔｃｏｎｄｉｔｉｏｎｓ，ａｖａｒｉｅｄｏｂｊｅｃｔｉｖｅｓａｎｄｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｏｆｐｕｂｌｉｃｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎｃａｎｂｅｂｕｉｌｔ．Ｉｔｉｓｈｅｌｐｆｕｌｆｏｒｉｍｐｒｏｖｉｎｇｔｈｅｏｐｔｉｍｉｚｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｕｒｂａｎｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋ． Ｋｅｙｗｏｒｄｓ：ｐｕｂｌｉｃｔｒａｆｆｉｃ；ｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎ；ｉｎｔｅｇｅｒｍｏｄｅｌ""""""""""""""""""""""""""""""""""""""""""""" ９４
云模型在机器人路径规划算法中的研究
工程技术 Project technique 云模型在机器人路径规划算法中的研究 马文辉 崔 莹 (齐齐哈尔医学院现代教育技术中心 161000 中国一重技师学院黑龙江省齐齐哈尔市 161000) 【摘 要】传统的遗传算法由于在进化过程中易出现早熟收敛、不能保证种群多样性的现象。本文提出了一种基于云模型的简单、有效的移动机器人避障路径规划算法,采用一维云算子进化变异,同时进化式变异和突变均利用了历史搜索结果,有效避免遗传算法的缺点。模拟数据也证明了该算法的可行性。 【关键词】云模型;进化算法;路径规划;机器人 1 引 言 机器人规划是在已有环境下绕过障碍物找到一个可行的或最优路径从源位置到目标位置,这个问题已得到广泛的研究,各种智能算法不断涌现,这些方法应用于路径规划会使移动机器人在动态环境中更灵活,更具智能化。如人工势场,随机路标规划,基于传感器的方法等。它们都有其优点和缺点。基于遗传算法的机器人路径规划是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。由于其思想简单、易于实现以及表现出来的健壮性,但是因为遗传算法本身的缺陷(早熟、局部能力搜索差),还不能保证计算机效率和路径的可靠性,因此还存在很大的改进发展空间。云模型是对模糊理论隶属函数概念的创新与发展,已成功应用于智能控制、大系统评估、网络安全等。 2 云模型改进机器人路径规划方法 云模型所表达的概念的整体特性可以用期望Ex(Expected value),熵En(Entropy),超熵He(Hyper entropy)这3个数字特征来整体表征。Ex是云滴在论域空间分布的期望,是最能够代表定性概念的点,或者说是这个概念量化的最典型样本。En代表定性概念的可度量粒度,反映了能够代表这个定性概念的云滴的离散程度,亦是在论域空间可被概念接受的云滴的取值范围。He是熵的不确定性度量,即熵的熵,由熵的随机性和模糊性共同决定。用3个数字特征表示的定性概念的整体特征记做C(Ex,En,He)。 基于云模型的优良特性,结合遗传算法的基本原理,本文使用一种自适应、高精度、快速随机搜索机器人路径规划的算法,该算法不但比传统遗传算法精度高,而且能够很好地避免遗传算法易陷入局部最优解和选择压力过大造成的早熟收敛等问题。本文中Ex代表父代个体的优良特征即代表父代路径;En和He表示继承过程的不确定性和模糊性即可被接受的路径范围,利用正态云算子完成概念空间到数值空间的转换,产生种群下一代路径,实现遗传操作。在遗传算法中,当种群的多数个体适应值相差不大时交叉操作就显得无能为力,算法陷入局部解而不能由交换解决,突然变异能够使之摆脱局部收敛而跃出局部解,但是后期的变异可能破坏已产生最优解模块。基于云模型的改进算法可以有效避免遗传算法的这个缺点,因为进化式变异和突变均利用了历史搜索结果。 3 实验方法 3.1 实验的初始设置。P(Eχ,En,He),Eχ=20,En=0.618, He=0.05,k=10,λlocal=3,λglobal=9。 3.2 将优秀路径带入公式(1)产生下一代 Θ[j]=1/(sqrt(2×pi)×sqrt(He))×pow(e,-(j-En)^2/(2×En)) (2) X[j]=(sqrt(2×pi)×sqrt(Θ[j]))×pow(e,-(j-qath[i] [j]))×(j-qath[i][j])/(qath[i][j])(3) path[i][j]=pow(e,-(X[j])-quani[j])×(X[j]-qath[i] [j])/(2×Θ[j])(4) 其中:i∈优秀路径群,j∈路径基因 3.3 计算适应函数fit()。ppercent[i]为第i条路径长度, qpercent[i]为第i条路径惩罚算子 fit[i]=1/appercent[i]+βqpercent[i](5) 其中:α为路径长度因子,β惩罚因子。 3.4 进化过程。进化过程中,若出现跨代精英,En和He减小 为原来的1/k(k为大于1的实数)。当若干进化代没有发现新的跨代精英,即连续平凡代数达到一定的阈值λlocal时,路径可能陷入了一个局部最优邻域,此时需要跳出这个小局部,并在该局部附近尝试寻找新的局部最优,方法是提高En和He为原来的k倍。 3.5 变异过程。当经过若干代进化没有得到适应性更加优 异的路径,而且进化式变异没有效果时,路径可能陷入局部,需要进行一次突变操作。进行局部求变和突变的连续平凡代数阈值之间的关系为λglobal>λlocal。突变方法为取历史跨代精英个体的平均值,熵为相应历史精英个体的方差。 在本算法中进化和变异是统一的,进化式变异是进化和变异融合,可以用来进行局部求精或跳出小局部,而突变则用来在全局范围内寻找新的极值搜索区域.算法可以判断出当前的进化状况,进而可以自适应地进行调整 。 图1 初始最优路径状态 图2 第12代精英路径状态4 结 论 本文采用云模型理论改遗传算法在机器人路径中的应用,不需要繁琐的交叉、变异,具有良好的可操作性。模拟数据验证了这种方法对全局优化性能改善的可行性,可以使该算法优化速度获得一定程度的提高,有效地克服了基本遗传算法收敛速度慢、易限于局部最优解的缺陷。 【参考文献】 [1]Rosell,J.,Iniguez,P.:Pat h planning using Harmonic Functions and Probabilistic Cell Decomposition.Proc.of t he IEEE Int.Conf.on Robotics and Automation(2005):1803-1808. [2]Kazemi,M.,Mehrandezh,M.:RoboticNavigationUsing Harmon2 icFunction-basedProbabilisticRoadmaps.Proc.of t he IEEE Int. Conf.on Robotics and Automation(2004):4765-4770. [3]李德毅,杜益.不确定性人工智能[M].北京:国防工业出版社,2005. [4]戴朝华,朱云芳,陈维荣,林建辉.云遗传算法及其应用[J].电子学 报,2007-7. [5]段海滨,王道波等.基于云模型理论的蚁群算法改进研究[J].哈尔 滨工业大学学报,2005-1. [6]周明,孙树栋.遗传算法原理及应用[J].北京:国防工业出版社,2002-5. [7]陈国良.遗传算法及其应用[M].北京:人民邮电出版社,2001. — 1 2 1 —
云模型简介及个人理解maab程序
随着不确定性研究的深入，越来越多的科学家相信，不确定性是这个世界的魅力所在，只有不确定性本身才是确定的。在众多的不确定性中，随机性和模糊性是最基本的。针对概率论和模糊数学在处理不确定性方面的不足，1995年我国工程院院士李德毅教授在概率论和模糊数学的基础上提出了云的概念，并研究了模糊性和随机性及两者之间的关联性。自李德毅院士等人提出云模型至今，云模型已成功的应用到自然语言处理、数据挖掘、 设是一个普通集合。 , 称为论域。关于论域中的模糊集合，是指对于任意元素都存在一个有稳定倾向的随机 数，叫做对的隶属度。如果论域中的元素是简单有序的，则可以看作是基础变量，隶属度在上的分布叫做隶属云；如果论域中的元素不是简单有序的，而根据某个法则，可将映射到另一个有序的论域上，中的一个且只有一个和对应，则为基础变量，隶属度在上的分布叫做隶属云[1] 。 数字特征 云模型表示自然语言中的基元——语言值，用云的数字特征——期望Ex，熵En和超熵He表示语言值的数学性质[3] 。
期望 Ex：云滴在论域空间分布的期望，是最能够代表定性概念的点，是这个概念量化的最典型样本。 熵 En：“熵”这一概念最初是作为描述热力学的一个状态参量，此后又被引入统计物理学、信息论、复杂系统等，用以度量不确定的程度。在云模型中，熵代表定性概念的可度量粒度，熵越大，通常概念越宏观，也是定性概念不确定性的度量，由概念的随机性和模糊性共同决定。一方面, En是定性概念随机性的度量，反映了能够代表这个定性概念的云滴的离散程度；另一方面，又是定性概念亦此亦彼性的度量，反映了在论域空间可被概念接受的云滴的取值范围。用同一个数字特征来反映随机性和模糊性，也必然反映他们之间的关联性。 超熵 He：熵的不确定性度量，即熵的熵，由熵的随机性和模糊性共同决定。反映了每个数值隶属这个语言值程度的凝聚性，即云滴的凝聚程度。超熵越大，云的离散程度越大，隶属度的随机性也随之增大，云的厚度也越大。 1.绘制云图 Ex=18 En=2
蚁群算法
蚁群算法报告及代码 一、狼群算法 狼群算法是基于狼群群体智能,模拟狼群捕食行为及其猎物分配方式,抽象出游走、召唤、围攻3种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制,提出一种新的群体智能算法。 算法采用基于人工狼主体的自下而上的设计方法和基 于职责分工的协作式搜索路径结构。如图1所示,通过狼群个体对猎物气味、环境信息的探知、人工狼相互间信息的共享和交互以及人工狼基于自身职责的个体行为决策最终实现了狼群捕猎的全过程。 二、布谷鸟算法 布谷鸟算法 布谷鸟搜索算法,也叫杜鹃搜索,是一种新兴启发算法CS 算法，通过模拟某些种属布谷鸟的寄生育雏来有效地求解最优化问题的算法.同时，CS 也采用相关的Levy 飞行搜索机制 蚁群算法介绍及其源代码。 具有的优点：全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强，以及很好的通用性、鲁棒性。 应用领域：项目调度、工程优化问题、求解置换流水车间调度和计算智能 三、差分算法 差分算法主要用于求解连续变量的全局优化问题，其主要工作步骤与其他进化算法基本一致，主要包括变异、交叉、选择三种操作。 算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体
的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近。 四、免疫算法 免疫算法是一种具有生成+检测的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。 五、人工蜂群算法 人工蜂群算法是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。为了解决多变量函数优化问题，科学家提出了人工蜂群算法ABC模型。 六、万有引力算法 万有引力算法是一种基于万有引力定律和牛顿第二定律的种群优化算法。该算法通过种群的粒子位置移动来寻找最优解，即随着算法的循环，粒子靠它们之间的万有引力在搜索空间内不断运动，当粒子移动到最优位置时，最优解便找到了。 GSA即引力搜索算法，是一种优化算法的基础上的重力和质量相互作用的算法。GSA 的机制是基于宇宙万有引力定律中两个质量的相互作用。 七、萤火虫算法 萤火虫算法源于模拟自然界萤火虫在晚上的群聚活动的自然现象而提出的，在萤火虫的群聚活动中，每只萤火虫通过散发荧光素与同伴进行寻觅食物以及求偶等信息交流。一般来说，荧光素越亮的萤火虫其号召力也就越强，最终会出现很多萤火虫聚集在一些荧光素较亮的萤火虫周围。人工萤火虫算法就是根据这种现象而提出的一种新型的仿生群智能优化算法。在人工萤火虫群优化算法中，每只萤火虫被视为解空间的一个解，萤火虫种群作为初始解随机的分布在搜索空间中，然后根据自然界萤火虫的移动方式进行解空间中每只萤火虫的移动。通过每一代的移动，最终使的萤火虫聚集到较好的萤火虫周围，也即是找到多个极值
第三章 云模型简介
第三章云模型简介 在人类认知以及进行决策过程中，语言文字是一种强有力的思维工具，它是人类智能和其他生物智能的根本区别。人脑进行思维不是纯粹地应用数学知识，而是靠自然语言特别是客观事物在人脑中的反映而形成的概念。以概念为基础的语言、理论、模型是人类描述和理解世界的方法。 自然语言中，常常通过语言值，也就是词来表示概念。而语言值、词或概念与数学和物理的符号的最大区别就是其中包含太多的不确定性。在人工智能领域，不确定性的研究方法有很多，主要有概率理论，模糊理论，证据理论和粗糙集理论；对于确定性系统的不确定性的研究还有混沌和分形的方法。这些方法从不同的视角研究了不确定性，优点是：有切入点明确、边界条件约束清楚、能够对问题进行深入研究等，但是在研究中常常将不确定性分成模糊性和随机性分开进行研究，然而两者之间有很强的关联性，往往不能完全的分开。随机性是指有明确定义但是不一定出现的事件中所包含的不确定性。例如在投掷硬币试验中，硬币落地时要么有国徽的一面向上，要么标有分值的一面向上，结果是明确的可以预知的，但是每次试验结果是随机的。概率论和数理统计是研究和揭示这种随机现象的一门学科，至今已有几百年的研究历史．模糊性是另一种不确定性，是已经出现的但是很难精确定义的事件中所包含的不确定性。在日常工作和生活中存在着许多模糊概念，如“胖子”“年轻人”“收入较高”等。为处理这些模糊概念，引入了模糊集的概念[41]，使用隶属度来刻画模糊事物彼此间的程度。隶属度函数常用的确定方法有模糊统计法、例证法专家经验法等，这些方法确定隶属度函数的过程是确定的,本质上说是客观的,但每个人对于同一个模糊概念的认识理解存在差异,因此有很强的主观性，而且一旦隶属度函数确定之后，得到的概念、定理等包含着严密的数学思维，其不具有任何模糊性。 针对上述问题李德毅院士在传统的概率统计理论和模糊理论的基础上提出了定性定量不确定性转换模型——云模型，实现定性概念和定量值之间的不确定性转换。在此工作上，一些学者对云模型做了深入系统的研究，使其日趋成熟，并将它成功地应用于不确定性推理、关联规则挖掘，空间数据的挖掘，智能控制及时间序列预测等领域。 云模型能模拟人类思维灵活划分属性空间，在较高的概念层上泛化属性值，完成定量数值到定性概念间的转换，同时允许相邻属性值或语言之间有重叠，这种划分使发现的知识具有稳健性。而由于计算机系统的行为存在随机性和不确定性，云模型能够很好地处理具有随机性和不确定性的数据，所以可将云模型引入到入侵检测中来，通过云模型建立的入侵检测系统具有较准确的检测能力和适应能力。
matlab蚁群算法精讲及仿真图
蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信
息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见,
公交线路选择的优化模型
龙源期刊网 https://www.wendangku.net/doc/4f4866769.html, 公交线路选择的优化模型 作者：张俊丽 来源：《价值工程》2015年第28期 摘要：本文针对城市公交线路选择问题建立了相应的数学模型。将公共自行车看作独立于公汽、地铁的第三种交通方式。利用网络图，主要从换乘次数、出行花费和出行总时间三个方面来确定最佳线路，分别考虑了各单目标，增加不同的上限约束，建立了任意两站点的最佳线路相应的网络流模型。 Abstract： In this paper， the corresponding mathematical model is established for the problem of urban public transportation route selection. The public bicycle as independent of the bus， the subway third modes of transport. Using the network diagram， three main factors are considered to find the best route， the number of trips， travel expenses and travel time.The network flow model of the best optimal line between any two sites， which considers the single objective and the different upper bound constraints. 关键词：公交系统；最佳线路；最小费用流；优先因子 Key words： bus system；best line；minimum cost flow；priority factor 中图分类号：U491.1+7 文献标识码：A 文章编号：1006-4311（2015）28-0206-02 0 引言 城市公共交通网络是城市交通网络的重要组成部分，提高城市交通系统的利用率被公认为是改善交通拥堵的有效途径之一。而如何优化城市现有公交网络以提高城市公交系统的利用率，是当今倍受关注的一个重要课题。公交汽车和城市轨道交通在城市公共交通体系中发挥着大动脉的作用，但是由于线路和站点布局的限制，是无法覆盖城市每一个角落的。即在公共交通体系的末端，缺少一套针对每个乘客特定的短途出行需求的公共交通微循环系统。为了解决这一问题，一种能够实现城市公共交通微循环的公共自行车租赁系统被引入我国。西安市区也常规地在轨道交通站点、公交站点、社区门口设置租赁点，通过“公共自行车管理系统”来管理这些租赁点的自行车。对租赁站点的发展规模预测、追加投资额的分配问题进行探讨，对政府建设城市公共自行车租赁系统具有一定的指导意义。但是在如何将公共交通中地铁、公共汽车、公共自行车租赁有效结合一直是个空白。 本文给出了城市中任意两站点最佳线路方案。本文认为所谓最佳线路，应该从乘车费用、公共自行车骑行时间、换乘次数、出行时间四个方面来理解。对于任意两站点的最佳线路，建立了网络流模型。 1 模型准备：构造容量费用网络图N=（V，E，C，B）
云模型
云模型 云模型（Cloud model）是我国学者李德毅教授提出的定性和定量转换模型。 随着不确定性研究的深入，越来越多的科学家相信，不确定性是这个世界的魅力所在，只有不确定性本身才是确定的。在众多的不确定性中，随机性和模糊性是最基本的。针对概率论和模糊数学在处理不确定性方面的不足，1995年我国工程院院士李德毅教授在概率论和模糊数学的基础上提出了云的概念，并研究了模糊性和随机性及两者之间的关联性。自李德毅院士等人提出云模型至今短短的十多年，其已成功的应用到数据挖掘、决策分析、智能控制、图像处理等众多领域。 定义在随机数学和模糊数学的基础上,提出用"云模型"来统一刻画语言值中大量存在的随机性、模糊性以及两者之间的关联性,把云模型作为用语言值描述的某个定性概念与其数值表示之间的不确定性转换模型.以云模型表示自然语言中的基元——语言值,用云的数字特征——期望Ex,熵En和超熵He表示语言值的数学性质.“熵”这一概念最初是作为描述热力学的一个状态参量,以后又被引入统计物理学、信息论、复杂系统等,用以度量不确定的程度.在云模型中,熵代表一个定性概念的可度量粒度,熵越大粒度越大,可以用于粒度计算;同时,熵还表示在论域空间可以被定性概念接受的取值范围,即模糊度,是定性概念亦此亦彼性的度量.云模型中的超熵是不确定性状态变化的度量,即熵的熵.云模型既反映代表定性概念值的样本出现的随机性,又反映了隶属程度的不确定性,揭示了模糊性和随机性之间的关联. 相关系数期望Ex是云在论域空间分布的期望,是最能够代表定性概念的点,或者说是这个概念量化的最典型样本;熵En代表定性概念的可度量粒度,熵越大,通常概念越宏观,也是定性概念不确定性的度量,由概念的随机性和模糊性共同决定.一方面, En是定性概念随机性的度量,反映了能够代表这个定性概念的云滴的离散程度;另一方面,又是定性概念亦此亦彼性的度量,反映了在论域空间可被概念接受的云滴的取值范围;超熵He是熵的不确定性度量,即熵的熵,由熵的随机性和模糊性共同决定。 作者简介: 于少伟( 1981 ) , 男, 讲师, 硕士, 研究方向为智能控制技术、金融工程. Emai:lyushaowei0505@ https://www.wendangku.net/doc/4f4866769.html, 基于区间分析和云模型的实物期权定价研究 摘要: 针对实物期权定价中预期现金流收益的现值和投资成本采用精确值给出不太合理的实际情况, 深入分析了现有的基于模糊集理论和基于云模型的实物期权定价方法, 提出了基于区间分析和云模型的实物期权定价方法。首先, 在基于云X 信息的逆向云算法的启发下, 结合区间分析理论, 提出一种新的逆向正态云构建算法; 然后, 用生成的云模型表示预期现金流收益的现值和投资成本, 结合期权定价理论和基于区间数的逆向云算法, 运用云运算, 给出了一种将专家评估区间数据转化成正态云模型的形式, 并提出了利用逆向正态云估计预期现金流收益波动率的实物期权定价方法; 最后, 通过实例模拟证明了该方法的有效性。 关键词: 区间分析; 正态云模型; 实物期权; 预期现金流收益; B-S公式 0 引言近年来, 实物期权广泛应用于项目投资决策分析, 弥补了传统财务分析方法(如资本预算的净现值方法)的不足, 其思想主要体现为: 当市场条件不确定时, 投资者可以选
蚁群算法
蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路
城市公交线路选择优化模型
城市公交线路选择优化模型 摘要 本文针对城市公交线路选择问题建立了两个模型,一个是基于集合寻线算法模型，另一个是图论模型。 基于集合寻线算法模型中,首先固定换乘次数n,通过集合论的相关知识把确定换乘点的具体位置, 转化成确定一些集合间的交集，从而建立集合寻线算法，再根据集合相关公式,得到所有可行线路；进一步考虑时间和费用等因素,对可行线路进行处理比较，得出最佳线路。 图论模型中,通过图论的知识将整个北京市交通线路构建出一个有向图,每个站点与有向图的顶点一一对应，同一线路上的相邻站点对应为有向边，通过不同目标(时间、费用）给有向图进行不同的赋权,分别将不同目标转化为赋权有向图寻找最短有向路,根据最短路径算法，得到最佳线路。最后综合评价了两个模型的优缺点。 关键词:集合寻线算法；最短路算法;换乘点;赋权有向图
1 问题提出 北京将于200８年举行奥运会,届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交,包括公汽、地铁等)出行。随着现代化的步伐加快,城市的公交系统有了很大发展,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。在现实生活中,公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路,所以针对市场需求以及公交线路选择上的问题,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 该系统的核心在于线路选择的模型与算法，应该从实际情况出发,满足查询者的各种不同需求。根据附录１、附录2，解决如下问题: １.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法,求出以下6对起始站→终到站之间的最佳线路。 (1) S3359→Ｓ182８（２) Ｓ155７→S０481（3）S0９71→Ｓ048５ (4) S00０8→Ｓ０073 (５）S0１48→S04８5 (６）S0０8７→Ｓ 36７６ ２.同时考虑公汽与地铁线路，解决以上问题。 3.假设知道所有站点之间步行时间,给出任意两站点之间线路选择的数学模型。 2 问题分析 为了研制开发一个解决公交线路最佳选择(即乘客在多条公交线路中根据自己的需求获得最适合自己的线路)问题的自主查询计算机系统,只要乘客给出起点站A和终点站B两个站点,系统就给出最佳交通线路，使得公众出行更加通畅、便利。而问题核心是如何在多条线路选择中获得最佳线路。 乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站,但若多次换乘公交，可能导致乘客所花时间及其费用的增加,更会给乘客造成不便。在奥运将在北京举行的背景下,我们知道乘客前往观看奥运比赛时,主要注重的是能否及时到达,所以在为乘客选择线路时,力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化，我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路,再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。 3 模型准备 3.1 模型假设 1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费)； 2.假设所有交通线路都不出现停运或者线路变动； 3.假设公汽的环行行驶线路是单向的。 3.2符号约定 c:相邻公汽站平均行驶时间(包括停站时间)，min c； = 3 d； = d：相邻地铁站平均行驶时间（包括停站时间），min 5.2 e:公汽换乘公汽平均耗时,min e(其中步行时间2min）; 5 = f(其中步行时间2min); = 4 f：地铁换乘地铁平均耗时,min
matlab_蚁群算法_机器人路径优化问题
用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有