Authors: E.Strelnikov, O.Kaverina
Several people working in the 1950s and the 1960s developed evolution−inspired algorithms for optimization and machine learning. Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), and Reed, Toombs, and Baricelli (1967) all worked in this area, though their work has been given little or none of the kind of attention or follow up that evolution strategies, evolutionary programming, and genetic algorithms have seen. In addition, a number of evolutionary biologists used computers to simulate evolution for the purpose of controlled experiments (see, e.g., Baricelli 1957, 1962; Fraser 1957 a,b; Martin and Cockerham 1960). Evolutionary computation was definitely in the air in the formative days of the electronic computer.
Genetic algorithms (GAs) were invented by John Holland in the 1960s and were developed by Holland and his students and colleagues at the University of Michigan in the 1960s and the 1970s. In contrast with evolution strategies and evolutionary programming, Holland's original goal was not to design algorithms to solve specific problems, but rather to formally study the phenomenon of adaptation as it occurs in nature and to develop ways in which the mechanisms of natural adaptation might be imported into computer systems.
Holland's 1975 book Adaptation in Natural and Artificial Systems presented the genetic algorithm as an abstraction of biological evolution and gave a theoretical framework for adaptation under the GA
The idea behind GA's is to extract the optimization strategies of the nature of the environment.
One could imagine a population of individual explorers
sent into the
optimization phase-space. Each explorer is defined by its genes, what means, its
position inside the phase-space is coded in his genes. Every explorer has the duty
to find a value of the quality of his position in the phase space. (Consider the
phase-space being a number of variables in some technological process, the value
of quality of any position in the phase space – in other words: any set of the
variables – can be expressed by the yield of the desired chemical product. ) Then
the struggle of life
begins. The three fundamental principles are
Only explorers (= genes) sitting on the best places will reproduce and create a new
population. This is performed in the second step (Mating / Crossover). The hope
behind this part of the algorithm is that good
sections of the two parents will be
recombined to. In fact, many of the created children will not be successful (as in
biological evolution), but a few children. These good
sections are named in some
publications as building blocks.
Now there appears a problem. Repeating these steps, no new area would be explored. The two are the two, the former, the former, and the other. The third step - the Mutation ensure the necessary accidental effects. One can imagine the new population being mixed up a little bit to bring some new information into this set of genes. Off course this has to happen in a well-balanced way!
Whereas in biology a gene is described as a macro-molecule with four different bases to code the genetic information, a gene in genetic algorithms is usually defined as a bitstring (a sequence of b 1´s and 0´s).
Remember: Don´t project results obtained from GA-performance or different
qualities of algorithm types to biological/genetic procedures. The aim of GA´s is
not to model genetics or biological evolution!
Genetic algorithms are used to solve the following problems: