Genetic Algorithm – Applications
Genetic Algorithm – Applications
History
This is an introduction to genetic algorithm methods for optimization. Genetic algorithms were formally introduced in the United States in the 1970s by John Holland at University of Michigan. The continuing price/performance improvements of computational systems has made them attractive for some types of optimization. In particular, genetic algorithms work very well on mixed (continuous and discrete), combinatorial problems. They are less susceptible to getting ‘stuck’ at local optima than gradient search methods. But they tend to be computationally expensive.
Applications
To use a genetic algorithm, you must represent a solution to your problem as a genome (or chromosome). The genetic algorithm then creates a population of solutions and applies genetic operators such as mutation and crossover to evolve the solutions in order to find the best one(s).
This presentation outlines some of the basics of genetic algorithms. The three most important aspects of using genetic algorithms are:
(1) definition of the objective function,
(2) definition and implementation of the genetic representation, and
(3) definition and implementation of the genetic operators. Once these three have been defined, the generic genetic algorithm should work fairly well.
Beyond that you can try many different variations to improve performance, find multiple optima (species – if they exist), or parallelize the algorithms.
Termination
This generational process is repeated until a termination condition has been reached. Common terminating conditions are:
- A solution is found that satisfies minimum criteria
- Fixed number of generations reached
- Allocated budget (computation time/money) reached
- The highest ranking solution’s fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
- Manual inspection
- Combinations of the above
Genetic Algorithm – Applications
The GA Lingo
application of ga
The genetic algorithm is very simple, yet it performs well on many different types of problems. But there are many ways to modify the basic algorithm, and many parameters that can be ‘tweaked’. Basically, if you get the objective function right, the representation right and the operators right, then variations on the genetic algorithm and its parameters will result in only minor improvements.
Since the algorithm is separated from the representation, searches of mixed continuous/discrete variables are just as easy as searches of entirely discrete or entirely continuous variables.
Array crossover operators
array crossover
These are some sample array crossover operators.
Typically crossover is defined so that two individuals (the parents) combine to produce two more individuals (the children). But you can define asexual crossover or single-child crossover as well. The primary purpose of the crossover operator is to get genetic material from the previous generation to the subsequent generation.
Notice that arrays may be fixed or variable length. They may also be 2 or 3 dimensional (or more). Also common are order-based arrays in which the sequence is important and nodes cannot be duplicated during the genetic operations. You can use more than one operator during an evolution.
Array mutation operators
array mutation
These are some sample array mutation operators.
Notice that lists may be fixed or variable length. Also common are order-based lists in which the sequence is important and nodes cannot be duplicated during the genetic operations. You can use more than one operator during an evolution.
The mutation operator introduces a certain amount of randomness to the search. It can help the search find solutions that crossover alone might not encounter.
« Improvement of anti-knocking characteristics of Diesel engine fuels Preparation of Neoprene »
Tell us Your Queries, Suggestions and Feedback