（通信与信息系统专业论文）蚂蚁算法的优化及其在atm网络路由选择中的应用.pdf

摘要 摘要 蚂蚁算法是一种新型的分布式模拟进化算法，广泛用于求解组合优化 问题，如分配问题、调度问题、图着色问题等，并且取得了很好的效果。 但蚂蚁算法与遗传算法等其他模拟进化算法一样，存在着收敛速度慢，容 易陷入局部最优等缺陷，如何克服这些缺陷成为该算法的研究热点之一。 本文首先从典型的组合优化问题旅行商问题出发，介绍了蚂蚁算 法提出的理论背景，并通过该问题建立了基本蚂蚁算法的模型。对于目前 已经提出的改进算法，本文作了简要介绍。 随后，本文对算法进行了以下两个方面的优化： 第一，在大量仿真实验的基础上，本文深入研究了蚂蚁算法搜索空间 与收敛性的矛盾，总结了算法本身的参数对于实验结果产生的影响，并提 出了动态调整参数的蚂蚁算法，在相同的试验次数内，获得了对应于原算 法更好的最优解； 第二，从影响算法的关键参数信息素出发，通过对其进行实时监 控，利用智能判断机制和削弱因子，有效的避免算法陷入局部最优，并提 出了引入局部搜索的智能型蚂蚁算法，利用更少的试验次数，获得了满足 同样条件的最优解。 通过对实验结果的比较，证明本文所提出的两种方案是可行且有效的。 最后，本文简要介绍了异步传输模式( a s y n c h r o n o u st r a n s f e rm o d e ， 简称a = n 山网络中交换虚信道的分配特点，并对于给定的网络拓扑结构和用 户的服务质量要求，将优化后的算法运用于交换虚信道分配之中。仿真实 验表明，优化后的算法能够有效的实现a t m 网络的路由选择。 关键词蚂蚁算法；旅行商问题；a t m 网络；交换虚信道；服务质量 燕山大学工学硕士学位论文 a b s t r a c t a n ta l g o r i t h mi san o v e ld i s t r i b u t e ds i m u l a t i v ee v o l u t i o n a la l g o r i t h m i ti s w i d e l ya p p l i e d t os o l v ec 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 s u c ha s d i s t r i b u t i o n , s c h e d u l e ra n dg r a p hc o l o r u pe t c ，a n dq u i t eg o o dr e s u l t s a r e o b t a i n e d b u ta n ta l g o r i t h ma p p e a r sl o wc o n v e r g e n c es p e e da n ds t a g n a t i o n l i m i t a t i o n j u s ta sg e n e t i ca l g o r i t h ma n d o t h e re v o l u t i o n a la l g o r i t h m n o wh o w t oa v o i dt h o s el i m i t a t i o n si saf o e l l so f t h ea l g o r i t h m b e g i nw i t ht s p ( t r a v e l i n gs a l e s m a np r o b l e m ) ，at y p i c c 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 ；i n t r o d u c et h e t h e o r e t i c a lb a c k g r o u n d so fa n t a l g o r i t h m ； a n ds e tu pab a s i cm o d e lv i at h i sp r o b l e m t h ep r e s e n ti m p r o v e da l g o r i t h m sa r e i l l u s t r a t e di nb r i e f t h e n o p t i m i z e t h ea l g o r i t h mf r o mt h ef o l l o w i n gt w oa s p e c t s ： f i r s t ，s t u d yt h ec o n t r a d i c t i o nb e t w e e ns e a r c h i n gs p a c ea n dc o n v e r g e n c e s p e e d ，b a s i n go nag r e a td e a l o fs i m u l a t i o n s ，a n dc o n c l u d et h ei n f l u e n c eo n e x p e r i m e n t a l r e s u l t so fa l g o r i t h m s p a r a m e t e r s p r e s e n tp a r a m e t e r - a d j u s t i n g d y n a m i c a l l ya l g o f i t h r aa n dg a i nb e t t e ro p t i m i z a t i o nt h a nf o r m e ro n e so nt h e s a m e e x p e r i m e n t a l t i m e s e c o n d ，b e g i n n i n g w i t ht h e k e yp a r a m e t e r - p h e r o m o n e ，r e a l - t i m e m o n i t o r i n g ，u s i n gi n t e l l i g e n tj u d g i n g m e c h a n i s ma n dw e a k e n i n gp a r a m e t e rc a n a v o i de f f i c i e n t l ys t a g n a t i o nl i m i t a t i o n i n t e l l i g e n ta n ta l g o r i t h mi m p o r t i n g l o c a l s e a r c h i n gi sp r e s e n t e da sw e l l ，a n dt h u so p t i m a ls o l u t i o nm e e t i n gt h e s a m e c o n d i t i o nc a nb eo b t a i n e dw h i l ev i al e s se x p e r i m e n t t i m e s b yc o m p a r i n g t h e e x p e r i m e n tr e s u l t s , t h et w o - p r e s e n t e ds c h e m e s a r e t e s t i f i e dt ob ef e a s i b l ea n de f f i c i e n t a tl a s t , t h ea l l o c a t i o nc h a r a c t e r i s t i cs v c ( s w i t c h e d v i r t u a lc i r c u i t ) i nt h e a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) n e t w o r ki s s h o w e di nb r i e f a p p l yt h e o 口t i m i z e da l g o r i t h mt ot h es v ca l l o c a t i o na c c o r d i n gt o t h eg i v e nn e t w o r k f r a m e w o r ka n dc l i e u t ss p e c i a lq o s ( q u a l i t y o fs e r v i c e ) n e e d s i m u l a t i o n s n a b s t r a c t s h o wt h a to p t i m i z e da l g o r i t h mc a nr e a l i z ei ne f f e c tt h er o u t i n gs e l e c to ft h e a t mn e t w o r k k e y w o r d sa n ta l g o r i t h m ；t s p ；a t mn e t w o r k ；s v c ；q o s 第l 章绪论 1 1引言 第1 章绪论 计算机的出现无疑是人类历史上的重大事件，它极大地推动了科学技 术的发展，并彻底地改变了世界的面貌。今天，计算机已经成为人类生存 与发展的必要工具，它正在人们的生活中发挥者越来越重要的作用。 计算机科学涉及到很多领域，其中的一对重要概念就是算法与程序。 下面我们首先给出算法的概念： 算法是指可用来求解某一问题的、带有一般性的一步一步的过程。它 是用来描述可在许多种计算机上实现的任一计算流程的抽象形式，其一般 性可以超越任何具体实现时的细节f 1 。 具体地说，算法是由若干条指令组成的有穷序列，它满足如下性质 2 1 ： ( 1 ) 有零个或多个由外部提供的量作为算法的输入； ( 2 ) 算法产生至少一个量作为输出； ( 3 】组成算法的每条指令是清晰的，无歧义的： ( 4 ) 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有 限的。 程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序 可以不满足算法的性质( 4 ) 。 举一个直观的例子，有利于我们对两者的区别比如操作系统，它 是一个在无限循环中执行的程序，因丽不是一个算法。然而我们可以把操 作系统的各个任务看成是一些单独的问题，每一个问题由操作系统中的一 个子程序通过特定的算法来实现。该予程序得到输出结果后便终止。 在这里，引入了问题的概念。所谓一个问题是指有待于回答的，通常 含有几个自由变量的一个一般性提问。问题一般由两部分决定；一是对其 所有参数的一般性描述；二是对该问题的答案所应满足的某些特性的说明。 而一个问题的某个例子可通过指定问题中所有参数的具体取值来得到。 1 垄些奎主三主堡主鲎壁笙兰 在本章下一节的叙述中，我们将简要介绍算法复杂性理论，旨在说明 蚂蚁算法提出的理论背景。 1 2 算法复杂性分析 1 2 1 算法度量值 上一节我们引入了“算法”和“问题”的基本概念，我们还应看到， 求解某一问题的不同算法在时间、空间上相差很大，即使同一算法，当其 用来求解同一问题的不同实例时，其性能表现差异也较大。由于实际问题 的千变万化，不仅对不同的问题往往设计不同的算法，且同时又想用同一 算法去尽可能多的求解不同类型的问题。那么，如何解释这错综复杂，多 种多样的现象呢? 能否给出一个一般的划分与衡量标准，以区分不同问题 的难易程度、度量不同算法有效性之间的差异呢? 广义的讲，一个算法的有效性可以用执行该算法时所需要的各种计算 资源的量来度量。最典型、也是最主要的两个资源就是所需的运行时间和 内存空间。不过，人们通常总是将最快的算法与最有效的算法等同起来， 这是因为时间需求常常是决定某一特定算法在实际问题中是否真正有用和 有效的决定性因素。因此，在复杂性研究中，衡量一个算法的效果，最广 泛采用的标准是在产生最终答案前它所花费的时间，并常常称复杂性为时 间复杂性。但是，我们知道，由于计算机速度和指定系统的不同，阃一算 法所需时间多少随着计算机不同可能有很大的差别。为使其具有一般性弗 在实际中有用，所给的时间度量方法就不应该依赖于具体机器。同时，即 使同一算法和同一计算机，当用它来求解某一问题的不同例子时，由于有 关参数取值的变化，使得所需运行时间也有较大差别，如何恰当的反映这 一差别也很重要。对于这两方面的问题，我们可分别用下述方法解决。 首先。通过探讨实际中已有或可能会存在的不同形式计算机的本质与 核心部分，并对其加以抽象，人们提出了一些简单而又能恰当反映绝大多 数计算机之基本运作原理的计算模型，如各种形式的圈灵机，随机存取机 等，然后基于这些计算模型来研究算法，进而为避免这些不同模型对运行 2 第1 章绪论 时间的影响，人们假设每做一次初等运算均需要一个单位时间，由此用算 法在执行过程中总共需要的初等运算步数来表示算法用于求解任一问题的 某一例子时所需要的时间。这里所谓的初等运算是指算术运算、比较和转 移等基本操作。 其次，为了恰当描述不同例子之间的差别和算法的运行时间随例子的 不同而发生变化的方式，人们引进了问题例子大小的概念。所谓一个问题 例子的大小是指为描述或表示它而需要的信息量。只要表示合适，可望例 子大小的值应该与其求解的难易程度成正比，并称相应的表示方法为编码 策略。通常所谓的合理编码策略应满足两个基本要求，即可解码性与简洁 性。 实际中，只要按照自然的常规与约定，则不难找到满足上述要求的合 理编码策略。一个典型的方法就是利用所谓的结构化字符串，通过递归、 复合的方式来给出所考虑问题的编码策略。 如此，给定一个问题，假设已找到该问题例子的一个合理编码策略， 则对于该问题中的一个例子，称其依照编码策略所得的相应字符串描述中 含字符的个数为其输入长度，并将该输入长度的具体数值作为这个例子的 正式度量。 1 2 2 多项式时间算法与指数时间算法 有了上面的准备，我们便可以给出一个算法复杂性函数的定义，它是 问题例子输入长度的函数。具体定义为：对某一问题和任一可能的输入长 度，如为n ，称用所给算法求解某一问题的所有大小为n 例子所需时间的 最大值为该算法在输入长度为n 时的复杂性。对于不同的算法，就有着不 同的时间复杂性函数。复杂性函数的不同变化方式反应了算法的好坏程度。 例如，时间复杂性函数关于输入长度的增长速度就是判别一个算法实际效 率的主要指标。那么，什么样的时间复杂性函数所对应的算法是好的、可 以接受的呢? 现今，在计算机科学中存在着这样一个一般的约定：仅当算 法的时间复杂性函数随着问题例子输入长度的增加而多项式的增长时，才 认为这个算法是实用的、有效的。按照这种观点，则可以将算法分为两大 燕山大学工学硕士学位论文 类。 在给出两类算法的定义之前，先引进在表示算法复杂性时常用的、类 似于数学中同价大小的记号0 ( ) ，对于定义于正整数集上的两个正实值函 数f i n ) 与g ( n ) ，若存在两个常数a b 0 ，使得当n 充分大时有b g ( n ) 鳗n ) 鲰( n ) ，则记f i n ) = 0 ( g ( n ) ) 。利用o ( ) 可将函数划分为不同的类，在复杂性 理论中，对如此定义的同一类型函数往往不加区分，故有下列定义： 多项式时间算法( p o l y n o m i a lt i m ea l g o r i t h m ) ，是指存在某个以输入长 度n 为变量的多项式函数p ( n ) ，使其时间复杂性函数为0 ( p ( n ) ) 的算法。因 此，复杂性为0 ( n ) 、o ( 1 0 6 i - 1 3 ) 、o ( 5 n 8 ) 等的算法均为多项式时间算法； 指数时间算法( e x p o n e n t i a lt i m ea l g o r i t h m ) ，是指任何其时间复杂性函 数不可能如上用多项式函数去界定的算法。这类算法的时间复杂性函数典 型的例子有：2 n 、n 、n ! 、n l 嘶等。在复杂性理论中，我们将所有这些类型 的函数统称为指数函数而不做进一步的细分。 为了对这两类算法有更直观的了解，我们用f ( n ) 表示不同的时间复杂 性函数，用n 表示计算机一天内所能求解的例子的规模，用m 表示计算机 速度提高1 0 倍后一天内所能求解的例子规模，得到结果如表1 - 1 所示。 表1 - 1 不同复杂性函数增长速度的比较与技术进步的影响 t a b l e1 - 1t h ec o n t r a s to f i n c r e a s es p e e d so f d i f f e r e n tc o m p l e xf u n c t i o n a n dt h ei n f l u e n c eo f t e c h n o l o g i c a l p r o g r e s s f ( n )f ( 1 0 )f ( 1 0 0 )i 0 0 0 ) nm 1 01 0 01 0 0 01 0 1 21 0 1 3 n 31 0 31 0 61 0 91 0 42 1 5 t o n b m2 0 9 9i 9 3 1 0 ”7 时1 0 2 97 99 5 2 “1 0 2 41 2 7 1 0 3 01 0 5 1 0 3 0 14 04 3 n f 3 ，6 2 8 ，8 0 0 0 1 5 84 z 0 2 5 6 71 41 5 4 第1 章绪论 由表1 1 可以明显看出，指数复杂性函数的增长速度要比多项式时间 复杂性函数快的多。因此，随着问题例子大小的不断增大，任意一个多项 式时间算法终归比任一指数时间算法更有效。 多项式时间算法的另一个特点是，在某种意义上，它具有能更好的利 用技术进步的优越性，如表1 1 中所示，当计算机速度提高1 0 倍时，多项 式时间算法在一天内所能求解例子的最大规模将在原有基础上增加1 到1 0 之间的某个常数倍。但对于指数时间算法来说，一天内所能求解例子的最 大规模仅有一加法的增加，即只能增加一个常数。最后，多项式时间算法 有一个较好的“封闭”性质，即几个多项式时间算法可以被复合：一个多 项式时间算法可以调用另一个多项式时间算法作为其子算法或子程序，其 最后的结果仍是一个多项式时间算法。 由于上述原因，多项式时间算法要比指数时间算法好得多，是人们常 常所更加希望得到的。也正是由于这些原因，人们往往将多项式时间算法 称为有效算法，并将“好”的算法与其等同起来。现在普遍认为，在找到 求解它的某个多项式时间算法之前，一个问题并未被很好的求解。因此， 常称一个问题具有难解性或为难解的如果它是如此困难，以至于没有 多项式时间算法可以去解它。 1 2 3 四类问题 上面我们依据算法的时间复杂性函数将算法大致分为多项式时间算法 和指数时间算法，在以下的叙述中，我们将把问题分为多项式确定( 简称p 类) 问题、非多项式确定( 简称n p 类) 问题、完全非多项式确定( 简称n p c 类) 问题和非多项式确定难( 简称n p h a r d 类) 等四类问题。 首先，p 类问题是指具有多项式时间求解算法的问题类。但迄今为止， 许多优化问题仍没有找到求得最优解的多项式时间算法，通常称这种比p 类更为广泛的问题为非多项式确定问题，即n p 问题。n p 的概念通常由判 定问题引入，下面介绍相应的若干概念。 ( 1 ) 实例是问题的特殊表现，所谓实例就是确定了描述问题特性的所有 参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实例 燕山大学工学硕士学位论文 的输入长度。 ( 2 ) 若个问题的每个实例只有“是”或“否”两种回答，则称该问题 为判定问题，并称肯定回答的实例为“是”实例，否定回答的实例为“否” 实例或非“是”实例。 ( 3 ) 若存在一个多项式函数g ( x ) 和一个验证算法h ，对类判定问题a 的任何一个“是”的判定实例i 都存在一个字符串s 是i 的“是”回答，满 足其输入长度d ( s ) 不超过g ( d ( i ) ) ，其中d o ) 为i 的输入长度，且验证算法验 证s 为l 的“是”回答的计算时间不超过g ( d ( 1 ) ) ，则称判定问题a 为非多 项式确定问题，简称n p 。 由此可见，判定问题是否属于n p 的关键是对“是”的判定实例是否 存在满足上述条件的一个字符串和算法，其中字符串在此可以理解为问题 的个解，而定义中没有强调字符串和算法是如何得到的。可见，p c n p 。 ( 4 ) 给定问题a 】和a 2 ，称a l 可多项式转换为a 2 ，若存在一个多项式函 数g ( x ) 和个字符串，满足：第一，对a i 的任何一个实例i l ，在其输入长 度的多项式时间g ( d ( 1 1 ) ) 内构造a 2 的个实例1 2 ，使其长度不超过g ( d ( 1 1 ) ) ； 第二，由此构造使得实例1 1 和1 2 的解一一对应，且d l 为1 1 的“是”回答的 充要条件为d l 对应的解是【2 的一个“是”回答。 ( 5 ) 给定判定问题a 1 和a 2 ，称a 1 可多项式规约为a 2 ，若存在多项式 函数g l ( x ) 和9 2 ( x ) ，使得对a 】的任何一个实例i ，在多项式时间内构造a 2 的一个实例，其输入长度不超过g l ( d ( d ) ，并对a 2 的任何一个算法h 2 ，都 存在问题a i 的一个算法h l ，使得h l 调用h 2 且计算时间f s 。( d ( i ) ) 皂2 ( f h 2 ( g l ( d ( d ) ) 。 由此可见，若问题a 2 存在多项式时间算法，则闯题a j 一定存在多项 式时间算法。 进一步，我们给出n p c ( n p c o m p l e t e ) 和n p h a r d 的概念。 ( 6 ) 称判定问题a e n p c ，若a n _ p 且n p 中的任何一个问题可多项式 规约为问题a 。称问题a 为n p h a r d ，只要上述第二个条件成立。 由此可见，n p c n p - h a r d ，而两者的区别仅在于n p - c 必须判断问题 属于n p 类。同时，若已知个问题为n p c 或n p - h a r d ，当遇到一个新问 第1 苹绪论 题时，若己知问题可多项式规约为新问题，则新问题为n p h a r d ，进而若可 验证新问题属于n p 类，则新问题为n p c 。 我们之所以介绍这四类问题的概念及其关系，是因为n p c 问题具有 重要的实际意义和工程背景，目前已有许多问题被证明为n p c ，如背包 问题、装箱问题、集合覆盖问题等；同时，我们下一章将要着重介绍的蚂 蚁算法，就是以一个典型的n p c 问题旅行商问题为模型，做进一步 展开的。 上述四类问题的关系可用图1 1 口嚷示。 p 图1 - 1四类问题的关系图【3 】 f i g 1 - 1i l l u s t r a t i o no f t h ef o u rp r o b l e m s r e l a t i o n s l 3 1 3 课题研究内容 本课题旨在分析现有的蚂蚁算法，以旅行商问题为模型，在大量仿真 的基础上，针对蚂蚁算法收敛速度慢，容易陷入局部最优的缺陷，对蚂蚁 算法加以优化；另外，由于a t m 网络中s v c 具有更多的优点，能够灵活 有效的利用网络资源，本课题在v p 网络拓扑结构已经确定的情况下，利 用改进的蚂蚁算法解决满足呼叫要求的s v c 路由选择。 本课题研究的内容主要有： ( 1 ) 以旅行商问题为例，建立基本蚂蚁算法模型，对现有的改进算法进 行仿真试验和比较研究； ( 2 ) 通过仿真比较总结出蚂蚁算法自身参数对其收敛性和搜索空间的影 响，并提出相应的动态调整参数方案； 7 燕山大学工学硕士学位论文 ( 3 ) 利用局部搜索和邻域函数，对算法加以优化，通过削弱重复路径上 的信息素含量，减小蚂蚁算法陷入局部最优的概率； ( 4 ) 根据a t m 网络中s v c 的分配特点，按照用户呼叫需求，将优化后的算 法合理的运用到a t m 网络的s v c 分配中去。 第2 章蚂蚁算法概述 第2 章蚂蚁算法概述 2 1 旅行商问题 2 。l 。1旅行商问题的一般概念 上一章我们已经提到，旅行商问题是一个典型的n p - c 问题，它也是 图论中一个很著名的问题，它之所以著名有两方面的原因：一是实际中有 很多应用问题都可以归结或转化为旅行商问题；二是由于旅行商问题的难 于求解性，特别是对规模较大的问题，从而吸引了许多有志者从事其有效 求解算法的研究。 为了便于理解，我们先给出现实中旅行商问题的两个例子，然后再给 出一般性概念。 例如，幼儿园巴士问题：某一幼儿园，有n 个小朋友，幼儿园有一辆 巴士负责每天接送他们上下学，问如何安排行车路线，才使每天的耗油量 最少。 再如，集成电路制造问题：在一块集成电路板上，往往容纳成千上万 的电子元件，在制造集成电路的过程中，从一个元件移动到另一个需要消 耗一定的能量，问如何安排制造的顺序，才能使所消耗的能量最少。 以上两个问题虽然涉及不同的领域，但它们存在着共同的特征，抓住 问题的本质，并代替用图论之术语，旅行商问题的一般概念是；给定n 个 城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最 短路线。其图论描述为：给定图g = ，a ) ，其中v 为顶点集，a 为各顶 点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最 短的h a m i l t o n 回路，即遍历所有顶点当且仅当一次的最短回路。 2 1 _ 2 旅行商问题的基本性质 为了更加细致而深入的探讨旅行商问题，这里我们研究一下旅行商问 题的基本性质。首先看一下它的分类。按照t s p 路径关系的不同特征，通 9 燕山大学工学硕士学位论文 常有以下两种基本分类【4 】： ( 1 ) 任意两个城市之间来回路径均相等或可以不相等，这可以归结为无 向图或有向图问题： ( 2 ) 任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单 行路径，这可以归结为完全图或者非完全图问题。 将以上两种情形加以组合，可以得到以下四种t s p 的路径关系： ( 1 ) 完全有向图； ( 2 ) 完全无向图； ( 3 ) 非完全有向图； ( 4 ) 非完全无向图。 而在大量的t s p 文献中，上述分类仅被表述为对称t s p 和非对称t s p ， 我们认为只用对称性来描述t s p 是过于简单的。 还可以按空间位置特征作如下两种分类： ( 1 ) 具有邻接路径关系的t s p 在这种类型中，各个城市之间的路径具 有明显的地域性限制，如果某城市在与之相邻的城市一边，则不能跨越这 个城市与该城市另一边的相邻城市建立直接的路径关系，例如各城市间的 公路网。即问题是“平面”的，由此构成的路径矩阵往往具有“稀疏矩阵” 的特点。 ( 2 ) 具有随机路径关系的t s p 这种类型中，任意两个城市之间均可以 存在路径，路径关系是随机的，不受地域限制，例如飞机的航线，即问题 是“立体”的。 当然，按照空间位置特征所作的分类( 1 ) 可归属于非完全图类，而( 2 ) 可 归属于完全图类。这种分类方式只是强调了实际应用。 讨论完旅行商问题的分类，我们再具体看一下它的难解性。 前面已经提到，旅行商问题是一个典型的n p c 问题，这里我们通过 一个实例来简单分析一下它的难解性： 假设n = 2 6 ，即2 6 个城市的旅行商问题，考虑完全有向图时的情形。 这样，假设用2 6 个英文字母代表2 6 个城市名称，那么，根据t s p 的概念， 问题转化为求解出2 6 个字母全排列中一条最短的路径来( 因为每一种排列 第2 章蚂蚁算法概述 方式都对应着一条路径的长度) ，我们来看一下问题的难解程度： 首先，2 6 个英文字母的全排列数为 2 61 4 1 0 2 6 阱每年3 6 5 天计算，每年共有 3 6 5 ) ( 2 4 3 6 0 0 = 3 1 5 3 6 x 1 0 7 秒 我们假设计算机每秒能处理l 亿种排列，则仅要完成这些排列就需要 4 x 1 0 2 6 ( 3 1 5 3 6 x 1 0 7 + 8 1 1 2 1 0 “年 显然，如此巨大的计算量是无法承受的，更不用谈大规模的问题求解 了。因此，旅行商问题一直倍受关注并得到了广泛的研究。 关于旅行商问题的研究进展，早期的有文献 5 1 0 】，近几年随着遗传算 法、蚂蚁算法等新型仿生类进化算法的出现，对旅行商问题的研究有了新 的进展，具体的情况可以参看文献 1 1 1 9 】。 2 2 基本蚂蚁算法 2 2 1 蚂蚁算法的产生 当传统算法在以旅行商问题为代表的一系列n p 问题中不能得到突破 性进展时，人们把眼光转向了适应性计算。 与传统的计算方法不同，适应性计算研究的是在系统不了解环境的情 况下，如何通过与环境的动态交互获得反馈信息，再利用反馈信息调整自 我，以期获得最佳的环境反馈。适应性计算的思想一般来源于两类系统， 其一是自然界的适应性系统，例如，生物进化、大脑以及哺乳动物的免疫 系统等；其二是社会系统和生态系统，例如经济市场或昆虫群体。因此说 计算中的适应性与生物学中的适应性有着千丝万缕的联系。通过与生物适 应性的对比，我们认为适应性计算有以下四个重疆含义。 ( 1 ) 无知识：生活在某一环境中的生物，事先常常没有关于这一环境的 知识，生物对环境的认识主要是通过与环境的交互完成的。因此，适应性 计算最大的特点之一就是不需要领域知识； ( 2 ) 动态环境：其实适应性计算适用于动态环境的一个原因就是它的无 燕山大学工学硕士学位论文 知识性。因为面临一个不断变化的未知环境，任何事先设定的知识都可能 失效，而根据反馈决定行为则较有保证。这一点与当前进化计算研究的核 心问题有所不同； ( 3 ) 学习：对机器学习的说法很多，目前公认的是s i m o n 对学习的阐述： “如果一个系统能够通过执行某种过程而改进它的性能，这就是学习”； ( 4 1 个性；自然界有各种各样的物种，它们之间有着不同的特性。例如 鸟善于飞翔，而鱼长于游泳，这是对不同环境的适应结果。另外，在同一 生物物种中也常有不同个性的个体，这与适应中的随机性有关。 目前，在适应性计算中一般有两条技术路线：群体进化方法和个体适 应方法。尽管在强调环境反馈上是一致的，但它们模拟的是不同的生物适 应过程，群体方法模拟物种的进化过程，而个体方法模拟生物个体的适应 过程，这导致它们在得到和利用反馈信息上有所区别。 个体适应方法主要包括增强式学习( r e i n f o r c e m e n tl e a r n i n g ，简称r l l 2 q ) 和分类器( c l a s s i f i e rs y s t e m ，简称c s ) 等方法。r l 方法假设环境是黑箱， a g e n t 需要在与环境的交互中调整自身的行为原则，以期获得最佳的环境反 馈；与r l 类似，c s 也把环境看作黑箱，a g e n t 在环境中的行动引发反馈 机制，再根据反馈信息调整自己的行为，其最终目的是获得最适应环境的 行为原则( 分类器) 。 群体进化方法主要包括遗传算法、进化策略( e v o l u t i o ns t r a t e g i e s ) 和进 化规划( e v o l u t i o n a r yp r o g r a m m i n g ) ，以及本文采用的蚂蚁算法等等。这些方 法统称为进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 。虽然这些方法是由不同的人 在不同的时期发展起来的，但它们都来源于自然界。自然界始终是人类灵 感的重要来源。控制论、人工神经网络、模拟退火算法、元胞自动机、遗 传算法等的研究方向都起源于对自然现象或过程的模拟，蚂蚁算法也是其 中之一。 蚂蚁算法是一种源于大自然中生物世界的新的仿生类进化算法，也是 求解适应性计算问题的一种算法。它是由意大利人m d o r i g o 等人首先提出 的【2 “，该算法模仿蚂蚁觅食时的行为，按照启发式思想，通过信息传媒 p h e r o m o n e 的诱导作用，逐步收敛到问题的全局最优解。 1 2 第2 章蚂蚁算法概述 出于前面提到的旅行商问题的典型性，以及蚁群搜索食物的过程与旅 行商问题之间的相似性，蚂蚁算法在求解旅行商问题中得到了相当广泛的 应用2 2 五4 1 ，在以下的叙述中，我们会发现，许多改进算法也是以旅行商问 题为标准进行研究比较的。 2 2 2 人工蚁群系统 在建立蚂蚁算法模型之前，我们先简要介绍一下人工蚁群系统的概念。 人工蚁群系统源于对自然蚁群的抽象，它是为了建立蚂蚁算法的模型而提 出的，由于其观点来源于真实蚁群，所以人工蚁群系统与真实蚁群存在以 下几点共同特征 2 5 1 ： ( 1 ) 一个个体能相互协作的群体人工蚁群系统中的人工蚂蚁和自然蚁 群中的真实蚂蚁一样，都能够找到一条从出发点到目的地的可行解，并且 都能够通过个体之间的相互协作逐渐找到最优解； f 2 ) 进行信息交流的信息素真实蚂蚁在它们经过的路径上留下了化学 物质信息素，人工蚂蚁在它们经过的路径上改变了路径上存储的数字 信息。这个信息考虑了蚂蚁当前的和历史的性能。并且还能被其它经过这 里的人工蚂蚁读和写。并且，在蚂蚁算法中有一个挥发机制，它像真实的 信息素挥发一样随着时间的推移改变路径上的人工信息素； f 3 ) 为找到最短路径纪录的当前移动队列人工蚂蚁和真实蚂蚁都要完 成一个相同的任务，寻找一条从出发点到目的地的最短路径。两者都不具 有跳跃性，即它们只能在相邻节点之间一步一步的移动： ( 4 ) 利用当前信息而没有未来信息的随机选择策略人工蚂蚁从一个节 点转移到下一个节点的求解方法是按照概率选择策略实现的。概率选择策 略只是利用当前的信息去预测未来的情况，而不能j | 用未来的信息。这一 点与自然蚂蚁也是一样的。 另外，人工蚁群还具有一些真实蚁群不具有的特点： ( 1 ) 人工蚁群生活在一个离散的世界中，它们的移动是指从离散状态到 离散状态的转换： ( 2 ) 人工蚁群具有一个内在的状态，这种私有的状态包括对该蚁群以前 1 l 燕山大学工学硕士学位论文 行为的记忆； ( 3 ) 人工蚁群放置信息素的定时性，是随问题而定的，它并不反映真实 蚁群的行为。例如，在一些例子中人工蚂蚁只在产生一个解之后才改变信 息素迹，并不是随时改变的； ( 4 ) 为改善系统的有效性，蚂蚁算法中可以增加一些额外的性能，比如 说预测未来、局部优化、回退等等。这些在真实蚁群没有中是没有的。在 很多应用中人工蚁群可以在局部优化过程中相互交换信息，还有一些蚂蚁 算法实现了简单的预测。 总之，人工蚁群系统来源于自然蚁群，它是对自然蚁群的抽象和优化。 人工蚂蚁寻找最优路径的方法就是根据真实蚂蚁寻找最优路径的方法提出 的，即让人工蚂蚁根据路径上的相当于p h e r o m o n e 的数字信息素的大小( o p 强度) 选择路径，并在所经过的路径上留下相当于p h e r o m o n e 的数字信息素， 然后随着时间的推移，最优路径上的数字信息素就会越来越大，从而选择 它的概率也就越来越大，最终所有的人工蚂蚁都将选择这条路径。 通过上面的分析不难发现，这种模拟蚁群搜索食物的过程与著名的旅 行商问题非常相c a ( o p 通过个体之间的信息交流与相互协作最终找到从蚁 穴到食物源的最短路径) ，这也是最初提出用蚂蚁算法来求解t s p 的原因。 虽然人工蚁群系统是对真实蚁群的抽象和模拟，但其本质利用的仍是 自然蚁群的正反馈机制，正反馈机制作用的强弱( 在这里实际上是数字信息 素的强弱) 直接影响着实验的最终结果。这便不可避免的使蚂蚁算法存有一 定的缺陷，关于这一点，我们将在下一章详细予以说明。在文章下面的叙 述中，如果不做特殊说明，我们所说的蚁群系统就是指人工蚁群系统，而 蚂蚁也特指人工蚂蚁。 2 2 3 基本蚂蚁算法模型 有了上面的准备，下面我们以旅行商问题为例，建立基本蚂蚁算法的 模型。在一些文献中，基本蚂蚁算法被称为a a ( a n ta l g o r i t h m ) 或a s ( a n t s y s t e m ) 。 首先引入以下符号，并对其作以简要说明。 1 4 第2 章蚂蚁算法概述 m ：蚁群中蚂蚁的数量： 西：城市i 、，之间的距离( f ，j = l ，2 ，n ) ： 蜥：蚂蚁由城市f 转移到城市，的期望度，可以由某种启发式算法确定。 在t s p 问题中，日。，= 1 d o ，称之为能见度； 功( 0 ：t 时刻在扩连线的路径上残留的信息量； p ( o ：r 时刻蚂蚁k 由城市i 转移到城市，的概率。 t 时刻，蚂蚁颤婷1 ，2 ，m ) 在城市i 处选择路径时按概率p 口( n 决定 转移方向： = 嘲( f ) d ：( f 砩( f ) r r b a t i o w f # o j 皂翘o w e t o t h e r w i s , ( 2 - 1 ) 其中，指数a 表示残留信息的相对重要程度；指数口表示期望度的相对重 要程度；用t a b u i 表示蚂蚁k 已经走过的城市的集合( 有一些文献中称t a b u , 为搜索禁忌表) ，则a 1 0 w e d k = 1 ，2 ，胛卜t a b u k 表示蚂蚁k 下一步允许选择的 城市( 人工蚁群系统有记忆功能，这是实际的蚁群所不具备的) 。经过胛个时 刻，蚂蚁完成一次环游，各条路径上的信息素量要根据式( 2 2 ) 和式( 2 3 ) 作 调整： d o + n ) = p 工口( f ) + a v “( 2 2 ) a r 口= a r ； ( 2 - 3 ) 其中，p 为小于1 的常数，表示轨迹的持久性；1 - p 表示轨迹衰减度，即信 息的消逝程度；a r u 表示本次循环中路径i ，上的信息量的增量；厶表示第 k 只蚂蚁在本次循环中留在路径玎上的信息量。 对于以，m d o r i g o 提出了3 种不同的模型，分别为： ( 1 ) a n t - q u a n t i t ys y s t e m 模型，译为蚁数系统模型，其取值为 。i 羊， 若第七只蚂蚁在时刻瘌f + n 2 间经过i j a r ；2 d “ l0 ， o t h e r w i s e 燕山大学工学硕士学位论文 ( 2 ) a n t d e n s i t ys y s t e m 模型，译为蚁密系统模型，其取值为 吲= 偿 若第七只蚂蚁在时刻r 和h 力之间经过 o t h e r w i s e ( 3 ) a n t c y c l es y s t e m 模型，译为蚁周系统模型，其取值为 。f 争， ，吐a r ：= 扭 ”噜 【0 ， o t h e r w i s e 其中，q 是反映蚂蚁所留轨迹数量的一个常数，要由具体实验确定其值；，k 表示第女只蚂蚁在本次循环中所走的路径，厶表示其对应长度；在初始时 刻，功( o ) ；常数，a t 0 = 0 ( i j = 1 ，2 ，n - - 1 ) 。 由于模型( 1 ) 、( 2 ) 中利用的是局部信息，而( 3 ) 利用的是整体信息，所以 对于也，本文采用m d o f i g o 提出的a n t c y c l es y s t e m 模型中的取值方法， 即 自5lk(2-4) o t h e r w i s e 这样，在每次实验过程中，每只蚂蚁都依据式( 2 1 ) 选取路径；而在每 次实验结束后，每只蚂蚁选取的结果又通过式( 2 2 ) 、( 2 3 ) 、( 2 4 ) 反馈给式 ( 2 1 ) ，作为下一次实验蚂蚁选取路径的依据。这便是基本蚂蚁算法的自催 化过程。 在这一过程中，我们注意到，形成自催化的关键参数是信息素白，蚂 蚁每次选取路径主要依靠信息素作出决策；当然，根据式( 2 1 ) ，路径的长 度函，也会对蚂蚁的决策产生影响。 2 2 4 蚂蚁算法特点 图2 1 给出了利用基本蚂蚁算法解决旅行商问题的流程图。 通过讲述蚂蚁算法原理，并建立基本蚂蚁算法模型，可以看出，蚂蚁 算法具有以下几个特点f 2 6 l ： ( 1 ) 其原理是一种正反馈机制或称增强型学习系统，它通过信息素的不 1 6 旦丘q ，、，l = y r 第2 章蚂蚁算法概述 断更新达到最终收敛于最优路径上； f 2 1 它是一种通用型随机优化方法，但人工蚂蚁决不是对实际蚂蚁的一 种简单模拟，它融入了人类的智慧； f 3 1 它是一种分布式的优化方法，不仅适合目前的串行计算机，而且适 应未来的并行计算机： f 4 1 它是一种全局优化方法，不仅可用于求解单目标优化问题，而且可 用于求解多目标优化问题。 厢丽 将每只蚂蚁随机放在一个城市节点上 每只蚂蚁按公式( 2 - 1 ) 选取下一 节点更 j 盱t a b u k n m b u k 已满? ly 按式( 2 2 ) ( 2 - 3 ) ( 2 - 4 ) 更新 各路径上的信息素台量 ! 各 1y ( 堡生鳖些苎里) 图2 - 1利用基本蚂蚁算法解决旅行商问题的流程图 f i g 2 - 1f l o wc h a r t o f s o l v i n g t h e t s p u s i n g a s 2 3 蚂蚁算法的改进 2 3 1 蚁群算法 收敛速度慢，容易陷入局部最优是基本蚂蚁算法的一个主要缺点。针 1 7 燕山大学工学硕十学位论文 对此问题，许多学者提出了各自的改进方案。其中，d o r i g o 和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 27 1 ，简称a c s ，中文译为蚁群算法。 蚁群算法较之基本蚂蚁算法主要作了以下三个方面的改进【2 8 1 1 ： ( 1 ) 在蚂蚁利用概率选择下一城市时，引入了状态转移规则。在a c s 中， 蚂蚁在城市i 处将按照公式( 2 5 ) 选择下一城市，。 la r g m a x ( r f ( r ) 】 7 7 口o ) 】9