（计算机应用技术专业论文）应用于tsp问题的蚁群优化算法参数研究.pdf

一一种应用于t s p 问题的蚁群优化算法 论文题目：应用于t s p 问题的蚁群优化算法参数研究 专业：计算机应用技术 硕士生：罗旭耀 指导老师：张军教授 摘要 基于自然的元启发式算法一直是人工智能领域中一个非常重要的研究课题， 在以往的研究工作中，学者们提出了神经网络，模拟退火，遗传算法等许多优秀 的元启发式算法，并在解决各类问题时取得了良好的效果。而作为一种较新颖的 启发式算法，蚁群算法白上个世纪九十年代初诞生以来，一直受到研究人员的关 注。蚁群算法在优化求解许多问题时都能够取得很好的效果，特别是在对一些离 散问题求解时的表现尤其突出。 然而，时至今日蚁群算法还是存在一些内在的问题有待解决。和许多其他的 启发式算法一样，蚁群算法的一个缺点在于，算法的优化性能往往取决于对于算 法控制参数的取值，这些取值在以往的工作中往往是非常机械的，各个参数的取 值也是独立的，如果取值不当，蚁群算法将容易陷入局部最优，并且优化性能也 不理想。 本文对以t s p 问题为优化对象的蚁群优化算法a c s 进行参数研究，分析各 个控制参数在优化过程中对算法的影响，以及某些参数之间的关系。从而制定一 种有效的参数预设规则，在保持算法优化性能的前提下，降低算法参数设置的复 杂度。本文的工作主要可以分为四个部分，第一部分，回顾了一些的经典的蚁群 算法的优化性能及其应用领域，同时研究了它们参数设置的规则。第二部分，描 述a c s 算法，研究收敛状态变化对优化性能的影响。第三部分，通过分析算法 优化原理，研究算法各个参数在迭代过程中对路径构建的作用，选取具体的预设 参数。第四部分，进行a c s 算法的仿真试验，研究参数对优化过程的影响，以 及参数之间的关系，制定一种有效的参数预设规则。本文的研究工作表明，参数 巾山大学硕士学位论文 预设规则应用于不同的t s p 问题实例时都能取得较好的效果，并且对蚁群算法 的参数研究具有很高的发展价值。 关键字：蚁群优化算法，旅行商问题，信息素，路径构建方法，参数设置 i i 一种应用于t s p 问题的蚁群优化算法 t i t l e ：p a r a m e t r i cs t u d yf o ra n tc o l o n yo p t i m i z a t i o na p p l i e dt ot r a v e l i n g s a l e s m a np r o b l e m m a i o r ：c o m p u t e r a p p l i c a t i o na n dt e c h n o l o g y n a m e ：x u y a ol u o s u p e r v i s o r ：p r o 角s s o rj u nz h a n g a b s t r a c t m e t a h e u f i s f i cd e r i v ef o r mn a t u r eh a sb e e ni n v e s t i g a t e da sas i g n i f i c a n ts u b j e c to f a r t i f i c i a li n t e l l i g e n c e m a n ye x c e l l e n tm e t a h e u r i s t i e sw c r ep r o p o s e ds u c ha ss i m u l a t e d a n n e a l i n g , g e n e t i ca l g o r i t h m l 时，算法将很快地陷入停滞的局面，此时，所有的蚂蚁都依照同一条路线 移动，最后构建出同一条路径，而这条路径却常常与优化目标相距甚远。 信息素更新 在所有的蚂蚁都构造好路径后，各边上的信息素将被更新。首先，根据一个 常量参数，减少每一条边的信息素量，然后，增加蚂蚁经过的边的信息素量。信 息素的蒸发根据下面的式子执行 乃4 - ( 1 一p ) 勺， v ( ，) 三， ( 1 - 2 ) 其中p 是信息素蒸发率，0 p 1 。参数p 的作用避免信息素的无限积累，使得 算法可以“忘记”之前选用的低劣的路径。事实上，如果一条边没有被任何蚂蚁 选择，它相应的信息素量将以迭代次数的指数级别递减。信息素蒸发步骤之后， 所有蚂蚁都在它们通过的边上释放信息素； 勺卜勺+ 瞄，v ( ，) 厶( 1 - 3 ) k - 1 0 一种应用于t s p 问题的蚁群优化算法 其中力是第_ j 只蚂蚁向它所有通过的边释放的信息素量。露被定义为 峥p 毗力啦b e l o n g s t o ；矿； c 4 ， 其中c 代表第| | 只蚂蚁建立的路径r 的长度，即r 中所有边的长度之和根据 式子( 1 - 4 ) ，我们可以看到，蚂蚁构建的路径越好，路径上的各条边就会获得更 多的信息素。一般而言，一条边被越多蚂蚁选择，它所在的路径的总长度越短， 就会获取越多的信息素，从而它很有可能会在以后的迭代中被蚂蚁选出。 1 3 2 最大最小蚂蚁系统 最大最小蚂蚁系统( 朋4 荽 ，f 硝a n ts y s t e m ，简称a 4 a 4 a s ) 在a s 算法的 基础上引入了四项主要的改进。首先，它强调了对最优路径的开发：只有迭代最 优蚂蚁( i t e r a t i o n b e s ta n t ) ，也就是在当前迭代中构建出最优路径的蚂蚁，或者 是至今最优蚂蚁，才被允许释放信息素。不幸的是，这种策略可能会导致停滞现 象的出现，即所有的蚂蚁都搜索同一条路径，这是因为某些边含有过量的信息素， 尽管这些边所在的路径是优秀的，却常常不是最优的。为了抵消这种影响， m m a s 提出了另一项修改，就是把信息素量的取值范围限制在一个区间 【? 。，f 一】内。第三，信息索量的初始值将被设定为其取值范围的上界，并与一 个较小的信息素蒸发速率相结合，使算法能在最初的搜索步骤中探索更多可能的 路径。最后，在m m a s 中，每当系统到达了停滞状态，或者在一定数目的迭代 过程中不再有更优的路径出现，则所有的信息素值都会被重新初始化 信息素更新 在所有的蚂蚁都构建完一条路径之后，信息素将根据a s 中的信息索蒸发规 则更新。接着，蚂蚁按照如下规则释放新的信息素。 勺卜勺+ ，( 1 - 5 ) 其中，l “= l ，c 。被允许释放信息素的蚂蚁可以是至今最优的蚂蚁， 9 中山大学硕士学位论文 这时有勺“= i c “，或者是当前迭代最优的蚂蚁，这时有乃“= 1 1 c 4 ，c “ 代表当前迭代的最优路径的长度。一般而言，在m m a s 中，当前迭代最优更新 规则和至今最优更新规则将被轮流使用。显然，使用这两种规则中的某一种的相 对频率将影响到算法的贪婪度：如果信息素一直通过至今最优蚂蚁来更新，则搜 索进程很快会收敛到产附近。然而，如果只使用当前迭代的最优蚂蚁来更新信 息素，则能够获取新信息索的边的数目将会增加，搜索的导向性将会减少。 实验结果表明。在小规模的t s p 实例中，只使用当前迭代最优更新规则可能 会取得最好的性能，然而，对于城市数目多达几百个的大规模t s p 实饲，逐渐 强调至今最优更新规则的使用将使算法获取最优的性能。这一点是可以实现的， 例如，逐渐增加更新至今最优路径7 “的信息素的频率。 信息素限制 在t w a 4 a s 中，任何一条边可能存放的信息素量都被限制在由下界f 盅和上 界f 一限定的一个范围内，以避免算法陷入停滞状态。特别地，这个信息素限制 规则的作用是把位于城市i 的蚂蚁选择城市j 作为下一个访问城市的概率岛限制 在区间【，】内，其中有o 中，如果不满足终止条件，蚂蚁就会移动到它的邻域 a 产以) 中的某个点，上，其中状态 ，p e 老。如果满足至少一个终止条件， 蚂蚁的移动就停止。 一蚂蚁利用概率决策规则进行移动的选择。概率决策规则是一个具有以下参数 变量的函数( 1 ) 局部可用的信息素值和启发值( 也就是指，蚂蚁在的图g 中的当前位置的成分以及( 到邻域的) 连接上的信息素和启发值) ；( 2 ) 蚂 蚁用来保存自己当前状态的私有记忆体；( 3 ) 问题相关的约束。 _ 当蚂蚁添加一个成分c ，到当前状态时，它会更新自身或有关边上的信息素的 值。 一一旦蚂蚁建立了一个解，它可以按原路返回并在返回的过程中对己添加的成 分上的信息索进行更新。 需要注意的一点是，蚂蚁之间是并行独立行动的，尽管每只蚂蚁中的机制已 经足够可以找到问题的一个解( 可能是很差的解) ，但只有通过蚂蚁互相之间的 交互协作，才能产生好的解。这种交互协作正是通过蚂蚁从存储信息素的变量中 阅读和记录有关的信息间接沟通得到的。这其实就是某种程度上的一个分布学习 的过程，每一个单独的蚂蚁并不是基于自身信息进行自我调整的，相反，它们是 根据问题表现的特征和其他蚂蚁所感知的情况地调整自身行为方式的。 1 4 种应用于t s p 问题的蚁群优化算法 最初的蚁群优化算法是应用于优化t s p 问题，不仅如此，我们还发现事实 上大部分蚁群优化算法都曾应用于t s p 问题中。这是由于t s p 问题可以很容易 地转化成构建图的形式求解。t s p 问题是一个涉及到多种实际应用领域的重要的 n t - 难的组合优化问题，其求解的目的就是找到一个代价最小的回路，该回路遍 历一个给定的城市集合中所有城市一次且仅有一次。形式上，t s p 问题可以用一 个带权完全图g = ( ，彳) 来描述，其中是代表城市的结点集合，彳是所有边的 集合。每一条边a r c ( i , j ) a 都分配一个权值( 长度) 矗，它代表城市i 到_ ，之间 的距离大小，其中j e n 。在非对称t s p ( a s y m m e t r i ct s p ) 中，一对结点， 之间的距离是由经过该边的方向决定的，也就是说，至少存在一条边a r c ( , d ， 有力d 。在对称t s p ( s y m m e t r i ct s p ) 中，集合a 中的所有边都必须满足 九= d 。这时t s p 的目标就转化成寻找图中的一条具有最小成本值的哈密顿回 路。t s p 实例的一个解可以用城市序号的一个排列来表示；这个排列是环状的， 在这个排列中城市的绝对位置并不重要，重要的只是城市之间的相对顺序在使用 蚁群算法优化t s p 问题时，基本上都是直接使用t s p 问题形式化描述中的完全 图g = ( n ，) 来作为构建图的。 2 2 蚁群系统( a c s ) 在这一节中，我们将讨论一种的a c o 算法。这种算法的主要思想源于a s 提供的灵感，然而，它使用了未出现在原始a s 中的新机制，进一步地获取更高 的性能。这种算法就是最成功的蚁群优化算法之一的蚁群系统算法。 蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) 由d o r i g o 等于1 9 9 7 年首次提出b 7 l 。 它与a s 的不同之处主要体现在三个方面。第一，它采用了一种更具积极性的动 作选择规则，从而具有比a s 更强的利用蚂蚁积累的经验知识的能力。第二，信 息素蒸发和信息素释放动作只在至今最优路径的边上执行。第三，蚂蚁每一次使 用边q , j ) 从城市i 移动到城市 它就会去掉该边上定量的信息素，增加探索 1 量 中山大学硕士学位论文 其余路径的可能性。下面，我们将更详细的介绍这些改动。 2 2 1a c s 路径构建 在a c s 中，位于城市i 的蚂蚁k ，根据伪随机比例( p s c u d o r a n d o mp r o p o r t i o n a l ) 规则选择城市，作为下一个访问的城市。这个规则由如下等式给出 ，：a r g 僦卅 【乃r 【r ) ，i 邮q 0 ； ( 2 - 1 ) 【五 o t h e r w i s e ； 其中g 是均匀分布在区间 o ，l 】中的一个随机变量，q o ( o q o 1 ) 是一个参数，是 根据式子( 1 - 1 ) 给出的概率分布产生的一个随机变量选择。 我们也可以这样理解，蚂蚁选择当前可能的最优方式移动的概率是吼，这种 最优的移动方式是根据信息素的积累量和启发式信息值求出的( 在这种情况下， 蚂蚁继续开发已知的知识) 。同时，蚂蚁以( 1 - q 。) 的概率有偏向性的探索各条边。 通过调整参数碍o ，我们可以调节对新路径的探索度，决定算法是应该集中搜索至 今最优路径附近的区域，还是应该探索其它的区域。 2 2 2a c s 全局信息素更新 在a c s 中，只有一只蚂蚁( 至今最优蚂蚁) 被允许在每一次迭代之后释放 信息索。这样，a c s 的信息素更新规则由下面的式子给出 巧卜( 1 一力勺+ 出乎，v ( , d t “，( 2 - 2 ) 其中“= i c “。需要特别注意的是，在a c s 的信息素更新规则中，无论是 信息素蒸发动作还是信息素释放动作，都只在构成丁“的边上执行，而不是像a s 那样应用到整个系统的所有边上。这一点是非常重要的，因为这种方式可以把信 息素更新的计算复杂度从o ( n 2 ) 降低到o ( n ) ，月代表待解的t s p 实例的规模。和 1 6 一种应用于t s p 问题的蚁群优化算法 其它方式一样，参数p 代表信息素蒸发速率。与a s 的不同，新释放的信息素量 将乘以参数p ，这使得更新后的信息素量将在旧的信息素量与新释放的信息素量 之间。 在最初的实验中，我们也考虑了选用当前迭代的最优路径作为信息素更新的 对象。尽管在小规模的t s p 实例中，至今最优路径更新方案和当前迭代最优路 径更新方案所能获取的最优解的差别很小，然而，在城市数目大子1 0 0 的较大规 模的t s p 实例中，使用至今最优路径更新方案所能获取的解远优于当前迭代最 优路径更新方案。 2 2 3a c s 局部信息素更新 除了全局信息素更新规则外，a c s 还采用了一个局部信息素更新规则。在路 径构建过程中，蚂蚁每经过一条边，都将立刻调用这条规则更新该边上的信息素。 勺卜o 一孝) 勺+ 善f o ，( 2 - 3 ) 其中， 善和r o 是两个参数，善满足o 善 l ，f o 是信息素量的初始值。在实 验中发现，善取值为o 1 ，f 0 取值为1 n c ”时，算法有较好的性能，其中，一代 表t s p 实例的城市数目，而c “代表由最近相邻方法得到的路径的长度。局部更 新的作用在于，蚂蚁每一次经过边( f ，) ，该边的信息素白将会减少，从而使得 其他蚂蚁选中该边的概率相对减少。在本文中，我们采用的a c s 算法有善= p ， 即局部信息索更新与全局信息素更新采用相同的挥发系数。 需要特别注意的是，在前面关于a s 和a s 的直接后继算法的讨论中，蚂蚁 以顺序方式构建路径，还是以并行方式构建路径，都不会影响算法的行为。然而， 由于局部更新策略的引入，在a c s 中这两种构建方式不再是等价的。目前大部 分的a c s 实现中，我们都选择让所有的蚂蚁并行地工作，尽管目前还没有实验 证据证明哪一种构建方式比另一种好。 中山大学硕士学位论文 a c s 是由一种更早地被g a m b a r d e l l a 与d o r i g o 于1 9 9 5 提出的a n t - q 算法跚 发展而来的。实际上，a c s 与a n t q 的区别仅仅在于f o 的定义。在a n t - q 中，f o 被定义为r o = j m a x l l ( 巧) ，其中，是一个参数。也就是说，如果位于城市i 的 蚂蚁t 的所有未访问的城市( 例如，相邻城市集合中的城市) 构成了一个城 市集合，连接城市i 到城市集合中所有城市的边构成了一个边的集合，那么，我 们选择这个边集合中具有最高信息素含量的边的信息素值作为f 0 定义的依据。 m m a s 与a c s 之间也存在着一个有趣的关系：它们都采用了信息素的限 制，尽管这个限制在a 4 m a s 中是直接给出的，在a c s 中则是隐含的。事实上， 在a c s 的实现过程中，由于在式子( 2 - 2 ) 和( 2 3 ) 给出的信息素更新规则中都 给信息素附加了一个大于或等于f 0 的值，并且信息素初值也被设为r o ，因而， 所有边的信息素值都不会低于矗。另一方面，如前所述，我们可以简单地验证所 有边的信息素值都不会大于1 c “。因此，在a c s 中，一个隐含的信息素限制就 是，保e v ( i , j ) ：r o s i c “。 最后，a c s 也是第一个使用候选列表( c a n d i d a t el i s t ) 限制每一个构建步骤 中可能的选择的数目的a c o 算法。一般而言，候选列表存放了一定数目的根据 某些启发式标准评定出的具有最优等级的选择。在t s p 中，每个城市积口应的候 选列表存放的就是距离i 最近的若干城市，的编号。有多种方式可以确定哪个城 市可以进入候选列表。a c s 最初把城市i 的所有相邻城市按照距离升序排列，并 选择距离最短的c a r d 个城市添加到i 的候选列表，c a ，l d 是给定的一个值。在这 种情况下，候选列表可以在解决t s p 问题之前建立，并且在整个算法执行的过 程中保持不变。一只位于城市i 的蚂蚁将在i 的候选列表中选择一个它未访问过 的城市作为它下一步要访问的城市。仅当候选列表中的所有城市都被该蚂蚁访问 过时，它才会访问不在候选列表中的其它城市。在t s p 中，实验结果表明使用 候选列表将会提高a c o 算法所能获取的解的质量，同时也会明显地加快求解的 速度。 在众多的蚁群优化算法中，比较成功的是最大最小a s 以及a c s ，它们在优 1 8 一种应用于t s p 问题的蚁群优化算法 化许多组合优化问题时都取得了很好的效果。但是，像许多其他的元启发式算法 一样，蚁群优化算法也有不足。在本文中，我们选取了a c s 对t s p 问题的优化 进行研究。 2 3 收敛性与停滞 2 3 1 收敛理论 判断一个元启发式算法性能优劣需要考虑的重要问题之一是看收敛问题 【1 】【2 】：算法能否找出最优解。a c o 算法的工作过程是随机搜索的过程，而由信息 素引起的偏差使得算法不会永远只停留在一个最优解上面。在考察一个随机优化 算法时，要特别关注的是，至少有两种可能的收敛类型：值收敛( c o n v e r g e n c ei n v a l u e ) 和解收敛( c o n v e r g e n c ei ns o l u t i o n ) 。 假定一个问题的最优解有多个，值收敛指的是算法对任意一个最优解的收 敛，要考虑的是算法求得一个最优解至少一次得概率。与值收敛不同，在解收敛 中，研究的是算法进入某种状态的概率，在这种状态下，算法会在迭代过程中持 续地生成某一个相同的最优解。尽管解收敛的状态比值收敛更为理想，但在实际 应用中，解决优化问题时，只要找到一个最优解就可以了，因此在本文后面的讨 论中，我们只关注算法的值收敛情况。 对元启发式算法而言，求解组合优化问题的目的就是得到最优解，也就是 具备值收敛性。在蚁群优化算法中，使用信息素对人工蚂蚁的搜索进行影响，使 得搜索空间随迭代次数增加而逐渐收缩到那些“优秀”的边上，从而提高求解的 质量。然而，许多蚁群算法包括a c s 在一定的迭代次数之后，有可能会进入求 解质量不会随迭代次数上升而有所改进的阶段。如果在进入此阶段以前算法就已 经找到了最优解，那么算法的这一次求解无疑是成功的，然而并不是每一次都能 找到最优解的，如果算法在只找到了局部最优解的情况下就会陷入局部最优，那 对组合优化问题的求解就失败了。而a c s 由于使用了两种不同的路径构建方法， 一定程度上降低了陷入局部最优的可能，但这也使得它的参数设置更加复杂。 中山大学硕士学位论文 2 3 2 判断算法进入停滞的标准 现在的问题就是如何判断a c o 算法在求解t s p 问题时是否进入了停滞期。 本文中涉及的判断标准有以下几种。 1 解的标准差以及变化系数 进入停滞期的算法会只生成一个解，因此计算每个蚂蚁求出解的标准羞仃， 就能判断算法是否进入了停滞期。 f 吒= o 算法停滞( 2 - 4 ) 【吒0 算法未停滞 然而，这种方法的一个缺点是标准差的大小取决于解的绝对值，因此对于 不同的t s p 问题实例来说。使用标准差不能直观地表现算法的停滞状态。还有 一种方法既是使用标准差与平均路径长度的商，即变化系数吒h 。 2 计算结点的选择概率的熵毛的平均值享= ：。c j n s h a n n o n 熵的说明如下：假设样本空间x 有 个事件，事件对应的概率为 a ，我们用函数刀p j ，p 2 ，( s h a n n o n 熵) 来表示样本空间中事件发生的“不确 定性”。 日( 岛，见，以) = 一只l o g p ， ( 2 5 ) 当日的值越大时，表示样本空间中的事件发生的“不确定性”就越高；目 的值越小，则表明“不确定性”越低。 判断算法是否停滞时，在一个结点中，以选择不同分支构造回路为事件来构 建样本空间，结点i 的熵等于岛= 一乃l o g p f ，其中砌是从结点i 选择结点_ ， 作为回路的下个结点的概率，通过类似随机比例规则计算；“l ，n - 1 ) 指的 是可供选择的分支数目然后，在每一次迭代之后计算构建图中所有结点的平均 熵f = 二乓 ，其中n 是t s p 问题中城市的个数。 露0 。篙熟 - 0 ， 1 f 算法未停滞 “ 一种应用于t s p 问题的蚁群优化算法 3 计算五分支因子 a 分支因子的定义基于下面的思想：对于一个给定的城市i ，如果绝大部分 与f 相关的边的信息素含量都很低，只有极少数的边含有大量的信息素，这意味 着在该城市扩展部分路径的选择是十分有限的。如果图中的所有结点同时出现这 种情况，则能被蚂蚁有效搜索的空间将变得相对较小。这样，城市f 的五分支因 子的定义如下：如果f 0 和f 孟分别代表与f 相关的边的最大信息素含量和最小 信息素含量，则与结点f 相关并且信息素含量满足+ 五( f 0 一) 的边的 数目被称为a 分支因子，其中五的取值区间是【o ，1 】，且分支因子的取值区间则 是【2 ，栉一1 】，其中玎是构建图的结点数目( 在t s p 中，胛代表该实例的城市数目) 。 平均a 分支因子驴= 研办是图中所有结点的五分支因子的平均值，它给出了 能被蚂蚁有效搜索的空间的大小。如果驴的值接近3 ，则表示对于每一个结点， 平均有3 条与该点相关的边有较高的概率被选中。 篆2 2 嵩徽 协， 1 6 ， 算法未停滞 这是因为t s p 问题的解是一条环路，所以每个结点的a 分支因子的最小值 为2 ，而当酽= 2 时意味着所有结点的五分支因子都是2 ，算法将反复生成同一 个解，进入停滞。 2 4 经典蚁群算法的不足 蚁群算法作为一种比较新颖的元启发式算法，能够有效地求解组合优化问 题，并且在优化一些组合优化问题( 特别是离散型问题) 时，能够达到甚至超越 其他一些经典的元启发式算法。并且由于元启发式算法的特性，蚁群算法只要进 行少量修改，就能够应用于许多的具体问题当中去。除了处理理论难题之外，蚁 群算法也被众多的学者应用到许多实际应用问题( 例如，水利系统分布问题，网 中山大学硕士学位论文 络路由问题) 当中去，并取得了很好的效果。 然而，蚁群算法本身依然存在不足之处。主要表现在： i 对控制参数的预设取值 算法的优化性能很大程度上依赖于对控制参数的取值。在以往的蚁群算法使 用过程中，大部分都是在优化开始之前分别对控制参数的取值进行人为的预设， 这种方法是非常机械化的，没有规则可言。以t s p 问题为例，每个实例的规模 都不一样，那么每一组控制参数的预设值也相应有所不同。对a c s 算法而言， 由于在构建路径的过程中引入了路盘赌的方法降低了算法陷入局部最优的可能， 但是也因此提高了每组控制参数的预设值的设定难度。但是我们认为可以制定一 种具有普遍性的参数预设规则，降低参数预设的复杂性。 2 容易陷入局部最优 蚁群算法运行时，人工蚂蚁根据构建图边上信息素的分布来构建解，同时也 在每次的迭代过程中更新各条边上的信息素，目的是使搜索空间能够随迭代次数 的增加能逐渐地收缩到那些“优质”的边上然而，这个收缩过程到了一定阶段 就会演化称为停滞期，算法求解得质量不再随着迭代次数得增加而有所改进，算 法可能会反复生成某个局部最优解。较理想的方法就是拖延算法进入停滞期的时 间，这就要对a c s 中的各个参数的关系进行研究。 因为蚁群算法有以上不是，所以许多学者都将目光放在了改进蚁群算法上 面。在本文中，我们试图通过对a c s 算法中参数关系进行研究，提出一种有效 的a c s 参数设置规则。 2 5 本章小结 本章主要介绍了t s p 问题的概念以及使用经典a c s 算法优化t s p 问题的具 体操作而后，本章简要介绍了收敛与停滞的相关理论，并结合经典蚁群算法进行 分析，总结出蚁群算法机械设置参数，忽略参数之间联系的不足。我们研究a o s 算法参数关系的目标就是要制定一种有效的参数设置规则，弥补经典蚁群算法的 以上缺陷。 一种应用于t s p 问题的蚁群优化算法 第3 章a c s 算法控制参数研究 如前所述，a c s 是一种比较成功的a c o 算法，它与其他的a c o 算法之间 有许多的不同之处，特别是它同时使用了两种不同的路径构建方法。在本文中， 我们主要是对a c s 优化t s p 问题时的参数预设规则进行研究 图3 - l 使用了参数预设规则的a c s 算法流程图 中山大学硕士学位论文 在这一章当中，我们会对a c s 算法进行研究，分析其控制参数对优化过程 的作用和各个参数之间存在的关联，据此选取需要进一步研究的控制参数，为制 定参数设置规则做准备： 1 以t s p 为例，分析各个控制参数取值的可行域。求出各个控制参数的可 行域，并且分析控制参数对优化效果的影响。 2 研究控制参数对于信息素变化的影响。信息素的分布是影响算法优化性 能的关键，如果局部最优解的边上的信息素过高，就会导致算法难以“探索”更好 的解，从而导致局部最优；然而，如果局部最优解的边上的信息素过低，算法就 难以“利用”已有的优化信息。 3 分析控制参数之间的联系，制定有效的参数设置规则。本文中的蚁群算 法参数设置规则是以a c s 算法为原型而设计得。并且适用于t s p 问题的优化。我 们希望通过使用这个规则，在保证a c s 算法的优化性能的前提下，降低算法参 数设置的复杂度。 3 1a c s 算法参数对优化的影响 与其他的基于自然的元启发式算法一样，a c o 的优化性能很大程度上取决 于对其控制参数的取值，在以往使用蚁群算法的时候，参数的取值都是在优化过 程开始之前机械设定的，没有规则可言，并且在设定时很少考虑参数之间的联系， 过程独立，复杂度比较大，同时容易使算法陷入局部最优。为了制定合理的参数 预设规则，就要研究参数对优化性能的影响，在这一小节中，我们就a c s 算法 中各参数对优化性能的影响进行研究。 蚁群算法自诞生以来就受到了众多学者的关注，而对参数取值的预设研究 也由来已久。m a r c od o r i g o 等研究了部分a c o 算法在优化组合优化问题时的合 理取值，特别证明了对于a c s 算法来说，蚂蚁数目的最佳取值应当为1 0 。z e c c h i n 等则研究了应用于水利分布系统中的蚁群算法的预设值，并细致地比较了不同取 值情况下的算法优化性能的优劣。 我们只对a c s 优化t s p 问题的初始取值进行研究，希望能得出一套控制参 一种应用于t s p 问题的蚁群优化算法 数的预设规则，进而提高算法在优化阶段( 特别是优化初期) 的性能。与m a r c o d o r i g o 和z e c ：c h i n 的研究不同，在a c s 的研究中，要在蚂蚁构建回路的过程中 考虑两种构建方法，即最大概率选择法和轮盘赌选择法；此外，在假设参数与参 数之间存在联系的基础上，本文也尝试了对某些参数取值的关联性进行研究 3 9 1 。 本文对以下的几种参数的初始取值进行了研究： 1 ) 决策控制参数，a 和历 2 ) 信息素挥发系数，口( 全局与局部更新都相同) ； 3 ) 构建法的比例系数，卯。 此外，在a c s 的所有算法中，根据d o r i g o 提出的最佳蚂蚁数，我们在每次 迭代时都只设置1 0 只蚂蚁来构建回路。 3 1 1 参数口和卢的设置研究 在a c s 算法以及其他的a c o 算法中，随机比例规则比a c s 算法中的其他 规则具有更高的优先级，使用在随机比例规则中的a 和声是最重要的参数之二， 它们各自决定了在构建路径过程中“信息素”这一启发式信息以及构建图中两点 之间距离的权重。如果这两个参数的取值不合理，启发式信息就不能有效地指导 路径构建过程，使得算法求解的质量下降。 表格3 - 1 在o l i v e r _ 3 0 ( 3 0 个城市的t s p 问题实例) 中a 和口的可行取值 ：优良，：较差，o ：很差，在每组参数组合下算法运行l o 次的得到的结果。 2 5 中山大学硕士学位论文 因此，我们首先要对a 和口的初始值进行研究。第一步就是分析这两个参 数取值的可行域。 在随机比例规则中，a 和口都是同时使用的，它们反映了信息素与期望度 ( 两点之问距离的反比) 在启发式信息中的权重，而蚂蚁也正是更具这些启发式 信息来构建路径的。在表1 中，我们显示了伍和口不同取值条件下的a c s 算法 的优化性能。根据对t s p 实例o l i v e r _ 3 0 的优化计算( 每组a 和芦组合下算法运 行1 0 次，每次1 0 0 0 代) ，可以把a 和芦组合的结果分为三类： 1 ) 优良：设置好a 和声的取值后，对p 和和进行取值，大部分情况中都 能够得到己知的最优解( 4 2 4 8 7 ) ，算法不容易陷入停滞。在表i 中用记号来表 示。 2 ) 较差：对a 和卢的值进行设定后，只有少部分p 和卯的组合能在1 0 0 0 次迭代中得到已知最优解。在表l 中用记号西来表示这中结果。 3 ) 很差：在此类口和算的取值中，算法几乎不能在任何情况下求出已知 最优解。并且陷入停滞的可能性非常高。 本文对其他的t s p 实例也做了相同的实验，表格3 2 和3 3 显示了实验结果。 表格3 - 2 在e l i 5 1 ( 5 1 个城市的t s p 问题实例) 中a 和的可行取值 ：优良，：较差，o ：很差，在每组参数组合下算法运行l o 次韵得到的结果。 一种应用于t s p 问题的蚁群优化算法 表格3 3 在k o r a l 0 0 ( 1 0 0 个城市的t s p 问题实例) 中口和户的可行取值 ；优良，：较差，o ：很差，每组参数组合下算法运行l o 次的得到的结果。 以上结果表明，d 和声的取值对a c s 的性能有非常大的影响。如果a 和卢 的取值合理，那么算法就比较容易得到已知最优解( 在算法的求解过程中是全局 最优解) ；反之，如果a 和口的取值不恰当，那么不管其他参数如何设置，算法 都难以得到已知最优解，甚至根本不能求出最优解。这也恰恰说明了b 和口取 值与其他的参数相比具有优先性，应当首先考虑。其中，对d 的合理取值范围是 【0 5 ，1 5 】；对的合理取值范围则是【0 ，5 】，根据具体实例的不同稍有差异。 3 1 2 参数p 的设置研究 在a c s 中，信息素是一个非常重要的启发式信息，人工蚂蚁就是根据信息 素与期望度在构建路径的过程中来选择边的，此外，人工蚂蚁还根据全局更新规 则和局部更新规则来修改特定边上的信息素，以便引导下次迭代的路径构建。理 想的情况是，通过对信息素的修改，算法中蚂蚁的搜索随着迭代次数的增加而逐 渐收敛到那些“优秀”的边上，构建出全局最优解。要做到这一点，就必须对全 局更新以及局部更新规则中的信息素挥发系数p ( 本文使用的算法中，两个更新 规则使用了相同的挥发系数) 进行合理的设置。 中山大学硕士学位论文 表3 - 4 算法取不同的p 值时的优化性能( o l i v e r _ 3 0 ) 由于信息素的挥发速率会直接影响算法收敛的速度，所以对挥发系数的选 择是非常重要的。然而，对系数p 的取值的设置是一个复杂过程，这是因为： 1 全局信息索更新规则使得在算法每次运行结束后，属于迭代最优解中的 所有边上的信息素有所增加。 这些边在以后的优化过程中应当会被优先考虑；而局部信息素更新则不同， 在蚂蚁每次选择一条边来构建回路后，局部更新规则会减少此边上的信息素，使 得蚂蚁在以后的回路构建中能更多地去考虑其他未被选择的边，从而发现较优的 解。而一旦对p 的取值不当，使用局部更新与全局更新规则不起到应有的作用， 甚至起到反效果。 2 对p 进行取值时，还应当考虑其他的参数设置。例如表3 _ 4 所示，当和 取不同值时，相同的p 也会取得不同的结果。表3 - 4 的结果是在口= j d ，伊i d 的条件下，算法每次迭代1 0 0 0 代得到的结果，其中县h 表示的是算法在1 0 次 运行过程中得到已知最优解4 2 4 8 7 的次数。 对p 的取值对蚁群算法的优化性能来说是非常重要的，实验表明对p 的取 值不应该过高，因为在全局信息素更新规则中，过高的p 值会使得迭代最优解的 边上的信息素快速增加，使得算法容易陷入局部最优；而使用局部更新规则时， 过高的p 值会使得已访问的边上的信息素过快地挥发减少，可能会造成某些“优 秀”边上的信息素小于其他“普通”边的信息素的情况。所以对p 的取值原则上 不应该过大，具体优化时，对p 进行取值也应该考虑实例规模，其他参数设置等 等情况。而根据表3 - 4 ，可以看出p 的可行域为【o 0 5 ，0 2 0 。 一种应用于t s p 问题的蚁群优化算法 3 1 3q o 的设置研究 a c s 与其他蚁群算法的一个重要的不同之处在于，在a c s 中，人工蚂蚁在 构建图上构建路径时可以使用两种方法来选择边：最大概率选择法和轮盘赌选择 法。系数和和( j 9 0 则分别表示了使用最大概率法选择边和使用轮盘赌选择边 的概率。和又被称为构建比例系数。表4 5 显示了取不同值时算法的优化性能变 化。 表3 - 5 算法取不同的和值时的优化性能 其中a = 1 0 ，牌0 并且旷田1 0 。m _ g 表示的是算法取得最优解的最小迭代次数。 表中的结果是1 0 次运行后的平均值。 o l i v e r3 0 a t t 4 8 卯= oq o = 0 6q o = 1 09 0 = oq o = 0 6q o = 1 0 b e s tt o u r 4 2 4 8 7 4 2 4 8 74 2 8 3 23 3 6 0 0 5 63 3 5 3 8 3 43 3 6 9 5 5 0 l e n g t h m - g 3 2 25 72 9 53 5 01 0 51 7 0 从表3 5 显示的结构来看，使用单一的路径选择方法时的算法性能( 即q o = 0 和q o = 1 0 时) 较差。同时使用两种路径选择时的求解精度( 最优路径长度) 以 及求解速度( mg ) 都要远远优于只使用一种路径选择法的算法。 对a c s 来说，同时使用最大概率选择法和轮盘赌选择法时算法的优化性能 比只使用一种路径选择方法的算法更为优秀。这是因为如果只使用最大概率选择 法，当某些局部最优解的边上的信息素较高时，算法在以后的路径构建过程中很 容易反复地生成这些解，从而陷入局部最优。而在加入轮盘赌选择之后，可以在 一定程度上降低陷入局部最优的可能性。反之，如果只使用轮盘赌选择法的化， 那么算法收敛到那些“优秀”边上的速度会大大降低，有时甚至不会收敛，这样 一来，随着迭代次数的增加，信息素的分布变化不能够指导蚂蚁找出更好的可行 解。图3 1 显示了在不同的g o 取值时，算法迭代过程中的求得的最优解的变化情 况。 中山大学硕士学位论文 图3 - 1a c s 算法迭代过程中的迭代最优解变化情况 -，o工。嚣do霉芒3- -，昌葛u蕾400童一 0上篙。蕾fo9菡 一种应用于t s p 问题的蚊群优化算法 图3 - 1 描述了a c s 算法优化o l i v e r3 0 时，迭代过程中的迭代最优解变化情 况其中a = 1 o 卢_ 2 0 并且旷田1 0 图3 1 ( a ) 显示的是只使用轮盘赌选择路径 法时算法优化结果，最优解的质量不会随迭代次数增加而提高，图3 一l ( c ) 中， 算法只使用了最大概率选择法，这时算法很快速地收敛到某条最优解上，很容易 陷入局部最优，求出己知最优解的速度较慢，或者根本不能求出已知最优解。图 3 1 ( b ) 中，算法同时使用了两种路径选择方法。使在“探索”和“利用”( e x p l o r a t i o n & e x p l o i t a t i o n ) 之间建立一个平衡点，求解的质量随着迭代次数的增加而有所提 高，并且降低了陷入局部最优的可能性，求出已知最优解的速度也较快。 在a c s 算法优化t s p 问题的时，信息素的分布对路径构建具有很高指导意 义，所以在大多数情况下使用最大概率选择方法，因此应当对g o 取较高的值， 但是轮盘赌的方法也应当适当使用，以降低算法陷入局部最优的可能。 3 2a c s 算法参数关系研究 本文除了分析控制参数对优化过程的影响以外，还两对参数之间的关系进行 了研究，希望通过对它们的学习，制定出合理有效的a c s 算法控制参数预设规 则。 3 2 1 参数口和卢的设置关系 在第二章中我们已经说过，位于城市i 的蚂蚁岛根据伪随机比例规则( 2 1 ) 选择城市，作为下一个访问的城市。 ，：j a r g m a x i e 吖 毛【嘞n ，i 幻q o ； ( 2 - 1 ) l 上o t h e r w i s e ； 其中口是均匀分布在区间【0 ，l 】中的一个随机变量，q o ( o s q o 1 ) 是一个参数，是 根据式子( 1 一1 ) 给出的概率分布产生的一个随机变量选择，在a c s 中，使用轮 盘赌的方法来完成这个随机选择。蚂蚁选择当前可能的最优方式移动的概率是 窖o ，这种最优的移动方式是根据信息素的积累量和启发式信息值求出的( 在这种 中山大学硕士学位论文 情况下，蚂蚁继续开发已知的知识) 同时，蚂蚁以( 1 一吼) 的概率有偏向性的探 索各条边。 荔= 磊，i 髟e 卵， ( 1 1 ) 其中白是连接结点i ，j 的边上的信息素的值，而巩则是此边距离的倒数。 如前所述，在a c s 算法以及其他的a c o 算法中，随机比例规则比a c s 算 法中的其他规则具有更高的优先级，使用在随机比例规则中的a 和口是最重要 的参数之二，它们各自决定了在构建路径过程中“信息素”这一启发式信息以及 构建图中两点之间距离的权重。如果这两个参数的取值不合理，启发式信息就不 能有效地指导路径构建过程，使得算法求解的质量下降。 在随机比例规则中，a 和口都是同时使用的，它们反映了信息素与期望度( 两 点之间距离的反比) 在启发式信息中的权重，而蚂蚁也正是更具这些启发式信息 来构建路径的。基于本文3 1 节中对参数c t 和声取值可行域的研究，我们发现口 的取值范围相对较小，而且在优化过程中起主要作用的其实是信息索与期望度在 启发式信息中的权重之比，也就口和芦的比例。所以在设置a 和声的取值时， 不用同时考虑两个参数，可以先固定一个参数的取值，然后调整另一个参数的取 值。本文的做法是固定的值，而根据t s p 问题的具体情况对声的值进行调整。 3 2 2 参数卢和q 口的设置关系 a c s 是一种非常成功的蚁群优化算法，a c s 与其他蚁群算法的一个重要的 不同之处在于，在a c s 中，人工蚂蚁在构建图上构建路径时可以使用两种方法 来选择边：最大概率选择法和轮盘赌选择法。系数和和( ，一q o ) 贝u 分别表示了使 用最大概率法选择边和使用轮盘赌选择边的概率。卯又被称为构建比例系数，合 理的和值可以使a c s 在使在“探索”和“利用”( e x p l o r a t i o n & e x p l o i t a t i o n ) 之 间建立一个平衡点，让算法有能力求出更优秀的解，从而降低陷入局部最优的可 能。 一种应用于t s p 问题的蚁群优化算法 图3 - 2a c s 在优化o l i v e r _ _ 3 0 时取不同的芦与和值时的效果 然而，两种路径构建方法都要考虑使用随机比例规则，而随机比例规则的两 个最重要的控制参数就是和，我们因此推测q d 的取值应当与a 和声存在某 种联系，这就意味着在设置和值的时候也要考虑仅和卢的取值。这个推测在对 o l i v e r3 0 的仿真实验中得到了证实，实验结果如图3 - 2 所示。 图3 - 3 ( a ) 显示的是在取不同卢与q 口值对o l i v e r3 0 问题优化1 0 0 次( 每次迭 代最大次数为1 0 0 0 次) 时得到全局最优解的情况。横坐标为口的值，纵坐标为 和的值，白色区域表示一百次运行中有1 0 0 次得到了全局最优解，而颜色越深的 区域命中全局最优解的次数越少。而图3 - 3 ( b ) 显示的是在取不同声与卯值对 o l i v e r3 0 问题优化1 0 0 次( 每次迭代最大次数为1 0 0 0 次) 时命中全局最优解的 中山大学硕士学位论文 迭代次数，如果本次运行没有命中则记为1 0 0 0 次。白色区域的迭代次数最少， 不到2 0 0 代就得到了全局最优解，而颜色越深的区域所需的迭代次数越多，而且 可能不能命中全局最优。 可以看出在图3 - 3 ( a ) ，( b ) 中的白区域的多与珈值都是比较合理的。从 3 1 3 节的内容我们知道使用两种路径构建的a c s 算法比仅使用一种方法的a c s 更有效，即勋的值不能是0 或1 。而当变化时，和的值也应当适当调整，一般 来说，和的合理取值范围是 o 7 ，o 9 】，而的合理取值范