A Molecular Dynamics Heuristic for Solving the Traveling Salesperson Problem

In this paper, a nature-based metaphor for computation is presented as a heuristic solution for a popular combinatorial optimization problem, the traveling salesperson problem (TSP). The metaphor was aptly named artificial chemistry (ACHEM) because the computational process is based on molecular dynamics. It is designed as a distributed stochastic algorithm that simulates reaction systems of algorithmic objects whose behavior is inspired by natural chemical systems. Finding the optimal solutions for TSP are particularly intractable for problem instances that are very large. This is the reason why a heuristic, such as the ACHEM, is a preferred solution than a computational procedure that provides optimal ones. To evaluate the utility of the heuristic, ACHEM was applied to find near-optimal solutions to large instances of the TSP. Results show that ACHEM outperformed other nature-based heuristics such as the simulated annealing and the self organizing maps, while it performed as good as the genetic algorithm and the ant colony optimization. Thus, ACHEM provides another natural metaphor for solving hard instances of the TSP.