A Brief Overview of Genetic Optimization

Evolutionary Algorithms started in the 1950's with [Fra57] and [Box57]. They form a powerful family of problem solving tools that attempt to mimic the natural selection process and evolution in order to find the optimal solution to a given problem. The most well known evolutionary methodologies are Evolutionary Programming [FOW66], Evolution Startegies [Rec73], and Genetic Algorithms [Hol75]. The first two methodologies emphasize mutation as the key search operator while the last one emphasizes crossover. In particular, the Genetic Algorithm (GA) has recently gained popularity due to its simplicity, close analogy with biological evolutionary systems, and its domain independent representation via bit-strings. A GA [Hol75,Gol89,SJB$^+$93] works on a population of individuals representing possible solutions to a particular problem. Each individual is evaluated using a fitness value which is a measure of how well adapted this individual is to its environment. As in nature, individuals mate and reproduce in a GA with a reproduction rate that is proportional to their fitnesses. The individuals are represented by their genetic material or genotype. This is accomplished by choosing a suitable representation scheme to code the possible solutions into individuals. Commonly, a solution is coded into a genotype consisting of a binary chromosome string with a predetermined number of bits which determines the problem's size. This coding creates a quantization of the solution space. A GA starts with an initial population of candidate solutions or individuals, and tries to modify them until th