Genetic Curriculum Learning for Distribution Generalization on the Travelling Salesman Problem

Authors: michael  li
christopher  haberland
natasha  jaques
Venue: NeurIPS_cc_2024_Workshop_MATH-AI
Published: 2024-09-26 10:29:20

Abstract: The Travelling Salesman Problem (TSP) is a classic NP-hard combinatorial optimization task with numerous practical applications. Classic heuristic solvers - and Large Language Models (LLMs) using such solvers as a tool - can attain near-optimal performance for small problem instances, but become computationally intractable for larger problems. Real-world logistics problems such as dynamically re-routing last-mile deliveries demand a solver with fast inference time, which has led to specialized neural network solvers being favored in practice. However, neural networks struggle to generalize beyond the synthetic data they were trained on. In particular, we show that there exist TSP distributions that are realistic in practice, which also consistently lead to poor worst-case performance for existing neural approaches. To address distributional robustness, we present Genetic Curriculum Learning (GCL), an efficient novel approach utilizing automatic curricula. We also present TSPLib50, a dataset of realistically distributed TSP samples, which tests real-world distribution generalization ability without conflating this issue with TSP instance size. We evaluate our method on various synthetic datasets as well as TSPLib50, and compare to state-of-the-art LLM results and neural baselines. We demonstrate that GCL improves distributional robustness, with most of its performance gains coming from worst-case scenarios.

Main paper: 
 introduction: 
 From least-cost shipping and warehouse logistics to efficient automated circuit board drilling, the Traveling Salesman Problem (TSP) has an outsized impact on global trade, accounting for billions of dollars worth of saved time, energy, and harmful emissions. The TSP is NP-hard, which means there exists no efficient algorithm for finding exact solutions. Classic heuristic methods have prohibitive runtimes for real-world situations requiring fast and dynamic decision-making. Neural combinatorial optimization (NCO) methods seek to effectively solve the TSP at lower computational cost [18, 10, 22] , but generalize poorly to unfamiliar distributions [11, 6] . In practice, such planning faults can be very expensive in terms of wasted time, money, and human resources.Given impressive recent gains in reasoning capabilities of Large Language Models (LLMs) [27, 28, 17] , LLMs potentially provide a promising path for solving novel TSP instances. However, LLMs currently perform suboptimally on the TSP [13, 26] . In this paper we directly study the performance of state-of-the-art LLMs prompted to solve TSP problems, and find that they have similarly prohibitive inference times as classic heuristics, in addition to inconsistent performance.Instead, we propose a novel adversarial training technique to enhance the robustness of NCO methods. Rather than training on limited TSP datasets or randomly generated TSP instances, which is inefficient and wasteful due to the high-dimensional parameter space, we propose to use a curriculum learning approach in which environments and tasks are adaptively evolved to be more challenging [3] . As applied to TSP solvers, a "task" or a "level" would be a TSP instance that needs to be solved.Curriculum-based methods have shown promise for combinatorial optimization [15] , but past works utilize very simple heuristic regimes, and are also focused on generalization across lengths, not distributions [20] . Zhang et al. [29] proposed a hardness-adaptive curriculum (HAC), which uses gradient ascent to produce increasingly harder levels. However, we show that HAC's sampling and gradient ascent procedure causes unreliable performance on specific types of TSP instances which are of practical interest.In this paper, we seek to improve model robustness to different distributions. We present an NCO optimization approach which maintains the computational benefits of NCO methods while improving generalization on disparate but practical distributions. We make the following contributions: 1) We propose the TSPLib50 dataset, a testing dataset of 10,000 instances sampled from realistic distributions, designed to test the robustness of TSP solvers; 2) We propose an automatic curriculum which mutates high-improvement-potential training distributions; 3) We present empirical results comparing the performance to the best prior work on curriculum learning for NCO and state-of-the-art LLMs, and show that our method gives better worst-case performance and improved robustness to varying distributions of practical interest. Our method is also relatively efficient to train, requiring only a single GPU and no more than a few hours of training for each model. 
