A java-based distributed genetic algorithm framework

A Java-based Distributed Genetic Algorithm Framework
Gabi Escuela, Yudith Cardinale and Jorge Gonz´ lez a Universidad Sim´ n Bol´var o ı Departamento de Computaci´ n y TI o Apartado 89000, Caracas 1080-A, Venezuela. {gescuela, yudith,01-33936}@ldc.usb.ve

Abstract
Distributed Genetic Algorithm (DGA) is one of the most promising choices among the optimization methods. In this paper we describeDGAFrame, a flexible framework for evolutionary computation, written in Java. DGAFrame executes GAs across a range of machines communicating through RMI network technology, allowing the implementation of portable, flexible GAs that use the island model approach. Each island can be configured independently from others providing the implementation of heterogeneous DGAs. To evaluate the performance ofDGAFrame, we implemented the Protein Structure Prediction problem and compare the DGA execution to its sequential counterpart through quality of solution. We also measure the computation to communication ratio and results show that the proposals consistently outperform equivalent sequential GAs.

1. Introduction
Genetic Algorithms (GAs) are efficient search methods based on principles of naturalselection and genetics, that are being applied successfully to find acceptable solutions to search, design and optimization problems in business, engineering, and science [1]. GAs are based on a basic evolutionary principle: better individuals survive and reproduce more often than other individuals. Given a problem to solve, a GA consider a set of potential solutions as a population ofindividuals. An individual is represented using a genotype that encodes the variables of the problem. Individual aptitude to solve the problem, called fitness, is measured in accordance with an objective function that guide the algorithm. Generally, a first population is generated randomly and it evolve in an iterative way through generations, in which selection, crossover and mutation operators are applied toindividuals in order to

get genetic variations, that allows to obtain better solutions, in terms of objective function. Even thought, GAs produce “good enough” solutions for certain kind of problems, in practices there are two main difficulties with them. One is premature convergence problem. During the evolution, the genetic features of an elitist individual in the population may dominate thewhole population, and make the evolution stuck to a local minimum due to the lost genetic diversity. The other difficult concern to performance. GAs are generally able to find good solutions in reasonable amounts of time, but as they are applied to larger and harder problems with complex searching spaces, there is an increase in the time required to find adequate solutions [2]. To overcome thesedifficulties, many authors have proposed distinct options, in order to increase the performance or to prevent premature convergence. Some of these approaches are: modified genetic operators [3], adaptive approaches [4], and methods based in the diversity preservation, through a spatial separation of the population [5, 6, 7]. Distributed Genetic Algorithm (DGA) is one of the most promising choices amongthe spatial separation methods. It is very suitable to parallel computers and its basic idea is to divide a large population into smaller subpopulations that are processed by a traditional GA, with each one being independent from the others. In the literature, this model is sometimes also referred as the Island Model, where each subpopulation represents an island or deme. This implies havingsubpopulations distributed among many processors, which requires a new operator to be added to the problem configuration: migration. Migration consists of selecting individuals to be exchanged amongst subpopulations. Technically the migration of individuals is controlled by three parameters: the topology that defines connections between subpopulations, migration rate that controls the percentage of...