（应用数学专业论文）基于lkh的tsp扰动问题的算法.pdf

基于l k h 的t s p 扰动问题的算法 专业：应用数学 硕士生：刘丰 指导教师：周天寿教授冯国灿教授 摘要 t s p 阀题在图论的意义下就是最小壬k 越l 白d n 圈问题，是组合优化领域的重要 问题之一，它有着广泛的应用，因而对其开展深入广泛的研究具有重要的理论价 值和实用意义。 本文主要工作是探讨l k h 算法解决t s p 问题。论文首先综述t s p 问题的研 究现状，介绍舀前解决t s p 闯题的主要算法，重点研究l k 经典算法和l i ( h 改进 算法，并对l k h1 3 版和2 0 版算法引擎做测试和评价。 在此基础上，本文致力于实现l _ k h2 o 舨算法弓| 擎的可视化，独立开发了 l k h c o n q u e r 的可视化t s p 系统。该系统不仅把t s p 问题生成的可视化、t s p 数据现实的可视化、t s p 求解性能的可视化集成，还抱窗口的各种属性参数化， 使整个可视化界面更直观、明了。 然后，提出l k h 算法的增量式改进算法，主要是针对t s p 问题的顶点增加、 删除和修改三种t s p 扰动的算法研究，并将其可视化，与l i 为顶点集，e 为边集，各项点的距离办 已知( 巩 0 ，丸= 佃，f ，矿) 并设 r 1 ，边( i ，j ) 在最优路线上 勤= 1 o ，其他 则t s p 的数学模型可写成如下线性规划形式： 脱= 办勤 j 7 勤= l ，y 勤= 1 ， f 矿 嘞蚓一1 ，对所有v 的子集s 0 ，1 f ，歹矿 这里，蚓为集合s 中所含图g 的顶点个数，前两个约束意味着一条边进和 6 一条边出，后一约束则保证了没有任何子回路解的产生，于是，满足上述约束条 件的解构成一条哈密尔顿回路。除此之外，模型还有其它一些等价的书写形式。 2 2 旅行商问题的分类 旅行商问题按不同的分类方法可以分成为不同的种类。 1 据距离矩阵划分 。当办= d g ，y ) 时，问题被称为对称型旅行商问题。反之，称为非对称 型旅行商问题。非对称型旅行商问题可以化为对称型旅行商问题并用对称型的方 法求解。 当所有f ，j ，| j y ，有不等式喀+ d 庸丸成立时，问题被称为满足三角不等 式，简写成三角型旅行商问题。一般而言，现实生活中的大多数问题都满足三角 形不等式，它是旅行商问题中的一种主要类型。个别不满足的，也可转换成其闭 包问题，它们的旅行商问题解是等价的。 当蟊是欧氏距离时，则称为欧氏距离的旅行商问题。显然此类问题既是对 称型旅行商问题也是三角型旅行商问题。 2 根据定点的分布形态划分 有均匀分布的、聚集分布、随机距离矩阵，此外还有旅行商问题库( t s p l i b ) 中的实际范例【1 1 】。前三种都是人工模拟产生的旅行商问题，主要用于测试算法对 不同分布形态的旅行商问题的表现，并计算算法的时间函数后一种实际范例才是 人们关注的重点。 3 根据距离矩阵在数据文件中的存储方式划分和来源划分 m a ：r r 型【1 1 】：距离矩阵直接给出。e u c2 d 或c e l l2 d ：给出顶点坐标， 距离矩阵需计算才能得到。g e o ：给出顶点坐标，距离矩阵需计算才能得到，坐 标来源于地理坐标。 2 3t s p 算法的评价标准 算法的性能不仅受其控制参数的影响，而且与算法的实现及算法的试验平台 等有关。在t s p 的研究中，常采用下述两种算法性能的评价标准： 7 1 期望值估计法：这种方法适用于随机产生的e u c l i d 平面，是由h e l d 和k a 等在文献【1 2 1 中提出的。对这样的t s p ，其期望最短路径的长度为r = 刖欣。此 处n 是城市的数目，r 是一个正方形的面积，在随机布点时，各城市皆位于该正 方形之内；k 是一个经验值，称为h e l d k a 印下界。已有实验表明 1 3 】，城市数n 不同时，k 值也稍有不同。一般采用7 6 5 【1 4 1 。 2 测试集法：使用由很多研究机构与人员建立的一个t s p 库1 1 】。在该库中， 有很多研究人员用各种方法计算过的t s p 问题，通常还提供已知的最短路径与 长度。这个t s p库在很多网点都可找到。例如， 邱：s o r l i b r i c e e d u p l l b t s p l i b ，t s p l i b t a 正z 。 我们在做t s p 问题的仿真实验的时候，用到的评价标准就是测试集，在后 面的章节中有涉及到。 2 4 旅行商问题的扩展 旅行商问题的研究经过几十年发展，取得了一系列的成果。除了经典的旅行 商问题外，目前已引申出许多扩展形式，常见的有： 1 最小哈密尔顿链的问题【1 5 】 这是起点和终点不同的旅行商问题，前面提到的许多算法都可略作修改，用 于求解该类问题。 2 瓶颈问题【1 6 】 目标函数为朋缸 ，气，) ，且f j ，f ，j f g 的旅行商问题。 3 非对称旅行商问题( a s y m m e 仃i ct s p ) 【1 6 】 距离矩阵非对称的旅行商问题。 4 多人旅行商问题( m l d t i p e r s o nt s p ) 1 6 】 由多人完成环游的旅行商问题。该问题可转换成等价的单人问题，只需将1 点改为m 个虚拟点( 1 ，2 ，疗) 其中间用边连接，距离为充分大肘 - 勺， 从虚拟点，到j 的距离印，= q ，对新问题求解其旅行商问题后，从虚拟点f 进入 原网络再回到虚拟点j f 的那段路线即是m 人中某一个的环游路线。 8 5 多图标旅行商问题( n 埘6 o 场e c 畦v et s p ) 【1 7 l 若各边弧上有m 个权值，则使得哈密尔顿圈上相应的m 个目标值都尽可能 小的解就称为多目标旅行商闯题的( p 嬲螬o ) 有效解。如实际阀题中常常需要考虑： 路程最短、时间最少、费用最省、风险最小等多方面的因素。由于多目标意义下 的所谓最优解是一种“折衷解、“非劣解 ，因此，多躁标旅行商问题解的含义 为：假定有一哈密尔顿圈的解h ，若不存在任何其它回路解q ，使得 乏乏，露= 毛磊，嬲，其孛至少有一个不等式严格藏立( 磊为穗应的目标 函数值) ，则为p 删胁解。 6 依次捧序闻题( s e q 豫崩蠢d 6 e f 娃据p 汹l 饿( s o p ) ) 【1 绣 这类问题是非对称旅行商问题，在给定的一系列项点和距离矩阵下，寻找最 短从l 顶点到n 顶点啥密尔顿链，同时满足限制：某些顶点要在另一些顶点之前 被连接。 7 载货量受限制的路径溺题萄 给定n _ 1 个顶点和一个仓库，已知顶点和顶点、顶点和仓库的距离。卡车的 载货量受限制，卡车每次在郝分顶点和仓库之闻往返，寻求一条经过所有顶点的 最短路线。 一般来说，这些扩展闯题都有特殊的不同子对称型旅行商l 萄题的求解方法， 但也可将它们转化成对称型旅行商问题求解。在本文中，除非特别说明，所提到 的旅行商问题都是对称型阀题。 2 。5 研究旅行商问题的应用 t s p 闯题是一今古老而有趣的阕题，它提供了一个平台让科学家们研究出更 多解决最优化问题的方法，最优化问题与人们的生活息息相关，而许多领域的发 展反健进善s p 闯题的研究。它们的影响是相辅褶成。 最初t s p 问题的最早应用是货运与物流，例如校巴接送学生上学就是t s p 闻题的简单应用。隧磊t s p 游题还应用在投递员送信，餐饮公司送外卖等。 现在t s p 问题的应用于各个领域： 在基因重组方面，美国里生研究所然蕊潍砖殛莲i 憾o f 琢癌氇) 剽蔫c 强f i 构造出辐射杂交图( 脚i a t i o nh y 研dm a p s ) ，c o n c o r d e 把局部辐射杂交图重组成 9 一个大的辐射杂交图口朝。2 0 0 1 年，法国的一个研究老鼠基因的小组同样利用这 种方法构造辐射杂交图。t s p 问题还应用在太空船上，休斯顿大学的个工程小 组把c h a i l l e dl k 算法应用在星光干涉计划( s t a l l i g h ti n t e 疵r o m e t e rp r 0 铲锄) ，这 个研究的目的是求得经过所有太空船的最小燃料【1 9 1 。 在半导体制造中，c o n c o r d e 被用来最优化整合电路的扫描链，扫描链是芯 片中一个回路，主要用来测试，出于时间和能量的考虑，要求扫描链越短越好。 在基因工程中，很重要的一步是将一些d n a 串嵌入到一个通用串中，研究员利 用c o n c o r d e 解决了通用串的最小化问题【6 】。 在艺术领域中，t s p 应用为绘制t s pa r t 。如下图2 1 ( a ) 和( b ) 就是由t s p 问 题构成的唯美图口o 】。 瀚 图2 - 1 ( a ) ：t s p a n - 士d a图2 一l ( b ) ：t s p a r t c o l l i s e 啪 此外，t s p 问题还应用在光纤和电缆的铺设、世界最短飞机路径等问题上。 1 0 2 。6 旅行商闻题的解法 2 6 。l 旅行商问题的精确解法 1 可解特殊旅行商问题的精确算法 对于旅行商问题昀一些特殊情况，业已研究出一系列j 常完美的结果，如： 机器排序问题等。由于可解情形的结果都是成熟的定理，因此严格来说已不属算 法研究的藏畴。 2 线性规划算法 这是求解旅行商离题的最早的一种算法【潮，主要是采用整数规划孛的裁平 面法，即先求解模型中由前二个约束构成的松驰线性规划问题，然后通过增加不 等式约束产生割平瑟，逐渐收敛到最优解。 d a n ：t z i g 等人早在1 9 5 4 年就求解过胪4 2 的旅行商问题最优解。7 0 年代 中麓对于稻多面体理论的研究【灞，产生了一些比较有效的不等式约束，如：子 回路消去不等式、梳子不等式等等。 露前，常震的方法是先用近似算法来求得近似解，再将此近似解作为下限， 用线性规划方法来精确求解或证明此下限为最优解。 3 。动态规划算法 由于动态规划算法的时间复杂度为q 拧2 2 “) ，空间复杂度为伙忍2 一) ，故除 了很小规模的问题外，几乎不予采用。 4 。分支定赛算法 分支定界法【2 1 】是一种应用范围很广的搜索算法，它通过有效的约束界限来 控制搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一 个最优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的 分支定界法。 1 ) 以分派问题为界 通过求解相应的分派闯题，得到旅行意阀题的一个下界，以此进行分支定界 搜索。这是一种使用较多的分支定界算法。 2 ) 以匹配问题为界 通过求解相应的匹配问题，得到旅行商问题的一个下界，以此进行分支定界 搜索。该方法适用于对称型旅行商问题。 3 ) 以最小权l 生成树问题为界 通过求解相应的最小权1 生成树问题，得到旅行商问题的一个下界，以此进 行分支定界搜索。在此基础上，h e l d 和k a r p 【1 1 曾将问题加以转换，得到更紧的 下界，有时甚至能将搜索树整个显示出来。 虽说分支定界法对于较大规模的问题并不十分有效，可有时却被用来求解近 似解。而且，将分支定界法与一些启发式算法相结合，常常能获得一些意外的成 功。 2 6 2 旅行商问题的近似解法 由于精确式算法所能求解的问题规模非常有限，实际中使用的往往都是多项 式阶数的近似算法或启发式算法。算法的好坏用c c 宰e 来衡量，c 为近似 算法所得到的总行程，c 宰为最优总行程，e 为最坏情况下，近似解与最优解的总 行程之比所不超过的上界值。 1 插入型启发式算法【1 6 】 插入型算法可按插入规则的不同而分为若干类，其一般思想为： s t e pl 通过某种插入方式选择插入边( i ，j ) 和插入点k ，将k 插入i 和j 之间， 形成 ，i ，k ，j ，) ； s t 印2 依次进行直至形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可以将出发点取遍v 中各点而得到多个解，从中选择最好的 一个，但此时的时间复杂度增加了n 倍。常见的插入型算法有： 1 ) 最近插入法 最坏情况：e 芦2 ；时间复杂度：d ( 万2 ) 。 2 ) 最小插入法 最坏情况：e = 2 ；时间复杂度：仪刀21 1 1 刀) 3 ) 任意插入法 最坏情况：e _ 2 1 萨+ 0 1 6 ；时间复杂度：d ( 以2 ) 1 2 4 ) 最远插入法 最坏情况：e _ 2 1 印+ o 1 6 ；时间复杂度：d ( 稽2 ) 5 ) 凸核插入法 最坏情况：e = 未知；时间复杂度：d ( 刀21 i l 功。 2 最邻近算法 s t 印1 任取一出发点； s t 印2 依次取最近的点加入当前解中直至形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可以将出发点取遍v 中各点而得到多个解，从中选择最好的 一个，时间复杂度增加了n 倍。但此时最坏情况：e ：( 1 舻1 ) 2 ；时间复杂度： d 0 2 ) 。 3 c l 砌【& w 五出算法【刀 s t 印1 任取一出发点p ，计算勺= 如+ 厶一办； s t e p2 将各由大到小排列； s t 印3 将排好后的各配对顶点 i ，j 依次适当连接，形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可将出发点p 取遍v 中各点而得到多个解，从中选择最好 的一个，但此时的时间复杂度增加了n 倍。最坏情况：e = 2 1 7 + 5 2 1 ；时间复 杂度：d ( 刀2 ) 。 4 双生成树启发式算法圆 s t e p1 首先求出最小生成树： s t 印2 将树中各边都添一重复边并求出其e u l e r 回路； s t 印3 在e u l e r 回路点序列中去除重复点，形成回路解。 适用范围：对称的三角型旅行商问题。最坏情况：e = 2 ；时间复杂度：d ( ，z 2 ) 。 5 c h r i s t 0 丘d e s 算法嗍 s 钯p1 首先求出最小生成树； s t 印2 对树中所有奇项点解最小权匹配问题； 1 3 s t e p3 将匹配边添入生成树并求出其e u l e r 回路； s t e p4 在e u l e r 回路点序列中去除重复点，形成回路解。 适用范围：对称的三角型旅行商问题。最坏情况：e - 3 2 ；时问复杂度：0 ( ) 。 6 r - o p t 算法1 9 】 该方法是一种局部改进搜索算法，由l i n 等人【7 1 提出。适用范围：对称型 旅行商问题。 s t 印1 根据一定的规则求出每个顶点的候选顶点集，人为地规定该顶点只能 和候选集中的顶点相连接； s t 印2 产生初始路线； s t e p3 对每一个顶点轮流进行卜o p t 交换，直到无法改进当前解为止； s t e p4 输出当前的解作为结果。 最坏情况：e - 1 2 ( n 8 ，r i 似) ；时间复杂度：d ( 玎7 ) 。 7 合成算法 用某个近似算法求得初始解，然后借助一个或若干个p t 算法对解加以改 进。这种合成型的算法往往能获得较好的解，但也很耗时，一般仅在对解有较高 要求时采用。 8 概率算法 该算法能对任意给定的e o ，在1 + e 之内几乎处处解决对称型旅行商问题。 假定g 位于单位正方形内，函数f ( 万) 映射到正有理数，满足a ：t 1 0 92 ( 1 0 9 2n ) ； b ：对所有n ，n t 是完全平方。则有： s t e p1 以【t ( n ) n 】2 为尺寸构成网格，将单位正方形分成n t ( n ) 个正方 形，将g 也分成n t ( n ) 个子图； s t 印2 用动态规划方法求解每个子图的最优回路； s t e p 3 将n t ( n ) 个子图各自收缩为一点，其间距离定义为原子图的最优子 回路间最短距离，并对新构成的图求最小生成树t ； s t 印4 将t u 各子图的最优子回路) 视为一可能有点、边重复的闭回路，根 据三角形不等式条件，归约重复点或边，得到旅行商问题的回路。 适用范围：对称型旅行商问题。 1 4 最坏情况：e _ 1 h 任意给定正数) ；时间复杂度：0 【刀m 刀) 】。 9 神经网络算法 八十年代中后期，美、日等国家出现了一股神经网络热潮，许多从事脑科学、 心理学、计算机科学以及电子学等方面的专家都在积极合作，开展这一领域的研 究。其早期思想源于四十年代，由于受v o nn e 咖砌呲串行处理体系的限制，一 直进展不大，直到八十年代，美国生物物理学家h o p f i e l d 提出人工神经网络( 删 模型，才被认为是一个重大突破。 人工神经网络o 蜥丘c i a l 洲n e t w o 咄姗，也称为神经网络 烈e u 例i n e 铆o r l ! 【s ，加叼，是由大量处理单元即神经元( n 伽r o n s ) 互相连接而成的网 络，通过反映人脑的基本特性，对人脑进行抽象、简化和模拟的一种工程系统。 人工神经网络算法成为近年来的热点研究领域，涉及到电子科学与技术、电气工 程、控制科学与技术等诸多学科，其应用领域包括了建模、时间序列分析、模式 识别和控制等，并且仍然在不断扩展。 作为神经网络的基本单元，神经元模型具备三个基本要素。其一是具有一组 突触或连接，常用w 日表示神经元i 和神经元j 之间的联接强度，或称之为权值， 取值可在负值和正值之间；其二是具有反映生物神经元时空整合功能的输入信号 累加器；其三是具有一个激励函数用于限制神经元的输出。 根据信息流向和网络的拓扑结构，可以将神经网络模型分成以下几大类： 1 ) 前馈神经网络；2 ) 反馈神经网络；3 ) 随机神经网络；4 ) 竞争神经网络。 而h o p f i e l d 和t a n k 【1 6 】用a n n 方法求解旅行商问题获得成功以来，更是引 起了极大的关注，国内也报导了求解数百个结点旅行商问题的有关结果。方法的 思想是通过对神经网络引入适当的能量函数，使之与旅行商问题的目标函数相一 致来确定神经元之间的连接权，随着网络状态的变化，其能量不断减少，最后达 到平衡时，即收敛到一个局部最优解。目前，前述的几种神经网络都有在旅行商 问题商的应用实例，且取得了一定的成功，但还存在着严重缺点，而且就一般实 际问题而言，无法与其它近似算法相比。因此，该算法的适用范围很可能在于非 欧空间或不可度量的旅行商问题方面。 1 0 模拟退火算法 这是一种源于五十年代基于m o n ：t cc a l l o 迭代求解思想的随机搜索算法，八 1 5 十年代才开始应用于组合优化领域，其出发点是将组合优化问题与统计力学的热 平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火处 理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降， 在热平衡条件下，物体内部处于不同状态的概率服从b o l t z m a i l n 分布，若退火步 骤恰当，则最终会形成最低能量的基态。这种算法在求解优化问题时，不但接受 对目标函数( 能量函数) 有改进的状态，还以某种概率接受使目标函数恶化的状 态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动能够 使之跳出局部极值点，故而得到的解常常很好。经典的模拟退火算法流程为： s t l 印1 选择初始状态h ( 初始解) 、初始温度、降温次数； s t 印2 生成h 的邻域状态h ，并计算z ( h ) z ( h ) ； s t e p3 按接受概率置换h ； s t e p4 重复s t 印2 直至停机条件满足。 模拟退火法所得解的好坏与初始状态、温度函数等都有一定的联系，降温较 快的效果不一定很好，效果好的，其降温过程又极其缓慢。但由于该方法适用范 围广，并且可以人为控制迭代次数，反复求解，因此具有很强的实用性。 1 1 遗传算法 它是一种来自生物进化理论中“适者生存 的自然选择原则的搜索( 寻优) 算 法瞄】，它基于生物学的自然选择原理和自然遗传机制模拟生命的进化，这种新 近发展起来的完全异于传统思想的搜索和优化方法。自j o h nh o l l a i l d 等( 1 9 7 5 ) 提 出以来，获得了广泛的应用。尤其是在人工智能领域，取得了极大的成功，对于 许多复杂困难问题的解决提供了强有力的处理办法【3 6 】。 遗传算法用于优化问题时，其最主要特征就是：它不在单点上寻优，而是从 整个种群( p o p u l a t i o n ) 中选择生命力强的个体产生新的种群；它使用随机转换原理 而不是确定性规则来工作。遗传算法中常用的遗传操作包括三个基本算子：复制 ( r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ) 、变异( m m a t i o n ) 。其中，复制算子用于旧种群 生成新种群，交叉算子用于从父母代生成子代，变异算子用于对子代作某种变异。 这里，复制和交叉操作是遗传算法的有效性所在，但有时会丢失一些重要的遗传 信息，适当的变异操作可保证这些有用信息的引入。 1 2 其它算法 1 6 除了前面提及的一些典型的旅行商问题算法之外，还有其它许多方法可供使 用，如n o r b a c k 等人【l q 的几何图解法、极小代数算法【1 6 1 、归约算法【1 6 l 、蚂蚁算 法等等。还有一种使用效果也相当不错的禁忌搜索法，它采用了类似爬山法的移 动原理，将最近若干步内所得到的解储存在禁忌列表中，从而强制避免再次重复 搜索表中的解，该方法在九十年代曾求解过几十万个顶点的大型旅行商问题。 1 7 第3 章l k 算法和l k h 算法的基本原理 3 1l k 算法 l k 算澍1 1 是由l i l l k e r i l i 班趾等人于1 9 7 3 年提出来的，它是在局部改进搜 索算法r o p t 算法【9 】的基础上完善的，它是一种非常高效的启发式算法。当问题 规模小于5 0 时，测试获得最优解的概率几乎为1 。当问题规模达到l o o 时，测 试获得最优解的概率降至2 0 0 0 。 3 1 1l k 算法基本原理 定义3 1t s p 问题中，对于路径r ，取消k 条边再补上k 条边，形成一条 新的路径，叫做一次k 帕p t 操作。 例如，当m 时，就是2 o p t 操作。图3 1 展示了2 - o p t 操作的例子。 t 4 t 3t 4 t 3 t 2 t l t 2t l 图3 l 2 叫操作 l k 算法乃至l k h 算法都是基于一系列的k o m 操作来实现的，这是整个算 法的基本概念。 定义3 2 如果一条路径不能通过任何k o p t 操作得到更短的路径，那么这条 路径就是k - o p t 路径。 由定义3 2 可以轻松得到如下两个定理： 定理3 1 一条路径如果是k - o m 路径，那么对于所有后( 1 是由图嘲中壶点集w 量 生成酶生成树帮盘点 1 引出的两条边构成的图。 需要注意的是，1 树并不是真正的树，它包含有一条回路。 定义3 2 2 最小1 树( m i n i m u ml 舭e ) 是总长度比其它1 壤 都小的l 。树。 定理3 2 1 最优旅行是每个点盼赛数都是2 的最小董树。 定理3 2 2 如果最小1 树是一条旅行，那么它就是最优旅行。 一般酶，基于穗阕节点集的最小生成树和最优旅行拥有很多穗圆的边，两最 优旅行又与最小1 树有7 0 8 0 的边相同，因此用最小1 树作为“接近度的 2 2 一种启发式度量标准非常合适。如果一条边属于或接近属于最小1 树，则它有很 大可能也属于最优旅行；反之如果一条边远不属于最小1 树，则它也很可能不属 于最优旅行。l k h 算法应尽量将“远 边排斥在旅行改善的候选边( c 锄d id a ：t e s ) 之外，当然同时也要把握好排斥力度，以免将最优旅行排斥在外。 定义3 2 3 用t 代表最小1 一树，它的长度是l ( t ) ；用r o ，) 表示必须包含 边( i j ) 的最小1 一树；则边( 巧) 的a 一接近度表示为a ( f ，歹) = 工( r ( f ，歹) 一三( r ) ) 。 因此，给定最小1 树的成本，一条边的a 一接近度等于包含该边的最小1 树与给定最小1 树的成本之差。由此得到的两个简单属性如下： a ( f ，) o ； 如果边( i j ) 属于给定的最小1 - 树，则口( f ，歹) = o 。 用a 一接近度刚可以更客观地预测边属于最优旅行的可能性。例如可以把那 些“最有希望的边 ，即“候选边集( c 锄d i d a t es e t ) 定义为：向每个节点入射的 “a 一接近度最小的k 条边 或者“口一接近度小于某个给定阀值的所有边 。 通过对t s p l m 的测试显示，用a 一接近度要远远优于经典l k 运算法中依 据成本确定候选边集。口一接近度确定的候选边集可以是很小规模，但丝毫不会 降低算法精度。例如上文提到5 3 2 点问题中最坏情况下的边，用c 接近度描述它 的一个节点是另一个节点第2 2 个最近的节点；而用a 一接近度描述同一节点， 其排序升至1 4 位。最优边集( 即最优旅行上的所有边) 在候选边集中的平均优 先值从2 4 升至2 1 。 这个改进是在p 曲算法1 3 刀基础上实施的，它总的时间复杂度为o ( n 2 ) 。事实 上此时还有改进的余地。改进基于以下事实【2 】： 设n 表示问题规模，令万= 乃， ，令c 衄= h ) 表示距离矩阵，其中 = c ( f ，) 表示城市i 到城市j 之间的距离。 定义见埘= 办i 吃= 白+ 乃+ 乃 ，用瓦表示用矩阵d 代替矩阵c 生成的最 小1 树，三( 瓦) 是根据矩阵d 计算的瓦的总长度，则 仞) = 三( 疋) 一2 乃 是原问题的一个下界。 h e l d 和勋印提出了梯度优化法( s u b 伊a d i e n to 埘m j 翻五o n ) 【2 7 】，通过迭代法调 节向量万，使何) 逐步增大，并使瓦越来越接近一条旅行( 即越来越多点的度数 是2 ) 。p o l j 划2 8 】证明这个迭代过程是收敛的，但速度很慢。l k h 则采用限制迭 代次数的办法，以在可接受的时间内获得可接受的近似上限。这时再根据向量巧 计算d 矩阵，生成基于d 的最小1 树，再计算基于d 的接近度，记为a 。 a 。比a 的性能又提高了。对于问题a t t 5 3 2 ，最优旅行上的边，统计其一个端 点在另一个端点的候选城市中的排名，如果依据a 。来排名，则最大排名为8 ，平 均排名为1 7 ，明显比口好。 l h k 算法是用基于d 的接近度作为标准为每个城市建立一个候选集，初始 集合为基于d 的接近度最小的城市，然后根据以下三点调整 a ) 如果城市i 属于城市j 的候选集，那么城市j 也应该属于城市i 的候选集； b ) 如果城市i 不属于城市j 的候选集，但在某个局部最优解中是j 的邻城， 那么将城市i 加入城市j 的候选集。 c ) 最近两次最优旅行的共有边，其一个端点在另一个端点的候选集中的位 置，被调整为第一个。 实验表明，用基于d 的接近度代替距离作为能否进入候选集的标准，可以 大大提高候选集的质量，从而大大提高搜索效率。 ( 1 ) 初始解 l k 算法就是多次从不同的初始解出发，通过优化路径来获得最终解的。它 认为任何用启发式算法获得初始解的工作都是徒劳的。然而，关于是否该用启发 式算法获得初始解的问题，却并不是那么容易回答的。l k h 算法采用如下算法 获得初始解： 步骤1 ：随机选择一个初始节点i ； 步骤2 ：按如下规则选择下一个尚未被选过的节点j ：边( i j ) 是一条候选边； 口( ，j f ) = 0 ；边( i j j ) 属于当前最优旅行。若不能满足上述全部3 条规则，则优 先选择满足规则的节点。再否则，在尚未被选过的节点中随机选择节点j ； 步骤3 ：令两，如果还有未被选择的节点，返回步骤2 。 2 4 如果在步骤2 有一个以上的节点可供选择，则随机选中其中一点。这样一个 选中节点的编号顺序就构成了一个初始旅行。该构造过程非常快，而且产生的各 初始旅行之间存在充分差异，由此保证后续启发式算法可以获得较好的最终解。 ( 2 ) 基本操作 l k h 改进算法从这两方面修正经典算法的实现框架。 首先，改进算法将基本移动设定为有序5 o p t 移动【鹅】，因此，算法考虑的移 动是一次或多次的5 - o p t 移动。但是，算法同时规定一旦发现新的路径改善机会， 立即停止当前5 - 0 p t 移动的构造，转下一次5 o p t 移动的构造按照这种方式，算 法就可以确保2 - o m 、3 _ 0 p t 和4 町p t 移动与5 o m 移动同等机会出现。 5 o p t 移动拓宽了算法的搜索深度，增强了求解能力，只是相应需要更长运 行时间。但是，如果考虑到使用更小规模的候选边集，运算时间变化并不显著。 而且，测试实例显示改进算法不再必需回溯( b a d k 昀c k 遗g ) ( 确定第一条要破坏的 边五的情况除外) 。取消回溯并未降低性能，且减少了运行时间，简化了编程实 现。 关于改进算法与原算法的性能比较，c h r i s t 0 丘d e s 和e i l o n f 2 9 1 的研究表明5 - o p t 较4 _ 0 p t 的性能改善优于4 - o p t 较3 叫的性能改善。 其次，经典算法的一个特殊情况是使用非有序交换。在改进算法中，充分考 虑了非有序交换对旅行的可能改善，于是把原算法的简单4 o p t 非有序移动用如 下“非有序移动集”( s e to f n 0 s e q u e n ：t i a ln 1 0 、髑) 代替： 当出现非有序2 0 p t 移动( 产生两个回路) ，其后使用可产生合法旅行的任 意2 o p t 或3 o m 移动( 将两个回路连接起来) 。 当出现非有序3 叫d p t 移动( 产生两个回路) ，其后使用可产生合法旅行的任 意2 0 p t ( 将两个回路连接起来) 。 可见，经典算法的非有序钿p t 移动是以上非有序移动集的一种个别情况。 通过使用这个移动集，算法寻优的能力被大大提高。依赖规模更小的候选边集和 “正获利规则”，非有序移动集的运行时间在算法总运行时间中占的微乎其微。 在经典算法中，非有序移动属于后最优化操作与之不同，改进算法一旦发现 子旅行改善机会，进一步的寻优即可以基于有序移动，也可以基于非有序移动。 ( 3 ) x 集的选取 l k h 算法对x 集的选取作出如下限制： a ) 第一条被删除的边，即x l ，不能是当前最优路径的边； b ) 基本操作的最后一条被删除的边，不能是当前系列的基本操作中曾经被 添加的边。 这两条限制是原l k 算法中限制2 的扩展，不但提高了效率，还简化了代码。 第4 章l k h 算法的可视化实现 4 1l k h 算法引擎 在介绍l k h 算法的可视化实现之前，需要先介绍l k h 算法引擎，算法引 擎是可视化实现的基础。本文使用的算法引擎是i ，k h 2 0 版，由i 沁l dh e l s g 籼 于2 0 0 7 年1 1 月份发布的，该算法引擎能求解出t s p l i b 9 5 里面的所有t s p 问题， 其中包括最大的8 5 9 0 0 个城市问题。 l 2 0 版算法引擎是用c 语言编译实现的，它的代码已经在网上公布，在 网址h t q p ：力m e r n l c d 咄e l d p u b l i ch 臼n l ，r e a r c m l k h 可以找到。以下简单介绍 主程序实现的框架。 主程序的实现框架： v o i d m a i n o r e a d p r o b l e m d a 眨i o ； c r e a 锄m 妇e s e t o ； b e s t c o 妒d b i ，m a x ； f 0 1 1 诬l u n i l ；r l 】n = r u n s ；r u n 十+ ) d o u b l ec o 妒f 砌1 0 u 哟； 珉c o s t p r i i l t b e 刚咕u 哟； ) r e a d p r o b l e r n d a t a o 是读入t s p 问题数据文件的程序，用c r e 锄e c a n d i d a t e s e t o 生成相应的候选边集。然后用l k h 算法f 砌迭代求出预定数量的局部最 优旅行，其中迭代的代数为r u n s 。最后这些旅行中的最优解将被输出到指定文 件p 血t b e s t t 0 u r o 。 2 7 l l m 算法引擎程序实现的主要框架详解，算法引擎的i o 控制详解，算法 引擎的技术难点分析等，给出了详细的介绍【耻3 2 3 9 ，4 1 4 5 】。 4 2l k h 算法可视化实现 本部分介绍了由我们基于l k h 算法2 o 版引擎开发的l k h c o n q u e r 可视化处 理软件，进一步进行功能模块的扩展，使该软件成为集问题制作、t s p 问题求解、 图形模式交互、坐标模式交互于一体的集成化软件，特别需要提出的是，该软件 还汇集l l 算法增量式改进功能。值得说明的是，本论文使用的l i m 引擎是 2 0 0 7 年1 1 月发布的2 o 版搜索引擎，此2 o 版的t s p 求解速度较1 3 版的有很 大提高，具体请看后面对t s p l i b 库的数据测试。 本部分用刚c + + 作为开发工具，可视化软件不仅在程序架构、数据处理 模块开发、可视化模块的开发【3 3 】改进，还在用户操作界面、功能扩展以及运算 模式等作较大的扩展。 下图4 1 是可视化模块的功能结构图 图4 1 可视化模块的功能结构图 本软件的可视化界面设置三种求解t s p 问题的方法，一是新建t s p 问题并 使用该软件计算求解，一是打开已有的t s p 问题并计算求解，最后是增量式求 解( 在下一章详述) 。不管是使用哪一种求解模式，可视化模块都使用在界面左 上角的“数据”模式来打开( 如图4 2 所示) ，”数据”下面两个图标是“新建t s p ”和 “打开已有t s p ”的快捷方式。 图4 2 初始界面 4 2 1 新建t s p 文件 在应用向导的主界面，选取“新建t s p 文件 。 前文己经介绍，l 也0 版的算法引擎支持t s p 、a t s p 和h c p 等模式，但 本文只针对t s p 问题( 即对称型t s p 问题) 。对称型t s p 问题是二维格式的坐 标数据问题，可以在图上显示，本软件地图路径设置缺省地图是中国地图，可以 根据用户需要选择其他地图( 地图需为幸b m p 格式) 。 按照图4 2 所示的设置，点击左上角新建文档，问题描述规范的参数设置图 4 3 所示。通过观察会发现，该对话框中的各参数设置是与问题描述文件结构【3 7 】 的各属性设置一一对应的。可视化界面下设置问题规范，同时要调用数据处理模 块类的格式检查函数，如果出现不兼容的规范设置，就回弹出消息框，提示用户 设置的规范存在错误。 图4 3 不妨按照缺省设置并点击“下一步”图4 4 所示，进入“运算参数设置”界面。 该对话框各参数的设置是与参数设置文件结构中的各属性设置一一对应的。与上 一步的操作( 图4 3 ) 类似，本对话框设置也有缺省设置，它直接调用了参数设 置文件结构中的缺省设置函数。另外，大部分数值型参数的缺省值都被设为1 ， 这表示这些参数不会在参数设置文件中出现，而将调用算法引擎中各参数的缺省 设置值。关于参数缺省设置值可参看上一章的相关内容，在这里按照“缺省设置” 点击“下一步”图4 5 所示。 结呆存放路径r r o l u r r l 日。i 13 t s p r c 。：| t 生瓮数j 旨存专定l 告径昨r i ：o 只 - a n c e f i l e ；13 p e r f i 喊件存放路径i p l r 旧广一i 使用次梯度算挂术解p 慎岩使用r 不使用 垂算次数 印 已知最优解i o p n m u 嘲，l 1 每次运算的循环次数m 蝼t r i a ls l 万一 每个节点的侯选边数量眦蛘c a n d l d a t e s ) 玎一 升级操作的节点侯这边数曼阳 a i p h a 值较环游长度下限构倍数玎一 升级操作的初始周期长度p n m 舢p e 剐o d l 万一 升级操f f 的初始步长h m a l s t e t s 旺 阿一 碴机数生成因子i s 旺d i 1 长度转换幅度喁e c 吲。呻 1 输出结皋的详缉层度m u c eie 、，e l | 和 竺曼i 堕|圭= 垄j! 二垄i堡塑| 图4 4 3 0 点击“完成”结束新建向导，软件主界面会更新如图4 - 5 所示 图4 - 5 软件主界面 图4 _ 6 地图模型的缺省图是中国地图 软件主界面，问题规范部分已自动生成，用户仅需要把问题数据添加到 “( 以下为添加数据部分) 和“ 以上为添加数据部分) 之间即可。拥有 地图模式的一大好处是，用户甚至不需要输入基本数据，仅需要在地图范围内添 加删除点，就可以相应更新问题文件上的数据。地图范围内，在任意位置上单击 3 1 左键则添加点、在已添加点的附近单击右键则删除该点，添加、删除点的操作同 时也反映到软件主界面的新建文件上点的相对坐标记录。 作为例子，不妨设有一位用户准备从广州出发作全国性的徒步旅行，他要经 过各省省会包括直辖市有且仅有一次，最后再返回广州，问他的旅行路线该如何 安排才能最短。 图4 7 全国旅行问题 用户可以在各省会的大体位置处单击左键添加点( 共3 4 点，如图4 7 所示) 。 另外，用户如果还想调节比例尺，可以设置“图形比例尺调节”( 默认是1 0 0 0 ： 1 0 0 0 ) ，本例仅做示范，不另设比例尺。 软件主界面的左侧是属性窗口，分别有“背景属性”、“画板属性”、“画点属 性”和“画线属性”四大块。其中“背景属性”有“地图”选项；“画板属性”有“比例尺”、 “边框颜色”、“绘制边框”、“绘制坐标系”、“填充背景”、“填充颜色”、“坐标系颜 色”等选项；“画点属性”有“边界颜色”、“标签颜色”、“标签字体”、“画点大小”、 “绘制边界”、“绘制填充”、“填充颜色”等选项；“画线属性”有“绘制箭头”、“线条 宽度”、“线条颜色”等选项，这些选项都是可以根据用户个人偏好，进行调节的， 特别是对特定的问题，经过以上选项的调节，会得到更直观的效果。 下面是对该问题求解，首先将该问题文件保存，然后点击地图模式上“算 法”- “l k h 算法”，此时程序运行将转入后台首先用户保存的问题文件被数 据处理模块读入；然后数据处理模块输出规范的问题描述文件，并对应该文件生 成引擎读入的参数设置文件算法引擎读取参数设置文件并开始计算，当计算结束 生成结果数据文件和性能数据文件，数据处理模块将读入处理这两个文件，然后 传给可视化模块并展现给用户。上述问题规模很小，不到1 秒就求出了最优解。 可视化模块生成三个界面：结果数据界面( 图4 8 ) 、性能数据界面( 图4 9 ) 、 更新的地图界面( 图4 1 0 ) 。 n a m e ：13 t s p m