Automatic design of algorithms for the traveling salesman problem

Abstract

The automatic generation of procedures for combinatorial optimization problems is emerging as a new alternative to address the hardest problems of this class. One of these problems still offering great computational difficulty is the traveling salesman problem. Its simple presentation masks the great difficulty that exists when solving it numerically. The results obtained so far for this problem are based on the hybridization of known heuristics. However, there is still a need for an experimental breakthrough in the study of all of the possible combinations of heuristics, which represents a huge search space. In this paper, we explore this space using evolutionary computing to automatically design new algorithms for the problem. We carried out a computational experiment to produce the algorithms that not only are competitive with some of the existing heuristics but that also contain several novel structures that directly influence performance.

Keywords

• traveling salesman problem
• automatic algorithm design
• heuristics, hyperheuristics, genetic programming, evolutionary computing