（运筹学与控制论专业论文）求解旅行商问题的进化算法.pdf

摘要 进化算法是人们从大自然的生物进化过程所得到的灵感中发展起来的一种现 代优化方法，它作为一种新型的、模拟生物进化过程的随机化搜索、优化方法， 具有全局优化，隐并行性，鲁棒性强，操作简单等特点，近十几年来在组合优化 领域得到了相当广泛的应用，并己在解决诸多典型的组合优化问题( 如旅行商问题) 中显示了良好的性能和效果。 首先，针对一类特殊的大规模旅行商问题，比如说城市可以分为若干组、而且 各组内城市之间的距离较小的问题，本文提出了一种基于聚类以及局部搜索技术 的新进化策略来进行求解，并且证明了该算法的全局收敛性。 其次，针对对称型的旅行商问题，本文设计了一个新的进化算法进行求解，该 算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解 的质量，同时被证明是全局收敛的。 最后，数值模拟实验结果表明，本文所提出的这两个算法都是有效的。 关键词：进化算法旅行商问题局部搜索全局收敛 a b s t r a c t e v o l u t i o n a r ya l g o r i t h m sa r en e wk i n d so fm o d e mo p t i m i z a t i o na l g o r i t h m sw h i c h a l ei n s p i r e db yt h ep r i n c i p l eo fn a t u r ee v o l u t i o n a sn e wk i n d so fr a n d o ms e a r c h a l g o r i t h m s ，t 1 1 e yh a v es o m ea d v a n t a g e s s u c ha s g l o b a l s e a r c ha b i l i t y , i m p l i c i t p a r a l l e l i s m ，r o b u s t n e s s ，s i m p l eo p e r a t i o na n ds oo i l i nt h er e c e n td e c a d e s ，e v o l u t i o n a r y a l g o r i t h m sh a v eaw i d er a n g eo fa p p l i c a t i o n si nt h ea r e ao fc o m b i n a t o r i a lo p t i m i z a t i o n t h e yh a v e b e e nu s e dt os o l v em a n yc l a s s i c a lc 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 ( e g t r a v e l i n gs a l e s m a np r o b l e m ) a n d s h o wt h e i rg o o d p e r f o r m a n c ea n de f f e c t i v e n e s s f i r s t l y , an e we v o l u t i o ns t r a t e g yb a s e do nc l u s t e r i n ga n dl o c a ls e a r c hs c h e m ei s p r o p o s e df o rs o m ek i n do fl a r g e s c a l et r a v e l i n gs a l e s m a np r o b l e m si nw h i c ht h ec i t i e s c a nb ec l a s s i f i e di n t os e v e r a lg r o u p sa n di ne a c hg r o u pt h ec i t i e sc r o w dt o g e t h e r t h i s a l g o r i t h mi st h e np r o v e dt oc o n v e r g et ot h eg l o b a lo p t i m a ls o l u t i o nw i t hp r o b a b i l i t y1 s e c o n d l y ，an e we v o l u t i o n a r ya l g o r i t h mi sp r o p o s e dt o d e a lw i t ht h es y m m e t r i c t r a v e l i n gs a l e s m a np r o b l e m s i nt h i sn e wa l g o r i t h m , an e w c r o s s o v a ro p e r a t o ra n dan e w m u t a t i o no p e r a t o ra r ed e s i g n e dt og e n e r a t eo f f s p r i n g t h e nal o c a ls e a r c hs c h e m ei s u s e dt oi m p r o v et h es o l u t i o n s a l s o t h eg l o b a lc o n v e r g e n c ew i t l lp r o b a b i l i t y1o ft h e p r o p o s e da l g o r i t h mi sp r o v e d f i n a l l y , t h e s i m u l a t i o nr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h et w op r o p o s e d a l g o r i t h m s k e y w o r d s ：e v o l u t i o n a r ya l g o r i t h m st r a v e l i n gs a l e s m a np r o b l e m s l o c a ls e a r c hg l o b a lc o n v e r g e n c e 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：窒i 臣堡日期兰! ! ! ! 竺 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的论文 在解密后遵守此规定) 本人签名：重丝笠 导师签名： 诌； 日期丝! ! ：! ：生 e t 期丛! 厶垡 第一章绪论 第一章绪论 1 1 引言 旅行商问题( 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 ) 是一个相当有名的组合 优化【1 】问题，已经吸引了许许多多的数学家和计算机科学家们的注意。该问题可以 简单的叙述如下：如果一个旅行商人想访问”个城市( 城市i 与城市，之间的费用是 e ，) ，他从其中一个城市出发，每个城市只能访问一次且仅一次，然后回到出发城 市，那么他应该选择哪一条线路( 回路) 而使得他的花费最少? 对于一个具有一个城 市的t s p ，它有伽一1 ) ! 2 条回路。当胛很大( 即当问题的规模很大) 的时候，这将是 一个天文数字，在目前的计算条件下，任何暴力求解的方法( 即枚举法) 都将无效。我 们该怎么办呢? 人们已经提出了许多求解t s p 的算法。这些算法基本可以分为两类：精确算法 与近似算法( 或者启发式算法) 。然而，求解这一问题的普遍适用的有效算法尚未出 现。其原因在于，从计算复杂性的角度来看，t s p 是一个n p 完全问题 2 1 ，而到目 前为止，人们还没有找到解决这类问题的有效算法，即多项式时间算法。进化算 法的出现为解决这类问题带来了曙光。旅行商问题属于组合优化问题，而组合优 化问题是进化算法基本的研究和应用领域之一。所谓组合优化是指在离散的、有 限的数学结构上，寻找一个满足给定约束条件并使其目标函数值达到最大或最小 的解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、 不连续的、多维的、有约束条件的、高度非线性的n p 完全问题，因此，精确地求 解组合优化问题的全局最优解，一般是不可能的。进化算法是人们从大自然的生 物进化过程所得到的灵感中发展起来的一种计算技术，它作为一种新型的、模拟 生物进化过程的随机化搜索、优化方法，具有全局优化，隐并行性，鲁棒性强， 操作简单等特点，近十几年来在组合优化领域得到了相当广泛的应用，并已在解 决诸多典型的组合优化问题中( 例如用遗传算法去求解旅行商问题) 显示了良好的 性能和效果。人们也已经开始应用进化算法来求解大规模的旅行商问题 3 , 4 , 5 1 ，并且 取得了很好的结果。因此，进化算法是解决这类问题的一个有效的工具。本文就 对进化算法在旅行商问题中的应用进行了研究。 1 2 进化算法的产生与发展 “物竞天择，适者生存”是达尔文进化论的核心。按照该理论，地球上的每 2求解旅行商问题的进化算法 一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐 发展成为高级、复杂的类型。各种生物要生存下去就必须进行生存斗争，包括同 一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗 争。具有较强生存能力的生物个体容易存活下来，并且有较多的机会产生后代； 具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。 二十世纪初，人们重新发现了孟德尔十九世纪七十年代的生物遗传学理论。 按照生物遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基 因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同 的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对 环境适应性强的后代。经过优胜劣汰的自然选择，适应度高的基因结构就得以保 存下来，从而逐渐形成了经典的遗传染色体理论，揭示了遗传和变异的基本规律。 现代遗传学则对基因的本质、功能、结构、突变和调控进行了深入的探讨，开辟 了遗传工程研究的新领域。在一定的环境影响下，生物物种通过自然选择、基因 交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。 大自然从来都是一个带给人们创造灵感的源泉。自然界的生物进化是一个不 断循环的过程。在这一过程中，生物群体不断地完善和发展。由此可见，生物进 化过程本质上就是一种优化过程。在计算机迅猛发展的时代，人们通过在计算机 上对生物进化过程中的繁殖、变异、竞争和选择这四种基本形式进行模拟，并在 实践中进行应用，创立了一种全新的优化计算技术一进化计算。最初，进化计 算( e v o l u t i o n a r yc o m p u t a t i o n , e c ) 包括三个分支：遗传算法( g e n e t i ca l g o r i t h m , g a ) 、 进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和进化策略( e v o l u t i o ns t r a t e g y , e s ) 。遗传 算法是由美国密歇根大学的j o h nh h o l l a n d 教授于1 9 7 5 年提出【6 】，进化规划是由 美国科学家l a w r e n c ej f o g e l 等人于1 9 6 6 年提出i _ ”，进化策略是由德国科学家i n g o r e c h e n b e r g 于1 9 7 3 年提出1 8 】o 后来，2 0 世纪9 0 年代初，在遗传算法的基础上又 形成了一个分支：遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 。这是由j k o z a 教授于 1 9 9 0 年提出的 9 1 。它们也可统称为进化算法( e v o l u t i o n a r ya l g o r i t h m , e a ) 。其共同 点都是借助生物进化的思想和原理来解决实际问题。在进化算法中，使用最普遍 又最具有代表性的是遗传算法【6 l o d 5 1 。目前，进化计算与人工神经网络、模糊系统 理论一起已形成了一个新的研究方向一计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) ”6 j 。 值得一提的是，近几年来，与计算智能相关的国际会议c i s ( c o m p u t a t i o n a l i n t e l l i g e n c ea n ds e c u r i t y ) 已经连续举办了三届( c i s 2 0 0 5 ，c i s 2 0 0 6 ，c i s 2 0 0 7 ) 。 2 0 世纪8 0 年代中期以来是遗传算法和进化计算的蓬勃发展时期。以遗传算法、 进化计算为主题的多个国际会议在世界各地定期召开。1 9 8 5 年，在美国卡耐基梅 隆大学召开了第一届遗传算法国际会议，即i c g a ( i n t e m a t i o n a lc o n f e r e n c eo n g e n e t i ca l g o r i t h m s ) 。这次会议是遗传算法发展的重要里程碑，此会以后每隔一年 第一章绪论 举行一次。其它类似的会议还有很多，比如i n t e r n a t i o n a lc o n f e r e n c eo ne v o l u t i o n a r y p r o g r a m m i n g ，i e e e i n t e r n a t i o n a lc o n f e r e n c eo ne v o l u t i o n a r y c o m p u t a t i o n , p p s n ( p a r a l l e l p r o b l e m s o l v i n g f r o m n a t u r e ) ，f o g a ( f o u n d a t i o n o fg e n e t i c a l g o r i t h m s ) 。每年夏季还在美国斯坦福大学召开有关遗传算法程序设计的国际会 议( t h e a n n u a l c o n f e r e n c e o f g e n e t i c p r o g r a m m i n g ) 。一些专门刊登进化算法的国际 专业杂志开始出现。1 9 9 3 年，美国m i t 出版社开始出版e v o l u t i o n a r yc o m p u t a t i o n 杂志( 由d ej o n g 担任主编) 。1 9 9 4 年，i e e e 神经网络委员会( i e e en e r u a ln e t w o r k c o u n c i l ) 出版了第一本“进化计算”专集；1 9 9 7 年，该委员会创办了i e e e t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 杂志( c ad a v i db f o g e l 任主编1 。这两本杂 志现在已经成为了进化算法这个领域的国际权威杂志。 我国有关遗传算法、进化计算的研究，从2 0 世纪9 0 年代以来一直处于不断 上升的时期，特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人 瞩目的成果。在国际刊物上发表的学术文章越来越多。关于遗传算法、进化计算 的专著陆续出现。1 9 9 5 年，刘勇、康立山出版了非数值并行计算( 第二册) 一遗 传算法；1 9 9 6 年，陈国良、王煦法等人出版了遗传算法及其应用；1 9 9 8 年， 潘正军、康立山等人出版了演化计算；1 9 9 9 年，周明、孙树栋出版了遗传算 法原理及其应用；2 0 0 2 年，王小平、曹立明出版了遗传算法一理论、应用与软 件实现，李敏强等人出版了遗传算法的基本理论与应用；2 0 0 3 年徐宗本等出 版了计算智能中的仿生学：理论与算法；2 0 0 4 年玄光男、程润伟等出版的遗 传算法与工程优化；等等。国内有关遗传算法的b b s 电子公告牌有国家智能中心 曙光站b b s n e i c a c c n 、北京大学阳光创意站b b s p k u e d u c n 、清华大学水木清华站 b b s n e t t s i n g h u a e d u c n 、西安交通大学兵马俑站b b s x a n e t e d u c n 等。 1 3 进化算法的应用 随着经济、科技和社会的不断发展，人们遇到的各种问题越来越复杂，迫切需 要寻找一种更好的求解方法。进化算法作为一种有效的全局搜索方法，从产生至 今不断扩展应用领域，比如工程设计【1 t 1 引，制造业【1 1 ，19 1 ，人工智削10 ，2 0 - 3 1 1 ，计算 机科学【1 9 3 2 1 ，生物工程1 3 3 】，自动控制瑚7 】，社会科学1 5 3 8 1 ，商业和金融等，同 时应用实践又促进了进化算法的发展和完善。比较成功的案例与应用领域如下： ( 1 ) 天然气管道的最优控制m 1 8 】 伊利诺斯大学的g o l d b e r g 采用遗传算法研究一个复杂结构输气管道系统的运 行控制问题。该系统模拟了从西南向东北输送天然气的输气管道系统。输气管道 由许多支线组成，每条支线上的送气量各不相同，仅有的控制手段就是用压缩机 来改变特定支线中的压力以及用阀门来调节储气罐进出气流的流量，而且管道气 4 求解旅行商问题的进化算法 压的实际变化极大地滞后于操纵阀门或压缩机的动作。g o l d b e r g 采用拟人控制器 经过遗传算法学习，建立了一套完备的规则知识层次体系，能够有效地实施管道 运行的实时控制，以及对管道被戳穿事故作出恰当的反映。 ( 2 ) 喷气式飞机涡轮机的设计【l l 】 通用电气公司和r e n s s e l a e r 综合技术学院的一组研究人员成功地将遗传算法用 到一种商业客机等使用的高函道比喷气式发动机的涡轮的设计之中。这种涡轮由 好几级静止的和旋转的叶扇组成，安装在近似圆筒形的函道内，是发动机开发计 划的核心部分。涡轮的设计涉及到至少1 0 0 个变量，每个变量的取值范围各不相 同，由此形成了具有1 0 3 8 7 以上个点的搜索空间。涡轮设计方案的“适应度”取决 于它满足一组限制的程度如何，这组限制有5 0 个左右，如内壁和外壁的形状，函 道内各点处燃气气流的压力、速度和扰动情况等。在一般情况下，一个工程师独 立工作并获得一个满意的设计要用大约几周时间。运行基于遗传算法的发动机模 拟软件和专家系统有助于引导设计人找出有意义的修改，工程师用这样的专家系 统，在不到一天的时间里就能完成一种设计。 ( 3 ) 旅行商问题 旅行商问题是经典的组合优化问题之一，已远远超出其本身的含义，成为了一 种衡量算法优劣的标准。t s p 是采用非标准编码遗传算法求解最成功的一例，用 旅行商人顺序经历的城市序号表示基因编码。由于使用标准交叉产生的后代可能 有重复或者丢失的基因而成为非可行解，故提出了非标准的交叉和变异方法【3 9 , 4 0 。 交叉主要采用重排序方法一部分匹配重排序( p m c ) 、顺序交叉( 0 ) ( ) 和循环交叉( c ) ( ) 等，变异主要采用位反转、对换、插入等方法。 ( 4 ) 作业调度问题( f l o w - s h o p0 1 s c h e d u l i n g ) 作业调度问题同样可以用遗传算法进行处理【1 5 ，4 1 , 4 2 4 3 1 ，比如c a r t w r i g h t 关于 化工厂生产计划的优化安排，s y s w e r d a 关于飞行支持设备调度问题，h i l l i a r d 关于 运输军队及其装备多目标通路的作业调度，g a b b e r t 关于铁路网络复杂运输调度等 问题，采用遗传算法均取得了明显效果。 ( 5 ) 遗传学习( g e n e t i el e a r n i n g ) 将遗传算法用于知识获取，构成以遗传算法为核心的机器学习系统，其中群体 由一组产生式规则组成。比较典型的是h o l l a n d 设计的用于序列决策学习的分类器 系纠1 0 1 ，以及机器人规划、模式识别、概念学习等 2 5 , 2 7 , 2 8 , 4 2 。 ( 6 ) 自动控制领域 遗传算法适用于求解复杂的参数辨识问题。m a c l a y 等人用遗传算法求解电车 模型参数辨识问题，取得了较好的结果i 删；k a r r 采用遗传算法设计自适应模糊逻 辑控制器，取得了显著的效果0 4 1 ；f r e e m a n 等人提出了应用遗传算法精调控制器中 的由人定义的模糊逻辑集合概念p 5 1 。另外，遗传算法在故障诊断1 4 5 4 6 】和机器人行 第一章绪论 走路径规划 2 5 , 4 7 , 4 8 】中的应用也取得了成功。 ( 7 ) 人工智能与计算机科学 遗传算法在人工智能能与计算机科学领域中的应用包括：数据挖掘与知识获取 4 9 - 5 1 】、数据库查询优化5 2 1 、人工神经网络结构与参数优化 2 0 - 2 3 , 5 3 - 5 6 、模式识别 5 0 , 5 7 , 5 8 1 、专家系统d 1 , 4 2 等。 ( 8 ) 社会与经济领域 遗传算法在早期就曾被应用于囚徒困境问题分析( p r i s o n e r sd i l e m m a p r o b l e m ) 1 4 1 1 ，b a u e r 对遗传算法在经济与投资中的应用进行了全面分析【3 8 1 。近年来， 商业、金融领域已经成为遗传算法应用的热点。遗传算法与现代计算机强大的运 算能力结合，使金融交易中瞬息万变的诸多因素能够为人所理解并能加以利用， 使交易者更多地依赖于计算机的速度。目前已经有许多基于遗传算法的软件包应 用金融系统和股票投资分析。 此外，很多专家学者将遗传算法应用于各自所从事的工程领域，比如v l s i 设 计、运输规划、设备布局、土木工程、生物工程等，对解决具体实践问题起到了 极大的促进作用。 1 4 本文的主要工作与结构安排 在这篇文章里，针对一类特殊的大规模旅行商问题，比如说城市可以分为若干， 组、且各组内城市之间的距离较小的问题，我们提出了一种基于聚类以及局部搜 索技术的新进化策略来进行求解，并且证明了该算法的收敛性。针对对称型的旅 行商问题，我们设计了一个新的进化算法进行求解，该算法使用了新的交叉算子 和变异算子以及一种局部搜索方法，同时被证明是全局收敛的。数值实验结果表 明，我们提出的这两种算法都是有效的。文章共分为五章，内容分别如下： 第一章：简单介绍了旅行商问题以及进化算法的产生与发展及其应用领域。 第二章：比较详细地叙述了旅行商问题，介绍了它的发展历史、定义、应用价 值、复杂性以及现有的求解算法等等。 第三章：比较详细地阐述了进化算法的内容，介绍了它的四大分支：遗传算法、 进化策略、进化规划、遗传程序设计，及其收敛性理论、设计时应遵循的原则和 步骤，还叙述了用进化算法求解旅行商问题的一些常用的编码方式、交叉算子和 变异算子等等。 第四章：针对一类特殊的大规模旅行商问题，提出了一种基于聚类以及局部搜 索技术的新进化策略来进行求解，并且证明了该算法的收敛性。 第五章：针对对称型的旅行商问题，设计了一个新的进化算法进行求解，并且 6 求解旅行商问题的进化算法 证明了该算法的收敛性。 第二章旅行商问题 7 第二章旅行商问题 2 1 旅行商问题的发展历史 旅行商问题，也称货郎担问题，是一个较古老的问题。其起源已经有些模糊 了。最早大概可以追溯到1 7 5 9 年e u l e r 提出的骑士旅行问题。十九世纪初，爱尔 兰数学家w i l l i a mr o w a nh a m 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 研究过 一些与旅行商问题相关的数学问题。他们的早期工作可参考著作g r a p ht h e o r y 1 7 3 6 - 1 9 3 6b yn l b i g g s ，e i cl l o y d ，a n d j w i l s o n , c l a r e n d o np r e s s ，o x f o r d , 1 9 7 6 二十世纪初，人们开始研究通用形式的旅行商问题。二十世纪二十年代，数 学家和经济学家k a r lm e n g e r 在维也纳向他的同事提出了这个问题。二十世纪三十 年代，旅行商问题出现在p r i n c e t o n 大学的数学圈子里，主要的推动者有h a s s l e r w h i t n e y 与m e r r i l lf l o o d 。二十世纪四十年代，统计学家( m a h a l a n o b i s ( 1 9 4 0 ) 。 j e s s e n ( 1 9 4 2 ) ，g o s h ( 1 9 4 8 ) 。m a r k s ( 1 9 4 8 ) ) 把它和农业应用联系在一起研究。美国 r a n d 公司也推动了这个问题的发展。最终，旅行商问题成为了组合优化问题中 的一个困难问题原型的典型代表。求解这种问题令人望而生畏：当问题规模变大 的时候，路径的数目将是个天文数字，逐一检查它们几乎是不可能的。在很长的 一段时间内，没有任何解决这个问题的好想法出现。 1 9 5 4 年，旅行商问题的求解终于获得了突破。g e o r g ed a n t i z i g ，r a yf u l k e r s o n 和s e l m e rj o h n s o n 提出了一个求解旅行商问题的算法并用它成功地解决了一个有 4 9 个城市的实例。这个规模在当时相当引人注目。此后，人们能解决的问题规模 越来越来。1 9 7 7 年，g r o e t s e h e l 找到了有1 2 0 个城市的旅行商问题的最优路径。1 9 8 7 年，p a d b e r g 与r i n a l d i 找到了规模为5 3 2 和2 3 9 2 的旅行商问题的最优路径； g r o e t s e h e l 与h o l l a n d 找到了规模为6 6 6 的旅行商问题的最优路径。a p p l e g a t e ，b i x b y , c h a v 6 t a l 和c o o k 于1 9 9 4 年解决了规模为7 3 9 7 的旅行商问题。此后，他们三个人 一起又解决了规模为1 3 5 0 9 和1 5 1 1 2 的旅行商问题，时间分别是1 9 9 8 年和2 0 0 1 年。2 0 0 4 年，一个具有2 4 9 7 8 个城市的旅行商问题的最优路径由a p p l e g a t e 。b i x b y , c h a v d t a l ，c o o k 和h e l s g a u n 找到。这是到目前为止精确找到最优解的最大规模的旅 行商问题。 旅行商问题吸引了越来越多的人对它进行研究。其中，有数学家，计算机科 学家，运筹学家，还有一些其它领域的研究者。然而，该问题是否存在一个有效 的通用的求解方法仍然是一个开放性的问题。事实上，旅行商问题的解决将意味 8 求解旅行商问题的进化算法 着p = n p 5 9 问题的解决。c l a ym a t h e m a t i c si n s t i t u t e 曾悬赏1 0 0 万美元来寻求这个问 题的解法，但没人拿到这个奖。 2 2 旅行商问题的定义 2 2 1 旅行商问题的描述及数学模型 旅行商问题( t s p ) 的文字描述可以表达如下：给定一组n 个城市和它们两两 之间的直达距离，找出一个闭合的回路，使得每个城市刚好经过一次且仅一次且 总的旅行距离最短。用数学的语言来说就是要寻求一条回路r = ( f ，r ：，t 。) ，使得 下列目标函数最小： n - 1 八r ) = d ( t 。，t s + 1 ) + d ( o ，t 1 ) f - l 上式中为城市号，取值为【l ，珂】，从而( ，1 t 2 ，) 就可以看作是关于1 的一个排列。 d ( ，t j ) 捌g t , 与f j 之间的距离。对于对称型t s p ，有d ( ，t j ) = d ( t j ，t ，) 。 用图论的语言可描述为：在一个赋权的完全图中，要找一个具有最小权值的 h a m i l t o n 圈。即令g = ( 以层) ，v = o ，d , j = o ，i , j v ，并且设 f l , 边( f ，_ ，) 在最优路径上 一1 0 ，其它 则t s p 的数学模型还可以写成如下的线性规划形式： m i n z = 或 s 1 = 1 f v = 1 j v 爿s i - 1 ，s v h l 时，根据最优 性原理，可将t s p 的动态规划方程写成c ( s ，七) = m i n ，西一 c ( s 一 ”， + 办) ，按 方程规划可迭代求解。由于动态规划算法的时间复杂度为o ( n 2 2 ”) ，空间复杂度为 o ( n 2 “) ，故一般除了很小规模的问题外，几乎不予采用。 4 分支定界算法 分支定界算法是一种应用范围很广的搜索算法，它通过有效的约束界限来控 制搜索进程使之能向着空间状态树上有最优解的分枝推进，以便尽快找出一个最 优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支 定界法。 ( 1 ) 以指派问题为界 通过求解相应的分派问题，得到t s p 的一个下界，以此进行分支定界搜索。 这是一种使用较多的分支定界法。 ( 2 ) 以匹配问题为界 通过求解相应的匹配问题，得到t s p 的一个下界，以此进行分支定界搜索。 该方法适用于对称型t s p 。 ( 3 ) 以最小1 树为界 通过求解相应的最小l 树问题，得到t s p 的一个下界，以此进行分支定界搜 索。 但是分支定界算法对于解大规模问题往往不是很有效。 2 5 1 2 近似算法 由于精确式算法所能求解的问题规模非常有限，实际中使用的往往都是多项 式时间的近似算法或启发式算法，算法的好坏用c c ss 来衡量，c 为近似算法 所得到的最小路径长度，c 为最优路径长度，占为最坏情况下，近似解与最优解 的路径长度之比所不超过的上界值。近似算法虽然不能保证找到最优解，但是它 们往往能够给出较好的解。 这类算法有： 1 插入算法 插入型算法可按插入规则的不同而分为若干类，其一般思想为： 步骤1 ：通过某种插入方式选择插入边( i ，j ) 和插入点k ，将k 插入i 和j 之间， 形成( ，i ，k ，j ，) ； 步骤2 ：依次进行直至形成回路解。 适用范围：对称型t s p 。一般有如下几种插入方法： 第二章旅行商问题 1 ) 最近插入法。最坏情况：s = 2 ；时间复杂度：o ( n 2 ) 。 2 ) 最小插入法。最坏情况：s = 2 ；时间复杂度：o ( n 2 l g 砷。 3 ) 任意插入法。最坏情况：b = 2 1 9 n + o 1 6 ；时间复杂度：o ( n 2 ) 。 4 ) 最远插入法。最坏情况：= 2 1 9 n + o 1 6 ；时间复杂度：o ( n 2 ) 。 5 ) 凸核插入法。最坏情况：s 未知；时间复杂度：o ( n 2l g n ) 。 2 最近邻算法 步骤1 ：任取一出发点； 步骤2 ：依次取最近的点加入当前解中直至形成回路解。 适用范围：对称型的t s p 最坏情况：g = ( 1 9 n + 1 ) 2 ；时间复杂度：o ( n 2l g n ) 。 3 c l a r k & w r i g h t 算法 步骤1 ：任取一出发点p ，计算勺= d ，+ 厶+ 吒； 步骤2 ：将各s 。由大n d , 排列； 步骤3 ：将排好后的s 。对应的各边o ，) 依次适当联接，形成回路解。 适用范围：对称型的t s p 最坏情况：g = 2 1 1 9 n 7 + 2 2 1 ；时间复杂度o ( n 2 ) 。 4 双生成树算法 步骤1 ：首先求出最小生成树； 步骤2 ：将树中各边都添一重复边并求出其e u l e r 回路； 步骤3 ：在e u l e r 回路点序列中去除重复点，形成回路解。 适用范围：对称型t s p 最坏情况：s = 2 ；时间复杂度o ( n 2 ) 。 5 c l f 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 最坏情况：s = 3 2 ；时间复杂度：o ( n 3 ) 。 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 法仍然是一种相当有效的近似算法。著名的l k 算法【6 5 l 就是基于2 o p t 和3 一o p t 的。 1 4求解旅行商问题的进化算法 适用范围：对称型t s p 最坏情况：8 = 2 ( n 8 ，r n 4 ) ；时间复杂度：o ( n 7 ) 。 7 混合算法 用某个近似算法求得初始解，然后借助一个或者若干个r q p t 算法对其加以改 进。这种混合型算法往往能获得较好的解，但也很耗时。 8 概率算法 该算法能对任意给定的8 0 ，在1 + s 之内几乎处处解决t s p ，假定g 位于单 位正方形内，函数f ( h ) 映射到正有理数，满足t _ l 0 9 2l 0 9 2 以；对所有胛，n i t 是完全平方。则有： 步骤1 ：以p ( n ) 玎】“2 为尺寸构成网络，将单位正方形分成n t ( n ) 个子正方形， 将g 也分成至多n t ( n ) 个子图； 步骤2 ：用动态规划方法求解每个子图的最优回路； 步骤3 ：将n t ( n ) 个子图各自收缩为一点，其间距离定义为原子图的最优子回 路间最短距离，并对新构成的图求最小生成树丁； 步骤4 ：将r u 各子图的最优子回路 视为一可能有点、边重复的闭回路，根 据三角形不等式条件，归约重复点或边，得t s p 回路。 适用范围：对称型t s p 最坏情况：s = 1 + 任意给定正整数；时间复杂度：o ( n l g n ) 。 以上的各种优化算法都是一种局部搜索算法，一般得到局部最优解，很难达 到全局最优解。并且很难适用于大规模的最优化问题。 2 5 2 智能优化算法 2 5 2 1 禁忌搜索方法( t s ) 禁忌搜索方法( t s ) 是对局部领域搜索的一种扩展，是一种全局逐步寻优算法， 是对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁 忌准则来避免迂回搜索，并通过一定准则来赦免一些被禁忌的优良状态，进而保 证多样化的有效探索以实现全局优化。 禁忌搜索算法的基本框架： 步骤l ：给定算法参数，随机产生初始解x ，置禁忌表为空； 步骤2 ：判断算法终止条件是否满足，如果满足，则停止，并输出最优解。 否则，执步骤3 ； 步骤3 ：利用当前解x 的领域函数产生其所有( 若干) 领域解，弗从中确定若 干候选解； 步骤4 ：对候选解判断藐视准则是否满足? 若满足，则用满足藐视准则的最 第二章旅行商问题 优状态y 替代x 成为新的当前解。即令x = y 。并用与y 对应的禁忌对象替换最早 进入禁忌表的禁忌对象，同时标记y 为“b e s ts of a r ”状态，转步骤5 。否则，执 行步骤2 ： 步骤5 ：判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象 对应的最佳状态为新的当前解。同时用与之对应的禁忌对象替换最早进入禁忌表 的禁忌对象元素。 2 5 2 2 模拟退火算法 模拟退火算法是基于m o n t e rc a r l o 迭代求解策略的一种随机寻优算法，其出发 点是基于物理中固体物质的退火过程与求解一般组合优化问题之间的相似性。模 拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳性在解空 间中随机寻找目标函数的全局最优解，使得局部最优解能概率性地跳出并最终趋 于全局最优解。 模拟退火算法的基本框架： 步骤1 ：给定初始温度t = t o ，随机产生初始状态x 0 ，置= x 。，令k = 0 ； 步骤2 ：判断是否满足m e t r o p o l i s 抽样稳定性，如果满足，转步骤3 ，否则从 领域n ( x i ) 中随机选一x ，如果m i n l ，e x p ( f ( x f l - f ( x , ) ) t i 】 r a n d ( o ，1 ) ，t = x j ， 否则保持当前状态不变，重复步骤2 ； 步骤3 ：t k “= u p d a t e ( t k ) ，k = k + l 。若满足终止条件，终止计算；否则转 到步骤2 。 以上这两种方法都是从一个解开始进行局域搜索，虽然采用一定机制有效避 免陷入局部极小并最终趋于全局最优，但往往效率比较低。 2 5 2 - 3 神经网络算法 该方法的基本思想是通过对神经网络引入适当的能量函数，使之与t s p 的目 标函数相一致来确定神经元之间的联结权，随着网络状态的变化，其能量不断减 少，最后达到平衡时，即收敛到一个局部最优解。要解刀城市的t s p ，要把问题映 射到一个神经网络上。可以使用珂栉神经元矩阵。矩阵中的每个元素的状态只能 为0 或l ，神经元的状态用圪表示，= 1 表示城市s 在路径中第i 个位置出现。 一次有效路径使每行每列有且仅有一个元素为1 ，其余为0 。为了最终解决t s p ， 必须构成这样的神经网络：在网络运行时，计算能量降低，网络稳定后其输出状 态表示城市被访问的次序。网络能量的极小点，对应于最优( 或近似最优) 路径的 形成。其解决问题最关键的一步，是构造能量函数。 2 5 2 4 遗传算法 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 局优化算法，是美国m i c h i g a n 大学的h o l l a n d 教授于1 9 7 5 年首次提出，起源于6 0 年代对自然和人工自适应系统的研究。7 0 年代d ej o n g 基于遗传算法的思想在计 1 6 求解旅行商问题的进化算法 算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架i 侧。g o l d b e r g 和 m i c h a l e w i e z 进行了大量的研究工作，并成功地将它应用到各种领域的优化问题。 遗传算法的早期应用主要围绕组合优化问题求解，如煤气管道的最优控制， t s p 问题等，近年来迅速扩展到机器学习、设计规划、神经网络优化、核反应堆 控制、喷气发动机设计、通信网络设计、人工生命等领域，显示了遗传算法应用 的巨大潜力。 多年来，遗传算法从理论到实际都已经取得了许多重要成果。由于它具有良 好的全局搜索能力，是目前解决各种优化问题的最有效的方法，己经成为研究热 点。遗传算法就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机 搜索算法。因此遗传算法在t s p 问题求解方面的应用研究，对于构造合适的遗传 算法框架、建立有效的遗传操作以及有效地解决t s p 等有着多方面的重要意义。 2 5 2 5 蚁群算法 人工蚁群算法是人们受到对自然界中真实的蚁群集体行为的研究成果的启发 而提出的一种基于种群的模拟进化算法，属于随机搜索算法，由意大利学者m d o r i g o 于2 0 世纪9 0 年代初首先提出。该算法充分利用了蚁群搜索食物的过程与 t s p 之间的相似性，通过人工模拟蚂蚁搜索事物的过程( 即通过个体之间的信息交 流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 。象蚂蚁这类群居 昆虫，虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚁群 却表现出极其复杂的行为，能够完成复杂的任务。蚁群之所以表现出复杂有序的 行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能 够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质 的存在及其强度，并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的 集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者 选择该路径的概率就越大。 用蚁群算法求解t s p 时，我们不难发现：蚁群算法的主要依据是信息正反馈 原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利