您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(工学版)》

山东大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (1): 42-48.doi: 10.6040/j.issn.1672-3961.0.2015.127

• 机器学习与数据挖掘 • 上一篇    下一篇

旅行商问题的一种选择性集成求解方法

王立宏1,李强2   

  1. 1.烟台大学计算机与控制工程学院, 山东 烟台 264005;
    2.烟台大学经济管理学院, 山东 烟台 264005
  • 收稿日期:2015-05-06 出版日期:2016-02-20 发布日期:2015-05-06
  • 作者简介:王立宏(1970- ),女,吉林镇赉人,教授,博士,主要研究方向为数据挖掘. E-mail: wanglh_000@163.com
  • 基金资助:
    国家自然科学基金资助项目(71372122,61403328);山东省自然科学基金资助项目(ZR2013FM011)

A selective ensemble method for traveling salesman problems

WANG Lihong1, LI Qiang2   

  • Received:2015-05-06 Online:2016-02-20 Published:2015-05-06

摘要: 针对大型TSP(traveling salesman problem)实例很难找到最优解的问题,提出了一种选择性集成求解方法。首先通过扩大路径法来选择集成多个较好解,构造出若干个极大路径;然后采用顶点插入法将剩余顶点和这些极大路径连接成一个哈密顿回路;最后使用2-opt方法对该回路进行提升。试验结果表明,算法在5个TSP实例上得出的最好解的最大偏差为1.69%,说明本算法可以有效求解TSP。

关键词: 选择性集成学习, 顶点插入, 旅行商问题, 人工智能, 极大路径

Abstract: To solve the problem of finding the optimum solution of very large TSP(traveling salesman problem), a selective ensemble method was proposed. Firstly, expanding path method was used to selective integrate some high quality solutions, and several maximum paths were obtained. And then vertex insertion method was employed to connect these paths and the remainder vertices to form a Hamiltonian tour. Finally, the tour was improved by 2-opt method. Experimental results on 5 TSP instances showed that the maximal bias was 1.69%, and the effectiveness was proved.

Key words: selective ensemble learning, artificial intelligence, maximum path, traveling salesman problem, vertex insertion

中图分类号: 

  • TP301.6
