1. Inicio
  2. Atrás
Título: Alternative strategies for asynchronous migration-controlled schemes in parallel genetic algorithm
Autores: Ochoa, Claudio
Gallard, Raúl Hector
Fecha: 2004-05-13
1999
Publicador: Unversidad Nacional de La Plata
Fuente:


Tipo: Articulo
Articulo
Tema: parallel genetic algorithms; island model; migration schemes; acceptance threshold; dynamic arbiter
Ciencias Informáticas
Informática
Algoritmos evolutivos
Algoritmos paralelos
Sistemas distribuidos
Programación paralela
Descripción: Migration of individuals allows a fruitful i nteraction 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 p ropagation 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 d issimilar 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.
Idioma: Inglés