﻿ 旅行商问题的一种选择性集成求解方法
 «上一篇 下一篇»
 山东大学学报(工学版)  2016, Vol. 46 Issue (1): 42-48  DOI: 10.6040/j.issn.1672-3961.0.2015.127 0

### 引用本文

WANG Lihong, LI Qiang. A selective ensemble method for traveling salesman problems[J]. Journal of Shandong University(Engineering Science), 2016, 46(1): 42-48. DOI: 10.6040/j.issn.1672-3961.0.2015.127.

### 文章历史

1.烟台大学计算机与控制工程学院, 山东 烟台 264005;
2.烟台大学经济管理学院, 山东 烟台 264005

A selective ensemble method for traveling salesman problems
WANG Lihong1, LI Qiang2
1. School of Computer and Control Engineering, Yantai University, Yantai 264005, Shandong, China;
2. School of Economy and Management, Yantai University, Yantai 264005, Shandong, China
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: artificial intelligence    selective ensemble learning    traveling salesman problem    maximum path    vertex insertion
0 引言

1 旅行商问题与2-opt 1.1 旅行商问题

 $c\left({{H^*}} \right)=\mathop {\min }\limits_H \sum\limits_{\left({{v_i},{v_j}} \right)\in H} {c\left({{v_i},{v_j}} \right).}$ (1)

1.2 2-exchange与2-opt

H=v1,v2,…vn,v1是一条线路,对于两个顶点vi,vj,2-交换(2-exchange)是指将线路中不相邻的两条边(vi,vi+1)和(vj,vj+1)换成(vi,vj)和(vi+1,vj+1),得到一条新线路[1]。如果c(vi,vi+1)+c(vj,vj+1)-c(vi,vj)-c(vi+1,vj+1)>0,则2-交换得到的线路是对原线路的改进。

 ${N_{{\rm{2opt}}}}\left(H \right)=\left\{ {{H_1} \in S:{2_{{\rm{ - opt}}}}\left({{H_1}} \right)=H} \right\}.$

2 算法设计

2-opt方法简单有效,经常应用于需要确定最优回路的组合问题中,因此采用2-opt方法作为提升回路质量的手段。将｛1,2,…,n｝的随机排列作为试算线路输入2-opt方法,得出的线路好于输入线路。对这些较好线路采用选择性集成策略,提出了扩大路径法来构造若干条极大路径。使用顶点插入法将剩余顶点和这些极大路径连接起来,构造出最初的线路H,希望H能出现在N2opt(H*)中。最后利用2-opt方法进行提升改进,给出最终线路。算法的流程图如图 1所示。

 图1 算法流程图 Fig. 1 Algorithm flow chart
2.1 选择性集成获取极大路径

(1)各边的投票数vote清0。

(2)从T中随机选取EMB个线路,每条线路t对所经过的边e=(vi,vj)进行投票:

 $vote\left({{v_i},{v_j}} \right)\leftarrow vote\left({{v_i},{v_j}} \right)+1.0c\left({{v_i},{v_j}} \right).$

(3)将各边投票数按从小到大排序,得到有序的投票序列v,重复的数值只保留一次。

(4)阈值thrd=v(round(length(v)*pos));％阈值为序列v的指定位置处的值。

(5)现有路径P清空。

(6)找出vote的最大值,记作g

(7)while g>=thrd

｛①将投票值等于g的边e=(x,y)按扩大路径法插入现有路径:

(a)如果x,y都不曾出现在现有路径中,如图 2(a),则新建一条路径(x,y);

(b)如果x,y中有一个(例如x)是现有路径的端点,另一个(y)不曾出现在现有路径中,如图 2(b),则将yx连接;

(c)如果x,y分别是两个路径的端点,如图 2(c),则将两个路径连接成一个路径;

(d)其余情况不再扩大路径,如图 2(d)

 图2 扩大路径法 Fig. 2 Expanding path method

②将边e的投票值清0。

