Introduction
Introduction
Overview Information
The Domain of Genetic Search
The Whats, and Whens of GAs
The Origin of the "Species" of GAs
Overview
Since genetic algorithms were introduced in the 50's as a research area attempting to apply the mannerisms of natural systems to artificial, numerous branches of research "evolved". This entire research group has been labeled as "Evolutionary Algorithms".
Evolutionary algorithm is an umbrella term used to describe computer-based problem solving systems which use "natural" computational models where evolution is the key element in design and implementation. A variety of evolutionary methods have been proposed. The major ones are:
GENETIC ALGORITHMS
EVOLUTIONARY PROGRAMMING
EVOLUTION STRATEGIES
CLASSIFIER SYSTEMS
GENETIC PROGRAMMING
They all share a common base of simulating the evolution of individual structures via processes of selection, mutation, and reproduction. Details
Origin of Genetic Algorithms?
It was in the 1950/60s that several independant researchers were studying the idea that evolution could be used as an optimization tool for engineering problems. The idea behind it all was to evolve solutions to problems by using natural means based on survival of the fittest. evolutionary strategies was introduced in the mid 60s by Rechenberg as a method he used to optimize real-valued parameters for hardware devices. Owens, Fogel and Walsh developed evolutionary programming, a techniwue used where candidate solutions to problems or tasks were represented as finite-state machines which were evolved by randomly mutating their state-transition diagrams and then selecting the fittest. Together with genetic algorithms, these three areas form the backbone of evolutionary computation.
Genetic algorithms were invented by Holland in the 60's and developed later in the 70's. This method was defined as a way to move from one popluation of chromosomes to another by utilizing natural selection and the operator of crossover, mutation, and inversion.
In recent years, there was been widespread interaction among researchers from varied evolution-based studies and as a result, we find some breakdown in the boundaries that define and separate the fields of genetic algorithms, evolution strategies, and evolutionary programming. Often, the term - genetic algorithm - is used to describe something very different from what was originally defined.
What are Genetic Algorithms?
Genetic Algorithms are nondeterministic stochastic search/optimization methods that utilize the theories of evolution and natural selection to solve a problem within a complex solution space.
GAs maintain a population of structures, that evolve according to rules of selection and genetic operators such as recombination and mutation. Details
Each individual in the population receives a measure of it's fitness in the environment.
Reproduction focuses attention on high fitness individuals.
Recombination and mutation provide general heuristics for exploration by adding variability.
GAs differ from conventional optimization/search procedures in that:
1. They work with a coding of the parameter set, not the parameters themselves.
2. They search from a population of points in the problem domain, not a
singular point.
3. They use a payoff information as the objective function rather than
derivatives of the problem or auxiliary knowledge.
4. They utilize probabilistic transition rules based on fitness rather
than deterministic one.
When Would You Use a Genetic Algorithm?
GAs are especially badly suited for problems where
efficient ways of solving them are already known.
(unless these problems are intended to serve as benchmarks). Special purpose
algorithms, i.e. algorithms that have a certain amount of problem domain
knowledge hard coded into them, will usually outperform GAs, so there is
no black magic in evolutionary computation.
GAs should be used when there is no other known efficient
problem solving strategy, and the problem domain is NP-complete.
GAs come into play, heuristically finding solutions where all else fails
or when you have a noisy search space. Examples.
Genetic programming is the extension of the genetic model of learning, as with genetic algorithms, into the space of programs. That is, the objects that constitute the population are not fixed-length character strings that encode possible solutions to the problem at hand, they are programs that, when executed, "are" the candidate solutions to the problem. These programs are expressed in genetic programming as parse trees, rather than as lines of code and are the chomosomes or individuals in the population upon which genetic operation occurs. Fitness is evaluated by how best they solve the problem addressed given a certain efficiency level and crossover takes places at randomized loci on the parse trees. Mutation is often not implemented in genetic programming and much discussion has been held about its usefulness or lack of.
Let's come to TERMS
(GP-Related):
Five Major Preparation Steps when applying genetic programming to a problem, define the following:
1. the set of terminals
2. the set of primitive functions
3. the fitnes measure
4. the parameters for controlling the run
5. the method for designating a result and the criterion
for terminating the run.
Evolving Algorithms
Research Environment and Tools