（计算机软件与理论专业论文）蚁群算法在物流系统中的应用研究.pdf

摘要 摘要 人们生活的现代社会是由计算机信息网络、电话通信网络、物流分派网络、 运输服务网络等等各种网络组成的一个复杂的网络系统。 随着研究对象的日益复杂化，一些传统的基于精确模型的确定性优化算法在 解决具体问题时都遇到了极大的困难，一些学者从生物的生活习性中受到启发， 提出了许多仿生类启发式智能优化算法。蚁群优化算法a c o ( a n tc o l o n y o p t i m i z a t i o n ) 则是其中一种，特别适合于解决一些组合优化问题。该算法由 d o r i g o 等人于2 0 世纪9 0 年代初提出以来，至今已引起越来越多人们的注意而发 展出许多后续对其改进的算法，并且在很多领域得到了广泛的应用。 由于蚁群优化算法是模拟蚂蚁觅食的习性，采用的是分布式并行计算机制， 具有较强的鲁棒性并易与其他方法结合的特点，但也和其他进化算法一样存在计 算量大、搜索时间长、易陷入局部最优的突出缺陷，针对算法的固有缺陷，后续 很多学者对蚁群算法进行了改进。本文对蚁群算法及其在物流系统优化中的应用 进行了研究，其主要研究内容如下： 在物流系统优化两类难题中，提出用蚁群算法来求解配送中心选址的实际问 题，针对该类组合优化问题，设计了一个改进算法，充分利用蚁群算法的并行机 制和正反馈机制，引入局部更新规则增强正反馈作用，加快搜索速度，在全局更 新中增加本轮最优路径上信息浓度，并在迭代后期引入动态平滑信息素轨迹机 制，增大那些低信息轨迹被选择的概率，增强算法的搜索能力，通过对实例问题 的求解，验证了改进算法的有效性，找到了最优解组合。针对第二类问题的t s p 模型实质和蚁群算法在解决该类问题中的固有不足，本文提出了一种具有奖罚机 制的分组蚁群算法。即对蚂蚁进行分组，利用蚂蚁组之问合作和组内蚂蚁相遇合 作思想，采用全局与局部更新规则和改进m m a s 策略，并引入奖罚机制对信息 素进行更新。仿真实验数据表明改进后的算法避免了算法停滞而陷入局部最优的 现象，加快了搜索速度，找到的解也较优，取得了算法时间和优化性能之间的平 衡，提高了算法的性能。 在物流系统供应链网络优化中出现的需寻求最优斯点或其组合来构造斯坦 纳最短树的问题，传统的算法难以解决此类n p 难题，本文探讨了蚁群算法的求 解方法，用改进后蚁群算法结合m s t 算法的模式来解决，实例验证它是有效的。 关键词：蚁群优化算法奖罚机制分组蚁群t s p 物流系统优化斯坦纳树 a b s t r a c t a b s t r a c t t h em o d e ms o c i e t yp e o p l el i v e di sc o m p o s e dw i t hm a n yc o m p l e xn e t w o r k s y s t e m s ，s u c ha st h ec o m p u t e ri n f o r m a t i o nn e t w o r k ，t e l e p h o n e c o m m u n i c a t i o n n e t w o r k ，a n de n e r g y , a s s i g nn e t w o r k ，t r a n s p o r ts e r v i c en e t w o r k a st h er e s e a r c ho b j e c tb e c o m i n gc o m p l i c a t e dg r a d u a l l y ，s o m et r a d i t i o n a l c e r t a i no p t i m a la l g o r i t h mb a s e do ne x a c tm o d e lh a de n c o u n t e r e dd i f f i c u l t yi n r e s o l v i n gs p e c i f i cp r o b l e m s ，p e o p l ea r ee n l i g h t e n e db yb i o l o g ye v o l u t i o na n db i o n i c s ， a n dp u t t i n gf o r w a r dal o to fh e u r i s t i ci n t e l l i g e n c eo p t i m i z a t i o na l g o r i t h m a c o ( a n t c o l o n yo p t i m i z a t i o n ) i so n eo ft h e m ；i ti sv e r ys u i t a b l e t or e s o l v et h ec o m p o u n d o p t i m i z a t i o np r o b l e m s t h ea l g o r i t h mw a sp r e s e n t e db yd o r i g oa n do t h e r si nt h e e a r l yl 9 9 0 m o r ea n dm o r ep e o p l ep a i da t t e n t i o nt oi ta n dg a v eo u tm a n yi m p r o v e d a l g o r i t h m ，a n dm a n yo ft h e mw e r ea p p l i e dt os o m e f i e l d ss u c c e s s f u l l y a st h ea c oa l g o r i t h mi ss i m u l a t i n gt h ew a yt h a ta n t sl o o kf o rf o o d ，i ta d o p t e da p a r a l l e lc o m p u t a t i o nm e c h a n i s ma n dh a ss t r o n gr o b u s t n e s sa n di se a s yt o c o m b i n e w i t ho t h e rm e t h o d s ，b u ti t ss e a r c h i n gs p e e di ss l o ww i t hm u c hc o m p u t a t i o na n di ti s e a s yt of a l li n t ot h el o c a lb e s tr e s u l t sa so t h e re v o l u t i o n a r ya l g o r i t h m b e c a u s eo ft h e d e f i c i e n c y , m a n ys c h o l a r sh a dp r e s e n t e dal o to fi m p r o v e m e n t sf o rb a s i ca c o i n t h i sd i s s e r t a t i o n ，i m p r o v e m e n t ，a p p l i c a t i o ni n l o g i s t i c ss y s t e mo p t i m i z a t i o n a n d s i m u l a t es t u d y i n go fa c oa r er e s e a r c h e dm a i n l y , t h em a i nc o n t e n ts t u d y i n gi n t h i s a r t i c l ea r ea sf o l l o w s ： r nt h ed i s t r i b u t ec e n t e rs e l e c t i n gp r o b l e mo fm a t e r i a ld i s p a t c hi nt w ol o g i s t i c s o p t i m i z a t i o np r o b l e m s ，a ni m p r o v e da c oa l g o r i t h mi sp r e s e n t e d t om a k eg o o du s e o fi t sp a r a l l e la n dp o s i t i v ef e e d b a c km e c h a n i s m ，t ob r i n gi nt h el o c a lr e n e w r e g u l a t i o nt oe n f o r c et h ep o s i t i v ef e e d b a c km e c h a n i s ma st oi m p r o v es e a r c hs p e e d ， i n c r e a s i n gt h ep h e r o m o n eo nt h el o c a lo p t i m a lr o u t eo fal o o pi nt h eg l o b a lr e n e w r e g u l a t i o n ，i nt h el a s th a l fl o o p s ，t h es t r a t e g yo fp h e r o m o n et r a i ls m o o t h i n gi s c a r r i e do u t ，w h i c hc a ne n h a n c et h ep r o b a b i l i t yt h a ta n t ss e l e c tt h et r a i lw i t hl e s s p h e r o m o n e ，a n dc a ni n c r e a s ea l g o r i t h m ss e a r c ha b i l i t y s i m u l a t i o n r e s u l t so ft h e e x a m p l ed e m o n s t r a t e dt h ee f f e c t i v e n e s so ft h i si m p r o v e da l g o r i t h mt os o l v et h e c o m p o u n do p t i m i z a t i o np r o b l e mi np r a c t i c a la p p l i c a t i o np r o b l e m s b e c a u s eo ft h e t s pm o d e lo ft h es e c o n dl o g i s t i c so p t i m i z a t i o np r o b l e ma n dt h ed e f i c i e n c yo fb a s i c u 一 ： 垒堕! 型一 a c o ，ag r o u p e da c oa l g o r i t h mw i t ha w a r d & p e n a l t ys t r a t e g y i sp r e s e n t e dt o i m p r o v et h ea c oa l g o r i t h m ，g r o u p i n g t h ea n t sa n dt a k i n ga d v a n t a g eo ft h e c o o p e r m i o nb e t w e e na n di n s i d et h eg r o u p e da n t s ，a d o p t i n gt h eg l o b a la n dl o c a l r e n e wr e g u l m i o n r e n e w i n gt h ep h e r o m o n ew i t ha w a r d & p e n a l t ys t r a t e g ya n d i m p r o v e dm m a ss t r a t e g y t h ed a t ao fs i m u l a t i o ns h o wt h a ti ta v o i ds t o p p i n ga n d f a l l i n gt ot h el o c a lb e s tr e s u l t s a l s o ，i tg e t st h e b a l a n c eb e t w e e nt h er e s u l t sa n d s e a r c h i n gs p e e d t h ep r o b l e mt h a ti st of i n dt h eo p t i m a ls t e i n e rp o s i t i o n ( s ) t os t r u c tt h es t e i n e r s h o r t e s tt r e ei nl o g i s t i c ss y s t e ms u p p l yc h a i n sn e t w o r ko p t i m i z a t i o n ，w h i c hi sh a r d l y r e s o l v e db yt r a d i t i o n a la l g o r i t h m sf o rt h e s en o n - d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m s ( n p ) a ni m p r o v e da c oa l g o r i t h mw i t hm s ta l g o r i t h mt os o l v et h ep r a c t i c a l a p p l i c a t i o ni ss t u d i e d t h ee x p e r i m e n t a lr e s u l t sf o re x a m p l e sa r ep r o v e d t ob ev a l i d k e yw o r d s ：a c o ( a n tc o l o n yo p t i m i z a t i o n ) ；a w a r d & p e n a l t ys t r a t e g y ；g r o u p e d a n t s ；t s p ；l o g i s t i c ss y s t e mo p t i m i z a t i o n ；s t e i n e r t r e e i i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得直昌太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名( 手写) ：皂达 签字日期：砂矽7 年。月汐日 学位论文版权使用授权书 本学位论文作者完全了解南昌大学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权南昌大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授权中 国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名( 手写) ：导师签名( 手写) ： 闷洲 签字日期：沙多年k 月日签字日期：沙年f2 - 月跏日 第1 章引言 1 1 选题研究背景及意义 1 1 1 选题背景 第1 章引言 人们生活的现代社会是一个由计算机信息网络、电话通信网络、能源和物 流分派网络、运输服务网络等各种网络组成的复杂网络系统。 优化是一个重要的数学分支，同时也是一门应用相当广泛的学科，目的是 对于给出的实际问题，从众多方案中选择出最优方案【1 l 。在最近的二、三十年 中，伴随着计算机技术的高速发展和优化计算方法的进步，各种优化问题的理 论研究发展迅速，新方法不断出现，优化问题在各行各业中的地位越来越重要， 而实际优化问题也更复杂。 研究群居性昆虫行为特性的科学家发现【2 】，昆虫在群落一级上的合作基本 上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决复 杂的问题，这种由群居性生物产生出来的一种集体行为，即产生的群集智能引 起了包括计算机科学家在内的众多研究人员的兴趣，随即提出了大量启发式仿 生类进化算法。 蚁群算法就是利用群集智能解决优化问题的典型例子【3 j 。2 0 世纪9 0 年代初 期，意大利学者d o r i g om a c r o 等从生物进化论中受到启发，通过模拟自然界中 蚂蚁集体寻优的行为而提出了蚁群优化算法 4 1 ( a n tc o l o n yo p t i m i z a t i o n , a c o ) 。 它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式 搜索算法之后的一种新型的基于种群的启发式仿生类进化算法，特别适合求解 规模较大的或问题状态随时间变化的组合优化问题，如著名的t r a v e l i n g s a l e s m a np r o b l e m ( t s p ) ，很多其他问题都可直接或间接地转化为t s p 最短路问 题上来。因此研究t s p 具有重要的意义，但它却是一个n p 问题，一些传统的 算法在时间和性能上难以很好地解决，初步的研究结果已显示出该算法在求解 复杂优化问题( 特别是离散优化问题) 方面的优越性。虽然蚁群优化算法的严 格理论基础尚未奠定，国内外有关研究仍停留在实验探索的阶段，但从当前的 应用效果来看，这种模仿自然界生物习性的新型寻优思想无疑表明它具有十分 第1 章引言 光明的应用前景。 复杂的社会系统使得生活中许多问题都具有需要进行组合优化的自然特 性，例如：t s p 中如何安排所走城市的顺序，物流配送中如何确定需求点和中 心仓库的位置，物流系统中如何引导车辆寻路等等【5 】。复杂性理论指出，在这 些应用下隐藏的组合优化问题通常都是n p 问题。实践经验也表明，现实世界 中这些问题的实例规模使得在可接受的时间内不可能完成精确的求解，因此人 们在努力研究如何去寻求问题的较优解。 蚁群算法从其实现的机理来看是一种天然的解决组合优化问题的方法。其 主要的特征是正反馈、分布计算以及结构性的贪心启发机制。j 下反馈使得它能 很快搜索到比较好的解；分布计算避免了算法陷入局部收敛而不能继续优化； 而贪心启发机制使它能在寻优的早期阶段就搜索到可接受的解。这些特征使得 蚁群算法成为解决n p 一完全组合优化问题的有力工具。 尽管蚁群算法具有解决n p 组合优化问题的优势，但它也和其他启发式进 化算法一样具有计算量大、搜索时间长、易于陷入局部最优出现运算停滞问题 的固有不足。也尽管国内外的诸多学者对蚁群算法进行了改进研究，但仍有许 多问题还有待解决，怎样利用蚁群算法更有效地解决实际应用问题是本课题的 主要研究内容之一。 本课题是对蚁群算法进行了深入研究，包括算法理论优化机制、模型、算 法的复杂度、算法性能指标。鉴于蚁群算法的优势，将蚁群算法应用在了物流 系统优化问题中，对物流系统优化问题中出现的选址和路径寻优两大类问题进 行了分析和研究，给出了蚁群算法的求解应用。应用中针对于算法的固有不足， 提出了一种具有奖罚机制的分组蚁群算法，在算法中采用了分组蚁群合作的思 想，对蚂蚁路径进行奖罚的机制，确定性与随机性集合的概率选择方法，局部 和全局更新策略等来提高算法的性能。对物流系统供应链网络中出现的需要寻 求最优斯点或其组合来构造斯坦纳最短树的问题进行分析研究之后，也给出了 改进蚁群算法结合m s t 算法的求解方法和模式。 1 1 2 研究意义 组合优化问题，一类是静态组合优化问题，另一类则是动态组合优化问题。 静态问题指一次性给出问题的特征，并且在解决问题的过程中，问题的特征不 会再改变。这类问题的范例就是经典t s p 问题；动态问题则是被定义为一些量 2 第l 章引言 的函数，这些量的值由隐含系统动态地设置1 6 , 2 7 】。因此，问题在运行时间内是变 化的，而优化算法须在线适应不断变化的环境。这类问题的典型例子是路由问 题。 基于t s p 问题的经典性和实用性，以及其思想上一定的通用性，其思想在 不同领域都具有非常广泛地应用，因此对它进行研究不论在理论思想上还是在 应用程度上都具有十分重要的意义。 对物流系统优化难题中的配送中心选址问题，其目标是在一定的约束条件 下，求得目标模型函数的最优解和o 1 选择。由于蚁群算法不依赖于梯度信息， 而是可以直接利用信息素这一启发因子来寻找全局最优点这一特征，特别适合 解决这类离散组合优化问题，本文对基本蚁群算法改进后来求解该类问题，扩 大蚁群算法的应用领域。 对物流系统中的第二类路径寻优问题，问题的实质为t s p ，该类问题有很 多求解方法和算法，问题不在于能否求解，而是各求解方法或算法的性能问题。 针对蚁群算法在求解该类问题中的固有不足，提出了一种具有奖罚机制的分组 改进的蚁群算法来克服基本蚁群算法的固有不足，取得算法时问和优化性能之 间的平衡，提高了算法的总体性能。 对物流系统供应链网络优化实际问题中存在的最小生成树问题，进行抽象 后即为图论中的斯坦纳最短树问题，设计用蚁群算法来寻求斯点或斯点组合来 构造斯坦纳最短树，具有一定的理论研究价值，另一方面也为求解斯坦纳最短 树问题提供了一种可行的方法。 1 2 蚁群算法国内外研究与发展 自1 9 9 1 年意大利学者d o r i g om 等人提出蚁群算法，在其后的近5 年时间 里，在国际学术界并没有引起广泛地关注【7 母j 。直到1 9 9 6 年，d o r i g om 等在( ( i e e e t r a n s a c t i o n so ns y s t e m ，m a n ，a n dc y b e r n e t i c s p a r tb 上发表了“a n ts y s t e m ： o p t i m i z m i o nb yac o l o n yo f c o o p e r m i n ga g e n t s ”一文，文中d o r i g om 等不仅更加 系统地阐述了蚁群算法的基本原理和数学模型，将其与遗传算法、禁忌搜索算 法、模拟退火算法等进行了比较，且初步探讨了初始化参数对算法性能的影响。 此后5 年时间里，蚁群算法逐渐引起了世界许多国家研究者的关注，应用领域 得到迅速拓展，大量研究成果陆续发表。 1 9 9 8 年1 0 月1 5 、1 6 日，由创始人d o r i g om 负责组织，在比利时布鲁塞 3 第1 章引言 尔召丌了第一届蚁群算法国际研讨会( a n t 9 8 ) ，首届会议就吸引了世界各地 5 0 多位蚁群算法的研究者，随后每隔2 年都在布鲁塞尔召丌一次国际研讨会。 2 0 0 0 年，d o r i g om 和b o n a b e a ue 等在国际顶级学术刊物( ( n a t u r e ) ) 上发表了蚁 群算法的研究综述，从而把这_ 领域的研究推向了国际学术的最前沿，蚁群算 法已经成为了一个备受关注的研究热点和前沿性课题。 鉴于基本蚁群算法的不足之处，国内外学者进行了大量的研究和改进工作， 共同的目的就是在合理的时间复杂度下，尽可能克服基本蚁群算法的固有不足， 提高算法的性能，并拓宽蚁群算法的应用领域。 1 2 1 蚁群算法国外研究状况 在c o l o m i 最早的的两篇关于蚁群优化a c o 的出版物中【1 0 , 1 1 l ，第一篇介绍 了a c o 并描述了其中的3 种a c o 模型( 蚁周模型、蚁密模型和蚁量模型) ， 在用于解决3 0 个城市和很好解决5 0 个和7 5 个城市t s p 中，蚁周模型是作为 最优的算法。第二篇为蚁周模型考查了参数设置、经验计算复杂性和t s p 结果 质量的分析。 d o r i g o 随后对t s p 给出了更全面的阐述，除了之前的介绍，还将蚁周算法 与禁忌表搜索( t s ) 和模拟退火( s a ) 算法进行了比较。同时还将a c o 用于了 非对称t s p 、二次指派问题和车间调度等其他问题【1 2 l 。 t h o m a ss t t l t z l e 和h o l g e rh h o o s 提出了一种改进算法m m a s 系统【b j 。 其思想是针对算法可能出现停滞现象，采取将各路径上信息量限制在【tm i n t m 舣】，并在蚂蚁完成周游后，只对最优解路径上信息更新，达到加快收敛的目的。 ，d o r i g o 和g a m b a r d e l l a 。为7 f s p 和非对称t s p 建立了蚁群算法1 5 】。算法结 合了详尽的搜索和蚂蚁路径选择机制，强调蚂蚁对最好解的关注度。在许多非 对称t s p 问题中获得了最好的解。 1 2 2 蚁群算法国内研究状况 我国在蚁群算法领域的研究起步较晚，从公开发表的论文看，国内最先研 究蚁群算法的是东北大学控制仿真研究中心的张记会博士与徐心和教授( 1 9 9 7 年1 0 月) 。 王颖等提出一种自适应的蚁群算法以克服蚁群算法的固有缺陷【l 酬。通过自 适应地改变算法的挥发度等系数，算法可以在保证收敛速度的条件下提高解的 4 第1 章引言 全局性，通过对t s p 问题的仿真证明该算法相对与原始的蚁群算法收敛速度和 解的性能都有一定的提高。 陈烨将遗传算法中的杂交算子引入蚁群算i ：去【1 7 】，很好地解决了蚁群算法搜 索速度慢，易陷入局部最优的缺陷，并使求得问题的解更加优良，用改进算法 求解t s p 的结果表明其改进算法是有效的。 郝晋等提出一种随机扰动的蚁群算法【1 8 】，探讨了算法中参数选择范围问题， 采用倒指数曲线来描述扰动因子，并设计了相应随机选择策略和扰动策略。实 验表明它可以有效地克服基本蚁群算法的固有不足，具有更好的全局搜索能力。 吴庆洪等提出的具有变异特征的蚁群算法【1 9 】，将变异机制引入到算法中， 并充分利用了2 交换法的简洁高效特点，加快了算法的收敛速度，仿真结果表 明它在克服基本蚁群算法的固有缺陷上是行之有效的。 陈峻、沈洁等提出用蚁群算法来求解连续空间的优化问题【2 0 1 。将解空间划 分成若干子域，算法的每次迭代中根据信息量来求出解所在的子域，然后在子 域内已有解中确定解的具体值。实例计算表明该算法比遗传算法和模拟退火算 法具有更好的收敛速度。 1 2 3 蚂蚁系统及其发展 1 ) 蚂蚁系统 蚂蚁系统a s ( a n ts y s t e m ) ，也就是第一个蚁群优化( a c o ) 算法【2 卜2 3 1 ，是 最早的随着蚁群这个概念提出来的算法，它是m d o r i g o 、a c o l o m i 、v m a n i e z z o 在意大利的米兰理工学院合作研究组合优化问题的计算机智能解决方法时的研 究成果，它首先被成功地运用于t s p 问题，随后v m a n i e z z o 、a c o l o m i 把a s 算法用于解决二次分配问题( q a p ) 。虽然与己经发展完备的一些算法( 如g a 等) 比较起来，a s 算法计算量比较大，最初的效果也并不理想，但是后续的研 究将蚁群算法和局部搜索以及其它的一些优化方法相结合来获得更好的算法性 能，它的成功运用还是激起了人们对蚁群算法的极大兴趣，并吸引了一批研究 人员从事蚁群算法的研究。 a s 算法有两个主要的步骤，即蚂蚁构建问题的解和信息素的更新。对于 a s 来说，一种好的初始化信息素的启发方法，就是把信息素的初始值设为略高 于每一次迭代中蚂蚁释放的信息素大小的期望值。因为初始值一co 太小，搜索区 域就会很快地集中到蚂蚁最初产生的有限几条路径中，将导致搜索陷入较差的 局部空间中；如果初始值to 太大，算法最初的许多轮迭代都将会被白白浪费， 5 第1 章引言 直到信息素逐渐蒸发并减少到足够小时，蚂蚁所释放的信息素才开始发挥指引 搜索偏向性的作用。 a s 算法只是单纯模拟真实蚁群的觅食行为，并没有增加额外的性能，随着 测试实例的规模不断扩大，比起其他元启发式算法，a s 算法的性能下降得十分 严重。因而大量的关于a c o 的研究工作都集中在如何改进a s 上。 2 ) 最大最小蚂蚁系统m m a s m m a s ( m a xm i na n ts y s t e m ) 1 2 4 - 2 5 1 是到目前为止解决t s p 、q a p 等问题最 好的a c o 类算法。和其他寻优算法比较起来，它仍然属于最好的解决方案之一。 其特点在于：1 ) 只对最佳( 迭代最优蚂蚁或迄今最优蚂蚁) 路径增加外激素的 浓度，即在所有蚂蚁完成一次周游后，按( 4 ) 式只对最优解的各路径上的信息素 进行更新，达到加快收敛的目的。 ti i ( t + n ) = ( 1 - p ) ti j ( t ) + ati i b e 轧，p ( 0 ，1 ) ( 4 ) 其中ti i b e n = 1 l b e s t 式( 4 ) 中，l b 。可以是全局最优路径，也可以是本轮循环中的最优路径。改 进算法中的l b 。将采用本轮循环中的最优路径。从而更好地利用了历史信息( 这 与a c s 算法的调整方案有点类似) ；2 ) 为了避免算法过早收敛于并非全局最优 的解，将各条路径可能的外激素浓度限制于 tm i n ，tm a x 】，超出这个范围的值 被强制设为tm i n 或者是rm a x ，可以有效地避免某条路径上的信息量远大于其 余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；3 ) 将 各条路径上外激素的起始浓度设为tm a x ，这样便可以更加充分地进行寻优。 从实验结果看，m m a s 算法在防止算法过早停滞及有效性方面对a s 算法有较 大的改进。 3 ) 基于排列的蚂蚁系统 由b u l l n h e i m e r 等1 2 1 i 提出的基于排列的蚂蚁系统是a c o 算法的另一个改进 版本，在该算法中，蚂蚁释放的信息素大小随着蚂蚁在排列中的先后次序逐渐 减少。也即在信息素更新之前，蚂蚁根据它们构建出来的路径长度按递增的顺 序排列，而蚂蚁将要释放的信息素大小的权值由该蚂蚁的排列顺序r 决定。如 果路径的长度相同，我们可以随意处理，比如可以按蚂蚁序号排列或其名字字 母顺序排列都可，否则就按蚂蚁路径长度递增排列。 每一次迭代中，只有排列在最前的( w - 1 ) 只蚂蚁和生成了迄今最优路径的 蚂蚁( 这只蚂蚁当然是不一定出现在算法的当前迭代蚂蚁集合中的) 才允许释 放信息素。在该次迭代中排名第r 的蚂蚁将根据1 c 。乘以权重m a x o ，w r 的 6 第1 章引言 值来更新它的信息素。其信息素更新规则为ti j = t 矿( w 一，) atr i j + wa tb 5 i j 其中tr i i = l c ，而atb s i 产l 怒b 5 。b u l l n h e i m e r 等人莳实验结果表明，基于排 列的蚂蚁系统算法的性能稍稍优于e a s ，而明显优于a c o 。 4 ) 引入知识的改进蚁群算法 正如前面所说，基本蚂蚁算法只是单纯模拟真实蚁群的觅食行为，并没有 增加额外的性能，当规模很大时性能下降得很快，往往需要对它进行改进以提 高其性能。以t s p 问题为例，通过分析t s p 问题的特点，可以看出解一定是不 含有交叉路线的一条闭合回路，也就是说，包含交叉路线的解必然不是t s p 的 最优解1 2 6 j 。 对此可进行如下改进：让蚂蚁具有这样的知识，即所选择的路径如果具有 交叉，那么该路径一定不是最优路径，并且具有识别交叉和消去交叉的能力。 改进后的算法在计算出每个蚂蚁的目标函数值后，遍历其禁忌表，如果存在交 叉，则在以交叉路径的四个节点为顶点的四边形中，选择一组对边取代交叉路 径，然后对禁忌表重新排序，以此来消除交叉路径。 该算法利用交叉识别技术对问题进行预处理，大大减轻了蚂蚁算法的工作 量，提高了算法的收敛速度，增强了系统的健壮性。 1 2 4 小结 回顾蚁群算法自创立以来十多年的发展历程【_ 7 9 】，目前人们对蚁群算法的研 究已经由当初单一的t s p 领域渗透到了多个应用领域。由解决一维静态优化问 题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连 续范围内研究，而且在蚁群算法的硬件实现上取得了突破性进展，同时在蚁群 算法的模型改进及与其他仿生优化算法的融合方面也取得了相当丰富的研究成 果，从而使这种新兴的仿生优化算法展现出前所未有的勃勃生机，并已经成为 一种完全可与遗传算法相媲美的仿生优化算法。而且还出现了蚁群算法仿生硬 件，可见这种新兴的仿生优化算法已经显示出强大的生命力和广阔的发展前景。 蚁群算法及其在网络优化中的研究状况和进展： 蚁群算法是一种智能仿生算法，其之所以优于传统算法，在于它在求解大 规模n p 问题上的成功，传统方法一般很难求解那些大规模组合优化问题，网 络优化是种组合优化问题。白蚁群算法提出以来，首次就成功应用在t s p 问 题的求解上，其优化思想得到了很好地表现。 7 第1 章引言 中国地大物博，版图东西经度和南北纬度跨越很大，以全国各省会城市为 中心的c t s p ，我国学者马良等人采用了融合局部搜索机制策略思想，对中国 1 4 4 城市的t s p 问题进行求解，结果为3 0 3 5 1 ( 最优解3 0 3 4 7 ) ，结果已相当优， 远远优于近几年公布的用模拟退火算法和遗传算法得到的结果。 以下总结了近年来蚁群算法及其在网络优化中研究应用的成果【7 】，如表1 1 所示 表1 1 总结了近年来蚁群算法及其网络优化应用中研究成果 问题名称研究者算法名称年代 d o r i g o ，m a n i e z z oa n d a s1 9 9 l t s p 问题c o l o m i ( t r a v e l i n g g a m b a r d e l l aa n dd o r i g o a n t q 1 9 9 5 s a l e s m a n d o r i g oa n dg a m b a r d e l l aa c s ；a c s - 3 o p t 1 9 9 6 p r o b l e m ，t s p ) s t u t z l ea n dh o o sm m a s1 9 9 7 b u l l n h e i m e ra n dh a r t l a s r a n k1 9 9 7 马良中国1 4 4 城市t s p 1 9 9 9 指派问题 m a n i e z z o ，c o l o m i ，d o r i g o a s - q a p , a n t s q a e a s - q a p 9 4 ，9 8 9 9 ( q u a d r a t i c g a m b a r d e l l a ，t a i l l a r d ，d o r i g o h a s q a p b 1 9 9 7 a s s i g n m e n t s t i z l ea n dh o o s m m a s - q a p 1 9 9 7 p r o b l e m ，q a p )r a m a l h i n h o ，l o u r e n c o ，s e r r a m m a s g a p1 9 9 8 t a l b i ，r o u x ，f o n l u p t ，r o b i l l a r d p a c2 0 0 l 调度问题 c o l o m i ，d o r i g o ，m a n i e z z o a s j s p1 9 9 4 ( s c h e d u l i n g s t i z l ea s f s p 1 9 9 7 p r o b l e m ，s p ) d e n b e s t e n ，d o r i g o ，m a n i e z z o a c s s m t w t p1 9 9 9 b a u e re ta la c s - s m t t p 1 9 9 9 b u l l n h e i m e r , h a r t l ，s t r a u s s a s v r p1 9 9 7 s c h o o n d e r w o e r d a b c 1 9 9 6 b o n a b e a u ，v a nd e rp u te ta l ab c s m a r t ，a b c - b a c k w a r d 1 9 9 8 w h i t e ，p a g u r e k ，o p p a c h e r a s g a1 9 9 8 路由问题( r o u t i n gd ic a r o ，d o r i g oa n t n e t f a ，a n t n e t f s 1 9 9 7 1 9 9 8 p r o b l e m ，r p ) s u b r a m a n i a n ，d r u s c h e l ，c h e nr e g u l a ra n t s 1 9 9 7 h e u s s ee ta lc a f 1 9 9 8 n a v a r r ov a r e l a ，s i n c l a i ra c 0 v w p1 9 9 9 8 第1 章引言 g a m b a r d e l l a , t a i l l a r d ，a g a z z i h a s v r p1 9 9 9 李生红，刘泽民，周正v c 路由选择 2 0 0 0 张素兵，刘泽民分布式多播路由 2 0 0 1 c o s t aa n dh e r t za n t c o l1 9 9 7 g a m b a r d e l l a , d o r i g o h a s s o p1 9 9 7 l e g u i z a m o n ，m i c h a l e w i c z a s m k p1 9 9 9 其他问题 m i c h e l ，m i d d e n d o r f a s s c s1 9 9 8 马良，蒋馥度限制最小树( d c m s t ) 1 9 9 9 l i a n g ，s m i t h a c o r a p1 9 9 9 马良，王龙德背包问题蚂蚁算法2 0 0 l 1 3 论文的主要工作与组织结构 本文首先分析了当今我们生活的现代社会网络，它是一个由各种网络组成 的复杂网络系统，正由于其复杂性，其中往往存在着组合优化问题，而优化又 是一个重要的数学分支，复杂性理论指出：这些组合优化应用问题通常都是一 些n p 难题，进而介绍了适合于求解该类问题的蚁群算法。论文分析了基本蚁 群算法的原理，算法的数学模型，介绍了蚁群算法的国内外研究和发展、典型 应用以及其他一些主要的元启发式算法，阐述了蚁群算法的一些优势。鉴于蚁 群算法的优势，本文将该算法应用在了物流系统优化问题中来解决两大类难题， 即选址问题和路径寻优问题。在路径寻优问题中，提出了一种具有奖罚机制的 分组蚁群算法，将改进后的算法用于求解t s p 类的实际问题，提高了算法的性 能。对物流系统优化中寻求斯点或斯点组合构造斯坦纳最短树的问题，也设计 了相应的蚁群算法求解模式。论文组织结构和具体章节内容安排如下： 第一章引言分析了课题的研究背景和意义，介绍了蚁群算法国内外的研究 和发展，并总结了近年来蚁群算法在网络优化中的一些典型应用。 第二章则具体介绍了基本蚁群算法及其发展，包括其基本原理和数学模型， 复杂度分析和性能指标及算法存在的固有缺陷和不足，并介绍了网络图论知识 和网络优化中几种主要的启发式进化算法，根据论文需要，重点分析了论文中 要涉及到的最小生成树( m s t ) 和斯坦纳( s t e i n e r ) 树，最后总结出蚁群算法 的特点、优势及其应用。 第三章介绍了物流系统优化问题，分析了在物流配送系统中存在的两大类 9 第1 章引言 网络优化问题，针对中心选址组合难题，设计了蚁群算法的求解模式，并对一 应用实例问题进行了求解、分析和验算。由于第二类问题即为t s p ，该类问题 的实质不在于能否求解，而是在于各求解算法的性能问题。在本章后半部分， 针对基本蚁群算法在求解t s p 时的固有不足提出了改进，并将改进后的算法用 于t s p 实际问题求解中，通过仿真实验进行比较验证。 第四章分析了在物流系统供应链网络中存在的优化问题，对出现的需要寻 求最优斯点或其组合来构造斯坦纳最短树的生成树问题，给出了蚁群算法求解 方法，最后分析验算了两组实例。 第五章则是论文的一个总结，指出论文还待进一步研究的不足之处和蚁群 算法的后续展望。 1 0 第2 章蚁群算法与网络优化算法 第2 章蚁群算法与网络优化算法 2 1 基本蚁群算法( a c o ) 蚂蚁算法( a n ta l g o r i t h m 简称a a ) 2 1 , 2 7 - 2 8 1 是近年来刚刚诞生的随机优化 方法，它是一种源于大自然的新的仿生类算法。由意大利学者d o r i g o 最早提出， 蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁 群优化方法( a n tc o l o n yo p t i m i z a t i o n 简称a c o ) 。由于模拟仿真中使用了人工 蚂蚁的概念，因此亦称蚂蚁系统( a n ts y s t e m ，简称a s ) 。 蚁群算法是利用群集智能解决组合