（计算机软件与理论专业论文）应用蚁群算法解决约束p中位问题.pdf

摘要 约束p 一中位问题( c a p a c j t a t e dp m e d i a np r o b l e m ，c p m p ) 作 为设备选址问题( f a c i l i t y1 0 c a t i o np r o b l e m ，f l p ) 的一个特殊分支，有 着广泛的应用背景，在选址理论和聚类理论中人们对其进行了深入地研 究。已知c p m p 是一类n p h a r d 组合优化问题，因此已有多种启发式 算法用于求解该类问题。 蚁群算法( a n tc o l o n ya l g o r i t h m ，a c o ) 由于其良好的优化性能， 已成为智能仿生算法领域中最具影响力的算法之一。它的主要优点是： 利用蚁群问的信息交互，来逐步优化对问题状态的信息素表示，进而指 导蚁群搜索问题的最优解。本论文旨在研究如何有效地将a c o 用于求解 c p m p ，以及如何解决与算法执行相关的一系列重要问题，以获得最好的 优化性能。本文的主要工作包括： 1 针对c p m p 的特点，提出了一种新的求解该问题的启发式算法一中位 学习算法( m e d i a nl e a m i n ga l g o r i t h m ，m l a ) 。该算法借鉴了a c o 的信息素学习机制，同时针对问题的结构设计了合理的对象分配方 式，通过结合局部搜索策略，算法的全局和局部优化性能得到加强， 最终生成问题的一个好的近似解。模拟计算表明，该算法具有良好的 全局优化性能和计算效率。 2 设计了适应值曲面投影方法，结合曲面的陡峭性指标，研究了c p m p 的适应值曲面的结构特征，进而深层次的刻画解空间的分布特征并据 此将问题分类。分析了影响算法性能的主要因素：问题结构，初始中 位选择策略，对象分配次序和方式，以及参数设置等。上述研究，为 理解算法优化行为，提高优化性能提供了理论依据，进而指导算法设 计。 3 在上述研究的基础上，提出了一种求解c p 的蚁群算法( p m a c 0 ) 。 该算法针对问题特征，设计了新型的初始中位选择方法；利用a c 0 的学习和优化机制，蚁群逐步学习对象的分配次序和方式；当搜索陷 于局部最优时，采用有效的信息素平滑策略以逃离局部最优，最终搜 索到问题的最优解。仿真试验表明，p m a c o 是一种性能较优的求解 c p m p 的算法，其设计思想和策略是合理有效的。 关键词：组合优化问题；约束p 一中位问题；启发式算法；蚁群算法 适应值夔瑟。 a b s t r a c t c a p a c i t a t e dp m e d i a np r o b l e m ( c p ) c a nb ev i e w e da s as p e c i a i e m b r a n c h m e n to ft h ef a c i l i t yl o c a t i o np r o b l e m ( f l p ) t h ec p m pa r i s e si n m a n vp r a c t i c a ls i t u a t i o n s i th a sb e e nr e s e a r c h e dw i d e l yi nl o c a 矗o nm e o r y a n dc l u s t e r i n gt h e o r y fi ti sa ni m p o n a j l tc o m p l e xc o m b i n a t i o no p t i m i z a t i o n p r o b l e ma 1 1 dh a sb e e np m v e dt ob en p _ h a r d m a n yh e u r i s t i c sa r ed e v i s e dt o s 0 1 v et h i sp r o b l e m a n tc 0 1 0 n ya l g o r i t h m ( a c 0 ) e n j o y sar 印i d l yg r o w i n gp o p u j a r i t yf o ri t s g o o do p t i m a lp e r f o 肌a n c e i na c o ，a j l t sc o m m u n j c a t ee a c ho t h e ri no r d e rt o o _ p t i m i z et h ep h e r o m o n ee x p r e s s i o n o fp r o b l e m s t a t es t e pb ys t e p t h e 】e a n l i n ge x p 嘶e n c ei n s t 珈c t sa j l tc o l o n yt os e a r c ho p t i m u mo fp m b l e m i ti s t h ep r i m a r vp u r p o s eo fo u rt h e s i st h a th o wt ou s et h ea c 0t os 0 1 v ec p m p e f f b c t i v e l ya n dd e v i s i n gg o o de x e c u t i n gs t r a t e g i e s i no r d e rt o i n l p r o v e p e r f o r m a n c eo f a l g o r i t h m t h ei m p o n a n tr e s e a r c hw o r k si n c l u d e ： 1 an e wm e d i a n1 e a m i n ga l g o r i t h m m l ai sp r o p o s e dt os 0 1 v ec p m p b a s e do nt h ec h a r a c t e r i s t i co fc p m p i tu t i l i z e st h ep h e r o m o n el e a n l i n g m e c h a n i s mo fa c 0 r e a s o n a b l ea l l o c a t i o nm e m o do fc u s t o m e r si s d e v i s e di nv i e wo fm es t r u c t u r eo fc p m l ai n t e 擎a t e s m e d h e r o m o n em e c h a n i s mo fa c ow i m l o c a ls e a r c hs t r a t e g ys ot h a tb o t l l m eg l o b a la n d1 0 c a ls e a r c ha b i l i t yo f 山ea l g o r i m m i sr e i n f o r c e d c o m 口u t a t i o n a lr e s u l t si n d i c a t et h a t t h em l ao u 印e r f o n n sa l t e m a t i v e m e t h o d sd e v e l o p e df o rs o l v i n gt h i sk i n do f p r o b l e m 2 t h ep r o i e c t i o nm e t h o do ff i m e s sl a n d s c a p ei sd e v i s e d t h es t m c 恤。e c h a r a c t e r i s t i co fc p m p sf i m e s sl a n d s c 印ei s r e s e a r c h e dd e t a i l e di n b a s eo ft h ep r o i e c t i o np l o tc o m b i n e dw i t ht h e c h a r a c t e “s t i ci n d e xo f f i 恤e s sl a n d s c 叩e d i s t r n ) u t i n gc h a r a c t e r i s t i c o fs o l u t i o ns p a c ei s d 印i c t e da 1 1 dp r o b l e m sa r es o r t e dh e r e b y m o r e o v e r ，w ea n a l y z em e 口r i m a r yf a c t o r sw h i c ha f k c tt h ea l g o r i t l l mp e r f o m a n c e t h e yi n c l u d e o fd r o b l e ms t m c 似i e ，t h es e l e c t i n gs t r a t e g y o fi n i t i a lm e d i a n s ，m e a s s i g r n i n go r d e ra n dm e t h o do fc u s t o m e r s ，t h ep a r m l e t e r ss e t t l n ga n d s o o n t h e s er e s e a r c h i n g r e s u l t s p r o v i d e t h e o q i n s 订r u c n o n t o r u n d e r s t a n d i n go p t i m i z a t i o nb e h a v i o ra n di m p r o v i n gp e r f b m l a n c eo f a l g o r i t h m t h e ya r eu s e dt oi n s n i u c tt h ea i g o r i t h md e v i s i n g a na c o - p m a c 0a l g o r i t h mi sp r o p o s e df o rc p m pb a s e do na b o v e r e s e a r c hr e s u l t s i td e v i s e sas e to fp e r f o r m i n gs t r a t e g i e so fa c oi n v i e wo ft h ec h a r a c t e r i s t i co fc p m p t h e s es t r a t e g i e si n c l u d et h e a t t r a c t i o ns e l e c t i n gs t r a t e g yo fi i l i t i a lm e d i a i l s ，t 1 1 ep h e r o m o n el e a m i n g s t r a t e g yo fc u s t o m e r s a s s i g 蛳e n tm e a n sa n dp h e r o m o n e s m o o t t h l e s s s t r a t e g yf o rg e t 【i n ga w a y 疗o mi o c a lo p t i m a t h e yi n s u r et h ep m a c 0 a l g o r i t h mc a ns o l v et h ec p m pe f f e c t i v e l y ，w h i c ha r ep r o v e db yt h e c o m p u t a t i o n a lr e s u l t s a tt h es 锄et i m e ，t h ed e v i s m gi d e ao fp m a c o a n dm ee 撬c j e n c yo f a b o v e - m e n t i o n e ds t r a t e g i e sa r ep m v e d k e v w o r d s ：c o m b i n a t i o no p t i m i z a t i o np r o b l e m ；c a p a c i t a t e dp m e d i a n p r o b l e m ；h e u r i s t a n tc o l o n ya 1 9 0 r i t h i t l ；f i t n e s s l a n d s c 印e 应用蚁群算法解决约束p 一中位问题 引言 蚁群算法( a c o ) 是近些年来发展的一类模拟进化算法，由于其良好的优化性能 和有效的学习机制，而得到了广泛关注和深入研究。蚁群算法的基本思想是：通过 蚁群间的信息交互，逐步修正对问题状态的信息素表示，学习所得的后验信息被用 来指导蚁群将来的搜索，最终促使蚁群集中到最优路径上来。蚁群的行为呈现了一 种自组织和自适应的特征，体现了一种信息正反馈的学习策略。它已被用于求解多 种组合优化问题，并取得了优于传统算法的结果，例如：旅行商问题( t r a w l i n g s a l e s m a n ) ，图着色问题( g r a p hc o l o u r i n g ) ，网络路由问题( n e m o r kr o u t i n g ) 等。 约束p 一中位问题( c p m p ) 就是将 个带权的对象划分成p 个互不相交的类， 使得所有的类内距离之和最小，并满足各中位点的容量约束。它有着广泛的应用背 景，特别是在选址理论和聚类理论中得到深入地研究。由于c p m p 是类n p h a r d 组合优化问题，因此一些启发式算法被提出以求解该类问题。禁忌搜索( t a b us e a r c h ， t s ) 方法，局部搜索( l o c a ls e a r c h ，l s ) 方法，模拟退火( s i m u l a t e d a n n e a l i n 2 ， s a ) 方法以及遗传算法( g e n e t i ca 1 9 0 r i t h m ，g a ) 等都被用于c p m p 的求解。 蚁群算法在求解组合优化问题上的良好表现促使我们考虑将它用于求解c p m p ， 因此在本文中，针对，= ，= ( 为常数) 情形下的c p m p ，我们提出了一种基于 a c o 的求解c p m p 的启发式算法中位学习算法( m l a ) 。在分析算法设计思想和 优化性能，以及研究问题适应值曲面特征的基础上，我们进一步研究了影响算法性 能的几个主要因素：初始中位选择策略，对象的分配次序和分配方式，参数的设置 以及问题的结构等，分析了它们对算法性能的影响方式及规律。在上述研究结果的 指导下，我们提出了一种求解c p m p 的a c o ( p m a c o ) ，针对问题特征，设计了合 理有效的初始中位选择策略，由蚁群通过信息正反馈来自适应的学习对象的分配次 序和方式，当搜索陷于局部最优时，我们设计了有效的信息素平滑机制来逃离局部 最优，模拟计算证明了算法的性能和执行策略的有效性。 下面是本文内容的章节安排： 第一章介绍了组合优化问题的基本理论，以及c p m p 的相关理论和问题描述及 其研究现状。介绍了蚁群算法的设计思想，算法框架以及仿生算法的发展现状。 第二章详细描述了基于a c o 的信息素学习机制的求解c p m p 的启发式算法一中 位学习算法( m l a ) ，并通过实验证明了算法的良好的优化性能。 第三章首先给出了适应值曲面及其特征指标的相关理论和定义，以及我们所设 山西人学2 0 0 5 届硕士学位论文 计的适庸值曲面投影方法，继而针对c p m p 的实例问题，刻画其适应值曲面，根据 睦面投影图及特征指标将问题分类，探索问题结构与其求解难度间的关系。另外， 我们还分析了初始中位的选择，对象的分配次序和方式，参数的设置等算法执行策 略对算法优化性能和效率的影响。 第四章基于第三章中对问题适应值曲面及算法执行策略的分析，给m 了一种求 解c p m p 的蚁群算法( p m a c o ) ，并通过数值计算将其与已有算法进行比较，表明 了算法具有良好的优化性能，同时验证了其设计思想和策略的有效性。 第五章总结了本文的主要成果，提出了需要进一步研究的问题。 应用蚁群算法解决约束p 一中位问题 第一章理论背景 本章第一节主要介绍了组合优化问题和约束p 一中位问题的概念及研究现状。蚁 群算法是近年来发展起来的一种著名的仿生算法，在第二节中我们详细介绍了仿生 算法的理论背景和研究内容，蚁群算法的设计思想和算法框架，及其研究现状。 1 1 本文研究问题 最优化问题广泛出现在工程技术，科学研究和经济管理等诸多领域，根据计算复 杂性理论，无法在多项式复杂程度内求得最优解的问题称为n p h a r d 问题，而约束 p 一中位问题就是一类n p h a r d 组合优化问题，需要采用启发式算法来求得问题的 近似最优解。 1 1 1 组合优化问题 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学方法的研究去寻找离散事 件的最优编排，分组，排序等，它是运筹学的一个经典且重要的分支。该问题可用 数学模型描述为： m i n ，( x ) ( i 1 ) s t g ( x ) 0 ， ( 1 2 ) x d ( 1 3 ) 其中，厂( x ) 为目标函数，g ( z ) 为约束函数，z 为决策变量，d 表示有限个点组 成的集合。 一个组合优化问题可用三参数( d ，尸，) 表示，其中d 表示决策变量的定义域，f 中的任何一个元素称为该问题的可行解，厂表示目标函数。满足 ，( x ) = m i n ，( x ) ix f ) 的可行解x + 称为该问题的最优解。组合最优化的特点是可行 解集合为有限点集，由直观可知，只要将d 中的有限个点逐一判别是否满足占( x ) 的 约束和比较目标值的大小，该问题的最优解一定可以得到。因为现实生活中的大量 优化问题是从有限个状态中选取最好的，所以大量的实际优化问题是组合最优化问 题。特别是在调度，规划，决策等工程问题中有着广泛的应用。 如何迅速准确地求解问题是组合优化问题研究的核心内容。由组合优化问题的定 义可知，每个组合优化问题都可以通过枚举的方法求得最优解，而枚举的耗费时 间可能无法承受。 定义1 1 对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个 多项式函数g ( x ) 和常数d ，使得c ( ，) 日g ( d ( ，) 1 对给定优化问题的任何一个实例都成 1 山砖大学2 0 0 5 耩硕士学位论文 立，则称给定f 勺优化问题怒多项式时间可解问题。 其中，蹩该组台傀纯溺题翡在一实铡，e f n 是该簿法隶薅实援j 靛基奉话纂总 次数，d f ，) 怒实例，的计辣机二进制输入长度。 若不存在个能求得策组合优化问题最优解的多项式时间算法，则该问题被称为 n p h f d 缓会优纯闷题。对于i 毫类阉题，遮羞茂题蕊模数增大，其技举的嗣闽代价 娩会迅速超出实际可承受的范匿，因此人们不得不采用启发式算法，以求能快滚求 得问题的近似最优解。 1 ，2 约束p 一中位问题f c p m p ) p 一中位闯题( p m p ) 就是将一缀给定的对象划分成p 类，鼹每类都有其选定 的中位，优化目标是从中位集合中找到p 个作为各类的中位，将所有对象分配给各 个类，使所膏对象受其所斌中位豹距离憨勰最枣。 p 一中位间题是设备定位问题的一个特殊分支。它潆宜丰富的应用背景，例如， 多船舶运输中，货物的装载( b r a m e la n ds i m c h i l e v i ，1 9 9 5 ) ；以及在嘲络中，为 隧正服务拥塞，合理划分各服务器麴服务范围( b 鑫挝aa 嬲l a r s o n ，1 9 9 2 ) 等。特剃 避在选鲢理论和聚类理论中p m p 得蜀广泛深入遮研究， 计算复杂性理论已经溉明p m p 问题是一类n p h a r d 问题( 1 9 7 9 ，g a r e va n d j o h n s o n ) ，所以无法找到一种多项式时划箨法来求解它，困此，绝大多数解决该闽题 豹算法都是瘵教式算法。在求解较大蕊攘懿p 粥p 辩，这些方法麓够垒成较好静近似 解，或者能够为精确算法掇供较好的中间结果。 约束尹一中位翘题( c a p a c i t y 芦一m e d i a np 。b l e m ， e p m p ) 约束p 一申位问题藏燕带有中往容鬣约束条件斡p 中位闻题，它可以表述为： 将 个带权的对象划分成p 个互不相交的类，使得所有的类内距离之和最小，同时臻 袋该分类方式满足各中位点灼容量约束。 约束p 一中位闯题通鬻祓描述为魏下懿f o ，l 整数麓麓阚题： m i n 西南 味艺焱s w j 。 芝：l 划 艺y ，= p x ；，、si i ，j 。7 罗， 0 ，l 歹， ( 1 4 ) ( 1 ，5 ) ( 1 。6 ) ( 1 7 ) ( 1 ，8 ) ( 。9 应用蚁群算法解决约束p 一中位问题 这里，涎，= 1 ，2 ， 是对象集合：，l ，= l ，2 ，m 是可选中位集合，其中只 有p 个中位可以利用；d 。表示对象海0 中位，的距离；w 表示对象f 的权重；，表示 中位的最大容量。y ，表示中位，是否被选作第类的中位，若是，则y ，= 1 ，否则， y ，= 0 。则表示对象f 是否被分配给中位j ，若是，则x ，= l ，否则，x ，= o 。 在该整数规划模型中，约束条件( 1 5 ) 确保各类对象的权值的总和均不超过其 中位的容量限制：每个对象仅被分配给一个中位，且不被分配给未选中的中位，由 约束条件( 1 6 ) 限定；约束条件( 1 7 ) 限定，有且仅有p 个中位被选中。为了便于 研究和描述，本论文仅针对= j ，妒，= ( 为常数) 情形下的约束p 一中位问题 予以研究。而对于一般情形下的p 一中位问题，由于可以通过增加虚拟对象和调节 距离值转化为上述特殊情形，因而本研究具有广泛适用性。 1 1 3c p m p 的研究现状 c p m p 在许多领域都有着广泛的应用，因而寻找实际而有效的算法显得颇为重 要。遗憾的是，计算复杂性理论给予我们的结论是，作为一类n p h a r d 问题，无法 找到求解c p m p 的多项式时间算法。因此，人们转向寻找近似算法或启发式算法， 以得到问题的近似最优解。 人们已经设计了多种精确算法以求解小规模c p m p 的最优解。p i r k u l ( 1 9 8 7 ) 提 出了一种对约束条件( 1 6 ) 进行拉格朗日松弛的分枝定界法( b r a l 】c ha i l db o u n d m 劬o d ) ；而基于对问题约束条件予以集合划分( s e tp a m t i o i l i n g ) 的精确算法技术， 也已经得到n e e b e ( 1 9 8 3 ) ，h a l l s 盟( 1 9 9 4 ) ，以及b a l d a c c i ( 1 9 9 5 ) 等人的广泛研究； 此外，b e a s l e v ( 1 9 8 5 ) ，h a n o u l 和p e e t e r s ( 1 9 8 5 ) 也提出了有效求解该问题的精 确算法。 许多传统的优化算法也被用于c p m p 的求解，例如，贪婪搜索算法( g r e e d y s e a r c h )( k u e l u la 1 1 d h a i l b u r g e r ， 1 9 6 3 ) ，交换邻域搜索算法( i m e r c h a n g e ) ( t e i t z a n db a n ， 1 9 6 8 ：以及m o r e n o p 6 r e z ， 1 9 9 6 ) ，局部搜索算法( l o c a ls e a r c h ) ( e r l e n k o n e r ，d ，1 9 7 8 ) 等。 此外，已有多种现代启发式算法被用于求解c p m p 。例如：禁忌搜索算法( t a b u s e a r c h ) ( p a u l om f r a i l c a ，1 9 9 9 ) ，模拟退火算法( s i m u l a t e d 锄e a l i n g ) ( c o m o l l y ， 1 9 9 0 ) 2 ，禁忌搜索与模拟退火的混合算法( o s m a na n dc 硪s t o f i d e s ， 1 9 9 4 ) 可 变邻域搜索算法( v a r i a b l en e i g h b o r h o o ds e a r c h ) ( h a n s e np ， 1 9 9 7 ； f 6 1 i xg a r c i a l 6 p e z ，2 0 0 2 ) f 4 1 遗传算法( g e n e t i ca l g o 矗t h m ) ( e l o us a n t o sc o r r e a ，2 0 0 2 ：j o 曙e 山西大学2 0 0 5 届硕十学位论文 h j a r a r n i l l o ，2 0 0 2 ) f 5 ，生态算法( b i o n o m i ca l g o r i t h m ) ( v i t t o r i om a n j e z z o ， l9 9 8 ) 6 等。而e r l e n k o t t e r ( 1 9 7 8 ) ，m u 】v e ya n db e c k 【7 】( 1 9 8 4 ) ， p i r k u l ( 1 9 8 7 ) ，c o l d e n a n d s k i s c i m ( 1 9 8 6 ) ，k o s k o s i d i sa n dp o w e l l ( 1 9 9 2 ) 等人也设计了多种有效的启发式算 法以求解c p m p 问题。 这些启发式算法的求解性能受到问题的规模，结构，求解难度以及可接受的求 解时间代价等多种因素的影响。其中一些好的算法在求解较大规模的c p m p 时，能 够生成较好的近似解，或者能够为精确算法提供较好的中间结果。特别是以遗传算 法为代表的仿生算法，以其自组织，自适应，有效的学习机制，可并行性等良好特 性，得到广泛研究和蓬勃发展。而本文正是研究，将蚁群算法这种具有良好优化性 能和发展前景的仿生算法，用于求解约束p 一中位问题，以期能克服已有算法的局 限性，获得较好的优化性能。这不仅对于中位问题本身及其广泛的应用领域有着深 刻的意义，而且也是对蚁群算法这一新型智能仿生算法的深入研究与发展。 1 2 蚁群算法( a c 0 ) 1 2l 仿生算法 仿生算法是指通过模拟人、自然及其它生物种群的结构特点、进化规律、行为方 式及思维结构而发展起来的，用于求解各类优化问题的计算技术和方法。 生物的多种特性与功能已经给科学研究者许多启示。早期冯诺依曼根据许多小 单元均只与其附近小单元相互作用的原则构造了可以“自繁殖”的元胞自动机。而 近年来，受到人的神经元的启发而设计的人工神经网络，根据生物遗传，进化机制 演变而成的遗传算法，进化计算，以及模拟生物有机体免疫记忆特性，抗体的自我 识别能力的免疫系统模型等智能仿生算法，得到了广泛研究和深入发展。 尽管仿生对象各不相同，但它们都呈现出自组织、自适应的特征。它们在求解用 传统方法难以得到满意解的组合优化问题时，具有明显的优势。因此已被广泛应用 于工程，经济，交通，通信等多个领域。无疑，仿生算法已经成为未来最有发展前 景的研究领域之一。 而将社会性昆虫群体解决问题的知识模型，转变为人工求解实际问题的技术，形 成了仿生算法的一个重要分支一群体智能。群体智能不仅在系统复杂性以及n p 问题 等方面为人工智能，认知科学，计算经济学等领域的基础理论问题的研究开辟了新 的研究途径，同时也为诸如组合优化，知识发现，机器人协作等实际工程问题提供 了新的解决方法。 应用蚁群算法解决约束p 一中位问题 蚁群算法正是近1 0 年来蓬勃发展起来的一种模拟蚂蚁的食物搜索行为求解难组 合优化问题的一类群体智能模型。它体现了群体智能的核心思想，即简单个体之间 通过环境的相互作用产生协调致的行为解决复杂的问题。 1 2 2 蚁群算法的原理 蚁群算法 8 】一【1 0 】( a n ta l g o r i t h m ， a c o ) 是由m d o g o 等人于1 9 9 1 年提出的一 类模拟自然界蚁群行为的智能仿生算法，它在求解难组合优化问题上的良好表现， 使其受到了国内外众多学者的广泛关注。 蚂蚁是一种群居的社会性昆虫，蚁群内部具有高度的组织性，彼此借助外激素这 一生化信息介质来协调群体行为。虽然单个蚂蚁的行为极为简单，但由单个简单的 个体组成的群体却表现出了极其复杂神奇的行为。蚁群能够在复杂的环境下最终找 到从蚁穴到食物源的最短路径。经过仿生学家的大量细致观察研究发现，这都源于 蚁群间有效的通信机制。 具体说来，蚂蚁在搜索食物时，能够在它所经过的路径上留下信息素这种物质， 而且蚂蚁在运动过程中能够感知信息素的强弱，并倾向于选择信息素密度较高的方 向。这样，蚂蚁对环境中信息素的强弱作出反应，并释放新的信息素，而这些信息 素又将对自己和群体中的其它个体的运动产生指导作用，这就在蚁群行为中表现为 一种信息正反馈现象。某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就 越大，这也使得该运动方向的信息素密度进一步得到加强，最终使蚁群逐步稳定到 以信息素密度最高为标志的最短路径上来。这正是蚂蚁群体间通过有效的通信机制， 集体协作的结果。这使得蚁群行为呈现出自组织和自适应的特征，体现了其信息正 反馈的学习策略。 m d o r i g o 等人正是受到蚁群搜索食物行为的启发，提出了蚁群算法。其基本思 想是：引入人工蚂蚁这一简单智能体，借助所求解问题的原始模型，来模拟真实蚂 蚁的食物搜索行为，从而得到求解该问题的一种更精确的算法。人工蚂蚁在搜索过 程中，首先收集当前环境的局部信息，包括问题本身所提供的状态信息以及蚁群释 放的信息素的强弱信息等。通过对所获信息予以评价，依概率选择下一状态，逐步 构造出问题的可行解。然后模拟真实蚂蚁的信息素释放行为，根据所获解的优劣， 完成对当前信息素的调整过程。最终，蚁群的搜索将逐步稳定到问题的最优解。由 此可知，有效的信息交互机制是蚁群算法的核心。 1 2 _ 3 蚁群算法的基本框架 山西大学2 0 0 5 届硕十学位论文 我们以n 个城市的旅行商问题( t r a v e i i n gs a l e s m a n p r o b l e m ， t s p ) 为例，来具 体给出蚁群算法的基本框架。t s p 问题就是要求旅行商必须以最短路径访问所有的 城市一次且仪一次，并回到出发地。它是组合优化问题的典型代表，可以用有向图 g = ( 矿，e ) 来表示，其中，定点集y = v ，v ：，v 。j 表示城市节点的集合， e = “q ，v ，) 表示边的集合。其优化目标就是寻找图g 中的满足问题约束条件的，具 有最小费用的节点序列( q ，v f 、，叶) 。 在a c o 中，蚂蚁搜索可行解的过程就是从一个状态转移到_ f 一个相邻状态，对 局部可行解不断扩充，直至获得一个可行解的过程。在第次迭代搜索过程中，假设 蚂蚁t 当前所处的城市是v 。挑选下一个城市时，蚂蚁首先收集与当前状态有关的局 部环境信息，即各路径上的信息素以及路径的启发信息。令口，f d w p 矾( f ，) 表示当前所 有可能的保持序列局部可行性扩充的城市集合，叩，( ，) 表示由问题的数据或经验提供 的关于有序对沁，v ，) 的优劣性评判( 称之为启发信息) ，而f 。( r ) 表示蚂蚁对有序对 ( v ，v ，) 的优劣性评判( 称之为信息素，模拟真实蚂蚁的信息素释放行为) ，初始时刻 时t ，( o ) = c ，c 为正常数。和的取值越大，意味着这有序扩充越容易出现在 最优解中。其次蚂蚁按照随机决策规则选择下一个城市。一般情况下采用下述决策 规则： f 丛娑善丽，徊，f o 。吲“) 蚓叫) ( 矿啪) 4 ”“。“ ( 1l o ) o d 历p n v f s p 非负参数a ，决定了信息素及启发式信息对蚂蚁选择路径的影响程度。当日= o 时，只有路径信息起作用，算法相当于最短路径寻优：当= o 时，路径信息的启发 作用等于零，此时算法相当于盲目的随机搜索。 当任一蚂蚁都获得一个可行解( ) 之后，蚂蚁根据所得解的优劣，在它所利用 的有序对上释放信息素，从而修改信息素的取值。解的质量f 饵。) 越好( 取值越小) ， 在所经过的有序对上留下的信息素就越大。例如，第只蚂蚁释放信息素的量按照下 述方式计算： r ：= 志，如果第职蚂蚁的解经过有序嘶v 。 ( 1 1j ) o ，否则 这里9 是正常数。而下个时刻环境的信息素分布r i ( ，+ 1 ) 可由下式给出 应用蚁群算法解决约束p 一中位问题 ( 1 一p ) f 。0 ) + 2 j f ；jr o + 1 ) ， ( 1 1 2 ) = l o 厂f ) ，亭f ，剐称解s 为局部最优解。 2 l 山西大学2 0 0 5 届硕士学位论文 从上述定义。j 以看出，距离测度的定义决定了邻域的结构，从而也决定适应值曲 面的形状，对同一优化问题采用不同的距离测度会得到性质f i 同的适应值曲面。而 为了能更好的研究曲面的结构特征和陡峭性分布，应当在深入分析所研究问题的特 点的基础上，选择合适的距离测度。 求解组合优化问题的优化算法的寻优过程，可以被形象的理解为：搜索在适应值 曲面上的移动过程，任一解的目标函数值被看作是它在曲面上所对应的点的高度， 对于最大化问题，其优化目标就是寻找适应值曲面的最高峰。 问题的解空间通常是非常庞大且无分布规律的，因此耍描述其中所有的点，进而 精确的刻画适应值曲面的结构实际上是不可能的，现实的做法是适量选择解空间的 一部分点，通过对由这些点所构成的曲面的分析研究，来推断曲面的整体性质。这 样点集的选择会直接影响分析的准确性，它应该能尽可能的覆盖解空间的各个区域， 从而保证分析的全面性；但同时其规模不能过大，以保证分析的时问代价不会过大。 通常是将某一启发式算法搜索所得的所有局部最优解选作研究点集。 适应值曲面分析为理解组合优化算法的行为，预测算法性能，以及揭示问题结构 与算法求解性能间的关系提供了理论依据及方法。同时，通过考察适应值曲面的结 构特征和陡峭性分布，进而指导算法设计，改进算法的优化性能。 3 1 2 适应值曲面的测度指标 问题的适应值曲面的结构特征可以反映优化算法求解该问题的难易程度 ( m a i 】d 舐c ke ta 1 ， 1 9 9 1 ； m i t c h e l lc ta 1 ， 1 9 9 2 ) ，为了定性的分析研究算法优化 性能和问题结构间的关系，研究者们设计了大量的测度指标来静态的刻画适应值监 面的结构特征，并力求能准确的反映影响算法求解难度的曲面的性质，同时针对各 指标的取值得出了具有指导意义的结论。这些指标主要反映了曲面的如下特征： 1 异位显性( e d i s t a s i s ) ，如异位显性相关系数等指标，异位显性是针对遗传算法 而言的，它是指相互作用的基因位的个数。研究表明异位显性越大，则遗传算法 求解该问题的难度也越大。 2 中间过渡性( n e u t r a l “y ) ，如中间过渡态的数目叫( t h e n u m b e ro f n e u t r a ln e i g h b o u r ) 和中间过渡路径f 1 6 】( n e u t r a lw a l k ) 等： 3 陡峭性( r u g g e d n e s s ) ，例如局部最优解的密度( t h ed e n s i t yo f i o c a lo p t i m a ) ，相 关函数- ( 2 1 】( c o r r e i a t i o n 丘m c t i o n s ) ，关联长度( c o h l a t i o nl e n g t h ) 等指标。曲面 陡峭性是影响算法性能的关键因素之一，也是最常被刻画的适应值曲面的特征之 应用蚁群算法解浃约乘，一中位闷题 ，下面我们对其作详细介绍。 陡峭性是与党滢蛙相对款，包含较少鼹帮最犹点虽甥邻点之闻逶痘谴差异鞍小 的曲面是光滑鹩，反之尉是陡峭的。影响曲西陡峭性的潮素有很多，包括曲面上楣 邻点之间目标函数值的关联稔度，局部最优解的数目等。有关曲面陡峭性的信息可 以擐导我们设计有效豹搜索策蹬。研究裘嬲麴葱越陡螭，冀法越难搜索到其最优解。 曲面鲍上述特征指标不彼帮问题的适应值函数有关，也与优化黧法本身有关， 因此要针对算法来具体分析曲面特征和问题结构以及算法的求解性能。通过分析遗 应值蛙面的上述测度指标，鸯剥予理矮难优化闽题，同时还可根据这些臻标特征对 瀚题加以分类，遗蔼疆霉冀法设计，瞄雯辩酶求耱缝合优化问题。 但由于任何启发式算法都是一个复杂的系统，且对适应值曲面的分析具有局限性 积不完整性，戳丽上述指标势不能准确的葳欧算法的性能帮问题的缩构，即它们之 瀚不存在绝对豹对应关系。j e 瓣e y 珏在文f 2 2 】中藏籀爨傻矮遗绩冀法求簿菜些肇 峰问题可能是嗣难的，丽对于一些多峰闯题，其求解则是相对容易的，这表明曲飚 的陡峭性并不能完全的决定簿法求解该问题的难易程度。因而已有的关于测度指标 戆结论吴毒一定弱羧注，箕餐导佟震是畜条件熬。 虽然算法的复杂性和适应值曲面的多样性使得测度指标与算法求解性能间没谢 绝对的对应关系，但是针对嶷体问题和算法，仍然存在反映二者本质特征和关系的 攒搽。p 酝e f z 裂蘧逶应蓬魏溪分辑方法戒凌数蘧述了二次分配窝题鳃分类特经，黪 基于这些特征设计了有效的求解算法。b ，n a u d t s 也利用该方法对约柬满足问题进行 了研究。这些都表明，适应值曲面分析方法是一种有效的分析和预测算法性能的研 突方法。 下面我们来舆体介绍几种常用的刻画适应值曲面特 芷的指标： 自相关函数( a u t o c o r r e l a t i o nf u n c t i o n ) 宅是由娥i l 出e f 静一2 1 3 提撼的诗算适瘦德趋嚣醚鹚链酌指标，反魏了麴嚣豹攘关绥 构( c o r r e l 撕o ns t n 】c c e ) 。给寇适应值馥蕊爷，l 厂，d ) ，定义s 上任一点算的邻域为( x ) ， 设k ，五， 怒解空间s 上的个单步随机移动点列，即札，( t ) ，扭o ，1 ，甩一1 ， 穗汐瓴) ，f 蕞) ，魄) ) 是该点列甄对应的适应擅时润黟剜( 蛀m es e r i e s ) ，该指标的 设计思想就是莉精该时间序列的统计特镊米麴酉适应德凿西上稻邻点之闻的关联耩 度。 定又3 1 3囱相关函数( a t i t o c o 玎e l a t i o nf u n c t i o n ) ：给定适应值魏谶( s ，存) 上豹 肇步随辊移动适应值序翻 歹( ) ，厂( 薯k ，( ) ，藉该序列髂蠡相关蕊鼗定义如下； 2 3 山晒大学2 0 0 5 届硕十学位论文 m 、：垒巡墨! 幽型! 塑丝丛 ( 3 1 ) 、 e 【_ 厂( 工，) 。 一 厂( 一) 2 其中研厂( 一) 是随机变量厂( ) 的期望，s 是矧隔步长。 显然，根据数理统计原理可知，一1 ，( j ) 1 。i ，( s ) l 接近o ，则表明曲面上相邻 点之间的适应值差异较大，关联程度较低，曲面较陡峭；反之，越接近i ，则关联程 度越高，曲面越光滑。通常，关联度较低的曲面包含大量的局部最优点。从而使得 算法易陷于局部最优，而很难搜索到最优解。 在，( 一) 的分布未知的情况下，可以由如下估计值来计算自相关函数： 面，= 擎群 z ， 这里，7 = 去：，厂( 一) ，7 o ( b 。x a n dj e i l l ( i n s ，1 9 7 0 ：g r a n g e r a n d n e w b 。1 d ，1 9 8 6 ) 使用随机移动序列来评估曲面的关联程度是一种极为有效的方法，但对于约束 组合优化问题而言，由于存在非可行解区域，使得利用该分析方法很难准确的评估 曲面关联程度。此时需要从点的满足问题约束的邻域内选择其相邻点来生成随机移 动序列，并尽可能扩大所选择点的多样性，使得该随机序列能较好的反映适应值曲 面特征，从而更为精确的评估曲面的陡峭性。 关联长度( c o r r e l a t i o nl e n g t h ) 自相关函数可以通过如下方式来计算： r ( j ) = e x p ( 一s f ) ( 3 3 ) 其中r 就是关联长度2 ”，这表明适应值曲面的关联长度和自相关函数是紧密联系的 两个指标。关联长度是指曲面上适应值显著相关的两个点之间的最大间隔步数。当 步长s = 1 时，它由如下公式计算： 一赢当“1 净o 。4 l n d r ( 1 ) 1 ) 一般情况下，需要进行多次单步随机抽样，并分别计算相应抽样的估计值，( 1 ) ， 最终以它们的平均值作为r ( 1 ) 的估计值，来计算曲面的关联长度。关联长度直接反映 了曲面的陡峭崎岖程度。一般而言，f 越小，曲面越陡峭，反之，衄面越光滑，局部 搜索算法越容易得到其全局最优解。 下面我们来介绍一些根据关联长度来评估曲面特征的结论，这些结论引自文献