（计算机应用技术专业论文）最大独立集和最小弱顶点覆盖问题求解及其应用研究.pdf

摘要 摘要 全局优化问题，特别是组合优化问题，是科学研究与工程计算中最基本的问题之一， 这类问题的求解一直是算法研究领域的热点问题。全局优化方法一般分为确定型和随机 型方法，确定型方法在数学理论上较为完善，但难以应用，而传统的随机型方法对于复 杂的全局优化问题又难以解决，这时启发式算法的引入使得随机型方法和整个全局优化 方法得到了新的发展，尤其是元启发式算法。 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 作为一种新的元启发式算法，具 有分布式计算、自组织、正反馈以及贪心启发等特点，使其能够成功解决许多n p - h a r d 组合优化问题。a c o 算法作为一种全局搜索算法，其全局优化性能的优劣在很大程度 上与参数的正确选择有关。但由于a c o 算法参数之间的关联性，使得最优参数组合成 为一个极其复杂的优化问题，目前还没有形成完善的理论依据，一般都是根据经验来确 定参数值。而禁忌搜索算法( t a b us e a r c h ，简称t s ) 以其灵活的禁忌表和相应的禁忌准则 来避免重复迂回搜索，具有强大的全局优化性能。所以为弥补a c o 算法易出现停滞现 象和陷入局部最优这一缺陷，本文将a c o 算法与t s 算法组合起来，提出了基于禁忌搜 索的蚁群优化算法( t a b us e a r c hb a s e da n tc o l o n yo p t i m i z a t i o n ，简称t s b a c o ) ，并将该 算法用于求解最大独立集问题。实验表明：禁忌搜索策略的引入，不仅提高了t s b a c o 算法的全局优化性能而且还提高了搜索效率。 为了增强超大规模集成电路( v l s i ) 系统运行时的可靠性与稳定性，需要在电路设计 中引入容错技术增强系统的容错能力。在v l s i 阵列的容错技术中，一般有冗余法和降 阶法两种重构方法，这两种方法都属于n p h a r d 问题。本文是通过冗余法来解决这一问 题的，根据阵列中缺陷单元的分布情况，构造相应的矛盾图模型，将阵列的重构问题转 化为求解矛盾图的独立集问题。通过t s b a c o 算法对矛盾图的独立集进行求解且使得 所求独立集大小恰为缺陷单元个数，找出合理的补偿通道来完成阵列的重构问题。实验 分析表明该重构方法是简单有效的。 为进一步验证t s b a c o 算法在求解组合优化问题方面的实用性和有效性，本文将 其应用于网络流量测量中的有效测量点选择问题。通过对图论中最小顶点覆盖模型的研 究，网络流量测量点选择问题可以抽象为最小弱顶点覆盖问题，而求解该问题是一个 n p h a r d 问题，于是本文又提出了一种求解最小弱顶点覆盖问题的t s b a c o 算法。比较 现有的求解算法，实验结果表明：本文提出的t s b a c o 算法能够发现更小的弱顶点覆 盖集，且具有更好的可扩展性，是网络流量测量中的一种有效测量点选择算法。 关键字：蚁群优化算法禁忌搜索算法最大独立集最小弱顶点覆盖 a b s t r a c t a b s t r a c t g l o b a lo p t i m i z a t i o np r o b l e m s ，e s p e c i a l l yc 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 r eo n e o ft h em o s tf u n d a m e n t a lp r o b l e m si ns c i e n t i f i cr e s e a r c ha n de n g i n e e r i n gc o m p u t a t i o n h o wt o s o l v es u c ht y p eo fp r o b l e m se f f i c i e n t l yh a v eb e e nt h ec o r ep r o b l e m so fr e s e a r c hf i e l do f a l g o r i t h m c l a s s i f i c a t i o no fg i o b a lo p t i m i z a t i o nm e t h o d si sa l w a y sd i v i d e di n t od e t e r m i n i s t i c a n dp r o b a b i l i s t i cm e t h o d s t h ef o r m e rh a st h es t r i c t n e s sa n di n t e g r i t yi nm a t h e m a t i c s ，b u t t h e ya r ed i f f i c u l tt oa p p l yi ne n g i n e e r i n g t y p i c a lp r o b a b i l i s t i cm e t h o di sd i f f i c u l t l ya p p l i e dt o l a r g e s c a l ea n dc o m p l i c a t e d 百o b a lo p t i m i z a t i o np r o b l e m s t h ei n t r o d u c t i o no fh e u r i s t i c s a l g o r i t h m sb e c o m ean e wd e v e l o p m e n tp h a s eo fd e t e r m i n i s t i ca n dp r o b a b i l i s t i cm e t h o d sa n d g l o b a lo p t i m i z a t i o nm e t h o d s ，e s p e c i a l l ym e t a - h e u r i s t i ca l g o r i t h m s a san e wm e t a h e u r i s t i ca l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h mw h o s e m a i nc h a r a c t e r i s t i c sa r ed i s t r i b u t e d c o m p u t a t i o n ，s e l f - o r g a n i z a t i o n ，p o s i t i v ef e e d b a c ka n d c o n s t r u c t i v eg r e e d yh e u r i s t i cc a ns o l v em a n yn p h a r dc 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 s s u c c e s s f u l l y a sak i n do fg l o b a ls e a r c ha l g o r i t h m ，a c oa l g o r i t h m sg i o b a lo p t i m i z a t i o n c a p a b i l i t yd e p e n d so nr i g h ts e l e c t i o no fp a r a m e t e r st oal a r g ee x t e n t as e to fu n s u i t a b l e p a r a m e t e r sm a yr e s u l ti nl o c a lo p t i m u mo ff i n a ls o l u t i o na n dp r e m a t u r ec o n v e r g e n c e t o c o m p e n s a t es o m el i m i t a t i o n so ft h eb a s i ca c oa l g o r i t h m ，i nt h i sp a p e lw ei n t r o d u c ean e w h y b r i da n tc o l o n yo p t i m i z a t i o na l g o r i t h m ：t a b us e a r c hb a s e da n tc o l o n yo p t i m i z a t i o n a l g o r i t h m ( t s b a c o ) t h a tc o m b i n e sa n tc o l o n yo p t i m i z a t i o nw i t ht a b us e a r c hs t r a t e g yt o s o l v em a x i m u mi n d e p e n d e n ts e t ( m i s ) p r o b l e m a sc o m p a r e dw i t ha c o a l g o r i t h m ，o u r p r o p o s e dt s b a c oa l g o r i t h ms h o w e dt h a tg l o b a lo p t i m i z a t i o np e r f o r m a n c ea n dc o m p u t a t i o n e f f i c i e n c yi sm u c hb e r e r t h a nt h ea c o a l g o r i t h m t oe n h a n c et h es t a b i l i t ya n dr e l i a b i l i t yo fv l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) s y s t e m s ， f a u l t - t o l e r a n tt e c h n i q u e sa r en o r m a l l ye m p l o y e di nv l s ia r r a y s g e n e r a l l y , t w om e t h o d sf o r r e c o n f i g u r a t i o n ，n a m e l y , t h er e d u n d a n c ya p p r o a c ha n dt h ed e g r a d a t i o na p p r o a c h ，a r e e m p l o y e di n f a u l t - t o l e r a n tt e c h n i q u e sf o rv l s ia r r a y s b o t h a p p r o a c h e sa r en p h a r d p r o b l e m s t h i sp a p e rd i s c u s s e st h ep r o b l e mo fv l s ia r r a y sr e c o n f i g u r a t i o nb a s e do nt h e r e d u n d a n c ya p p r o a c h t h ep r o b l e mo fa r r a y sr e c o n f i g u r a t i o ni st r a n s l a t e d i n t ot h e i n d e p e n d e n ts e tp r o b l e mo fc o n t r a d i c t i o ng r a p ha n ds o l v i n gt h em a x i m u mi n d e p e n d e n ts e t p r o b l e mw i t ht h et s b a c oa l g o r i t h ma n dt h en u m b e ro fi n d e p e n d e n ts e te q u a l st ot h e n u m b e ro ff a u l t yu n i t i ti sp r o v e db ye x p e r i m e n tt ob ea s i m p l ea n du s e f u la p p r o a c h t of u r t h e rp r o v et h ep r a c t i c a b i l i t ya n de f f e c t i v i t yo ft h et s b a c oa l g o r i t h mi n 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 ，t h et s b a c oa l g o r i t h mi s a p p l i e dt ot h ee f f e c t i v e m o n i t o r - n o d e ss e l e c t i o np r o b l e mi nn e t w o kt r a f f i cm e a s u r e m e n ti nt h i sp a p e r w es t u d i e d m i n i m u mv e r t e xc o v e rm o d e lo fag r a p ha n dt h ep r o b l e mo fs e e k i n gm o n i t o r - n o d e sf o r a b s t r a c t m e a s u r i n gt h en e t w o r kt r a f f i ci sr e g a r d e da st h ep r o b l e mo ff i n d i n go u tt h em i n i m u mw e a k v e r t e xc o v e rw h i c hi sn p h a r d t h e nt h et s b a c oa l g o r i t h ms o l v i n gm i n i m u mw e a kv e r t e x c o v e rp r o b l e mi sp r o p o s e da n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h et s b a c oa l g o r i t h mc a n f i n ds m a l l e rw e a kv e r t e xc o v e rt h a no t h e ra l g o r i t h m 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 ，t a b us e a r c h ，m a x i m u mi n d e p e n d e n ts e t ，m i n i m u m 伦a kv r e r t e xc o v e r i i i 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 塑霪孥 日 期： 2 丝星：竺：星 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 摊昌期： 第一章绪论 第一章绪论弟一早三百y 匕 1 1 研究背景及意义 目前科学技术正处于多学科相互交叉和渗透的时代，特别是计算机科学与技术的迅 速发展与普及，从根本上改变了人类的生产与生活。同时，随着人类生存空间的扩大以 及认识与改造世界范围的拓宽，人们对科学技术提出了新的更高的要求。其中，对于高 效的优化技术和智能计算的要求日益迫切。 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一 个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应 用，比如：系统控制、人工智能、模式识别、生产调度和计算机工程等。实现生产过程 的最优化，对提高生产效率与效益、节省资源具有重要的作用。同时，优化方法的理论 研究对改进算法性能、拓宽算法应用领域、完善算法体系同样具有重要作用。因此，优 化理论与算法的研究是一个同时具有理论意义和应用价值的重要课题。鉴于工程问题的 复杂性、约束性、非线性、建模困难等特点，寻求一种适合于大规模并行且具有智能特 性的算法已成为相关学科的重要研究目标和引人注目的研究方向。 近几年来，随着工程结构的大型化和复杂化，出现了许多有待解决的全局优化问题， 比如超大规模集成电路的阵列容错问题和网络流量有效监测点的选择问题。针对此类全 局优化问题，目前产生了许多全局优化方法，而计算机科学与技术的快速发展也使得全 局优化方法得以更好的发展与实现。全局优化问题是一个在数学理论上还无法精确定义 的问题，而许多工程实际问题都属于全局优化问题。目前用于解决各种全局优化问题的 具体方法很多，但还没有一种通用的能够解决这个问题的数学方法。由于全局优化问题 的数学理论还不完善，一方面需要进一步深化完善其数学理论，另一方面人们渴望寻找 一种预先不需要在数学理论上承认却能够直接达到优化效果的方法，启发式方法就应运 而生了。 启发式方法的灵活性和易操作性等使其迅速发展起来，其中近些年来在此基础上发 展起来的元启发式算法更是取得了令人鼓舞的成果，例如蚁群优化算法( a c o ) 、模拟退 火算法( s a ) 、遗传算法( g a ) 、禁忌搜索算法( t s ) 、神经网络算法( n n ) 等，这些算法 都是从不同的角度利用不同的搜索机制和策略来实现全局优化性能。然而，面对各种全 局优化问题的复杂性和多样性，每一种算法都表现出自身的优势和缺陷，都面临着时间 性能和优化性能的双重挑战，所以单凭某种优化算法是很难而且是不可能解决所有全局 优化问题的，而优化算法的混和则是拓宽其适用领域和提高算法优化性能和效率的有效 途径和手段。 元启发式算法的发展很快，而其中a c o 算法是最近1 0 多年发展起来的一种新型元启 发式算法，它的模型和原理都非常简单，而且具有较强的鲁棒性和易于与其他启发式算 法相结合等特点，所以迅速得到学者们的研究与应用，并且已经取得令人鼓舞的成果。 虽然a c o 算法拥有诸多优点，但此方法也存在一些缺点。比如，较长的搜索时间、容易 江南大学硕士学位论文 陷于局部最优解和出现停滞现象等。为弥牢b a c o 算法的这些局限性和进一步提高算法的 求解质量和搜索效率，方法之一就是与其它启发式算法的混合，形成混合优化算法，利 用其它启发式算法的优点来弥补自身的缺点，最终达到改进和完善a c o 算法优化性能的 目的。 1 2 蚁群算法的研究进展 蚁群算法( a n tc o l o n ya l g o r i t h m ) 最早是由m d o r i g o 等人在1 9 9 1 年首次提出的，最 初被称为蚂蚁系统( a n ts y s t e m ，简称a s ) ，利用蚂蚁觅食行为与旅行商问题的相似性， 模拟产生的一种仿生算法。主要通过一种叫做信息素的物质进行信息交流，根据信息素 的多少进行选择和更新，通过数次迭代产生全局最优解，是一种正反馈机制。自蚁群算 法提出之后，吸引了许多学者对该算法进行研究，并成功运用于解决复杂组合优化问题， 热i t s p 、j s p 、q a p 等问题。 由于a s 算法中信息素的全局更新规则对系统中的所有蚂蚁都进行更新，降低了搜索 最优路径的效率，所以a s 算法的性能并不理想。于是，m d o f i g o 等人在a s 算法的基础 上提出了a n t q 算法，建立了a s 算法与q 学习机制的联系。它在a s 算法的随机比例状态 转移规则基础上，在解的构造过程中提出了伪随机比例状态转移规则，从而能够实现在 解的构造过程中知识探索( e x p l o r a t i o n ) s 1 1 知识利用( e x p l o i t a t i o n ) 的平衡，并且引入了使用 q 学习机制的信息素局部更新过程。此外，在信息素的全局更新规则中采用了精英策略， 即每次迭代后只对最优蚂蚁所走过的路径进行信息素更新。所以a n t q 算法是个非常 有效的算法。此后，m d o f i g o 等人又在a n t q 算法基础上提出了a c s ( a n tc o l o n ys y s t e m ) 算法。 通过对蚁群算法的研究发现，将蚂蚁的搜索行为集中到最优解的附近可以提高解的 质量和收敛速度，从而改进算法的性能，但这种搜索方式会使早熟收敛行为更容易发生， 所以必须将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，于是 t s m t z l e 和h h o o s 提出了最大最小蚂蚁系统( m a x m i na n ts y s t e m ，简称m m a s ) 。m m a s 限定了信息量允许值的上下限，并在算法中采用了轨迹平滑机制。初始时，m m a s 将所 有路径上的信息量设为最大值r 。每次迭代后，只有迭代最优蚂蚁或全局优化蚂蚁进 行信息素更新，同时为了避免发生早熟现象，该算法将各条路径上的信息量限制在区间 【，】之内，这样可以有效地避免某条路径上的信息量远大于其他路径，使得所有 蚂蚁都集中到同一条路径上。直到现在，m m a s 仍然是解决t s p 、q a p 、j s p 等离散域优 化问题的最好蚁群算法模型之一，很多对蚁群算法的改进策略都渗透着m m a s 思想。 1 9 9 9 年，m d o r i g o 等人把此前各种基于a s 算法演化而得到的蚁群算法归结到一个 统一的框架中，并提供了抽象而规范的算法描述，称为a c o 元启发式算法( a n tc o l o n y o p t i m i z a t o nm e a t h e u r i s t i c ) ，简称a c o 算法。a c o 算法的优点在于：利用正反馈原理加 快进化过程，是一种本质并行的算法，不同个体之问不断进行信息的交流和传递，从而 能够相互协作，有利于发现较好的解。由于鲁棒性强，所以易于解决各种不同的优化问 题。但是，a c o 算法的计算量比较大、搜索时间长、有时候效果并不理想，所以国内外 2 第一覃绪论 的学者针对a c o 算法的这些问题，做了许多研究工作，有的将蚁群算法与其它启发式算 法相结合，有的给蚁群系统加入变异特征，取得了许多研究和应用成果。初步的研究表 明，a c o 算法在求解复杂优化问题方面，尤其是离散优化问题，比目前广泛应用的遗传 算法、神经网络算法等具有一定的优势。 目前所有蚁群算法的改进都是建立在a c o 算法之上的。1 9 9 9 年，吴庆洪等人提出了 具有变异特征的蚁群算法，其核心思想是为了改善蚁群算法收敛性较慢的问题，采用了 逆转变异方式。这种变异机制充分利用2 一换位法( 2 o p t ) 简洁高效的特点，因而具有较快 的收敛速度，这种方法克服了原有蚁群算法选择次最短距离概率很小的缺点，增加了解 的全局优化性。随后又出现了其他引入启发式因子或策略的改进蚁群算法，如信息素更 新分段化、引入扰动因子、引入杂交策略、自适应进化算子、增强型信息素更新规则等。 这些启发式因子或策略的引入对于a c o 算法的改进途径主要有三个：改进选择概率，增 加选择概率的自适应性，使选择概率能够以一定概率选择较差解；改进信息素更新规则， 增加信息素的自适应性，使信息素的分配更合理，避免信息素分配的大量冗余；使用其 他启发式策略对a c o 算法求出的解决方案进行进一步的搜索，实际上是多种邻域搜索方 法的结合，这样可以增强解的多样化。 目前大量的研究工作注重于a c o 算法的实际应用，然而，近几年的研究发现：a c o 算法用于解决组合优化问题时，也会遇到类似进化算法中的d e c e p t i o n 和b i a s 现象。例如 c 。b l u m 和m 。s a m p e l s 币0 ：究a c o 算法用于作业调度问题( s h o ps c h e d u l i n gp r o b l e m s ) 时发 现：a c o 算法执行段时间之后，其性能会由于信息素模式和处理的问题实例而下降， 这种现象称为：s e c o n do r d e rd e c e p t i o n 或者s e a r c hb i a s ，它意味着随着时间的推移找到更 好解的可能性越来越小。j m o n t g o m e r y 等人试图找出导致算法s e a r c hb i a s 的原因； c b l u m $ 1 m d o r i g o 针对a c o 算法求解组合优化问题时遇到的s e c o n do r d e rd e c e p t i o n 问 题，也做了大量的研究工作。然而算法性能的下降原因仍然是未知的，这些情况表明我 们需要对a c o 算法行为做更多更深入的了解。 应当指出，现阶段对a c o 算法的研究大多还只是停留在仿真阶段，尚未能提出一个 完善的理论分析，对它的有效性也没有给出严格的数学解释。但是，理论上的不完善并 不妨碍应用，有时应用还会超前于理论，并推动理论研究，a c o 算法的研究正是如此。 目前，a c o 算法已成为国际智能计算领域关注的热点和前沿课题。尽管a c o 算法的严格 理论尚未奠定，但这种新兴的智能进化仿生算法已展现出勃勃生机。 1 3 广义邻域搜索算法及其统一结构 在目前的全局优化算法中；还没有一种可以完全通用的优化算法，对于各种优化算 法本身而言，如果只凭单一的某种优化算法是很难而且是不可能解决所有全局优化问题 的。在各种优化算法本身的改进中，经常是由于其它优化算法的启发而“取长补短。 蚁群算法的改进也大都是进行的局部改进。近些年来，混合算法逐渐引起人们的重视， 这种优化算法是从整体结构上对两种或两种以上的优化算法进行结合，使优化算法之间 具有自适应性的互补。但混合优化算法并不是几种优化算法的简单拼凑，因此对于混合 3 江南大学硕士学位论文 优化算法的构造，有一个较为统一的指导思想和结构是很重要的。广义邻域搜索算法的 概念及其统一结构就为开发新型混合优化算法提供了一条指导途径。 传统的邻域搜索算法是一种利用邻域结构进行逐步优化的局部搜索算法。相对于梯 度下降法、爬山法等算法而言，蚁群优化算法、模拟退火算法、遗传算法、禁忌搜索算 法等智能启发式搜索算法，都是对传统邻域搜索算法的改进和变型。同时，近些年来出 于提高优化性能的需要，在诸多研究领域又相继出现了许多混合优化算法。为了区别于 传统的邻域搜索算法，我们将上述通过不同途径而构成的改进算法统称为广义邻域搜索 算法。 那么在具体设计新型广义邻域搜索算法时，需要考虑以下几个关键问题，并遵循一 定的指导性结论： 1 搜索机制的选择 搜索机制是构造算法框架和实现优化的关键，是决定算法搜索行为的根本点。基于 局部优化的贪婪机制可用于构造局部优化算法，如梯度下降法、爬山法等；基于概率分 布的优化机制可用于设计概率意义下的全局搜索算法，如蚁群优化算法、模拟退火算法 等。 2 搜索方式的选择 搜索方式决定着优化的结构，即每代有多少解参与优化。并行搜索方式以多点同时 或交叉优化，来取得较好的优化性能，但计算和存储量较大，如蚁群优化算法、遗传算 法等；串行搜索方式可视为并行方式的一个特例，优化进程中始终只有一个当前状态， 处理较为简单，但优化效率一般较差，如模拟退火算法。 3 邻域函数的设计 邻域函数决定了邻域结构和邻域解的产生方式。算法对问题的不同描述方式，使解 空间的优化曲面形状和解的分布有所差异，会直接影响邻域函数的设计，进而影响算法 的搜索行为。同时，即使在编码机制确定的情况下，邻域结构也可采用不同的形式，以 考虑新状态产生的可行性、合法性和对搜索效率的影响。在确定邻域结构后，当前状态 邻域中候选解的产生方式既可以是确定性的，也可以是随机性的，甚至是混沌性的。 4 状态更新方式的设计 更新方式是指以何种策略在新旧状态中确定新的当前状态，是决定算法整体优化特 性的关键步骤之一。基于确定性的状态更新方式的搜索，一般难以穿越大的能量障碍， 容易陷入局部极小；而随机性的状态更新方式，尤其是概率性劣向转移，往往能够取得 较好的全局优化性能。 5 控制参数的修改准则和方式的设计 控制参数是决定算法的搜索进程和行为的又一关键因素。合适的控制参数应有助于 增强算法在邻域结构中的优化能力和效率，同时也必须以一定的准则和方式进行修改以 适应算法性能的动态变化。一般而言，在当前控制参数难以使算法性能取得较大提高时， 就应考虑修改参数；同时，参数的修改幅度必须使算法性能的动态变化具有一定的平滑 性，以实行算法行为在不同参数下的良好过渡。算法收敛理论为参数设计提供了指导， 4 第一章绪论 而实际设计时也可根据优化过程的动态性能按规则自适应调节参数。 6 算法终止准则的设计 终止准则是判断算法是否收敛的标准，决定了算法的最终优化性能。算法收敛理论 为终止准则提供了明确的设计方案，但是基于理论分析所得的收敛准则往往是很苛刻 的，甚至难以应用。实际设计时，应兼顾算法的优化质量和搜索效率等多方面性能，或 根据问题需要着重强调算法的某方面性能，采用与算法性能指标相关的近似收敛准则， 如给定最大迭代次数、最优解的最大停滞次数和最小偏差阈值等。 在算法设计时，总是希望优化算法具有各种优良性能，对复杂问题尤其要求算法具 有避免陷入局部极小和全局优化能力。但是我们也应该看到，依赖于单一邻域结构的搜 索算法一般是难以实行高效优化的，所以基于混合邻域结构的搜索算法日益受到重视。 没有一种方法对任何问题都是有效的，各方法均有其相应的适用域，而算法的混合正是 扬长避短、拓宽其适用域和提高性能的有效手段。 目前混合优化算法的结构类型主要可归纳为串行、镶嵌、并行和混合结构。 总之，通过对上述关键问题合理和多样化的处理，就可以构造出各种复杂结构的性 能高效的混合优化算法。 1 4 本文基本结构 本文的研究内容将具体分为以下几个部分展开： 第二章：在介绍a c o 算法基本原理的基础上，以经典组合优化问题一t s p 问题为 例，详细介绍了其解决组合优化问题的基本框架。 第三章；为克服a c o 算法易出现停滞现象和陷入局部最优的缺陷，我们提出了一 种新型混合优化算法，即基于禁忌搜索的蚁群优化算法( t s b a c o ) ，并将该算法用于最 大独立集问题的求解。随后研究了t s b a c o 算法中各种参数设置对算法性能的影响， 提出了针对相关参数的改进策略，获得了比较好的实验效果。 第四章；提出了一种单通道冗余v l s i 阵列重构算法，根据阵列中缺陷单元的分布情 况，可以将阵列重构问题转换为求解矛盾图的独立集问题，通过t s b a c o 算法对矛盾图 独立集的求解可以有效解决阵列容错问题。 第五章：提出了一种网络流量测量中的有效测量点选择算法，根据网络流量测量模 型，可以将测量点选择问题抽象为图论中的最小弱顶点覆盖问题，通过t s b a c o 算法 对最小弱项点覆盖问题的求解可以有效解决网络流量测量问题。 第六章：总结了本文的主要内容，并且展望了a c o 算法今后的发展之路。 5 江南大学硕士学位论文 第二章蚁群优化算法 受到自然界中真实蚁群集体行为的启发，意大利学者m d o d g o 于1 9 9 1 年，在他 的博士论文中首次系统地提出了一种基于蚂蚁种群的新型优化算法蚁群算法( a n t c o l o n ya l g o r i t h m ) 。该算法采用了分布式并行计算机制，易于与其他方法结合，而且具 有较强的鲁棒性，但搜索时间长、易陷入局部最优解是其最为突出的缺点。蚁群算法最 早成功应用于解决旅行商等组合优化问题，并且在解决这类问题中取得了一系列较好的 实验结果，受其影响，该算法逐渐引起了许多研究者的注意，并将其应用到许多实际工 程问题中。 2 1 蚁群算法的基本原理 2 1 1 蚁群行为描述 根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放 出一种特殊的分泌物( 信息素) 来寻找路径。当它们碰到一个还没有走过的路口时，就随 机地挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则 释放的信息素越少。当后来的蚂蚁再次碰到这个路口时，选择信息量较大路径的概率相 对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越多，而其它路径上 的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出一条最优路径。同时蚁 群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快地重 新找到最优路径。可见，这整个寻优过程中，虽然单只蚂蚁的选择能力有限，但是通过 信息素的作用使整个蚁群行为具有非常高的自组织性，蚂蚁之间交换着路径信息，最终 通过蚁群的集体自催化行为找出最优路径。这里用如图所示的形象图例来进一步说明蚁 群的搜索原理。 e ( a ) f ee f f ( b ) 图2 - 1 蚂蚁觅食模拟 f i g 2 1a n t sf o r a g es i m u l a ti o n 6 ( c ) 第二苹蚁群优化算法 图2 1 中，设a 点是巢穴，d 点足事物源，e f 为某一障碍物。由于障碍物的存在， 蚂蚁只能由a 经e 或f 到达d ，或由d 到达a ，各点之间的距离如图2 1 ( a ) 所示。假设 每个时间单位有3 0 只蚂蚁由a 点到达d 点，有3 0 只蚂蚁由d 点到达a 点，蚂蚁经过 后留下的信息量为1 。为了方便起见，设该物质停留时间为l 。在初始时刻，由于路径 b f 、f c 、b e 和e c 上均无信息量存在，位于a 和d 点蚂蚁可以随机选择路径，从统计 学的角度可以认为蚂蚁以相同的概率选择b f 、f c 、b e 和e c ，如图2 1 ( b ) 所示。经过 一个时间单位后，在路径b f c 上的信息量是路径b e c 上信息量的2 倍。又经过一段时 间，将有2 0 只蚂蚁由b 、f 和c 点到达d 点，如图2 1 ( c ) 所示。随着时间的推移，蚂 蚁将会以越来越大的概率选择路径b f c ，最终将会完全选择路径b f c ，从而找到由巢穴 到事物源的最短路径。 2 1 2 蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的启发式算法引入的，该算法基于 如下基本假设： ( 1 ) 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出 反应，也只对其周围的局部环境产生影响。 ( 2 ) 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际 上是其基因的适应性表现，即蚂蚁是反应型适应性主体。 ( 3 ) 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁 的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和 协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂 蚁越多，信息素量越大，则该路径越容易被选择，时间越长，信息素量会越小；在协作 阶段，候选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习 机制。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求 问题的每方面都有详尽的认识。自组织本质上是蚁群算法机制在没有外界作用下使系 统熵增加的动态过程，体现了从无序到有序的动态演化，其逻辑结构如图2 2 所示。 由图2 2 可见，基本蚁群算法的逻辑结构可知：可以先将具体的组合优化问题表述 成规范的格式，然后利用蚁群算法在“探索( e x p l o r a t i o n ) 和“利用( e x p l o i t a t i o n ) 之间 根据信息素这一反馈载体确定决策点，同时按照相应得信息素更新规则对每只蚂蚁个体 的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可 求解出组合优化问题的最优解。 蚁群算法就是根据蚂蚁群体觅食行为的规律，建立的一个利用群体智能进行优化搜 索的模型，相对其他的各类启发式搜索算法，蚁群优化算法具有明显的优越性。它在众 多n p h a r d 组合优化问题的求解中取得了卓有成效的结果，其典型代表有旅行商问题 ( t s p ) 、指派问题( q a p ) 、作业调度问题( j s p ) 、车辆路线问题( v r p ) 等经典组合优化问题。 蚁群算法为n p h a r d 组合优化问题提供了新颖且有竞争力的求解方法。 7 江南大学硕士学位论文 图2 - 2 基本蚁群算法的逻辑结构 f i g 2 - 2l o g i c a lo r g a n i z a t i o no fb a s i ca n tc o l o n ya l g o r i t h m 2 1 3 人工蚂蚁与真实蚂蚁的异同 在蚁群算法中，提出了人工蚂蚁的概念。人工蚂蚁有着双重特性：一方面，它们是 真实蚂蚁行为特征的一种抽象，通过对真实蚂蚁行为的观察，将蚁群觅食行为中最为关 键的部分赋予了人工蚂蚁；另一方面，由于所提出的人工蚂蚁是为了解决一些工程实际 中的优化问题，因此为了能够使蚁群算法更加有效，人工蚂蚁具备了一些真实蚂蚁所不 具备的本领。 人工蚂蚁大部分的行为特征都源于真实蚂蚁，它们具有的共同特征主要表现如下： 1 人工蚂蚁和真实蚂蚁一样，是一群相互合作的个体。 这些个体可以通过相互的协作在全局范围内找出问题较优的解决方案。每只人工蚁 能够建立起一种解决万案，但高质量的解决方案是整个蚁群合作的结果。 2 人工蚂蚁和真实蚂蚁有着共同的任务。 人工蚂蚁和真实蚂蚁的共同任务，就是寻找连接起点( 蚁穴) 和终点( 食物源) 的最短 路径( 最小代价) 。真实蚂蚁不能跳跃，它们只能沿着相邻区域的状态行进，人工蚂蚁也 一样，只能一步一步地沿着问题的邻近状态转移。 3 人工蚂蚁和真实蚂蚁一样也通过信息素进行间接通讯。 8 第二章蚁群优化算法 人工蚂蚁能够在全局范围内释放信息素，这些信息素被局部地存于它们所经过的问 题状态中。在人工蚁群算法中信息素轨迹是通过状态变量来表示的。状态变量用一个 刀7 的信息素矩阵来表示，其中刀表示问题规模，在旅行商问题中为城市数。矩阵中的 元素值表示在节点f 选择节点，作为移动方向的期望值。随着蚂蚁在所经过的路径上释 放信息素的增多，矩阵中的相应项也随之改变。人工蚁群算法就是通过修改矩阵中元素 的值来模拟自然界中的信息素轨迹更新的过程。 与真实蚂蚁的间接通讯相似，人工蚂蚁之间的通讯也有两个主要特征： ( 1 ) 模拟真实蚂蚁信息素的释放 通过给问题状态分配合适的状态变量来模拟仿真真实蚂蚁信息素的释放。 ( 2 ) 状态变量只能被人工蚂蚁局部到达 在人工蚁群中，人工信息素轨迹是一种分布式的数值信息。只有经过信息素轨迹的 人工蚂蚁使用相应的状态变量来表明它感受到了信息素，相反，没有经过该轨迹就不能 感受到相应的信息素。蚂蚁通过修改这些信息来反映它们在解决一个具体问题时所积累 的经验。在蚁群算法中，局部的人工信息素轨迹是人工蚂蚁进行通讯的唯一渠道。 4 人工蚂蚁利用了真实蚂蚁觅食行为中的自催化机制正反馈。 当一些路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，使得信息 素强度增大。根据蚂蚁倾向于选择信息强度大的路径的特点，后来的蚂蚁选择该路径的 概率也越高，从而又增加该路径的信息素强度，这种选择过程称为自催化过程。自催化 机制利用信息作为反馈，通过对系统演化过程中较优解的自增强作用，使得问题的解向 着全局最优的方向不断进化，最终能够有效地获得相对较优解。正反馈在基于群体的优 化算法中是一个强有力的机制。但在使用正反馈时，要注意避免早熟收敛。 5 信息素的挥发机制。 在蚁群算法中存在着一种挥发机制，类似于真实信息素的挥发。这种机制可以使蚂 蚁逐渐忘记过去，不受过去经验的过分约束，这有利于指引蚂蚁向着新的方向搜索，避 免早熟收敛。 6 不预测未来状态概率的状态转移策略 一 人工蚂蚁和真实蚂蚁一样，应用概率的决策机制沿着邻近状态移动，从而建立起问 题的解决方案。人工蚂蚁的策略只是充分利用了局部信息，而并没有利用前瞻性来预测 未来的状态。因此，所应用的策略在时间和空间上是完全局部的。这个策略既是一个由 问题状态所表示的信息函数，又是一个由过去的蚂蚁引起的环境局部改变的函数。 人工蚂蚁拥有一些真实蚂蚁所不具备的行为特征，主要表现在以下五个方面： 1 人工蚂蚁存在于一个离散的空间中，它们的移动实质上是从一个离散状态到另 一个离散状态的转换。 2 人工蚂蚁具有一个记忆其本身过去行为的内在状态。 3 人工蚂蚁存在于一个与时间无关联的环境之中。人工蚂蚁释放信息素的时间可 以视情况而定，而真实蚂蚁是在移动的同时释放信息素。人工蚂蚁可以在建立了一个可 行的解决方案之后再进行信息素的更新。 9 江南大学硕士学位论文 4 人工蚂蚁的运动不是完全盲目的，它要受到问题空间特征的启发。 5 为了系统的总体性能，蚁群被赋予了很多其他的本领，如前瞻性、局部优化、 原路返回等等。在许多实际工程应用中，蚁群算法还加入了局部更新规则。 2 1 4 蚁群算法的实