③找出vote的最大值,仍记作g;｝

(8)返回极大路径的集合P

2.2 线路生成

 图3 顶点插入法 Fig. 3 Vertex insertion algorithm
 $c\left({{v_l},{v_{is}}} \right)+c\left({{v_{is}},{v_{l+1}}} \right)- c\left({{v_l},{v_{l+1}}} \right).$ (2)

(1)依次处理每个极大路径p1,p2,…pki=1;H=Cm

(2)设极大路径pi的两个端点为si,ti,记作pi=[si,ti],其长度记为Len(pi)。

(3)考虑H的每条边el=(vl,vl+1):％注:将pi=[si,ti]插入回路H

①如果vl,vl+1是普通顶点,则计算

 $\begin{array}{l} c\left({{v_l},{p_i}} \right)+c\left({{p_i},{v_{l+1}}} \right)- c\left({{v_l},{v_{l+1}}} \right)- \\ \min \left\{ {c\left({{v_l},{p_i}} \right)+c\left({{t_i},{v_{l+1}}} \right)+{\mathop{\rm len}\nolimits} \left({{p_i}} \right),c\left({{v_l},{t_i}} \right)+c\left({{s_i},{v_{l+1}}} \right)+{\mathop{\rm len}\nolimits} \left({{p_i}} \right)} \right\} - c\left({{v_l},{v_{l+1}}} \right). \end{array}$ (3)

②如果vl是超级顶点vl=[ul,rl],则(3)式中c(vl,si)=c(rl,si),c(vl,ti)=c(rl,ti)。

③如果vl+1是超级顶点,则(3)式中c(si,vl+1)和c(ti,vl+1)的计算类似。

(4)选取使(3)式取最小值的边el,将pi按(3)式取最小值时的放置方式插入el,即pi=[si,ti]或pi=[ti,si]。更新回路H,i=i+1,回到2,直到所有极大路径处理完毕。

(5)返回H

3 试验与结果分析

 $ATT\left({{z_i},{z_j}} \right)=\left\lceil {\sqrt {\left({{{\left({{x_i} - {x_j}} \right)}^2}+{{\left({{y_i} - {y_j}} \right)}^2}} \right)/10.0} } \right\rceil$

(1)以eil51为例,随机生成200个｛1,2,…,51｝的排列,每个排列看作是一个可行解。对每个可行解进行2-opt提升,共得到200个较好解,各个解的最小值min、最大值max、平均值mean、方差var见表 2,均值与方差已取整。表 2中同时列出其余TSP实例的较好解情况,其中Pr76(1)和Pr76(2)是Pr76的两组较好解,每组均包含200个解。

(2)试验步骤2选择性集成与线路生成

 图4 集成算法在fl1400上的运行时间 Fig. 4 Running time of the ensemble algorithm on fl1400
4 结语

 [1] REGO C, GLOVER F. Local search and metaheuristics[M]. New York: Springer Science+Business Media, 2007:309-368.(5) [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.(1) [3] LIN S, KERNIGHAN B W. An effective heuristic algorithm for the traveling salesman problem[J]. Operations Research, 1973, 21(3):972-989.(1) [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.(1) [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.(1) [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.(1) [7] APPLEGATE D, BIXBY R, CHVATAL V, et al. Finding tours in the TSP[R]. Bonn: University of Bonn, 1999.(1) [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.(1) [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.(1) [10] DIETTERICH T. Machine learning research: four current directions[J]. AI Magazine,1997, 18(4):97-136.(1) [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.(1) [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.(1) [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.(1) [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.(2) [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.(2) [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.(2) [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.(1) [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.(1) [19] PUNNEN A, MARGOT F, KABADI S. TSP heuristics: domination analysis and complexity[J]. Algorithmica, 2003, 35:111-127.(1) [20] GUTIN G, YEO A. Exponential neighborhoods and domination analysis for the TSP[M]. New York: Springer Science+Business Media, 2007: 223-256.(1)