Combinatorial optimization
Attention-Based Policy Learning for the TSP
Transformer and reinforcement-learning policies for TSP, evaluated for solution quality, generalization, and exploration strategies.
- Year
- 2025
- Status
- Project
- Topics
- Transformers · Combinatorial optimization · Reinforcement learning
A conceptual illustration of the mathematical idea, not a plot of measured experimental results.
The question
How well can an attention-based policy learn to construct short traveling-salesperson tours?
Central insight
A learned policy must make a sequence of decisions whose value depends on the completed tour. Evaluating that policy involves both the quality of its solutions and how it behaves on new instances.
Approach
- 01
Train attention-based policies for the traveling-salesperson problem.
- 02
Evaluate the quality of the resulting tours and generalization to new instances.
- 03
Compare exploration strategies during policy learning.
My contribution
- Trained transformer/RL policies for TSP.
- Evaluated solution quality, generalization, and exploration strategies.
Result
An experimental study of learned combinatorial decision-making, covering training, solution evaluation, and exploration.
What remains
A possible extension is to combine learned tour proposals with classical local search.