{'fraction_non_alphanumeric': 0.04345211722260903, 'fraction_numerical': 0.014621178555604785, 'mean_word_length': 4.4859375, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.


Introduction
The travelling salesman problem (TSP) is a well-known combinatorial optimization problem with various real-life applications, such as transportation, robots routing, biology, circuit design. Given n cities as well as the distance d ij between each pair of cities i and j, the TSP aims to find a cheapest tour which starts from a beginning city (arbitrarily chosen), visits each city exactly once, and finally returns to the beginning city. This problem is NP-hard, thus being extremely difficult from the viewpoint of theoretical computer science.
Due to its importance in both theory and practice, many algorithms have been developed, mostly based on traditional operations research (OR) methods. Among the existing TSP algorithms, the best exact solver Concorde [3] succeeded in demonstrating optimality of an Euclidean TSP instance with 85,900 cities, while the leading heuristics [17] and [40] are capable of obtaining near-optimal solutions for instances with millions of cities. However, these algorithms are very complicated, which consist of many hand-crafted rules and heavily rely on expert knowledge, thus being difficult to generalize to other combinatorial optimization problems.
To overcome those limitations, recent years have seen a number of machine learning (ML) based algorithms being proposed for the TSP (briefly reviewed in the next section), which attempt to automate the search process by learning mechanisms. This type of methods do not rely heavily on expert knowledge, can be easily generalized to various combinatorial optimization problems, thus become a promising research direction.
For the TSP, existing ML based algorithms can be roughly classified into two categories, i.e., (1) supervised learning (SL) algorithms which attempt to discover common patterns supervised by pre-computed TSP solutions. (2) reinforcement learning (RL) algorithms which try to learn during the interaction with the environment (without pre-computed solutions).
Once well trained, SL models are able to provide useful information that significantly speeds up the search of high-quality TSP solutions. However, the performance of a pre-trained model of fixed size may decrease drastically while tackling TSP instances of different sizes, since the distributions of the training instances are very different from the test instances. On the other hand, training SL models generally requires a large number of pre-computed optimal (at least high-quality) TSP solutions, being unaffordable for large-scale TSP instances. These drawbacks seriously limit the usage of SL on large-scale TSP instances.
However, we believe the idea of discovering common patterns in a supervised manner is valuable. If we can train a small-scale SL model within reasonable time and find a way to smoothly generalize it to large-scale cases (without precomputing a large number of solutions again), it is hopeful to inherit the advantages of SL while avoiding its drawbacks. Motivated by this idea, we develop a series of techniques, in order to improve the generalization ability of the model trained by SL. Furthermore, we combine SL and RL to form a hybrid algorithm, which performs favorably with respect to the existing ML based TSP algorithms. Overall, the main contributions are summarized as follows.
• Methodologies: At first, we train a small-scale (with size m) model by supervised learning, based on a graph convolutional residual network with attention mechanism (Att-GCRN). Once well trained, given a TSP instance with m vertices, the model is able to build a heat map over the edges. Then, we try to smoothly generalize this model to handle large instances. For this purpose, given a large-scale TSP instance, we repeatedly use a graph sampling method to extract a sub-graph with exactly m vertices, then con-vert it to a standard TSP instance, and call the pre-trained model to build a sub heat map. Finally, all the sub heat maps are merged together, to get a complete heat map over the original graph. Although the Att-GCRN is somewhat similar to the network in [19], to our best knowledge, the graph sampling, graph converting and heat maps merging techniques are firstly developed for the TSP in this paper, which significantly improve the generalization ability of the trained model. Furthermore, based on the merged heat map, we use a RL based approach, i.e., Monte Carlo tree search (MCTS), to search high-quality solutions. To our best knowledge, there are two existing works [36] and [43] which also use MCTS to solve the TSP. However, they are both constructive approaches, where each state is a partial TSP tour, and each action adds a city to increase the partial tour. By contrast, our MCTS method is a conversion based approach, where each state is a complete tour, and each action converts the current state to a new complete tour. Therefore, our method is very different from the existing MCTS algorithms.
• Results: We carry out experiments on a large number of TSP instances with up to 10,000 cities (one order of magnitude larger than the instances used to evaluate the existing ML algorithms). On all the data sets, our new algorithm is able to obtain optimal or near-optimal solutions within reasonable time, clearly outperforming all the existing learning based algorithms.

Related works
In this section, we briefly review the existing ML based algorithms on the TSP, and then extend to several other highly related problems. Non-learned methods are omitted, interested readers please find in [3], [31], [17] and [40] for an overlook of the leading TSP algorithms. The idea of applying ML to solve the TSP dated back to several decades ago [18], but becomes a hot and promising topic only in recent years. A number of ML based TSP algorithms have been developed, which can be classified into two categories.
Supervised learning (SL) methods: (author?) [41] introduced a pointer network which consists of an encoder and a decoder, both using recurrent neural network (RNN). The encoder parses each TSP city into an embedding, and then the decoder uses an attention model to predict the probability distribution over the candidate (unvisited) cities. (author?) [29] proposed a supervised approach, which trains a graph neural network (GNN) to predict an adjacency matrix (heat map) over the cities, and then attempts to convert the adjacency matrix to a feasible TSP tour by beam search (OR based method). (author?) [19] followed this framework, but chose deep graph convolutional networks (GCN) to build heat map, and then constructed tours via highly parallelized beam search. (author?) [43] trained a graph neural network (GNN) to capture the local and global graph structure, based on which they used a MCTS procedure to construct TSP tours. These SL based methods require a large number of pre-computed TSP solutions, thus being difficult to directly generalize to large-scale instances.
Reinforcement learning (RL) methods: To overcome the drawback of SL, several groups chose RL instead of SL. For example, (author?) [4] implemented an actor-critic RL architecture, which uses the tour length as a reward, to guide the search towards promising area. (author?) [21] proposed a framework which maintains a partial tour and repeatedly calls a RL model to select the most relevant city to add to the partial tour, until forming a complete TSP tour. (author?) [11] also implemented an actor-critic neural network, and chose Sinkhorn policy gradient to learn policies by approximating a double stochastic matrix. Concurrently, [9], [22] both proposed a graph attention network (GAN), which incorporates attention mechanism with RL to auto-regressively improve the quality of the obtained solution.
In addition to the works focused on the classic TSP, there are several ML based methods recently proposed for other related problems, such as the decision TSP [30], the multiple TSP [20], and the vehicle routing problem [28], [7] and [26], etc. For an overall survey, please refer to [5] and [13].

Methods Preliminaries
In this paper, we focus on the two-dimensional Euclidean TSP, which is formulated as an undirected graph G(V, E), where V (with |V | = n) denotes the set of vertices (each vertex corresponds to a city), and E denotes the set of edges. Without loss of generality, assume all the vertices are distributed within a two dimensional unit square, i.e., for each vertex i ∈ V , its coordinates x i and y i both belong to [0, 1], and the distance d ij is defined as the Euclidean distance between vertices i and j. Furthermore, corresponding to graph G, its heat map is defined as a n×n matrix P , whose element P ij ∈ [0, 1] denotes the probability of edge (i, j) belonging to the optimal TSP solution.
As a preliminary step, we at first train (off-line learning) a graph convolutional residual neural network with attention mechanisms (denoted by Att-GCRN for short, whose architecture is described in the full version of this paper 1 ), with fixed input size m (a parameter). To train the model, 990,000 TSP instances with m vertices are randomly generated as the train set, and the solutions produced by the exact solver Concorde [1] are used as the ground-truth solutions. Once well trained, given a new TSP instance with m vertices (randomly distributed within an unit square), the model is able to build a heat map, which estimates the probability P ij of each edge (i, j) belonging to the optimal solution.

Pipeline
Given a TSP instance of arbitrarily large size, the pipeline for solving this instance is shown in Fig. 1, which consists of three main steps. Respectively, the first step (off-line learning) uses a graph sampling method to extract from the original graph a number of sub-graphs (each exactly consists of m vertices), and then uses the pre-trained Att-GCRN model to build a sub heat map corresponding to each sub-graph. After that, the second step tries to merge all the sub heat maps into Building and merging heat maps The pre-trained model is able to build a heat map of a TSP instance with m vertices. However, it can not be directly used to handle instances of different size. To deal with this issue, an optional approach is to train a series of models with different sizes, like the choice of [19]. Unfortunately, this approach seems unreasonable for very large TSP instances, since the supervised learning process requires a large number of pre-computed optimal (at least high-quality) solutions, being unaffordable for large-scale TSP instances. To avoid repetitively training models, in this paper we develop a series of techniques (illustrated in Fig. 2 and described as follows), to extend the predication ability of the fix-sized model to arbitrarily large TSP instances.
Graph sampling The graph sampling method is used to extract a number of sub-graphs (each with m vertices) from the original graph G. To do this, for each vertex i ∈ V or each edge (i, j) ∈ E, let O i or O ij (initialized to 0) respectively denote the times that vertex i (or edge (i, j)) belongs to an extracted sub-graph. Then, at each iteration, we choose the vertex i with the minimal value of O i (randomly choose one if there are multiple such vertices) as the clustering center, and use the k-nearest neighbors algorithm [10] to extract a sub-graph G which consists of exactly m vertices (including the clustering center). Then, for each vertex i or each edge Above process is repeated, until the minimal value of O i reaches a lower bound ω (a pre-defined parameter). Notice that the extracted sub-graphs may overlap, i.e., any vertex or edge may belong to different sub-graphs.
Graph converting For each instance of the train set, all the vertices are distributed randomly within an unit square. To make sure the extracted sub-graph G also meets this distribution, we should convert it to a new graph G . For this purpose, let x min = min  max(x max −x min ,y max −y min ) be an amplification factor. Then, for each vertex i ∈ G , we convert its coordinates ( After that, sub-graph G is converted to a new graph G .
Building sub heat maps For each converted sub-graph G , the coordinates of the m vertices are fed into the pre-trained Att-GCRN model, to build a sub heat map over G .
Merging sub heat maps Above two steps are repeated, thus we can obtain a number (denoted by I) of sub heat maps. Finally, we try to merge them into a complete heat map. To do this, for each edge (i, j) of the original graph G, we estimate its probability P ij of belonging to the optimal TSP solution as follows.
where P ij (l) denotes the probability of edge (i, j) (after conversion) belonging to the optimal solution of the lth converted sub-graph G .
After merging all the sub heat maps, we obtain a complete heat map over the original graph G. Then, all the edges with P ij < 10 −4 are marked as unpromising edges, which are eliminated directly to reduce the search space.

Reinforcement learning for solutions optimization
Based on the heat map obtained above, we develop a reinforcement learning based approach to search high-quality solutions. The search process is considered as a Markov Decision Process (MDP), which starts from an initial state π, and iteratively applies an action a to reach a new state π * . The details are described as follows.
States and actions In our implementation, each state corresponds to a complete TSP solution, i.e., a permutation π = (π 1 , π 2 , . . . , π n ) of all the vertices. Each action a is a transformation which converts a given state π to a new state π * . Since each TSP solution consists of a subset of n edges, any action could be viewed as a k-opt (2 ≤ k ≤ n) transformation, which deletes k edges at first, and then adds k different edges to form a new tour.
Obviously, each action can be represented as a series of 2k sub-decisions (k edges to delete and k edges to add). This representation method is straightforward, but seems a bit redundant, since the deleted edges and added edges are highly relevant, while arbitrarily deleting k edges and adding k edges may result in an unfeasible solution. To overcome this drawback, we develop a compact method to represent an action, which consists of only k sub-decisions. Formally, an action can be represented as a = (a 1 , b 1 , a 2 , b 2 , . . . , a k , b k , a k+1 ), where k is a variable and the final vertex must coincide with the first vertex, i.e. a k+1 = a 1 . Each action corresponds to a k-opt transformation, which deletes k edges, i.e., (a i , b i ), 1 ≤ i ≤ k, and adds k edges, i.e., (b i , a i+1 ), 1 ≤ i ≤ k, to reach a new state. Notice that not all these elements are optional. Once a i is known, b i can be uniquely determined without any optional choice (explained and exemplified in the full version of this paper). Therefore, to determine an action we should only decide a series of k sub-decisions, i.e., the k vertices a i , 1 ≤ i ≤ k. Additionally, an action involving an unpromising edge (b i , a i+1 ), i.e., P biai+1 < 10 −4 , is marked as an unpromising action and eliminated directly.
Intuitively, this compact representation method brings advantages in two-folds: (1) fewer (only k, not 2k) subdecisions need to be made; (2) the resulting states are necessarily feasible solutions.
State initialization For state initialization, we choose a constructive procedure, which starts from an arbitrarily chosen begin vertex π 1 , iteratively selects a vertex π i , 2 ≤ i ≤ n among the candidate (unvisited) vertices and adds it to the end of the partial tour, until forming a complete tour π = (π 1 , π 2 , . . . , π n ). More precisely, at the ith iteration, if there are more than one candidate vertices, each candidate vertex j is chosen with a probability proportional to exp(P πij ), while all the candidate vertices share a total probability of 1.
Enumerating within small neighborhood To maintain the generalization ability of our approach, we avoid to use complex hand-crafted rules, such as the α-nearness criterion in [15] and the POPMUSIC strategy in [40], which have proven to be highly effective on the TSP, but heavily depend on expert knowledge. Instead, starting from a new state, we at first use a straightforward method to search within a small neighborhood. More precisely, the method examines one by one the promising actions with k = 2, and iteratively applies the first-met improving action which leads to a better state, until no improving action with k = 2 is found. This simple method is able to efficiently and robustly converge to a local optimal state.
Targeted sampling within enlarged neighborhood Once no improving action is found within the small neighborhood, we switch to an enlarged neighborhood which consists of the actions with k > 2. Unfortunately, there are generally a huge number of actions within the enlarged neighborhood (even after eliminating the unpromising ones), being impossible to enumerate them one by one. Therefore, we choose to sample a subset of promising actions (guided by RL) and iteratively select an action to apply, to reach a new state. Following this idea, we choose the Monte Carlo tree search (MCTS) as our learning framework. Inspired by the works in [8], [6], [37] and [38], our MCTS procedure (outlined in Fig. 3) consists of four steps, i.e., (1) Initialization, (2) Simulation, (3) Selection, and (4) Back-propagation, which are respectively designed as follows.
Initialization: We define two n × n symmetric matrices, i.e., a weight matrix W whose element W ij (initialized to 100 × P ij ) controls the probability of choosing vertex j after vertex i, and an access matrix Q whose element Q ij (initialized to 0) records the times that edge (i, j) is chosen during simulations. Additionally, a variable M (initialized to 0) is used to record the total number of actions already simulated. Note that this initialization step should be executed only once at the beginning of the whole process of MDP.
Simulation: Given a state π, we use the simulation process to probabilistically generate a number of actions. As explained before, each action is represented as a = (a 1 , b 1 , a 2 , b 2 , . . . , a k , b k , a k+1 ), containing a series of subdecisions a i , 1 ≤ i ≤ k (k is also a variable, and a k+1 = a 1 ), while b i could be determined uniquely once a i is known. Once b i is determined, for each edge (b i , j), j = b i , we use the following formula to estimate its potential Z bij (the higher the value of Z bij , the larger the opportunity of edge (b i , j) to be chosen): Where Ω bi = j =b i W b i j j =b i 1 denotes the averaged W bij value of all the edges relative to vertex b i . In this formula, the left part emphasizes the importance of the edges with high W bij values (to enhance the intensification feature), while the right part ln (M + 1) Q bij + 1 prefers the rarely examined edges (to enhance the diversification feature). α is a parameter used to achieve a balance between intensification and diversification, and the term "+1" is used to avoid a minus numerator or a zero denominator.
To make the sub-decisions sequently, we at first choose a 1 randomly, and determine b 1 subsequently. Recursively, once a i and b i are known, a i+1 is decided as follows: (1) if closing the loop (connecting b i to a 1 ) would lead to an improving action, or i ≥ 10, let a i+1 = a 1 . (2) otherwise, consider the vertices with W bij ≥ 1 as candidate vertices, forming a set X (excluding a 1 and the vertex already connected to b i ). Then, among X each vertex j is selected as a i+1 with probability P j , which is determined as follows: Once a i+1 = a 1 , we close the loop to obtain an action. Similarly, more actions are generated (forming a sampling pool), until meeting an improving action which leads to a better state, or the number of actions reaches its upper bound (controlled by a parameter H).
Selection: During above simulation process, if an improving action is met, it is selected and applied to the current state π, to get a new state π new . Otherwise, if no such action exists in the sampling pool, it seems difficult to gain improvement within the current search area. Then, the MDP jumps to a random state (using the state initialization method described above), which serves as a new starting state.
Back-propagation: The value of M as well as the elements of matrices W and Q are updated by back propagation as follows. At first, whenever an action is examined, M is increased by 1. Then, for each edge (b i , a i+1 ) which appears in an examined action, let Q biai+1 increase by 1. Finally, whenever a state π is converted to a better state π new by applying action a = (a 1 , b 1 , a 2 , b 2 , . . . , a k , b k , a k+1 ), for each edge (b i , a i+1 ), 1 ≤ i ≤ k, let: (6) Where β is a parameter used to control the increasing rate of W biai+1 . Notice that we update W biai+1 only when meeting a better state, since we want to avoid wrong estimations (even in a bad action which leads to a worse state, there may exist some good edges (b i , a i+1 )). With this backpropagation process, the weight of the good edges would be increased to enhance its opportunity of being selected, thus the sampling process would be more and more targeted. W and Q are symmetric matrices, thus let W ai+1bi = W biai+1 and Q ai+1bi = Q biai+1 always.
Termination condition The MCTS iterates through the simulation, selection and back-propagation steps, until no improving action exists among the sampling pool. Then, the MDP jumps to a new state, and launches a new round of search within small and enlarged neighborhood again. This process is repeated, until the allowed time (controlled by a parameter T ) has been elapsed. Then, the best found state is returned as the final solution.

Experiments
To evaluate the performance of our method, we program the algorithm for building heat maps in Python, and program the MCTS algorithm in C++ language 2 . Then, we carry out experiments on a large number of TSP instances, and make comparisons with eight newest learning based baselines, as well as three strong non-learning algorithms (the programming and training details about the baselines are given in the full version of this paper). Notice that, for the baselines, we just directly download and rerun the source codes, based on the pre-trained models (only for learning based baselines) which are publicly available. To ensure fair comparisons, all the learning based baselines as well as our new algorithm are uniformly executed on one GTX 1080 Ti GPU (to fully utilize the computing resources, as many instances as possible are executed in parallel). For the three non-learning algorithms, their source codes currently do not support running on GPU, thus we re-run them on one Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz (with 8 cores), and list the results just for indicative purposes. Notice that our method is a learning based algorithm, thus we do not aim to strictly outperform the non-learning algorithms.

Data sets
We use two data sets: (1) Set 1 3 , which is divided into three subsets, each containing 10,000 automatically generated 2D-Euclidean TSP instances, respectively with n = 20, 50, 100. This data set is widely used by the existing learning based algorithms. (2) Set 2, following the same rules, we newly generate 400 larger instances, i.e., 128 instances respectively with n = 200, 500, 1000, and 16 instances with n = 10000.

Parameters
As described before, our method relies on six hyper parameters (m, ω, α, β, H and T ). For parameter m which controls the size of the pre-trained model, we set m = 20 for the small instances of data set 1, and set m = 50 for the large instances of data set 2. For the following four parameters, we uniformly choose ω = 5, α = 1, β = 10, H = 10n as the default settings. Finally, for parameter T which controls the termination time, we respectively set T = 10n and T = 40n milliseconds for each instance of data set 1 and data set 2, to ensure that our algorithm elapses no more time than the best (in terms of solution quality) learning algorithm proposed in each reference paper.
Results on data set 1 Table 1 presents the results obtained by our algorithm (Att-GCRN+MCTS) on data set 1, with respect to the existing baselines. Respectively, the first three lines list two exact solvers, i.e., Concorde [1] 4 and Gurobi 5 , as well as one strong heuristic LKH3 [17]. The following eight lines are all learning based algorithms which combine traditional operations for post-optimization. There are also several End-to-End ML models in the literature, but they all produce very poor results, thus being omitted here. For the columns, column 1 indicates the methods, while column 2 indicates the type of each algorithm. Columns 3-5 respectively give the average tour length, average gap in percentage w.r.t. Concorde, and the total clock time used by each algorithm on all the 10,000 instances with n = 20. To ensure fair comparisons, for some learning baselines, the original parameters (such as the width of beam search) are adapted to prolong the total running time. These adapted results are indicated in blue color in the table. For our method (last line), the time is divided into two parts, i.e., the time for building heat maps plus the time for running MCTS. Columns 6-8, 9-11 respectively give the same information on the instances with n = 50 and 100.
As shown in Table 1, the three non-learning algorithms obtain good results on all the test instances, while the existing learning based algorithms all struggle to match optimality on the instances with n = 100. Compared to these baselines, our algorithm performs quite well, which succeeds in matching the ground-truth solutions (reported by Concorde) on most of these instances, corresponding to an average gap of 0.0000%, 0.0145%, 0.0370% respectively on the instances with n = 20, 50, 100. The total runtime of our method remains competitive with respect to all the learning baselines only except two (with greedy heuristics), which are deterministic thus the results cannot be improved by prolonging the runtime.

Results on data set 2
At first, we summarize in Table 2 the results obtained on the 384 instances with n = 200, 500, 1000. Concorde and LKH3 still perform well on these instances, while Gurobi performs well on the instances with n=200 and 500, but fails to terminate within reasonable time on the instances with 1000 cities. For the learning baselines, they all produce results far away from optimality, especially on the instances with 1000 vertices. By contrast, our method is able to obtain, within short time, results very close to optimality (corresponding to a gap of 0.8844%, 2.5365% and 3.2238% respectively on the instances with n = 200, 500 and 1000), clearly outperforming the existing learning baselines. Furthermore, we evaluate the performance of Att-GCN+MCTS on the 16 largest instances with 10,000 vertices. On these large instances, several baseline algorithms face a big challenge. For example, the three learning based algorithms proposed in [19] all fail due to memory exception (tested on the same platform as previously described), while the two exact solvers (Concorde and Gurobi) as well as the two GAT models in [9] all fail due to time exception (up to five hours is allowed for each instance). Therefore, we exclude these seven baseline algorithms, and just compare our Att-GCRN+MCTS algorithm with the remaining three learning based algorithms [22], all evaluated on one GTX 1080 Ti GPU. The results produced by LKH3 (evaluated on one Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz) are listed for indicative purpose. As shown in Table 3, Att-GCRN+MCTS is able to produce solutions close to LKH3, corresponding to a small average gap of 4.3902%. By contrast, the three learning based algorithms correspond to a huge average gap of 501.2737%, 97.3932%, 80.2802% respectively. The runtime of our algorithm remains reasonable (shorter than the best one of the three baselines).
Additionally, we would like to mention two MCTS based TSP algorithms, i.e., (author?) [36] and (author?) [43]. The source codes of these two papers are both not publicly available, thus we cannot evaluate them uniformly on the same platform to make strictly fair comparisons. In (author?) [36], the authors did not report instance-per-instance results, thus it seems impossible for us to make direct comparisons with this method. In (author?) [43], on the test instances with 20, 50, 100, 200, 500, 1000 cities, the authors respectively claimed an average gap of 0.01%, 0.20%, 1.04%, 1.91%, 4.37%, 4.48% with respect to optimality (all worse than ours), while the time elapsed on each instance was much longer than ours. Roughly speaking, compared to this recent MCTS algorithm, our algorithm is able to produce overall better results within reasonable time (although evaluated on different platforms).

Ablation study about heat map
To emphasize the importance of the heat map, for each instance, we assign an equal probability to each edge, and rerun the MCTS algorithm alone to search solutions. The results are summarized in Table 4, where the left part lists the results obtained by the original Att-GCRN+MCTS algorithm, and the right part lists the results obtained by MCTS alone (without heat map). Clearly, after disabling the heat map, the performance of the algorithm decreases drastically, corresponding to a huge gap with respect to optimality on each data set. For comparison, the original Att-GCRN+MCTS algorithm produces results very close to optimality on each data set. These comparisons clearly certificate the value of the method for identifying promising candidate edges.

Conclusions
Supervised learning based techniques are useful for discovering common patterns, but require a large amount of training data, being difficult to generalize to large-scale TSP instances. This research shows that, it is possible to train a small-scale model in supervised manner, and smoothly generalize it to tackle large TSP instances, by applying a series of techniques such as graph sampling, graph converting and heat maps merging. This method can inherit the advantages of supervised learning, and avoid repetitively training models of dif-  Table 4: Ablation study about the heat map. ferent sizes. Experimental results confirmed that, this method is able to develop highly competitive learning based TSP algorithm, and significantly improve the generalization ability of the pre-trained model. In the future, we will try to solve larger TSP instances or non-Euclidean TSP instances, and extend the method to other challenging optimization problems.