background: 
 Traveling Salesman Problem. The Traveling Salesman Problem (TSP) is a NP-Complete combinatorial optimization problem (COP), which requires finding the shortest tour through a set of cities. The TSP has been of intense interest to computational theorists due to its applicability in many practical scenarios, especially in the logistics sector. Past works as well as this paper consider the 2D-Euclidean TSP, which is formally defined in the Appendix.Deep and Reinforcement Learning for TSP. Neural combinatorial optimization (NCO), or the use of deep learning for combinatorial optimization, can be broadly grouped into three primary approaches: solutions utilizing 1) pointer networks [23, 14] , 2) graph neural networks [8, 19, 30] , or 3) transformers [12] . Reinforcement learning (RL) has seen successful applications in learning to solve the TSP [16, 4] . Deep RL methods often use a neural network to generate a tour, and then treat tour length as a negative reward, or "cost". Kool et al. [10] propose a transformer-based solver trained with REINFORCE [25] , using a simple deterministic greedy rollout baseline. However, neural networks are known to often generalize poorly to distributions outside their training data, and existing NCO solvers are no exception. This makes them a risky solution for real-world deployments, in spite of their fast inference time. In this paper, we aim to improve the reliability and robustness of RL-based NCO approaches.Curriculum Learning for TSP. Curriculum methods improve robustness and sample efficiency by proposing tasks to learn from which are optimal for learning by being neither too easy nor too hard [3, 24, 1] , and have been applied to real-world problems such as web navigation [7] . In the context of Neural COP solvers, Zhang et al. [29] propose a hardness-adaptive curriculum (HAC) for the TSP, which mainly consists of two components: a hardness-adaptive generator that conducts gradient ascent on training instances, and a re-weighting procedure for batch gradients in favor of updates for harder levels. We directly compare to HAC in this work, and include the HAC hardness metric H(X, M ) as defined by Zhang et al. [29] in the Appendix. The hardness-adaptive generator conducts gradient ascent on input samples X (t) given a model M [29] :X (t) ′ = X (t) + η∇ X (t) H(X (t) , M ). 
preliminary study: 
 TSPLib50 and Other Evaluation Datasets. We first motivate the creation of TSPLib50, a new testing dataset. TSPLib, a collection of real-world TSP instances, is often used as a benchmark for combinatorial optimization solvers [21] . Because TSPLib is based on real data, its distributions are both varied and relevant for real-world applications. However, many solvers are trained on relatively small TSP instances. When tested on TSPLib, the gaps incurred by such models are correlated with instance size. For instance, we find a strong Pearson correlation of 0.907 between TSPLib instance size and optimality gap of HAC models (see the Appendix). Improving model generalization to larger instance sizes often requires extensive computational resources, and is beyond the scope of preceding papers as well as this paper. Figure 2 : Architecture of our proposed Genetic Curriculum system. After the forward pass, we compute improvement and then mutate high-improvement levels while saving Fisher information about low-improvement levels.Following the work of Zhang et al. [29] , we focus on 50-node instances. Hence, we introduce TSPLib50, a dataset of 10,000 instances, each created by sampling 50 points uniformly at random from a TSPLib instance. Because the distribution of points in TSPLib50 is the same in expectation as the distribution of points in TSPLib, we can thus disentangle generalization ability on different distributions with generalization ability on different instance sizes.We also test performance of our method on challenging synthetic distributions. We test on a Gaussian mixture distribution from prior work [29] , and a "Diagonal" distribution of our design where all points align with a main diagonal. We justify and visualize these distributions in the Appendix.Hardness-Adaptive Curriculum Shortcomings. While HAC improves performance by training on harder distributions [29] , it only conducts one step of gradient ascent on data sampled from a uniform distribution. As a result, HAC fails to cover instances that deviate far from a uniform distribution.In HAC, changes in X (t) are determined by η∇ X (t) H(X (t) , M ). We find that elements in η|∇ X (t) H(X (t) , M )| tend to have a mean around 0.077 and median around 0.023, which are small relative to the unit square [0, 1] 2 that points are placed in. Thus, points are only mildly perturbed.In Figure 1 , we visualize high-gap TSPLib50 levels for HAC, and find that HAC performs suboptimally on levels with large distances between nodes. TSPLib50 bootstraps from real-world distributions, and thus represents use cases of practical interest. We seek to address this issue. 
