Distributed Genetic Algorithm with Centralized Multiple Crossovers Applied to Traveling Salesman Problems
Mitsunori MIKI, Tomoyuki HIROYASU, Yoshiko HANADA, Takanori MIZUTA
This paper proposes a new method of genetic algorithms (GAs) for discrete optimization problems. For continuous optimization problems, it has been reported that distributed genetic algorithms (DGAs) show the higher performance than conventional GAs. However, for discrete optimization problems, the performance of DGAs has not been clear so far. In this paper, we propose a new approach in DGAs to discrete optimization problems. The proposed method is based on the multiple crossovers applied to the population consists of offsprings from elite individuals in distributed subpopulations (Centralized Multiple Crossover : CMX). We examine the performence of a conventional GA, DGA and proposed method for a typical discrete optimization problem, the Traveling Salesman Problem (TSP). The experiments showed that the proposed method provides better performance than the conventional DGA.