An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

Abstract

In this paper an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area the well-known generalized traveling salesman problem (GTSP) is chosen where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore through the experimental analysis of results the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm. (C) 2009 Elsevier Inc. All rights reserved.