FHome
|
Distributed Genetic Algorithms |
|
Introduction to Genetic Algorithms The concept of genetic algorithms is the same as biology's "natural selection". In brief, we design our problem in the following way: we design our chromosomes (lists or arrays of 1's and 0's) , we can also make many chromosomes to denote floating points, additional information if we're working with numbers etc... We also have to specify a fitness function that, given a certain chromosome, evaluates its performance according to what we seek. In addition, we need to make our encoding and decoding functions in order to convert our chromosomes to and from useful data. In the first phase, we start by generating a random "population" of chromosomes that start "getting married" and generate newer populations that we have to evaluate after each epoch, keep the best and kill the rest. In order to make the evolution more flexible we can specify a mutation probability and a crossing-over probability. Populations can get so big, however, we can limit the size by killing unnecessary chromosomes. However, bigger generations imply better chromosomes. The problem The problem is not problematic as much as it's efficiency-related. Meaning: If we want to have better solutions, we need to make bigger generations and make our genetic algorithm run for long periods. By distributing the problem, the efficiency can improve (basically. (no tests have been made yet) ). The problem is designed in the following way: Genetic algorithms (with the same fitness function of course) run on many computers. Let's say n computers. Those computers can not communicate except with the main "country". The main country is the computer that contains the best chromosomes of all the generations in all the other computers. After each generation in every node, the node sends to the main country a list of its best [k] chromosomes. (k is to be specified. let's say 10 chromosomes.) The main country performs the genetic algorithm too, having the best of the bests, it should evolve faster. Theoretically, if everything is well synchronized and the computers have the same speed, we would improve the performance by n times. (n being the number of nodes).
|
