蚁群算法在路径优化中的应用
作者：孙阳阳指导老师：刘冲
摘要针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学
形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3
个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很
好的效果.
关键词蚁群算法算法模型算法步骤分析应用
1 引言
路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地点到目标地点最优的路径.蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化系统,计算法采用分布式并行计算和正反馈机制，且易于其它算法结合，目前已有许多关于其在路径规划方面的文献.
建立蚁群算法模型]2][1[，解决城市交通路径优化问题，实验结果表面在搜索效率和搜索最优解的能力两方面都有很大的提高.但是传统蚁群算法易陷入局部最优解和收敛速度较
4[ ，将传统蚁群算法进行改进，例如与栅格法相结合、慢，为此在机器人路径规划的应用中]7
在几何模型下建立模型等.提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解的问题，扩大了蚂蚁的搜索空间，增强了蚁群算法在机器人路径规划中的适应能力.
本文通过对蚁群算法的研究以及解决几实际路径规划问题，得出了蚁群算法是有其可行性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用.
2 蚁群算法
蚁群算法(ant colony optimization),又称蚂蚁算法，简称ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径.
2.1 蚁群算法的基本原理
蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小，这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径.
2.2 蚁群算法的数学模型
2.2.1 问题的描述
求解两地间最优路径，即为求某两地间用时最少的行进路线.如在一个城市中，有A 、B 两个地点，从A 到B 有多条路径线路可选，即求一条从A 到B 用时最少的路线.又比如在当今热门研究项目机器人路径规划问题中，其本质为在规划空间内依据环境信息，在某些评价标准下，找出从出发点到目标点最优的路线，比较有代表的问题是喷涂机器人，即在一个复杂曲面上如何规划喷涂机器人的路径，使其喷涂效率最高.
这些问题都符合蚁群算法的思想，因此可以用蚁群算法来求解.
2.2.2 模型的建立
首先将蚂蚁觅食与路径优化问题进行对照如表1所示
表1 蚂蚁觅食和路径优化对照表
蚂蚁觅食
路径优化问题 蚂蚁要遍历的各个路径
各个状态 整个蚁群经过的一条完整的路径
解 最短路径
最优解 信息素的浓度
各状态的吸引度 信息素的更新
状态更新 路径的长度 目标函数
以旅行商问题（TSP ）为例来构建模型，定义路与路段的交叉口为节点，路段为边.即TSP 问题可描述为给定n 个节点和每两个节点之间的距离，要寻找到一条路径，从某个节点出发周游到其它节点一次且仅一次，最终回到出发节点的封闭环路径长度最短.设节点数为n ，蚂蚁的数目为m ，蚂蚁从一个节点到另一个节点逐步完成搜索的过程.蚂蚁k (k =1,2,3...m )，根据概率转换的规则选择下一个节点.由此可以生成一个由n 个节点组成的行动路线，并伴有信息素的不断更新.()i b t 表示位于t 时刻节点i 的蚂蚁数目.则有：
12()()...();n m b t b t b t =+++(,1,2,3....,)ij d i j n =
d 表示两个节点 i 和 j 之间的距离
在基本蚁群算法模型中，人工智能蚂蚁有以下特点：
(1) 人工智能蚂蚁具有记忆功能.每一个蚂蚁k (k =1,2,3,....m )都有一个禁忌表(k tube )，即蚂蚁经过节点i(i n ∈)后，不能再经过节点i .
(2) 两个节点的距离越近，能见度则越大，被选择的期望也就越高，由此来指引人工智能蚂蚁的搜索.定义1ij ij
d η=
，被称为期望因子，所以蚂蚁k 在t 时刻从节点i 转移到节点j 的概率可表示为： [][]
()
()(),()()()()0,()k ij ij k k is is ij s J i k t t j J i t t p t j J i αβ
αβτητη∈??????????∈?=?????
∑ （1）
其中()k tube s 表示禁忌例表中第s 个元素，即蚂蚁所走过的第s 个节点；()k J i 为蚂蚁所允许到达的节点的集合，{}()1,2...,k k J i n tabu =-；
期望因子ij η表示对边,i j 上的期望程度；α表示信息素的相对重要程度；β表示启发式因子的相对重要程度.这里需要重点说明一下：当α取较大值时，蚂蚁在选择路径的过程中路上的信息素非常重要；当α取较小值时蚁群算法变成随机的贪婪算法.β取较大值时会使整个蚁群陷入随机搜索，这样的话收敛速度 较慢，很难找到最优的结果，β取较小值时虽然加快了收敛速度，这样会很快得到一个最优解但是容易陷入局部最优的状况.
(3) 在蚁群算法中有一个非常重要的参数指标，就是信息素浓度.蚁群在节点i 到节点j 时，算法会在路径ij 上遗留信息素，而信息素是时时刻刻动态变化的，它的多少决定蚁群选择该路径的概率大小.下面我们给出信息素浓度公式，设()ij t τ表示t 时刻,i j 上的信息数浓度，则在t +n 时刻此路径上的信息素浓度为
1()(1)()()m k ij ij ij k t n t t τρττ
=+=-+?∑ （2）
式中，(01)ρρ＜＜
它表示信息物质的保留率；()k
ij t τ?表示时刻t 在蚂蚁k 在路径ij 上信息素的增量. ()0k k ij Q L t τ???=???
（3）
式中，Q 表示蚂蚁释放的信息素量；L 表示蚂蚁k 在本次周游遍历中所经过边的总和长度,k L 表示本次遍历中蚂蚁所用的时间总和.
以上4个因素即禁忌列表、期望因子、概率转换规则、信息素浓度蚁群系统路径选择的实现和信息素更新策略，两者互相配合，实现模型的正反馈机制，促进人工智能蚂蚁收敛于最优解.
根据信息素更新策略的不同，又出现了3种不同的模型：蚁量模型、蚁密模型、蚁周模型.
① 蚁量模型
(,1)k ij t t τ?+=4）
在式中，Q 为常量，信息素的增加量与边ij 的长度有关.
② 蚁密模型
(,1)0k ij Q t t τ??+=??，， （5） 蚂蚁k 在时刻t 和t +1经过ij 否则
在式中，Q 为常量，也就是说信息素增加量只是个固定值，与边ij 的距离无关.
③ 蚁周模型
,(,1)0,k k ij Q L t t τ???+=???
（6）
在式中，Q 是常量表示k 只蚂蚁的周游路线，即如果蚂蚁经过边ij 信息素的增加量为一个常量除以蚂蚁k 循环路线长度.这里信息素的增加量只与蚂蚁的循环路线和Q 有关，与ij d 没有关系.在该模型中采用了全局信息的更新，较前两种模型性能更优.原因是蚁周模型利用整体信息，即蚂蚁在历经一个循环路径所释放的信息素量与所得解的质量成正比.周游路径长度越短的蚂蚁，释放在该路径上的信息素量越多，而前两种模型在搜索解时，只使用了局部更新信息，没有用到任何解的信息.
2.2.3 选参原则
讨论的参数包括,,,,m Q αβρ.上文已经提到信息素的相对重要程度α和启发式因子的重要程度β对算法模型的影响，这里主要说下信息素蒸发系数ρ，蚂蚁数目m 以及蚂蚁释放的信息数量Q 对搜索过程的影响.ρ增大，残留信息素1ρ-减少，负反馈机制增强，随机性增强，利与发现更多最优解，但是收敛性降低.反之ρ增大，残留信息素增加，正反馈加强，虽然收敛性加快，但是随机性减弱容易陷入一个范围狭小的搜索圈，所以搜索质量并不高.蚂蚁数m 较小时，会使为走过路径上的信息素减小为0，即搜索的随机性能会降低，虽然加快了收敛性，但是搜索的全局性能降低，算法稳定性差，容易陷入过早的停滞.m 较大时，会使搜索路径上的信息素浓度过于平均，收敛速度变慢.对于蚂蚁释放的信息素量Q 来说是一个常量，Q 越大，路径信息素积累越多，收敛速度越快.显然可见，参数的选择对于搜索的准确性是很重要的，这里选参原则如下：
(1) 确定蚂蚁数目m ,可参照“问题规模数约为蚂蚁数目的1.5倍”;
(2) 参数,αβ的粗调，常用的几种组合有(1,1),(1,2),αβαβ====
(1,5),αβ==(0.5,5)
αβ== (3) 参数ρ细调，ρ通常设定在0.5以下.
2.3 蚁群算法的基本步骤（流程）
这里主要是以蚁周算法为例，总结蚁群算法的基本步骤.
流程框图如下所示：
注: (1) 在流程图中整个算法的迭代过程是以N 为刻度，max 1N N ≤≤（max N 为最大迭代次数）.在迭代过程中以时间t 为刻度(1t n ≤≤),蚂蚁k 根据概率转换公式选择下一个节点.
(2) 禁忌表(tube ):禁忌表是为了避免蚂蚁走进同一个节点的数据结构.设k tube 为蚂蚁k
蚂蚁k 在本次周游中经过边ij 否则
tube中，表示下一的禁忌列表，则蚂蚁k走过节点i后就将该节点加入到自己的禁忌列表
k
tube s表示禁忌列表中第s个元素，即蚂蚁k所走过的第s个节点，次不能再走节点i,用()
k
完成一此周游后，也即遍历n个节点后，清空禁忌列表.
3 蚁群算法在路径规划中的应用
蚁群算法在优化领域的应用是很广泛的，下面我们给出几个例子进行分析，需要说明一下这些结果是基于实际情况和仿真实验的基础上得出的.
3.1 利用计算机仿真实验求两地最短路径
蚁群算法在搜寻最短路径时，对于每一步的扩展，蚂蚁在下个节点的选择上需要遵循以下两个原则：①每次所选的节点n在地图上是可以移动的，②在已访问过的节点中不包括节点n.实验步骤按照上文所给的基本步骤来求解.
本实验是在VC+ +6.0的环境下进行的，实验采用的是美国某州的电子拓扑图，所选参数
N .将20只蚂蚁放置于起始节点，对于按照选参原则，最大循环的次数即迭代次数100
c
所有蚂蚁用式(1)计算出蚂蚁选择路径的转换概率，利用赌轮法选择出满足①②原则的路径，并根据公式(2)(4)对路径上的信息素进行更新.重复这一步骤直到所有蚂蚁搜寻到最短路径时结束或者达到最大的迭代次数，循环结束时输出最短路径和长度.在拓扑图上选择A.B两
点，利用蚁群算法求出两地之间的最短路径，最终得出的结果如图2中粗线所示.因为20只蚂蚁搜寻路径的节点序列表比较大，这里就不在给出.
图2 蚂蚁觅食拓扑图
从计算的序列表格中可以看出20只蚂蚁最终有17只蚂蚁找到了最短路径，另外3只蚂蚁找到的虽然不是最短的路径，但是都接近最短路径，有可能是第(1,2,...)n n =短的路线，对于最优路径的搜寻引导仍具有利用价值.我们还将设计的参数数值做出了如下改变，在前50次循环中取0.5,1,0.7αβρ===，在后50次循环中取参数为1,5,0.9αβρ===.这样做是为了防止最优路径上的信息素在搜寻过程中削弱，实验结果表明有19只蚂蚁找到了最短路径，只有1只没有找到准确的最短路径.这说明了，适当对参数调整可以提高解的质量.
3.2 蚁群算法在城市交通路径选择中的应用
当今的城镇道路布局一般采用的是“棋盘+环线”的形式，在图论中可表示如下：无向图(,)G V E ,V 表示结点集合(即交叉路口)，123(,,...)V V V V =,E 表示所有边的集合.表示该路段特性的数(,)i j d V V 为路段ij 的连接长度即ij d .以消防队员灭火抢险为例，我们都知道在突发事件中以最快的时间到达现场是最重要的，但是往往用时最短的路径并不是最短路径，因为这里要考虑到各条路径的路况状态，都会影响消防车的速度.因此在此优化问题中我们将选取最优时间来代替最短路径，可设(01)ij ij W W ≤＜和(01)ij ij D D ≤＜分别表示在边,i j 上影响消防车速度v 的路况状态参数和交通状态参数.因为1ij ij
t η=
，可用ij t 来衡量ij P ，ij t 表示消防车在边ij 上所消耗的时间.可得出： ij
ij ij ij d t W D v =
式中v 是一个固定值.图3为某市简化的交通路网，一共有13个节点，节点1表示消防车站，节点10和11为两处失火点.给出了连线上的(,,)ij ij ij d W D 的数据，ij d 为实际路径,i j 的长度，ij W 和ij D 是根据实际情况给出的数值.现求从消防站出发到两失火点的最优路径.
单一的蚁群算法显然解决起来比较复杂，因此需要改进蚁群算法(具体改进措施参考文献[8]).
将蚁群算法与TA 算法相结合，利用阈值排序法改进蚁群算法，可以加快算法的收敛性.这里取20,20,13,1,1,80,500c Q m k v N αβ=======.基于改进后的算法，按照算法步骤在奔腾双核5300E 上，以图2为对象，利用java 程序编写改进后的算法程序.
图3 城市简化交通网
阈值排序法得到的k 个边由好到坏的排列： 13,36,1113,126,1013,12,56,210,1112,72,1011→→→→→→→→→→→ 512→
所以可得出：
由1到10的最优路径为1210→→，
循环次数为:135；
由1到11的最优路径为1361211→→→→
循环次数为:186.
分别对改进的蚁群算法和基本蚁群算法各运行50次，结果对比如表2所示，失败表示所得结果并不是最优结果.
表2 改进蚁群算法与基本蚁群算法对比结果
算法
失败 成功率 改进蚁群算法
4 92% 基本蚁群算法 10 80%
表3为蚁群算法改进前后所用迭代次和所得结果的比较.
表3 算法改进前后的比较
算法
路径 平均迭代次数 实际最优路径 改进后的
蚁群算法
110→ 111→ 137 189 1210→→ 1361211→→→→ 基本蚁群
算法 110→ 111→ 323 431 1210→→ 1361211→→→→
可以看出蚁群算法可以应用于应急抢险中，而对其改进算法大大提高了应用中的效率.
3.3 蚁群算法在TSP 问题中的应用
3.3.1 TSP 问题的描述
TSP 问题：一个商人去n 个城市销售货物，所有城市走一遍之后再回到起点，使做走的路径最短.
TSP 问题也可用有向图来表示，即一个N 个城市的有向图(,)G N A =，
其中
()(){}1,2,...,,,|,N n A i j i j N ==∈,
城市之间的距离
()
ij n n d ?
可设目标函数为 ()11l l n
i i i f w d -==∑ 其中()12,,...,n w i i i =为所到城市1,2,...,n 的一个排列，且11n i i +=.
3.3.2 蚁群算法在TSP 问题应用中的原理
利用蚁群算法去解决TSP 问题，假设m 只在图的相邻节点移动，从而相互协作得到问题的解.每只蚂蚁的下一步转移概率由图中每条边上的两类参数来决定的：1 信息素值即信息素蒸发系数ρ,2 能见度即期望因子ij η.
信息素更新方式有两种，一是挥发，也就是所有蚂蚁经过的路径上的信息素以一定的比例进行减少，从而模拟自然环境下蚁群的信息素随时间的变化挥发的过程；二是增强，对于评价值优秀即蚂蚁数量多的路径增加信息素.
对于算法模型的建立在上文中以及给出式(1)至(6)，所以在计算问题过程中要选择合适的式子.
3.3.3 蚁群算法在TSP 问题应用中的算法步骤
初始的蚁群算法是一种基于图的蚁群算法，简称为GBAS 算法，可利用它作为本问题的算法步骤，具体如下：
步骤1：对于TSP 问题，给予每条路径(),i j 赋予信息数初值1(0)ij A
τ=，假设有m 只蚂蚁在工作且所以蚂蚁都从同一个城市0i 出发，当前得到的最优解为()12,,...,n w i i i =.
步骤2：如若满足算法的停止规则，则停止计算并输出算法得到的最优解.否则使蚂蚁k 从起始点0i 出发，用()L k 表示蚂蚁k 所行走过的城市集合，初始()L k 为空集，1k m ≤≤.该步骤是一个外循环.
步骤3：按照蚂蚁1k m ≤≤分别来计算.当蚂蚁在城市i ，
若
()L k N =或者(){}|(,),l i l A l L k φ∈∈=，
完成第k 只蚂蚁的计算.
否则，若
()L k N ≠且()(){}{}0|(,),k J i l i l A l L k i φ=∈?-≠，
则以概率
()()
()
()1,1k ij ij k ij l J i t P j J i t ττ∈-=∈-∑， ()0,ij k P j J i =∈ 到达 j,()(){},:;L k L k j i j ==U
若
()L k N ≠且()(){}{}0|(,),k J i l i l A l L k i φ=∈?-≠
则到达()(){}000,,:;i L k L k i i i ==
重复步骤3.该步骤是一个内循环.
步骤4: 对于1k m ≤≤，若()L k N =，按照()L k 中的城市顺序计算路径程度；若()L k N ≠，可将路径长度设置为一个无穷大值(即蚂蚁不可到达).比较m 只蚂蚁的路径长度，记走最短路径的蚂蚁为c .如果()()()()
f L c f L W ＜，则()W L c =.可用以下公式对W 路径上的信息素浓度进行加强，对其它路径上的信息素痕迹进行挥发. ()()()()()()111()11......,()11...............,t ij t ij ij
t ij t t i j W t t i j ρτρττρτ---?=--+???=--? 得到新的(),:1ij t t t τ=+，重复步骤2.
在步骤4中，挥发因子t ρ对于一个固定的1T ≥，满足
()
ln 1,..............ln 1t t t T t ρ≤-
≥+ 并且 1t t ρ
∞==∞∑
经过t 次挥发，非最优路径的信息素逐渐减少蜘蛛消失.
在上面的算法中，蚂蚁搜寻过程中，以信息素的概率分布来决定城市i 到城市j 的转移.而信息素的更新不外乎挥发和增强两个方面，在2.3.3选参原则中我们已经给出了信息素浓度的减少和增加对算法结果的影响，步骤3中，蚁群永远记忆到目前为止的最优解.
3.3.4 蚁群算法在TSP 问题应用中的数据验证
为W 上的一条边 不是W 上的一条边
因为下式满足：
(),1,0ij
i j A t t τ∈=?≥∑ 即()t τ是一个随机矩阵.
给出4个城市非对称的TSP 问题，距离矩阵和城市图(图3)如下所示：
()010.5110111.55011110ij D d ?? ? ?== ? ???
图4 城市图
假设蚂蚁数目4m =，所有的蚂蚁都从城市A 出，挥发因子0.5,1,2,3t t ρ==.根据GBAS 的计算步骤，矩阵共有12条弧，初始信息素记忆矩阵为：
()()()011211211211201121120011211201121121121120ij ττ?? ? ?== ? ???
计算GBAS 算法的步骤2，设蚂蚁行走路线如下表所示：
表4 蚂蚁行走路线表
蚂蚁k
路线 目标函数值 1:W A B C D A →→→→
()14f W = 2:W A C D B A →→→→ ()2 3.5f W = 3:W A D C B A →→→→ ()38f W = 当前最优解为：这个解是截止到当前的最优解，碰巧是实际最优解.
根据信息素更新规则，得到更新矩阵
第1只
第2只
第3只
()()()0124161241601241241112411201612416124
0ij ττ?? ? ?== ? ??? 这是第一次外循环结束的状态.
重复外循环步骤，由于上一次得到的2W 已经是全局最优解，因此按照信息素更新规则，无论蚂蚁如何搜寻，都只对路线2W 上的城市信息素进行加强，其它路线上的信息素进行挥发.得到更新矩阵为：
()()()014852414852401481482214814805241485241480ij ττ?? ? ?== ? ???
这是第二次外循环结束的状态.
继续重复外循环步骤，因为路线2W 为全局最优解.GBAS 只记录第一个最优解，信息素的更新也将不再依赖于群的行走路线，而是不断增强最优路径的信息素浓度，同时进行挥发.第三次外循环得到的矩阵为：
()()()0196114819611480196196331961960114819611481960ij ττ?? ? ?== ? ???
蚂蚁以一定的概率从城市i 到城市j 进行转移，信息素的更新是在步骤4中完成的，并随T 而变化.假设T 次外循环后得到了矩阵()()()|,ij
t t i j A ττ=∈，得到了当前最优解()W t .第T 次外循环前的信息素矩阵最优解为()(){}1,1,t W t τ--经过了T 次外循环后，得到()(){},t W t τ.
通过对蚁群算法在路径中应用分析我们可以得出 蚁群算法具有以下几个优点：
(1) 蚁群算法与其它启发式算法相比，在求解性能上面具有很强的鲁棒性(即基本的蚁群算法模型稍加修改，便可以应用于其它领域之中.)和搜索较优解的能力.
(2) 蚁群算法是一种基于种群的进化算法，具有本质并行性，易于计算中的并行实现.
(3) 蚁群算法容易与其它多种算法相结合，用于改善算法的性能.
结 束 语
蚁群算法因为其自身寻优能力强、在求解能力上有很强的鲁棒性、优化效率高、算法
灵活易于和其它算法相结合等特点，在各个优化领域中的应用是非常广泛的.
本文首先介绍了什么是蚁群算法及其原理，利用数学形式建立了算法模型，
诚然，该论文还许多不足之处.比如蚁群算法在实际应用的方面还没有完全发觉其潜力，我们大多数是在仿真实验中来研究该算法的，在参数选择中我们也是往往根据自己的直觉性和经验性来择优选择.大多都是对在实际问题研究条件或约束条件进行简化的前提下进行的，虽然简化了计算过程，但是和实际情况的结果还是有点出入的.因此这是个长期的研究过程，只有不断积累研究才能让蚁群算法在路径优化中得到更广泛的应用.
参考文献
[1] 黄贵玲,高西全,靳松杰,谈飞洋. 基于蚁群算法的最短路径问题的研究和应用[J]. 计算机工程与应用. 2007 (13)
[2] 靳凯文,李春葆,秦前清. 基于蚁群算法的最短路径搜索方法研究[J]. 公路交通科技. 2006 (03)
[3] 陈宏,胡宁静. 基于改进蚂蚁算法的城市交通最佳路径选择[J]. 长沙电力学院学报(自然科学版). 2006 (01)
[4] 温如春,汤青波,杨国亮. 基于改进蚁群算法的移动机器人路径规划[J]. 兵工自动化. 2010 (08)
[5] 陈伟,赵德安,平向意. 基于蚁群算法的喷涂机器人喷枪路径规划[J]. 机械设计与制造. 2011 (07)
[6] 牛治永,李炎,李晓岚. 基于改进蚁群算法的机器人路径规划[J]. 自动化技术与应用. 2011 (07)
[7] 刘雄，雷勇，涂国强. 基于蚁群算法的移动机器人路径规划[J]. 计算机仿真. 2011 (11)
[8] 崔丽群，许堃. 进蚁群算法求解两地是间最优路径[J].计算机仿真.2012(06)
[9] A Colorni，M Dorigo，V Maniezzo．Distributed optimization by antcolonies［C］．Proc of the First European Conf On Artificial Life，Paris，France Elsevier Publishing，1991:134－142．
Ant colony optimization algorithm is applied in the path
Auhuor: Sun Yang Yang Supervisor: Liu Chong
Abstract: How to choose the optimal in multifarious road system path is an important
issue in ant colony algorithm in path optimization. Understand the concept and principle
of ant colony algorithm is presented in this paper, on the basis of using mathematical
form the mathematical model of ant colony algorithm are given, the basic steps of ant
colony algorithm in the application. Through the analysis of the problems, solve several
path planning of ant colony algorithm is superior to domestication points, on the current
situation of the development of algorithms for the future research direction.
Keywords: ant colony optimization the algorithm model analysis of the application
research status and the future of the develop
致谢
时光荏苒，大学一晃而过，在最后的学习阶段即大学论文设计阶段我的我的论文导师刘冲老师给了我很大的帮助.我自己在从论文选题到搜集资料，从写稿到反复修改，期间经历了喜悦、聒噪、痛苦和彷徨.但是刘冲老师在这段时间里给了我很大的帮助，给了我耐心
的指导和无私的关怀，每次在论文方面遇到难题，刘冲老师都会抽出时间来和我们讨论，他对该论文独特的见解让我深受启发，经过刘冲老师的精心点拨，我的研究思路得到极大的扩展，最终也帮助我论文的顺利完成.在我设计论文的过程中刘冲老师严肃的科学态度，严谨的治学精神，精益求精的工作态度深深感染着并激励着我，在这里我要真挚的对刘老师说一声：谢谢！
我还要感谢在这四年中教导过我的所有老师，真是因为你们认真而负责任的教导不仅让我学到了知识，还让我学会了做人的道理，让自己的人格得到了升华，谢谢你们！最后还要谢谢在论文设计中帮助过我的同学，你们给了我很多建议和帮助，让我受益匪浅.
时间匆匆而过，转眼就是大学毕业时节，纵然有万分不舍但是终究还是要离开学习了四年的大学.在这里我要对所有老师，同学以及帮助过我的朋友表达我真挚的谢意.我也永远不会忘记自己是安庆师范学院的一名学生，在今后的工作中也会把安庆师范学院的优良传统发扬光大.
捕食搜索算法 动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成 的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有 发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有 猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间 没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻 找猎物。 模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatory search algorithm, PSA)。基本思想如下：捕食 搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较 优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从 而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索 之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(traveling salesm an problem )和超大规模集成电路设计问题(very large scale integrated layout)。 捕食搜索算法设计 (1)解的表达 采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一 6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负 贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾 客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。 (2)邻域定义 4 仿真结果与比较分析(Simulation results and comparison analysis) 设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。
山西工商学院 毕业设计 题目浅析物流配送路径优化问题 学生姓名杨美玲 学号200822054247 专业物流管理 班级08物流二班 指导教师李桂娥 二零一一年十月二十八日
目录 摘要 (ⅰ) 一、引言（问题的提出） (1) 二、物流配送路径优化问题的数学模型……………………………X 三、物流配送路径优化问题的遗传算法……………………………X （一）遗传算法的基本要素………………………………………X （二）物流配送路径优化问题的遗传算法的构造……………………X 四、实验计算与结果分析…………………………………………X 五、结论…………………………………………………………X 参考文献…………………………………………………………X 致谢………………………………………………………………X
中英文摘要 摘要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的遗传算法，并进行了实验计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方便有效地求得问题的最优解或近似最优解。 关键词：物流配送；遗传算法；优化 Study on the Optimizing of Physical Distribution Routing Problem Based on Genetic Algorithm Abstract：On the basis of establishing the optimizing model on physical distribution routing problem, this paper presents a genetic algorithm for solving this problem, and make some experimental calculations. The experimental calculation results demonstrates that the optimal or nearly optimal solutions to the physical distribution routing problem can be easily obtained by using genetic algorithm. Keywords：physical distributio n；genetic algorith m；optimizing
用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 之间有
学年论文之 家乐福超市物流配送路线优化 专业物流工程 班级 姓名 学号 日期
在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。 通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题，并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配送路线还可以进行再优化，从而达到运输成本最小化的目标。 关键词：物流配送；路径优化；节约里程算法
1.绪论 (1) 1.1选题目的和意义 (1) 1.2国内外物流配送路线优化研究现状 (2) 2. 家乐福超市配送路线现状 (3) 2.1家乐福超市概况 (3) 2.2家乐福超市配送路线作业现状 (4) 2.2.1 配送距离分析 (4) 2.2.2 车辆数分析 (5) 2.2.3 需求量分析 (6) 2.2.4 商品品种分析 (6) 2.3家乐福超市配送现有路线问题分析 (7) 3.配送路线优化建模与求解 (9) 3.1研究对象目标设定 (9) 3.2模型的构建 (11) 3.3节约算法 (12) 3.3.1节约算法的基本原理 (12) 3.3.2节约里程算法主要步骤 (13) 3.3.3基于节约算法的配送路线优化 (13) 3.3.4优化后的配送线 (24) 4.优化结果分析 (25) 4.1优化前结果 (25) 4.2优化后结果 (25) 4.3结论 (26) 5.总结与建议 (27) 参考文献: (28)
MATLAB实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE，其中AB，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC的蚂蚁分别走过了BCD 和DCB，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题
摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。 三、算法分析 对于本文的上述问题，有两种算法一(传统算法)和二(逆向标号算法)可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法[2]，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已
机器人的路径规划---蚁群算法 1.蚁群算法 众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M．Dorigo等意大利学者在1991年首先提出蚁群算法(Ant Colony System，ACS)以来，这种新型的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的使用。 蚁群算法的特点主要表现在以下五个方面： (1)蚂蚁群体行为表现出正反馈过程。蚁群在寻优的过程中会释放一定量的信息素，蚁群的规模越大，释放的信息素的量也就越大，而寻优路径上存在的信息素浓度越高，就会吸引更多的蚂蚁，形成一种正反馈机制，然后通过反馈机制的调整，可对系统中的较优解起到一个自增强的作用，从而使问题的解向着全局最优的方向演变，最终能有效地获得全局相对较优解。 (2)蚁群算法是一种本质并行的算法。个体之间不断进行信息交流和传递．有利于最优解的发现，并在很大程度上减少了陷于局部最优的可能。 (3)蚁群算法易于和其他方法结合。蚁族算法通过和其他算法的结合，能够扬长避短，提高算法的性能。 (4) 蚁群算法提供的解具有全局性的特点。一群算法是一种群只能算法，每只蚂蚁巡游的过程相对独立，他们会在自己的活动空间进行搜索，蚂蚁在寻优过程中通过释放信息素，相互影响，互相通信，保证了解的全局性。 (5) 蚁群算法具有鲁棒性。蚁族算法的数学模型易于理解，可以广泛使用在很多复杂的优化问题中，蚁族算法区别于传统优化算法的一个特点在于该算法不依赖于初始点的选择，受初始点的影响相对较小，并且在整个算法过程中会自适应的调整寻优路径。 由此可见，在机器人寻找最优路径的过程中，采用蚁群算法实现路径的规划问题，可以高效，准确的找到最优的路径。 2.移动机器人的路径规划 2.1环境信息处理 假设机器人运行环境为边长分别为x和Y的矩形区域，在矩形区域内分布有n
第三方物流运输方式和配送路径优化研究 摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。
用AＣＯ算法求解机器人路径优化问题 4.1问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗,最短行走路线，最短行走时间等),在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.２算法理论 蚁群算法（Aｎt ＣｏｌonｙＡｌｇoｒithm，ACA)，最初是由意大利学者Ｄｏｒigo M. 博士于１991 年首次提出，其本质是一个复杂的智能系统,且具有较强的鲁棒性,优良的分布式计算机制等优点。该算法经过十多年的发展,已被广大的科学研究人员应用于各种问题的研究，如旅行商问题,二次规划问题,生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Ｄorigｏ提出了精英蚁群模型（ＥAS）,在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢,并不能取得较好的效果。次年Dorigｏ博士在文献［3０]中给出改进模型(ACＳ),文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略,来得进行深度搜索。 Stüｔzｌe 与Hoｏｓ给出了最大－最小蚂蚁系统（MAX-MINAＳ),所谓最大－最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优,设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的,蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物,蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能,可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示,AE 之间有
蚁群算法在车辆路径问题中的应用 摘要 蚁群算法（Ant Colony Optimization, ACO）是意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。通过介绍蚁群觅食过程中基于信息素（pheromone）的最短路径的搜索策略，给出了基于MATLAB 的蚁群算法在车辆路径问题（Vehicle Routing Problem, VRP）中的应用。蚁群算法采用分布式并行计算机制，易于其他方法结合，而且具有较强的鲁棒性，但搜索时间长，容易陷入局部最优解。针对蚁群算法存在的过早收敛问题，加入2—opt方法对问题求解进行了局部优化，计算机仿真结果表明，这种混合型蚁群算法对求解车辆路径问题有较好的改进效果。 关键词：蚁群算法、组合优化、车辆路径问题、2-opt方法 1.车辆路径问题 车辆路径问题（VRP）来源于交通运输，1959年由Dantzig 提出，它是组合优化问题中一个典型的NP-hard问题。最初用于研究亚特兰大炼油厂向各个加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点。
车路优化问题如下： 已知有一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干可供派送的车辆，运载能力给定，每辆车都是从起点出发，完成若干客户点的运送任务后再回到起点。现要求以最少的车辆数和最少的车辆总行程来完成货物的派送任务。 2、蚁群系统基本原理 在蚂蚁群找到食物时，它们总能找到一条从食物到蚁穴之间的最短路径。因为蚂蚁在寻找食物时会在路途上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，会随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后面的蚂蚁再次碰到这个路口时，会选择激素浓度较高的路径走。这样形成了一个正反馈，最优路径上的激素浓度越来越高，而其他的路径上激素浓度却会随时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻找过程中，整个蚁群通过相互留下的信息素作用交换着路径信息，最终找到最优路径。 3、基本蚁群算法求解车辆路径问题 求解VRP问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，若干蚂蚁过程之间通过信息素值来交换信
蚁群算法在路径优化中的应用 作者：孙阳阳指导老师：刘冲 摘要针对蚁群算法在路径中的优化问题，本文首先介绍了蚁群算法的概念及其原理，利用数学 形式建立算法模型.根据蚁群算法计算的基本步骤来分析蚁群算法在交通路径优化、TSP问题等3 个方面的应用，由实验结果可知蚁群算法在路径优化中具有很好的可行性和优越性，能起到很 好的效果. 关键词蚁群算法算法模型算法步骤分析应用 1 引言 路径规划是指在具有障碍物的环境下，在符合某种评价条件中，寻找到一条从起始地点到目标地点最优的路径.蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化系统,计算法采用分布式并行计算和正反馈机制，且易于其它算法结合，目前已有许多关于其在路径规划方面的文献. 建立蚁群算法模型]2][1[，解决城市交通路径优化问题，实验结果表面在搜索效率和搜索最优解的能力两方面都有很大的提高.但是传统蚁群算法易陷入局部最优解和收敛速度较 4[ ，将传统蚁群算法进行改进，例如与栅格法相结合、慢，为此在机器人路径规划的应用中]7 在几何模型下建立模型等.提高了算法的有效性和鲁棒性，解决了蚁群过早陷入局部最优解的问题，扩大了蚂蚁的搜索空间，增强了蚁群算法在机器人路径规划中的适应能力. 本文通过对蚁群算法的研究以及解决几实际路径规划问题，得出了蚁群算法是有其可行性和优越性的，说明了该算法可以在众多优化领域中得到广泛的应用. 2 蚁群算法 蚁群算法(ant colony optimization),又称蚂蚁算法，简称ACO.是由Dorigom、Maniezzov、Colorni等人在1992年所发表的论文提出的，其灵感来源于蚂蚁在寻找食物中发现路径的行为.它是一种模拟进化算法，通过人工模拟蚂蚁觅食过程，即个体间的信息交流与合作不断排除不适合的路途，最终寻找到从蚁穴到食物源的最短路径. 2.1 蚁群算法的基本原理 蚂蚁在搜寻食物过程中总能找到一条从蚁穴到到食物的最优路径，这是因为蚂蚁在搜寻路径上释放一种特殊的信息素.当它们遇到一个还没有被走过的路口时，会随机的选择一条路径，而选择的路径与信息素的浓度有关，同时在该路径上它们也会释放自己的信息素.路径越短，信息素浓度越大；反正路径越长信息素堆积的越少.则过一段时间蚂蚁选择信息素浓度高的路径的概率越来越大，而其它路径随着蚂蚁越来越少的选择信息素浓度逐渐减小，这一就形成了一个正反馈现象，最终指导整个蚁群找到从蚁穴到食物源的最短路径. 2.2 蚁群算法的数学模型 2.2.1 问题的描述
物流配送的车辆路径优化 专业：[物流管理] 班级：[物流管理2班] 学生姓名：[江东杰] 指导教师：[黄颖] 完成时间：2016年6月30日
背景描述 物流作为“第三利润源泉”对经济活动的影响日益明显，越累越受到人们的重视，成为当前最重要的竞争领域。近年来，现代物流业呈稳步增长态势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业的市场需求持续扩大。特别是进入21世纪以来，在国家宏观调控政策的影响下，中国物流行业保持较快的增长速度，物流体系不断完善，正在实现传统物流业向现代物流业的转变。现代物流业的发展对促进产业结构调整、转变经济增长方式和增强国民经济竞争力等方面都具有重要意义。 配送作为物流系统的核心功能，直接与消费这相关联，配送功能完成质量的好坏及其达到的服务水平直接影响企业物流成本及客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，其中，车辆配送线路的合理优化对整个物流运输速度、成本、效益影响至关重要。 物流配送的车辆调度发展现状 VRP（车辆调度问题）是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序的通过，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量等限制）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为，不涉及时间的是路径问题，涉及时间的是调度问题。VRP示意图如下 当然，VRP并不止是这样的一个小范围，而是又更多的客户点与一个仓库链接，从而达
到一整个物流集群。 根据路径规划前调度员对相关信息是否已知，VRP可分为静态VRP和动态VRP，动态VRP 是相对于静态VRP而言的。静态VRP指的是：假设在优化调度指令执行之前，调度中心已经知道所有与优化调度相关的信息，这些信息与时间变化无关。一旦调度开始，便认为这些信息不再改变。 而VRP发展到现在的问题也是非常突出的，例如，只有一单货物，配送成本远高于一单的客户所给的运费，在这种情况下，该如何调度车辆？甚至还有回程运输的空载问题，在这些问题之中，或多或少都涉及到了VRP的身影，那么在这样的配送中怎么有效的解决车辆的路径优化问题就是降低运输和物流成本的关键所在。 解决怎么样的问题？ 现如今对于VRP研究现状主要有三种静态VRP的研究、动态VRP的研究以及随机VRP的研究。 而我对于VRP的看法主要有以下几点。 有效解决VRP或者优化车辆调度路径优化问题，那么将非常有效的降低物流环节对于成本的比重，有效的增大利润。 而我想到的方法，就是归类总结法。 建立完善的信息系统机制，将订单归类总结出来，可以按地区划分出来，一个地区一个地方的进行统一配送，这样也有效的降低了物流配送的车辆再使用问题，降低了成本。如下图所示。 仓库 客户 变换前 由上图可以看出来这样的路径，车辆需要来回两次，严重增加了配送成本，也增加了运输成本，使得利润并不能最大化。
其中，表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率。allowedk = C ? tabuk表示蚂蚁k下一步允许选择的城市。α为启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强。β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越 大，则该状态转移概率越接近于贪心规则；ηij(t) 为启发函数，表达式为。式中，dij表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中。（7）若集合C中元素（城市）未遍历完，即k for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCity(j,3))^2); end end MAXIT=10;%最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第K只蚂蚁 deltatau=zeros(NC,NC); % 第K只蚂蚁移动前各边上的信息增量为零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点[routek,lengthk]=path(distance,tau,alpha,beta,Citystart); % 指定起始点if lengthk 基于遗传算法的物流配送路径优化研究 标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 用单亲遗传算法求解配送车辆调度问题的研究 郎茂祥 （北京交通大学交通运输学院，北京 100044） 摘要：论文建立了物流配送车辆调度问题的数学模型，并针对传统遗传算法对复杂问题搜索效率低，易陷入“早熟收敛”的缺点，构建了求解物流配送车辆调度问题的单亲遗传算法，并进行了实验计算。计算结果表明，用单亲遗传算法求解物流配送车辆调度问题，可以取得比传统遗传算法更优的结果。 关键词：物流配送；车辆调度问题；单亲遗传算法；遗传算法 Study on the Partheno-Genetic Algorithm for Physical Distribution Vehicle Scheduling Problem LANG Mao-xiang，HU Si-ji （School of Traffic and Transportation，Northern Jiaotong University，Beijing 100044，China） Abstract：This paper established the model of physical distribution vehicle scheduling problem. On the basis of analyzing the shortcomings of traditional genetic algorithm in low searching efficiency and “Immature Convergence”, this paper established a partheno-genetic algorithm for solving physical distribution vehicle scheduling problem and made some experimental computations. The computational results had demonstrated that the partheno-genetic algorithm had higher optimizing efficiency and quality than 摘要 自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。 【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类 Study on Ant Colony Algorithm and its Application in Clustering Abstract： As the ant colony algorithm was proposed by M. Dorigo in 1991,it bringed a extremely large attention of scholars, in past short more than ten years, optimized, the network route, the function in the combination optimizes, domains and so on data mining, robot way plan has obtained the widespread application, and has obtained the good effect.This acticle discussed the basic principle of it at first, then introduced the TSP,this acticle also analysed the ant colony algorithm and its improved algorithm, and explanated it by the computer simulates, then it analysed the clustering algorithm and the ant clustering algorithm, builded the ant clustering algorith to solution the clustering by the traditioned ant algorithm. At last, this article also proposed the ant clustering algorith to soluted the clustering dependent on pheromon. Carry on the classification to the artificial data using this ant clustering algorithm; Use this algorithm to carry on the classification of the synthesize strength of the 2005 Chinese 24 universities; we can obtain the classified result which matches to the actual situation case. In the next work, we also should do the different cluster algorithm respective good and bad points as well as the classified performance aspect the comparison research; distinguish the different performance of different algorithm in the analysis when the dates are different. Key words： Ant colony algorithm; Computer simulation; clustering; Ant clustering 目录基于遗传算法的物流配送路径优化研究
基本蚁群优化算法及其改进毕业设计
相关主题
文本预览