genetic curriculum learning: 
 Improvement Potential Metric. In Genetic Curriculum learning (GCL), we compute the "improvement potential" I(X, M ) for each training instance after each epoch with the current model M and REINFORCE baseline model M ′ : I(X, M ) = C M (X) -C M ′ (X). Note that I(X, M ) is similar to H(X, M ) as used by Zhang et al. [29] . Genetic Curriculum Algorithm. GCL proposes novel usage of an evolutionary approach to maintain a population of challenging levels, drawing inspiration from genetic programming [2] . GCL stores a population of level "genes" that describe the probabilistic process creating the levels. After each epoch, the 50% of highest improvement-potential levels have their genes edited and placed into the next epoch. We find that mutating a population of genes achieves better results than mutating a population of levels. The genome consists of 6 bases: 0) Cluster size of the distribution points are drawn from; 1) Cluster width of the distribution points are drawn from; 2) Rotation angle; 3) Scale factor; 4) x-axis translation factor; 5) y-axis translation factor. Through this genome, we try to address distribution invariance, rotational invariance, scale invariance, and translation invariance. Technical details of level sampling from genomes, genetic mutation procedure, and motivation for related hyperparameters are in the Appendix.GCL also uses Elastic Weight Consolidation (EWC) [9] to maintain performance on its learned knowledge, because as the genetic curriculum evolves to harder instances, it is possible that catastrophic forgetting is leading the model to perform poorly on easier instances. Figure 2 provides a diagram of the architecture of GCL. An algorithmic specification of GCL is provided in the Appendix. 
experiments: 
 Our experiments work on fine-tuning an attention-based model with a REINFORCE rollout baseline, previously trained exclusively on uniform random distributions. We compare our model to results from OpenAI's GPT-4o, a state-of-the-art LLM. We also compare against 2 NCO baselines: a "Uniform" baseline which samples from uniform distributions without curriculum, and a "HAC" baseline which samples from uniform distributions but uses HAC. Notably, all experiments are run on a single GPU, and no model takes longer than a few hours to train. Full experimental details and hyperparameters are in the Appendix. 1We plot gaps of all models relative to oracles. We present results for average gaps on the Gaussian Mixture, Diagonal, and TSPLib50 distributions. We also present results on worst-case 1%, 0.5%, and 0.1% of gaps on TSPLib50, to demonstrate robustness to challenging out-of-distribution cases.To further investigate our method, we run three tests to better interpret GCL. First, we run ablation tests on the genome and EWC components of our method. Second, we plot the distribution of each genome base over the course of training, to better understand the role the genome plays in GCL. Third, we plot the optimality gap of our baseline model M ′ and current model M on training data over the course of training, to better understand model convergence behavior. 
results: 
 Large Language Model Performance. Despite advances in mathematical and reasoning capabilities, Large Language Models (LLMs) often fail to find satisfactorily optimal TSP solutions, and have prohibitively slow inference, requiring around 47 seconds on average. Even with prompt engineering, 1 . On all distributions, HAC already improves significantly on the uniform baseline, as HAC uses a hardness-adaptive generator. GCL, our proposed method, achieves consistent improvement over HAC on the harder distributions. We observe an approximately 1/4 factor gap decrease on both hard distributions: the gap decreases from 8.85% to 6.22% on Gaussian mixtures, and from 3.94% to 3.02% on the diagonal distribution. For the TSPLib50 distribution, GCL improves only slightly on HAC in terms of average gap. This makes sense because a large portion of TSPLib50 levels are easy, while GCL focuses on robustness to challenging levels.We find decreases in average gap between HAC and GCL to be statistically significant, with values of p < 0.01 in two-sample t-tests for all distributions.Worst-Case Gaps. We can see that the slight improvement on TSPLib50 average gap mostly comes from gap decreases on hard levels by analyzing worst-case scenarios. On TSPLib50, GCL provides a 1.82% gap improvement on the worst 1% of cases, a 2.52% gap improvement on the worst 0.5%, and a 3.42% gap improvement on the worst 0.1%. This is significant because in large-scale real-world applications that route millions of TSP problems every day, 1% of routes is still an important and costly fraction. For example, if a large shipping company routes 40,000 loads, 1% of routes would still equate to 400 loads.We find decreases in worst-case TSPLib50 gap between HAC and GCL to be statistically significant, with values of p < 0.001 in two-sample t-tests for worst 1% and worst 0.5%, and p < 0.03 for worst 0.1%. GCL also improves gap from 204.40% by HAC to 98.47% on the worst 1% of Gaussian Mixture cases, and from 31.63% by HAC to 14.03% on the worst 1% of Diagonal cases. This demonstrates GCL's significant impact on improving robustness in the most challenging scenarios. Detailed tables are in the Appendix.Method Interpretations. In our ablation tests, we find that performance gains are mainly provided by the genetic component of our method. In our genome evolution plots, we observe that the diversity of genome bases decreases over training, suggesting our genome is effective at encouraging exploration of new configurations. In our optimality gap plot, we observe that the baseline gap starts higher than model gap, but dramatically decreases at around epoch 60, which further supports the previous point on the genome promoting exploration. Detailed results and explanations are in the Appendix. 
