您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 分支限界搜索 >

分支定界TSP(精)

发布时间:2019-06-24 21:01 来源:未知 编辑:admin

  2007 年 第 28 卷 第 2 期 中 北 大 学 学 报(自然科学版) V o l.28N o .22007 (总第 112 期) JO U R N A L O F N O R T H U N IV E R SIT Y O F C H IN A (N A T U R A L SC IE N C E E D IT IO N ) (Sum No.112) 文章编号: 1673-3193(2007)02-0104-04 用分支定界算法求解旅行商问题 管琳, 白艳萍 (中北大学 理学院, 山西 太原 030051) 摘要:在 0-1 整数规划的基础上建立了数学模型, 利用 M AT LAB 6.5 优化工具箱中的 linprog 函数进 行求解, 再经过分支定界算法计算, 求出了只含有 0 和 1 的解.实验结果表明, 该算法可以求解小规模旅行 商问题. 关键词:旅行商问题; 分支定界; linprog 函数 中图分类号:O29文献标识码: A A B ranch and B ound A lgorithm for T raveling Salesm an P roblem G U A N L in, BA I Y an-ping (School of Science, North U niversity of China, T aiyuan 030051, China) A bstract: Based on 0- 1 int eger linear prog ram m ing , m at hem at ics m odel is set and solved by linprog funct ion in optim ist ic toolbox of M A T L A B 6.5.T he solution only containing zeros and ones is acquired using branch and bound alg orithm .T he ex perim ent al results indicate t hat t his alg orit hm is suit able for sm all T SP (t raveling salesm an problem ). K ey w ords: traveling salesm an problem ; branch-and-bound algorit hm ; linprog funct ion 1旅行商问题简介 所谓“旅行商问题”, 即 T SP (T raveling Salesm an Problem ) 问题是一个十分有名的难以求解的优化 问题, 其要求很简单: 在个城市的集合中, 找出一条经过每个城市各一次, 最终回到起点的最短路径. 如果用 d ij表示从城市 i 到城市 j 的距离, 则路径的总长度 d =∑d ij.T SP 的最优解是求长度 d 为最 短的一条有效的路径.因为对于 n 个城市的全排列共有 n! 种, 而 T SP 没有限定路径的方向, 即为全组 合, 所以其旅行方案数为 n2n!(n≥4) 种[1]122 .若采用穷举搜索法, 则需要考虑所有可能的情况, 再进行比 较, 找出最短路经.因其计算复杂度随城市数目的增加呈指数增长, 可能无法计算.这类问题称为完全 非确定性多项式问题 (N ondet erm inist ic Polynom ial Com plet e), 简称 N P 完全问题. T SP 问题在组合优化中是一个求最小的带权哈密顿回路问题[1]219, 哈密顿圈是一个完全无向图, 每 个顶点的度为 2.因此, 假设 n 个城市为 n 个顶点, 顶点集合 V ={1,2,…,n}, 各个城市之间有路连接 就称两个顶点间有一条边, 用 E ={X ij│(i,j),i,j=1,2,…,n}表示边的集合, 且 X ii=0.用 D (d ij) 表示 距离矩阵, D 是一个对称阵.x ij是一个 0-1 型变量, 且 x ij= 1, 0, 点 i 与点 否则 j 之间有边.由上述假设对 磁 收 稿 日 期 : 2006-05-22 基金项目: 山西省自然科学基金资助项目(20051006) 作 者 简 介 : 管 琳 (1981-), 女 , 硕 士 生 .主 要 从 事 神 经 网 络 算 法 与 应 用 研 究 .白 艳 萍 (1962-), 女 , 教 授 , 博 士 .硕 士 生 导 师 . (总第 112 期) 用分支定界算法求解旅行商问题(管琳等) 105 T SP 问题建立如下数学模型 ∑x ij = 2 j∈ v m in z = ∑ ∑x dij ij, i∈ vj∈ v 对所有 i∈ V , s.t . ∑ x ij ≥ 2 i∈ S ,j∈ v- s 对所有 S 炒 V ,3 ≤ S ≤ [ V 2 ], x ij ∈ {0,1} ij ∈ E . 以 4 个城市的 T SP 问题为例, 用上述模型求 T SP 的最短路径.随机地取距离矩阵 0 78 21 13 78 0 11 14 D= , 21 11 0 9 13 13 9 0 求解得到三组解, 这三组解分别构成 A ,B ,C 三个邻接矩阵(A ,B ,C 的邻接矩阵图如图 1~图 3 所示). 0110 0011 0101 1001 0011 1010 A= ,B = ,C= . 1001 1100 0101 0110 1100 1010 由计算可知, 最优目标函数值 z倡 =59.显然, 这是一个 0-1 的整数规划问题, 可以用分支定界法 求解. 1 2 1 2 1 2 4 3 图 1 A 的邻接矩阵图 F ig.1 A adjacent m atrix f igure 4 3 图 2 B 的邻接矩阵图 Fig.2 B adjacent m atrix f igure 4 3 图 3 C 的邻接矩阵图 F ig.3 C adjacent m atrix f igure 2分支定界算法 分支定界算法(Branch and Bound M ethod, B&B)由 L and Doig 等人于 20 世纪 60 年代提出, 其算法 思 想不仅适用于表达成整数线性规划(或混合整数线性规划)的问题, 也适用于几乎任何组合优化问 题[3] .它采用了类似分而治之的算法策略, 在分析一个组合最优化问题一切可行解的过程中, 采取了必 要的限制条件, 设法排除可行域中大量非最优解区域, 从而能够求解一些规模较大的问题[2].设有最小 化整数规划问题 P , 相应的松弛问题 P 0. m in z = c′x , m in z = c′x , P: A x ≤ b, x ≥ 0, x i为 整 数 ; P 0: A x ≤ b, x ≥ 0. 先求解 P 的松弛问题 P 0 .P 0 的最优解不符合 P 的整数条件, 则取其中一个非整数解分量 x i=ai, 在约束条件的基础上增加一个整数约束 x i≥[ai]+1 或 x i≤[ai], 得到 P 1 层的两个线性规划问题.分支 定界法就是将 P 0的可行域 F 通过每次增加一个整数约束, 分成两个子区域 F 1,F 2,F 1炒F ,F 2炒F , 称为 分支的方法.若子线性规划问题的解仍然不满足整数条件, 则重复上述过程; 若找到一个满足整数条件 的解, 则得到一个可行解, 那么它的目标函数值就是一个“界限”, 可作为衡量其他分支的一个依据, 称 之为“定界”.因为整数规划问题的可行解集是它的松弛问题可行解集的一个子集, 前者最优解的目标函 数值不会优于后者[1]20 , 所以对于那些目标函数值比上述“界限”差的后继问题可以不再考虑了.当然, 如 果在以后的分支过程中出现了更好的“界限”, 则以它取代原来的. 分支定界算法可以等价于在一个深度为 n 的二叉树上的搜索, 在二叉树的每一个节点上求解一个线 性规划问题.每一个子节点都是在其父节点线性规划问题基础上增加一个约束 x i≥[ai]+1 或 x i≤[ai] 的线性规划问题.因此, 子节点的解不优于父节点[4], 其叶节点中的最优者是原问题 P 的最优解. 可以看到, 随着问题规模的增加, 要进行约 20+21+22+…+2n 个线性规划问题的求解, 并且求解过 106 中 北 大 学 学 报(自然科学版) 2007 年第 2 期 程中要存储大量的数据, 进行多次比较, 因此对于较大规模的 T SP 问题此算法效率不高.经验表明, 在 可能的情况下, 根据对实际问题的了解, 事先选择一个合理的“界限”, 可以提高分支定界法的搜索效 率 . [1]120 文献 [3] 对上述分支定界法作了改进, 使得求解效率进一步提高.将 P 0 的最优值作为 P 的目标函 数值的一个上界, 记为 z珔; 而 P 的任意可行解的目标函数值将是的 z 一个下界, 记为 Z .在搜索过程中, - 还可以逐步减小 z珔和增大 z.因此, 该方法应设法找到最优解的上下界, 在上下界之外的节点不再考虑, - 称之为剪枝.一般遇到下列情况时需要剪枝: 1) P i无可行解; 2) P i的最优解符合整数约束, 则不必再分支; 3) P i的最优值 f珚i≥f珚, 通过比较, 若子问题不剪枝则继续分支[7] . 当所有子问题都剪枝了, 即没有需要处理的子问题时, 达到当前上界的可行解即原问题的最优解, 算法结束.由于子节点的解不优于父节点, 因此确定下界意义不大, 确定上界是一项十分有意义的 工 作[8] . 3实验结果与分析 本文利用 M A T L A B 6.5 优化工具箱中的 linprog 函数对 T SP 问题进行求解.实验数据由文献 [11] 给出, 如表 1 所示. 表 1分支定界算法实验结果与最优解对比 T ab.1 C o m par iso n bet w een B&B so lut io n and t h e best s o lut io n 实验数据 T ex t16 T ex t24 U lysses16 A tt48 E il101 分支定界最优解 3 .2 4.399 2 .1 5 3 5 4 .4 0 9 6 7 .0 6 8 1 最优解 3.2 4 .3 9 9 2 .1 2 6 3 .8 9 2 7 .8 1 1 图 416 个城市最优路径图 图 524 个城市最优路径图 F ig.4 Bes t t o ur o f 16 cit ies F ig.4 Best t o ur o f 24 cit ies 从图 4 和图 5 中可以看到, 分支定界算法对于解决小规模城市分布对称的问题是非常有效的. 图 6 是用分支定界算法求出的路径, 不是最优解.图 7 是该问题的最优路径.可以看到, 随着问题 规模的增大以及城市分布任意性的增加, 运算复杂度呈指数性增长, 运算量较大, 迭代过程中产生的误 差也较大, 运算结果不理想.Eil101 运算结果偏小, 主要原因在于约束条件不足, 使得路径中形成了多 个圈.根据实际问题, 可以考虑加入必要的约束条件, 避免形成奇数圈和偶数圈. (总第 112 期) 用分支定界算法求解旅行商问题(管琳等) 107 图 616 个不对称城市 B&B 算法路径图 F ig.6 T o ur o f 16 asy m m et r y cit ies by B&B 图 716 个不对称城市最优路径图 F ig.7 Best t o ur o f 16 asy m m et r y cit ies 参考文献: [1]胡运权.运筹学教程[M ].北京: 清华大学出版社, 1998: 209-219. [2]汪祖柱, 程家兴.求解组合优化问题的一种方法 分支定界法[J].安徽大学学报(自然科学版), 2004, 28(1): 10-14. Wang Zuzhu, Cheng Jiaxing.An algorithm on solving combinatorial optimization problems branch-and-bound method[J].Journal of Anhui U niversity Natural Science Edition, 2004, 28(1): 10-14.(in Chinese) [3]M attias Elf, Carsten Gutw enger, M ichael Jünger.Giovannni Rinaldi: Branch-and-Cut Algorithms for Combinatorial Optimization and T heir Implementation in ABACU S[M ], 2000: 163-172. [4]杜江, 孟香惠.一种改进的分支定界算法[J].数学杂志, 1998, 18: 55-58. Du Jiang, M eng Xianghui.An improved algorithm for branch-and-bound method[J].January of M ath, 1998, 18: 55-58.(in Chinese) [5]PEM Shutler.An improved branching rule for the symmetric traveling salesman problem [J].Operational Research Society, 2001, 52: 169-175. [6]全惠云.求解 T SP 的演化算法[J].湖南师范大学自然科学学报, 1999, 22(2): 27-34. Quan Huiyun.An evolutionary algorithm for T SP [J].Acta Science Natral U niversity Norm Hunan, 1999, 22(2): 27-34.(in Chinese) [7]吴祈宗.运筹学与最优化方法[M ].北京: 机械工业出版社, 2003: 180-191. [8]袁亚湘, 孙文瑜.最优化理论与方法[M ].北京: 科学出版社, 1997: 467-473,608-614. [9]白艳萍, 胡红萍.一个改进的弹性网络算法求解 T SP 问题[J].中北大学学报, 2005, 26(4): 235-238. Bai Yanping, Hu Hongping.A modified elastic net algorithm for traveling salesman problem[J].Journal of North U niversity of China, 2005, 26(4): 235-238.(in Chinese) [10]胡红萍, 胡红莉, 王建中.严格有向图 Hamilton 性质的研究[J].华北工学院学报, 2005, 26(2): 83-86. Hu Hongping, Hu Hongli, Wang Jianzhong.A sufficient and necessary condition digraph w ith directed hamiltonian path[J].Journal of North China Institute of T echnology, 2005, 26(2): 83-86.(in Chinese) [11]http://w ayne.cs.nthu.edu.tw /~roland/nn/index 2c[DB/OL ].html.

http://gamesbaby.net/fenzhixianjiesousuo/525.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有