（应用数学专业论文）蚂蚁族群演算应用在组合问题之研究.pdf

哈尔滨理t 九学珲。 砷卜学n 诊史 蚂蚁族群演算应用在组合问题之研究 摘要 蚂蚁族群最佳化( a n tc o l o n yo p t i m i z a t i o n ) 为一崭新的近似求解演算法， f l j d o r i g o ；m a n i e z z o 等学者于9 0 年代初期所提出，对于解决一些困难的组合 问题，已被证明有相当好的成效。蚂蚁族群算法的设计构想源自于蚂蚁觅食 的合作行为，与诸多模拟自然界现象的算法如：仿真退火、基因算法、禁忌 搜寻法等等一样，己成为一成功的自然算法，吸引了相当多学者的注意与关 切。自1 9 9 1 年d o r i g o 等学者，发表以蚂蚁系统成功解决旅行销售员问题后， 许多学者也纷纷投入相关之研究，并将蚂蚁族群最佳化的精神，应用于其它 组合问题上。然而我们相信此一优秀的解题策略之适用范围绝不仅止于此， 应该还有许多类型的问题，能够套用蚂蚁族群最佳化的精神而获得解决的。 本研究主要之目的在于：对蚂蚁族群最佳化进行深入之研究。除了详实 探讨蚂蚁族群算法的特性外，也针对新的组合问题提出了蚂蚁族群演算法， 以扩大蚂蚁族群最佳化的应用范圈；这包括了：最小节点覆盖问题、基地台 分配问题、远程扩张树问题与演化树建构问题。在最小节点覆盖问题中，我 们以子集合模式，取代既有的路径或树状模式寻求解答；在基地台分配问题 中则引用双向连接图形，及不同族群问的分工与合作束解题；在远程扩张树 问题中，则结合了子集合与树状模式，完成解答之搜寻；而在演化树建构问 题中，本研究提出了一图形表示方法，以解决该问题动态解答空间之特性。 此外本研究并针对一些以蚂蚁族群算法成功解题的问题，进行初步分析与归 类，试图提供往后学习者一解题设计的分类指引。 关键词蚂蚁族群最佳化；最小节点覆盖问题：基地台分配问题；远程扩 张树问题；演化树建构问题 哈尔滨理t 九学坤学绚i 学忙诊 t h e s t u d yo na n tc o l o n yo p t i m i z a t i o nf o rs o m e c o m b i n a t o r i a lp r o b l e m s a b s t r a c t t h ea n tc o l o n yo p t i m i z a t i o n ( a c o ) ，p r o p o s e db yd o r i g oe ta 1 i nt h ee a r l y 9 0 s i san e wm e t a h e u r i s t i ca p p r o a c ht os o l v eh 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 n p r o b l e m s j u s tl i k es i m u l a t e da n n e a l i n g ，g e n e t i ca l g o r i t h m s ，t a b us e a r c h ，e t c ， a n tc o l o n yo p t i m i z a t i o nh a sb e c o m eav e r ys u c c e s s f u ln a t u r a lm e t a - h e u r i s t i c a n dh a sa t t r a c t e dm a n yr e s e a r c h e r s a t t e n t i o n s i n c et h et s pw a ss o l v e db y d o r i g oe ta 1 1 9 9 1 ，m a n yr e f i n e dm o d e l sh a v eb e e np r o p o s e dt os o l v eh a r d o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s h o w e v e r ，w eb e l i e v et h a tt h ea c oa p p r o a c h e sc a n b ef u r t h e rg e n e r a l i z e da n da p p l yt om o r ec o m b i n a t o r i a lp r o b l e m s t h i sr e s e a r c h s h a l lt a k eat h o r o u g hs t u d yo na c o w es u r v e yt h ec h a r a c t e r i s t i c so ft h ea c o a l g o r i t h m sa n dp r o p o s eo u rd e s i g no fa c oa l g o r i t h m sf o rf o u rc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m si n t h i sp a p e r , i n c l u d i n gm i n i m u mw e i g h t e dv e r t e xc o v e r p r o b l e m ( m w v c ) ，c e l la s s i g n m e n tp r o b l e m ( c a ) ，r e m o t es p a n n i n gt r e ep r o b l e m ( r m s t ) a n de v o l u t i o n a r yt r e ec o n s t r u c t i o np r o b l e m ( e t c p ) i nm w v c ，w e f o u n das u b s e ti n s t e a do fap a t ho rt r e ei nag r a p ht oc o n s t r u c tt h es o l u t i o n i nc a w ei n t r o d u c e dt h ec o n c e p t so ft h eb i p a r t i t eg r a p hf o rp r o b l e mt r a n s f o r m a t i o na n d t h ed i v i s i o no fl a b o r st oe o o d i r a t et h ep o w e ro fc o l o n i e sw i t hd i f f e r e n ta b i l i t y i n r m s t ，w ec o m b i n e dt h ei d e a so fs u b s e ta n dt r e et of i n ds o l u t i o n s i ne t c p ，w e d e v e l o p e dap h e r o m o n er e p r e s e n t a t i o nf o rt h i sp r o b l e m ，w h i c hh a sad y n a m i c p r o b l e ms p a c e f u r t h e r , w eg a v eo u ra t t e m p t i o nt oc l a s s i f yt h ep r o b l e m sw h i c h a r es o l v e db ya c o a p p r o a c h e 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 ；m i n i m u mw e i g h t e dv e r t e xc o v e r p r o b l e m ；c e l la s s i g n m e n t ；r e m o t es p a n n i n gt r e ep r o b l e m ； e v o l u t i o n a r yt r e ec o n s t r u c t i o np r o b l e m i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文蚂蚁族群演算应用在组合 问题之研究，是本人在导师指导下，在哈尔滨理工大学攻渎硕士学位期间 独立遴行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果对本文研究工作做出贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果缛完全由本人承担。 作者魏掰淆吼伽6 - 易嘭 哈尔滨理工大学硕士学位论文使用授权书 蚂蚁族群演算应用在组合问题之研究系本人在哈尔滨理工大学攻渎 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归硷尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意乒校保留并融有 关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工 大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全鄢或 部分内容。 本学位论文属于 保密口在年解密后适用授权书。 不保密 作者签名：额沌蹶枷从f 6 岛妒“ 哈尔跨理丁大学弹学够卜学p 论史 第1 章绪论 一个算法的成功，在于能够正确且快速的解决人们所遭遇的问题。在先前 许多学者的努力下，已发展出许多知名且成功的算法，诸如：仿真退火、基因 算法、禁忌搜寻法等；而计算机硬件的快速进步，也使得这些算法能够在更短 的时间内，解决以往所无法负荷的大型计算问题。然而在人们所遭遇的问题， 依然存在着某些问题，其己知算法解题所需的时日j ，仍然随着问题的大小成指 数形式的成长，这一类问题便是众所周知的n p h a r d 问题。这一类问题，由于 求取最佳解的时间复杂度过高，通常我们不会花费如此冗长的时问去求得最佳 解，而希望在可接受时日j 内求得近似解。在这样的需求趋使下，造就了许多近 似解算法的发展空问。 1 1 研究背景及动机 在文献中，近似解法大致可概分为两类：第一类为经验式法则，即针对问 题特性，设计简单的决策方法；例如，在某些最短路径的问题中，一简单经验 式法则即是贪婪策略。第二类则是一些通用型概念，可适用于多种类型问题， 而这些解题策略通常取材自各种自然或科学等领域。近年来，人们对于取材自 自然界现象的算法兴趣与日俱增( m a n i e z z oa n dc o l o m i ，1 9 9 9 ) ，先前许多知名的 算法如：仿真退火( k i r k p a t r i c k , g e l a t ta n dv e c c h i ，1 9 8 3 ；v a nl a a r h o v e na n da a r t s ， 1 9 8 7 ) 、基因算法( g e n e t i ca l g o r i t h m ) ( o o l d b e r g1 9 8 9 ；s t e n d e r ，h i l l e b r a n da n d k i n g d o n ，1 9 9 4 ) 、禁忌搜寻法( t a b us e a r c h ) ( g l o v e r , 1 9 8 6 ；g l o v e ra n dl a g u n a , 1 9 9 7 ) 等纷纷在许多学者的研究下，有着辉煌的成果。然而学者们也抱持着怀疑：是 否存在着更精准或更有效率的解题策略? 为了职答这个疑惑，许多学苔纷纷朝 各种不同方向进行研究，企图能创造出更强力的搜寻策略，蚂蚁族群最佳化 ( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 便是在这样的环境下诞生。 蚂蚁族群最佳化为一崭新的求近似解算法，由d o r i g o ，m a n i e z z o 等学者 于9 0 年代初期所提r l ( d o f i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 1 ) 。其精神在于善用既 有的经验，并在可能的解答空间中探索新的可能解答以及改善既有解答，以反 复的自我改善过程逼近最佳解。对于解决一些围难的组合最佳化问题如：旅行 销售员问题f r s p ) 、( d o r i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 1 ) 、二次分派问题 ( 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 ) ( m a n i e z z o 。c o l o m ia n dd o f f g o ，1 9 9 4 ) 略尔 声坪t 夫学珲学垧t 学p 论 等，已被证明有相当好的成效。与诸多以自然界现象为譬喻的算法如：仿真退 火、基因算法等相同，蚂蚁族群算法也是一成功的自然算法，并吸引了相当多 学者的注意与关切。自1 9 9 1 年d o r i g o 等学者发表以蚂蚁系统成功的解决旅 行销售员问题后，许多学者也纷纷投入相关之研究，并试图将蚂蚁族群最佳化 的精神应用于其它类型的问题上；研究成果请参阅：( c o l o m i d o r i g oa n d m a n i e z z o 1 9 9 2 ；d o r i g oa n dg a m b a r d e l l a ，1 9 9 6 ；d o r i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 6 ； d o r i g oa n dg a m b a r d e l l a ，1 9 9 7 ；s t u t z l ea n dd o r i g o ，1 9 9 9 ；w a g n e r ，l i n d e n b a u m , m i c h a e la n db m c k s t e i n ，2 0 0 0 ；m a n i e z z oa n dc a r b o n a r o 2 0 0 0 ) 。然而此一优秀的解 题策略的适用范围，绝不仅止于此，相信仍育一些其它性质的问题，也能够套 用蚂蚁族群最佳化的精神而获得解决的。 1 2 研究问题 与其它以自然界现象为譬喻的算法，如：仿真退火( 1 9 8 3 ) 、禁忌搜寻 ( 1 9 8 6 ) 、基因演算法( 1 9 8 9 ) 相较，蚂蚁族群最佳化足较晚被提出的策略。因此 在于此策略性质上的研究与应用的开发起步也较晚，除目前已发表的文献外， 是否仍有未被开发的性质，或是新类型的问题应用未被发掘? 对于研究算法的 人们来说，相信这些问题是值得深入探讨的。而对于其它学科的人们来说，是 否也有些问题一直悬而未决；或是因科技的r 新月异而发现了一些新的问题， 却尚未有良好的解决方案而正寻求新的解题策略? 这些问题是否可被蚂蚁族群 算法妥善地解决就以上因素看来，本研究认为虫i 5 蚁族群算法仍有相当大之研究 发展空日】与价值：或朝新的应用问题发展以解决人们生活上的困难，或完整研 究与整理其性质以提供后人研究之依据，这部是可能的贞献。本研究所要探讨 之议题如下： 蚂蚁族群算法的特质为何? 蚂蚁族群算法之应用范围为何? 就不同问题类型，若要应用蚂蚁族群算法是否能有一指引? 为解答以上议题，本研究除以文献之探讨与分析外，并且将蚂蚁族群算法 于新的问题上，如：最小权重节点覆盖问题，基地台分配问题、远程扩张树、 演化树建构等问题，并提供完整之实验与分析，期能提供新的应用与解题指 引。 哈尔滓珲丁久学即擘师 ，管帕诊丈 1 3 研究目的 本研究主要目的在对蚂蚁族群最佳化算法作深入之研究与探讨，以印证蚂 蚁族群算法之成效。这将包含了针对蚂蚁族群最佳化性质的研究，以及新的应 用之开发。因此除了针对已发表之文献作一整理外，亦将对前一节所提之应用 问题，分别设计适合之蚂蚁族群算法进行求解实验：及将实验结果与该问题之 现有解法进行比较，以验证蚂蚁族群算法在这哆新j 口j 题上之适用性。并藉由文 献之研究与实验之印证，以更进一步了解蚂蚁族群算法之特质。 除此之外，本研究所提出的蚂蚁族群算法，可提供上述应用问题一个新的 解题途径；使得人们得以在有限时间内，取得品质更为优良之近似解答。最 后，针对上节所提之第三个议题，本研究希埋能将蚂蚁族群最佳化之应用范 围，作一初步分类。期能提供往后面临该类问题时之解题指引，相信对于学界 及实务界皆能有所助益。 哈尔演理t 夫学理学磅f 学位论文 第2 章文献探讨 本研究以蚂蚁族群最佳化为主体，讨论其对于一些困难的组合问题之应用 成效，因此应先对蚂蚁族群最佳化及其相关应用做探讨与整理。 2 1 蚂蚁族群最佳化 蚂蚁族群最佳化乃由c o l o r n i ，d o r i g o 与m a n i e z z o 于1 9 9 1 年所发表，最 初运用于解决旅行销售员问题，其后也成功的运用于其它类型的问题上。许多 学者均在这方面贡献不少心力，其中d o r i g o 所发表的一系列文章，如： ( d o r i g o a n d g a m b a r d e l l a , 1 9 9 6 ；d o r i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 6 ；d o r i g o ， g a m b a r d e l l a , 1 9 9 7 ；s t u t z l ea n dd o r i g o ，1 9 9 9 ) 等，可说足学习蚂蚁族群最佳化的良 好途径。( d 硎g o ，b o n a b e a ua n dt h e r a u l a z ，2 0 0 0 ) 也针对蚂蚁族群最佳化的应用作 完整的整理。这些文献均有助于我们对蚂蚁族群最佳化的了解。 2 1 1 蚂蚁族群 在自然界不断演化下，自然界中虫1 5 蚁族群已发展出一套完整且有效率的社 会体系。b e c k e r s 、d e n e u b o u r g 与g o s s 在1 9 9 2 年发表的文章( b e c k e r s ，d e n e n b o u r ga n dg o s s ，1 9 9 2 ) 中指出，自然界的虫l5 蚁能够不依赖视觉的辅助，只须依靠 种称为“费洛蒙”( p h e r o m o n e ) 的化学物质，再透过蚂蚁间共同合作，便能寻 找出蚁巢与食物间最短路径。纵使每一只虫l j 蚁个体几乎都是相同的：每只蚂蚁 所残留的费洛蒙数量相近，每只蚂蚁行进的速度相当，每只蚂蚁受费洛蒙左右 其行为的程度也相同。 蚂蚁此种合作的行为在( d o r i g oa n dg a m b a r d e l l a , 1 9 9 7 ) 的研究中有更佳的诠 释。请参见图2 1 的图标：原本从蚁巢到食物| 目j 的路是畅通的，如图2 - 1 a ；一 旦在路面上突然出现了障碍物的阻挡，如图2 一l b ：此时在障碍物两端的蚂蚁必 须决定要向左转或向右转以继续前进。在此，我们假设每只蚂蚁选择左边或右 边的机率是相等的，因此向左及向右的蚂蚁数量几乎是一样多的。但此时较短 的一端因为较快能到达目的地，同样地也较快回到蚁巢，因此费洛蒙累积的速 度也较快，如图2 1 c ；最后在虫- j 蚁追随较高费洛蒙的习性下，较短的路径因为 有较高的费洛蒙浓度，吸引了大多数的虫j 蚁选择该路径；而较多虫号蚁行走，又 使得费洛蒙累积更为快速。在这种正向p 1 馈( p o s i t i v ef e e d b a c k ) 的运作下，在一 哈尔派理t 大学理学磅i 学倍诒定 段时间后，几乎所有的蚂蚁都会选择相同的一边日u 进，如图2 1 d 。 - - 蚁巢 一 食物 二o 警咭螭鲰一 ：一_ ， q l b q t - 皇 一- ir 帚- 一 障碍物 图2 - l 自然界蚂蚁的觅食行为图 f i g2 - lt h eb e h a v i o rd i a g r a mo f l o o k i n gf o rf o o do f n a t u r a la n t 2 1 2 人工蚂蚁 研究蚂蚁族群问这种自我组织而能搜寻出最短路径的能力，对于电脑科学 有相当的助益；亦即这种自然界的搜寻能力，似乎有助于人们搜寻最佳解的过 程。只是，在将自然界蚂蚁转化进入电脑系统时，我们该如何保留住某些特 性，使得人工蚂蚁也具有如此优秀的搜寻功能呢? ( d o r i g oa n dg a m b a r d e l l a ， 1 9 9 7 ) q ，提及了以人工蚂蚁模拟自然界蚂蚁行为的三大关键特性： 1 蚂蚁倾向于选择具有较高费洛蒙的路径； 2 对于较短的路径，其费洛蒙累积的速度较为快速； 3 蚂蚁透过费洛蒙达到f b j 接沟通的效果。 我们不难发现，这些特性都环绕着一个主题：“费洛蒙”。如同自然界中 的蚂蚁，费洛蒙足蚂蚁间间接沟通的工具：也好比人类社会中经验的传承，先 前走过该路径的众多蚂蚁，透过费洛蒙指引往后的蚂蚁们是否选择该路径继续 前进。然而人工蚂蚁也并非是全然模拟自然界虫1 5 蚁的生活模式，毕竟我们的目 标在于透过模拟蚂蚁而达到将求解最佳化之效果。在电脑系统中的蚂蚁，至少 与自然界的蚂蚁会有以下差异( d o r i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 1 ) ： 1 人工蚂蚁将有自己的记忆空日j ； 2 人工蚂蚁不会是全然盲的，即存在着除费洛蒙外的指引； 哈尔泞碑t 赶学珲肇崎 学柑冷定 3 人工蚂蚁所生存的环境，其时间足离散的。 而d o r i g o 与g a m b a r d e l l a 也建议，为了能够获得良好的解甚或足最佳解， 人工蚂蚁必须能够参考过去所经历过的较佳路径，这种行为称为“丌发”，同 时也要能够发现之前未曾尝试过的解答组合，这种行为可称之为“探索”。开 发的功用主要在于改善既有的解答，但此行为有可能被局限于区域最佳解的状 态而无法脱出；若能辅以探索机制使其跳脱至另一未曾尝试过的解答空间，便 能有更多机会以寻求更佳之解答。图2 2 可以说明这两种行为的效果，如何有 效运用这两种机制，使得蚂蚁演算法能够更青效率的逼近最佳解，足在设计人 工蚂蚁族群如何运作时所不可或缺的考基。 现在解 探索 图2 - 2 开发b 探索示意图 f i g2 - 2d e v e l o p m e n ta n di n v e s t i g a t e 综合以上分析，设计人工蚂蚁需完成以下三项工作： 1 制定状态转移规则：此状态转移患指当蚂蚁在建构一解答时，选择某 一解答元素前后状态之转移。以旅行销售员问题为例，则是指选择下一城市时 供蚂蚁依循的机制。而当蚂蚁由一状态进入下一状态时的依据，则需考虑开发 与探索的所占比重，以及如何运用费洛蒙以及适当的启发函数。启发函数的引 用意在指引蚂蚁朝向较短路径( 较佳解) 移动：丌发与探索、费洛蒙的变化与启 发函数的指引相互间的影响即决定求解的效率以及收敛的趋势。( m a n e z z oa n d c o l o r n i 1 9 9 9 ) 曾指出：过高的费洛蒙权莺之设定，容易使得蚂蚁们在取得最佳 解之前陷入停滞不前。相对的，过低则使得费洛蒙的效果不易显现，即过于偏 袒启发函数的效果，也容易陷入函数所引导的区域最佳解。 哈尔泞砰t 大学珲学砷i 学付诊史 2 建立问题限制：许多问题本身育着严格的限制，若违反了这些限制， 便不算是一个可行解。必须存在某种机制，使得人工蚂蚁在求解过程中所得的 解答，能够符合问题的限制。若缺乏此机制，将使得人工蚂蚁耗费许多时| 日j 去 取得不合法之解答，徒然耗费系统资源，影响求解效率。以旅行销售员问题为 例：同一个城市只能拜访一次而不得莺复，因此每只蚂蚁需有自己的区域记忆 空日j ，以纪录拜访过之城市，避免重复拜访情形发生。 3 设计费洛蒙异动规则：自然界虫t j 蚁透过费洛蒙进行日j 接沟通，而我们 设计的人工蚂蚁也盼望着能透过费洛蒙进行日j 接沟通，进而取得较佳之解答。 在先前的文献中，费洛蒙异动的策略可包含下列三种： 1 ) 区域更新：只要有蚂蚁走过的路径，即改变路径上的费洛蒙。区域更 新的主要精神在于避免产生个过于强势的路径，吸引所有的蚂蚁走上该路径， 如此无法进行适当的探索新路径动作，而影响所得解答的品质。 总体更新：针对每回合取得最佳解答的路径改变其费洛蒙；在此回合 是指所有人工蚂蚁均取得一可行解的时f s 】。总体更新的精神则在于对于好的解 答给予奖赏，以引导蚂蚁依据这些路径进行开发及探索。d o r i g o 指出总体更新 有两种方式实施：回合最佳与总体最佳，前告指针对“每回合所得解答中最好 的路径”进行增加费洛蒙的动作；后告指则在“截至目前所获得的解答中，针 对最好者的路径”进行费洛蒙更新。但在( d o r i g oa n dg a m b a r d e l l o ，1 9 9 7 ) 针对 t s p 的实验中指出，二者所得效益相差不大。 3 ) 费洛蒙蒸发：与自然界的现象相同，蚂蚁留置于地面的费洛蒙会随着 时间而蒸发。蚂蚁族群最佳化进行费洛蒙蒸发的目的，在于避免某些路径上费 洛蒙无限量的累积，使得蚂蚁有机会探索其它解答：另一方面也是让人工蚂蚁 族群可对于曾经取得的可行解，在时间经过后，未再有其他蚂蚁经过而获得费 落蒙累积的情况，能适时的遗忘。设定过高的费洛蒙蒸发率将使得求解经验无 法累积，大幅降低费洛蒙所应有的功用，进而拖垮系统取得解答的效能 ( m a n i e z z oa n dc o l o m i 。1 9 9 9 ) 。决定适当的费洛蒙累积率，将有助于取得解答的 效能与效率。 2 1 3 搜寻精神 在了解蚂蚁族群最佳化的元素人工蚂蚁后，接着再探讨蚂蚁族群最佳化的 搜寻精神：分散计算，正向回馈及建构式启发法则( d o r i g o ，m a n i e z z oa n d c o l o r n i ，1 9 9 1 ) 。 哈尔涫珲丁大学邱学母卜学仲论吏 1 分散计算：一只孤立的蚂蚁虽然也同样受费洛蒙影响，但所面临的选 择却较为有限，容易将选择集中在某些特定路径上。分散计算以多数蚂蚁于不 同起点出发增加探索的可能性，则可避免过早选择完全相同之路径，即所谓过 早收敛。 2 正向回馈：正向回馈是一种可自我加强的过程，即所谓自动催化的行 为。将使得原本较多蚂蚁选择的路径，吸引更多的蚂蚁i j 来，这也是许多强化 学习演算法，这种正向回馈过程本身具备能快速取得相当好之解答的能力。 3 建构式启发法：一般最普遍使用的为贪婪法则。这种做法便是要在短 时间内建构出可行解，可以快速的在解题过程初期，便提供一不算太差的解。 如此做法可避免早期浪费时间进行无效的搜寻，加速解题过程之进行。 2 1 4 蚂蚁族群演算法 将蚂蚁族群最佳化的通用法则应用于特定问题中，完成人工蚂蚁的搜寻设 计，即成就了蚂蚁族群演算法或简称蚂蚁演算法。我们将蚂蚁族群演算法设计 的关键因素，再详细予以说明。 首先必须能将问题转化成能让人工蚂蚁在其上寻找解答的特定模式，通常 为一图形( 或排列等模式) ，使得人工蚂蚁能够在其上行动，以求得可行解。 此步骤与问题特性高度相关；除了需考虑问题本身的限制外，如何让费洛蒙代 表解答元素成为最佳解的可能性，则是相当不容易，而这更可说是整个蚂蚁演 算法是否成功的关键因素。适当的问题表达模式，将使蚂蚁族群演算法更能有 效率地寻找解答。 其次则需找到能指引人工蚂蚁寻求最佳解的启发函数，启发函数的功用在 指引蚂蚁求解。根据不同问题的需求，启发函数在蚂蚁系统的应用可区分成静 态与动态两类：静态指一旦代表问题的模式确立后，其值只需经过一次计算便 不再更动；而动态则随着求解过程的进行需萤新计算。 接着便是决定人工蚂蚁间如何互动，办即制定整个系统的自动催化过程。 这包含了费落蒙异动及状态转移规则的制定；费落蒙除了是人工蚂蚁问接沟通 的媒介，也扮演着系统经验累积的角色，更足蚂蚁族群最佳化运作的精神所 在。在系统运作过程中，费落蒙将指引着人工蚂蚁寻求较佳的解答，而人工蚂 蚁也留下费落蒙以指引以后的蚂蚁朝具有较佳解的区域移动，以能取得更佳的 解答。 在此必须注意的事，便是问题限制式的满足。除了能在刚开始将问题模式 哈尔演理丁夫学珲学垧t 哮付论文 化时就隐含进去的限制外，通常还会有些限制是较难化为特定模式的一部份。 此时，便须靠人工蚂蚁自己的区域记忆空间或处理程序去让所找到的解答是符 合问题限制的可行解。 在完成了以上步骤后，才能顺利的运用蚂蚁族群演算法解题。而蚂蚁族群 演算法也能不负所托，通常能够寻找到一个足够好甚至足最好的解答。本论文 蚂蚁族群演算法的基本程序如下。 i n i t i a l i z e l o o p + e a c hl o o pi sc a l l e da ni t e r a t i o n e a c ha n ti sp o s i t i o n e do na s t a r t i n gp o i n t l o o p + e a c hl o o pi sc a l l e ds t e p e a c ha n ts e l e c ta ne l e m e n ta d dt oi t ss o l u t i o n l o c a lp h e r o m o n eu p d a t i n gr o l e u n t i la l la n t sb a r eb u i l ta c o m p l e t es o l u t i o n al o c a ls e a r c hi sa p p l i e d7 + o p t i o n + a g l o b a lp h e r o m o n eu p d a t i n gr u l ei sa p p l i e d u n t i 】e n dc o n d i t i o n 蚂蚁族群演算法之虚拟码，可表示如下 p r o c e d u r ea c o _ m e t a h e u r i s t i c o w h i l e ( t e r m i n a t i o n _ c r i t e r i o n n o t s m i s f i e d ) s c h e d u l ea c t i v i t i e s a n t s _ g e n e r a t i o na n da c t i v i t y ( ) ； p h e r o m o n e _ e v a p o r a t i o n ( ) ； d a e m o n _ a c t i o n s ( ) ； e n d _ s c h e d u l e _ a c t i v i t i e s e n d _ w h i l e e n d _ p r o c e d u r e p r o c e d u r ea n t sg e n e r a t i o na n da c t i v i t y ( ) ； w h i l e ( a v a i l a b l e _ r e s o u r c e s ) s c h e d u l e t h e c r e a t i o n o f a n e w a n t ( ) ； n e w _ a c t i v e _ a n t ( ) ； e n dw h i l e 哈尔演理t 大学坪学绚 学忙论文 e n dp r o c e d u r e p r o c e d u r en e w _ a c t i v e _ a n t ( ) ； i n i t i a l i z e _ a n t ( ) ； m = u p d a t e a n t m e m o r y ( ) ； w h i l e ( c u r r e n t _ s t a t e - - t a r g e ts t a t e ) a - - r e a d _ l o c a l _ a n t m u t i n gt a b l e ( ) ； p = e o n p u t et r a n s i t i o np r o b a b i l i t i e s ( a ，m ，q ) ； qd e n o t e st h ec u r r e n tc o n s t r a i n t st ot h ep r o b l e m n e x ts t a t e = a p p l y _ a n t _ d e c i s i o n _ p o l i c y ( p 。q ) ； m o v et ot h en e x ts t a t e ( n e x t _ _ s t a t e ) ； i f ( 1 0 c a l p h e r o m o n eu p d a t e ) d e p o s i t _ p h e r o m o n eo nt h ev i s i t e da r c 0 ； u o d a t e _ a n t - r o u t i n g _ t a b l e o ； e n d _ i f m - - u p d a t ei n t e r n a l _ s t a t e ( ) ； e n d w h i l e l f ( g l o b a lp h e r o m o n e _ u p d a t e ) ； f o r e a c hv i s i t e d _ a r evd o d e p o s i tp h e r o m o n eo nt h ev i s i t e d _ a r c ( ) ； u p d a t e _ a n t - r o u t i n g _ t a b l e ( ) ； e n d f o e a c h e n d _ i f d i e o e n dp r o c e d u r e 其中步骤为建构一可行解的子程序，如在t s p 中则为城市到城市问的一次 移动。回合则为所有人工蚂蚁均取得一解答之时日j ：区域搜寻用以将目前解答 改进至区域最佳解的状态，一般常使用如2 - o p t 、3 - o p t 等方式( d o r i g oa n d g a m b a r d e l l a , 1 9 9 刀。适当使用区域搜寻可增加丌发效率，并促使蚂蚁族群演算 法更容易找到最佳解；当然这并 一定得使用，如：d o r i g o 与g a m b a r d e l l a y 于 1 9 9 6 年所提之a c s 与a c s 3 c p t ，无论足对称与非对旅行销售员问题，二者 称均能得到相当好的懈答。而结束条件可设定为执行最大回合数或所使用的中 央处理器时间，或是两次解答改进日j 之最大回合数，可视问题及个人需要而加 哈尔演理t 夫学柙7 垧t 学”论丈 以设定。 2 2 蚂蚁族群最佳化的应用 表2 1 列出许多蚂蚁族群最佳化的应用及其出处，以下本研究将针对一些 具代表性问题的蚂蚁族群演算法设计加以描述。 表2 一l 蚂蚁旅群最佳化府用问题 t a b l e 2 - 1a n tc o l o n yo p t i m i z a t i o na p p l i e dp r o b l e m n e t w o r kr o u t i n g s u b r a m a n i a n ，d r u s c h e la n dc h e r t1 9 9 7 ，c a r oa n d d o r i 9 0 1 9 9 7 ，c a r oa n dd o f g o1 9 9 8 b o n a b e a u ，h e n a u x , g u e r i n 。s n y e r s , k u n t za n dt h e r a u l a z1 9 9 8 ，v a r e l aa n d s i n c l a i r1 9 0 9 坠塑q 旦i 翌g 翌垒! 曼塑鉴坚旦! 互：型z 剑! 璺璺垡兰盟y 曼垡：! ! 1 2 s e q u e n t i a lo r d e r i n gp r o b l e m g a m b a r d e l l aa n dd o r i g o , 1 9 9 7 m u l t i p l ek n a p s a c kl e g u i z a m o na n dm i c h a l e w i c z , 1 9 9 9 c o n s t r a i n ts a t i s f a c t i o ns c h o o f sa n dn a u d t s 。2 0 0 0 g r a p h t r a v e r s a l w a g n e ll i n d e n b a u sa n db r u c k s t e i n ，1 9 9 6 ，w a g n e r b r u c k s t e i n1 9 9 9 鱼! ! 盟! i 垄4m 丛虫型! ! 生卫生l 虫! 四奠垫塑出；鲤! 堂堂! 型! ! 翌! 塑 n y ! ：! 也垫g ! 丛2 q 1 2 型! 函g 里匹磐! 磐n y ! = ! 也8 四h ：i g 当z q q 2 以下各小节则分别讨论一些重要组合问题的定义，针对蚂蚁族群演算法作 扼要说明。 2 2 1 旅行销售员问题 旅行销售员问题为蚂蚁族群最佳化最仞所应用的问题。此问题即一地区有 若干城市，城市问有道路相连，而道路本身有距离远近之分：今可由任一城市 出发，途中需经过所有城市且不得重复，最后要回到原出发之城市，而其目标 则在求此一旅程的最短距离。蚂蚁系统( a n ts y s t e m 简称a s ) ( d o r i g o ，m a n i e z z o a n dc o l o m i 。1 9 9 1 ) 在状态转移规则的设定如下： 哈尔滨理丁大学珲学砷t 学。诒艾 最( ) = r ( 邶) r _ ( ) r r ( r ，“) 。 ，7 ( r ，”) 4 ”t 盯 o s 芒m k 其他 其中，只( r ，j ) 为蚂蚁i 在城市r 是选择走到城市j 的机率，r ( r ，s ) 为道路( s ) 上的费洛蒙，r ( r ，j ) 为，帆为蚂蚁七的禁忌列表，记录已拜访过的城市。我 们可以发觉这是一种有权重的机率模式，距离较短且累积较高费洛蒙的路线被 选择的机率较高。而在a s 时还未加入区域更新功能，仅针对所有路径执行总 体更新，其费洛蒙更新原则如下： f ( f + 1 ) = ( 1 一p ) ( ，) + 乃( ，+ 1 ) ， 勺( ，) = 芍( ，) ， 。硝归 南( f ，加r ) 【0 其他 其中p 为费洛蒙蒸发率，t 为回合数，为蚂蚁所得解答总长度，则为蚂 蚁k 所得的解答。依据d o r i g o ( d o r i g o ，m a n i e z z oa n dc o l o m i ，1 9 9 1 ) 实验资料可 发现，a s 比其他自然演算法，如：基因演算法，更能获得较佳之解答。 在a s 后，许多改良型态的演算法也纷纷产生d o r i g o ( d o r i g oa n d g a m b a r d e l l a ，1 9 9 7 ) 所提之蚂蚁族群系统( a n tc o l o n ys y s t e m ，简称a c s ) 与蚂蚁 族群系统配合区域搜寻版本( a n tc o l o n ys y s t e mw i t h3 - o p t ，简称a c s 3 o p t ) ，其 主要改变部分为： 1 状态转移规则：提供一直接管道予丌发功能。即增加一鼋。变数，使得 在0 至l j q o 的机率下直接选择最高机牢者，办即： 哈尔谆理t 大学珲学硕l 擘抽诒史 其中 ，：扣鼢) ，s ) n g 吼 ie ( ) 其他 只( ， j ) = 2 总体更新仅针对隶属于回合最佳或总体最佳的路径执行。 3 于建构解答同时进行区域更新。 4 加入区域搜寻3 - o p t 。 至此，蚂蚁族群演算法整体架构已经定型，往后之变化则在于费洛蒙更新 策略及数量的改变，以及针对启发函数作变动。如：a n t ，q ( d o r i g oa n d g a m b a r d e l l a ，1 9 9 6 ) 结合q 1 e a r n i n g 精神，修改费洛蒙增加量；m a x m i na n t s y s t e m ( 简称m m a s ) 则设定所有费洛蒙的最小及最大值，以避免选择路径过于 集中，以增加发现新路径的机会。但在众多针对旅行销售员的蚂蚁族群演算法 中，a c s 的总体表现仍可说是凌驾于其他版本之上( d o r i g o ，d ic a r oa n d g a m b a r d e l l a ，1 9 9 9 ) 。 2 2 2 二次分派问题 二次分派问题( q a p ) d - i 解释为：将n 个设备分派给 个地点，设备问本身 有相互的流量需求：地点间则存在着彼此距离不同的状况，目标则是使分配后 距离乘以流量之和的成本值为最低。在此设备与地点可视为更一般化的概念， 如设备可以是建筑物、工作单位等，而地点也可以是位置，或机器等。许多问 题都可化为二次分派问题，如：厂房规划、校区建筑舰划、电路规划等。 继旅行销售员问题后，蚂蚁族群最佳化便应用在二次分派问题上。产生了 二次分派的蚂蚁系统( a n ts y s t e