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

doi:10.6040/j.issn.1672-3961.0.2015.127

摘要/Abstract

摘要： 针对大型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

王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.

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

参考文献

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

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed