A study on various strategies for distributed genetic algorithms working on clusters for a number of described problems

Abstract

Genetic algorithms solve problems by borrowing from Darwin's concept of evolution, survival of the fittest. A genetic algorithm works by creating many generations from an initial population of possible solutions through the use of selection, crossover and mutation operations. A distributed genetic algorithm (or DGA) is a series of serial genetic algorithms working in parallel on the same problem, in the hope of finding a better solution in a shorter time. A particular kind of DGA is the coarse grain type. These kind of DGAs are composed of several genetic algorithms working independently of each other which regularly exchange individuals (migration) with each other according to a pre-specified scheme. Coarse-grain distributed genetic algorithms are defined by various factors, including the migration interval (how many individuals migrate), migration rate (how frequently do these individuals migrate) and the topology (which populations exchange their individuals with which other populations). This project has two main objectives. The first objective is to create a generic DGA tool which allows the user to solve any kind of problem (be it the TSP problem or the bin-packing problem) using a DGA. Furthermore, this tool should enable the user to define his own DGA by allowing him to specify parameters like the population size, the number of nodes to be used, migration interval, migration rate and the topology scheme. The second objective of this project is to carry out various DGAs (with different parameters) using the generic DGA tool built for two problems (a TSP problem of 89 cities and a partition problem of 1000 integers) and compare their performances. This could provide some insight into which set of DGA parameters are better suited for each problem.