（管理科学与工程专业论文）连续空间蚁群算法研究及在工业过程控制中的应用.pdf

山东师范大学硕士学位论文 连续空间蚁群算法研究及在工业过程控制中的应用 摘要 最优化是一个重要的数学分支，也是一门应用相当广泛的学科，最优化的目 的是对于给出的实际问题，从众多方案中选择出最优方案。在最近的二、三十年 中，伴随着计算机技术的高速发展和优化计算方法的进步，各种优化问题的理论 研究发展迅速，新方法不断出现，实际应用日益广泛。如遗传算法、进化规划、 进化策略等。蚁群算法是最近几年才提出的一种新型的模拟进化算法，在该算法 中，可行解经过多次迭代后，最终将以最大的概率逼近问题的最优解。 蚁群算法是一种适于求解复杂组合优化问题的新型模拟进化算法，除离散型 的组合优化问题外，蚁群算法也可用于求解连续空间函数优化问题，它具有许多 优良性质和实际应用价值。本文以基本蚁群算法的性能分析为背景，探讨了蚁群 算法的原理、构成、性能及其特点。提出了一种改进的蚁群算法，并将其用于求 解连续空间函数优化问题和工程控制过程中p i d 控制器参数优化中的应用，实验 证明了此改进算法的可行性。主要内容如下： 1 综述了蚁群算法的生物学机理、发展过程、算法特点及其研究和应用状况， 指出其在解决组合优化问题方面的优越性，以及在解决连续空间优化问题研究方 面的不足；介绍了蚁群算法基本模型a s ( 觚s y s t e m ) 的原理、特点、构成和实现 方法，并且综述了目前用于连续空间优化的蚁群算法的改进技术。 2 由于最初的蚁群算法思想起源于离散型的网络路径问题，因此，在一般函 数的优化问题中，必须对原蚁群算法数学模型的许多实施细节进行修正，在总结 和分析已有研究成果的基础上，对连续空间蚁群算法c a c a 数学模型的许多实 施细节进行休整，包括解空间的分区数、搜索蚂蚁群体数及其他参数选择。 3 针对蚁群在解空间作随机搜索的局限性，引入确定性搜索方法变尺度法， 提出了改进蚁群算法v a c a 。将改进算法模型应用于一维和多维连续函数优化 中，并与c a c a 的仿真结果进行比较，以证明算法的有效性。 4 因此本文应用改进蚁群算法对热工控制系统中控制器各参数进行优化整 定，并与z i e g l e r - n i c h o l s 算法和c a c a 算法的仿真结果进行比较，来证明改进蚁 山东师范大学硕士学位论文 群算法在实际应用中的有效性，表明该算法优化效率和求解质量上都有所提高。 蚁群算法是一种随机搜索算法，它具有许多优良性质，它比目前应用广泛的 遗传算法等具有更好的适应性。蚁群算法已经在若干领域获得了成功的应用，但 仍有许多尚待研究和解决的课题。蚁群算法出现的时间不长，对其研究还远不像 其它启发式算法那样形成系统的理论。算法中参数的选择更多的是依靠实验和经 验，没有理论来指导，且计算时间偏长，容易出现停滞现象，这些都表明该算法 在理论和实践方面尚有许多问题需要更深入的研究与解决。 关键词：蚁群算法，连续空间优化问题，变尺度法，p i d 控制，适应度函数 中图分类号： t p 3 0 1 6 l i 山东师范大学硕士学位论文 a b s t r a c t o p t i m i z a t i o ni sa ni m p o r t a i l _ tb 舢c h0 fm a t l l e m a t i c s ，赳l daw i d e 啪g eo f d i s c i p l i n e so fs u b j e c t f o rt l l ep u 印o s eo f t 1 1 ea c 砌p r o b l e m ，m eb e s tp r o g 舢c a i lb e c h o s e nf r o mm a r l yp r o g r a m s r e c e n t l y ，a c c o m p a i l i e db yt l l er a p i dd e v e l o p m e mo f c o m p u t e rt e c l l i l o l o g ya n do p t i m j z e dm e t l l o d s ，a 1 1k i n d so ft l 】【e o r e t i c a l 咖d yh a v e d e v e l o p e da 1 1 dp r a c t i c a la p p l i c a t i o i l s a r ei 1 1 c r e 嬲i i l g l y 埘d e s p r e a d a n tc o l o n y a l g o r i t 量1 mh 锻b e e np u tf o m ，卸r do i l l yi nr e c e my e a r s ，w h j c hi san e wt ) r p i eo fs i m u l a t e d e v o l u t i o n a 巧a l g o r i t i l i l l t h eb i g g e s tp r o b a b i l i t ) ，晰l le v e n t u a l l y 印p r o a c hn l e 叩t i i i l a l s o l u t i o no ft 1 1 ep r o b l e ma r e rs e v e r a li t e r a t i o n s a n tc 0 1 0 n yo p t i m i z a t i o na l g o r i t h m ( a c o ) i san e ws t i m u l a t e de v o l u t i o n a d r a l g o r i t l l i na t t a c k i n gh a r dc 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 nh a ss h o w e da 班a t d e a lo fs a l i e n tc h a r a c t e ra i l dp e r f o 眦e dg r e a tv a l u ei i li t sa p p l i c a t i o n c h o o s i n gt h i e a 1 1 a l y s i so fc h a r a c t e ro fa n ts y s t e m ( m eb a s i ca l g o r i 岫so f 锄tc o l o n ”弱t l l e r e s e a r c hb a c k g r o u i l d ，t l l i sp 印e rf o c u s e so nt h ep r i n c i p l e ，t l l em o d e l ，t l l eb e h a v i o r 觚d 砥c b a r a c t e r i s t i c s i nt h i sp a p e r ak i r l do fa c oa l g o r i m mb a v eb e e np r o p o s e df o r s o l v i n gt l l ec o n t i n u o u ss p a c eo p t i m i z a t i o na n d p i dc o n t r o l l e rp a r 锄e t e r so p t i m i z a t i o n i ni 1 1 d u s t r i a lp r o c e s sc o n 仃0 1 f i n a l l y 也er e s u l t so b t a i n e dv i ac o m p u t e rs i m u l a t i o n s h o wi t sv a l i d i 班t h em a i nw o r k sa n di i l i l o v a t i o n s 嬲f o l l o w s ： 1 t h eb i o l o g i c a lm e c h a n i s m ，t 1 1 ed e v e l o p m e n ta i l dc h a r a c t e ro ft h ea n tc o l o n y a l g o r i t i l i i la r eo u t l i n e t h ec 咣n ts i t u a t i o n so fr e s e a r c ha n d 印p l i c a t i o no fn l e 锄t c o l o r l ya l g o d m mi si n t r o d u c e d t h es u p e r i o r i 够i ns o l v i n gc o m b i n a t o r i a lo p t i m i 刎o n p r o b l e m s 孤dm es h o r t a g e si ns o l v i n gt h e c o n t i 芏l u o u ss p a c eo p t i m i z a t i o np r o b l e m sa r e p r e s e n t e d ；i nm i sp 印e r ，w ea l s oi n t r o d u c et h ep r i n c i p l e ，廿l em o d e l ，t l l ec h a r a c t e r i s t i c s a n dm em a n a g e m e n ta b o u tt 1 1 eb a s i ca l g o r i t l l m so f 觚tc o l o n y ( a n ts y s t e m ) a n dal i s t o fi m p r o v e m e n t so fc o n t i n u o u ss p a c eo p t i m i z a t i o nh 嬲b e e nr e f e r e n c e d 肌dp r e s e m s ； 2 o nt h ef o u l l d a t i o no fs 啪m a r i z i n g 趾l da i l a l y z i n gt h ee x i s t i n gr e s e a r c hr e s u l t s ， m a i l yd e t a i l so fo r i g i n 2 l la n ta l g o r i t h mm o d e lh a v eb e e ni m p l e m e n t e d ，i n c l u d i n gm e m 埘b e ro fd i v i s i o ns p a c e ，m em l m b e ro fs e a r c l l i n ga i l t sa i l do l e rp a r 锄e t e r s 3 f a c i n gt h el i m i t a t i o n so fm er a n d o ms e a r c hm t l l es o l u t i o ns p a c e ，w eu s e l e c e r t a i n t ys e a r c hm e m o d ，v i r i a b l em e t r i ca l g o r i t i h n ，t l l ei i l l p r 0 v e da 1 9 0 r i t h mv a c a h a sb e e ng o t t e n t h ei m p r o v e da l g o r i t h mh 嬲b e e n 印p l i e dt 0o n e d i m e n s i o n a l 锄d m u l t i - d i m e n s i o n a lc o n t i n u o u s 如n c t i o no p t i m i z a t i o n c o m p a r e dw i t ht l l es i i i m l a t i o n r e s u l t so ft h eo r i g i i l a la a d ，t l l ee f f e c t i v e n e s so fm e 印p r o a c hc 锄h a v eb e e np r 0 v e d 4 i nt l l i sp a p e r ，p i dc o n l | r 0 n e rp a r a m e t e r so p t i m i z a t i o nc a nb er e a l i z e du s i n gn l e i m p r o v e da l g o r i n l 】m ，t 0v e r i 匆t l l ee 虢c t i v e n e s so fi t sp r a c t i c a l 印p l i c a t i o n 加以 i e x p e r i m e n t ss h o wt l l a t 叩t 砌z 撕0 ne 伍c i c y 觚dq u a l 毋h a sb e e ni m p r o v e d t h e 锄tc o l o n ya l g o r i t i sab n do fs t o c h a s t i ce x p l o r a t i v ea l l g o r i t h mw l l i c hh a s s h o w e dm a l l ye x c e l l e n tc h a r a c t 嘶s t i c s ni sd e m o i l s 仃a t e dm a tt h ea n tc o l o n v a l g o r i t l l mi sm o r ea d 印t i v et 0 也eg e n e t i ca l g o r i t h i n s 觚d 恤s i i i l u l a t e da l l l l e a l i n g a l g o r i n 吼sw h i c hw e r e 缸h i o n a b l ef o rat i m e a l u 曲s o m es u c c e s s 如l 印p l i c a t i o n s h a 、，eb e e np r e s e n t e d ，“a l s oh a sm a i 】l y p r o b l e m sf o rs o l v i n ga i l dm a 虹n g 如n h e r i n v e s t i g a t i o n a n tc o l o n ya l g o r i t l l i n ，w t l i c hi sd i 虢r e n t 舶mo m e rh e u r i s t i ca l g o r i t l l i i l ， h 弱n o tf 0 加1 e dt h et h e o 巧s y s t e m p a r a m e t e rs e l e c t i o nr e l i e so nm o r ee x p e 血n e n t sa n d e x p e n e n c e i tt a k e sm o r et i m et 0c a l c u l a t ea i l di ti sp r o n et 0s t a g n a t i o nw b j c hs h o w s t h a tt h ea l g o r i t i nt h e o 巧a i l dp r a c t i c eh a sm a l l yp r o b l e m st os o l v ea n d r e s e a r c h 1 ( e yw o r d s ：a mc o l o n yo p t i m i z a t i o n ，c o n t i n u o u ss p a c eo p t i m i z a t i o n ，v i r i a b l em e t r i c a l g o r i t ，p i dc o n t r 0 1 l e r ，f i t n e s s t i o n c l a s s i 6 c a “o n ：t p 3 01 6 i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者签名够 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解邋有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权越可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解 密后适用本授权书) 学位论文作者签名：叠己易 导师签 签字日期：2 0 07 年6 月2 日 签字日期：2 0 0 夕年月；日 山东师范大学硕士学位论文 第1 章绪论 本章给出了论文的写作背景及其意义，首先介绍了蚁群算法的特点及其原 理；然后讨论了近年来蚁群算法的若干改进以及在许多新领域的发展应用；最后 扼要介绍了本文的主要工作。 1 1 选题意义及研究背景 最优化是一个重要的数学分支，也是一门应用相当广泛的学科，最优化的目 的是对于给出的实际问题，从众多方案中选择出最优方案。在最近的二、三十年 中，伴随着计算机技术的高速发展和优化计算方法的进步，各种优化问题的理论 研究发展迅速，新方法不断出现，实际应用日益广泛。如遗传算法、进化规划、 进化策略等。蚁群算法是最近几年才提出的一种新型的模拟进化算法，在该算法 中，可行解经过多次迭代后，最终将以最大的概率逼近问题的最优解。 人们在很早的时候就对自然界中存在的群集行为感兴趣，如大雁在飞行时自 动排成人字形，蝙蝠在洞穴中快速飞行却可以互不碰撞等。同时受蚂蚁、飞鸟等 社会性昆虫行为的启发，单个的个体智能并不高，但依靠群体的能力，却发挥出 超出个体的智能。这种现象揭示了简单智能的主体通过合作可以表现出复杂智能 行为的特性。通过对其行为的模拟，产生了一系列解决复杂优化问题的新思路和 方法，用于解决组合优化问题和其它一些实际应用问题的新方法相继产生。一些 启发于群居性生物的寻食、打扫巢穴等行为而设计的算法成功地解决了组合优 化、通信网络和机器人等领域的实际问题，这些研究被称为对群体智能( s w 锄 i n t e l l i g e n c e ) 的研究。群体智能引起了包括计算机科学家在内的众多研究人员的 兴趣，蚁群算法【l 】就是利用群集智能解决优化问题的典型例子。 2 0 世纪9 0 年代初期，意大利学者d o r i g om a c r o 等从生物进化论中受到启发， 通过模拟自然界蚂蚁集体寻优的行为提出了蚁群优化算法( a mc o l o n y o p t i i i l i z a t i o n ，a c o ) 【2 】，它是继模拟退火算法、遗传算法、禁忌搜索算法、人 工神经网络算法【3 】等启发式搜索算法之后的一种新型的基于种群的启发式仿生 类进化算法。该算法的出现引起了学者们的极大关注，已在组合优化、网络路由、 山东师范大学硕士学位论文 函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得了较好 的效果。蚁群算法特别适合求解规模较大的或问题状态随时间变化的组合优化问 题，如著名的t s p 、q a p 、j s p 【4 ，5 ，6 】等复杂组合优化问题。此外，蚁群算法在连 续空间优化中的应用【7 ，8 9 】也是近年来许多学者关注的研究方向。 目前蚁群算法在最初模型的基础上得到了改进和扩展，它在连续空间寻优中 的应用为人们所关注，但由于至今为止蚁群算法还没有建立完备的理论体系，因 此，在将优化性能良好的蚁群算法用于连续性空间优化问题时，都是利用蚁群算 法的原理和人们对优化函数取得的有关先验知识来构造相应的算法模型，并对算 法中许多实施细节加以修正，从而确定在优化过程中蚁群协同决策所选择的移动 方向，由此来求得最优解。这样使得各种算法在没有坚实的理论基础上存在着一 些缺陷，如容易陷入局部最优和搜索时间较长等，本文针对这些问题提出了一种 改进的连续空间蚁群算法模型。该模型在将变尺度法嵌入到a c o 算法的局部搜 索过程中，来确定蚂蚁在局部搜索过程中的移动步长，减少了蚂蚁陷入局部最优 解的可能性，以克服a c o 算法搜索时间过长的缺点，为蚁群算法应用于实际优 化问题提供了一条可行途径。 蚁群优化算法的严格理论基础尚未奠定，国内外有关研究仍停留在实验探索 阶段，但从当前的应用效果看，这种模仿自然生物的新型系统寻优思想无疑具有 十分光明的前景。 1 2 蚁群算法简介 蚁群算法是一种模拟进化算法，d o r i g o 等人充分利用了蚁群搜索食物的过程 与著名的旅行商问题( t r a v e l i n gs a l e s m a i lp r o b l e m ) 之间的相似性，吸收了昆虫 王国中蚂蚁的行为特性，通过人工模拟蚂蚁搜索食物的过程( 即通过个体之间的 信息交流与相互协作最终找到蚁穴到食物源的最短路径) 来求解t s p 问题。为 了区别于真实蚂蚁群体系统，我们称这种算法为“人工蚁群算法”。为了说明“人 工蚁群算法 的原理，首先简单介绍一下蚂蚁搜索食物的具体过程。 像蚂蚁这类群居昆虫，虽然视觉极其微弱，却能找到由蚁穴到食物源的最短 路径。仿生学家们经过大量细致的观察研究发现，生物世界中的蚂蚁在搜索食物 时，能在其走过的路径上释放一种信息素，使得在一定范围内的其他蚂蚁能够察 2 山东师范大学硕士学位论文 觉到并影响其搜索行为。蚂蚁个体之间是通过一种称之为外激素( p h e r o m o n e ) 的通讯介质来互相传递信息的，从而能相互协作，完成复杂的任务。蚂蚁在运动 过程中，能够在它所经过的路径下留下该物质，而且蚂蚁在运动过程中，能够感 知路径上这种物质的存在及其强度，并且以此来指导自己的运动方向，蚂蚁倾向 于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群( 觚c o l o n y ) 的集体行为便表现出一种信息正反馈的现象：当某路径上经过的蚂蚁越多时，留 在相应路径上信息素的迹( 碱1 ) 也越多，以致信息素的强度增大，后来的蚂蚁 选择该路径的概率也就越高，从而进一步增加该路径的信息素强度，这样的选择 过程被称为蚂蚁的自催化行为( a u t o c a t a l 舛cb e h a v i o r ) 。蚂蚁个体之间就是通过 这种信息的交流达到快速搜索食物的目的的。 人工蚂蚁算法是受到人们对自然界中真实的蚁群集体行为研究成果的启发， 而提出的一种基于种群的模拟进化算法，属于随机搜索、全局优化算法。与其它 模拟进化算法一样，通过多个候选解( 可行解) 组成的群体的进化过程并以最大 概率逼近问题的最优解。该过程包括两个基本阶段：适应阶段和协作阶段。在适 应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间 通过信息交流，以其产生性能更好的解。以t s p 问题的求解为例，求解开始时， 蚂蚁群各自随机行动，以后则按概率选择留有信息素的且尚未走过的路径，直至 完成一次搜索，这样即构成问题的一个可行解。因而，蚂蚁成功地搜索一轮所形 成的是一组可行解，然后记录其中的最好节，各蚂蚁所遗留下的信息素的迹也将 按持久程度( 即挥发状况) 保留到以后各轮搜索，从而为蚂蚁以后的路径搜索产 生特有的生物行为影响。 1 3 蚁群算法研究现状 1 3 1 蚁群算法的特点 蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法 等启发式搜索算法以后的又一种应用于组合优化问题的启发式随机搜索算法。众 多的研究结果已经证明，蚁群算法具有很强的发现较好解的能力，这是因为该算 法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质并 山东师范大学硕士学位论文 行的算法，不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利 于发现较好的解。蚁群算法可以解释为一种特殊的强化学习算法。 蚁群算法的主要特点概括如下： ( 1 ) 采用分布式控制，不存在中心控制； ( 2 ) 每个个体只能感知局部的信息，不能直接使用全局信息； ( 3 ) 个体可改变环境，并通过环境来进行间接通讯( s t i g m e q g ) r 机制) ： ( 4 ) 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的 智能( e m e 唱e n ti n t e l l i g e r l c e ) ； ( 5 ) 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会 求得全局最优解； ( 6 ) 其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导 性，及目标函数和约束函数的精确数学描述； ( 7 ) 是一类基于多主体( m u h i a g e n t ) 的智能算法，各主体间通过相互协作 来更好的适应环境。 1 3 2 蚁群算法的应用 自从蚁群算法成功求解著名的t s p 问题以来，目前已陆续渗透到其他许多 领域。 ( 1 ) 网络路由一通讯问题 蚁群算法在动态组合优化问题研究中的应用主要集中在通讯网络方面【1 0 1 。随 着h l t e m e t 上广泛的分布式多媒体应用对服务质量( q u a j 埘o f s e r v i c e ，q o s ) 需 求的增长，各种服务应用对网络所能提供的q o s 提出了不同的要求，而路由是 实现q o s 的关键之一。将蚁群算法用于解决受限路由问题，目前可以解决包括 带宽、延时、包丢失率和最小花费等约束条件在内的q o s 组播路由问题【1 1 1 4 1 ， 比现有的链路状态路由算法具有明显的优越性，但所研究的实例相对简单，没有 对更复杂的q o s 问题进行深入讨论。 ( 2 ) 车辆路径问题( v r e l l i c l er 0 u t i n gp r o b l e m ，v r p ) v i 冲问题是一类交通运输优化问题，即在给定车辆的载重量及各个需求点 的需求量，优化目标是在保证各个需求点需求的前提下，通过车辆的调度，使车 4 山东师范大学硕士学位论文 辆的总行程最短。目前，除了一些经典的智能算法以外，采用t s p 风格的蚁群 算法同样可求解v r p ，求解时可将车辆模拟成蚂蚁。近年来，国内外学者在用 蚁群算法求解v r p 方面的研究取得了很多成果，但模拟效果距现实中的v i 冲问 题还有一定的差距。因此，这方面的研究还有待于进一步加深。 ( 3 ) 生产调度问题( j o bs c h e d u l i n gp r o b l e m ，j s p ) 蚁群算法机制可以不断从过去的加工经历中学习，能自然地适应车间内外部 环境的变化，从而实现动态调度。所以，它能适应动态的工件到达，不确定的加 工时间以及机床故障等扰动，比静态确定性算法具有更好的应用背景”，1 6 1 。 蚁群算法同样可求解动态任务多目标分配问题，并对车间内外部环境变化具 有良好的自适应性，但这些应用研究大多是针对小规模实例的仿真，用蚁群算法 解决大规模生产调度和多目标分配问题是今后进一步的研究方向。 ( 4 ) 电力系统优化问题 电力系统优化是一个复杂的系统工程，它包括无功优化、经济负荷分配、电 网优化及机组最优投入等一系列问题，其中很多是高维、非凸、非线性的优化问 题。文献 1 7 】解决了该算法在配电网优化规划中的初步设计问题。 电力系统优化中的机组最优投入问题是寻求一个周期内各个负荷水平下机 组的最优组合方式及开停机计划，使运行费用最小。利用动态、决策及路径概念， 将机组最优投入问题设计成类似t s p 问题的模式，从而可方便地利用蚁群算法 来求解。t e n g 等针对分布式系统中开关重定位问题对蚁群算法进行了遗传变异 改进，但未能给出解决这类非线性。不可微目标函数优化问题的蚁群算法参数选 择原则。文献【1 8 】将蚁群算法编入水利发电规划能源管理软件，可很好地节约能 源，但对于蚁群算法在实际应用中的可靠性问题还需迸一步探讨。 此外，蚁群算法还在数据挖掘 1 9 】、图像处理 2 0 】、参数辨识【2 1 】、凸整数规 划问题 2 2 】、机器人路径规划问题 2 3 】以及图形着色 2 4 】等领域的应用取得很大进 展。除离散型的组合优化问题外，蚁群算法也可用于求解连续空间函数优化问题， 其求解的核心思想是将连续的搜索空间离散化，用一个从起始点出发的运动矢量 集合来描述蚂蚁的移动路径，这样就可用一个离散的结构来表示蚁群的连续运动 区域。已有一些学者对其进行了研究，但算法参数的选择缺乏严格的理论证明， 算法的优化性能也有待进一步提高。 5 山东师范大学硕士学位论文 1 4 本文的主要工作 本文以基本蚁群算法性能的分析为背景，探讨了蚁群算法的构成、性能、特 点及其改进措施，提出了在连续空间优化问题中改进蚁群算法模型，并通过实例 分析了算法的可行性，给出了算法的构造和仿真试验结果，进而指出了连续空间 优化问题中蚁群算法的进一步研究方向。全文共分6 章，主要内容如下： ( 1 ) 第一章综述了蚁群算法的选题意义及研究背景、发展过程、算法特点及 其研究现状和应用现况，指出其在解决组合优化问题方面的优越性； ( 2 ) 在第二章中着重指出了蚁群算法的基本原理和模型及流程图，并且对当 前蚁群算法的应用尤其在连续空间优化问题中的应用研究进行了综述； ( 3 ) 对原连续空间蚁群算法数学模型的许多实施细节进行修正，包括解空间 的分区数、搜索蚂蚁群体数、自变量随机移动步长及其他参数选择等； ( 4 ) 蚁群在解空间中做随机搜索，但随机性搜索具有一定局限性，包括求解 效率较低，求解结果较分散等，因此第四章中引入确定性搜索方法变尺度法以求 改进。从机制的融合、行为互补、削弱参数的苛刻性等几个方面出发，作为选择 将变尺度法和a c o 算法混合的出发点。定义了新的蚁群信息素更新规则、蚁群 在解空间的寻优方式和蚁群行进策略； ( 5 ) 第五章针对p i d 控制器参数优化设计问题，将蚁群算法设计的结果与遗 传算法、传统z i e g l e r - n i c h o l s 设计的结果进行了比较，数据仿真结果表明蚁群算 法具有一种新的模拟进化优化方法的有效性和应用价值； ( 6 ) 蚁群算法已经在若干领域获得了成功的应用，但仍有许多尚待研究和解 决的课题。在第六章中指出了蚁群算法的应用和理论研究中，今后有待深入研究 的有关课题。 6 山东师范大学硕士学位论文 第2 章蚁群算法基本模型及其特点 2 1 蚁群算法原理模型 2 1 1 蚁群算法的基本原理 仿生学家研究发现：蚂蚁在觅食过程中能够在所经过的路径上留下一种称为 信息素的物质，而且蚂蚁在觅食过程中能够感知这种物质的存在及其强度，并以 此指导自己的运动方向，他们倾向于朝着该物质强度高的方向移动。因此，由大 量蚂蚁组成的集体觅食行为就表现出一种信息正反馈现象：某一路径越短，该路 径上走过的蚂蚁就越多，所留下的信息素强度也就越大，后来者选择该路径的概 率因此就越大。蚂蚁个体之间通过这种信息交流来选择最短路径并达到搜索食物 的目的。蚁群优化算法就是模拟蚁群这一觅食行为的优化算法。 蚁群算法主要包括两个基本阶段：适应阶段和协作阶段。在适应阶段，各候 选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息素数量越 大，则该路径越容易被选择，时间越长，信息素数量越少；在协作阶段，候选解 之间通过信息交流，以期望产生性能更好的解。 为了能够清楚的理解蚁群算法的数学模型，仍以求解平面上船个城市的t s p 问题为例说明。船个城市的t s p 问题就是寻找通过刀个城市各一次且最后回到出 发点的最短路径。 首先引进如下记号：设所是蚁群中蚂蚁的数量，d ，施= 1 ，2 ，) 表示城市f 和城市，之间的距离，6 ，o ) 表示，时刻位于城市f 的蚂蚁的个数，则有 聊= 6 ，( f ) 。勺o ) 表示，时刻在城市f ，连线上残留的信息量。初始时刻，各条 路径上信息量相等，设勺( o ) = c ( c 为常数) 。每一个简单蚂蚁有以下特性： ( 1 ) 蚂蚁依据以城市距离和连接边上信息素数量为变量的概率函数选择下一 个城市。 ( 2 ) 规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市，由禁忌 7 山东师范大学硕七学位论文 表控制( 设砌甜。( 七= 1 ，2 ，加) 表示第七个蚂蚁的禁忌表) 。 ( 3 ) 它完成周游后，蚂蚁在它的每一条访问的边上留下信息素。 基本的蚁群算法可以简单表述如下：在o 时刻进行初始化过程，蚂蚁放置在 不同的城市，每一条边都有一个初始信息素强度( o ) ；每一只蚂蚁的禁忌表的 第一个元素置为它的开始城市：然后，每一个蚂蚁从城市，移动到城市，依据 两个期望措施的概率函数选择移动城市。在c 次循环后，所有蚂蚁都完成了一 次周游，它们的禁忌表将满；在这时，计算每一个蚂蚁尼的所走的路径总长度。， 力依据信息素更新规则进行更新，而且，由蚂蚁找到的最短路经( 即 m i n 三。，七= 1 ，2 ，历) 将被保存，所有禁忌表将置空；这一过程重复直到周游计 数器达到最大( 用户定义) 周游c 删x ，或者所有蚂蚁都走同一路线，后一种 情况被成为停滞状态。如果算法在c 次循环后结束，蚂蚁算法的复杂度为 d ( 人刀2 朋) 。 蚂蚁七( 七= 1 ，2 ，历) 在运动过程中，根据各条路径上的信息量决定转移方 向。群1 3 f ) 表示在，时刻蚂蚁七由城市礴专移到城市歹的概率： p ；=揣小枞吐 o ) 兹p ) “一”一七 o ，0 f h e r w 话e 其中，为先验知识或称能见度，在t s p 问题中为城市辟章移到城市的启 发信息，一般取嘞= 1 吒；口为路径( f ，歹) 上残留信息的重要程度：为启发信 息的重要程度；算法中的蚂蚁与大自然中的真实蚂蚁不同，具有记忆功能， 砒w p 以= 一砌甜。 ，是一组城市；砌材。( 后= 1 ，2 ，朋) 用以记录蚂蚁七当 前所走过的城市，称为禁忌表，集合硒“。随着进化过程作动态调整。 随着时间的推移，以前留下的信息素逐渐消逝，用参数p 表示信息素消逝程 度，蚂蚁完成一次循环以后，各路径上的信息量要作以下调整。 8 山东师范大学硕士学位论文 准则l ( 局部调整准则) ：局部调整是指每只蚂蚁在建立一个解的过程中进 行，经过办个时刻，两个城市之问的局部信息素数量要根据下式作调整： 勺( ，+ 厅) = ( 1 一善) f o ) + 善f o 1 气2 正 式中，善 o ，1 】，z n l i n 是两个最近城市之间的距离。 准则2 ( 全局调整准则) ：只有生成了全局最优解的蚂蚁才有机会进行全局 调整，全局调整规则为： 毛( f + 1 ) = ( 1 一p ) 乃( f ) + p 勺 勺= t f - l 其中，t 表示第七只蚂蚁在本次循环中留在路径 ，上的信息量，表示 本次循环中路径耖上的信息量的增量。一般设置周游次数计数器c ，当达到设 定值时结束，最短路经詈o ，( 七= 1 ，2 ，加) 2 1 2 蚁群算法模型及程序流程框图 d o r i g om a c r 0 曾给出了不同的蚁群算法模型，分别称为a n t c y c l e 模型， a i l t q u a i l t 时模型和觚t d e n s i t y 模型。它们的差别在于力( f ) 的求法不同。 在觚t c y c l e 模型中： 相_ 詈，凯只蚂蚁在时咳i j ，和f + 1 之间经过册 ( 2 1 ) i o ，其他 式中：q 是信息素强度，它影响算法的收敛速度；。是第七只蚂蚁在本次 循环中所走路径的长度。 在a i l t - q u a n t i 够模型中： 山东师范大学硕士学位论文 硝忙净酆只蚂蚁在时咳i j ，和f “之间经过拊 ( 2 - 2 ) lo ，其他 在趾t d e n s 时模型中： 啪= 恪凯朋蚁在时絮“加经过绀 ( 2 3 ) 模型比较：式( 2 2 ) 和式( 2 3 ) 利用的是局部信息；而式( 2 1 ) 中利用的是整体信 息。在一系列标准测试函数问题上运行的实验表明，基于觚t c y c l e 模型的蚁群 算法的性能优于其他两种模型算法。因此，对蚂蚁系统的研究正朝着更好地了解 觚t c y c l e 模型的蚁群算法的方向发展。 算法实现的计算机程序流程框图如图所示： 回 图2 1 基本蚁群算法计算机程序流程图 f i g 2 1f l o wc h a r t0 fs t 觚d a r d 绷tc o l o n ya i g o r i t h mi nc o m p u t e r 2 2 蚂蚁算法的几个缺陷 虽然蚁群算法具有很强的全局寻优能力，在很多领域获得了广泛的应用，但 存在一些缺陷，主要是： l o 山东师范大学硕士学位论文 ( 1 ) 与其他的寻优算法相比教，蚁群算法的搜索时间过长。一般地，蚁群算 法的时间复杂度为d ( c 万2 掌m ) ，肥为循环次数，以为城市的个数( t s p 问题 中) ，加为蚂蚁个数，大部分的时间被用于解的构造。 ( 2 ) 蚁群算法的执行过程中容易出现停滞现象。蚁群算法中搜索进行到一定 的程度后，所有蚂蚁个体发现的解趋于一致，此时，即使使用随机搜索策略，也 不可能在解空间中进一步搜索，这样就存在陷入局部极小的可能性，不利于发现 更好的解。原因在于信息素轨迹更新规则中不被选用的弧段上的信息素轨迹和选 中的弧段上的信息素轨迹的差异会变的越来越大，而蚂蚁始终沿着信息素轨迹高 的弧段爬行，这就导致当前不被选用的弧段今后被蚂蚁选择的概率变的越来越 小，进而使算法只会在某些局部最优解附近徘徊，出现停滞现象。 2 3 蚁群算法的改进 2 3 1 基于离散模型的改进蚁群算法 为了克服蚁群算法的缺陷，近年来，众多学者对蚁群算法进行了修正，发 表了大量有价值的学术论文。下面介绍几种具有代表性的改进方法： ( 1 ) 蚁群系统( a m tc o l o n ys y s t e m ，a c s ) 1 2 5 】是d o r i g o 和g 锄b a r d e l l a 在1 9 9 6 年提出来的，用于改善蚂蚁系统的性能。蚂蚁系统能够在一个有限的时间里找到 好的解决方案，仅限于小规模的问题。首先，a c s 中使用了一种状态转移规则 来指导蚂蚁最初的寻优过程，同时积累系统当前的状态。 状态转移规则的引入可使蚂蚁在进行路径选择时，不仅可以利用前面同伴提 供的反馈信息，还可以进行一定程度的随机探索操作。 其次，在a c s 中，每次循环后只对最优蚂蚁所走过的路径进行信息素增强， 其他路径由于挥发机制信息素会逐渐减少，这就增大了最优路径和最差路径再信 息素上的差异，从而使其搜索行为能够很快地集中在最优路径附近；此外，蚂蚁 在构造路径的同时进行局部更新，提高了算法的搜索效率。 ( 2 ) 最大最小蚂蚁系统( m a 】【m i na n ts y s t e m ，m m a s ) 【2 6 】是德国学者s t i n z l e 等提出的一种蚂蚁算法的改进方案。这是目前为止解决t s p 和q a p 等组合优化 问题最好的一类蚂蚁算法。m m a s 的特点是引入特别的机制来防止过早的停滞 山东师范大学硕士学位论文 现象。在每个解的元素( 在t s p 中是每条边) 上的信息素轨迹量的值域范围被 限制在一定区间内，从而有效的避免了某条信息素轨迹浓度大于其余路径。 ( 3 ) 自适应蚁群算法：通过自适应的改变算法的挥发度等参数【2 7 捌，可以在 保证收敛速度的前提下提高解的全局性。通过改进路径选择策略，全局修正信息 量规则，引入蚁群中蚂蚁分工与协同学习【2 9 ，3 0 ，3 1 1 ，协同工作的思想，可以提高算 法的自适应能力。 ( 4 ) 蚁群混合策略：将蚁群算法和其他智能优化算法相融合，形成优势互补， 是改进和完善蚁群算法的又一种重要途径。文献【3 2 ，3 3 ，3 4 】将遗传算法和蚁群算 法相结合，用遗传算法生成信息素分布，利用蚁群算法求精确解，形成了一种时 间效率和求解效率都比较好的启发式算法；文献 3 5 】把免疫思想引入到蚁群算法 中，综合了蚁群和免疫系统的优点。 2 3 2 连续系统优化的蚁群算法 蚁群算法来源于离散模型，但将蚁群算法用于连续系统优化已得到越来越多 的重视与研究，为了克服蚁群算法在求解连续空间优化方面的不足，人们对其作 了若干改进。这里介绍几种用于连续系统优化的蚁群算法。 文献 3 6 】曾提出了运用人工蚁群搜索的规律来求解一般函数优化蚁群算法模 型。该模型的基本思想为：将函数的解空间分割成一些均匀的小块( 称之为区域) ， 在各个区域中任取一点作为人工蚂蚁所处的初始位置，人工蚂蚁便按如下的规则 进行最优解的搜索： ( 1 ) 在一个循环中，首先按一定的规则计算各个蚂蚁在区域之间的转移概率。 如果符合相应的状态转移条件，则进行蚂蚁状态的转移；如果蚂蚁不符合有关状 态的转移规则，进行区域内的遍历搜索。 ( 2 ) 在新的循环开始之前，按一定的规则更新各个区域蚂蚁先前已搜索位置 的先验知识及有关启发信息。在此基础上计算各个区域间蚂蚁的状态转移概率， 按类似的状态转规则进行新一轮的循环与搜索。 从上述的一般函数优化的蚁群算法模型我们看到，该算法全局上虽表现为人 工蚂蚁某种先验知识和启发信息引导下的优化搜索，但在局部上采用的却是遍历 性搜索策略，而且对应于连续空间的残留信息得不到保存。当一个函数优化问题 1 2 山东师范大学硕士学位论文 的求解精度要求高或解空间的维数较高时，这种搜索策略的时间效率显然是比较 低的。 文献【7 】提出在连