A Guided Learning Algorithm for solving the Traveling Salesman Problem

摘要

We propose a novel algorithm for solving the Traveling Salesman Problem (TSP). Our approach uses Genetic Algorithm as a guiding tool to direct Monte Carlo search towards convergence. This hybrid approach leverages a Genetic Algorithm to generate individuals with highly fit genes and uses that information as a base plan for Monte Carlo search. Our experiments suggest that this two-step Expectation-Maximization approach not only converges faster than either of the two algorithms studied individually, but also arrives at solutions that are closer to optimal.