Session:

LBP - Late Breaking Papers

Title:

A Local Search Algorithm Based on Genetic Recombination for Traveling Salesman Problem

Authors:

Peng Gang
 Ichiro Iimura
Hidenobu Tsurusawa
Shigeru Nakayama

Abstract:

Genetic Algorithms(GAs) have been applied in many different fields and optimization problem domains. It is well known that it is hard to solve the complex problems with a Simple Genetic Algorithm (SGA). Many previous studies have shown that the hybrid of local search and GAs is an effective approach for finding near optimum solutions to the traveling salesman problem (TSP). In this paper, an approach based on the Genetic Recombination is proposed and applied to the TSP. The algorithm is composed of two SGAs which only consist of the basic genetic operators such as selection, crossover and mutation. One of the SGAs is named as the Global Genetic Algorithm (GGA) and carried out in the main tours which are designed for searching the global optimal solutions. Another one is named as the Local Genetic Algorithm (LGA) and carried out in the sub tours which are designed for searching the local optimal solutions. The LGA is combined to the GGA as an operator. The local optimal solutions are recombined to the main tours for improving the search quality. To investigate the features of the proposed algorithm, it was applied to a small double circles TSP and some interesting results were presented in our experiments.