Jaderick P. Pabico, Jose Rene L. Micor and Ma. Christine A. Gendrano
jppabico@uplb.edu.ph, jrlmicor@uplb.edu.ph, ma.christine.gendrano@dlsu.edu.ph
Institute of Computer Science, University of the Philippines Los Baños
Institute of Chemistry, University of the Philippines Los Baños
College of Computer Studies, De La Salle University – Science and Technology Complex
Asia Pacific Journal of Education, Arts and Sciences | Vol. 1, No. 1 | March 2014
A Molecular Dynamics Heuristic for Solving the Traveling Salesperson Problem 922 KB 1 downloads
Jaderick P. Pabico, Jose Rene L. Micor and Ma. Christine A. Gendrano jppabico@uplb.edu.ph,...
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.
Keywords – Artificial chemistry, combinatorial optimization, traveling salesperson problem, TSP