（计算机软件与理论专业论文）大规模组合优化问题蚁群算法应用研究.pdf

郑重声明 y 9 7 7 2 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿崽承担由此产生的一切 法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ：蘸费乐 ) 形年，月f 日 大规模组合优化问题蚁群算法应用研究 摘要 蚁群算法作为一种新型的模拟进化算法，是由意大利学者m a c r od o r i g o 等最 早提出，它在解决组合优化问题方面效果显著。但是蚁群算法在求解大规模组合 优化问题时其求解速度过慢，为了将蚁群算法成功的引入大规模组合优化问题的 解决当中，本文在深入的探讨了组合优化问题和蚁群系统的基础上，结合了基本 蚁群算法解决大规模组合优化问题的缺点，给出了如何运用蚁群算法解决大规模 组合优化问题的策略以及相应的算法。 由于基本蚁群算法鲁棒性很强可以很容易和别的算法结合，所以改进后的算 法运用了数据聚类，规则集挖掘，遗传算法等知识。为了解决蚁群算法求解大规 模t s p 问题时速度较慢的缺点，本文提出了几点改进措旌，首先，利用遗传算法 对蚁群的参数进行了进化，得到了较为理想的参数配置，该参数配置可以针对问 题规模的大小对参数进行合理配置，而合理配置的蚁群算法参数有利于算法运行 速度的提高和得到较优的运行结果。其次，利用聚类算法对所给问题进行聚类得 到几个规模较小的子问题，对每个子问题分配参数，然后并行运算，同时针对聚 类算法的波动性进行了一定的探讨。其三，针对蚁群算法中当循环进行到一定程 度的时候，在局部内可能已经存在的局部最优路径，可以通过分类算法将这些局 部内的最优路径找出来，归并为一个城市，并且利用模式学习不断的分析判断求 解得到的局部最优路径是否出现在全局最优路径终，由此可以避免大量的重复计 算：进而减少收敛时间。其四，利用信息熵作为判断算法结束的条件，改变原有 的利用迭代次数最为结束条件的方法。 通过选取t s p l i b 9 5 中几个经典的t s p 问题作为实例进行模拟测试，该算法 对于大规模优化组合问题有一定的解决能力。 关键字：蚁群系统；大规模t s p 问题；聚类算法；遗传算法；模式学习 大规模组合优化问题蚁群算法应用研究 a b s t r a c t a m tc o l o n ya l g o r i t h m ( a c a ) i sa e w n do fs i m u l a t e de v o l u t i a r ya l g o r i t l i m 1 ti sp r o p c db yi t a l i m a c r od 喇9 0 ，a n t l o ya l g o f i l h mh a sm a l l y9 0 0 de 觑c t s w h c ni th a s l v e dt h ec o m b i n a t i o no p t i n l i z a t i o np r o b l 锄h a w e v e r w h e ni tc o m e s l a f g es c a l ec o m b i n a t i a lo p t i l l l i z a t i o np m b l e m ，i t ss e a r c h i n gs p e e di ss l o w i no f d e r t os u c c e 船f i i l l ys o l v el a 唱es c a l e m b i n a t i o n a lo p t i m i z a t i o np m b l e m ，i nt l l i sp a p e i ，o n t l l eb a s i co fd e 印l ys t u d yo fl a q 紧s c a l ec o m b m a t i o n a lo p t i m i z a t i o na l i da 1 l tc o l o n y a l g o r i t l l i l l ，ib m u g l l tu pas t f a t e g y 姐da l g o r i t l l i nf o fs o l v i n gl a 玛es c a l ec o m b i n a t i o n a l o p t i m i z a t i o np r o b l 唧 b e i n go fb a s i ca c a i se a s i l yc o m b i i i e dw i t ho t h e ra l g o r i t h m ，s u c h 硒c l u s t e r i i l g a l g o r i t h m 、g e n e t i ca 1 9 0 r i t l l l na n dd a t am i n i h g ，ib 咖g h tu pf o u rm e a s u r e s f i r s t l y a n e wp a r 锄e t e re v o l u t i o na l g o r j t l l mo fa n tc o l y 趴e v o l u t i o na l g o r i 童l l ma b o u t p a r a m e t e ro f a l i ts y s t e m ，i sp m p o s e di n t h i s p a p e rh e r e c l l i et o t h i se v o l u t i 咖 a l g o r j t h m ，if o u n dp e r f e c tc o n f i g u r a t i o no fp a f a m e t e r ，柚dm i sp 盯啪e t e rc 锄i m p r o v e t h es p e e do fn i n n i n go fa c 九s e c 0 栅y ，l a r g es c a l cc o m b i a t i o n a lo p t i i n i z a t i o n p f o b l e mw 勰p r o v i d e ds o m e np f o b l e mo fl i t t l es c a l ep r o b l e l l fb yu s i n gc l u s t c r i n g a l g o r i l h m ，a t t h es a m et i m e ，a 岫a tw a v eo fd u s t e r i i l ga 1 9 0 r i t l l i n ，s o m ed i s c i l s sa b o u t i tw a sb m u g l l tu p 1 1 i i r d l y b yu s i n go fd a t 昌lm i n i n ga l g 嘶t h m ，i 蕾叫n d0 u ts 伽c1 0 l o p 恤n i z a t i p a t h ，b ym e r g c ro fp a t h0 fl o c a l0 p t i m i z a t i o n ，t h es c a l eo fp r o b l e mw a s r e d u c e d ，a tt i l e s a m et i m e ，t h et i l eo fn l n i i l go fa c aw a sr e d u c e d ，l a s t l y i n f 0 珊a t i o ne n t m p yw a si l l t m d l i c e di n t h i sp a p e r ，i n f o m a t i o ne n t r o p yi n s t e a do f i t e r a t i v ed e g r e ew a su s c do fe n d j i 塔c o n d i t i o n t h er e s u l to f t h ee x p e r i m e n ts u g g c s t st h a tt h ei m p m v e da l g o r i t i l mi se 饪e c t i v e k e yw o r d s ：a n tc o l o n ys y s t e m ；al a 喀es c a l et s p ；d u s t c fa l g o r j t h m ；g e n e t i c a l g o r i t l l m ；m o d e l l e a m i n g ； 2 大规模组合优化问题蚁群算法应用研究 第一章绪论 随着计算机软硬件技术的飞快发展，计算机解决问题的能力越来越强，解决 问题的速度也越来越快，许多实际工程问题往往属于大规模t s p ，例如v l s l 芯 片加工问题( 对应于1 2 1 0 6 城市t s p ，k o n e ，1 9 8 8 ) 、x - r a y ( 对应于1 4 0 0 0 城市 的t s p ，b l 柚d e t a l ，1 9 8 9 ) 、电路板设计中的钻孔问题( 对应于1 7 0 0 0 城市t s p ， 工j t k c ，1 9 8 4 ) ，以及对应于4 4 2 城市b p 的著名p c b 4 4 2 问题( g m t s c h c l e t a l ，1 9 9 1 ) 等，虽然由于硬件速度的提高使得运算速度得到了较大的提高，但是，这个运 算时间还是相当长的，所以为了继续缩短运算时间，在提高硬件质量的同时，改 进算法运行效率也成为一个研究的重点。 社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目 的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研 究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发 现最短路径。受其启发，意大利学者m d o 啦r o ，vm a n i e z z o 和a c o l o m i 通过模 拟蚁群觅食行为提出了一种基于种群的模拟进化算法蚁群优化。该算法的出 现引起了学者们的极大关注，在过去短短十多年的时间里，已在组合优化、网络 路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得 了较好的效果。本论文围绕蚁群优化的原理、理论及其应用，就如何改进基本蚁 群优化算法、蚁群优化的并行实现，蚁群优化算法在组合优化、机器人路径规划 等领域的应用进行了较为深入、系统的研究。 但是由于蚁群算法起步较晚，相比遗传算法等成熟的算法，蚁群算法还存在 很多目前为止没有解决的问题，如计算时间过长，参数设置没有理论指导等等， 对于这些问题，国内外很多的专家学者给予了很多的研究和关注，目前蚁群算法 j 下处于快速发展的阶段。 1 1 研究背景 蚁群算法作为一个新兴的研究方向，目前已经引起了很多专家学者的关注 5 大规模组合优化问题蚊群算法应用研究 大量优秀的论文在各种核心杂志上刊出，这些对蚁群算法的研究起到了很大的推 动作用，蚁群算法由于其本身的特点非常容易和其他算法结合从而解决更多的难 题，遗传算法、聚类算法以及基于规则集的挖掘算法由于其坚定的理论基础已经 被广泛的应用于各个领域。为了弥补蚁群算法本身的种种不足，已经有很多的研 究人员将蚁群算法和遗传算法、聚类算法等其他算法结合，并且取得了较为满意 的结果。 随着计算机并行技术的日渐成熟，计算机的并行能力越来越来强大，解决问 题的速度比以前有了很大的提高，对于大规模的优化组合问题，利用并行计算是 目前最具代表性的解决方法。 为了使蚁群算法也能够解决大规模的组合优化问题，例如大规模t s p 问题， 将蚁群算法和其他算法结合起来，一则可以利用蚁群算法本身的优点，二则利用 别的算法和知识弥补蚁群算法的先天不足。 1 2 我的工作 本文主要内容为：利用蚁群算法解决大规模t s p 问题。针对蚁群算法的不 足指出，本文给出了相应的解决方法。 首先，由于参数是否合理配置对蚁群算法的运行速度和效率有很大的影响， 并且不同规模的t s p 问题其参数要求也是不同的，为了解决蚁群算法的参数设 置问题，本文给出了循环和参数进化的方法进行求解，以得出合适的参数配置。 其二，找到一种好的聚类方法将大规模的1 s p 问题聚类为几个规模较小的 自问题，然后根据每个子问题的规模大小，配置合理的参数利用蚁群算法并行计 算，并且详细探讨了聚类问题的波动性及其减少波动干扰的方法。 其三，虽然问题通过聚类划分为了几个规模较小的子问题，但是对于每个子 问题若其城市数量较大的时候，利用蚁群算法仍然需要较长的收敛时间，为了较 少收敛时间，可以利用分类算法将那些局部内较优的路径找到，由于这些局部最 优路径在每次执行程序时都被运算，但结果又是相同的所以浪费了很多时间，故 此可以把这些局部范围内的最优路径简化为一个城市，通过这个过程，可以将城 市的规模逐渐减少，以达到在较少的时间内完成收敛。 大规模组合优化问题蚁群算法应用研究 其四，找到更好的结束条件，以往蚁群算法的结束条件往往是限定跌代的代 数，即达到限定的代数即可结束算法执行，然而这样做往往浪费大量的计算机时 间，所以找到合适的结束条件势在必行。 我的工作主要是基于以上几个问题作了相应的分析和研究，给出了自己的策 略和改进算法。 7 大规模组合优化问题蚁群算法应用研究 第二章大规模组合优化问题 2 1 组合优化问题概述 组合优化问题广泛存在于经济管理、交通运输、通信网络等领域，其目的主 要是寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中的一个经典而 重要的分支。一些组合优化问题随着规模的扩大，会造成计算规模的迅速增加， 被称为n p 、n p c 和n p _ h a r d 复杂性问题吲。 组合优化问题是一种离散最优化问题，在规划、调度、资源分配、决策等问 题中有着非常广泛的应用。它的数学模型描述为：m i n “x ) s 1 g ( x ) = ox d ，其 中，f ；( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示有限个点组成的集 合。通常，一个组合优化问题可用三参数( d ，f f ) 表示，其中d 表示决策变量的 定义域，f 表示可行解域f = x | x d ，g ( x ) = o ，f 表示目标函数，满足 坟x ) = m i n “均i x f ) 的可行解x 称为问题的最优解【3 7 1 。 虽然目前具有代表性的组合优化问题有很多，但是由于t s p 问题更容易理 解接受也更容易进行实验和理论上的分析，所以本文主要以t s p 问题为例进行 探讨。 2 2 大规模t s p 问题 b p 问题是一种典型的n p - h a r d 组合优化问题，在网络和车辆路由以及 v l s i 芯片设计和电路版布局等领域中存在的组合优化问题可抽象为t s p 旅行商 问题，其特点是迄今还没有一种算法能在多项式时间里找到最优解。能保证此类 问题找到最优解的确定性算法，其运行时间呈指数复杂度。 t s p 问题的描述为：在给定城市个数和各城市之间距离的条件下，找到一 条遍历所有城市且每个城市只能访问一次的总路线最短的路线。其数学描述为： 大规模组合优化问题蚁群算法应用研究 假设有n 个城市，并分别编号，i 城市到 城市之间的距离用d i i 表示，并设该城 市矩阵是对称的，则t s p 问题可表示为：n i i n j - 1l on 1 ( d 兀f n ，+ d 兀n 丌1 ) s t d 日 o 。从以上描述可以看出t s p 是求解总权最小的哈密顿图的问题。 目前，随着计算机软硬件技术的飞快发展，计算机解决问题的能力越来越 强，解决问题的速度也越来越快，在生产和生活中有许多问题往往属于大规模的 髑p 问题，例如：x r a y 问题对应于1 4 0 0 0 城市的t s p 、电路板设计中的钻孔问 题对应于1 7 咖城市t s p 虽然由于硬件速度的提高使得运算速度得到了较大的 提高，但是，相比于人类所需要的运算时间，这个运算时间还是很长的，所以为 了继续缩短运算时间，在提高硬件质量的同时，改进算法运行效率也成为一个研 究的重点。本文便是以t s p 问题为例讨论了如何以蚁群算法求解大规模组合优 化问题。 9 人规模组台优化问题蚁群算法应用研究 3 1 蚁群系统概论 第三章蚁群系统( a c s ) 蚂蚁是最古老的社会昆虫之一，它的个体结构和行为虽简单，但是由这些简 单个体构成的蚂蚁群体，却表现出高度结构化的社会组织。蚂蚁王国俨然是一个 小小“社会”。在这里，有专司产卵的蚁后；有为数众多的从事觅食打猎、兴建 屋穴、抚育后代的工蚁；有负责守卫门户、对敌作战的兵蚁；还有专备为蚁后招 婿纳赘的雄蚁等等。蚂蚁是社会性昆虫，组成社会的三要素之一就是社会成员除 有组织、有分工之外，还有相互的通讯和信息传递。研究表明，蚁群有着奇妙的 信息系统。其中包括视觉信号、声音通讯和更为独特的无声语言，即包括化学物 质不同的组合、触角信号和身体动作在内的多个征集系统，来策动其它个体。蚂 蚁特有的控制自身环境的能力，是在高级形式的社会性行为及不断进化过程中获 得的。觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究，发现 蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环 境变化适应性地搜索新的路径，产生新的选择。虽然单个蚂蚁的行为极其简单， 但是，由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为，能够完成复杂 的任务【。 通过生物学家和仿生学家大量的细致观察研究发现，蚂蚁在觅食走过的路径 上释放一种蚂蚁特有的分泌物信息激素( p h e r o m o n e ) 。蚂蚁个体之间正是通 过这种信息激素进行信息传递，从而能相互协作，完成复杂任务。在一定范围内 蚂蚁能够察觉到这种信息激素并指导它的行为，当一些路径通过的蚂蚁越多，则 留下的信息激素轨迹( t r a i l ) 也就越多，招致后来更多的蚂蚁选择该路径的概率也 越高，于是越发增加了该路径的信息素强度。这种选择过程称之为蚂蚁的自催化 过程，形成一种j 下反馈机制，可理解为增强型学习系统，蚂蚁最终可以发现最短 路径【洲，这种寻找最优路径的过程可以从下图3 1 看出。 大规模组合优化问题蚁群算法应用研究 f f t = o 时亥0 t = 1 时刻t = 1 0 0 时刻 c c 图3 1 蚂蚁寻找路径模拟图 在图3 1 中，a 点表示蚁巢，e 点表示食物，f g 、g h 、h c 分别为三个障碍 物，蚂蚁若要从b 点到达d 点，可以经由b f d ，b g d ，b h d ，b c d 四条路径， 图中采用红、黄、蓝、紫四种颜色代表该路径上遗留的信息素的强度，从红到紫， 信息素强度依次增强，在t = 0 时刻，由于在此前各条路径上没有蚂蚁经过，所 以没有任何信息素遗留，故此，每只蚂蚁以相等的概率判断下一步的要走的路径， 在t = 1 时刻，由于各条路径的长短不同，较长路径上信息素挥发较多，所以此 时短路径上相对有较多的信息素，故此，b g d 和b h d 采用黄色线，而b f d 和 b h d 采用红色线，当t = 1 0 0 时，可以看出，路经b h d 上遗留的信息素最为多， 而b f d 上遗留的信息素最少。 正是基于了蚁群的这种特点，意大利学者m d 0 r i g o 、vm a n i e z z o 、a c o o l r i n i 等人提出了一种新型的模拟进化算法蚁群算法，也可以称之为蚁群 大规模组合优化问题蚁群算法应用研究 系统，该算法通过模拟自然界蚂蚁寻找路径的方法求解诸如t s p 问题、分配问 题、工作调度等问题均取得了较好的结果。 3 2 蚁群系统的模型 3 2 1 蚁群算法流程 虽然基本蚁群算法是在模拟自然界蚂蚁寻找路径的基础上得来的，但是人工 蚂蚁和自然蚂蚁有所区别，它与自然蚂蚁最大的不同在于它具有一定的记忆功 能，这种记忆功能可以使蚂蚁具备一定的视觉能力，在算法上表现为设置一个称 之为t a b u 的数据结构，该数据结构储存了该蚂蚁已走过的路经，通过t a b u 这个 数据结构可以防止蚂蚁重复走过相同的路经，即在寻找下一个城市节点的不会找 到当前节点的祖先节点，同时通过设置t a b u 的大小，可以判断本轮蚂蚁是否走 完了所有的城市，其流程图如下页所示。 大规模组台优化问题蚁群算法应用研究 图3 2 蚁群算法流程图 下面给出基本蚁群算法的算法思想。 算法3 1 初始化。 设黉参数初始值。 置每只蚂蚁到初始城市。 按公式3 1 计算每只蚂蚁下一步要转移的城市。 按公式3 2 执行局部更新规则。 循环执行步骤 ， 直到每只蚂蚁都已完成，然后执行下一步。 若每只蚂蚁都已遍历所有城市，则执行下一步，否则转至 。 按公式3 3 执行全局更新规则。 大规模组台优化问题蚁群算法应用研究 循环执行步骤 ，直到重复执行的次数超过规定的次数，或所求解 无明显改进。 = 1 0 参数循环是否结束，否，更新参数转至 ，是，继续下一步。 3 2 0 蚁群算法参数及公式 本文以平面上n 个城市t s p 问题为例说明基本蚁群系统模型，为此首先引入 如下记号： n ：城市的数量( o ，1 ，n 一1 表示城市序号) ； m ：蚁群中蚂蚁的数量； d 。j ( j ，j ：1 ，2 ，n ) ：表示城市i 和城市j 之问的距离； tt j ( t ) ：表示t 时刻在i j 连线上即城市i j 之间残留的信息量，ti j ( o ) = c ( c 为常数) 为初始时刻各条路径上的信息素初始量，蚂蚁k 在运动过程中根据 各条路径上的信息量计算选择各条路径的概率p k 然后选择概率最大的那条 路径； p 。t j ( t ) ：表示在t 时刻蚂蚁k 由位置i 转移到位置j 的概率，下面给出该概 率的计算公式。 p j 一拦亦砒眦d 。( 船1 ) 5 n l t ；l ，e d。 式3 1 中口f f d w 耐 = 0 ，1 ，n 一1 卜衄妇t ，细妇t ( k = 0 ，l ，n 一1 ) 表示蚂 蚁k 下一步允许选择的城市，叩。i 表示由城市i 转移到城市j 期望程度，可根据某 种启发式算法具体确定，在本文中规定叩。= 1 d ， 根据自然规律，随着时间的推移，每条路径上以前留下的信息素应逐渐消逝， 所以经过一段时间之后算法要对每条路径进行信息素更新，但是根据蚁群算法的 特点，本文算法规定了不同的信息素更新规则。 通过分析，本文规定了两种信息素更新规则，即局部更新和全局更新，对于 1 4 大规模组合优化问题蚁群算法应用研究 局部更新和全局更新本文分别介绍如下： 局部更新：蚂蚁每走一步都要进行的信息素更新，即每只蚂蚁从一个城市到 达另外一个城市之后立刻进行信息素的更新，在经过w 个时刻之后，本文规 定的局部更新规则如下： 勺o + 。) 一( 1 一，) 勺( f ) + ，。勺 ( 式3 2 ) 全局更新：不再适用于所有蚂蚁，而是只对每一次循环中最优的蚂蚁使用该 更新规则，经过了n 个时刻，更新规则如下： f “( f + 。) 掌( 1 p g 曲“) + f # o ) + p g k k f + f u ( 式3 3 ) 式3 3 中2 荟f ：，第。只蚂蚁在本次循环中留在路径1 ，3 上的信息素的浓度，h 本次循环所有蚂蚁在路径( i ，j ) 上所释放的所有信 息素浓度之和。 在基本蚁群算法提出的时候，d o r i g o m 曾根据信息素的更新时刻和更新量的 不同，他给出3 种不同模型，分别称之为a n tc y c l es y s t e m ( a c s ) ，a n tq u a n t i t y s y s t e m ( a q s ) ，a n td e n s i t ys y s t e m ( a d s ) ，它们的主要区别在于： ( 1 ) 信息素的更新时刻不同：a c s 模型是在蚂蚁走完全程，回到起点时按式； ( 2 ) 更新信息素，而a q s 、a d s 模型则是在蚂蚁每到达一个城市就更新它所走 过的边上的信息素； ( 3 ) 每次信息素更新的量a f ：不同，它们的区别在于后两种模型中利用的是 局部信息，而前者利用的是整体信息，下面分别给出其公式。 a c s 模型 吲； io l a q s 模型 叫弘 若第七只蚂蚁经过边( f ，_ ) ( 式3 4 ) 否则 若第七只蚂蚁经过边( f ，) ( 式3 5 ) 否则 大规模组合优化问题蚁群算法应用研究 a d s 模型 呓一 孑薯盖七只蚂蚁经过边a 。式。删 在式3 4 中，l 表示第k 只蚂蚁在本次循环中所走路径的长度，卜p 表示 信息消逝程度。 蚁群算法中所使用的主要参数有：m 、c 、q 、且、p1 、pg 、q 。在3 3 章 中本文会给出详细的分析和讨论。 3 2 3 蚁群算法的优缺点及目前研究的难点 对比以往的其他模拟进化算法，蚁群算法具有如下几种优点： ( 1 ) 较强的鲁棒性：基本蚁群模型稍加修改，便可以应用于其它问题； ( 2 ) 分布式计算：基本蚁群算法是一种基于种群的进化算法，具有其本质上 的并行性，易于并行实现； ( 3 ) 与其它方法结合：基本蚁群算法可以与多种其他启发式算法相结合，以 改善基本蚁群算法的性能； 该算法的其中一个主要缺陷是计算时间较长，随着计算机的发展和计算速度 的提高，可以弥补这一缺陷。蚁群算法的研究刚刚开始，远未象g a 、s a 等算 法那样形成系统的分析方法和坚实的数学基础，有许多问题有待进一步研究。但 是目前的研究初步显示出其优势，随着研究的深入，该方法必将获得越来越广泛 的应用【矧。 蚁群算法具有很强的发现较好解的能力，不容易陷入局部最优，这是因为该 算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质 并行的算法，个体之间不断进行信息交流和传递，有利于发现较好解。单个个体 容易收敛于局部最优，多个个体通过合作，很快收敛于解空间的某一子集，有利 于对解空间的进一步探索，从而不容易陷入局部最优，有利于发现较好解。但是， 这种算法也存在一些缺陷，如：需要较长的搜索时间，对于这一问题，以往的很 多学者也曾经指出过，但没有提出改善方法。虽然计算机计算速度的提高和蚁群 太规模组合优化问题蚁群算法应用研究 算法的本质并行性在一定程度上可以缓解这一问题。但是，对于大规模优化问题， 这还是一个很大的障碍。蚁群中各个体的运动是随机的，虽然通过信息交换能够 向着最优路径进化，但是，当群体规模较大时，很难在较短的时间内从大量杂乱 无章的路径中找出一条较好的路径。这是因为在进化的初级阶段，各个路径上信 息量相差不明显，通过信息正反馈，使得较好路径上的信息量逐渐增大，经过较 长一段时间，才能使得较好路径上的信息量明显高于其它路径上的信息量，随着 这一过程的进行，差别越来越明显，从而最终收敛于较好的路径。这一过程一般 需要较长的时间【1 6 1 。 由前面对蚁群算法的介绍可知，蚁群算法在运算过程中，蚁群的转移是由各 条路径上留下的信息量的强度和城市之间的距离来引导的。蚁群运动的路径总是 趋近于信息量最强的路径。通过对蚁群以及蚁群算法的研究表明，不论是真实蚁 群系统还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径 比较接近。然而，信息量最强的路径不是所需要的最优路径的情况仍然存在，而 且在人工蚁群系统中，这种现象经常出现。这是由于在人工蚁群系统中，各路径 上的初始信息量是相同的，蚁群创建的第一条路径所用到的信息就主要是城市之 间的距离信息，这时，蚁群算法将等价于贪心算法，这一次蚁群在所经过的路径 上留下的信息就不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或 者所计算的路径的组合较多时，就更不能保证蚁群创建的第一条路径能引导蚁群 走向全局最优路径。这一次循环中，蚁群留下的信息会因正反馈作用使这条不是 最优，而且可能是离最优解相差很远的路径上的信息得到不应有的增强而阻碍以 后的蚂蚁发现更好的全局最优解。不仅是第一次循环所创建的路径可能对蚁群产 生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上， 这次循环所产生的路径就可能会对以后蚁群的选择产生误导。因此，蚁群所找出 的解需要通过一定的方法来增强，使蚁群所留下的信息尽可能地不对以后的蚁群 产生误导1 2 1 】。 1 7 人规模组合优化问题蚁群算法应用研究 3 3 参数设置的重要性和盲目性及参数进化算法 3 3 1 参数设置的重要性及盲目性 基本蚁群算法中n 、b 、p 等参数的设置对算法性能有很大的影响，算法运 行速度的快慢以及算法运行结果的优异程度，在很大程度上取决于所选参数是否 合适。例如：a 值的大小表明留在每个结点上的信息量受重视的程度，a 值越大， 蚂蚁选择以前经过的路线的可能性越大，但过大会使搜索过早陷于局部最小解； b 的大小表明启发式信息受重视的程度，b 值越大，蚂蚁选择离它近的城市的可 能性也越大；p 表示信息素的保留率，如果它的值取得不恰当，得到的结果会很 差。根据以上分析，参数n 、b 、p 的最佳配置，对发挥蚁群算法在实际问题中 的作用有很重要的意义，下面给出各个参数的意义和他们对算法的影响【2 0 1 。 从历年发表的国内外文献看，目前关于蚁群算法中参数设置的合理性研究还 都是处于基于实验分析，其实验参数的确定没有理论上的指导大多是通过经验得 出，许多理论问题有待进一步研究。 表3 1 中本文给出算法中最主要参数的意义及它设置不当时对算法所造成的 影响。 表3 1 蚁群算法参数意义及影响 参数名称参数意义参数设置过小 参数设置过大 m 蚂蚁数量交流的信息量太少很难 运行时间过长 找到晟优路径 q 轨迹路径长度影响收敛速度算法不能收敛到较优解 残留信息的相对重要选择走过路径的可能性 过早陷于局部最优 程度太小 b 期望值相对重要程度过早陷于局部最优选择走过的可能性小 p残留信息的保留率 挥发过大不易传递信息 挥发小积累信息小，不易 更新 丈规模组合优化问题蚁群算法应用研究 对于如何寻找基本蚁群算法合适的参数配置，基本上有两种方法：其一是通 过循环设置参数，然后将每组参数配置给基本蚁群算，然后通过分析算法运行的 时间和结果，对改组参数是否优异进行判断。其二是通过遗传算法对参数进行进 化，将参数翻译为染色体代码之后，通过遗传算法的交叉和变异算子不断生成新 的代码，再寻找合适的适应度函数对这些代码进行计算，根据适应度函数计算的 结果分析这些参数组合的性能。下面主要通过第二种方法对基本蚁群算参数进行 分析。 3 3 2 实数编码 遗传算法( g e n e t i c g 耐t h m ，g a ) 是近年来迅速发展起来的一种全新的随机 搜索与优化算法，其基本思想是基于d a 九v i n 的进化论和m e n d e l 的遗传学说。该 算法由密执安大学教授h o l l a n d 及其学生于1 9 7 5 年创建忱此后，遗传算法的研 究引起了国内外学者的关注。自1 9 8 5 年以来，国际上已召开了多次遗传算法的 学术会议和研讨会，国际遗传算法学会组织召开的i c g h t 锄a t i o n a lc o n f c r e n c e g e n c t i c 舢g 嘶t h m s ) 会议和f o g a ( w b r k s h o po nf o u d a t i o no fg e n e t i ca l g o r i t h m s ) 会议，为研究和应用遗传算法提供了国际交流的机会。近年来，遗传算法已被成功 地应用于工业、经济管理、交通运输、工业设计等不同领域，解决了许多问题。 例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、 图像处理以及数据挖掘等。本文将从遗传算法的理论和技术两方面概述目前的研 究现状，描述遗传算法的主要特点、基本原理以及各种改进算法，介绍遗传算法 的应用领域，并对遗传算法的性能进行分析。 与传统搜索算法不同，遗传算法从一组随机产生的初始解，称为群体，开始 搜索过程。群体中的每个个体是问题的一个解，称为染色体。这些染色体在后续 迭代中不断进化，称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交 叉或变异运算生成下一代染色体，称为后代。染色体的好坏用适应度来衡量。根 据适应度的大小从上一代和后代中选择一定数量的个体，作为下一代群体，再继 续进化，这样经过若干代之后，算法收敛于最好的染色体。它很可能就是问题的 最优解或次优解。遗传算法中使用适应度这个概念来度量群体中的各个个体的在 优化计算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函 火规模组台优化问题蚁群算法应用研究 数。适应度函数的定义一般与具体求解问题有关。 遗传算法自其创始人h o l l 如d 于7 0 年代初提出以来，h o l l a i l d 最初提出的遗 传算法是采用二进制编码的【”。后来通过许多学者对遗传算法进行的各种改进， 有人提出了十进制编码。编码机制对遗传算法的性能影响很大。到底该采用二进 制编码还是采用十进制编码。针对这一问题对二进制编码与十进制编码在搜索能 力与保持种群稳定性方面做了定量的分析【3 3 1 。 通过比较可以发现，在对参数进行进化时，利用实数进行编码具有比二进制 更加适合的优点，所以本文所用遗传算法的染色体编码采用的是实数编码。实数 编码遗传算法的发展时间并不长，但对于参数十连续型变量的数值优化问题，直 接采用实数表示基因是特别自然的，它与传统遗传算法( 二进制编码遗传算法) 不同的是：直接采用实数表示基因，等位基因就是实数的取值，染色体则是一个 实数向量，染色体的长度即此实数的大小。目前，实数编码遗传算法已引起越来 越多的专家学者的关注，而且取得了大量的理论研究成果和应用研究成果。 实数编码直接使用问题变量进行编码。 染色体】【的形式为：x x 。，x 2 ，溉，溉) ，) ( i 属于实数，i = 1 ，2 ，n 。 使用这种编码的遗传算法称为实数编码遗传算法( r e a l c o d e dg e n e t i c 触9 0 r i t j l m ，简称r c g a ) 。实数编码遗传算法具有精度高，便于大空间搜索等优 点，本文仅限于概括介绍实数编码遗传算法的发展及已有的研究成果。本文提出 的浮点数编码遗传算法步骤总结如下f 4 3 】： ( 1 ) n 个指定范围内的浮点数排列在一起成为一个个体随机产生p 0 p 个这 样的个体作为初始种群； ( 2 ) 计算每一个体的目标函数值并对这p 0 p 个函数值由小到大排序，记录最 优个体； ( 3 ) 淘汰m 个较大函数值对应的个体并分别替换成m 个较小函数值对应的 个体； ( 4 ) 对这p o p 个个体随机两两配对，按一指定概率p c 进行式( 1 ) 的交叉操作； ( 5 ) 对每一个体中的每一参数，按一指定概率p m 进行式( 3 ) 的变异操作； ( 6 ) 删除种群中一任意个体并替换成步骤( 2 ) 中记录的最优个体； f 7 ) 若满足收敛条件则输出最优解并退出，否则转向步骤( 2 ) 。 人规模纰台优化问题蚁群算法麻用研究 图3 3 遗传算法流程图 3 3 3 利用遗传算法对参数进行进化 自 然 选 择 目前，确定这些蚁群算法参数的方法还没有可靠的理论依据，很多学者在分 配参数的主要还是参照以前实验得到参数数值，目前最常用的做法是从实验中观 察、比较。主要的方法有两种： ( 1 ) 利用循环和计算机的并行计算比较不同的参数组合，然后比较不同参数 所得结果以确定合理的参数。 有性生殖 大规模组合优化问题蚁群算法应用研究 ( 2 ) 利用遗传算法，将蚁群算法中的参数看作是染色体g 中的代码，然后利 用实数编码技术将此染色体通过遗传算子交由一个进化过程处理，通过 一系列的进化处理，最终会得到一个较为理想的染色体，对该染色体翻 译之后可以得到所需要的参数配置。 以下是利用实数编码的遗传算法对蚁群参数进行进化计算的算法流程： 算法3 2 初始化。 初始化种群 从种群中利用选择算子选择杂交的父染色体。 “ 利用杂交算法对选择出的父染色体进行杂交，得到新的种群。 ( 5 按照一定概率进行变异。 将得到的种群翻译为蚁群算法的参数然后传送给蚁群算法。 利用 中得到的参数运行基本蚁群算法。 利用 中得到的结果计算适用度。 记录本轮循环的结果。 算法是否结束，否，转至( 3 ，是，继续下一步。 1 1 ，统计所有结果，得出最佳适用度函数值时的染色体代码，翻译此代码 得到优化的蚁群算法参数值。 算法中所采用的适应度函数利用如下中所介绍的四个函数的和即： 卢三c t 虾t ，其中f t 是适应度函数中所包涵的子函数，c ；为各个子函数的权值。 在表3 2 中，本文给出了算法中适应度函数所包含的四个函数中参数所代表的意 义，以及每个函数的权值嘲。 大规模组合优化问题蚁群算法应用研究 表3 2 适应度参数意义及权值的大小 适应度公式公式中参数意义 权值 f l = 1 ( l + 1 - l + )l 为本次循环所得最短路径，l + 为所有循环c l 介于o 2 到0 3 之问。 的最短路径。 f 2 = e v 5 木n v 为取得最短路径时的迭代次数，反映运算c 2 介于0 5 到o 8 之间。 的快慢程度。 f 3 = e m 1 0 村1 n 为城市数量，m 为最优路径蚂蚁个数mc 3 = o 5 。 应尽量的小缩短运行时间。 f 4 = e 一6 n 6 = i n t ( a n 幸b ) ，n 为城市耷数，a 和b 参加c 4 介于0 2 到0 5 之间。 进化。i n t 为取整函数。 算法中染色体编码采用实数编码，采用的主要算子如下： 选择算子：轮盘赌选择法。先选定一个参照点，在进行选择时，转动圆盘， 当圆盘停止转动时，参照点落在哪个扇形中就选择哪个扇形对应 的数据f 2 刚。 重组算子：线性重组，子个体= 父个体1 + a ( 父个体2 一父个体1 ) ，n 为比例因子i 删。 变异算子：x 。一o 5 ，a4 薯。z ，“i ) 以概率l m 取值为l ， 以l 一1 m 取值为0 ，m 一般为2 0 ，l 为变量取值范围，x 为变异 前变量取值，x 为变异后取值i 捌。 该算法执行后的结果： 实验中取蚁群的迭代次数为1 0 0 次，进化算法最大代数为4 0 代，共进行8 次进化，以o l i v e r 3 0 和ei 1 7 6 为例，它们采用蚁群算法迭代分别达到最优路径 长度为4 2 4 8 6 9 和5 3 8 时，适应度函数值最高的染色体代码值，经翻译之后统计 结果如图3 4 和图3 5 所示。 大规模组合优化问题蚁群算法应用研究 表3 3 利用o l i v e r3 0 为例进化后结果 cq o 10 p l o c a l pg l 西姐 q ba 1 51 6 9 6 70 1 4 5 l0 2 5 5 80 9 3 8 10 4 9 2 41 2 3 0 49 2 4 l1 0 1 95 1 4 50 1 7 2 60 1 8 6 70 8 6 9 0 1 5 6 7乏9 6 ；6 78 0 7 8 4 1 9 2 15 7 3 2 70 7 0 7 60 2 9 5 2o - 5 2 2 5o 3 7 1 72 4 2 1 42 0 0 8 72 “3 5 9 60 4 3 50 2 0 5 7o 3 9 90 2 8 6 61 5 2 1 32 。3 2 3 42 1 94 4 8 6 90 5 6 7 20 2 7 2 40 5 哇6 5 0 3 跎51 8 6 9 62 9 8 0 l1 6 2 14 3 5 4 40 7 0 9 50 4 4 1 60 8 唾哇 0 3 9 1 12 8 7 7 32 8 5 0 2 3 2 23 3 9 1 70 6 下4 lo 1 7 2 90 5 4 1 30 4 0 1 62 0 0 9 72 2 9 0 3l 1 54 8 0 伯0 4 9 5 5o 2 6 60 5 3 9 6o 4 7 5 92 4 9 0 72 4 6 8 3l 1 3 5 4 8 1 90 。5 0 1 6o 3 0 1 20 6 0 唾10 哇9 1 32 6 2 2 62 3 9 5 i1 5 1 27 5 9 7 40 8 2 0 2 8 5 l0 3 7 7 9o 8 0 5 92 3 3 6 22 8 6 2 61 2 2了5 7 0 30 3 4 9 20 2 7 2 30 唾5 0 20 躬2 92 3 l i ：2 45 2 3 6 21 9 2 06 9 9 3 7o 3 7 3 3o 4 0 1 2o 7 9 5 5 0 3 2 4 5 2 l9 2 1 3 2 6 8 8 51 1 87 2 7 9 30 5 6 3 60 3 5 6 2o 7 4 3 5 0 。4 0 0 32 7 0 4 83 3 3 6 8l 2 17 6 4 7 40 4 3 7 70 3 3 0 50 7 8 1 6o - 4 1 4 3 2 2 3 4 8 2 5 7 7 1l 2 28 。1 0 9 90 4 6 5 20 。3 4 5 l0 8 2 4 60 4 4 22 3 1 9 22 7 1 2 43 2 27 9 8 9 60 4 5 7 9o 。3 4 1 30 8 1 3 5 0 4 3 4 62 2 9 6 52 6 7 6 41 4 1 丁