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

doi:10.6040/j.issn.1672-3961.0.2015.127

Abstract

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

CLC Number:

TP301.6

WANG Lihong, LI Qiang. A selective ensemble method for traveling salesman problems[J].JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 42-48.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 10

[1]	CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[2]	WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[3]	LIU Xin ¹, SONG Sili ¹, WANG Xinhong ². [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[4]	. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[5]	CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[6]	. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 131 -136 .
[7]	LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[8]	ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .
[9]	ZHAO Zhi-guang,WANG Deng-jie,TIAN Yun-fei . Roadbed settlement based on the gray theory[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 86 -88 .
[10]	YAO Zhan-yong,SHANG Qing-sen,ZHAO Zhi-zhong,JIA Zhao-xia . The influence analysis of the semirigid asphalt pavement configuration stress and distortion by interface conditions[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 93 -99 .

A selective ensemble method for traveling salesman problems

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 5

Metrics

Comments

Recommended 10

[1]	DAI Hongwei, YANG Yu, ZHONG Zhaoman, LI Cunhua. Improved quantum crossover immune clonal algorithm and its application [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 17-21.
[2]	ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*. Heuristic construction method for the initial tour of the Lin-Kernighan algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 30-35.
[3]	CAI Rong-ying, WANG Li-jin, WU Chao, ZHONG Yi-wen*. A kind of iterative improvement based ant colony optimization algorithm for the traveling salesman problem [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 6-11.
[4]	XIA Hui1, WANG Hua1, CHEN Xi2. A kind of ant colony parameter adaptive optimization algorithm based on particle swarm optimization thought [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 26-30.
[5]	DONG Ai-Feng, DIAO Ge-Ji, SCHOMMER Christoph. A fingerprint engine for author profiling [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 27-31.