discussion: 
 Our results demonstrate that GCL is able to significantly improve the performance of TSP solvers on hard distributions. We also show that a portion of this improvement occurs in "worst-case" scenarios on real-world distributions of practical interest. Such improved robustness and performance guarantees are significant in real-world deployment.GCL is a general methodology, and could be applied to other NCOs methods or COPs. As the Kool et al. [10] architecture generalizes to other problems such as the Vehicle Routing Problem (VRP) and Capacitated VRP (CVRP), it would be exciting to see GCL used for other COPs.Formally, given a set of cities V = {1, 2, . . . , n} and a n × n distance matrix D where D i,j is a real number denoting the distance between city i and city j, the Traveling Salesman Problem (TSP) seeks to find the optimal permutation of cities σ * that minimizes total tour length [5] :EQUATIONThe 2D-Euclidean TSP is a special case of the TSP where all cities are given a position on the 2D Euclidean plane, and all D i,j represent the Euclidean distance between cities i and j. Because σ * is theoretically translation-invariant and scale-invariant, 2D-Euclidean TSP problems often provide city locations that are translated and scaled to fit in the [0, 1] 2 unit square. For an old task A and a new task B, Elastic Weight Consolidation (EWC) computes a mean given by the model parameters θ * A and the diagonal of the Fisher information matrix F . For some importance hyperparameter λ and loss L B (θ) on task B, EWC loss is formally defined as follows [9] :EQUATIONThe optimality gap G for a dataset X used by the hardness-adaptive generator is the gap in cost C between the current model M and an oracle model M * :EQUATIONThe hardness metric H for a dataset X used by the hardness-adaptive generator is the gap in cost C between the current model M and a surrogate model M ′ which is greedily updated by a few steps of gradient descent [29] :EQUATIONNote that the formulation for H(X, M ) is similar to the formulation for G(X, M ). In fact, Zhang et al. [29] observe that H(X, M ) is always a lower bound for G(X, M ).Figure 4 demonstrates the high correlation between TSPLib instance size and resulting performance, justifying the necessity of our creation of TSPLib50. We also test on the Gaussian mixture distribution because it tends to pose a challenge to existing TSP solvers, as noted by previous works [29] .We also test on a "Diagonal" distribution of our design because it is intended to be difficult in another manner. Previously, we identified a common feature of HAC failure cases being that they have much empty space, and we justified this interpretation mathematically. However, another common feature of those cases is that they have points in distinct clusters. The diagonal distribution aims to experimentally demonstrate that empty space is a primary factor for difficulty, by having all points aligned along a main diagonal. As such, there is only one cluster, but there is still much empty space on the level. Our algorithm for generating TSPLib50 is specified in Algorithm 1. Note that when generating TSPLib50, we only sample from TSPLib instances with 150 or more nodes to ensure that there is sufficient diversity in the generated TSPLib50 instances.Our algorithm for generating Gaussian mixture datasets is specified in Algorithm 2. Note that while we generate Gaussian mixture distributions in the same fashion as Zhang et al. [29] , our dataset composition is different. Zhang et al. [29] add instances of the uniform distribution and Gaussian mixtures with c dist = 1 to the testing dataset. Note that Gaussian mixtures with c dist = 1 are "close to uniform" by our definition, as there is not much empty space on the level. We do not do this, and keep the Gaussian mixture distribution as purely Gaussian mixtures. Thus, our reported gaps Negate y-coordinates in l with p = 0.5Rescale l to fit in [0, 1] 2 7:D ← D + l 8:end for 9: end for 10: return D with HAC are higher than those reported by Zhang et al. [29] , as uniform distributions and Gaussian mixtures with c dist = 1 incur very low gap.Our algorithm for generating Diagonal datasets is specified in Algorithm 3.Algorithm 4 provides an algorithmic specification of GCL.Recall that the GCL genome consists of 6 bases: 0) Cluster size of the distribution points are drawn from; 1) Cluster width of the distribution points are drawn from; 2) Rotation angle; 3) Scale factor; 4) x-axis translation factor; 5) y-axis translation factor. Levels are drawn from a "clustered uniform distribution", and then rotated, scaled, and translated in that order. Combined, these parameters address distributional invariance, rotational invariance, scale invariance, and translation invariance. Intuitively, the clustered uniform distribution generates points in various clusters, which serves as a better starting point for the gradient ascent step in the hardness-adaptive generator to reach a variety of distributions. A sampling algorithm for this distribution is specified in Algorithm 5.Beginning each epoch, training data is sampled from the genomes in a probabilistic process. Our algorithm for sampling a level l from a gene g is specified in Algorithm 6. Compute improvementI = C M (X) -C M ′ (X) 13:Sort D and G using I Place centers within [0, 1] 2l ← 50 points ∼ Unif(centers -ϵ, centers + ϵ)Rescale l to fit in [0, 1] 2D ← D + l 8: end for 9: return D Genetic mutation procedure ψ: After each epoch, we select the 50% of highest-improvement genes and mutate their bases with ψ. Each base is incremented with probability 1/12 and decremented with probability 1/12. Note that in aggregate, this means each base is mutated with probability 1/6. Following are the min/max bounds and increment/decrement magnitudes for the bases: Genome distribution Ψ: After each epoch, we select the 50% of lowest-improvement genes and resample them from Ψ, as specified below per base. These initial values are often "middle" values that allow exploration in both directions, which mitigates the possibility of getting stuck in a gene pool "local minima", as detailed in our hyperparameter interpretations below.Input: Gene g Output: Level l 1: l ∼ ClusteredUniform(c = g[0], ϵ = g[1]) 2: l ← Rotate(l, θ = g[2]) 3: Rescale l to fit in [0, 1] 2 4: l ← l × g[3] 5: l ← l + (∆x = g[4](1 -g[3]), ∆y = g [5] (1 -g [3] )) 6: return l• 0: Uniform split between {1, 5, 10, 15}• 1: 0.05• 2: 0 • 3: 1 • 4: 0.5 • 5: 0.5Following are interpretations for the two important end-of-epoch mutation hyperparameters:• Mutate 50% of high-improvement levels: We mutate the 50% of most improved levels and re-sample 50% as it strikes a balance between fresh training distributions and hard distributions that the model needs to improve at. This also minimizes the risk of getting stuck in possible gene pool "local minima", where the majority of genes are focused on distributions that used to be hard, but are no longer challenging. • Mutate each genome base with 1/6 probability: During mutation, each base is mutated with 1/6 probability; because there are 6 bases in each level's genome, in expectation only one base is modified per mutation. This allows genetic diversity of levels while preventing levels from mutating so much that the mutated genes' difficulty is vastly different from the original genes' difficulty.After each epoch, a number N of least-improved levels are saved and used to compute Fisher information diagonals and means for the network parameters θ. This is then used in the EWC penalty for constraining gradient updates in the next epoch. The intuition is that low improvement-potential levels are likely representative of the model's strengths, and thus important related parameters should not be changed.Following the work of Kool et al. [10] , we use an attention-based architecture trained with a REIN-FORCE rollout baseline. We also use the gradient re-weighting curriculum from Zhang et al. [29] .All our experiments work on fine-tuning a model previously trained exclusively on uniform random distributions. We work off the Kool et al. [10] codebase, which is released under an MIT license.We compare our model against two baseline methods: a uniform baseline trained on uniform distributions without any form of curriculum, and a HAC baseline which samples from uniform distributions but uses HAC to make training instances more challenging. Note that the uniform baseline is equivalent to the model used by Kool et al. [10] , while the HAC baseline is equivalent to the model used by Zhang et al. [29] .We plot gaps of all models relative to Concorde solutions, as Concorde is an optimal solver. For all distributions, 10,000 instances are sampled for evaluation. We also train 5 models for each setting, and report averaged results between the 5 models for each setting. We assume a normal distribution of error across these averages, and plot error bars equal to 1-σ of these averages.The base hyperparameters used for training all models are listed below. For fair comparison, we use the same model architecture used by Kool et al. [10] and Zhang et al. [29] .• The exact training and evaluation commands which we use to obtain our results are included in our code. Those commands give additional information about default/implicit hyperparameters not listed.Our criteria for selecting final parameter settings was best average gap on testing distributions. Note that we did not tune all parameters concurrently; in particular, our EWC parameters were selected at a stage of our tuning when EWC had a more significant effect on results. Hyperparameter ranges used for tuning are as follows:• Architecture: Not tuned, consistent with Kool et al. [10] We train 5 models for each setting, and report aggregate results over the 5 models for each setting. All test datasets were generated with the random seed "1234". Our models are not explicitly seeded, but we find variance between runs to be consistent and reproducible.All experiments were run on a singular NVIDIA L40 GPU on a Linux operating system with 20GB requested memory. However, our hyperparameter settings do not fully utilize GPU capabilities, and results should be reproducible on lower-memory GPUs such as the GeForce RTX 4060. No model takes longer than a few hours to train.Our source code is publicly available at https://github.com/ML72/Genetic-Curriculum-TSP.Relevant software libraries and frameworks are listed in the dependencies file included in our code.We also include special documentation on installing pyconcorde, which we use as our oracle solver. All exact code used for plotting and conducting statistical tests is included in our code. We run brief experiments to demonstrate that large language models have inconsistent performance and lengthy inference times when asked to solve TSP problems. We prompted OpenAI's GPT-4o, which boasts state-of-the-art performance on mathematical and logical reasoning tasks, to solve the first 5 TSP instances in TSPLib50. Performance on these instances is printed in Table 2 .As opposed to prior work which uses meta-prompts [26] , we prompt the LLM to directly solve a given TSP instance, for simplicity and faster inference. We use prompt engineering to improve response performance and consistency to the best of our ability. In our prompt, we ask for a permutation of the indices 1 to 50 and nothing else, to encourage the LLM to consistently return a valid permutation. We also ask the LLM to solve the problem to the best of its ability, to avoid errors where the LLM tries to use tools or libraries not in its environment and thus encounters an error. If we directly ask for a solution to the TSP instance without such further instructions, the majority of responses do not provide a tour, falling into one of the following failure cases:• GPT-4o correctly identifies the problem as being the TSP and describes methods for approximating a solution, but makes no attempt to solve the instance provided. • GPT-4o provides code which runs classic heuristic-based algorithms to solve the TSP, but does not provide an actual permutation. • GPT-4o writes code and attempts to run it, but encounters into an error because some library that it needs is not in its current environment.A sample prompt is printed below: What is the optimal tour permutation of the cities to minimize the total distance traveled? Solve the problem to the best of your ability. Reply with only a permutation of the indices 1 to 50, and nothing else.From Table 2 , we can immediately see that the inference time required by GPT-4o is prohibitively expensive in situations requiring fast and dynamic decision-making. Furthermore, the performance is inconsistent: we can see that the gap incurred by GPT-4o has high variance, which is especially evident in the gap incurred on instance 2. Even in the best-case scenarios, the gap provided is still suboptimal compared to NCO methods. It is also worth mentioning that the formatting of the outputs produced by GPT-4o have slight inconsistencies as well. A permutation was provided for all 5 instances, but sometimes there were artifacts such as extra square brackets around the permutation. These small formatting variations pose a possible risk of feeding unexpected input into downstream applications that utilize these outputs.Worst-case gap results on TSPLib50 can be seen in Table 3 . We can observe that there is significant improvement by GCL on the hardest TSP instances.In Table 4 , we report ablation results for the two aspects of our curriculum. It can be seen that without the genome component, the gap increases significantly, while without the EWC component, We acknowledge that there are realistic distributions out there that GCL still fails to consistently generate and train on, as noted by worst-case gaps that are still significantly above average.This paper also focused on instances with 50 nodes. With more compute, GCL could be tested at scale to see if trends hold with larger instance sizes.Additionally, while we conducted basic hyperparameter searches for curriculum-based parameters, by no means is our search exhaustive due to the large parameter space. Thus, we believe that our performance could be optimized upon further tuning. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).All code is provided at https://github.com/ML72/Genetic-Curriculum-TSP/ 
 
 Appendix:  


