Learning to Solve Travelling Salesman Problem with Hardness-Adaptive Curriculum
Authors: Zeyang Zhang, Ziwei Zhang, Xin Wang, Wenwu Zhu9136-9144
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that our hardness-adaptive generator can generate instances ten times harder than the existing methods, and our proposed method achieves significant improvement over state-of-the-art models in terms of the optimality gap.In this section, we conduct experiments to answer the following questions: Q1: Can our hardness-adaptive generator continuously generate samples with diverse hardness levels than uniform sampling? Q2: Can our curriculum learning model train more powerful TSP solvers that are better generalizable to different distributions? |
| Researcher Affiliation | Academia | Tsinghua University zy-zhang20@mails.tsinghua.edu.cn, zwzhang@tsinghua.edu.cn xin wang@tsinghua.edu.cn, wwzhu@tsinghua.edu.cn |
| Pseudocode | Yes | Algorithm 1: Hardness-adaptive Curriculum Learner |
| Open Source Code | Yes | The codes1 are publicly available. 1https://github.com/wondergo2017/TSP-HAC. |
| Open Datasets | No | The paper describes generating TSP instances using uniform sampling and a Gaussian mixture generator, but does not refer to a publicly available dataset with concrete access information like a link, DOI, or formal citation. |
| Dataset Splits | No | The paper specifies training and testing set sizes (e.g., '100,000 TSP instances for each training epoch' and '100 randomly selected instances as the testing set'), but does not explicitly detail a separate validation split or its size/methodology. |
| Hardware Specification | No | The paper does not specify any particular hardware (e.g., GPU/CPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper mentions using 'GAT' and 'Gurobi 2', and 'Adam optimizer', but does not provide specific version numbers for software dependencies, such as 'PyTorch 1.9' or 'Gurobi 9.1'. |
| Experiment Setup | Yes | For the TSP solver, the GAT has three encoding layers with the embedding dimensionality 128 and the number of attention heads 8. Training methods such as batch normalization, tanh clipping of action logits and clipping of gradient norms are kept unchanged as in the original paper to stabilize the training process. We use Adam optimizer with the learning rate of 0.0001, the weight decay of 1.0, and the batch size of 512. The significance threshold used to update the RL baseline is α = 0.05. |