（计算数学专业论文）关于tsp问题的演化算法研究.pdf

摘要 t s p ( t r a v e l i n gs a l e s m a np r o b i e m ) 问题是组合优化中最为著 名的问题，它综合了一大类组合优化问题的典型特征。从理论上讲， 使用穷举法不但可以求解t s p 问题，而且还可以求出该问题的最优 解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索 空间中寻求最优解，几乎是不可能的。所以，各种求t s p 问题近似 解的优化算法应运而生了，其中演化算法的运用为求解t s p 问题带 来了新的希望。 演化算法是种模拟自然界自适应演化过程而发展起来的通用问 题求解方法。它采用简单的编码技术来表示各种复杂的结构，并通过 对编码进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确 定搜索的方向。简单的遗传操作和优胜劣汰的自然选择机制使演化算 法具有不受搜索条件的限制、不需要其它辅助信息的特点。它采用的 种群搜索模式，有利于搜索到全局最优解，能较好的解决解的局部性 问题。因此，演化算法被广泛的用来求解具有挑战性的问题。 在求解t s p 问题时，蚁群算法( a c o ) 和粒子群算法( p s o ) 都显 示了有效的解决问题的能力。而郭涛算法在求解t s p 问题时性能表 现特别突出。本文分析和研究了改进的蚁群算法中的信息素的积累及 信息的交换方式，通过实验证明该算法避免了算法过早停滞的缺点，提 高了解的质量，同时算法的收敛速度得到保证。对微粒群优化算法的 速度位置算式的改进进行了分析研究，该算法符合组合优化问题的特 点，在求解t s p 上有较高的搜索效率。在将原郭涛算法算子的线性 逆转改为环形逆转以及引入映射算子、优化算子以及增加一些控制策 略基础上，通过基因片断的路径长度来决定环形路径逆转的方向，对 随机选择的城市所在的基因片断进行了路径长度的判断，针对t s p 解的环形路径的特点，以一定的概率进行了局部优化。 关键词：t s p 问题，演化算法，蚁群算法，p s o 算法，郭涛算法 a b s t r a c t t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) i so n eo f t h em o s tf a m o u sa m o n g t h ec 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 i th a st h et y p i c a lc h a r a c t e r i s t i c so f al o to fc 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 t h e o r e t i c a l l ys p e a k i n g t h e e n u m e r a t i o nn o to n l yc a ns o l v et s p , b u ta l s oo a lg e tt h e b e s ta n b 耕e r b u t t oa l lc o m p u t e r sn o w a d a y s , i t sh a r d l yt oo b t a i ni t sb e s ta n s w e ri ns u c h h u g es e a r c hs p a c eb yu s i n gc o n l m o b e n u m e r a t i o mt h e r e f o r e ，a l lk i n d so f a l g o r i t h m st os o l v et s pe m e r g e db e c a u s eo fd e m a n d a m o n go ft h e m , e v o l u t i o n a r ya l g o r i t h mb r i n g s 惦n o wm e n u st os o l v et h et s p e v o l u t i o n a r ya l g o r i t h m a ) i sa l li n t e l l i g e n ta l g o r i t h mt h a tl e a r n s f r o mt h ee v o l u t i o n a r yp r o c e s si nt h en a t u r e e ae m p l o y sac o d i n g t e c h n o l o g ya n ds o m eg e n e t i co p e r a t i o n s u n d e rt h ep r e s s u r eo fs e l e c t i o n , w h i c hm e n i a l s ”f i t ss u r v i v e ”，t h ea l g o r i t h mc a np r o d u c ea no p t i m a l s o l u t i o n b e c a u s ee ai ss i m p l ea n di ts e l d o mn e e d sa n ya d d i t i o n a l i n f o r m a t i o na b o u tt h ep r o b l e m , e ab e c o m e sag e n e r a ls o l v e ro fc h a l l e n g e p r o b l e m s i nt h et s p , a n ta l g o r i t h m ( a c o ) a n dt h ep a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) h a v ed e m o n s t r a t e dt h ea b i l i t yt os o l v ep r o b l e m se f f e c t i v e l y , a n dg t ( g u ot a oa l g o r i t h m ) p e r f o r mw o n d e r f u l l y t h i sp a p e ra n a l y z e sa n ds t u d i e s t h ee x c h a n g ea n da c g u m u l a f i o nm o d ea b o u tp h e r o m o n ei nt h ei m p r o v e d a c o ，t h ea l g o r i t h mw i l ln o ts t o p p e de a r l i e r , ab e t t e rs o l u t i o nc a na l s o l i k e l yb eg o ta n ds p e e do ft h ec o n v e r g e n c ec a nb eg u a r a n t e e d t h e i m p r o v e dp s of o r m u l aa b o u tt h es p e e da n dl o c a t i o ni sa n a l y z e da n d s t u d i e d , t h ea l g o r i t h mi sc h a r a c t e r e db yt h ec o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m sa n di tp e r f o r m sh i g h e re f f i c i e n c yi ns e a r c h i n gb e t t e rs o l u t i o n a f t e rs u b s t i t u t i n gt h ea n n u l a r - r e v e r s ef o rt h el i n e a r - r e v e r s e ，i n t r o d u c i n g t h em a p p i n ga n do p t i m i z a t i o no p e r a t o ra n di n c r e a s i n gs o m ec o n t r o l s l x a t e g i e si nt h e 撕g i n a lg t , t h ea n n u l a r - r e v e r s ed i r e c t i o nw i l lb e d e t e r m i n e db yt h ep a t hl e n g t ho ft h ed n af r a g m e n t s ，w h e t h e rt h e r a n d o m l ys e l e c t e dc i t yw i l lb ea c c e p t e dd e p e n d so nt h el e n g t ho ft h e d n a f r a g m e n tc o n t a i n e di t , b e c a u s et h ef i g u r eo ft h et s ps o l u t i o ni s a n n u l a r , t h el o c a lo p t i m i z a t i o ni s a d d e di n t oi ta c c o r d i n gt oc e r t a i n p r o b i l i t y k e yw o r d s ：t r a v e l i n gs a l e s m a np r o b l e m , e v o l u t i o n a r ya l g o r i t h m ， a n ta l g o r i t h m , p a r t i c l es w a r mo p t i m i z a t i o n , g u ot a oa l g o r i t h m m 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体。均已在文中以明确方式标明。本人 湖南师范大学学位论文版权使用授权书 日 鬣裂稚霹芗弧i ! i 锄麟：铡日御嶂印够日 i 关于t s p 问题的演化算法研究 1 1t s p 问题概述 第一章绪论 t s p 问题( 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 问题是组合数学中一个 古老而又困难的问题，它的历史由来己久，可追溯到上个世纪2 0 年 代。经过了7 0 多年的研究，虽然取得了很多进展，但直至今日，这 个问题至今尚未彻底解决，现已归入所谓的n p 完全性问题。其简单 描述为：一名商入欲到n 个城市推销商品，每两个城市i 和j 的之间 的距离为心d ，v i ，如何选择一条路径使得商人每个城市走一遍后回 到起点，且所走的路径最短。相应的数学描述为： r a i n 噍，墨， ( 卜1 ) h s t 毛，= 1 i 2 l ，2 ，n i = l ( 1 - 2 ) ，= lj = 1 ，2 ，n 一 ( 卜3 ) 面 一，s 阁一l2 受蚁群觅食行为 二 ( f o r a g i n gb e h a v i n r ) 中的基于信息素( p h e r o m o n e ) 的间接通信机 制的启发，提出了一种蚂蚁算法( a n ta l g o r i t h m ) 。并用该算法求解 旅行商问题( t s p ) 获得了很好的效果。 2 1 蚁群算法 蚁群算法是受到对真实蚁群的觅食行为的研究的启发而提出的， 生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最 短路径，而单只蚂蚁却不能。生物学家通过大量细致的观察研究表明， 蚂蚁个体之问是通过一种称之为信息素的物质进行信息传递的，蚂蚁 在运动过程中，能够在它所经过的路径上留下信息素，蚂蚁在运动过 程中能够感知这种信息素，并根据信息素的浓度来选择自己的行走路 径。一条路上的信息素越浓，其它蚂蚁将以越高的概率跟随此路径， 从而该路径上的信息素将被进一步加强，因此，大量蚂蚁的集体行为 表现出一种信息正反馈现象：某一路径上所走过的蚂蚁越多，则后来 者选择此条路径的概率也就越大。 2 。1 。1 蚁群算法的基本原理 图2 - l 蚁群总能够找到从巢穴到食物源泉的最短路径 现实生活中单个蚂蚁的能力和智力非常简单，但它们通过相互协 调、分工、合作完成不论工蚁还是蚁后都不可能单独完成的筑巢、觅 食、迁徙、清扫蚁穴等复杂行为，比如在蚂蚁觅食过程中能够通过相 硕士学位论文 互协作找到食物源和巢穴间的最短路径( 现实中我们总可以观察到大 量蚂蚁在巢穴和食物源之间形成近乎直线的路径，而不是曲线或者圆 等其他形状，图2 - 1 ) 。像蚂蚁这样的群居昆虫，虽然没有视觉，却 能找到由蚁巢到食物源的最短路径，原因是什么呢? 静s t _ 一5 7- 熊盎崖 嘲f 蜘茹 一即静一一 o b s t e c | e 图2 - 2 蚂蚁以等同概率选择各条路径 蚁群群体能够完成复杂的任务，不仅如此，蚂蚁还能够适应环境 的变化，如：在蚁群运动路线上突然出现障碍物时，一开始各个蚂蚁 分布是均匀的，不管路径是否区分长短，蚂蚁总是先按同等概率选择 各条路径( 图2 - 2 ) 。 但经过一段时间后蚂蚁能够很快的重新找到最优路径，蚁群是如 何完成这些复杂任务的呢? 所有这些问题，很早就激起了生物学家和 仿生学家的强烈兴趣，仿生学家经过大量细致观察研究发现，蚂蚁个 体之间是通过一种称为外激素( p h e r o m o n e ) 的物质进行信息传递， 从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行 为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过 程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程 中能够感知这种物质的存在及强度，并以此指导自己的运动方向，蚂 蚁倾向于朝着该物质强度高的方向移动。如路径上出现障碍物时相等 时间内较短的路径上信息量就遗留得比较多，选择较短路径的蚂蚁也 随着增多( 图2 - 3 ) 。 关于t s p 问题的演化算法研究 s i l t蝴 _ 。掣 k 瞪- 一 。雌一忡矿铺_ f 季， 摹 ￥专驹霉。1 图2 _ 3 较短路径上信息量较大，选释该路径的蚂蚁增多 蚂蚁选路过程中较短路径上遗留的信息量会在很短时间内大于较 长路径的原理我们不妨用下图( 图2 - 4 ) 说明：假设a 、e 两点是蚁 群的巢穴和食物源，从其间有两条路径a b h - d e 和a b _ c d - e ，其 中b - h 和h - d 间距离为l m ，b - c 和c - d 间距离为0 5 m 。 最初( 即t = o 时刻) 。如图2 4 所示，当3 0 只蚂蚁走到分支路 口b 或者d 点时，要决定往哪个方向走，因为初始时没有什么线索可 供它们选择，所以它们就以相同的概率选择路径，结果是有1 5 只蚂 蚁走左边的路径d _ h 、b - h ；另外1 5 只蚂蚁走右边的路径d c 、b - c ， 这些蚂蚁在行迸过程中分别留下信息量。若假设蚂蚁都具有相同的 速度( i m l s ) 和信息量释放能力，则经过1 秒后从d 点出发的3 0 只 蚂蚁有1 5 只到达了h 点，有1 5 只经过c 到达了b 点，同样的从b 点 出发的3 0 只蚂蚁有1 5 只到达了h 点，有1 5 只经过c 到达了d 点。 彳艮显然，在相等的时间问隔内路径沪h b 上共有1 5 只蚂蚁经过并遗 留了信息量，d c b 上却有3 0 只蚂蚁经过并遗留了信息量，其信息 量强度是d h b 路径上的2 倍。因此，当3 0 只蚂蚁分别回到a 、e 点重新选择路径时就会以2 倍予d - h - b 的概率选择路径d - c b ，从而 d - h - b 上的蚂蚁数目变成了1 0 只，是d - c b 上蚂蚁数目的半，距 离较短的路径上信息量很快得到了强化，其优势也很快被蚊群所发 现。 硕士学位论文 图2 - 4 蚂蚁选路过程示例 不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息 正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概 率就越大，蚂蚁个体之间就是通过这种信息的交流搜索食物，并最终 沿着最短路径行进( 图2 - 5 ) 。 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优 路径的方法提出的，即让人工蚂蚁根据路径上的相当于p h e r o m o n e 的 数字信息量的强度选择路径，并在所经过的路径上留下相当于 p h e r o m o n e 的数字信息量，然后随着时间的推移，最优路径上的数字 信息量将积累的越来越大，从而被选择的概率也越来越大，最终所有 人工蚂蚁将趋向于选择该路径。这种模拟蚁群搜索食物的过程与著名 的旅行商问题非常相似，因而最初人工蚁群算法被提出用于求解旅行 商问题。 可见，人工蚁群算法是一种随机搜索算法。与其他模拟进化算法 一样，通过侯选解组成的群体的进化过程来寻求最优解，该过程包含 两个基本阶段：适应阶段和协作阶段。在适应阶段，各侯选解根据积 累的信息不断调整自身结构；在协作阶段，侯选解之间通过信息交流， 以期望产生性能更好的解。 关于t s p 问题的演化算法研究 n e s t 秣。 。磅_ 竺 一_ k 鳢a 硼1 = p p 。拍 丌嫌邗静一 o b s t a c l e 图2 - 5 蚂蚁最终饶过障碍物找到最短路径 2 1 3 蚁群算法的发展 自从d o r i g o 等提出第一个a c o 算法，即a s ( a n ts y s t e m ) 算法 ( d o r i g o ，m a n i e z z o c o l o m i ) 后，许多学者对就如何改进基本a c o 算法进行了大量的研究，如具有精英策略的a s 。( b u l l n h e i m e re t a 1 ) ，基于蚂蚁等级的a s 。( b u l l n h e i m e re ta 1 ) ，引入了妒学习 机制的a n t - q ( d o r i g om l m g a 皿b a r d e l l a ) ，采用伪随机比例规则 的a c s ( d o r i g om l m g a m b a r d e l l a ) ，将信息限制在一定的范围 内并使用了信息素平滑机制的最大最小蚁群算法m h a s ( s t u t z l e ，h o o s 唧) 。此外，国内的学者就提高 c o 算法的性能也做了大量有益的工 作。张纪会等人提出了自适应的蚊群算法t “。采用确定性选择和随机 选择相结合的策略，在搜索的过程中动态地调整选择的概率，实现了 选择概率的自适应，提高了算法的速度和性能。陈烨提出带杂交算子 的蚁群算法p l ，通过引入遗传算法中用到的杂交算子来改善蚁群，使 其对应的问题的解更加优良。目前，越来越多的学者被蚁群算法的优 势所吸引。并将它应用于各个领域。 2 2 改进的蚁群优化算法求解t s p 问题 2 2 1 求解t s p 问题的基本蚁群算法模型 用岛( f ) 表示f 时刻位于城市f 的蚂蚁的个数，m = 壹饥( r ) 为蚂蚁的总 l f f i l 硕士学位论文 数o ) 表示f 时刻边 上的信息素，白( o ) 为乃o ) 的初值( 为常数) 随着 时间的推移，新的信息素加进来，旧的信息素要挥发，1 一p 表示信息素 的挥发快慢当所有蚂蚁完成一次周游后，各条边上的信息素按下式调 整： o 十1 ) = pr u f f ) + a 勺 ( 2 - 1 ) a r u = ( 2 - 2 ) a 表示本次周游中路径盯上的信息素增量，初始时刻，a 勺= o 苟表 示第k 只蚂蚁在周游过程中释放在边移上的信息素 肾皆= 删删删蝴蝴洲( 2 - 3 ) q 为常数，厶表示本次周游后，第k 只蚂蚁所形成的回路的长度 蚂蚁在周游时，向那个城市转移由转移概率拼决定 咖 萎棘一 【o e l s e 其中a l l o w e d 。= o ，1 ，丑一1 ) 一豇加。表示蚂蚁k 当前能选择的城市集合， t a b u 。为禁忌表，它记录蚂蚁k 已路过的城市，用来说明人工蚂蚁的记忆 性，巩是某种启发信息，口，体现了信息素和启发信息对蚂蚁决策的 影响 在t s p 问题中，a c o 基本的运行过程是这样的：m 只蚂蚁同时从某 个城市出发，根据( 2 4 ) 选择下一次旅行的城市，已去过的城市放, 人t a b u 。 中，一次循环完成后，由公式( 2 1 - 2 3 ) 更新每条边上的信息素，反复重复 上述过程。直到终止条件成立 2 2 2 改进的蚁群算法 蚁群算法是一种随机搜索优化算法，与其它模拟进化算法一样存 在着缺陷样存在着缺陷。在算法的初期，由于各条路径上的信息素相 同，算法只能按启发信息( 路径长短) 进行求解，导致求解速度缓慢； 1 4 关于t s p 问题的演化算法研究 而信息的正反馈又容易于过早的陷入局部最优，使算法停滞。为了提 高算法的全局搜索能力和求解速度，需要增加算法初期各条路径上的 信息素分布，增强算法搜索的随机性。增加求解空间解的多样性。 l 、对蚁群算法的改进 1 ) 、对搜索方式的改进，采用分区搜索。 分区搜索的目的在于获得局部较优解的组合，产生初始信息素分 布。使各条路径上的信息素分布有所不同，提高算法的搜索速度。分 区的方式要有利于全局搜索。针对不同的问题可以有不同的分区方 法，以5 0 个城市为例进行分区，以搜索区域的中心为划分中心，将 整个区域分成4 个小区，每个小区分布的城市数目大致相等。在4 个小区分别进行蚁群搜索后产生每一小区的较优解，将这些较优解进 行优化组合( 可以进行不交叉判断或用最邻近点相连规则) ，形成一 个全局较优解，产生初始信息素分布。 2 1 、引入变异 为了克服蚁群算法时间较长的缺陷，这里引入遗传算法中变异算 子，经过局部优化后，整个群体的性能就会有明显改善，使算法保持 更好的多样性特征。这里对蚁群算法的变异主要采取逆转变异。在所 得的某一解中随机选两点，再把这两点内的路径按反序插入原位置 中。例如，路经a 寻 o 1 2 3 4 5 - 6 7 8 - 9 o ) 的逆转点选择3 、6 ，经逆 转后，变为a = f o 1 2 石4 5 3 7 = 8 9 - 0 ，这种变异操作对于t s p 问 题，就调整前后的t s p 圈的长度变化而言属于非常细微的调整，因 而可使得局部优化的精度提高，但所需的计算稍微复杂一些。在实现 过程中，逆转变异法可在每次循环安排完m 只蚂蚁的路径之后、信 息素调整之前进行，且应考虑到时间问题。在具体的应用中，有的方 案只对每次循环的最优路径进行变异，如果变异后路径长度小于变异 前。就保留这个最优解，否则就维持路径原值 3 ) 、采用自适应的挥发系数。 信息素挥发度l p 的大小直接关系到蚁群算法的全局搜索能力 及其收敛速度。当l p 过大时，以前搜索过的路径被再次选择的可 能性过大，会影响到算法的随机性能和全局搜索能力；反之，通过减 小信息素挥发度l p 虽然可以提高算法的随机性能和全局搜索能 硕士学位论文 力，但又会使算法的收敛速度降低。因此，可通过自适应方法改变信 息素挥发度l p 。最后，将各条路径上可能的信息量限制在【，】 之间，超出这个范围的值将被限制为或者为嘲。可以有效 地避免算法停滞；f 一可以避免某条路径上的信息量远大于或远小于 其余路径情况的发生，使得所有的蚂蚁都集中到同一条路径上，从而 使算法不再扩散，加快收敛速度。 2 、仿真实验： 通过对随机产生的5 0 个城市、7 5 个城市以及从通用t s p l i b 9 1 中 选用的c h l 5 0 ( 1 5 0 个城市) t s p 问题进行仿真研究，比较了基本的蚁 群算法b a s i c - a c o t ”1 和本文提出的改进型蚁群算法i m p r o v e d a c o 的 计算结果仿真试验结果如表2 1 所示。 表2 1 两种算法的计算结果 5 0 个城市7 5 个城市 c h l 5 0 算法 平均值最好结果平均值最好结果平均值最好结果 b a s i c - a c o4 3 4 24 3 0 45 5 2 3 5 4 9 9 7 5 1 2 67 4 7 2 4 l m p r o v l - a c o 4 2 7 84 2 7 45 4 6 65 4 5 86 8 2 3 66 7 2 1 8 同时给出两种算法计算5 0 个城市所获得的最优路径如图2 _ 6 和 2 7 所示5 0 个城市的t s p 问题在b a s i c a c o 求解下的最优路径长度 为4 3 0 4 ，最优路径图形如图2 - 6 所示；在i m p r o v e d - a c o 求解下的最优 路径长度为4 2 7 4 ，最优路径图形如图2 7 所示 关于t s p 问题的演化算法研究 从表i 可以发现，改进后a c o 算法明显优于b a s i c a c o 算法，分析 原因，主要是b a s i c - a c o 算法过分加强了信息的正反馈作用，虽然加快 了算法的收敛速度，但易于使算法过早停滞，陷入局部解。该算法通过 改变搜索方式，加入了特有的变异算子，改变了信息素调节方式从而 使得可行解的范围扩大，而又保证了一定的正反馈作用，改善了算法的 求解质量，解的稳定性也比较好。 2 3 本章小结 蚁群算法从提出到现在，已经成为求解t s p 问题的一个有效工具， 但也存在一些不足之处。本章第一部分简要介绍蚁群算法的基本原理 和其发展历程，第二部分给出了蚁群算法求解t s p 问题的基本模型， 并对改进的蚁群算法进行了分析研究，实验结果表明改进后的算法性 能要优于基本的蚁群算法。 关于t s p 问题的演化算法研究 第三章粒子群优化算法其对t s p 问题的求解 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n , p s o ) 算法是由 k e n n e d y 和e b e r h a r t ”1 于1 9 9 5 年提出的一种基于群智能方法的优 化算法，其源于鸟群和鱼群的群体运动行为的研究。p o s 广泛应用到 工程中，近年来p s o 算法在求解t s p 问题上也取得了比较大的进展。 3 粒子群优化算法 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n , p s o ) 算法最初由k e n n e d y 提出，它源于鸟群和鱼群群体觅食运动行为研究结果的启发。与遗传 算法类似，都是一种基于群体的进化计算方法【”l 。它与遗传算法不同 韵是：每个个体( 称为一个粒子) 都被赋予一个随机速度并在整个问题 空问中流动；个体具有记忆功能；个体的进化不是通过遗传算子，丽是 通过个体之间的合作与竞争来实现的。 3 1 1 粒子群优化算法的基本原理 p s o 算法源于对鸟群觅食行为的研究。研究者发现鸟群在飞行过 程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体 总保持一致性，个体与个体间也保持着最适宜的距离。通过对类似生 物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制， 它为群体的进化提供了一种优势【1 4 1 ，这也是p s o 算法形成的基础。 我们可以设想这样一个场景：一群鸟在随机搜索食物。在这个区 域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当 前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简 单有效的就是搜寻目前离食物最近的鸟的周围区域。 如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中 飞行的一只觅食的“鸟”就是p s o 算法中在解空间中进行搜索的一 个“粒子”( p a r t i c l e ) 。也是优化问题的一个解。“食物”就是优化问 题的最优解。粒子的概念是一个折衷的选择，它只有速度和加速度用 于本身状态的调整，没有质量和体积。“群”( s w a r m ) 的概念来自于 人工生命d r ，满足人工生命的五个基本原则1 1 5 i 。因此p s o 算法也可 硕士学位论文 看作是对简化了的社会模型的模拟，社会群体中的信息共享是推动算 法的主要机制。 p s o 算法中每个粒子即解空间中的一个解，它根据自己的飞行经 验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历 过的最好位置，就是粒子本身找到的最优解。整个群体所经历过的的 最好位置，就是整个群体目前找到的最优解。前者叫做个体极值 ( p b e s t ) ，后者叫做全局极值( g b e s t ) 。每个粒子都通过上述两个极值 不断更新自己，从而产生新一代群体。实际操作中通过由优化问题所 决定的适应度函数值( f i t n e s sv a l u e ) 来评价粒子的“好坏”程度。显 然，每个粒子的行为就是种追随着当前的最优粒子在解空间中搜索。 在p s o 算法中每个粒子可以看作是解空间中的一个点。如果粒 子的群体规模为n ，则第i ( i = 1 ，2 ，n ) 个粒子的位置可表示为x i ，它所经历过的“最好”位置记为p b e s t 【i 】，它的速度用vi 表示， 群体中“最好”粒子的位置的索引号用g 表示。所以粒子i 将根据 下面的公式来更新自己的速度和位置【”1 1 7 】： k = ，k + f t r a n d o ( p n e s t i - x t ) + c 2 r a n d o ( p b e s t l g 一x ，) 0 1 ) 置-x,+e(3-2) 其中c 1 、c 2 为常数，称为学习因子；r a n d0 和r a n d0 是【o ，1 l 上的 随机数，w 惯性权重( i n e r t i aw e i g h o 。公式由三部分组成，第一部分 是粒子先前的速度，说明了粒子目前的状态；第二部分是认知部分 ( c o g n i t i o nm o d a l ) ，表示粒子本身的思考；第三部分为社会部分( s o c i a l m o d a l ) 。三个部分共同决定了粒子的空间搜索能力。第一部分起到 了平衡全局和局部搜索的能力。第二部分使粒子有了足够强的全局搜 索能力，避免局部极小。第三部分体现了粒子间的信息共享。在这三 部的共同作用下粒子才能有效的到达最好位置。 另外，粒子在不断根据速度调整自己的位置时，还要受到最大速 度( ) 的限制。当k 超过时将被限定为。 关于t s p 问题的演化算法研究 3 1 2 粒子群优化算法的发展 p s o 收敛快，特别是在算法的早期，但也存在着精度较低，易发 散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优 解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的 方向飞去，所以粒子趋向同一化( 失去了多样性) 。使得后期收敛速度 明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的 精度也比g a 低，因此很多学者都致力于提高p s o 算法的性能，下 面对这些改进作简单介绍。 l 、收敛速度的改进 s h y y & e b e r h a r t r c ( 1 9 9 8 ) 提出了惯性权重w 的方法，惯性权 重w 是与前一次速度有关的一个比例因子，而速度更新方程可由 ( 3 1 ) 来表示。用惯性权重来控制前面的速度对当前速度的影响， 较大的w 可以加强p s o 的全局搜索能力，而较小的w 能加强局部搜 索能力。基本的p s o 可以看作w = l ，因此在迭代后期缺少局部搜索能 力。实验结果表明，w 在【o 8 ，1 2 】之间p s o 有更快的收敛速度。针对 w 的取值问题。s h y y & e b e r h a r t r c ( 1 9 9 9 ) 提出了从9 9 到0 4 进 行线性下降的方法，s h yy & e b e r h a r trc ( 2 0 0 1 ) 提出用模糊控制器来 动态自适应地改变惯性权重的技术。 c l e r em ( 1 9 9 91 提出在速度方程中用压缩因子来帮助p s o 算法 收敛，加入压缩因子后的速度修改方程为： k = x ( w k + q r a n a 0 + ( t , b e s t i - 五) + c 2 + e , a n a o ( p b e s t l g 一置) ) ( 3 - 3 ) 式中z 是压缩因子。 另外，有些学者提出用遗传算法中的基本算子的思想来改进p s o 的运动方程，例如，a n g e l i n ep ( 1 9 9 9 ) 提出的混合p s o 主要应用p s o 的基本机制以及演化计算所采用的自然选择机制，而l o v b j e r g 等人 ( 2 0 0 1 ) 将遗传算法中的复制和重组这些称为繁殖的操作加入到全局版 p s o 中，这些方法都在一定程度上提高了p s o 的局部求精能力，加 快了算法的收敛速度。 2 、多样性的改进 2 1 硕士学位论文 对提高p s o 的群体多样性的研究主要集中在局部p s o 的研究上， 研究如何通过定义合适的近邻结构来提高群体的多样性，比如， s u g a n t h a np n ( 1 9 9 9 ) 提出了基于粒子的空间位置划分的方案，在迭代 中，计算每一个粒子与群中其他粒子的距离，如果距离小于一个闭值， 则属于此粒子的近邻；k e n n e d yj ( 1 9 9 9 ) 研究了几种不同的邻域拓扑结 构( 包括环形结构、随机化环形结构、轮形结构和随机化轮形结构等) 对局部p s o 算法性能的影响，结果表明，拓扑结构对算法性能的影 响很大，且最佳的拓扑形式因问题而定，如对有很多局部最优的函数， 轮形拓扑邻域算法能得到最好的结果，k e n n e d y 推测，这是由于此种 结构的信息流动较慢；而对于单峰函数，星形拓扑邻域算法可以产生 较好的结果，因为它有较快的信息流动( 这里的拓扑都是在粒子序号 空间下的拓扑) 。k e 衄e d y j ( 2 0 0 0 ) 提出了混合空间邻域和环形拓扑方 法的另一个局部p s o 版本，称为社会趋同法，因为生活中人们往往 是试图追随一个群体的共同观点，而不是群体中某个人的立场，将该 思想应用到p s o 中，即不用每个粒子的经验而是用它所属空间聚类 的共同经验来更新自己。 3 、其它改进方法 b e a s l e y 等( 1 9 9 3 ) 提出的最初使用在遗传算法中的序列生境技术 可以系统地访问每一个全局极值，其思想是在找到每一个极值后。都 用下降函数来自适应地改变适应值函数，如此算法就不会再回到该极 值。v a nd e nb e r g hf ( 2 0 0 2 ) 分析了序列生境技术对p s o 性能的作用， 虽然将序列生境技术引入p s o 会带来诸如参数选择、引入更多局部 极值等问题，但是该法能够枚举所有全局极值，在多目标优化问题上 还是很有意义的。为了减小定位所有全局极值的花费，p a r s o p o u l o s 等( 2 0 0 i ) 将自适应改变目标函数方法应用到了p s o 中，他提出一个两 步的转化过程来改变目标函数，以防止p s o 返回己经找到的局部极 值，该方法能跳出局部最优，有效定位全局最优点，有助于p s o 稳 定地收敛，虽然增加了计算量，p s o 的成功率却有明显的提高，但该 方法不能枚举全部最优。v 锄d e nb e r g hf 和e n g e l b r e c h tap ( 2 0 0 1 曲 提出了一种协同p s o ，该方法是将1 1 维向量分到1 1 个粒子群中，每粒 子群优化一维向量，评价适应值时将分量合成一个完整向量。例如针 关于t s p 问题的演化算法研究 对第i 个粒子群。除第j 个分量外，其他n - 1 个分量都设为最好值， 不断用第j 个粒子群中的粒子替换第j 个分量，得到第j 维的最好值， 其他维的处理也相同。为