（交通信息工程及控制专业论文）遗传算法在TSP上的应用及改进.pdf

摘要旅行商问题( t s p ) 是著名的n p 完全难题，也是组合优化、计算机科学界经典的问题之一。因此对t s p 寻找出实际而又有效的算法，就具有重要的理论意义和实际应用价值。而遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，具有简单、通用、稳健等特性，能依概率收敛到问题的全局最优解。这就是本文提出的改进遗传算法求解t s p 的目的和意义。本文从旅行商问题的概述出发，介绍了t s p 的数学描述与分类，在原有的基础上，对t s p 作了更细致的分类；介绍了遗传算法的基本概念、原理、步骤及意义，将遗传算法的一些主要的操作过程用数学形式表示，使其变得简单而又公式化；通过依赖于遗传操作的基本遗传机理的叙述，为以后算法的改进打下理论基础。本文主要工作如下：( 1 ) 分析了影响遗传算法性能的一些重要参数，通过基本遗传算法( s g a )对不同种群规模的砖p 问题分别进行计算机模拟仿真，讨论了基本遗传算法在求解t s p 中存在的不足。( 2 ) 针对现有的遗传算法的不足和髑p 本身的特点，提出了三种改进的混合遗传算法( h g a ) 。首先提出了混合遗传算法i ( h g a i ) ，在h g a i 中采用了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，而且生成的初始种群的随机路径的总长度服从正态分布。将依概率的近邻法和边重组交叉算子与启发式变异算子结合起来得到h g ai 。其次为了进一步改进其性能，保证算法的全局收敛性，混合遗传算法( h g a ) 应用改良圈算法及最大容许停滞代数，不仅避免了h g ai 中终止进化代数的选取问题，而且大大加快了算法的收敛速度，使算法具有很好的鲁棒性。同时在h g a i i 中采取杰出者记录与“父子混合”选择策略以及随机因素控制参数口，从理论上保证了算法的全局收敛性最后在混合遗传算法( h g a ) 中引入多元回归分析中的三均值的概念对遗传算法的控制参数进行动态调整，从而克服用不变的控制参数来控制遗传进化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。( 3 ) 对设计出的三种混合遗传算法通过数据进行了计算机仿真模拟，对算法的性能进行了分析测试。关键词：遗传算法旅行商问题混合遗传算法n p cm a s t e rd e g r e ed i s s e n a t i 佃a p p h c a h o n a n d i m p r o v 哪e n t o f g e n e 6 c a j g o r i t h m i n s o i v i n g t s pc a n d i d a t e ：x u eh 蛆弘址供e 细o r k m p u t i n 曲d i r e c t 脚b yz h a n g b a i y ic h 粕g 姐u n i v e 腭i 饥】| 【i a n7 l 0 0 6 91 h v e l i n gs a l e s m 姐p r o b l e mp )h 觞b e c o m et h ew e l l l m o 、】l ，nn o n d e t e 锄j n i s t i cp o l y n o m i a lc o m p l e t e n e s sp 叱z l e ，i ti sa l s oo n co ft h ew o r l dt y p i c a l锄b i n a t i o no p t i m i z a t i o n 卸dc o m p u t e rs d e n c cp r o b l 锄t h e r e f o r e ，句1 d i n go u tp 删c a l 锄dc f f i d e n ta 1 9 0 r i t l l mh 丛翘i m p o n a n tt h c o r e t i c a l 勰w c l l 觞p r a c t i c a l印p l i 龃t i o ns i 口i f i c a n c c n eg e t i ca l g o r i t l l mi sal d n do fm d o ms e 砌i n gm e ds i m u l a t i i l gb i o l o 百c a ln a t u r a ls e l e c t i o na i l dg e n c t i cm e c h a n i s m ，w h i c bn o to n l yh 舔m ec h a r a c t e r i s t i co fb e i n gs i n i p l e ，u l l i v e r s 吐粕ds k l b l e ，b u ta l s oc o n v c r g ct h eg i o b a ls o i u t i o nb 龉e do np r o b a b i l i t y t h i si st h ev e r ) ，p u r p o s eo fm c n t i o l l i n gt h ei m p r a v e dg e t i ca 1 9 0 r i t l i i i lt os o l v et s pi i it h i se s s a y t h ee s s a ys t a n sw i t ht h cg e n e r a la c c o u mo ft s p ，e x p l a i n st h em a t h e m a t i c a ld e s c r i p t i o n 卸dd 舔s i f i c a t i o no ft sp 0 nt h eo r i g i i i a ib 嬲i s ，m ce s s a ym d et h o r o u 曲d 勰s i 丘c a t i o ft s p ；n ee s s a yi l l 仃0 d u c e dt l l eb 嬲i cc 0 唧t ，p r i n c i p l e ，p 烈剃u r ea n ds i 印访啪c co ft h cg c n e t i ca l g o r i t h m i ta l s od i s p l a y c d m em a j o rp m c c s si nm a t l l e m a t i cw a y s ，m a k i n gt h e 掣m c t i ca l g 吲n u nc o m p r e h e n s i b l ea n df o m u l i z e d t h m u g ht h ed e s c r i p t i o no ft h cb a s i cg e n c t i cm e c h a n i s mb 弱e do nt h eg e n c t i co p e r a t i o n ，t h ee s s a yl a i dm e t h o df 0 蛐d a t i o nf b rt h cl a t e ri m p m v c m e n to fa l g o r i t l l n l m m a j o r t a s k so f t h ce s s a y ：( 1 ) a n a i y z e d m ej n l p o r t a n tp a 舳e t e 培砌u e n c i n gc a p a b i l i t yo fg e n c t i ca l g o r i 皿，t h r o u 曲c o m p u t c rs i m u i a t i n gt l l et s pb ys i m p l eg c n e t i ca l g o r i t h m ( s g 舢d i f f h e n tp o p u l a t i o ns c a l e ，t h ee s s a yd i s c i i s s c dt h ed i s a d v 强t a g e so ft l i cs i m p l eg e n c t i ca l g o r i t h mi n l v i n g 弼p ( 2 ) g i v e nt h ed i s a d v 姐t a g c so fe x i s t i n gg e n c t i ca i g o r i t t l i i l 肌dt h cc h 啪d e f so ft s p n l ce s s a yb r o u g i l tf o n ht h r e ei m p r o v c dh y b d dg e n e t i c 舢g 耐t h m ( h g a ) 1 if i r s tp u tf o r w a r dh g ai ，i nw h i c ha d o p t e dp m b a b i l i t yg r c e d ym e t h o dp r o d u c e do r i g i n a ip o p u l a t i o i ss u p e r i o rt ot h er a n d o m l yp r o d u c e do r i 百n a lp o p u l a t i 衄，b u ti n f e t i o rt ot h ef e e d ym e t h o d o nt h eo t h e rh a n d ，i t sv a r i e t yp r e c e d e s 乎e e d ym e t h o d ，a n dt h eo v e r a i ll e n 磬h0 ft l l ep m d u c e do r i 舀n a lp o p u i a t i o nr a d o mp a t hf o l l o w sn o m a ld i s 胁u t i o n w eo b t a i l l e dt h ch g aib yc o m b i i l i n gt h ep r o b a b i l i t yg r e e d ym c t h o dw i t he d g er e c o m b i i l ec s s 叩e m t o r 卸di n s p 试n gm u t a t i o no p e r a t o r t h e n ，i no r d e rt of u n h e ri m p r o v ec h a m c t e ra n dg u a r 卸t e c 百o b a lc o n v e r g e n c co fh g ai ，h g al ia p p l y sa m e n d m e n t c i r c l em g o r i t h ma n dm a x c o n c e s s i o n a l s t a 印a t e da l g c b 扭，n o to i l l ya v o i d st h es e l e c t i o np r o b l e mo ft h et e r i n i n a t e de v o l m i o na l g e b m ，b u t铲e a t l yi m p f o v c dt h ec o n v e r g e n c es p e e d ，s o 髂t 0m a l 【et h ea l g o r i t h mm o r es t a b l e a tt h cs 锄et i n l e ，t h ea d o p t i o fe l i t i s ts 眦e g y 卸df a t h e 础印r i n gc o m b i n e ds e l c c t i s t f a t e g y ，a n dr a n d o m 血c t o rc o n t m l sp a r a m c t e 墙口j nh g a ，g u a r a n t e e st h e9 1 0 b a lc o n v e r g c n c co fa l g o r i t h mi nt h c o r y |f i n a l l y t h ei n 仃o d u c l i 蛆o ft h et h r - m e 姐n c c p to fm u n i 柚a l y s i si nh g a d y n 锄i c a l l ya d j u s t st l l ec o n t r o lp 盯a m c t e ro ft h eg e n c t i ca 培o r i t h m ，s o 勰t oo v e r c o m ct h ep r c - m a t i l mp h e n 咖e n 凹c a 璐e di nt h cp r o c 骼so fg c n c t i cc v 0 1 u t i o nc o n 仃o l l e db yt h cs t e a d y 鼬lp 砌种e r i m p f o v c dt h es e a r c h i n ge f f i d c n c y 弛dc 印a b i m yo ft h ea l g o r ! i t h m ( 3 ) t h ee s s a y 船a l y z e d 卸dt e s t e d 也cc a p a b i l i t yo ft l l ea l g o r i t h mb yc o m p u t e rs i m u l a t i n gt h et h r e eh g lk e yw o r d s ：g e n c t i ca i g o r i t h m ，t r a v e l i n gs a l e s m 蛆p r o b l e m ，h y 雠dg c t i ca 1 9 0 r i t h m ，n d e t e m i l l i s t i cp o l y n o m i a lc o m p l e t e s sm论支缴纠佳声明本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表的成果。本声明的法律责任由本人承担。燃糍一辅一肿细论吏知识产仅仅属声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为长安大学。( 保密的论文在解密后应遵守此规定)谢一：舐辅导师签名：7 孔$ ，蒯年f 月形日d6 年r 月彤日第一章绪论近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透和相互促进，而遗传算法是近年来计算机科学、信息科学及人工智能领域研究的一个“热点州小帅1 。它是由美国学者h o l l a n d 提出的一种基于达尔文生物进化论及门德尔基因遗传理论的仿生学的概率性迭代搜索算法。广泛用于解决传统方法难于求解的复杂问题，如组合优化、模式识别、图像处理等复杂问题，能得到令人满意的解。近年来，遗传算法在解决连续变量的函数最优化问题时表现出的鲁棒性、全局性、并行性使其成为目前应用广泛的一种智能优化算法。1 1选题依据遗传算法( g e n e t i ca l g o r i t h m _ _ g a ) 正是以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法“3 它借鉴生物界自然选择和自然遗传机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的最优解。1 9 7 5 年，由美国密歇根大学( u n i v e r s i t yo fm i c h i g a n ) 的心理学教授、电子工程学与计算机科学教授j o h n h h o l l a n d 和他的同事与学生共同研究了具有开创意义的遗传算法理论和方法。其主要特点是采用群体搜索技术和在群体中个体间进行信息交换，利用简单的编码技术和繁殖机制来表现复杂的现象，不需要求导或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。遗传算法目前己在优化、机器学习、并行处理等领域得到了越来越广泛的应用。在组合优化领域内，随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。典型的n p 问题就是很好的例子对于这类复杂问题，人们已经意识到应把精力放在寻求其满意解上，而遗传算法则是寻求这种满意解的最佳工具之一因遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛的应用于很多学科特别是近年来在问题求解、优化与搜索、机器学习、智能控制、模式识别和人工生命等领域取得了许多令人鼓舞的成就t s p ( t r a v e l i l l gs a l e s m 姐p r o b i 锄) 问题是十九世纪初爱尔兰的数学家w i u i a mr o w 柚h 锄i l t o n 和英国数学家髓o m 鹊p 缸y n 昏o nk i r l 觚提出的，t s p 问题是著名的n p 完全难题，也是组合优化、计算机科学界经典的问题之一它在广泛的应用于运输、生产、国防、生物、计算机等领域以外，还为离散优化问题中各类算法提供了思想方法平台例如：印刷电路板的钻孔路线方案，连锁店的货物配送路线，数控机床的运作等问题，经过简单处理，均可建模为b p 问题，因而对倦p 寻找出实际而又有效的算法，就具有重要的理论意义，同时也具有重要的实际应用价值。再者，作为遗传算法的应用实例，研究求解t s p 问题的遗传算法，对促进遗传算法本身的发展也有着重要的意义。1 2 计算的复杂性理论当今社会，计算机在人们的日常生活中扮演的角色越来越重要，人们越来越多的依赖于计算机，因此对计算机的期望值也越来越高。然而，并不是所有的问题的解决都可以通过计算机完成。一是对于那些不确定的非计算机任务，根本不可能用计算机解决( 或者说目前的计算机还不具备这样的功能) 。因为计算机仅能执行算法，即只能准确地和一般地理解一系列的指令，此指令序列是用于求解严格确定的可计算型问题。二是对有些问题，虽然原则上存在一种算法可求解其任一实例，但因该算法需要过长的时间或过大的存储空间而使它变得完全无用。另一方面，对于绝大多数问题，我们常常会遇到这样的情形：求解某一问题的不同算法在时间、空间要求上相差很大。即使同一算法，当其用来求解问题的不同实例时，其性能表现差异也较大。由于实际问题的千变万化，不仅对不同问题往往要设计不同的算法，同时又想用同一算法去尽可能多地求解不同类型的问题。那么，如何解释这些错综复杂、多种多样的现象呢? 能否给出一个一般的划分与衡量标准，以区分不同问题的难易程度、度量不同算法的有效性之间的差异呢?广义地讲，一个算法的有效性可以用执行该算法所需要的各种计算资源的量来度量。最典型、也是最主要的两个资源就是所需的运行时间和内存空间。不过，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间需求常常是决定某一算法在实际中是否真正有用和有效的决定性因素。因此，在复杂性研究2中，衡量一个算法的效果，最广泛采用的标准是在产生最终答案前它所花费的时间，并常称复杂性为时间复杂度。实际上，一般没有必要精确的计算出算法的时间复杂度，只需大致计算出相应的数量级( o r d e r ) 。例如，对数组排序的各种简单算法的时间复杂度为d m 2 ) 数量级的，求具有n 个元素集合的所有子集的算法的时间复杂度为d ( 2 4 ) 数量级，用枚举法解h 个城市t s p 的算法的时间复杂度数量级为0 ( n ! ) 。下表1 1 是在假设所用计算机每秒可以执行1 0 亿次运算的前提下，对不同的时间复杂度函数所耗费时间作的比较。表1 1 不同的时间复杂度函数所耗费时间的比较时间复杂度输入量函数1 02 03 04 01 0 0 21 0 0 n s4 1 ) o n s9 0 0 n s1 6 “s1 0 “sz1 0 2 4 s1 0 4 8 6 m s1 0 7 3 7 s1 8 3 2 5 2 m j n4 0 世纪n13 6 2 踞m s7 7 1 4 7 年8 4 1 扩2 世纪2 6 1 0 ”世纪3 0 1 一”世纪我们知道对输入规模为_ 1 1 个城市t s p ，找到最优解的时间复杂度数量级为d ! ) ，从表1 1 可以看出：当n 比较大时，耗费的时间已经是个天文数字因此，对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解有的最优化问题可以由许多方法加以解决，人们需要根据求得最优解的效率对它们进行分类；也有的最优化问题可能根本难以解决，因而不存在有效地寻求最优解的方法。计算复杂性理论就是用于研究算法有效性和问题难度的手段。以下是几个重要的复杂性分类：定义1 1 ：p 问题与n p 问题。凡是在多项式复杂程度内可以求出最优解的问题，称为p a p 0 l y n o m i a l ) 问题，其它的则是n p ( n - p o l y n o m i a l ) 问题在算法问题上，假如一个问题是p 问题，我们通常认为它是“简单的”，对于一个n p 问题，通常认为它是“复杂的”经过研究，人们发现一个更为令人惊奇的性质：这些n p 问题都可以在多项式3时间内相互进行转化【5 l 【1 1 】1 1 2 1 。即假如某一个n p 问题存在多项式时间的解法，那么所有的n p 问题都可以在多项式时间内求得问题的最优解有许多问题，例如旅行商问题、m 1 背包问题、汉密尔顿环问题等，被认为是无法在多项式时间被求解的，而且己经证明它们可以在多项式的时间内相互转化，因此把他们称为n p c 问题，即n p 完全问题。定义1 2 ：n p c 问题。假如有一个问题，可以经过多项式计算时间的转化，变为求解一个已被证明的n p c 问题；另外，存在一个已被证明的n p c 问题，经过多项式计算时间的转化，可以变为求解该问题。那么，这个问题就成为n p c问题。t s p 问题是n p c 中有代表性的问题，与其他n p c 问题具有等价性，若在t s p的求解当中取得突破，则大量n p c 问题的求解方法就可以迎刃而解。由于n p c问题在现有的数学知识和计算机水平情况下找不到确定型的多项式时间算法，因此，近年来，对n p c 问题的研究逐渐向两个方向演化。一个是探求在多项式的计算时间内，求得具有上确界的解的算法。另一个方法则是，探索启发式的搜索方法。相对来说，前一类方法更具理论意义，后一类方法显得更具实践价值。而且，启发式搜索方法已经应用在许多实际问题上并取得了令人满意的结果。1 3 旅行商问题的应用t s p 广泛的应用于运输、生产、国防、生物、计算机应用等领域以外，还为离散优化中其他各类算法提供了思想方法平台，例如：印刷电路板的钻孔路线方案，连锁店的货物配送路线，数控机床的运作等问题，经过简单处理，均可建模为t s p 问题，因而对t s p 寻找出有效的启发式算法，就具有重要的理论意义，同时也具有重要的实际应用价值。t s p 很自然的作为大量的运输和后勤应用的一个子问题提出。例如，在小区内如何安排校车路线接送学生的问题，因为它对m e r r i l lf 1 0 0 d ( 二十世纪四十年代初一位研究t s p 的先驱者) 的研究提供了源动力，所以这个运输应用对t s p有着重要的历史意义。从1 9 4 0 年开始t s p 问题的第二个应用包括从某地运输农耕设备到另一个地方去检测土壤，这吸引了孟加拉的p c m a h a l a n o b i s 和爱荷华州r j j e s s e n 的数学研究更多的新近的应用包括电报公司中呼叫服务的时序4安排，货舱中栈式起重机的路线安排，收邮包的卡车行车路线安排等等。虽然运输问题是t s p 最自然的应用，但由于其模型的简单性，使得t s p 在其它领域都有着有趣的应用。例如如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。t s p 在减少费用上就扮演了一个非常重要的角色。当前，半导体厂家使用一种主要用计算t s p 的程序代码c o n c o r d e 中链式l i n k e r n i g h a n 启发式算法来优化整个电路的扫描链路，用来检测的扫描链路被包含在一个芯片中它可以最小化时间或者能量的消耗。另外，t s p 还应用于如基因工程中d n a 序列的计算，以及网络中q o s 组播路由问题等其他方面的问题。1 s p 问题具有广泛的应用背景，因此有效的解决这个被归入2 1 世纪的科学难题，在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。这就是本文写作的意义所在。：1 4 本文的内容安排与主要创新点近年来，遗传算法在许多领域都得到了广泛的应用本文在对大量的相关文献资料进行研究的基础上，针对现有的遗传算法的不足和t s p 本身的特点，提出了三种改进的混合算法。本文内容安排如下：第一章简单介绍了该论文的选题依据、计算的复杂性理论以及其具有的重要理论意义和实际应用价值。第二章从旅行商问题的概述出发，介绍了t s p 的数学描述与分类，在原有的基础上，对t s p 作了更细致的分类，综述了旅行商问题c r s p ) 在近几十年的研究分支以及算法进展与分类第三章介绍了遗传算法的基本概念、原理、步骤及意义，在原有的基础上，将遗传算法的一些操作过程用数学形式来表示，使其变得简单而又公式化最后叙述了遗传算法所依赖的基本遗传操作的基本机理，为以后各章研究的理论打下基础。第四章介绍了遗传算法在求解t s p 问题的基本原理及实现方法对于遗传算法运行性能有重要影响的一些参数进行了分析讨论，而且用基本遗传算法对种群规模为2 0 和3 0 的弼p 问题分别进行计算机模拟仿真，分析讨论了基本遗传5算法( s g a ) 在求解t s p 中出现的不足，为下一章的算法改进打下基础。第五章针对现有的遗传算法的不足和t s p 本身的特点，提出了三种改进的混合遗传算法( h y 晡dg 印c t i c 舢9 0 r ! i 吐姐，简记为h g a ) 。本文的主要创新之处有以下几点：( 1 ) 在原有的基础上，对鸭p 进行了更细致的分类并将遗传算法的一些主要操作过程用数学形式来描述，使其变得简单而又公式化。( 2 ) 提出了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，而且生成的初始种群的随机路径的总长度服从正态分布。( 3 ) 应用改良圈算法及最大容许停滞代数，不仅避免了s g a 中终止进化代数的选取问题，而且大大加快了算法的收敛速度，使算法具有很好的鲁棒性。( 4 ) 采取杰出者记录与“父子混合”选择策略以及随机因素控制参数口，使算法从理论上保证了全局收敛性。( 5 ) 引入多元回归分析中的三均值的概念对遗传算法的控制参数进行动态调整，从而克服用不变的控制参数来控制遗传进化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。62 1t s p 概述第二章t 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 ) 问题是十九世纪初爱尔兰的数学家w 订1 ia i i ir o w a nh a i i l i l t o n 和英国数学家t h o m a sp e n y n g t o nk i r k m a n 提出的，通常被描述为：对给定城市交通网络，如何为一个推销商选择一条路线，从网络的某一点( 驻地) 出发，经过每一个结点后回到出发点，使得总行程最短。t s p问题是著名的n p 完全难题，也是组合优化、计算机科学界经典的问题之一它在广泛的应用于运输、生产、国防、生物、计算机等领域以外，还为离散优化中各类算法提供了思想方法平台，因而对旅行商问题( t s p ) 求解方法的研究具有重要的实际价值。标准的t s p 在图论的意义就是所谓的最小h 枷i l t o n 圈问题。由于其在许多领域都有着广泛的应用，因而寻找其实际而又有效的算法显得颇为重要，遗憾的是，计算复杂性理论给予我们的结论是：这种可能性尚属未知。t s p 在理论上已归结为所谓的n p - 完各问题类，即非确定性多项式完备问题。关于这类十分困难的问题，现在所知道的仅仅是：任何n p 一完备问题都不能用已知的多项式算法来解决；用多项式算法去研究t s p 问题起于五十年代，如线性规划算法、动态规划算法、分枝定界法这些算法虽然对一些小规模的t s p 问题可精确求解，但计算的复杂度与城市的数目n 成指数增长。在大规模的问题上，这些精确算法显得无能为力，而且容易产生组合爆炸，因而人们退而寻求非尽善尽美的所谓启发式算法( 近似算法) ，来处理各种实际问题七十年代和八十年代是启发式算法的全盛时期，但由于绝大多数启发式算法都是按某种确定性的搜索规则来运行，想要改进所得解的可能性极小因此，从八十年代后期一直到九十年代，一些来i 刍其它学科的新一代求解方法相继出现，在组合优化问题的求解中取得相当的成功和一系列成果。如h o p f i e l d 和t a n k 提出用神经网络联想记忆技术求解t s p ，1 9 8 3年k i r k p a t r i c k 等首先提出了源于固体物理的模拟退火( s i 哪! a t e da n n e a l i n g )算法求解复杂的组合优化问题，1 9 8 7 年g r e n f e n s t e t t e 等提出的源于生物学的遗传算法( g e n e t i ca 1 9 0 r i t l m ) 求解t s p 问题，以及近几年来问世的源于昆虫王国的蚂蚁算法( a n ta 1 9 0 r “h m ) 我国的许多学者研究中国城市的t s p 问题，7基本上都采用h o p f i e l d 神经网络求解。尽管t s p 仍未找到最优解，但是求解它的算法逐渐改进。2 0 0 0 年，马良总结、归纳出1 9 5 4 年到1 9 9 6 年国内外近几十年求解t s p 的算法，可分为两类：一类是精确算法如线性规划、动态规划、分枝定界法等：另一类是近似算法( 启发式算法) ，如插入算法、i 卜_ o p t 算法、神经网络算法、模拟退火算法、遗传算法、蚂蚁算法等。目前，对于求解t s p 问题，国内外都有相当好的进展，2 0 0 0 年，周培德用点集凸壳的多项式时间算法解决了3 1 个顶点的中国货郎担问题。1 9 9 8 年，美国加利弗利亚大学d a ng u s f i l e d 根据出度、入度均为的2 的有向图g 中有一条h a l n i l t o n 路的这一特性，提出了用g r e e d y 算法求解出度、入度均为2 的t s p 。2 0 0 0 年，澳大利亚v l a d i m i rg d e i n e k o 证明了距离满足d e m i d e n k o 矩阵时，m a x t s p ( 指遍历所有城市的最大权h 锄i l t o n 圈) 是n p - 难题，而之前已证t s p 在此条件下是多项式时间可解的。几十年来对于求解t s p 问题出现了很多传统方法，其中有精确算法如线性规划方法、动态规划方法，分支定界方法；近似优化算法有插入法、最近邻算法、c l a r l ( w r i g h t 算法、生成树法、c h r i s t o f i d e s 算法、r o p t 算法、混合算法、概率算法等。近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法、遗传算法、模拟退火算法等。时至今日，人们已经发现有许多问题本质上都可归结为一个t s p 或是将其作为一个子问题来处理，但要想真正有效的求解，目前仍然是一件很困难的事。而由t s p 引伸出来的一些扩展问题，如瓶颈问题、多目标问题等，却由于t s p 本身的难度而一直少人问津。2 2t s p 的数学描述与分类2 2 1t s p 的数学描述旅行商问题c r s p ) ，也称货郎问题，有两种提法i 廿】。一种鸭p 的简单描述是：一名商人欲到n 个城市推销商品，每两个城市弭口，之间的距离为氏，如何选择一条路径使得商人每个城市走一遍回到起点后，所走的路径最短。其数学模型为在加权图上求一个h 锄m 圈c ，使得8职c ) - 荟心) 兰州各恤砸砌圈的栅上述t s p 经典的定义比实际问题就要狭隘了，因为实际上旅行商可以在一段路程上往返，往往反而节省了整个巡回的总费用( 大都用距离来表示) 。此外，如果有图2 1 所示的t s p 用上述经典的定义是找不到解的，但在实际中的旅行商仍可选择一条最优路线，只不过顶点3 要被访问两次。图2 1于是旅行商的另一种提法就是商人从某城市出发，遍历各个城市至少一次后返回原出发点，设计出一条路线，使总路程最短此时，其数学模型是在加权图g ，层) 上求一个生成回路c ，使得w ( c ) = w ( c ) - l i l i 各个生成回路的权) 露这个c 叫做理想回路。从算法理论上讲，这两种提法的难度是相当的。2 2 2t s p 的分类从问题对应到图的类型，t s p 通常有两种基本的分类：( 1 ) 任意两个城市之间来往的路径均相等或可以不相等；就可以归结为无向图或有向图问题( 2 ) 任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单行路径；这种类型可以归结为完全图或者非完全图问题将上述两种情况加以组合，便可得到以下四种t s p 的路径关系：( a ) 完全有向图；( b ) 完全无向图；( c ) 非完全有向图；( d ) 非完全无向图。从问题本身的限制条件的强弱，t s p 主要有三类，第一类不作任何限制，只给出距离矩阵，求最小回路：第二类要求距离间要满足三角不等式( 对于一个旅9枣行商问题中的任意三个城市p ，q ，r ，假如从p 经过q 到达r 的旅行费用不低于从p 到r 的旅行费用，那么称这个旅行商问题满足三角不等性) ，满足三角不等性的旅行商问题，具有许多优良的性质，可以大大方便计算但另一方面，已经证明，满足三角不等性的对称旅行商问题，也是n p 完全问题。对于满足三角不等性的对称旅行商问题，可以在多项式的计算时间内求得近似解。第三类就是定义在欧氏平面上的髑p ，即e u d i dt s p ，它以欧氏平面上的坐标和欧氏距离来给出城市问的坐标和城市间的距离。从问题的多项式可解性上，t s p 可分为两类。一类是目前已知有多项式的时间算法可解的，比如其距离矩阵满足d e m i d e n i 【o 条件、k a l m a l l s o n 条件或者s 叩n i c k 条件等；另一类是目前尚未发现有多项式时间算法可解的，而研究热点就是如何寻找更多的多项式时间可解的情形，使得第一类集合扩大，第二类缩小。除此之外，鸭p 的研究经过了几十年的发展，还引申出其它扩展形式，比如多旅行商问题( m u l t i s “啪a n p r o b l 锄) ，它是由多人完成环游的t s e 该问题可转化为等价的单人问题求解。还有多目标旅行商问题( m u l t i 0 b i e c t i v ct s p ) ，该问题在每条边都有m 个权值，则使得h a m m o n 回路上相应的m 个目标值都尽可能小的解就称为多目标t s p 的有效解，如实际问题中要考虑的路程最短、时间最小、费用最省、风险最小等多方面的因素。2 3 前人的工作目前针对t s p 的算法主要分为两类：精确算法和启发式算法( 近似算法) 。2 3 1 精确算法精确算法能保证完全搜索问题的整个解空间，从而找到最优解，但需要消耗d o ! ) 级的运算时间；有些精确算法虽然运用一些精巧的技术来减少搜索空间，但其本质上还是进行全局搜索，并没有降低运算时间复杂度。( 1 ) 线性规划方法求解t s p 的最早的一种算法，主要是采用整数规划中的割平面法，即先求解模型中由前两个约束构成的松弛l p 问题，然后通过增加不等式约束产生割平面，逐渐收敛到最优解。1 0d z t z i g 等人早在1 9 5 4 年就求过n - 4 2 的t s p 最优解，7 0 年代中期对于t s p多面体理论的研究，产生了一些比较有效的不等式约束，如子回路消去不等式( s u b t o u re l i m i n a t i o n ) 、梳子不等式( c o m bi n e q u a l i t i e s ) 等。由于该方法在寻找割平面时常常凭借经验，因此，后来很少作为一般方法使用。( 2 ) 动态规划方法记s 为集合 2 ，3 ，n 的子集，k s ，c ( s ，k ) 为从l 出发遍历s 中的点并终止在k 的最优行程。当- 1 时，c ( k ) ，k ) = 丸，( k = 2 ，3 n ) ，当吲1 时，根据最优性原理，可将t s p 的动态规划方程写成c ，七) 一m i n c ( s 一 七) ，j ) + d 业l j s 一 七) 再按方程规划可迭代求解。j由于动态规划算法的时间复杂度为0 0 2 z ) ，空间复杂度为d ( n z ) ，故一般除了很小规模的问题外，几乎不予采用。( 3 ) 分支定界算法分支定界算法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制搜索进程使之能向着空间状态树上有最优解的分支推进，以便尽快找出一个最优解。该方法的关键在于约束界限的选取，不同的约束界限可形成不同的分支定界法。但是分支定界算法对于解大规模问题不是十分有效。2 3 2 启发式算法启发式算法不能保证搜索问题的全部解空间，所以也不能保证能够搜到最优解，甚至在某些实例上连解都得不到，但它们与精确算法相比却具有运算时问上的优势，即它们的运算时间复杂度都只是多项式，并不会随着输入规模的扩大而产生“组合爆炸”这类算法采用的是启发式策略来指导搜索，普遍比精确算法要快。对t s p 的启发式算法的研究是本文的重点。对于启发式算法，算法的好坏常用。s 来衡量，c 为启发式算法所得到的总行程，c 为最优总行程，f 为最坏情况下的近似解与最优总行程之比的上界值这类算法有：1 11 插入算法插入型算法可按插入规则的不同而分为若干类，其一般思想为：步骤( 1 ) 通过某种插入方式选择插入边( f ，j ) 和插入点七，将七插入f 和，之间，形成 ，f ，七，j ，” ；步骤( 2 ) 依次进行直至形成回路解。适用范围：无向图的t s p( 1 ) 最近插入法：最坏情况：= 2 ：时间复杂度：0 0 2 ) 。( 2 ) 最小插入法：最坏情况：= 2 ：时间复杂度：d 0 2 l g 以) 。( 3 ) 任意插入法：最坏情况：= 2 1 9 n + o 1 6 ；时间复杂度：d 0 2 ) 。( 4 ) 最远插入法：最坏情况：= 2 1 9 n + o 1 6 ；时间复杂度：d 0 2 ) ( 5 ) 凸核插入法：最坏情况：未知；时间复杂度：d 0 2 l g 咒) 。2 最近邻算法步骤( 1 ) 任取一出发点；步骤( 2 ) 依次取最近的点加入当前解中直至形成回路解。适用范围：无向图的t s p最坏情况：= ( 1 9 n + 1 ) 2 ；时间复杂度：d 2 ) 。3 c l a r k w r i g h t 算法步骤( 1 ) 任取一出发点p ，计算吒- 厶+ 如+ 嘞；步骤( 2 ) 将各由大到小排列；步骤( 3 ) 将排好后的各( f ，j ) 依次适当联接，形成回路解。适用范围：无向图的t s p最坏情况：一2 1 9 彳+ 1 时间复杂度：d 0 2 ) 4 双生成树算法步骤( 1 ) 首先求出最小生成树。步骤( 2 ) 将树中各边都添一重复边并求出其e u l e r 回路；步骤( 3 ) 在e u i e r 回路点序列中去除重复点，形成回路解。适用范围：无向图的t s p最坏情况：- 2 ：时间复杂度：d 0 2 ) 。5 c h r i s t o f i d e s 算法步骤( 1 ) 首先求出最小生成树；步骤( 2 ) 对树中所有奇顶点求最小权匹配问题；步骤( 3 ) 将匹配边添入生成树并求出其e u l e r 回路；步骤( 4 ) 在e u l e r 回路点序列中去除重复点，形成回路解。适用范围：无向图的t s p最坏情况e = 2 3 ：时间复杂度：d 0 2 ) 。6 r o p t 算法，该方法是一种局部改进搜素算法，由l i n 等人( 1 9 6 5 ) 提出，其思想是对给定的初始回路，通过每次交换r 条边来改进当前解。对不同的r ，根据大量计算发现，3 一o p t 法比2 一o p t 法好，而4 - o p t ，5 一o p t 等并不比3 一o p t 优，况且r 越大，运算时间越长所以一般采用3 一o p t 法。适用范围：无向图的t s p最坏情况：2 2 0 28 ，5 ) ：时间复杂度：d 0 7 ) 7 模拟退火算法( s i 叫1 a t e da n n e a l i n ga l g o r i t h i i i )模拟退火算法是基于m e n t ec a r l o 迭代求解策略的一种随机寻优算法。其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优解。模拟退火算法得到解的好坏与初始状态，温度函数等都有一定的联系，降温较快的效果不一定很好，效果好的往往降温过程又及其漫长。但由于该方法适用范围广，并可人为控制迭代次数，反复求解，因此具有很强的实用性。8 禁忌搜索方法( t s )禁忌搜索方法是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以实现全局优化。9 遗传算法( g e n e t i ca l g o r i t h i l l )这是一种来自生物进化理论中“自然选择，适者生存”原则的搜索算法，它基于生物学的自然选择原理和自然遗传机制模拟生命