A Proposal and Evaluation of Heuristic Scheme for Solving TSP Based on the Evolution of Instances

摘要

Evolutionary computation is a method for solving combinatorial optimization problems, that is based on the imitation of livings that could evolve themselves into the environment. Actual livings take different ways of evolutions when they are placed on different environment. Prom the viewpoint of mathematical optimization, such a phenomenon could be regarded as a modification of the energy space according to the change of the actual environment whose concrete landscape depends on the current instance. In addition, we could observe in many cases that a good solution could be easily obtained for the instances with a simple landscape, that motivates the study of "evolution" of the given instance depending on the change of the environment, as was originally pointed out by Papadimitriou and Sideri in 1998. In this paper, we extend the observations made by Papadimitriou and Sideri, and propose a new scheme based on a similar idea on the evolution of instances. The result of experiments implies that our extension really improves the performance of the previous scheme.