[1] REGO C, GLOVER F. Local search and metaheuristics[M]. New York: Springer Science+Business Media, 2007:309-368.
[2] DANTZIG G B, FULKERSON D R, JOHNSON S M. Solution of a large-scale traveling-salesman problem[J]. Operations Research, 1954, 2(4):393-410.
[3] LIN S, KERNIGHAN B W. An effective heuristic algorithm for the traveling salesman problem[J]. Operations Research, 1973, 21(3):972-989.
[4] 吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1329-1333. WU Bin, SHI Zhongzhi. An ant colony algorithm based partition algorithm for TSP[J]. Chinese Journal of Computers, 2001, 24(12):1329-1333.
[5] 孟佳娜,王立宏.具有自识别能力的遗传算法求解旅行商问题[J].计算机工程与应用,2006,42(13):51-53. MENG Jiana, WANG Lihong. A genetic algorithm with self-identify capability to solve TSP[J]. Computer Engineering and Applications, 2006, 42(13):51-53.
[6] 孟佳娜,王立宏.基于组织调整的进化算法求解TSP问题[J].计算机工程与应用,2006,42(12):57-59. MENG Jiana, WANG Lihong. Evolutionary algorithm based on organization adjustment to solve TSP[J]. Computer Engineering and Applications, 2006, 42(12):57-59.
[7] APPLEGATE D, BIXBY R, CHVATAL V, et al. Finding tours in the TSP[R]. Bonn: University of Bonn, 1999.
[8] 杨辉,康立山,陈毓屏.一种基于构建基因库求解TSP问题的遗传算法[J]. 计算机学报,2003,26(12):1753-1758. YANG Hui, KANG Lishan, CHEN Yuping. A gene-based genetic algorithm for TSP[J]. Chinese Journal of Computers, 2003, 26(12):1753-1758.
[9] 申铉京,刘阳阳,黄永平,等. 求解TSP问题的快速蚁群算法[J]. 吉林大学学报(工学版),2013,43(1):147-151. SHEN Xuanjing, LIU Yangyang, HUANG Yongping, et al. Fast ant colony algorithm for solving traveling salesman problems[J]. Journal of Jilin University(Engineering and Technology Edition), 2013, 43(1):147-151.
[10] DIETTERICH T. Machine learning research: four current directions[J]. AI Magazine,1997, 18(4):97-136.
[11] ZHOU Z H, WU J X, TANG W. Ensembling neural networks: many could be better than all[J]. Artificial Intelligence, 2002, 137(1-2):239-263.
[12] 张春霞, 张讲社. 选择性集成学习算法综述[J]. 计算机学报, 2011, 34(8):1399-1410. ZHANG Chunxia, ZHANG Jiangshe. A survey of selective ensemble learning algorithms[J]. Chinese Journal of Computers, 2011, 34(8):1399-1410.
[13] 毕凯,王晓丹,姚旭,等. 一种基于Bagging和混淆矩阵的自适应选择性集成[J]. 电子学报,2014, 42(4):711-716. BI Kai, WANG Xiaodan, YAO Xu, et al. Adaptively selective ensemble algorithm based on bagging and confusion matrix[J]. Acta Electronica Sinica, 2014, 42(4):711-716.
[14] 郝红卫,王志彬,殷绪成,等. 分类器的动态选择与循环集成方法[J].自动化学报,2011, 37(11):1290-1295. HAO Hongwei, WANG Zhibin, YIN Xucheng, et al. Dynamic selection and circulating combination for multiple classier systems[J]. Acta Automatica Sinica, 2011, 37(11):1290-1295.
[15] JIA J H, XIAO X, LIU B X, et al. Bagging-based spectral clustering ensemble selection[J]. Pattern Recognition Letters, 2011, 32:1456-1467.
[16] WANG L H, WANG X L. Eigenvectors selection for spectral clustering based on semi-supervised selective ensemble[J]. Journal of Computational Information Systems, 2014, 10(9):3701-3710.
[17] 潘吴斌,程光,郭晓军,等. 基于选择性集成策略的嵌入式网络流特征选择[J]. 计算机学报,2014,37(10):2128-2138. PAN Wubin, CHENG Guang, GUO Xiaojun, et al. An embedded feature selection using selective ensemble for network traffic[J]. Chinese Journal of Computers, 2014, 37(10):2128-2138.
[18] 汤健,柴天佑,丛秋梅,等. 基于EMD和选择性集成学习算法的磨机负荷参数软测量[J]. 自动化学报,2014, 40(9):1853-1866. TANG Jian, CHAI Tianyou, CONG Qiumei, et al. Soft sensor approach for modeling mill load parameters based on EMD and selective ensemble learning algorithm[J]. Acta Automatica Sinica, 2014, 40(9):1853-1866.
[19] PUNNEN A, MARGOT F, KABADI S. TSP heuristics: domination analysis and complexity[J]. Algorithmica, 2003, 35:111-127.
[20] GUTIN G, YEO A. Exponential neighborhoods and domination analysis for the TSP[M]. New York: Springer Science+Business Media, 2007: 223-256.
[1] 易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.
[2] 戴红伟, 杨玉, 仲兆满, 李存华. 改进量子交叉免疫克隆算法及其应用[J]. 山东大学学报(工学版), 2015, 45(2): 17-21.
[3] 曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.
[4] 蔡荣英,王李进,吴超,钟一文*. 一种求解旅行商问题的迭代改进蚁群优化算法[J]. 山东大学学报(工学版), 2012, 42(1): 6-11.
[5] 董乃鹏 赵合计 SCHOMMER Christoph. 作者写作特征提取引擎[J]. 山东大学学报(工学版), 2009, 39(5): 27-31.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 程代展,李志强. 非线性系统线性化综述(英文)[J]. 山东大学学报(工学版), 2009, 39(2): 26 -36 .
[2] 王勇, 谢玉东.

大流量管道煤气的控制技术研究

[J]. 山东大学学报(工学版), 2009, 39(2): 70 -74 .
[3] 刘新1 ,宋思利1 ,王新洪2 . 石墨配比对钨极氩弧熔敷层TiC增强相含量及分布形态的影响[J]. 山东大学学报(工学版), 2009, 39(2): 98 -100 .
[4] 田芳1,张颖欣2,张礼3,侯秀萍3,裘南畹3. 新型金属氧化物薄膜气敏元件基材料的开发[J]. 山东大学学报(工学版), 2009, 39(2): 104 -107 .
[5] 陈华鑫, 陈拴发, 王秉纲. 基质沥青老化行为与老化机理[J]. 山东大学学报(工学版), 2009, 39(2): 125 -130 .
[6] 赵延风1,2, 王正中1,2 ,芦琴1,祝晗英3 . 梯形明渠水跃共轭水深的直接计算方法[J]. 山东大学学报(工学版), 2009, 39(2): 131 -136 .
[7] 李士进,王声特,黄乐平. 基于正反向异质性的遥感图像变化检测[J]. 山东大学学报(工学版), 2018, 48(3): 1 -9 .
[8] 赵科军 王新军 刘洋 仇一泓. 基于结构化覆盖网的连续 top-k 联接查询算法[J]. 山东大学学报(工学版), 2009, 39(5): 32 -37 .
[9] 赵治广,王登杰,田云飞 . 基于灰色理论的路基沉降研究[J]. 山东大学学报(工学版), 2007, 37(3): 86 -88 .
[10] 姚占勇,商庆森,赵之仲,贾朝霞 . 界面条件对半刚性沥青路面结构应力分布的影响[J]. 山东大学学报(工学版), 2007, 37(3): 93 -99 .