Decision: This paper presents a new algorithm for the classical TSP problem that will be of interest to the MATH-AI community. The authors are encouraged to include more analysis of their algorithm and include a more detailed discussion/comparison of more recent related work such as Sym-NCO.

Reviews: review: title: title: A good TSP solver for real-world applications
main_review: main_review: **Summary**

The authors propose a method Genetic Curriculum Learning (GCL) to solve the traveling salesman problem (TSP). They present a neural combinatorial optimization (NCO) approach to solve the TSP problem that improves the generalization and robustness of the model on real-world practical TSP distributions. The authors propose an automatic curriculum in which the environments and tasks are adaptively evolved to be more challenging by mutating training distributions that have high-improvement-potential.
The paper also introduces a new dataset TSPLib50 consisting of 10k TSP instances sampled from realistic distributions.

**Strengths**

The work is shown to improve the performance of TSP solvers on hard and practical distributions. 
The authors mentioned statistical significant values for all the experiments they conducted to show improvements of GCL on “worst-case” optimality gaps.
The authors also compared GCL with LLMs (with chain-of-thought reasoning) to solve the TSP problem.
The robustness and generalizability of the approach on real-world practical scenarios facilitates significant real-world deployment and applications.


**Weaknesses**
The authors could have talked about any real-life practical problems/examples to demonstrate the effectiveness of their approach. 
It would be nice to compare the results with ChatGPT o1 as well (as it is claimed to have better reasoning capabilities).
title: title: The GCL method is interesting, but its practicality is in question.
main_review: main_review: The paper uses LLM to solve the TSP, which is well-known to be NP-hard. Previously, LLM and heuristic solvers could do well for small problem sizes, but struggle in larger problems, and real-world data could be out of the distribution of the training dataset. This work proposes a genetic curriculum learning approach to address distributional robustness and a new dataset for more realistic data distribution.

