Alternative strategies for asynchronous migration-controlled schemes in parallel genetic algorithms

Abstract

Migration of individuals allows a fruitful interaction between subpopulations in the island model, a well known distributed approach for evolutionary computing, where separate subpopulations evolve in parallel. This model is well suited for a distributed environment running a Single Program Multiple Data (SPMD) scheme. Here, the same Genetic Algorithm (GA) is replicated in many processors and attempting better convergence, through an expected improvement on genetic diversity, selected individuals are exchanged periodically. For exchanging, an individual is selected from a source subpopulation and then exported towards a target subpopulation. Usually, the imported string is accepted on arrival and then inserted into the target subpopulation. Our earlier experiments on controlled migration showed an improvement on results when contrasted against those obtained by conventional migration approaches. This paper describes extended implementations of alternative strategies to oversee migration in asynchronous schemes for an island model and enlarges a previous work on three processors with a set of softer testing functions [9]. All of them try to decrease the risk of premature convergence. A first strategy attempts to prevent unbalanced propagation of genotypes by applying an acceptance threshold parameter to each incoming string. A second one permits independent evolution of subpopulations and acts only when a possible stagnation is detected. In such condition an attempt to evade falling towards a local optimum is done by inserting an expected dissimilar individual to improve genetic diversity. A third alternative strategy combines both previous mentioned strategies. The results presented are those obtained on the functions that showed to be more difficult for the island model using a replication of a simple GA. A description of the corresponding system architecture supporting the PGA implementation is described and results for the parallel distributed approach among 3, 6 and 12 processors is discussed.