Genetic algorithms
From DDL Wiki
The term "genetic algorithms" (GAs) refers to a set of stochastic heuristic optimization techniques inspired by Charles Darwin’s concepts of natural selection and evolution. Stritcly, genetic algorithms are a subset of evolutionary algorithms; however, this distinction is often lost in the literature. GAs are commonly used as optimization techniques for large problems with complex formulations and where exhaustive search is not an option. Just as natural selection is thought to lead to improvements in the fitness of a biological organism, genetic algortims seek to "evolve" the design.
Contents |
Overview
A basic genetic algorithm consists of 5 main steps.
1. Establish a Population
A sample population of designs must be created. Each member of the population contains a set of randomly generated traits (design variables). For example, in lions, a population would be created where each member possessed a randomly generated speed, strength, stealth, and loudness of roar.
2. Assign Fitness
A fitness function is used to assign to each member of the population a fitness value. This value is based on the attributes of the design, and the fitness function is analogous to the objective function in classical optimization. Members of the population that contain preferred attributes will have higher fitness. In the case of our lions, the faster, stronger, stealthier and louder roaring lions will have a higher fitness.
3. Assign Selection Probability
Each member of the population is then assigned a selection probability based on its fitness value, such that those members with higher fitness function are probabilistically more likely to be chosen. A stronger fates lion may be able to hunt better, but a broken leg or encounter with a hunter would take him out of the mix and allow a less fit lion to be selected.
4. Reproduction
Members of the previous population are chosen, based on their selection probability, to reproduce and form an offspring. The offspring is modified through a variety of operators analogous to gene mixing, including crossover and mutation. The new lion will contain traits from both its parents as well as new traits.
5. Repeat
Steps 2-4 are repeated for a set number of generations or until and solution is found. The most fit solution is recorded in each generation for more efficient optimization. As with the lions, the most fit lion would become the King of the pride.
Genetic Operators
During the reproduction stage of the genetic algorithm process, the new generation must undergo some changes. These changes are a function of traits from parents as well as some genetic mutation. The process is analogous to gene recombination. The two major genetic operators are:
Crossover
In genetic crossover, the DNA strands of each parent lie next to each other. Each of the strands are then connected at certain points in between. Some of the newly form segments switch, creating a unique DNA strand which results in an offspring. Using the previous lion example, the father may be strong and fast yet clumsy and have a low roar. The mother may be slow and weak yet stealthy and roar loudly. Through crossover, the offspring could have any combination of these traits, such as strong, fast, stealthy and loud. The picture below shows an example of crossover.
(1)
Mutation
After crossover, some of the genes may randomly mutate. This random mutation is supported by Darwin’s theories. This allows the next generation the possibility to achieve better fitness then was previously possible through their parents. If both parents of the new lion were slow, it would be impossible for the offspring to be fast unless the speed gene randomly mutated.
Although the concept was derived from genetic code, it can be applied to any population with discretized attributes. The attributes can be made into a bit string, with each bit being analogous to a link in the DNA chain.
Pseduocode
First a population latex($$P(m)$$) is created. Then the loop beings with the first generation, latex($$G$$). The Population is evaluated by latex($$E(P(m))$$) to form the evaluated population latex($$E(m)$$). This evaluated population is then refined by another evaluation function to form the fit population latex($$FP(m)$$), whihc consists of the individuals fit enough to reporduce. A new population is formed by using a number of genetic operators, latex($$GO(FP(m))$$). This population is then put back throught the loop. The termination criteria in this pseudocode is number of generations. However, it can also be a different function, such as reaching a threashold fitness value.
latex($$P = P(m)$$).latex($for$ $G = 1:100$).latex($$EP(m) = E(P(m))$$) . latex($$FP(m) = E(EP(m))$$) latex($$P'(m) = GO(FP(m))$$) latex($$P(m) = P'(m)$$) latex($$End$$)
Strengths
Genetic algorithms are often able to find good solutions relatively shortly. They are also suited for handling large complex populations where the problem may not be fully understood, or where mixed integer and nonconvex formulations make it difficult to find global solutions with classical optimization methods. Some examples include circuit design and video quality optimization.
Weaknesses
Many algorithms tend to drive toward local minima instead of a global minimum. This is referred to as early convergence. A very fit member of the population may appear early. Due to its high fitness, it is more likely to reporduce and propagate its characteristics through the generations, eliminating the options that may have enventually lead to the global maximum. Another drawback to genetic algorithms is that this method has not guarantee of finding a local or global solution, but rather finds a good solution. The best solution may never appear in any generation. Some variations are used to combat these problems such as widowing, exponential, linear transformation and linear normalization.
Among the greatest strengths and weaknesses of GAs is the large number of variations and parameters that can be tuned. While these parameters allow the algorithm to be tuned to solve a particular problem, the problem-dependent nature of the algorithm makes it difficult to predict performance of the algorithm in general, and practitioners often spend a significant amount of time tuning the algorithm.
Conclusion
Genetic algorithms can be a great solution method for a specific type of optimization problem. The concept has been shown to be effective through Darwin’s observations. However, the method suffers from the same setbacks that natural selection and evolution suffer from. The form of the data, genetic operators, and fitness equations must be carefully chosen to eliminate the chance of error and to make the method more efficient.
References
Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA
Gen, Mitsuo and Cheng, Runwei, (1997), Genetic Algoithms and Engineering Design, Wiley.
Other Links
Google Images (1)
