Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

4.5 GENETIC ALGORITHM: OPTIMISTIC LOAD BALANCING

Genetic algorithm (GA) is also a general technique for solving combinatorial problems [15], by modeling the natural-selection process where the fittest progeny always survives. GA have been quite successfully applied to optimization problems like VLSI designs, wire routing, database query, scheduling, and load balancing in distributed and parallel simulation systems.

Genetic algorithms use a vocabulary borrowed from natural genetics. This vocabulary includes individuals (or genotypes, structures) in a population; quite often these individuals also are called strings or chromosomes, and are made of units—genes (also features, characters, or decoders)—arranged in a linear succession; every gene controls the inheritance of one or several characters. Genes of certain characters are located at certain locations of the chromosome, which are called loci (string positions). Any character of individual states, such as a hair color, can manifest itself differently; the gene is said to be in several states, called alleles, feature values.

A genetic algorithm (as any evolution program) for a particular problem consists of (1) a string representation of the genes of the population or the nodes in the search space of the optimization process; (2) a set of genetic operators that alter the composition of children; (3) a way to create an initial population of potential solutions; (4) a probabilistic evaluation function that controls the operation ...