（控制理论与控制工程专业论文）改进蚁群优化算法的研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 蚁群优化算法是由意大利学者d o r i g o 等人受到蚂蚁觅食行为的启发提 出的一种新型的智能仿生类进化算法。大量实验结果表明，它在解决许多 组合优化问题时都能表现出较好的求解能力，目前此算法已经得到了比较 广泛的应用。但是与其它仿生学进化算法相比，蚁群算法存在搜索时间长、 易陷入局部最优等缺点。本文针对蚁群算法的这些缺点，给出了3 种改进 的算法，并将其用于求解旅行商问题，主要内容如下： 1 通过对基本蚁群算法初始化参数的分析，给出了一种通过自适应改变 启发式因子口和期望启发式因子卢的蚁群算法。当算法在连续给定代数进化 后的最优解没有变化时，改进后的算法通过对启发式因子口和期望启发式因 子芦的自适应调整来提高全局最优解的求解质量。通过对t s p 问题的仿真 表明改进后的蚁群算法在求解最优解和收敛速度方面与基本蚁群算法相比 存在优势。 2 通过对基本蚁群算法初始化参数的分析，给出了一种基于信息素挥 发因子p 自适应调整的蚁群算法，当算法在连续给定代数进化后的最优解没 有变化时，改进后的算法通过对信息素挥发因子p 的自适应调整来提高全局 最优解的求解质量，并证明了该算法在迭代次数充分大时能以概率1 收敛 到全局最优解。通过对t s p 问题的仿真实验表明改进后的蚁群算法在求解 最优解和收敛速度上与基本蚁群算法相比存在优势。 3 对已有的融入遗传算法的混合蚁群算法进行改进。算法在每代进化中 保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进 行运算。对优秀解公共解集的保留加快了算法收敛速度，引入交叉和变异 扩大了解的搜索空间，提高了解的全局性。最后用m a r k o v 过程证明了当迭 代次数充分大时算法能以概率1 收敛到满意解集。通过对t s p 问题的仿真 西南交通大学硕士研究生学位论文第1 l 页 表明融入遗传算法的蚁群算法在收敛速度和解的全局性上都有较大的改 善。 最后，对全文的研究工作进行了总结，并展望了蚁群优化算法进一步 还要研究的课题。 关键词：蚁群算法；自适应；遗传算法；收敛性 西南交通大学硕士研究生学位论文第1 li 页 a b s t r a c t a n tc o l o n yo p t i m i z a t i o n ( a c o ) i san o v e la l g o r i t h mw h i c hi sp r o p o s e db y i t a l i a ns c h o l a r sd o r i g ow h o s ei n s p i r a t i o ni ss p a r k l e db y w a t c h i n ga n t ss e a r c h i n g f o rf o o d a f t e rl o t so fe x p e r i m e n t sa c 0h a se x h i b i t e di t se x c e l l e n t p e r f o r m a n c e a n d e f f i c i e n c y i n e x p e r i m e n t s f o r s o l v i n g a g r e a t l o to f c 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 ，a n dn o wi ti su s e di nm a n ya r e a s b u t c o m p a r et oo t h e rb i o n i c se v o l u t i o na l g o r i t h m sa c oh a sd i s a d v a n t a g e ss u c ha s l o n g t i m es e a r c h i n ga n dl o c a lb e s ts o l u t i o na n ds oo n t h i sp a p e ro f f e r st h r e e i m p r o v e da l g o r i t h m si no r d e rt oo v e r c o m et h e s ed i s a d v a n t a g e s ，a n dt s pc a nb c s o l v e db yu s i n gt h e s ei m p r o v e da l g o r i t h m s t h em a i nw o r k so ft h i sp a p e r i n c l u d e ： 1 an o v e la c oa l g o r i t h mw h i c hi sa ni m p r o v e da l g o r i t h mb a s e do n a d a p t i v e l ya d j u s t i n gp a r a m e t e ra ，bh a sb e e np r o p o s e d w h e nb e s ts o l u t i o nh a s n o tc h a n g e da f t e rs e v e r a lg e n e r a t i o n s ，t h en o v e la c oa l g o r i t h ma d a p t i v e l y a d j u s t st h ep a r a m e t e ra ，bt oi m p r o v et h eg l o b a la b i l i t yo ft h es o l u t i o n t h e s i m u l a t i o n sf o rt s ps h o wt h a tt h ei m p r o v e da c 0 a l g o r i t h mc a nf i n db e t t e rb e s t s o l u t i o na n dh a v eb e t t e rc o n v e r g e n c et h a nb a s i ca c o 2 an o v e la c oa l g o r i t h mw h i c hi sb a s e do n a d a p t i v e l ya d j u s t i n g p h e r o m o n ed e c a yp a r a m e t e rph a sb e e np r o p o s e d w h e nb e s ts o l u t i o nh a sn o t c h a n g e da f t e rs e v e r a lg e n e r a t i o n s ，t h en o v e la c oa l g o r i t h ma d a p t i v e l ya d j u s t s t h ep a r a m e t e rpt oi m p r o v et h eg l o b a la b i l i t yo ft h es o l u t i o na n di th a sb e e n p r o v e dt h a t f o ra s u f f i c i e n t l yl a r g en u m b e ro fi t e r a t i o n s ，t h ep r o b a b i l i t yo f f i n d i n gt h eg l o b a lb e s ts o l u t i o nt e n d st o1 t h es i m u l a t i o n sf o rt s pp r o b l e m s h o wt h a tt h ei m p r o v e da c oc a nf i n db e t t e rr o u t e st h a nb a s i ca c o 3 an o v e lh y b r i d a l g o r i t h mw h i c hi sac o m b i n a t i o no fg a ( g e n e t i c a l g o r i t h m ) a n da c oh a sb e e np r o p o s e d t h ea l g o r i t h mi m p o r t sc r o s so p e r a t o r 西南交通大学硕士研究生学位论文第1v 页 a n dm u t a t i o no p e r a t o ra f t e rr e s e r v i n gt h ei n t e r s e c t i o no ft h ef i r s tb e s ts o l u t i o n a n dt h es e c o n db e s ts o l u t i o ni ne v e r ye v o l u t i o n t h em a n i p u l a t i o no fr e s e r v i n g t h ei n t e r s e c t i o na c c e l e r a t e sc o n v e r g e n c es p e e d t h em a n i p u l a t i o no fi m p o r t i n g c r o s so p e r a t o ra n dm u t a t i o no p e r a t o rb r o a d st h es o l u t i o ns p a c ea n di m p r o v e st h e g l o b a la b i l i t yo f t h ea l g o r i t h ma n db yu s i n gm a r k o vp r o g r e s s i th a sb e e np r o v e d t h a tf o ras u f f i c i e n t l yl a r g en u m b e ro fi t e r a t i o n s ，t h ep r o b a b i l i t yo ff i n d i n gt h e s a t i s f i e ds o l u t i o n st e n d st o1 t h es i m u l a t i o n sf o rt s pp r o b l e ms h o wt h a tt h e i m p r o v e da l g o r i t h mh a sb e t t e rc o n v e r g e n c e e f f e c t i v ea n dg l o b a la b i l i t y f i n a l l y , t h ew o r k o ft h i st h e s i si ss u m m a r i z e da n dt h ep r o s p e c t i v eo ff u t u r e r e s e a r c hi sd i s c u s s e d 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 ；a d a p t i v e ；g e n e t i ca l g o r i t h m ； c o n v e r g e n c e 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇 编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密函，使用本授权书。 ( 请在以上方框内打“ ) 学位论文作者签名：列互夺 日期：z - 7 1 2 ) 箩 雀 压越 签7 腔7 老b，影2 匕日+ n 西南交通大学学位论文创新性声明 本人郑重声明 所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本 人承担。 本学位论文的主要创新点如下： ( 略) 1 对基本蚁群算法初始化参数中启发式因子和期望启发式因子进行自适应 调整； 2 对基本蚁群算法中信息素挥发因子进行自适应调整并对改进后算法的收 敛性进行分析； 3 对已有的一种蚁群遗传融合算法进行改进。 西南交通大学硕士研究生学位论文第1 页 1 1 蚁群算法的历史 第1 章绪论 蚁群算法是由意大利科学家m a r c od o f i g o 等人f 1 2 】在2 0 世纪9 0 年 代初提出来的。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工 神经网络算法等启发式搜索算法后的又一种启发式搜索算法。m a r c o d o r i g o ，vm a n i e z z o 等人在观察蚂蚁觅食习性时发现，蚂蚁总能找到巢 穴与食物之间的最短路径。这个现象引起了他们极大的兴趣。于是蚂蚁 被捉到实验室，蚂蚁的群体智能开始为人们所重视。d o r i g o 等人在实验 室中做了一系列实验，在蚂蚁已形成的最短路径上设置障碍，而当蚂蚁 在发现原来路径有障碍物后，它们会绕开这个障碍物四散的走开，但是 经过一段时间，分散的蚁群会渐渐的重新走到同一条路径上来，而这条 路径，却恰恰是添加障碍物后的从巢穴到食物源之间的最短路径。之后， d o r i g o 等人又不断的在蚁群经过的新路径上设置障碍，而惊奇的发现蚂 蚁们总能根据障碍物的位置，分散开来然后又重新聚集到当时条件下的 从巢穴到食物源的最短路径。经研究发现，蚂蚁的群体协作是通过一种 叫做外激素( p h e r o m o n e ) 的化学物质进行通信和协调的。虽然蚂蚁具有一 定的视力，但是它们却将外激素化学通信作为基本信息交流方式之一。 外激素在蚂蚁们的生活工作习性中起着至关重要的作用。d o r i g o 等人受 蚂蚁觅食行为中基于外激素的间接通信机制的启发，提出并设计了一种 蚁群算法( a n ta l g o r i t h m ) ，该算法被先后应用于t s p 问题、资源二次分 配问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ) 等经典优化问题，得到了很好的效 果。上个世纪9 0 年代后期，这种算法逐渐引起了很多研究者的注意， 他们对算法做了各种改进或应用到其他领域，取得了些令人鼓舞的成 西南交通大学硕士研究生学位论文第2 页 果。为了给算法提供一个重译的描述框架，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 ) 的算法框架【3 5 】所有符合蚁群 优化描述框架的蚂蚁算法都可称之为蚁群优化算法( a c o ) ，或简称为蚁 群算法。研究表明，蚁群优化算法在解决离散组合优化问题方面有着良 好的性能，并在多方面得到了应用。 1 2 蚁群算法的科学意义 在管理科学、计算机科学和工程技术等领域中存在着大量的组合优 化问题，对于一些复杂的组合优化问题，至今尚无很好的解决办法，人 们先后使用了禁忌搜索法算法、模拟退火算法、遗传算法、人工神经网 络等算法。这些新的智能算法的迅速发展，无论理论研究还是应用研究 都空前的活跃，而一种新的模拟进化算法蚁群算法也逐渐发展起 来，并应用到求解t s p 问题【引，车间作业调度问题【9 1 ，控制参数优化问题 1 1 们，图像处理问题【1 1 】等；同时蚁群算法还与其它进化算法结合，比如与 遗传算法结合的具有遗传特性征的蚁群算法，与神经网络融合的蚁群算 法。这些初步研究和应用已经显示出蚁群算法在求解复杂优化问题方面 的一些优越性。蚁群算法不仅能够智能搜索、全局优化，而且具有鲁棒 性、正反馈、分布式计算的特点。利用正反馈原理可以加快进化进程； 分布式计算使算法易于并行实现，个体之间不断进行信息交流和传递， 有利于发现较好解。因此，蚁群算法为诸多领域解决复杂优化问题提供 了有力的工具。这一切都证明了它是一种很有发展前景的方法。 西南交通大学硕士研究生学位论文第3 页 1 3 蚁群算法的国内外研究现状 1 9 9 6 年，d o r i g o 等在( i e e et r a n s a c t i o n so ns y s t e m ，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 f c o o p e r a t i n ga g e n t s ”一文1 3 1 ，在这篇文章中，d o r i g o 等不仅更加系统地阐 述了蚁群算法的基本原理和数学模型，还将其与遗传算法、禁忌搜索算 法、模拟退火算法、爬山算法等进行了仿真实验比较，并对蚁群算法中 初始参数对其性能的影响做了初步探讨，这是蚁群算法历史上具有奠基 性文章。自1 9 9 6 年后5 年间里，蚁群算法逐渐引起了世界许多国家研 究者的关注，其应用领域也得到了循序拓宽。在1 9 9 9 年g u t j a h r w j 撰 写的学术报告【4 l 在蚁群发展史上首次对蚁群算法的收敛性进行了证明。 进入本世纪后国际著名的项级学术刊物( n a t u r e 曾多次对蚁群算法的 研究成果进行报导【5 ，( f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s 和( i e e e t 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 分别于2 0 0 0 年和2 0 0 2 年出 版了蚁群算法特刊。如今，蚁群算法已经成为一个备受关注的研究热点 和前沿性课题。 目前蚁群算法研究学者主要集中在比利时、意大利、德国等国家， 美国和日本也在上世界末开始了对蚁群算法的研究。我国在蚁群算法领 域的研究起步较晚，国内最先研究蚁群算法的是东北大学控制仿真研究 中心的张纪会博士与徐心和教授( 1 9 9 7 年1 0 月) 1 2 】，后来在北京、上 海、东北等的学校和研究所开展了此项工作，主要是围绕t s p 及相关问 题的实验仿真。 蚁群算法已经成功的在通信、交通及人工智能等领域中应用。d o r i g o 等最初提出蚁群算法时，利用t s p 问题与觅食的相似性，运用了正反馈 原理和分布式算法，通过模仿蚂蚁行为解决了t s p 这个具有典型代表的 组合优化问题。随后他们又相继解决了二次指派问题( q u a d r a t i c 西南交通大学硕士研究生学位论文第4 页 a s s i g n m e n tp r o b l e m ，q a p ) 车间调度问题( j o bs h o ps c h e d u l i n g ，j s p ) 等， 并作了大量的实验研究。结果表明，该算法具有明显的优越性。近几年 来，d o r i g o 以及其它研究者还将蚁群算法用于解决网络路由问题 ( n e t w o r k i n gr o u t i n g ) 、机器人安排( m a c h i n gs c h e d u l i n g ) i h l 题、频率分配 问题( f r e q u e n c ya s s i g n m e n t ) 等。尤其是瑞士洛桑大学的k e l l e r 等将蚁群 算法的程序编入到微型机器人中，众多微型机器人便可以像蚂蚁一样协 同工作去完成复杂的任务。这项成果被国际著名刊物( n a t u r e 报导后， 在国际上引起了强烈的反响，以至在很多领域掀起了研究蚁群算法热 潮。 虽然蚁群算法有很多优点，但是这种新兴的算法也存在一些缺陷。 与其它仿生学进化算法相比，蚁群算法存在搜索时间长、易陷入局部最 优等缺点。针对这些缺陷，近些年来众多国内外学者在蚁群算法的改进 方面做了大量的研究工作。d o r i g o 等【1 3 】【1 4 】在基本蚁群算法的基础上提 出了一种a n t qs y s t e m 的蚁群算法。德国学者s t u z l e 和h o o sh 提出了 一种“最大最小蚂蚁系统”( m a x m i na n ts y s t e m ，m m a s ) 1 1 ”7 l 。蚁群算法 的研究工作刚刚开始，和遗传算法、神经网络算法等相比较，蚁群算法 还未形成系统的分析方法和坚实的数学基础，很多问题有待进一步研 究。 1 4 本文研究内容及成果 本文围绕蚁群算法的原理和理论进行研究，全文共分六章，各章节 内容安排如下： 第一章：绪论 本章阐述了蚁群算法产生的背景、发展历史和研究的意义，最后对 蚁群算法的国内外现状进行了介绍。 第二章：t s p 问题和蚁群算法的基本原理 西南交通大学硕士研究生学位论文第5 页 本章通过t s p 问题建立蚁群算法的数学模型并对该数学模型分析， 阐述了蚁群算法的基本原理，并对蚁群算法中各个初始参数的含义及其 对蚁群算法的影响进行了阐述，并通过t s p 问题说明蚁群算法的求解过 程。最后阐述了基本蚁群算法的缺陷及一些改进方法。 第三章：基于信息启发式因子口和期望启发式因子卢的改进蚁群算 法 本章从蚁群算法的初始参数口，户对算法的求解性能影响入手，逐 一对口，参数进行分析，给出一种自适应调整口，卢参数的改进算法。 第四章：基于自适应挥发因子p 的改进蚁群算法及其收敛性分析 本章通过对蚁群算法的初始参数挥发因子p 对蚁群算法求解性能 影响的入手，给出一种挥发因子自适应调整的改进算法，并且对改进后 的蚁群算法进行收敛性分析。 第五章：融合遗传算法的蚁群算法及其收敛性分析 本章对已有的蚁群遗传混合算法进行改进，给出了一种新的融入遗 传算法的蚁群算法，并对本章改进算法的收敛性进行分析。 第六章：结论与展望。 西南交通大学硕士研究生学位论文第6 页 第2 章t s p 问题和蚁群算法的基本原理 2 1t s p 问题简述 蚁群算法首先成功应用于t s p 问题。下面先对t s p 问题进行简单 介绍。 t s p 问题是组合优化中最著名的问题之一，它易于描述而难于求解。 自1 9 3 2 年，km e n g e r 提出t s p 问题以来，已经引起许多数学家的兴趣， 但至今尚未找到有效的求解方法。t s p 问题描述如下：给定n 个城市和每 两个城市间的距离( 或给定n 个城市和各城市的坐标，这样同样可以求 出任意两个城市间的距离) 。一个旅行商自某一个城市出发巡回售货， 旅行商应该如何选择路线，使每个城市经过一次且仅一次以完成一个回 路，并且路径最短。这个问题可以用有向图g = ( ve ) 表示，其中v 表示 丑个城市，e 表示各个城市之间的边。非负矩阵d = d i j 表示各个边的距 离。t s p 的一个解可表示为一个循环排列c - ( c l ，c 2 ，c n ) ，c i ( 1 s fs 刀) 是该路径中第i 个经过的城市，所有可行解集构成解空间s ，即 s = n 个城市的所有循环排列。其目标函数厂( c ) 。d 竹( 约定c n + l = c 1 ) 。 t s p 的目标是使路径长最小，即求目标函数f ( c ) 最小。其中 如- “一x ，) 2 + o ，j y ，) 2 对于t s p 问题，找不到一个算法能保证在多项式时间内得到最优 解。目前，对于该类问题的研究有两个方向：完全算法和近似算法。完 全算法能保证得到最优解，但是运行时间是呈指数复杂度的，因而难以 适应大规模的实例；近似算法则只要求找到近似解，而在多项式时间内结 束。在t s p 问题上的近似算法分为两类：环路构造算法和环路改进算法。 西南交通大学硕士研究生学位论文第7 页 前者从某个非法解开始，通过某种增广策略逐步改变该解，直到得到一 个合法解为止。这类算法包括最近邻算法、贪心算法等。环路改进算法 则在给定初始的合法解之后，使用某种策略来改进初始解。蚁群算法采 用的是近似算法中的环路改进算法思想。 2 2 蚁群算法的基本原理 2 2 1 蚁群行为描述 根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过 在路径上释放出一种特殊的分泌物信息素来寻找路径【毖矧。当它们 遇到一个还没有走过的路口时，就随机的挑选一条路径前行，同时释放 出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。 当后来的蚂蚁再次遇到这个路口的时候，选择信息量较大的路径的概率 相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越 大，而其它路径上的信息量却会随着时间的流逝而逐渐减小，最终整个 蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动 路径上突然出现障碍物时，蚂蚁也能很快地重新找到最优路径。可见， 在整个寻找最优路径过程中，虽然单只蚂蚁的选择能力有限，但是通过 信息素的作用使整个蚁群行为具有很强的自组织性，蚂蚁之间交换着路 径信息，最终通过蚁群的集体自催化行为找出最优路径。 2 2 2 基本蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式 引入的，该算法基于如下基本假设： ( 1 ) 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围 的局部环境做出反应，也只对其周围的局部环境产生影响。 西南交通大学硕士研究生学位论文第8 页 ( 2 ) 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物， 蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主 体。 ( 3 ) 在个体水平上，每只蚂蚁仅环境做出独立选择；在群体水平上， 单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群 体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶 段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断 调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易 被选择；反之，路经上经过的蚂蚁越少，随着时间的流逝，信息量会越 小【2 4 抛】；在协作阶段，候选解之间通过信息交流，以期望产生性能更好 的解。 2 2 3 基本蚁群算法的数学模型 蚁群算法最先用于求解t s p 问题，下面就以t s p 问题为例来说明 蚁群系统【引。设有n 个城市组成的集合c ，m 只蚂蚁，用d i j , ( i , j = l ，2 ， n ) 表示城市i 和城市j 之间的距离，t i j ( t ) 表示在时刻t 城市i 和城市j 之 间的路径上的残留信息素强度，以此来模拟实际蚂蚁的分泌物。蚂蚁 k ( k = l ，2 ，m ) 在运动过程中，根据各条路径上的信息量决定其转移方向， 同时用禁忌表t a b u k ( k = 1 ，2 ，n ) 来记录蚂蚁k 当前已经走过的城市，集合 随着t a b u k 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上 的信息量及路径的启发信息来计算状态转移概率。露o ) 表示在t 时刻蚂 蚁ke h 城市i 转移到城市j 的状态转移概率，其表达式为( 2 1 ) ： 栅岸捣商毗 弘。 io 否则 西南交通大学硕士研究生学位论文第9 页 式中，a l l o w e d k = c - - t a b u k 表示蚂蚁k 下一步允许选择的城市；口 为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中 所积累的信息在蚂蚁运动时所起的作用；夕为期望启发式因子，表示能 见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径 中的受重视程度。m ( t ) 为启发函数，其表达式为( 2 - 2 ) - ，7 o ) - 石1 ： ( 2 2 ) 为了避免残留信思素过多引起残留信息淹没启发信息，在每只蚂蚁 走完一个循环后，要对残留信息进行更新处理。其表达式为( 2 - 3 ) - o + 1 ) 一( 1 一j d ) o ) + p 。f )( 2 - 3 ) 其中( f ) 。荟噶1 0 f ) ( 2 - 4 ) 其中p 为信息素挥发系数为了防止信息的无限积累，p 的取值范围 为【o ，1 ) h o ) 表示蚂蚁k 在本次循环中在城市i 和城市j 之间的路径上 留下的信息素，其计算方法可以根据计算模型而定，在最常用的 a g t - c y c l e 模型中，o ) 的表达式为( 2 - 5 ) o ) ；l 詈，蚂蚁k 在本次循环中经过城市i 和城市j ( 2 5 ) 【0 ， 否则 其中，q 表示信息素强度，为常数，它在一定程度上影响算法的收 敛速度。k 为蚂蚁在本次循环中所走的路径的总长度。基本蚁群算法中 参数口，声，p ，q ，可以用实验的方法确定其最优组合。停止条件可以 西南交通大学硕士研究生学位论文第1 0 页 用固定进化代数或者当进化趋势不明显时便停止计算。 2 2 4 基本蚁群算法的实现步骤 s t e p l ：参数初始化，令时间t = o ，循环次数n c = 0 ，设置最大初循环 次数n c - , m a x ，设置信息素q ，将m 只蚂蚁置于n 个元素( 城市) 组成的集 合c 中，令有向图上每条边( i ，j ) 的初始化信息量t i j ( t ) = c o n s t ，且初始 时刻a t i i ( o ) = o ，其中c o n s t 为常数； s t e p 2 ：循环次数n c = n c + l ； s t e p 3 ：设置蚂蚁的禁忌表索引号k = l ； s t e p 4 ：蚂蚁数目k = k + l ； s t e p 5 ：蚂蚁个体根据状态转移公式( 2 - 1 ) 计算的概率选择元素( 城 市) j 并前进，j 忙一纪6 唯j ； s t e p 6 ：修改禁忌表指针，将蚂蚁移动到新的元素( 城市) ，并把该元 素( 城市) 移动到该蚂蚁个体的禁忌表中； s t e p 7 ：若k m ，则跳转到s t e p 4 ，否则执行s t e p 8 ； s t e p 8 ：根据公式( 2 3 ) ，( 2 4 ) ，( 2 5 ) 更新每条路径上的信息量； s t e p 9 ：若满足结束条件，即如果循环次数眦2 n c m 旺，则循环结束 并输出程序计算结果，否则清空禁忌表并跳转到s t e p 2 。 以t s p 为例，基本蚁群算法的程序流程图如图2 1 所示。 西南交通大学硕士研究生学位论文第1 1 页 1 开始 i 山 初始化 j 1 迭代次数n c = n c + l 上 蚂蚁k = l l 7 蚂蚁k = k + l 0 按照状态转移概率公式( 2 - 1 ) 选择下一个元素 上 l 修改禁忌表 n 一 按照公式( 2 3 ) ( 2 4 ) ( 2 5 ) 进行信息量更新 磊：、n 图2 1 基本蚁群算法的程序流程图 西南交通大学硕士研究生学位论文第12 页 2 2 5 基本蚁群算法的性能评价指标 为了全面衡量基本蚁群算法的优劣程度，首先引入评价基本蚁群算 法性能的三个基本指标。 ( 1 ) 最佳性能指标 定义相对误差e 0 为最佳优化性能指标，其公式见( 2 6 ) 助。三阜1 0 0 ， ( 2 6 ) c 、 式中，c b 表示算法多次运行得到的最佳优化值；c 表示所求问题 的理论最优值，当理论最优值未知时可用已知最优值来代替。最佳性能 指标用以衡量基本蚁群算法对问题的最佳优化程度，其值越小意味着蚁 群算法的优化性能越好。 ( 2 ) 时间性能指标 。 定义基本蚁群算法的时间性能指标e t ，其公式见( 2 7 ) d 。警1 0 0 ( 2 7 ) i 眦 式中，i i 表示算法多次运行后，满足终止条件时的迭代平均值；i m “ 表示给定的最大迭代次数：t o 表示算法一次迭代的平均计算时间。时间 性能指标用以衡量基本蚁群算法对问题解的搜索快慢程度，在i m 鲅固定 的前提下，e t 越小说明蚁群算法的收敛速度越快。 ( 3 ) 鲁棒性能指标 ， 定义基本蚁群算法的鲁棒性能指标e r ，其见公式( 2 - 8 ) 西。半1 0 0 ( 2 8 ) c 式中，c a 表示算法多次运行后所得到的平均值；c 簟表示所求问题的 理论最优值。鲁棒性能指标用以衡量基本蚁群算法对随机初值和操作的 依赖程度。其值越小说明算法的鲁棒性越强。 西南交通大学硕士研究生学位论文第13 页 基本蚁群算法的综合性能指标e 可以表示为上述三个指标性能的加 权组合，见公式( 2 9 ) emg 。e o + 6 e t + c d 一 ( 2 - 9 ) 式中，a , b ，c 分别表示最佳性能指标、时间性能指标和鲁棒性能指标的加 权系数，且满足a + b + c = l ； e 值越小则说明算法的综合性能越好。 2 2 6 蚁群优化算法的几个缺陷及一些改进方法 虽然a c o 算法具有很强的全局寻优解的能力，在很多领域获得广 泛的应用，但也存在一些缺陷，主要有以下两点： ( 1 ) 与其它的寻优算法相比，a c o 算法的搜索时间过长。一般地， a c o 算法的时间复杂度为o ( i i c 一刀2 x 历) ( 其中n c m 瓠表示循环次数，n 为城市数，m 为蚂蚁数) ，大部分的计算时间被用于解的构造。 ( 2 ) a c o 算法的执行过程中容易出现停滞现象，存在陷入局部最优 的可能性。具体地说，就是搜索进行到一定的程度后，所有蚂蚁个体发 现的解趋于一致，此时，即使采用随机搜索策略，也不一定能在解空间 中进一步搜索，这不利于发现更好的解。原因就在于信息素轨迹更新规 则中不被选用的弧段上的信息素轨迹和选中的弧段上的信息素轨迹的 差异会变得越来越大，而蚂蚁始终沿着信息素轨迹高的弧段爬行，这就 导致当前不被选用的弧段在那以后被蚂蚁选择的概率变得越来越小，进 而使算法只会在某些局部最优解附近徘徊，出现停滞现象。要减弱或消 除停滞现象，一个可能途径就是在蚂蚁搜索空间的延拓和蚂蚁反馈学习 的选取两方面做折衷，利用适当的信息素差异平滑策略和信息素挥发机 制来逐步拓展搜索空间，以跳出局部最优状态。 基于此，一些学者提出了一些改进算法，主要有以下几种： 1 ) 精英策略。在每次所有蚂蚁完成一次周游，选取最好的几个解( 路 西南交通大学硕士研究生学位论文第14 页 径) ，对这几个最好的解进行路径信息素更新。这样做可以保证每次保 留的解的质量，提高运算速率，缩短运算时间。但如果数量过多，会导 致某些路径上信息素强度相对其他路径占优，使蚂蚁集中到几条路径上 来，导致搜索过早停滞，算法陷入局部最小。 2 ) 更新所有路径。这样虽然可以避免过早收敛，但蚂蚁的搜索不易 停留在较好解附近，算法计算时间过长，解的质量不高。 3 ) a n t q 算法。a n t q 算法是将强化学习算法引入到蚁群算法中用 来解决t s p 问题的一种启发式算法。d o r i g o 等人发现蚂蚁在一个一个城 市中寻找最短路径的行为和强化学习一q 学习过程很相似，认为蚂蚁寻 找最短路径的过程实际上就是一个q 学习过程。该算法在一些较小规模 的t s p 问题上取得了比模拟退火和自组织网络等算法更好的计算结果。 但这个算法比较复杂，同样在处理大规模t s p 问题时效率不高，没有解 决根本问题。因此，该算法提出后没有被太多学者接受。 4 ) 最大最小蚁群算法。由于信息素在蚁群算法中起到联系、协作、 保存和引导的功能，所以如何更好的处理信息素是提高算法效率的关 键。t h o m a ss t i i t z l e 等人发现，算法停滞是因为信息素过分集中到几条 较好的路径上，其他路径由于长时间没有蚂蚁经过，信息素的挥发使得 路径上信息素浓度接近于o ，这时候蚂蚁几乎不会选择这些信息素极低 的路径，从而丧失了搜索新路径的可能性，算法就会表现出停滞现象。 最大最小蚁群算法与基本蚁群算法相比，在四方面进行了改进：( 1 ) 在一 次循环后，仅对一个解添加信息素，这个解可以是在所有循环中发现的 全局最优解，也可以是当前这次周游中找到的局部最优解。实验结果表 明，对本次循环的局部最优解进行信息素更新效果要更好。另外一种更 新信息素的方法是，每次循环更新本次循环的局部最优解的路径上的信 息素，并周期性更新全局最优解的路径上的信息素。( 2 ) 将每条边上的信 息素t i i ( t ) 限定在【t m i n ，t m a x 】之间，通过设定信息素的上下限，既防止了 西南交通大学硕士研究生学位论文第15 页 某些路径上信息素过高，防止蚂蚁爬行集中在这些路径上而出现停滞现 象，又使得另外一些路径上信息素浓度不至于太低，从而蚂蚁在后期爬 行中仍然有可能搜索到这些路径，使得算法搜索到新路径的可能性不至 于太低。( 3 ) 在初始化时，每条边上的信息素浓度初始化为信息素最大值 t i j ( 0 ) = t m 珏，并设定p 为一个比较小的值，使得信息素的挥发非常缓慢， 代表了一个缓慢的学习过程。这一措施也使得算法不至于过早停滞。( 4 ) 蚁群算法与局部搜索方法相结合以提高局部搜索效率。实验结果表明， 最大最小蚁群算法在寻找解的有效性方面和防止过早停滞方面都有较 大的改进。 2 7 蚁群优化算法的发展 任何事物都具有两面性，蚁群优化算法作为一种新兴的仿生优化算 法也不例外。蚁群算法固然具有采用分布式并行计算机制、易于与其他 方法结合、具有较强的鲁棒性等优点，但搜索时间长、容易陷入局部最 优是其最突出的缺点。针对这些缺点，近些年来众多国内外学者在蚁群 算法的改进方面做了大量的研究工作，这些改进有一个共同目的，那就 是在合理时间复杂度的限制条件下，尽可能提高蚁群算法在一定空间复 杂度下的寻优能力，从而改善蚁群算法的全局收敛性，并拓宽蚁群算法 的应用领域。对一些组合优化问题搜索空间特征的研究表明，对于许多 问题，在解的质量和最优解的距离之间存在着一定的关系。因此，将搜 索集中于搜索过程中所找出的最优解的周围，是这些改进算法提高基本 蚁群算法性能的主要方法。 西南交通大学硕士研究生学位论文第16 页 第3 章基于信息启发式因子a 和期望启发式因 子卢的改进蚁群算法 3 1 引言 在蚁群算法中，信息素和启发函数、信息量和启发函数的乘积 p o ) r 切o ) r 、蚂蚁之间的合作行为会严重影响到算法的收敛性，可见 信息启发式因子口和期望启发式因子p 对算法性能的好坏起着很重要 的作用，其选取方法和选取原则直接影响到蚁群算法的全局收敛性和最 优解的质量。但由于口、卢和其它参数之间的关联性，如何确定各个参 数之间的最优组合是一个复杂的优化过程，目前还没有完善的理论依 据，大多数情况下是根据经验而定。 基于此，d o r i 9 0 1 3 】等最早对口、。p 、p 、m 等参数的选择进行了初 步的探讨；b o t e ehm 等1 3 4 】用遗传算法求得口、卢、p 、m 等参数的组 合优化，但是这种利用遗传算法求解组合参数的方法比较麻烦，效果也 不明显；随后，段海滨【3 5 3 6 l 、郝晋【3 7 1 、詹士副3 引、叶志伟1 3 吼删在蚁群 算法的参数分析和优化组合方面进行了卓有成效的工作。 蚁群算法中的参数设定至今尚未有严格的理论依据，也没有确定的 优化参数的通用方法。本章通过对口、卢、p 、m 参数进行分析，给出 一种自适应调整口，p 参数的改进算法。 西南交通大学硕士研究生学位论文第17 页 3 2 蚁群算法初始化参数口、外p 、m 对蚁群算法性能的 影响 启发式因子口反映蚂蚁在运动过程中所积累的信息量在指导蚁群 搜索中的相对重要程度，其值越大蚂蚁选择以前走过路径的可能性就越 大，搜索的随机性减弱：而当启发式因子口过小时，则易使蚁群算法陷 入盲目的随机搜索。 期望启发式因子声反映了启发信息在指导蚁群搜索过程中的相对 重要程度，其大小反映了蚁群寻优过程中先验性、确定性因素的作用强 度。过小，将导致蚂蚁群体陷入纯粹的随机搜索，通常在这种情况下 很难找到最优解；岁过大时算法的收敛速度加快，但算法搜索最优路径 的随机性减弱，易于陷入局部最优。 信息素挥发因子p 的大小直接关系到蚁群算法的全局搜索能力及 其收敛速度。当p 过大时，以前搜索过的路径被再次选择的概率过大， 会影响算法的随机性和全局搜索能力；反之，通过减小p 虽然可以提高 算法的随机性能和全局搜索能力，但会使算法的收敛速度降低。 对于t s p 问题，单只蚂蚁在一次循环中所经过的路径表现为问题可 行解集中的一个解；m 只蚂蚁在一次循环中所经过的路径则表现为问题 可行解集中的一个子集。在实际应用中，m 过大时，会使大量的曾被搜 索过的路径上的信息量的变化趋于平均，信息正反馈作用减弱，虽然全 局搜索的随机性得到了加强但收敛速度减慢。反之若m 过小，会使那些 从来没有被搜索到的解上的信息量减小到接近于0 ，全局搜索的随机性 减弱，虽然这使收敛速度加快，但会使算法的稳定性交差，且容易出现 过早停滞现象。 西南交通大学硕士研究生学位论文第18 页 3 3 参数口、夕的自适应调整的改进算法 定义3 1 当算法求出的最优解在n ( n 为常数) 次循环后没有变化时则认 为最优解疑似陷入局部最优。 根据3 2 中参数口，声对算法全局性和收敛速度的分析，可以在初 始阶段给a ，设置较小的值，这样可以扩大初始阶段蚁群的搜索范围， 在后期阶段可以通过增大参数a ，卢的值来减少解的空间，使搜索逐渐 向较优的路径上靠拢并形成正反馈，以此来防止那些较优的路径上的信 息素强度在循环过程中被减弱，从而使得较优路径更容易被蚂蚁选中， 这样不但可以