（计算机应用技术专业论文）基于模糊分群的多种群蚂蚁优化求解车辆路径问题.pdf

摘要 在组合优化问题中，车辆路径问题( v e h i c l er o u t i n gp r o b l e m ) 属于比较典型的 n p h a r d 问题。一般情况下组合问题可以模式化为排序问题与分类问题，然而 v r p 则同时具备排序与分类这两个属性，且这两个属性问题在本质上都是n p 难 的，从而v r p 一般很难得到解决。以往解决该问题的方法多半是先分组然后再 排序，这种方法在规模较小的时候比较有效，但规模稍微扩大，结果就会很不理 想。或者一些算法过分注重排序，从而在一定程度上忽视了分群的影响。本文以 蚁群优化( a c o ) 以及扫描法为出发点，提出了一种模糊分群的多利，群蚂蚁优化解 决车辆路径问题，综合运用模糊分群、多蚁群、自适应技术来改进现有a c o 在 解决车辆路径问题上的缺陷，使问题能够更快更好的解决。 经过几组v r p 的仿真测试，并和其它a c o 求解v r p 的求解结果比较分析 发现，本文提出的算法在一定程度上改善了原有算法的求解结果。 关键词：蚁群优化车辆路径问题模糊分群 a b s t r a c t i nc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，v e h i c l er o u t i n gp r o b l e m ( v r p ) i sa t y p i c a ln p h a r dp r o b l e m g e n e r a l l ys p e a k i n g ，c o m b i n a t i o no p t i m i z a t i o np r o b l e m sc a l l b em o d e l e dt o s e q u e n c i n gp r o b l e m sa n dc l u s t e r i n gp r o b l e m s ，h o w e v e r ，v r p c o m b i n e sb o t hs e q u e n c i n g ( t od e t e r m i n es e q u e n c eo fr o u t e ) a n dc l u s t e r i n ga t t r i b u t e s m o r ei m p o r t a n t l y , t h e s et w oa t t r i b u t e sa r en p h a r di ne s s e n c e s o ，i ti sv e r yh a r dt o s o l v ev r p ，i nt h ep a s t ，m o s ta p p r o a c h e st os o l v es u c hp r o b l e mi sr o u t ef i r s t c l u s t e r s e c o n d w h e nt h ep r o b l e ms c a l ei sv e r ys m a l l ，s u c hk i n do fa p p r o a c h e sa r ee f f e c t i v e b u t ，a st h es c a l ei sm u c hl a r g e r ，t h es o l u t i o nb yt h o s ea p p r o a c h e sb e c o m ei n v a l i d i n t h i sp a p e r , w ep r o p o s ean e wa p p r o a c ht os l o v ev r p , w h i c hb a s e do na n tc o l o n y o p t i m i z a t i o n ( a c o ) a n ds w e e pm e t h o d b e s i d e s ，b yu s i n gf u z z yc l u s t e r i n g ，m u l t i p l e a n tc o l o n i e sa n da d a p t i v et e c h n o l o g yt oi m p r o v et h ea l g o r i t h m w ea l s ot e s to u ra l g o r i t h mo ns o m ev r pb e n c h m a r k sp r o b l e m sa n dc o m p a r et h e s o l u t i o nw i t ht h eo t h e ra c o a l g o r i t h m _ t h er e s u l t ss h o wt h a to u ra l g o r i t h mp e r f o r m b e t t e ri ns o m er e s p e c t s k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ，v e h i c l er o u t i n gp r o b l e m ，f u z z yc l u s t e r i n g 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：当鱼主圭 日期：呈! ! 里：至：圣 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位敝作者警蟊海洋 日期：2 口挥舌月弓白 弩争日煮轹哞 签 币职嚣 中山大学硕士学位论文 1 1 研究背景与动机 第1 章绪论 近年来，由于贸易的高度自由化以及各产业内部竞争的白热化，提高效率以 及利润率成为了各企业能否战胜竞争对手的关键。然而提升效率以及利润率，必 须做到高效的供应链管理( s u p p l yc h a i nm a n a g e m e n t ，s c m ) 来不断压缩产品生命周 期，而物流( l o g i s t i c ) 成为了供应链管理的关键。所以能够很好的使用物流技术以 提升顾客服务水平、满足顾客的多元化需求已成为企业强化竞争优势的重要策 略。 据有关数据统计显示，物流成本往往要占到销售金额的1 5 到2 5 左右， 而运输成本往往又占到了物流成本的3 5 到5 0 之间。上述比例在不同地区以 及不同产业可能略有调整，但这些数据足以证明运输对物流总成本的节约具有举 足轻重的作用，所以有效降低运输成本是提升企业整体利润的直接方法。 高效的运输往往离不开一个良好的运输规划方案，近些年来企业对运输路径 规划非常重视，特别是第三方物流公司，都存在专业的路径规划机构。在学术研 究上，特别是运筹研究( o p c r a t i o n a lr e s e a r c h ) 学术上，把运输路径规划问题转化 为网络组合最优化问题( n e t w o r kc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m ) 1 ，2 来求解， 并正式命名为车辆路径问题( v i h i c l em u t i n gp r o b l e m ，v r p ) 。目前，比较常见的模 式化( m o d e l i n g ) 方法是利用整数规划( i n t e g e rp r o g r a m m i n g ) 进行精确解( e x a c t s o l u t i o n ) 计算。但绝大多数能求得精确解的方法，在问题规模较大时都无法在多 项式时间内求得结果。随后出现了一些简单的启发式算法( h e u r i s t i ca l g o r i t h m s ) ， 例如扫描法( s w e e pa l g o r i t h m s ) 、插入法( i n s e r t i o n ) 、节省法( s a v i n g sm e t h o d ) 9 等 等相继被提出，可以快速计算出比较经济的运输路径，但求解质量不高。 出于以上考虑，学者们又相继提出了元启发式算法( m e t a h e u r i s t i c ) 来求解车辆 路径问题。这些元启发式算法包括：禁忌搜索( t a b us e a r c h ，t a ) 、模拟退火法 ( s i m u l a t e da n n e a l i n g ，s a ) 、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、粒子群优化算法 ( p a r t i c l es w a r mo p t i m i z a t i o n ) 、蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 等 3 ，4 ，8 】。a c o 相对其它算法在车辆路径问题上的研究要少，虽然已经达到不错的 中山大学硕：i ：学位论文 求解效果，但是仍然存在很大的改进空间以及深入研究的地方。 1 2 研究目的与内容 蚁群优化最早是用来求解旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，目前 有关a c o 在解决旅行商问题上有了较大的进展，对于较大规模的旅行商问题都 能够得到很满意的解。但是在车辆路径问题上，却很难有较大的突破。一方面是 由于车辆路径问题在难度上确实要难过旅行商问题很多；另一方面，传统的蚁群 优化在解决车辆路径问题上存在过于偏重路径而忽略顾客问分群的问题。没有良 好的顾客分群做为基础，其实很难做到路径长度或者说成本上的较大优化。 本文的研究目的在于提出一种新型的改良式多种群蚂蚁优化算法来解决车 辆路径问题。文中主要从以下几点出发来实现这一目的： 1蚁群优化是近十几年来提出并广泛应用的算法，在求解各种离散优化问题上 已有良好的表现。其中关于使用a c o 来求解v r p 系列问题也有将近十年的 历史。文中较详细整理了目前国内外学者使用a c o 解决v r p 的各种模式并 作一般性比较。 2 过往学者在使用a c o 求解v r p 时经常使用候选列表( c a n d i d a t el i s t ) 来提高 路径转移时的计算效率。这种方法在一定程度上改善了算法运行效率，但是 也忽略了问题本身的整体性，而且候选列表的大小较难把握。本研究尝试使 用了一种基于扫描法的模糊聚类方法来强化顾客的群体性，以此来达到整体 性以及候选列表的作用。 3本研究继承了以往学者关于多种群的思想，设计了两个种群的蚂蚁，分别针 对性的进行区域性搜索以及整体性改善。第一个种群的蚂蚁必须以事先的模 糊分群为导向，称之为区域导向型蚂蚁；而第二种群的蚂蚁在构建路劲的时 候以全体顾客为候选集并且不存在任何区域导向，称之为整体性蚂蚁。在蚂 蚁数量上，整体性蚂蚁的数量要小于以区域导向型蚂蚁。但是，两群蚂蚁公 用同一个信息素矩阵，从而达到交流以及彼此协作的目的。 4 研究后期，主要进行小范围的样例测试，主要为了获取本研究所提出的模 式的求解效果。最后。进行标准的v r p 样例测试来比较本研究的算法和其 它求解v r p 的a c o 算法进行比对。 2 中山大学硕士学位论文 本文研究的内容主要是针对具有载重限制的车辆路径问题( c 妞) 进行的， 其它复杂的车辆路径问题，比如说带时间窗、带回程，暂不作研究范围，但可以 进行相应的扩展与应用。 1 3 研究架构与流程 图1 - 1 研究流程图 在确定了研究的相关主题后，本研究首先查阅相关问题的文献著作，确定问 3 中山人学硕：i ：学位论文 题的数学模型，并且仔细研究了各种求解v r p 的算法，认真分析了现有蚁群优 化在求解v r p 时所用到的方法，然后提出自己的研究构想，设计具体的算法并 编码事先，再进行具体的样例测试以及算法调整，最后进行比较分析。研究流程 可如图1 1 所示。 1 4 论文内容安排 第1 章首先介绍了论文选题的背景与动机，随后简要介绍了本文将要研究的 内容与目的。 第2 章为文献回顾章节，概要性的介绍了车辆路径问题的定义、模型以及各 种解法，紧接着从蚁群优化的起源、发展、应用三个方面详细分析了蚁群优化算 法，最后简要性的介绍了蚁群优化算法在车辆路径问题上的应用发展。 第3 章为本文的核心章节，介绍了本文所使用的新型蚁群优化算法求解车辆 路径问题的模型与思想。 第4 章对上一章节所提的思想进行实验验证与分析。 第5 章为工作总结与未来展望。 4 中山大学硕士学位论文 第2 章文献回顾 本章首先对车辆路径问题做了一个综述性的回顾，分析了当前各种算法求解 车辆路径问题的。本章第二部分主要就蚁群优化算法进行了探讨，主要包括蚁群 优化算法的起源、各种蚁群优化算法以及蚁群优化算法的主要应用。最后介绍了 各种求解车辆路径问题的蚁群优化算法。 2 1 车辆路径问题 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是一个具有强烈应用导向的现 实问题，但是问题本身又具有很高的理论价值。所以自d a n t z i g 和r a m s e r ( 1 9 5 9 ) 年 1 】首次提出卡车配送问题( 也就是后来的v r p 的原型) 后就受到了广泛的关注 和众多学者的深入研究与探索。此外，由于电子计算机的应用与普及，也为v r p 的深入研究以及应用提供了物质上的保证。 2 1 1 车辆路径问题定义与模型 虽然车辆路径问题首次提出是在1 9 5 9 年，但是车辆路径问题的子问题旅行 商问题( t r a v i n gs a l e s m a np r o b l e m ，t s p ) 却很早就被提出，并且一直被学者们广泛 讨论和研究。t s p 的定义十分简单：旅行商( 或称为销售员) 从某个特定城市出发， 访问其他城市，最后再回到原出发城市，这些城市都只能够访问一次，并且主要 目标是使得总旅行距离最小。针对本研究，可以这样描述，一辆货车从配送中心 出发，完成所有送货服务后，再回到配送中心的最短车辆路径问题。虽然t s p 描述十分简单，但是当问题的维度较高时，最优解一般很难求得，t s p 很早就被 证明为n p - h a r d 问题。 以下使用数学语言来对t s p 进行简单的描述。 记g = ( 旧为赋权图，肛( j ，z ：以) 为顶点集，e 为边集，各顶点间的距离由 已知( 妒0 ，d i i = o o ，i d 功。则经典的t s p 可写成如下的数学规划模型 m i n 办嘞( 2 1 ) 中山人学硕：l ：学位论文 s u b j e c tt o ： 畅= 1 ， i v ， j = l 吻= 1 ， 歹y ， 而- ls l - 1 ，v scv ， i = l 户l 而 o ，1 ) ( 2 2 ) 其中，i 习为集合s 中所包含g 的顶点数，第一个和第二个约束表面每个点只有 一条边进和一条边出；第三个约束则表明没有任何回路，事实上也就是一条哈密 顿回路 2 ，1 8 】。 与基本的t s p 相比较，v r p 同样需要对每一个城市或者顾客进行一次访问， 且最终找到一个总代价最小的路线集。但是，v r p 一般需要多辆车并且还存在 载重限制，可如图2 1 所示，其中图2 1 ( a ) 表示简单t s p ，2 1 ( b ) 表示v r p 。 图2 1t s p 与v r p 的区别 此外，v r p 还可能包含一些各种限制，如： 1 容量限制，对于每个顾客f 都存在一个需求量西，任何车辆所负责解决的需 求量不能超过车辆的负载能力。这种v r p 是较为基本的类型，称为c v r p 。 2 总长限制，任何路径( 或时间) 长度不能超过某一个常数，这个长度包括顾客 6 中山大学硕士学位论文 间的行驶时间和在顾客点的停滞时间。该限制的v i 冲一般称为d v r p 。 3 时间窗限制，某个顾客必须在某时间段 6 懈e 】中被访问，追踪带时间窗限制 的v r p 称为冲t w 。 此外，随着现实中的各种需要，还存在各种各样的限制，比如说访问顺序的限制， 以及顾客的优先级等 2 ，9 】。 由于c v r p 具有典型的代表性，且其他类型的v r p 可以规约为c v r p ，故 以下针对c v r p 进行分析。一般c v r p 用数学语言可以这样描述，给定一个网 络图g = ( ，肛 m ，“，) 代表需求顾客的节点集合，其中刀表式有以个顾客， 1 ，d 表示配送中心，e = 仉桫l 吁玢q ) 为边的集合，代表各需求节点之间的路 径长度，v f 和哆之间的路径成本可以用距离矩阵c = 勺，fd = o ，1 ) ，c i j 表示f 节点 到_ ，节点的路径成本；假设有m 辆载重相同的运输车辆，每台车载重量为q ，每 个节点的需求量为q i ，且q i 为自然数，将n 个节点指派给m 辆车作配送服务， 每个需求点必须被服务且只能被一辆车服务一次，每两车服务的载重容量不能超 过车辆的容量限制，依照最小运输成本的原则安排每两车配送的路径，且配送路 径由配送中心出发最后又返回配送中心，每辆车的配送路径不能产生子回路。根 据上述定义与要求，可以写成如下简单的具有装载限制的车辆路径问题( c 廿) 数学模型： m i n c ：f 勘( 2 3 ) s u b j i e c tt o ： 喀儿q i _ l 膏 虼= l 七= i x 肚= y j k i = l x o k = 儿 皇i 啄- l s l 一1 i j e s x s k l ，2 ，k )( 口) ( 6 ) j 1 ，2 ，胛) ，k 1 ，2 ，k ) ( c ) i l ，2 ，以) ，k 1 ，2 ，k ) ( d ) s l ，2 ，胛) ，k l ，2 ，k ) ( p ) 啄 o ，1 ) i 1 2 ，刀) ，j l 2 ，以) ，k l 2 ，厨( 力 y t k 0 ，1 ) i l ，2 ，刀) ，k l ，2 ，k )( g ) ( 2 4 ) 式( 2 - 3 ) 为求解目标，式( 2 4 ) 中( a ) 式为每辆车的载重限制，( b ) 式表明每个顾客点 7 中山人学硕i ：学位论文 必然有一辆车经过，( c ) 式和( d ) 式共同确保了每个顾客点只有一条边进入和一条 边出去，( e ) 式表明了路径中没有回路，( f ) 和( g ) 分别限定了取值【1 8 】。 2 1 2 车辆路径问题的常见求解方法 根据b o d i n 等人【2 2 】的总结以及最新的研究结果 3 2 ，3 3 】可以将常见的求解车 辆路径问题的方法规约为以下几个大类： l 先分群然后再排路径( d u s t e rf i r s t r o u t es e c o n d ) ：先将顾客点分成若干个群组， 然后分别对每一个群组设计最优的路径，如g i l l e t 和m i l l e r ( 1 9 7 4 ) 【1 4 提出 的扫描法( s w e e pa l g o r i t h m ) ，还有f i s h e r 和j a i k u m a r ( 1 9 7 8 ) 提出的花瓣法 ( p e t a la l g o r i t h m ) 。 2 先安排路径然后再进行分群处理( r o u t ef i r s t d u s t e rs e c o n d ) ：先将整个问题当 成t s p 进行路径安排，然后进行分割，方法有b o d i n ( 1 9 8 3 ) 等人 2 3 1 提出的 巨集分割算法( g i a n tt o u r a l g o r i t h m s ) 。 3 改善法以及交换法( i m p r o v e m e n t e x c h a n g e ) ：首先根据某些方法获取一组解， 然后再针对这组解进行改善，常见的有l i n ( 1 9 6 5 ) 等人提出的r - o p t 。更多的 时候该方法是作为其他方法的辅助性算法。 4 节省法( s a v i n g sh e u r i s t i c ) ：较为经典的是c l a r k e 和w r i g h t ( 1 9 6 4 ) 1 5 提出的 算法，顾名思义，节省法一般计算两顾客点之间若相连相对于分别到配送中 心之和的节约量。后来的各种启发式算法也常用整个值作为启发值或者说相 关值，包括最开始的a c o 解决v r p 的算法( 1 9 9 7 ) 3 。 5 精确解法( e x a c tp r o c e d u r e s ) ：精确性解法包括分支限界法( b r a n c ha n db o u n d m e t h o d ) 、动态规划( d y n a m i cp r o g r a m i n g ) 等。由于v r p 属于n p - h a r d 问题， 因此这类解法只能够解较小规模的问题，一旦规模稍微扩大，这类方法基本 不可能获得最优解。 6 人机互动法( i n t e r a c t i v eo p t i m i z a t i o n ) ：这类方法将使用者的决策和计算机的 计算能力并入求解过程。事实上，很多经典的方法都有可能从这种方法发展 而来，只不过是将人的决策进行详细的分析，然后进行总结，形成确定性的 事实。 7 数学规划法( m a t h e m a t i c a lp r o g r a m m i n ga p p r o a c h ) ：以数学规划法直接求解 中山大学硕士学位论文 v r p 1 8 ，但这类方法能够求解的v r p 十分有限，一般只能求解小型问题。 8 元启发式算法( m e t a h e u r i s t i c s ) ：v r p 求得最优解的时间会随着顾客点数的增 加而成指数型的增加，在计算时间有限的情况下，一般很难求得最优解。启 发式算法则以近似最优解来代替最优解，但在求解时间上则较小。启发式算 法为目前最为常用的方法，有g e n d r e a u 等人提出的禁忌搜索( t a b us e a r c h ) 、 j l a w r e n c e 提出了用遗传算法( g e n e t i ca l g o r i t h m ) 来解决v r p 9 ，1 2 ，1 3 。 事实上，经过几十年的发展与研究，特别是最近二十年物流业的大规模发展，已 经存在着很多求解v r p 的方法与模式，但是本文不可能一一进行详尽的分析与 说明，以下只是就本文将要用到的一些基本方法进行说明与分析。 扫描法( s w e e pa l g o r i t h m ) 扫描法由g i l l e t t 和m i l l e r 于1 9 7 4 1 4 年首先提出，属于先分群再排路径的两 阶段式求解方法。第一阶段如图2 - 2 ( a ) 所示，为分群阶段，已站场为原点计算出 所有顾客的极坐标值，并进行排序处理。然后再以一顾客为起始顾客，开始往顺 时针或者逆时针方向扫描，直到满足车辆路径最大装载量但同时不超过装载限制 的顾客属于同一分群。然后在第二阶段将各分群完的顾客作为独立的t s p 来进 行求解。具体的算法步骤可如下所示 1 9 】： 步骤1 选择一辆未使用的车辆k ； 步骤2 从最小角度且未被访问的顾客点开始装车，直至将要超过车辆的载 重为止。如果还存在未访问的顾客点，返回至步骤1 ； 步骤3 依据解决t s p 的方法( 精确法或者近似法) 来优化每一条车辆路径。 此外还可以根据路径间交换法来改善解的质量。 m i l l e r 和g i l l e t 在文中提到，把问题先做聚群处理的优点时，将问题的复杂 度降低了，不会随着问题的规模而求解的复杂度呈指数增长，当然并不一定能够 保证求解质量。此外，扫描法也不够稳定，当从不同的顾客为扫描起始时，解的 质量可能存在巨大的差异。 事实上，扫描法是对人类处理这类问题的直观解决方法的总结，呈现出一种 贪心心态，而且适用范围有很大的限制，对于存在路径长度限制的车辆路径问题 则不易处理。但是，扫描法对于一种事实的认识与总结，对于求解这类问题确实 存在一定的启发作用。 9 中山人学硕i ：学位论文 图2 - 2 扫描法示例图 节省法( s a v i n g sh e u r i s t i c ) c l a r k e 与w r i g h t ( 1 9 6 4 ) 1 5 首先提出节省发来求解车辆路径问题，该方法 以三角不等式为基础，起始条件为一辆车只服务一个顾客，因此若有刀个顾客便 会有，l 条路线，然后计算路线问合并而产生的节省值，依据节省值进行从大到小 的排序，在车辆载重限制下，依序进行合并路径，直到不能有所改善为止。使用 的方法有三种：连接( j o i n ) 、并 k ( a t t a c h ) 、合并( m e r g e ) - - 种，总体而言，这种方 法是利用交换的方式，将较短路径与原始路径进行交换来降低路劲距离成本。有 关节省值的计算以及示意图( 图2 3 ) 如下： 1 0 中山大学硕士学位论文 图2 - 3 节省法不意图 s o = d 吣+ d o j d 口 其中幽表示顾客i 到配送中心的距离，或者距离成本，如表示顾客f 到顾客_ ，的 距离值。关于连接、并入、合并的定义如下： ( 1 ) 连接：将两个单独顾客点连接成一条线路，也就是图2 3 所示。 ( 2 ) 并入：一个为单独顾客点线路，另一个为某一条线路中的一个点，将该顾客 点并入该线路，基本和( 1 ) 类似。 ( 3 ) 合并：将两条线路合并为一条线路。 k - o p t 交换法 k - o p t 交换法最早是在1 9 6 5 年 1 0 ，1 9 3 提出，其中k 表示每次交换的路径数。 k 值愈大一般能改善的可能性也越大，而且改善的效果也有可能越明显，但是算 法的复杂度随之要高很多。所以k 值一般不会太大，常见的就是2 - o p t 和3 - o p t 。 对于2 - o p t ，可以用这样一个范例来说明，比如说给定一个配送中心以及4 名顾客，预设的行驶路径为 如图2 3 所示。然后在路径上选 取两条不相邻的两条( 1 ，2 ) 和( 3 ，4 ) ，用( 1 ，3 ) 和( 2 ，4 ) 代替，如果调整后的路径为可行 解并有所改善，就保留交换后的路径。 中山人学顾1 j 学位论文 图2 4 2 - o p t 交换法 2 2 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ) 蚁群优化( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 最早( 1 9 9 1 年) 是由意大利的学者 d o r i g o 等人 2 3 】根据蚂蚁寻觅食物的行为所提出来的一种群体智慧( s w a r m i n t d l i g e n c e ，s i ) 算法。经过将近二十年的深入研究与发展，现在的蚁群优化已由 当初的简单版本蚂蚁系统( a n ts y s t e m ) 发展出各种颇具实用性以及优越性的版 本，比如说精华蚂蚁系统( e l i t i s ts t r a t e g yf o ra n ts y s t e m ，e a s ) 2 7 ，基于排列的蚂 蚁系统( a s 啪l c ) 2 5 1 ，最大最小蚂蚁系统( m a x - m i na n ts y s t e m ，m m a s ) 2 4 】以及较 为经典的版本蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 6 】。于此同时，a c o 的应用领 域也迅猛扩展，特别是在组合优化领域展现了极强的生命力，已从最开始的旅行 商问题、二次分配问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ，q a p ) 渗透到图着色问题、 工件排序问题、车辆调度问题、大规模集成电路设计、通讯网络的优化、机器学 习等等 1 6 】，a c o 在对于各种离散优化问题似乎存在着天然的优势。 1 2 中山大学硕士学位论文 2 2 1 自然界真实蚂蚁的行为 自然界中，蚂蚁所需要的食物总是毫无规律的散布于蚁穴周围，而且在距离 上经常会远远超过蚂蚁的视力以及嗅觉范围。但是，通过观察可以发现，蚂蚁总 是能够找到一条从蚁穴到食物源的最短路径或者近似最短路径。 生物学研究表明，单只蚂蚁的能力是非常弱的，几乎不可能完成寻找最优路 径的任务。蚂蚁之所以能够完成如此复杂的任务，在于蚂蚁是一种群居性昆虫， 单个蚂蚁的能力虽然十分有限，但是一群蚂蚁却能够达到一种高度结构化的群体 组织，通过相互间的协作来完成远远超过单只蚂蚁个体能力的复杂任务。研究发 现，为了完成蚂蚁个体间以及蚂蚁与周围环境之间的通信，蚂蚁向所走过的路径 上释放的一些化学物质，一般将这些化学物质称为信息素( p h e r o m o n e ，也称为费洛 蒙) 。当一群蚂蚁开始寻觅食物的时候，蚂蚁最开始总是在蚁穴的附近随机的探 索，每当蚂蚁走过一段路径，就会在路径上释放信息素，信息素的浓度会随着时 间增长而慢慢的蒸发，然而蚂蚁可以嗅到信息素的气味，并根据信息素的气味以 及浓度来判断下一步移动的方向。当最先的蚂蚁找到食物返回蚁穴的途中，会跟 随群体所留下的信息素来移动返回蚁穴，同样，在返回的蚁穴的路径上，也会再 次留下信息素分泌物来加强浓度，使得其它蚂蚁能跟随较强的信息素浓度来持续 强化这条路径的信息素浓度，从而使得蚂蚁不会走较长的路径。该过程是一个正 向反馈的过程，当蚂蚁选择一条路径的几率增加，蚂蚁的数量也会相应的增加， 使得蚁群最终趋向于同一最优路径。以下的范例边具体描绘出蚂蚁从开始觅食到 寻找到一条从蚁穴到食物源间的最短路径过程。 图2 5 是真实描述了蚂蚁在寻觅食物过程中遇到障碍物时，如何透过信息素 来选择较短路径的过程。假设有蚁群蚂蚁正在食物和蚁穴之间来回往返，如图 2 - 5 ( a ) 所示。突然间，在此路径上加上一个障碍物，使得原本蚂蚁行走的路径中 断，如图2 5 ( b ) 所示。经过一段时间后发现，蚂蚁会在岔路处选择较短的路径继 续行走。图2 5 的详细描述如下 6 】： ( a ) 假设一开始蚁穴和食物源之间没有任何障碍物，一般蚂蚁会随着信息素的浓 度选择最近的路径往返。 ( b ) 突然在路径上加入一个较大的障碍物，使得原来的路径上出现了一长一短两 条岔路。最开始，由于两条岔路都没有信息素，所以蚂蚁选择路径的概率是 中山人学硕二l ：学位论文 相同的。 图2 5 真实蚂蚁寻找最优路径的过程( 参考自d o n g oe t a l ，1 9 9 7 1 6 ) ( c ) 两条路径上都存在较多的蚂蚁行走，但是由于蚂蚁行走的速度基本一致，所 以较长路径上爬行的蚂蚁平均每一段上要少过较短路径上的蚂蚁，又由于信 息素的蒸发，则较长路径上的信息素要明显弱过短路径。 ( d ) 由于短路径上积累的信息素要明显强过长路径，所以到最后会有更多的蚂蚁 选择短路径，而长路径几乎不再有蚂蚁选择。 从上述蚂蚁真实觅食的过程，可以总结出蚂蚁的行为具有以下三大特性：( 1 ) 路径越短，路径上的信息素的累积速度越快；( 2 ) 选择路径时会明显偏向于信息 素浓度较高的路径；( 3 ) 蚂蚁时间具有很好的协作精神，利用信息素这个平台来 相互沟通。蚁群优化正是受这些启发从而开发出来的。 2 2 2 蚁群优化算法的发展 受到自然界真实蚂蚁的启发，意大利学者d o f i g o 等【2 3 】于1 9 9 1 年提出了最 早的蚁群优化算法一蚂蚁系统( a n t s y s t e m ，a s ) 。蚂蚁系统最初也只是应用于旅 行商问题( t s p ) 上。事实上，当初求解的效果并不理想，和一些经典的元启发 式算法相比，还存在一定的差距。但是，蚂蚁系统的提出却开辟了一条崭新的道 1 4 中山大学硕士学位论文 路，为后续改进的蚁群优化算法提供了一个平台，从而能够开发出各种优秀的蚁 群优化算法，同时蚁群优化算法的应用范围也不断扩展。 表2 - 1a c o 算法( 按照出现时间的先后顺序排列，参考自d o r i g oe t a l 。2 0 0 6 1 1 6 ) a c o 算法主要参考文献作者 蚂蚁系统( a s ) 精华a s a n t - q 蚁群系统( a c s ) 最大最小a s 基于排列a s a n t s 超立方体a s d o r i g o ( 1 9 9 2 ) ；d o r i g o ，m a n i e z z o ，& c o l o m i ( 1 9 9 1 a , b ) 2 3 】 d o d g o ( 1 9 9 2 ) ；d o r i g o ，m a n i e z z o ，& c o l o m i ( 1 9 9 1 a , b ) 2 7 】 g a m b a r d e l l a & d o r i g o ( 1 9 9 5 ) ；d o r i g o & g a m b a r d e l l a ( 1 9 9 6 ) 2 6 】 d o r i g o & g a m b a r d e l l a ( 19 9 7 a , b ) 6 】 s t t l t z l e & h o o s ( 19 9 6 ，2 0 0 0 ) ；s t u t z l c ( 19 9 9 ) 2 4 】 b u l l n h e i m e r ，h a r t l ，s t r a u s s ( 1 9 9 7 ，1 9 9 9 c ) 2 5 】 m a n i e z z o ( 19 9 9 ) 2 8 】 b l u m ，r o l i ，d o r i g o ( 2 0 0 1 ) ；b l u m & d o r i g o ( 2 0 0 4 ) 2 9 】 表2 一l 中按照时间顺序展示了一系列蚁群优化算法，其中的大部分算法都是 以a s 为基础进行扩展的，也就是说，这些算法基本保留了a s 算中构造解的过 程以及信息素的蒸发模式。这些扩展算法大致包括：精华蚂蚁系统( 简称e l i t i s t a s ) 、基于排列的蚂蚁系统( 简称r a n k - b a s ea s ) 和最大最小蚂蚁系统( 简称 m a x - m 1 na s ) 。与a s 算法相比，这些扩展算法的不同之处主要体现在对信息 素的更新方式有所不同，此外还有信息素积累过程中的一些附加细节。此外，学 者们积极探索能够进一步改善问题求解效果的新型蚁群优化算法。这些新型扩展 算法，主要包括a n t q 和它的后续算法蚁群系统( a n tc o l o n ys y s t e m ，简称 a c s ) ，采用数学程序设计中的下限技术的a n t s 算法，以及a c o 的超立方体 ( h y p e r - c u b e ) 框架，主要是为了自动调节信息素的值，使得它们都能够落在 o ，1 】 中。在此，文中将以优化t s p 为例，简要介绍一下几种常用蚁群优化算法，并大 致了解一下蚁群优化算法的发展过程以及各种版本之间的异同。 蚂蚁系统( a n ts y s t e m ) 系列优化方法 蚂蚁系统( a s ) 是最初被提出的蚁群优化算法，作为基础，随后又产生出 了两个衍生版本，即精华蚂蚁系统( e a s ) 以及基于排列的蚂蚁系统( a s 跳) 。这 些版本的蚁群优化算法在主题构建上基本类似，所不同的只是存在信息素更新以 中山大学硕j ：学位论文 及一些实现细节上的差距。以下将以a s 为基础首先介绍这些算法的共同之处， 然后分别说明e a s 以及a s 啪k 在一些实现细节上的差异。 a s 的主体大致包括两个部分，即路径的构建以及信息素更新，以下将以t s p 为实例详细介绍上述两个过程。 路径的构建 路径的构建过程主要依据两个方面的信息，其一启发式信息，其二，路 径上人工蚂蚁所产生的信息素浓度t ，。每当蚂蚁七从城市i 出发选择下一个将要 访问的城市歹时，便会依据由上述两个信息组成的概率选择公式进行选择下一个 会访问的城市，这里暂且记作，选择公式可如下： 露= 晶瑚n ； ( 2 5 ) 式中的口和是两个重要性参数，分别代表了信息素信息勺以及启发式信息嘞 的重要性程度。式中的启发式信息嘞= 1 略( 由一般表示为两个城市间的距离) 。 根据实验表明，口一般设置为【1 ，2 之间的某一个常数，而为 2 ，5 之间的某一个 常数，往往算法能够达到较优的结果。此外，任何一项为0 ，则算法就蜕化为随 机贪心算法或者毫无偏向性的累积优化算法，这两种方法基本上都不能够得到较 优的结果。此外，n ，七则为限定集合，表明下一步有可能将要访问的城市集合， 主要为了排除那些不能够访问的城市，比如说已经访问过的或者城市i 本身不能 到达的城市，这样能够减少搜索访问，防止不可行解的产生。 信息素更新 为了对上述所产生的路径进行良好的反馈，从而使得搜索朝着一个更加良好 的方向，一般需要进行信息素的更新。信息素更新主要是为了突出那些较优的路 径，使得在一轮的迭代过程中有更多的蚂蚁选择这些较优路径的边或者在这些较 优路径附近进行相关的探索性改善。 为了防止信息的无限制积累，一般信息素更新的第一步是对每一条边进行信 息素的挥发，挥发表达式如下： 白卜( 1 一p ) r 扩，v ( i ，) 厶 ( 2 6 ) 1 6 中山大学硕士学位论文 其中p 表示信息素挥发率，且0 p l ，一般设置为o 1 或者更小。这样做主要 是为了下一轮的搜索总能够依据当前最新的信息，而不是很久所探索的信息，或 者说这种做法使得蚂蚁能够“忘记”以前的较优路径，防止无限的积累。 第二步就是对每一只蚂蚁所走过的路径进行一次信息素的增加过程，其增 加的量一般依据该蚂蚁k 所做过路径r 的总长度c ，更新式可如下所示， 乃卜勺+ 缸；，v ( i ，) l ， ( 2 - 7 ) k = i 其中峰，i f 酬“芝， 当完成信息素的更新，就进入下一轮的路径构建。 ( 2 8 ) 图2 - 6 a s 算法基本流程 蚂蚁系统的基本框架可如上所述，整体而言该算法具有如下几个显著特点： 中山人学硕j ：学位论文 l 算法具有广泛的实用性：这种算法模式可以很容易的应用到其它组合优化问 题中。 2 分布式计算：a s 让所有的蚂蚁从不同的城市出发来增加搜索的广度，以避免 过早收敛。 3 以群体( p o p u l a t i o n ) 为基的方法：群体中的每一只蚂蚁都有记忆功能，同时也 是解的进一步构建者。 4 正反馈：正反馈是一种良好的自我学习的机制，也成为自催化行为。这种机 制使得较多蚂蚁所选择的路径会自动吸引更多的蚂蚁进行探索。 下一将简要介绍e a s 以及a s m n k ： e a s 及a s n n k 作为候选版本的e a s 以及a s m k ，算法的求解效果在一定程度上要优于a s 。 其所作的改进主要在于为了更加凸显目前所搜索到的较优路径的重要性， e a s 算法中加入了一个对至今最优路径产的额外强化，其强化主要是通过 向产所经过的每一条边增加一个大小为e c 如的信息素量，其中e 表示一个参 数，定义了路径产的权值大小，产表示了路径产的长度。此时，信息素更新 规则的表达式( 2 6 ) 和( 2 7 ) 可变成： 勺 - - - t 扩+ 缸；+ 以f 笋，v ( i ，) 三 ( 2 9 ) 其中，f ；的定义和式( 2 - 8 ) 相同，f 笋的定义如下： 孝： “矿，讧a r c ，j ) b e l o n g st o 产；( 2 - 1 0 )” 10 ，o t h e r w i s e ； 和e a s 不同的是，a s m n l ( 会选择排名前w 只蚂蚁进行信息素更新，而不仅 仅是最好的蚂蚁，且每一只蚂蚁更新的信息量也不同，排名越靠前的蚂蚁往往更 新的信息量最多，排名越靠后则更新越少。信息量的更新式如( 2 - 1 1 ) 所示 f 卜勺+ ( w - r ) a r ；+ w f 笋，v ( i ，) l ( 2 1 1 ) r ：= l c 7 ，i f m e ，一豁眦t a l ( e sr o m e ( ( 2 - 1 2 ) 9 l0 o t h e r w i s e 其中c7 表示排名第，的蚂蚁的路径长度，r 的定义和式( 2 1 0 ) 相同。由于a s 髓n k 1 8 中山大学硕士学位论文 往往能够得到更多的正信息反馈，在理论上能够达到更好的求解效果。在 b u l l n h e i m e r 等人 2 5 ( 1 9 9 9 ) 的实验中也证明了这一点。 关于a s 的核心流程可如图2 - 6 所示，从中可以看出，算法主要就是包括上 述的三个个过程，信息素的初始化、路径的构建以及信息素值的更新。这种简单 的模式为算法的扩展改进以及应用提供了良好的基础。 蚁群系统( a n tc o l o n ys y s t e m