（计算机软件与理论专业论文）求解旅行商问题的微粒群算法研究.pdf

中文摘要 旅行商( t s p ) j 口7 题，是一个古老而又典型的n p h a r d 组合优化问题。该问题的 有效求解，不仅有着重要的理论和学术价值，同时对于许多实际工程应用问题有 着重要的指导意义。因此，寻求高效的t s p 优化算法一直是优化领域的一个热点 课题。微粒群算法是一种新型的群智能计算方法，算法模型简单、操作便捷，具 有自组织、自适应、自学习等智能特性，已被证明是一种求解大规模复杂问题的 有效工具，因此也是求解t s p 问题的一种智能计算方法。然而，面对复杂的离散 组合优化问题，现有的微粒群算法模型存在着效率低下，求解精度不高，易于早 熟等缺陷。 为此，本论文基于t s p 优化问题，着重围绕离散微粒群算法的模型设计和性 能改进，进行以下内容的研究： 一、基于微粒群算法的优化机理，分析了离散微粒群算法设计的主要方法和 基本原则，进而研究了离散微粒群算法的关键技术，包括离散问题的编码、个体 微粒的评价及其主要进化操作，为后续的研究提供技术基础。 二、为提高离散微粒群算法的全局收敛性，提出了一种引入局部扰动策略的 改进微粒群算法。首先基于整数编码，并结合遗传算法中的p m x 算子，对离散 微粒群算法中的速度、位置及其进化操作进行了重新定义，其次引入微粒的活力 信息来实现控制参数的自适应调节，构造局部扰动策略以避免群体局部收敛。改 进算法被用于典型t s p 坝i j 试问题，其仿真结果表明该算法的有效性。 三、为提高离散微粒群算法对复杂问题的求解能力，提出一种基于边编码， 采用表示边的两城市点之间所有点依次倒置插入的微粒更新操作的改进离散微 粒群算法。并在对算法方程进行重新定义的基础之上，加入微粒适应值变优则更 新，变差按一定概率更新的策略。通过在典型中型t s p 问题上进行的实验，求 解时间、求解精度上均令人满意。然后在这个改进算法的基础之上加入多级规约 策略，为微粒群算法求解大规模问题提供了一种思路。 关键词：智能计算；群智能计算；微粒群算法；t s p 问题；组合优化 a b s t r a c t t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i sa no l da n dt y p i c a ln p h a r d 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 ，i t sv a l i da n de f f e c t i v es o l u t i o n sn o t o n l y h a s i m p o r t a n t t h e o r e t i c a la n da c a d e m i cv a l u e s ，b u ta l s oh a s i m p o r t a n tg u i d i n gs i g n i f i c a n c e f o r m a n yp r a c t i c a le n g i n e e r i n g a p p l i c a t i o n s s ot s pi s ah o tt o p i ci no p t i m i z a t i o nf i e l d p a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) i sa n e wm e t h o db a s e do ns w a r mi n t e l l i g e n c e ，w h i c h a r ec h a r a c t e r i z e dm a i n l y b ys i m p l em o d e l ，c o n v e n i e n to p e r a t i o n ， s e l f - o r g a n i z i n g ，s e l f - a d a p t i v e ， s e l f - l e a r n i n g ， e t c p a r t i c l es w a r m o p t i m i z a t i o nh a sb e e np r o v e dt o b ea ne f f e c t i v et e c h n i q u et os o l v e l a r g e s c a l ec o m p l e xp r o b l e m s t h e r e f o r e ，i ti sa l s oa ne f f i c i e n tm e t h o d t o s o l v et s p h o w e v e r , t h e e x i s t i n g p s oa l s os u f f e r sf r o ms o m e s h o r t c o m i n g s ，s u c h a sl o w e f f i c i e n c y , l o wa c c u r a c y , p r e m a t u r e c o n v e r r e n c e 。e t c 。e s p e c i a l l yt o rt h el a r g es c a l ea n dc o m p l e xa l s c r e t e 一 ， ， 一 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 ed i s s e r t a t i o nf o c u s e so nt h em o d e ld e s i g n i n ga n dp e r f o r m a n c e i m p r o v i n go fd i s c r e t ep a r t i c l es w a r ma l g o r i t h m ( d p s o ) b a s e d o nt s p , i t s m a i nr e s e a r c h e sa r el i s t e da st h ef o l l o w i n g ： 1 b a s e do nt h eo p t i m i z a t i o nm e c h a n i s m so fs w a r mi n t e l l i g e n c e ，t h e d i s s e r t a t i o nm a k e sa l la n a l y s i so ft h ep r i m a r yd e s i g nm e t h o d sa n dt h e b a s i cp r i n c i p l e sf o rd i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o nf i r s t l y a f t e rt h a t ， t h ek e yt e c h n i q u e so fd p s oa l s oa r ea n a l y z e di nd e t a i l s ，i n c l u d i n gt h e c o d em e t h o d sf o rd i s c r e t e o p t i m i z a t i o np r o b l e m s ，t h ee v o l u t i o n a r y o p e r a t i o n si nd i s c r e t es o l u t i o ns p a c e ，e t c ，w h i c hp r o v i d ea v a l i dt e c h n i c a l f o u n d a t i o nf o rt h ef o l l o w i n gs t u d y 2 t oi m p r o v et h eg l o b a lc o n v e r g e n c eo fd p s o ，t h ed i s s e r t a t i o n d e v e l o p sa na d a p t i v ed p s ot os o l v et s p f i r s t l y ，t h ei m p r o v e dd p s o a d o p t s t h ei n t e g e rc o d em e t h o da n dr e d e s i g n st h ep a r t i c l e s v e l o c i t y , l o c a t i o n a n dt h e i rd i s c r e t ee v o l u t i o no p e r a t i o n sb a s e do nt h ep m x i i i o p e r a t o ro fg e n e t i ca l g o r i t h m s e c o n d l y ，t h ei m p r o v e dd p s oi n t r o d u c e sa l o c a l a d j u s t m e n ts t r a t e g y f o rt h e p a r a m e t e r s t oa v o i dt h el o c a l c o n v e r g e n c e o ft h e s w a r m ，w h i c hi sc o n t r o l l e db yt h e d y n a m i c i n f o r m a t i o no f p a r t i c l e s t h es i m u l a t i o nr e s u l t sb a s e do nt h et y p i c a lt s p p r o b l e m ss h o wt h a tt h ep r o p o s e da l g o r i t h mv a l i d l yi m p r o v e st h eg l o b a l p e r f o r m a n c eo fp s oi nd i s c r e t eo p t i m i z a t i o np r o b l e m s 3 t o d e v e l o pt h ep e r f o r m a n c eo fd p s of o rc o m p l e xd i s c r e t e o p t i m i z a t i o np r o b l e m s ，t h ed i s s e r t a t i o np r o p o s e da n o t h e ri m p r o v e dd p s o ， w h i c ht a k e sa d v a n t a g eo fs i d e - c o d et e c h n i q u ea n dam u l t i l e v e lr e d u c t i o n s t r a t e g y t h ei m p r o v e dd p s or e d e s i g n st h ep a r t i c l e s v e l o c i t y , l o c a t i o n ， a n dt h e i rd i s c r e t ee v o l u t i o no p e r a t i o n sb a s e do nt h es i d e - c o d et e c h n i q u e a f t e rt h a t ，am u l t i l e v e lr e d u c t i o ns t r a t e g yi si n t r o d u c e dt oi m p r o v et h e g l o b a lc o n v e r g e n c eo ft h ea l g o r i t h m f i n a l l y , t h ei m p r o v e da l g o r i t h mi s a p p l i e dt os o l v em e d i u mo rl a r g es c a l et s pp r o b l e m s ，t h es i m u l a t i o n r e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi sav a l i dt e c h n i q u ef o rc o m p l e x t s pp r o b l e m s k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；t r a v e l i n gs a l e s m a np r o b l e m ； c o m p u t a t i o n a li n t e l l i g e n c e ；c o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m i v 士= z ：l明明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：日期： 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：薹整一 日期：一銎兰星篁! # 新繇j 塍l 隰一趟型仁- 第一章绪论 第一章绪论 1 1 课题研究背景与意义 1 1 1 旅行商问题( t s p ) 问题概述 旅行商问题【1 1 1 2 ( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 自19 3 2 匀z ，k m e n g e r 提出 以来，己引起各领域许多研究者的兴趣。它是组合数学中一个古老而又困难的问题， 也是组合优化中研究最多的问题之一，但至今尚未彻底解决。其描述为：一推销员 要到若干城市推销货物，从某一城市出发，经过其余各城市一次且仅一次，然后回 到出发点，求其最短行程。很显然，这是一条哈密尔顿回路。从问题对应到图的类 型，t s p 的研究经过几十年的发展，还引申出其他扩展形式，如多旅行商问题( m u l t i s a l e r m a np r o b l e m ) 和多目标旅行商问题( m u l t io b j e c t i v et s p ) 。本文主要针对的是单 目标旅行商问题。 根据旅行商问题的定义，它的数学描述为： m i n d v x 口 ( 1 1 ) s ，嘞= 1i = 1 ，2 ，3 刀 ( 1 2 ) j = l 勤= 1j = 1 , 2 ，3 ” ( 1 3 ) t = l x i s l - 12 i s l n - 2 ，sc 1 ，2 ，胛) ( 1 4 ) i ，j l 时， 可将t s p 的动态方程写成c ( s ，| i ) = ，墨职) c ( s 一 j ，七) ，) + d 琥】，按动态规划可迭代求 解，由于动态规划算法所需要的时间资源即复杂度为o ( n 2 2 ”) ，所需要的空问资源 复杂度为o ( n 2 ”) ，因此当增加到一定的数量后，复杂程度急剧上升，故一般除了很 小规模的问题外，几乎不予以采用。 i n 第二章相关的研究基础 分支定界法 分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制搜 索进程使之能向着空间状态树上有最优解的分支推进，一边尽快找出一个最优解， 该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支定界法。 但在解决大规模问题时不是很有效。 2 2 2 求解t s p 问题启发式算法 插入算法 插入算法提出了一个不同的构造巡回的启发式算法。它首先开始于连接两个结 点的巡回，然后把剩余的结点逐个地加入到巡回中，在加入结点的过程中要使得巡 回费用的增加最小。从哪两个结点开始，更重要的是在每一个步骤选择哪个结点插 入，都会影响最后的结果。 最邻近算法 最邻近算法的基本思想是：从任意一个结点开始，访问当前未访问过的结点中 最近的结点，当所有的结点都访问过时回到最初的开始结点。具体实施中，可以把 出发点取遍仲各点而得到多个解，从中选择最好的一个，但此时的时间复杂度增加 了3 倍，同时较容易陷入局部最优。 一o p t 算法 - o p t 算法是一种局部改进搜索算法，有l i n 等人( 1 9 6 5 ) 提出，其思想是对给定的 初始回路，通过每次的交换r 条边来改进当前的解，对不同的厂，根据大量计算发现， 3 - o p t l 卜, 2 一o p t 求解的质量要好，而4 一o p t ，5 - o p t 并不比3 一o p t 好，况且，| 越大，运算的时 间越大，所以经常使用的是采用3 一印触。 总之，传统的算法对于寻找小规模的t s p 的局部最优解非常的有效，通常可以在 很短的时间内计算出这些t s p 问题的高质量的解，但是，这些算法过于依赖问题本身 的特征，容易陷入局部的最优。 2 3 解决旅行商问题的智能计算方法 在现阶段，解决t s p 问题的智能计算方法主要人工神经网络、模拟退火算法、禁 忌搜索算法、以及以遗传算法为代表的进化算法，和以蚁群算法、微粒群算法为代 表的群智能算法。 由于在本文中微粒的更新较多的借鉴遗传算法中的遗传算子，并且蚁群算法和 微粒群算法同属于群智能算法，我们在本节着重介绍这两种算法。 1 1 求解旅行商问题的微粒群算法研究 2 3 1 解决t s p 问题的智能计算方法 人工神经网络 人工神经网络畔】的基本思想是通过对神经网络引入适当的能量函数，使之与t s p 的目标函数相一致来确定神经元之间的联结权，随着网络状态的变化，其能量不断 减少，最后达到平衡时，即收敛到一个局部最优解。但是，当城市的数少于3 0 时， 在大多数情况下可以求的最优解的近似解，但是当城市大于3 0 时，求解结果并不能 令人满意。当规模更大时，易于收敛到非法解或局部极小解。同时，它还具有收敛 速度慢、对模型参数和初始条件敏感等缺点。 模拟退火算法 模拟退火算法的基本思想是从一定解开始的，从邻域中随机产生另一个解，接 受准则允许目标函数在有限范围内变坏。它由一控制参数t 决定，其作用类似于物理 过程中的温度丁，对于f 的每一取值，算法持续进行“产生新解一判断一接受或舍弃 的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换 后，可以求得给定控制参数r 值时优化问题的相对最优解。然后减小控制参数t 的值， 重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统亦越来越趋于平衡 状态，最后系统状态对应于优化问题的整体最优解。模拟退火算法所得解的好坏与 初始状态、温度函数等都有一定的联系，降温较快的效果不一定很好；效果好的， 其降温过程又极其缓慢。但由于该方法适用范围广，并可以人为控制迭代次数，反 复求解，因此具有很强的实用性。 禁忌搜索算法 禁忌搜索的思想最早由g l o v e r 等于1 9 8 6 年首次提出，是一种亚启发式搜索技术 它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法。禁忌搜索算法通过引入 一个灵活的存储结构和相应的禁忌表来避免重复搜索，并通过藐视准则赦免一些被 禁忌的优良状态。禁忌搜索算法最重要的思想是标记对应己搜索到的局部最优解的 一些对象，并在进一步的迭代搜索中尽量避开这些对象，从而保证对不同的有效搜索 途径的探索，最终实现全局优化。禁忌搜索算法对初始解的依赖性较强，好的初始解 有助于搜索很快达到最优解，迭代搜索过程是串行的，仅是单一的移动，而非并行 搜索。在禁忌搜索算法中多样性搜索尤其重要，但是在解决较大的规模时候，传统 的以频率记忆和改变参数赖实现多样性搜索的策略往往得不到理想的解。 1 2 第二章相关的研究基础 2 3 2 遗传算法与蚁群算法 遗传算法i 删 遗传算法( g a ) 生物学的自然选择和自然遗传机制模拟生命进化的原理赖寻求 问题的最优解，为一种进化算法，n h o l l a n d j 等提出以来，获得了广泛的应用，用该 算法求解t s p 问题的基本思想是：把问题的解表示成“染色体 ，在求解t s p 问题时 通常用一条周游路径来表示“染色体 ，在执行算法之前，随机地给出一群初始“染 色体”，即假设解。然后把这些假设解置于问题的“环境”中，并按适者生存，劣 者淘汰的原则，从中选择出较适应环境的“染色体”，进行复制，再通过交叉，变 异过程产生更适应环境的新一代“染色体 群。这样，经过一代一代的进化，最终 收敛到最适应环境的一个“染色体”上，它是问题的最优解。 遗传算法求解t s p 问题可包括：编码、种群初始化、适应度的评价、遗传操作( 选 择、交叉、变异) 、终止条件判断、解码等步骤。 遗传算法的优点是将问题的参数编码成染色体后进行优化，而不是针对参数本 身，从而不受函数约束条件的限制。搜索过程从问题解的一个集合开始，而不是简 单的个体，具有隐含并行搜索特性，可大大减少陷入局部最优的可能。主要的缺点 是对于结构复杂的组合优化问题，搜索的空间大，搜索时间比较的长，往往会出现 早熟收敛的情况，对初始种群很敏感，初始种群的选择常常直接影响到解的质量和 算法的效率。 g o l d b e r g 等首次应用遗传算法求解t s p 问题，提出三种交叉方法：部分匹配交叉 ( p m x ) ，顺序交叉( o x ) 和环交叉( c x ) 。这三种交叉方法已广泛应用于自然 编码遗传算法中，实际应用中发现这几种交叉方法存在收敛速度慢而且效果不理想， 为此后来的学者提出各种各样的针对上面三种交叉算子存在的问题的改进交叉算 子。其中，郭涛4 7 1 于1 9 9 9 年提出的一种i n v e r o v e r 算子，该算子具有交叉、变异的特 性，在解决2 0 0 个城市点以内的t s p i h - 题时，无论在精度还是计算的速度上都成为目 前最为有效的求解该问题的方法。 算子描述如下： ( 1 ) 变异算子：在父体s 中随机地选取两个城市c 、c ，对c 的下一个城市与c 间的所有城市( 包括c ) 进行到位操作。例如，在父体s ( 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) 中随 机地选取c = 2 ，c ，- 6 ，则进行变异操作后得到的个体为s ( 1 ，2 ，6 ，5 ，4 ，3 ，7 ，8 ) 。 ( 2 ) 杂交算子：在父体s 中随机选取一个城市c ，另取一父体s ，在s 中指定c 求解旅行商问题的微粒群算法研究 的下一个城市为c7 ，对s 中c 的下一个城市与c7 间的城市实旋到位操作，若s 中c 是与城市c 相邻的城市，则不进行到位操作。例如，选取一父体s ( 1 ，2 ，3 ，4 ，5 ，6 ，7 ， 8 ，) ，令c = 2 ，随机地选取另一个父体s ( 1 ，3 ，5 ，6 ，8 ，4 ，2 ，7 ，) ，则c = 7 ，在s 中 对2 至7 间的基因实施到位操作得到的子代为( 1 ，2 ，7 ，6 ，5 ，4 ，3 ，8 ) 。 i n v e r o v e r 算子对染色体进行到位操作。这个算子实际上是连续的运用倒置不断 地打断原来个体中的旧边，生成新边。大多数新边都来自于群体中的其他个体，也 就是从群体中获得信息，还有一部分是随机产生边。期望提供到全局最优解的可能 性。该操作可以有效地增加群体的多样性，扩大搜索域，防止过早地产生局部收敛， 并迅速地找到满足条件的最优解。其几何意义是：禁止边与边之间有交叉的现象出 现。对基因片段不停地逆转操作使它能够有效地增加群体的多样性，扩大搜索域， 所以算法的早期收敛快。但是，到了算法的后期，几乎所有的染色体所表示的解的 路径都是没有交叉的合法的环形路径了，再进行这种盲目的基因片段的逆转操作是 没有意义的。所以，算法在后期的收敛速度很慢，容易陷入局部最优值。 蚁群算法【6 】 蚁群算法( a c 0 ) 化算法，由意大利学者d o f i g o 等人首先提出，他们称之为蚁群系 统，并用该方法求解t s p 问题，取得了较好的实验效果受其影响，蚁群系统模型逐渐 引起其他学者的注意，并将蚁群算法用于指派问题、频率分配问题、电力系统故障诊 断等n p h a r d 题。下面说明蚁群算法解决t s p 问题的过程。 以平面上的n 个城市点的t s p 问题为例，设m 是蚁群中蚂蚁的数量，d 。( f ，_ 1 ，2 ， 3 ，n ) 表示城市f 和城市，之间的距离，f 。，( ，) 表示f 时刻在城市i 和城市，连线上的 信息素的浓度。初始时刻，各条路径上的信息素的浓度相同，设f 。，( o ) = c ，c 是常 数，蚂蚁k ( k = 1 ，2 ，聊) 在运动的过程中，根据各条路径上的信息素的浓度 决定转移的方向，露( t ) 表示在t 时刻蚂蚁k 从城市砖专移到城市j 的概率，其计算公 式为： f 嘭= 【 r ；( f ) 7 7 夕( f ) r ；( f ) 7 7 乡( f ) t e a l l o w , 0 ，其他 ，j 萑t a b u ( 2 4 ) 在上面的公式中：t a b u 女( k = - i ，2 ，m ) 表示蚂蚁k 已经走过的城市的集合， 开始i 对t a b u 。中只有一个元素，即蚂蚁尼的出发城市，随着进化的进行，t a b u 。集合放 1 4 第二章相关的研究基础 入元素不段的增加；a l l o w e d k ，k = - o ，1 ，0 ，- 1 ) ，t a b u t 表示蚂蚁k 下一步允许选择的城 市；7 7 。是能见度，去路径( f ，歹) 长度的倒数，a ，卢调节信息素浓度r 于能见度7 7 的相对重要的程度。 随着时间的推移，以前留在各条路径上的信息素逐渐消失，用参数1 一p 表示信 息素的挥发程度。经过w 个时刻，蚂蚁完成一次循环，各路径上的信息素的浓度可 根据一下的公式进行调整： f 盯o + w ) = p f 口o ) + a r ， p ( o ，1 ) a t 口= a t ； ( 2 5 ) ( 2 6 ) 上面的公式中：f ：表示第k 只蚂蚁在一次循环中留在路径( 厶，) 上的信息素 的信息素的浓度；a t ，表示本次循环所有蚂蚁在路径( 厶，) 上所释放的信息素的浓 度之和。 在解决t s p 问题时，g u t j a h r 提出一种以图为基础构建的蚁群算法系统框架，在一 定的条件下，每次迭代所得到的解能以近似于1 的概率向最优解收敛。t s a i 等提出一 种求解大规模t s p 问题的基于蚂蚁进化规则的算法等等。 蚁群算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一 种本质并行的算法，个体之间不断进行信息的交流和传递，有利于发现较好的解。 单个个体容易收敛到局部最优，但是多个个体通过合作，很快收敛于解空间的某一 个子集。有利于对解空间的进一步的探索，从而不易陷入局部最优。但是蚁群算法 也具有速度慢、易陷入局部最优等缺点。蚁群算法的运动是随机的，当群体的规模 较大时，要找出一条较好的路径需要较长的搜索时间。 总之，上述独立于问题的各种算法，通过模拟和解释某些自然现象或过程而得 以发展，为解决复杂问题提供了新的思路和方法，这类算法虽然不能保证在有限的 时间内获得最优的解，但是充分多个解验证后，错误的概率可以降到一个可以接收 的程度。 2 4 微粒群算法 k e n n e d y j 【1 2 和e b e r h a r t r c 在1 9 9 5 年的i e e e 国际神经网络学术会议上正式发表 了题为( ( p a r t i c l es w a r mo p t i m i z a t i o n ) ) 的文章，标志着微粒群算法的诞生。 算法基本原理 求解旅行商问题的微粒群算法研究 在微粒群算法中，每个优化问题的潜在解都可以想象成d 维搜索空间上的一个 点( b i r d ) ，我们称之为微粒( p a r t i c l e ) ，所有微粒都有一个被目标函数决定的适应值， 每个微粒还有一个速度来决定他们飞行的方向和距离。然后微粒们就在解空间中搜 索最优位置。具体地说，每个微粒是根据自己的飞行经验和整个微粒群目前的最优 位置来调整飞行的速度，从而使每个微粒飞向最优位置。 基本微粒群算法 4 6 】 在微粒群算法中，首先须初始化一群随机的微粒，然后通过迭代找到最优解。 假设在一个d 维搜索空间中，微粒群算法初始化为m 个随机微粒。在每一次迭代过 程中，微粒通过跟踪两个极值来更新自己：第一个就是微粒本身目前所找到的最优 解，叫做个体极值尸，可以看作是微粒自己的飞行经验；另一个极值是整个微粒群 目前所找到的最优解，叫做全局极值只，可以看作群体经验。 设x ，= ( x n ，x 缈，x 。) 为微粒珀勺当前位置，k = ( v 肿v ，v 。) 为微粒珀勺当前 飞行速度；其中p b ，= ( p b n ，p b f 2 ，p b 。) 为微粒i 所经历的最好位置，也就是微粒i 所经历过的有最好适应值的位置，称为个体最好位置。为整个微粒群中，所有微粒 迄今为止所搜索到的全局最好适应值的位置，称为全局最好位置。从文献1 2 1 中可知， 每一个微粒就是按照下面的公式来更新自己的速度和位置的： = 1 1 i 侈乙+ c 1 r a n d ( ) ( p 耐一x 甜) + c 2 r a n a ( ) ( p 一x 耐) ( 2 7 ) x 肼= x 科+ g d ( 2 8 ) 其中， i = 1 ，2 ，m ，m 是群体中的微粒的数目； d = 1 ，2 ，d ，d 是解空间的维数，即自变量的个数； x d 表示微粒i 位置矢量的d 维分量； 表示微粒工速度矢量d 维的分量； 匕表示第i 个微粒最好位置矢量( 只) 的d 维分量； 表示整个微粒发现的具有最优适应值的位置矢量( 尸g ) 的d 维分量； 形为惯性权重；其大小决定了对微粒当前速度继承的多少，合适选择可以使微 粒具有均衡的搜索和开发能力。即也就是起到权衡全局搜索能力和局部搜索能力， 此值较大时，前一速度影响较大，全局搜索的能力较强；较小时，局部搜索的能力 较弱。 c ，c ，为学习因子，通常是c 。= 岛= 2 o ； r a n d ( ) 是均匀分布在( o ，1 ) 之间的随机数； 1 6 第二章相关的研究基础 c r a n d ( ) 代表微粒从个体极值中获得的信息继承度，c 2 r a n d ( ) 代表微粒从全局极 值获得的信息继承度。 x 耐区砌。，x d 一】，根据实际问题来确定微粒的取值范围； d 少拥“，d j ，速度的最大值根据微粒的取值间长度来确定； 由上两式可知，微粒i 的新的速度的计算主要由三部分决定：微粒i 前一次的速 度，微粒i 当前位置与自己历史最好位置之间的距离( 匕一x 矗) ，微粒j 当前位置与 群体目前最好位置之间的距离( 匕一x 耐) 。通过这两个公式，就可以确定出微粒珀勺 新位置。微粒移动原理可由图2 - 1 表示：其中圪和圪+ ，分别为更新前后的速度。 图2 1 微粒飞行示意图 f i g 2 1s c h e m a t i cd i a g r a mo fp a r t i c l e sf l i g h t 微粒群算法的社会行为分析 如果从社会学的角度来看，公式的第一部分彤d 为微粒的先前速度所起的惯性 作用，若速度计划方程仅保留这部分，此时，微粒将会保持速度不变，成为记忆项； 第二部分c ，r a n d ( ) ( p d x 耐) 为“认知”部分，表示微粒自身的经验，表示微粒自身 的思考。如果微粒群算法的进化方程仅保留认知部分，由于不同的微粒之间缺乏交 流，且没有社会信息共享，则一定规模的群体等价于运行了和规模相同次单个微粒 的微粒群算法，微粒将会很难找到最优解；第三部分c 2 r a n d ( ) ( p g d x 耐) 为“社会” 部分，表示微粒间的社会信息共享。若速度进化方程中仅包含这一部分，则微粒缺 乏个体的认识能力。此时，虽然微粒在相互作用下，有能力到达新的搜索空间，但 是对于复杂问题，容易陷入局部最优点。因此，微粒群算法的速度进化方程有认识 和社会两部分组成。虽然目前的一些研究表明，对于某些问题，模型的社会部分比 认知部分更重要，但是两部分的相对重要性还没有从理论上给出结论。 若速度的进化方程仅保留第二、三部分，由于微粒的速度将取决于其历史最优 1 7 求解旅行商问题的微粒群算法研究 位置和群体的历史最优位置，从而导致速度的无记忆性，即先前速度的影响为0 。假 设在开始时，微粒j 处于群体的历史最优位置，则它将停止进化直到群体发现更优的 位置，而其他微粒将收敛于群体的历史最优位置。因此，若群体在收敛时没有发现 更优的位置，则整个群体的搜索区域将会收缩到当前历史最优位置附近，从而表明 此进化方程具有很强的局部搜索能力。 由于标准微粒群算法具有一定的全局搜索能力，因此，微粒速度进化方程的第 一项呱d 用于保证算法具有一定的全局搜索能力，而第二和第三项则保证微粒群算 法具有局部搜索能力。 算法的基本流程 p s o 的具体的实现步骤如下： s t e p l 在初始化范围内，对微粒群进行随机初始化，即设置微粒的初始位置、 初始速度和种群规模； s t e p 2 计算每一个微粒的适应值； s t e p 3 更新每一个微粒的个体最优尸和只； s t e p 4 根据公式和公式对微粒的速度和位置进行更新； s t e p 5 判断是否满足终止条件。如果满足，转s t e p 6 ；否则，转s t e p 2 ，继续 迭代。 s t e p 6 输出全局最优只，算法运行结束。 2 4 小结 智能算法为解决复杂问题提供了新的思路和方法，作为经典的复杂问题，t s p 问题既是有价值的实际应用问题，也是各种算法在离散领域的测试用例。本章简要 介绍了现阶段解决这一问题的各种算法，包括传统算法、智能计算方法。因本文的 需要，较详细的介绍了微粒群算法、遗传算法及蚁群算法。 第三章解决t s p 问题的离散微粒群算法的设计 第三章解决t s p 问题的离散微粒群算法的设计 3 1 离散微粒群算法 经典的微粒群优化算法在求解连续空间的优化问题方面显示了优良的特性：结 构简单，收敛速度较快，鲁棒性好等等。但是目前微粒群算法的研究主要集中在连 续微粒群算法，正如公式( 2 7 ) ( 2 8 ) 所示，其速度、加速度等状态量都是连续的， 它们的运算法则也是连续量的运算。这些连续性特征给算法在离散优化问题上的应 用带来巨大的困难。 在现阶段，解决离散问题的微粒群算法的设计主要存在以下两种方法： 其一，以经典的连续微粒群算法为基础，针对特定的问题，将离散问题空间映 射到连续微粒运动空间，并适当修改微粒群算法进行求解。计算上仍采用经典微粒 群算法在连续领域应用的速度位移方程对微粒进行更新，之后再将微粒的连续解映 射为离散解进行适应值评价，如此交替进行，可以在应用现有的微粒群算法的研究 成果的同时，解决离散问题。如：二进制微粒群算法( b p s o ) 【26 ，对微粒位置的近似 取整策略的改进微粒群算法，如文献【3 3 j 等等。 其二，以微粒群算法信息更新本质机理为基础，在经典微粒群优化算法的基本 思想算法框架下，重新定义微粒群算法传统的信息共享和微粒更新方程来求解。在 计算上以离散空间对矢量的位操作取代传统向量计算，从信息流动机制上看，仍保 留了微粒群算法特有的信息交换和流动机制。对现有微粒群算法进行改进以满足实 际应用的需要。如文献【3 5 】【3 7 】【3 9 】【4 0 】【4 8 】中的改进算法。 用于连续空间的离散微粒群算法在求解离散问题时，算法产生的连续解与整数 规划问题的目标函数之间存在多对一的映射，因此该目标函数不能完全反映微粒群 算法中连续解的质量。此外整数规划问题的连续化导致大量冗余解空间与冗余搜索， 从而影响算法的收敛速度以及求解的质量，同时建立理想的问题解到微粒位置空间 的映射本身也是一个难题。所以研究新的离散微粒群算法模式，重新定义微粒群算 法在离散问题空间的状态表示和运算规则，扩展传统微粒群算法的更新操作，实现 算法在离散空间的搜索，是应用微粒群算法求解离散问题，尤其是高维复杂离散问 题的一个可行之选。正是鉴于此，本文即采用这样的技术主线，在保持原有算法优 化机理的前提下，结合t s p 问题的特性，对微粒群算法进行改进。下面是对微粒群算 法的优化机理进行分析。 1 9 求解旅行商问题的微粒群算法研究 3 2 微粒群算法的优化机理 公式( 2 7 ) ( 2 8 ) 代表单位迭代微粒的更新，为传统算法的核心实现方案，体 现了微粒群优化机理。根据速度位移迭代公式可知，微粒的更新按照以下步骤进行： 1 微粒从个体历史最优值继承部分的信息 由公式( 2 7 ) 可知，单位迭代微粒更新的本质：微粒所代表的解向量在连续解 空间跟踪其个体历史最优和邻域历史最优值的向量运算。其中，微粒从个体历史最 优值获得更新信息：q r a n d ( ) ( 巳一x ，d ) ，q r a n d o 代表了微粒从个体历史最优值岛的 信息继承度，反映了对匕信息的置信指标。 2 微粒从其邻域极值继承部分信息 微粒以相同的方式从邻域历史最优值获得更新信息：c 2 r a n d ( ) ( p g a x 耐) ，同 样c ：r a n d ( ) 代表微粒从继承信息的程度，反映了对白信息的置信指标。 3 微粒进行随机或局部搜索 根据公式( 2 7 ) ，微粒在从个体历史最优和邻域历史最优极值获得更新信息后， 进行如下的更新操作呱j ，其中呱d 初始化的随机性使得微粒具有在解空间上的全 局所搜能力，惯性权重形则是具有平衡算法全局搜索与局部搜索的能力，即搜索的 随机程度随度随迭代线性下降，在算法后期趋于局部搜索。 由以上分析可知，微粒群优化机理的本质为微粒从其个体历史最优和邻域历史 最优值中获得更新信息，并在此基础上进行随机或局部搜索。但是基于该机理的传 统算法实现局限于具体更新操作即速度位移更新算子，而该算子本身的局限性限制 了算法在离散及组合优化领域的应用。而从另一方面看，传统算法的核心更新公式 ( 2 7 ) 也可以理解为：一个正在进行“飞行 的微粒要从别的微粒，和自身记忆中的经 过的最好位置中得到这样的信息，每一维上为一个什么样的数值才能使一个解变成 一个较优秀的解，或者怎么样的解是一个优秀的解。所以此处的“+ ”可以理解成如 何把一个个体历史最优和邻域历史最优值位置中积极的信息传递到自身中去，而不 必拘泥于采用何种方式传递过去，比如可以理解为遗传算法中的交叉操作，因为遗 传算法中的交叉操作最本质的意义就在于两条染色体通过交叉操作，保留彼此中的 优秀基因片段，以形成新的优秀染色体。而微粒群算法在解决t s p 问题时，速度同样 携带优秀的片段路径信息。这样就可以借鉴优秀的交叉算子，更加有效的传递这些 信息。同样彤d 因为是微粒个性的反映，就是微粒在“飞行”的过程中按照自身“思 想”，选取自身认为合适方向。所以同样也不用拘泥去增加一个随机的数值，而应该 第三章解决t s p 问题的离散微粒群算法的设计 根据自身要解决的问题，适当的重新定义这部分，采用适合于自身问题的方式，例 如，可以理解为遗传算法中的变异，这样就可以采用遗传算法中的优秀的变异算子。 微粒群优化算法中微粒从其个体历史最优和邻域历史最优值获得更新信息，具 有较大的选择压力。相对于遗传算法以概率从整个种群中获得进化信息，蚁群算法 从别的蚂蚁留下的信息素获得进化信息比较，其信息共享机制中信息的流动是单方 向的，信息流动的目的性更强，效率更高，即一次信息流动对解的改进较大，从而 避免了大量冗余的信息传递操作，提高收敛速度。但是，理论上该信息流动拓扑结 构的潜在缺陷在于算法过于贪婪地获取更新信息，使得微粒的搜索受其个体与邻域 极值的影响较大，一旦其个体历史最优值为局部最优，微粒将难以摆脱该局部极值。 而一旦邻域历史最优值为局部最优解，其信息将覆盖整个邻域种群，导致该种群以 较大概率陷入局部收敛。但是正如文献跚中所提并证明的，事实上因为个体历史最 优和邻域历史最优值本身为较优的解，从以上个体获得更新信息至少可以保证微粒 可以获得上述相近质量的解。与通过概率选择交叉个体的遗传算法相比，其目的性 更强，避免大量冗余的遗传操作。微粒部分继承个体历史最优和邻域历史最优值的 信息至少可以保证微粒不会收敛到与个体历史最优和邻域历史最优值相差较大的局 部最优解，因此在一定程度上可以降低算法局部收敛的概率。虽然这样的设计有利 于降低算法陷入局部最优的可能，但是彤j 仍然起着了很大的作用，简单的按照标 准微粒群算法中的惯性因子定义形，正已不再实用于解决一些实际的离散问题，同 样应该被重新的定义。如文献【3 5 】【3 7 】 3 8 1 3 9 】 3 3 解决t s p 问题的离散微粒群算法设计的基本原则 通过上一小结对微粒群算法优化机理的分析并参考文献【4 5 】中所建议的微粒群算 法的设计原则，我们可以总结设计解决t s p 问题的离散微粒群算法的一些基本原则： 1 适用性原则 一个算法的适用性，是指该算法所适用的问题的种类，这取决于算法所需要的 限制与假设。如果优化问题的性质不同，则相应的处理方式