（基础数学专业论文）结余分配策略蚁群算法.pdf

a n t c o l o n ya l g o r i t h m w i t hs u r p l u sa s s i g nm e n ts t r a t e g y b yl i ud a o s u p e r v i s o r ：v i c e p r o f e s s o rz h a n g w e i n o r t h e a s t e r nu n i v e r s i t y n o v e m b e r2 0 0 7 0780 4 舢8 iii-啪y j，1ii 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的 说明并表示谢意 学位论文作者签名： 胡也 日期：渊、i 、，口 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流 学位论文作者签名：纠堕 日 期：勘硼、j 、j9 另外，如作者和导师不同意网上交流，请在下方签名；否则视为 同意 学位论文作者签名：导师签名： 签字目期：签字日期： 东北大学硕士学位论文摘要 结余分配策略蚁群算法 摘要 a n ts y s t e m ( a s ) 算法和m a x m i na n ts y s t e m ( m m a s ) 算法是蚁群算法的两种算 法模型，它们都包含信息量更新准则在更新信息量时，a s 算法通常使用a n t c y c l e 模型对信息量进行更新，而m m a s 算法则用限制最大最小信息量的方式对信息量 进行更新两种算法在实际中有广泛的应用 结合a s 算法和m m a s 算法更新方式，并考虑到a n t c y c l e 模型采取的是“平 均”原则更新信息量，即对同一条路径上的各弧段( 无论弧段优劣) 一律补充等量的 信息量；m m a s 算法采取的是“一刀切 标准更新信息量，即对信息量小于f 。或 大于f 一的弧段，一律将其信息量强制取为f 。加或r 一，两者在更新信息量时都没有 全面准确地反映弧段的优劣性这关键信息，本文提出基于弧段优劣性的按比例分 配全局更新方式，以及基于此的结余分配策略，给出了结余分配策略蚁群算法新 算法在全局更新过程中，一改“平均”原则为“比例”原则，二改“一刀切”标准 为“结余分配”策略，使得“优弧”能减少信息量，“劣弧 能补充信息量，且能充 分体现弧段的优劣性 证明了新算法依概率收敛，从理论上保证了新算法的可行性 实验仿真结果很好，与“蚁群算法实验室”所得结果以及目前公布的最好结果 比较，优于前名且很接近于后者，说明新算法有实效 关键词：蚁群算法；信息量；更新；比例；结余 j ， i ( 东北大学硕士学位论文a b s t r a c t a n tc o l o n y a l g o r i t h mw i t hs u r p l u sa s s i g n m e n ts t r a t e g y a bs t r a c t a n ts y s t e m ( a s ) a n dm a x m i na n ts y s t e m ( m m a s ) a r et w oa l g o r i t h mm o d e l so fa n t c o l o n ya l g o r i t h m b o t ho ft h e mi n c l u d ep h e r o m o n eq u a n t i t yu p d a t er u l e a sa l g o r i t h mo f t e n u s e sa n t - c y c l em o d e lt ou p d a t ep h e r o m o n eq u a n t i t i y , a n dm m a sa l g o r i t h mu s e st h ew a yo f r e s t r i c t i n gm a x i m u ma n dn l i n i m u l t lo fp h e r o m o n eq u a n t i t yt ou p d a t ei t i np r a c t i c a lp r o b l e m s ， m e y a r eu s e dw i d e l y a s a n dm m a s u p d a t er o l ea r eu n i t e di nt h i sp a p e r b e c a u s ea n t c y c l em o d e lu s e s “e q u a l p r i n c i p l e ”t ou p d a t ep h e r o m o n eq u a n t i t y , t h a ti s ，e a c ha r co f o n ef i x e dt o u r , n om a t t e ri ti sg o o do r b a d ，i ss u p p l i e de q u a la m o u n tp h e r o m o n eq u a n t i t y , a n dm a x - m i na n ts y s t e mu s e st h es t a n d a r do f o n es w o r dc u t s t ou p d a t ep h e r o m o n eq u a n t i t y , t h a ti s ，e a c ha l e sp h e r o m o n eq u a n t i t yt h a ti s b e l o wf m mo ro v e rr “，r i om a t t e ri ti sg o o do rb a d ，i so r d e r e da s f 。 o ri m a x i nt h eu p d a t e p r o c e s s ，b o t l lo ft h et w oa l g o r i t h m sd o n ts h o we a c ha r c sc h a r a c t e rw h e nt h ep h e r o m o n e q u a n t i t ya r es u p p l i e d b e c a u s eo ft h i s ，w e 晰n gf o r w a r dan e ws t r a t e g y - - s u r p l u sa s s i g n m e n t s t r a t e g y , t h e nb a s e do nt h i sn e ws t r a t e g yw eb r i n gf o r w a r dan e wa l g o r i t h m - - - a n tc o l o n y a l g o r i t h m 、j 、，i t l ls u r p l u sa s s i g n m e n ts t r a t e g y i nt h eu p d a t ep r o c e s so ft h en e wa l g o r i t h m ：f i r s t l y , “e q u a lp r i n c i p l e ”i si m p r o v e da s “p r o p o r t i o n a lp r i n c i p l e ”；s e c o n d l y , t h es t a n d a r do f o n es w o r d c u t s i si m p r o v e da s s u r p l u sa s s i g n m e n t s t r a t e g y a f t e ru s i n gt h en e wp r i n c i p l eu p d a t e p h e r o m o n eq u a n t i t y , e a c hs u p e r i o ra r c sp h e r o m o n eq u a n t i t yi sd e c r e a s e d ，a n de a c hi n f e r i o ra r c s p h e r o m o n eq u a n t i t yi ss u p p l i e d a n dm e a n w t g l e ，t h e i ro w n c h a r a c t e rc a nb ea l s os h o w e da f t e rt h e p h e r o m o n eq u a n t i t yi ss u p p l i e d w ep r o v et h en e wa l g o r i t h mi sc o n v e r g e n ti np r o b a b i l i t yi nt h i sp a p e r t h a ti s ，i ta s s u r e st h e f e a s i b i l i t yo f t h en e wa l g o r i t h m c o m p a r i n gw i t h t h el a b o r a t o r yo ft h ea n tc o l o n ya l g o r i t h m a n dt h ec u r r e n tp u b l i cb e s t r e s u l t , t h er e s u l tw h i c hw eg a i ni sb e t t e rt h a nt h ef o r m e ra n dc l o s et ot h el a t e ri ns i m u l a t i o n e x p e r i m e n t s o ，i ta s s u r e st h ee f f e c t i v e n e s so f t h en e wa l g o r i t h m k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；p h e r o m o n eq u a n t i t y ；u p d a t e ；p r o p o r t i o n ；s u r p l u sa s s i g n m e n t v 1 一 巳 东北大学硕士学位论文 目录 目录 独创性声明一i 摘要i i i a b s t r a c t v 第l 章引言1 1 1 蚁群算法产生的背景1 1 2 蚁群算法的发展历程及其在我国的发展状况2 1 3 蚁群算法的应用3 1 4 本文主要工作一5 第2 章蚁群算法一7 2 1 基本蚁群算法7 2 1 1 蚁群行为描述j 7 2 1 2 原理8 2 1 3 基本算法1 0 2 2 蚁群算法的三个算法模型1 l 2 2 1a n ts y s t e m ( a s l 1 1 2 2 2m a x m i na n ts y s t e m ( m m a s ) 12 2 。2 3a n tc o l o n ys y s t e m ( a c s ) 1 2 第3 章结余分配策略蚁群算法1 5 3 1 全局更新一1 5 3 2 算法1 7 3 3 收敛性18 第4 章仿真2 3 4 1 仿真实验2 3 4 2 结果分析：一2 5 第5 章总结2 7 参考文献一2 9 致谢3 l 附录3 3 东北大学硕士学位论文第1 章引言 第1 章引言 1 1 蚁群算法产生的背景 自古以来，自然界就是人类各种技术思想、工程原理及重大发明的源泉种类 繁多的生物界经过长期的进化过程，使它们能适应环境的变化，从而得到生存和发 展随着生产的需要和科学技术的发展，从2 0 世纪5 0 年代以来，人们已经认识到 生物系统是丌辟新技术的主要途径之一，逐渐地便把生物界作为各种技术思想、设 计原理和创造发明的源泉此时模拟生物不再是引人入胜的幻想，而成了可以做到 的事实生物学开始跨入各行各业技术革新和技术革命的行列，而且首先在自动控 制、航空、航海等军事部门取得了成功于是生物学和工程技术学科结合在一起， 互相渗透孕育出一门新生的科学仿生学 仿生算法源于仿生学，是通过模仿自然界生物的行为形成的算法它是经过数 学抽象，将生物真实的行为提炼成数学公式，并通过公式体现出各个真实行为的特 性，所形成的一种较完善的算法仿生算法主要有遗传算法、蚁群算法、微粒群算 法、人工免疫算法、人工鱼群算法、混合蛙跳算法等 蚁群算法是十几年前提出的一种仿生算法生物学家通过对蚂蚁觅食和筑巢行，。 为的长期观察发现，每只蚂蚁的智能并不高，也没有统一的指挥，但它们却能协同 工作，依靠群体智慧集中觅食，建起坚固漂亮的蚁穴 通过对真实蚁群的研究，意大利学者m d o z i g o 等人于1 9 9 1 年提出基本蚁群算 法，称为蚁群系( a n ts y s t e m ，a s ) 【l 】，并利用它在解决旅行商问题( 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 ) 、指派问题( a s s i g n m e n tp r o b l e m ，a p ) 、调度问题( s c h e d u l i n g p r o b l e m ，s p ) 等问题上得出了一系列比较好的结果由此，蚁群系统模型渐渐引起了 其他学者的注意之后，陆续出现了许多研究蚁群算法的文章，其中有关于算法模 型改进的，关于算法理论研究的，关于算法应用性的，关于蚁群算法和其它算法融 合的文章等【2 - 5 1 虽然蚁群算法发展至今还不到二十年，但是这些初步研究已显示出蚁群算法在 求解复杂优化问题，特别是离散优化问题方面的一些优越性，表明它是一种有发展 前途的方法 - 1 第l 章引言 东北大学硕士学位论文 1 2 蚁群算法的发展历程及其在我国的发展状况 自1 9 9 1 年意大利学者m d o r i g o 等人提出基本蚁群算法后的近五年时间里，算 法没有在国际学术界引起广泛关注，算法理论及其应用的研究也没有取得突破性进 展1 9 9 6 年，m d o r i g o 等人在i e e et r a n s a c t i o n s o ns y s t e m s ，m a n ，a n d c 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 a t i o nb yac o l o n yo fc o o p e r a t i n g a g e n t s 【6 】 一文在该文中，m d o r i g o 等人更加系统地阐述了蚁群算法的基本原理 和数学模型，将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等进行了仿 真实验比较，把单纯地解决对称t s p 拓展到解决非对称t s p 、指派问题以及车间作 业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) ，对算法中初始化参数对算法性能的 影响作了初步探讨这是蚁群算法发展史上的又一篇奠基性文章从目前已公开发 表的蚁群算法相关论文看，7 0 以上的论文都将这篇文章或1 9 9 1 年m d o r i g o 等人 在首届欧洲人工生命会议上发表的“d i s t r i b u t e do p t i m i z a t i o nb ya n tc o l o n i e s t l 】”一文 列为参考文献自1 9 9 6 年之后的五年时间里，蚁群算法逐渐引起了世界许多学者的 关注，其应用领域得到迅速拓宽，大量有价值的研究成果陆续发表对蚁群算法不 断高涨的研究热情，促成第一届蚁群算法国际研讨会( a n l 、s 7 9 8 ，1 9 9 8 1 0 1 5 1 6 j 比利时，布鲁塞尔) 的召开，会议由创始人m d o r i g o 负责组织第一届吸引了来自 世界各地的5 0 多位蚁群算法研究者，以后每隔两年在布鲁塞尔都要召开一次蚁群算 法国际研讨会历届会议的论文集均由著名的( ( l e c t u r en o t e si nc o m p u t e rs c i e n c e ( s c ii n d e x ) 结集出版2 0 0 0 年，m d o r i g o 和e b o n a b e a u 等人在国际顶级学术刊物 ( ( n a t u r e ) ) 上发表了蚁群算法研究综述，把这一领域的研究推向了国际学术的最前 沿鉴于m d o r i g o 在蚁群算法研究领域的杰出贡献，2 0 0 3 年1 1 月欧盟委员会特别 授予他“居里夫人杰出成就奖( m a r i ec u r i ee x c e l l e n c ea w a r d ) ” 最近几年，( ( n a t u r e ) ) 多次对蚁群算法的研究成果进行报道，( ( f u t u r eg e n e r a t i o n c o m p u t e rs y s t e m s ) ) ( v 0 1 16 ，n o 8 ) 、i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) ( v 0 1 6 ，n o 4 ) 分别于2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊如今，在国内外许多学 术期刊和会议上，蚁群算法已经成为一个备受关注的研究热点和前沿性课题 我国在蚁群算法领域的研究起步较晚，从公开发表的论文( 以投稿日期为标准) 看，国内最先研究蚁群算法的是东北大学控制仿真研究中心的张纪会博士与徐心和 东北大学硕士学位论文第1 章引言 教授【7 。8 1 ( 1 9 9 7 年l o 月) 在国内蚁群算法的众多研究者中，值得一提的是当时年仅 1 7 岁高二学生陈烨，2 0 0 1 年他在计算机工程( v 0 1 2 7 ，n o 1 2 ) 上发表了“带杂交 算子的蚁群算法【9 】”一文，并基于v i s u a lb a s i c 开发了一个功能齐全、界面友好的“蚁 群算法实验室”，引起了国内广大蚁群算法研究者的极大关注 回顾蚁群算法十多年的发展历程，目前人们对蚁群算法的研究已由当初单一的 t s p 领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态组合 优化问题，由离散域范围内研究逐渐拓展到连续域范围内研究，在蚁群算法的模型 改进及与其他仿生优化算法的融合方面也取得了相当丰富的研究成果，而且在蚁群 算法的硬件实现上也取得了突破性进展，使这种新兴的仿生优化算法展现出前所未 有的勃勃生机 1 3 蚁群算法的应用 1 自m d o r i g o 等人首次将蚁群算法应用于旅行商问题( t s p ) 以来，国内外许多学点 者在这方面又进行了大量深入的研究，将其推广到了更多领域，已取得相当丰富的 研究成果一些代表性应用( 来自文献 1 0 - 12 】) 如下： ( 1 ) 旅行商问题( t s p ) 一 旅行商问题研究的是：给定刀个城市，有一个旅行商从某一城市出发，访问各 城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径( s 0 闭合回簧 路) 具体求解时，用人工蚁群移动模仿旅行商行走，最终利用蚁群算法找出最优路 径 ( 2 ) 网络路由问题 随着i n t e r n e t 上广泛的分布式多媒体应用对服务质量( q o s ) 需求的增长，各种服 务应用对网络所能提供的q o s 提出了不同的要求，而路由是实现q o s 的关键之 一将蚁群算法用于解决受限路由问题，目前可以解决包括带宽、延时、包丢失率 和最小花费等约束条件在内的q o s 组播路由问题，比现有的链路状态路由算法具有 明显的优越性但所研究的实例相对简单，没有对更复杂的q o s 问题进行深入探讨 m gr y a n 等利用蚁群算法较好地解决了光纤网络中的波分复用动态拓扑最优 传输规划问题t i m o h a m m a d 等利用该算法很好地解决了移动自组网( m a n e t ) 最 优规划问题，但仅用1 0 只蚂蚁对1 0 个处理单元进行了仿真研究，没有对这类问题 第1 章引言 东北大学硕士学位论文 进行泛化 ( 3 ) 生产调度问题 生产调度是一个复杂的动态管理优化问题因为蚁群算法机制可以不断地从过 去的加工经历中学习，能自然地适应车间内外部环境的变化，从而能适应动态的工 件到达、不确定的加工时间以及机床故障等扰动，实现动态调度，所以蚁群算法比 静态确定性调度算法具有更好的应用前景 蚁群算法同样可求解混流装配线调度等动态任务多目标分配问题，并对车间内 外部环境变化具有良好的自适应性但这些应用研究大多是针对小规模实例的仿真， 用蚁群算法解决大规模生产调度和多目标分配问题是今后的进一步研究方向 ( 4 ) 电力系统优化问题 电力系统优化是一个复杂的系统工程，它包括无功优化、经济负荷分配、电网 优化及机组最优投入等一系列问题，其中很多是高维、非凸、非线性的优化问题侯 云鹤等将蚁群算法成功地用于解决经济负筒分配问题；王志刚等则解决了该算法在 配电网络优化规划中的初步设计问题 电力系统优化中的机组最优投入问题是寻求一个周期内各负荷水平下机组的最 优组合方式及开停机计划使运行费用最小m 题利用状态、决策及路径概念，将机 组最优投入问题设计成t s p 模式，便可利用蚁群算法求解。 ( 5 ) 机器人路径规划问题 机器人路径规划就是在障碍有界空间内找到一条从出发点到目标位置的无碰撞 且能满足一些特定要求的满意路径通常把指定的出发点假设为蚂蚁的蚁穴，目标 位置假设为要寻找的食物，则机器人路径规划问题可以转化为蚂蚁寻找食物的路径 寻优问题，利用蚁群算法便可求解 ( 6 ) 车辆路径问题( v r p ) v r p ( v e h i c l er o u t i n gp r o b l e m ) 研究的是运输问题研究在车辆载重量和各客户 点需求量确定的前提下，至少需要多少车辆才能满足需求，使车辆总行程最短的问 题目前除了一些经典的智能算法以外，采用t s p 风格的蚁群算法同样可求解v r p ， 求解时可将车辆模拟成蚂蚁 此外，蚁群算法在数据挖掘、参数辨识、图像处理、图形着色、分析化学、岩 石力学以及生命科学等领域的应用也取得很大进展 4 东北大学硕士学位论文第1 章引言 1 4 本文主要工作 蚁群算法是一种具有实际应用价值的全局优化概率搜索算法，在实际中有广泛 的应用从产生至今，无论在理论方面还是应用方面，它都受到了广泛的关注和青 睐学者们研究的一个主要方面是对算法更新方式的改进本文研究的预期，一是 改进算法的全局更新方式，二是改进算法的更新策略 本文内容将分五部分：第一部分将介绍蚁群算法的产生背景及其发展过程；第 二部分将介绍基本蚁群算法原理及蚁群算法三个代表性模型；第三部分将介绍本文 的研究成果；第四部分是对本文研究成果的仿真实验；第五部分为全文总结 0 尹；：， 东北大学硕士学位论文 第2 章蚁群算法 2 1 基本蚁群算法 2 1 1 蚁群行为描述 第2 章蚁群算法 虽然单个蚂蚁的行为比较简单，但由这样简单的个体所组成的群体却表现出极 其复杂的行为特征，能够完成复杂的任务不仅如此，蚂蚁还能够适应环境的变化， 如：在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快重新找到当时环境下长度 最短的路径( 即长度最短的轨迹) ，即最优路径蚁群是如何完成这些复杂任务的呢? 人们通过研究发现，蚂蚁个体之间通过一种称之为外激素( p h e r o m o n e ) 的物质进行信 息传递，依据信息调整自己的行为，使其逐渐与整体行为趋于一致，从而完成复杂 的任务蚁群之所以表现出复杂有序的行为，个体之间信息不问断的交流与相互协 作的意识起着重要作用蚂蚁在运动过程中，能够感知外激素这种物质的存在及其 浓度，并以此指导自己运动的方向( 蚁群倾向于朝着外激素浓度高的方向移动) ；能 够在所经过的路径上留下自己的外激素蚁群的集体行为因此表现出一种信息正反 馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大蚂蚁正 是通过这种外激素信息交流达到食物搜索目的【1 引 图2 1 可以形象地解释蚁群是如何发现从蚁穴到食物源的食物搜索最优路径 c c ba d b ( a ) 蚂蚁开始选路( b ) 蚂蚁完成选路 ( a ) a n ts t a r t st oc h o o s et o u r( b ) a n tf i n i s h sc h o o s i n gt o u r 图2 1 蚂蚁的食物搜索 f i g 2 1a n t sf o o ds e a r c h 在网络的节点a 与节点b 之间有两条支路a c b 和a d b ，如图2 1 ( a ) 所示，其中a c b 支路的长度大于a d b 支路的长度若有两只蚂蚁由节点a 向节点b 行进，在初始时刻， 由于各个支路上没有任何信息素( 即外激素) 的痕迹存在，所以这两只蚂蚁选择走哪 第2 章蚁群算法东北大学硕士学位论文 条支路的概率是相等的假设两只蚂蚁各沿着支路a c b 和a d b 向着节点b 行进，由 于蚂蚁行进的速度相同，所以在一段时间之后，当一只蚂蚁经过支路a d b 至i j 达节点 b 时，另一只蚂蚁却还在支路a c b 的途中( 如图2 1 ( b ) ) 每只蚂蚁在各支路上均留下 同样数量的信息素，但由于路径长度不同，长度短的支路上信息素浓度高，所以蚂 蚁在支路a d b 上留下的信息素浓度要高于支路a c b 上的信息素浓度此后若再有蚂 蚁从节点a 到节点b ，由于受到信息素痕迹的诱导，它们选择支路a d b 的概率就会较 大，这种选择又会不断地增加支路a d b 上的信息素浓度，形成j 下反馈作用；与此同 时，遗留在支路a c b 上的信息素浓度会因蚂蚁移动导致信息素不断地挥发而进一步 减弱这样一来，选择走支路a d b 的蚂蚁就会越来越多，选择走支路a c b 的蚂蚁就 会越来越少，最后呈现出：有较强信息素痕迹的那些支路便会形成一条从蚁穴到食 物源的最优路径1 2 , 6 】 2 1 2 原理 蚁群个体的行为包含两个认知阶段：适应阶段和协作阶段在适应阶段，各候 选解( 从起点到终点的一条路径) 根据积累的信息不断调整自身结构；在协作阶段， 候选解之间通过信息交流，以期产生性能更好的解 为能清楚地理解蚁群算法的基本原理，卜商将借助对称t s p 进行说明 ， 对称t s p ：假设c = c 。，c ：，c n ) 是由，1 个城市( 状态点) 组成的集合， l = ( f ，) iq ，c j c ) 是集合c 中元素两两连接( 通常称谓的边或弧段) 的集合， z ，( ，= 1 ，2 ，聆) 为弧段( f ，) 的e u c l i d e a n 距离，( ；= ( rl ) 是有向图对称是指任意 两城市间的往返距离相等t s p 是指从有向图g 中找出长度最短的h a m i l t o n 圈，即 对c = c 。，c ：，q ) 中玎个元素访问且只访问一次的最短封闭曲线 设删为蚁群中蚂蚁的数目，z 为组合优化问题( 即离散优化，通过数学方法去寻 找离散事件的最优编排、分组、次序或筛选等) 状态点的个数，在初始时刻各弧段信 息素浓度( 简称信息量) 相等，f 。，( f ) 为，时刻( 蚂蚁运动到第t 个状态点时所对应的时刻 称为t 时刻， ，) 弧段( f ，) 上的信息量，厂= f 。( ，) iq ，c ，c ) 是t 时刻各弧段上信息 量的集合在有向图g = ( c ，l ，厂) 上寻优的蚁群算法主要遵循三种方式( 蚂蚁的状态 转移、信息量的局部更新和信息量的全局更新) 的组合具体实现【1 - 4 1 1 状态转移 - 8 东北大学硕士学位论文第2 章蚁群算法 状态转移是指蚂蚁从当前状态点移动到下一个状态点的过程这里采用依转移 概率最大原则选择下一状态点 算法中的蚂蚁( 称为人工蚂蚁) 与实际蚂蚁不同，具有记忆功能用禁忌表 t a b u k ( k = 1 ，2 ，m ) 记录蚂蚁k 当前已走过的城市( 状态点) ，髟( f ) 表示，时刻蚂蚁k 由 城市辟专移到城市，的转移概率在搜索过程中，蚂蚁将根据各弧段的信息量和启发 信息( 为了避免耗费较长的时间，给算法加入一个初始的引导，即启发信息) 计算状 态转移概率，转移概率公式的一般形式为 学( ，) =器，靴砒w 以 f ：q ) 7 7 霎o ) 。口“”“。 0 ，否则 其中： a l l o w e d k = c - t a b u 。表示允许蚂蚁k 下一步可选择的城市集合( 状态点集) ； a 为信息启发式因子，表示轨迹的相对重要性，反映蚂蚁在运动过程中所积累 的信息量在蚂蚁运动时所起的作用，常取l 5 间的整数； 训 口为期望启发式因子，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径时的受 重视程度，常取l 5 问的整数； 仉( f ) = l i d , , 为弧段( f ，) 上的启发函数，表示f 时刻蚂蚁从状态点f 转移到状态点 ，的期望程度 蚂蚁k 由当前状态点i 转移到下一状态点，： 产a r g ，戮 嘭( f ) ) ( 2 - l 2 ) 这里a r g 邺 硭( f ) 表示s a l l o w e d k 时硭( f ) 取最大值时所对应的s 的取值 曩a l l o w e a l 、 2 局部更新 局部更新是指在两个时刻之间对各弧段上的信息量进行调整的过程 局部调整是每只蚂蚁在建立一个解( 即从起点到终点的一条路径) 的过程中进行 的经过h ( h 为r l 的正整数因子) 时刻，两个状态点之间弧段上的信息量要作调整( 即 更新) ，局部更新公式一般形式为 第2 章蚁群算法 东北大学硕士学位论文 f p ( ，+ 办) = ( 1 一妒) r ”( ，) + 妒a v p ( ，) ，t = 0 ，h ，2 h ，力一h ( 2 1 3 ) 其中： f ，( 0 ) = ， t o 为各弧段的初始信息量，通常事先设定； o ( ，) = f ：( ，) ，a r ，( ，) 表示在时刻t 与t + l 之间弧段( f ，) 上信息量的增量， k = l r ：( ，) 表示第k 只蚂蚁在时刻，与t + l 之间留在弧段( f ，) 上的信息量； 缈为信息量衰减系数，9 0 ，l 】 3 全局更新 全局更新是指当每只蚂蚁均完成对所有城市的周游后，对所产生的路径上的信 息量进行调整的过程 全局更新公式一般形式为 f ( f ，j ) = ( 1 一p ) r ( i ，) + j d a v ( i ，) ，( 2 1 4 ) 这罩z ( i ，_ ，) 表示一次周游开始前弧段( f ：) 上的信息量，f ( f ，) 表示完成一次周游后弧 段( f ，) 上的信息量其中： p 为信息量挥发系数，l j d 为信息量残留因子，p f 0 ，l 】； a r ( i ，) = a z 。( f ，) 为一次循环( 蚂蚁完成对所有城市的周游称为一次循环) 后 弧段( f ，) 上信息量的增量，a r k ( i ，) 表示第k 只蚂蚁在一次循环后留在弧段( f ，) 上 的信息量 4 终止准则 蚁群算法的终止条件一般为设定的最大循环次数m 2 1 3 基本算法 算法步骤如下： s t e p l ：各弧段信息量的初始化； s t e p 2 - 每只蚂蚁按状态转移公式( 2 1 2 ) 选择下一状态点； s t e p 3 ：每只蚂蚁在生成一次周游路径的过程中，按更新公式( 2 1 3 ) 对各弧段上 的信息量进行更新； 1 0 - 东北大学硕士学位论文第2 章蚁群算法 s t e p 4 ：蚂蚁完成一次周游后，按更新公式( 2 1 4 ) 对各弧段上的信息量进行更新； s t e p 5 ：判别终止条件若满足，则终止；否则，转到s t e p 2 2 2 蚁群算法的三个算法模型 随着研究的深入，越来越多的改进蚁群算法应运而生纵观蚁群算法整个发展 过程，有如下三个典型算法模型 2 2 1a n ts y s t e m ( a s ) a n ts y s t e m 算法足最初的蚁群算法，通常也被称为基本蚁群算法，1 9 9 1 年由意 大利学者m d o r i g o 等人提出【1 1 1 9 9 6 年，m d o r i g o 再次系统地阐述了蚁群算法的 基本原理和数学模型f 6 i 虽说当时对信息量的更新方式在概念上未象现在这样细分 为局部更新和全局更新，但事实更新就已经是现在的局部更新或全局更新算法内 容概括如下： 1 状态转移 每只蚂蚁按状态转移公式( 2 1 2 ) 选择下一状态点 ： 2 信息量更新 各弧段信息量的更新公式为( 2 1 3 ) 或( 2 1 4 ) 。 基于更新思想的不同，m d o r i g o 提出了三种不同的基本蚁群算法模型，分别是 a n t c y c l e 模型、a n t q u a n t i t y 模型及a n t d e n s i t y 模型它们的差别仅在于更新公 式中增量的计算方法不同 在a n t c y c l e 模型中， a q ( i ：摆若第职蚂蚁在本次循环中经过弧段( f 力( 2 2 1 ) ，j ，) = 厶7 一 ( 2 1 ) io ，否则 其中q 为事先设定的信息量，厶为第k 只蚂蚁在本次循环中所走路径的总长度 第七只蚂蚁在本次循环中经过弧段( f ，_ ，) 表明第k 只蚂蚁在本次循环的某时刻t 和，+ l 之间必经过弧段( f ，) ，反之亦然 在a n t - q u a n t i t y 模型中， 第2 章蚁群算法 东北大学硕士学位论文 咄) ：垮若第职蚂蚁在时批秕“之间经过弧段( f ，力 【0 ，否则 在a n t - d e n s i t y 模型中， r ：( f ) = 苌喜需七只蚂蚁在时刻，和，+ 1 之间经过弧段o a n t c y c l e 性能较好，因此通常将a n t c y c l e 模型作为蚁群算法基本更新模型 2 2 2m a x m i na n ts y s t e m ( m m a s ) m a x m i na n ts y s t e m ( m m a s ) ( t s t 讧t z l e ，h h o o s ，1 9 9 7 ) 算法是在a s 算法基础 上发展起来的蚁群算法，它与a s 算法的状态转移公式相同，但更新公式不同 m m a s 算法的更新公式【1 3 1 为 r ( f ，) = 【( 1 - p ) r ( i ，j ) + a r ( i ，川= ， ( 2 2 2 ) 这里， 撕舻亡，若本次循环最好路径经过弧即( 2 2 渤 10 ，否则 为本次循环后弧段( f ，) 上信息量的增量，k 为本次循环最好路径的长度 ia ，若z a 函数【x 】：= b ，若x 。 ，萄a l l o w e d k 0 ，否则 更新【2 1 此 合执行 为蚂蚁k 由状态点碑专移到状态点的状态转移概率； 卢为期望启发式因子； 叩( j ，) = 1 吨为弧段o ，) 上的启发函数； 口r g 卿m a x 。 r ( f ，s ) 叼卢( f ，s ) ) 誊示j 口l l o w p 吨时f ( f ，j ) 7 7 p ( f ，s ) 取最大值时所对应的 s 的取值； 孵湖m 。a 。x 。 p t ( i ，s ) 表示$ e a l l o w p 破水j - p t ( i ，s ) 取最大值时所对应的s 的取值； q 为【o ，1 上的随机数，q o ( o q o 1 ) 为参数 2 局部更新 各弧段的信息量按更新公式( 2 1 3 ) 以及下式进行更新 删= 协鬻只蚂蚁在嗽屿h 悯经过弧段u ， ( 2 2 4 ) 意义同前 3 全局更新 各弧段的信息量按更新公式( 2 1 4 ) 与( 2 2 3 ) 进行更新 1 3 - 一砖 | 以一呵生埘力一“ 詈一 ，、 = 、，o 中其 查! ! 垄兰丝主兰堡垒查箜! 主竺全坌坠簦垒坚墅簦鲞 第3 章结余分舀己策略蚁群算法 结合a s 算法和m m a s 算法的更新方式，并考虑到a s 算法利用a n t c y c l e 模 型采取的是“平均”原则更新信息量，即对同一条路径上的各弧段( 无论弧段优劣) 一律补充等量的信息量；m m a s 算法采取的是“一刀切”标准更新信息量，即对信 息量小于f 。或大于f 的弧段，一律将其信息量强制取为f 。或r 两者在更新 信息量时都没有全面准确地反映弧段的优劣性这一关键信息，我们提出基于弧段优 劣性的按比例分配的全局更新方式，以及基于此的结余分配策略，给出结余分配策 略蚁群算法，并对其收敛性进行证明 结余分配策略蚁群算法在全局更新过程中，一改“平均”原则为“比例”原则， 二改“一刀切”标准为“结余分配”策略，使得“优弧”能减少信息量，“劣弧”能 补充信息量，且能充分体现弧段的优劣性 结余分配策略蚁群算法的状态转移公式与a s 算法的相同，局部更新公式与 a c s 算法的相同 3 1 全局更新 结余分配策略蚁群算法的全局更新包括按比例分配原则进行全局更新和结余再 分配更新策略 1 比例原则 利用a n t c y c l e 模型按公式( 2 2 。1 ) 更新信息量时，蚂蚁对路径的不同弧段( 无论弧 段优劣) 所更新上去的信息量均相等，即采用“平均”原则更新信息量，由此各弧段 自身的优劣性在更新过程中完全未得到体现对此不合理之处，我们提出按“比例” 原则更新不同弧段上的信息量，把公式( 2 2 1 ) 改进为 瓴似胪 誓 罢， 若第七只蚂蚁在本