Strengths:
- The proposed approach to address distributional robustness is interesting and could be applied in other settings as well.
- The work has a substantial amount of contributions and results.

Weaknesses:
- Aside from training LLM, the significance of this work is a bit questionable. LLM has a slow inference time and is inconsistent. Moreover, RL-based methods are usually better for this task, so from a solver's point of view this is not very efficient. However, I do appreciate the attempt to improve LLM's capability to solve this task.

- I'm a bit skeptical of the amount of computational resources dedicated to training for this task. The family of genetic algorithms is usually very inefficient, so I doubt that this method would be practical.
title: title: Genetic Curriculum Learning for TSP: Promising but Marginal Gains
main_review: main_review: This paper addresses the challenge of distribution generalization in the traveling salesman problem (TSP). The authors highlight the limitations of the baseline method, HAC, which struggles to handle instances significantly deviating from a uniform distribution. To overcome this, they propose a novel approach based on genetic curriculum learning that incrementally trains on harder distributions. Experimental results demonstrate that the proposed method outperforms HAC in these more complex scenarios.

Pros:

The application of genetic curriculum learning to improve distribution generalization is a well-motivated and intuitive extension. It effectively addresses the shortcomings of the baseline method in a structured manner.

Cons:

While the proposed method shows improvement, the gains over HAC appear modest, raising questions about the practical significance of the enhancement in certain scenarios.