genetic algorithms

A genetic algorithm (GA) is a search technique used in computer science to find approximate solutions to optimization and search problems. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, Mutation (genetic algorithm)mutation, natural selection, and crossover (genetic algorithm)recombination (or crossover). Genetic algorithms are typically implemented as a computer simulation in which a population of abstract representations (called ''chromosome (genetic algorithm)chromosomes'') of candidate solutions (called ''individuals'') to an optimization problem evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but different encodings are also possible. The evolution starts from a population of completely random individuals and happens in generations. In each generation, the fitness (biology)fitness of the whole population is evaluated, multiple individuals are stochasticstochastically selected from the current population (based on their fitness), modified (mutated or recombined) to form a new population, which becomes current in the next iteration of the algorithm.

Operation of a GA - An individual, or solution to the problem to be solved, is represented by a list of parameters, called chromosome (genetic algorithm)chromosome or genome (genetic algorithm)genome. Chromosomes are typically represented as simple string#Mathematics and Computer Sciencestrings of data and instructions, although a wide variety of other data structures for storing chromosomes may also be used. Initially several such individuals are randomly generated to form the first initial population. The user of the algorithm may seed the gene pool with "hints" to form an initial population of possible solutions.During each successive generation, each individual is evaluated, and a value of fitness is returned by a fitness function. The pool is sorted, with those having better fitness (representing better solutions to the problem) ranked at the top. Notice that "better" in this context is relative, as initial solutions are all likely to be rather poor.The next step is to generate a second generation population of organisms, based on the processes of selection (genetic algorithm)selection and reproduction of selected individuals through genetic operators; crossover (genetic algorithm)crossover (or recombination (genetic algorithm)recombination), and mutation (genetic algorithm)mutation. For each individual to be produced, a pair of ''parent'' organisms is selected for breeding. Selection is biased towards elements of the initial generation which have better fitness, though it is usually not so biased that poorer elements have no chance to participate, in order to prevent the population from converging too early to a sub-optimal or local solution. There are several well-defined organism selection methods; roulette wheel selection and tournament selection are popular methods.Following selection, the ''crossover (genetic algorithm)crossover'' (or ''recombination (genetic algorithm)recombination'') operation is performed upon the selected chromosomes. Commonly, genetic algorithms have a ''probability of crossover'', typically between 0.6 and 1.0, which encodes the probability that two selected organisms will actually breed. Organisms are recombined by this probability. Crossover results in two new child chromosomes, which are added to the next generation population. The chromosomes of the parents are mixed during crossover, typically by simply swapping a portion of the underlying data structure (although other, more complex merging mechanisms have proved useful for certain types of problems). This process is repeated with different parent organisms until there are an appropriate number of candidate solutions in the next generation population. The next step is to mutation (genetic algorithm)mutate the newly created offspring. Typical genetic algorithms have a fixed, very small ''probability of mutation'' on the order of 0.01 or less. Based on this probability, the new child organism's chromosome is randomly mutated, typically by flipping bits in the chromosome data structure.These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding. The entire process is repeated for this second generation: each organism is evaluated, the fitness value for each organism is obtained, pairs are selected for breeding, a third generation population is generated, etc. This generational process is repeated until a termination condition has been reached. Common terminating conditions are

Fixed number of generations reached

Allocated budget (computation time/money) reached

An individual is found that satisfies minimum criteria

The highest ranking individual's fitness is reaching or has reached a plateau such that successive iterations do no longer produce better results

Manual inspection

Combinations of the above

Pseudo-code algorithm - Choose initial population Repeat Evaluate the individual fitnesses of a certain proportion of the population Select pairs of best-ranking individuals to reproduce Apply crossover operator Apply mutation operator Until terminating condition

Observations - There are several general observations about the generation of solutions via a genetic algorithm:

Unless the fitness function is handled properly, GAs may have a tendency to converge towards local optimumlocal optima rather than the global optimum of the problem.

Operating on dynamic data sets is difficult, as genomes begin to converge early on towards solutions which may no longer be valid for later data. Several methods have been proposed to remedy this by increasing genetic diversity somehow and preventing early convergence, either by increasing the probability of mutation when the solution quality drops (called ''triggered hypermutation''), or by occasionally introducing entirely new, randomly generated elements into the gene pool (called ''random immigrants'').

Selection is clearly an important genetic operator, but opinion is divided over the importance of crossover versus mutation. Some argue that crossover is the most important, while mutation is only necessary to ensure that potential solutions are not lost. Others argue that crossover in a largely uniform population only serves to propagate innovations originally found by mutation, and in a non-uniform population crossover is nearly always equivalent to a very large mutation (which is likely to be catastrophic).

GAs can rapidly locate ''good'' solutions, even for difficult search spaces.

For specific optimization problems and problem instantiations, simpler optimization algorithms may find better solutions than genetic algorithms (given the same amount of computation time). GA practitioners may wish to try other algorithms in addition to GAs.

GAs cannot effectively solve problems in which there is no way to judge the fitness of an answer other than right/wrong, as there is no way to converge on the solution. These problems are often called "needle in a haystack" problems.

As with all current machine learning problems it is worth tuning the parameters such as mutation probability, recombination probability and population size to find reasonable settings for the problem class you are working on. A very small mutation rate may lead to genetic drift (which is non-ergodic in nature) or premature convergence of the genetic algorithm in a local optimum. A mutation rate that is too high may lead to loss of good solutions. There are theoretical but not yet practical upper and lower bounds for these parameters that can help guide selection.

How the fitness function is evaluated is an important factor in speed and efficiency of the algorithm.

Variants - The simplest algorithm represents each chromosome as a bit string#Mathematics and Computer Sciencestring. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, associative arrayhashes, object (computer science)objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.A slight, but very successful variant of the general process of constructing a new population is to allow some of the better organisms from the current generation to carry over to the next, unaltered. This strategy is known as ''elitist selection''.Parallel implementations of genetic algorithms come in two flavours. Coarse grained parallel genetic algorithms assume a population on each of the computer nodes and migration of individuals among the nodes. Fine grained parallel genetic algorithms assume an individual on each processor node which acts with neighboring individuals for selection and reproduction.Other variants, like genetic algorithms for online optimization problems, introduce time-dependence or noise in the fitness function.

Problem domains - Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabletimetabling and scheduling problems, and many scheduling software packages are based on GAs. GAs have also been applied to engineering. Genetic algorithms are often applied as an approach to solve global optimization problems. As a general rule of thumb genetic algorithms might be useful in problem domains that have a complex fitness landscape as recombination is designed to move the population away from local minima that a traditional hill climbing algorithm might get stuck in.

History - Genetic algorithms or "GAs" originated from the studies of cellular automata, conducted by John Henry HollandJohn Holland and his colleagues at the University of Michigan. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held at The University of Illinois. As academic interest grew, the dramatic increase in desktop computational power allowed for practical application of the new technique. In 1989, The New York Times writer John Markoff wrote about Evolver (software)Evolver, the first commercially available desktop genetic algorithm. Custom computer applications began to emerge in a wide variety of fields, and these algorithms are now used by a majority of Fortune 500 companies to solve difficult scheduling, data fitting, trend spotting, budgeting and virtually any other type of combinatorial optimization.

Applications -

Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics.

Automated design of mechatronicsmechatronic systems using bond graphs and genetic programming (NSF).

Calculation of Bound States and Local Density Approximations.

Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (Fullerenebuckyballs).

Container loading optimization.

Distributed computer network topologies.

Electronic circuit design, known as Evolvable hardware.

File allocation for a distributed system.

Parallelization of GAs/GPs including use of hierarchical decomposition of problem domains and design spaces nesting of irregular shapes using feature matching and GAs.

Game Theory Equilibrium Resolution.

Learning Robot behavior using Genetic Algorithms.

Learning fuzzy rule base using genetic algorithms.

Mobile communications infrastructure optimization.

Molecular Structure Optimization (Chemistry).

Multiple population topologies and interchange methodologies.

Protein folding and protein/ligand docking.

Plant floor layout.

Scheduling applications, including job-shop scheduling. The objective being to schedule jobs in a sequence dependent or non-sequence dependent setup environment in order to maximize the volume of production while minimizing penalties such as tardiness.

Software engineering

Solving the machine-component grouping problem required for cellular manufacturing systems.

Tactical asset allocation and international equity strategies.

TimetableTimetabling problems, such as designing a non-conflicting class timetable for a large university.

Training artificial neural networks when pre-classified training examples are not readily obtainable (neuroevolution).

Traveling Salesman Problem.

Related techniques - Genetic programming (GP) is a related technique popularized by John Koza, in which computer programs, rather than function parameters, are optimized. Genetic programming often uses Tree_data_structuretree-based internal data structures to represent the computer programs for adaptation instead of the linked listlist, or array, structures typical of genetic algorithms. GP algorithms typically require running time that is orders of magnitude greater than that for genetic algorithms, but they may be suitable for problems that are intractable with genetic algorithms.Interactive genetic algorithms are genetic algorithms that use human evaluation. They are usually applied to domains where it is hard to design a computational fitness function, for example, evolving images, music, artistic designs and forms to fit users' aesthetic preference.Simulated Annealing (SA) is a related global optimization technique which traverses the search space by testing random mutations on an individual solution. A mutation that increases fitness is always accepted. A mutation which lowers fitness is accepted probabilistically based on the difference in fitness and a decreasing temperature parameter. In SA parlance, one speaks of seeking the lowest energy instead of the maximum fitness. SA can also be used within a standard GA algorithm, simply by starting with a relatively high rate of mutation, which decreases over time along a given schedule.Tabu search (TS) is similar to Simulated Annealing, in that both traverse the solution space by testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest fitness of those generated. In order to prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions. It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas. While usually inferior to genetic algorithms and other forms of local search, it is able to produce results in problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied.Memetic Algorithm is a term that is used by some researchers to define forms of genetic algorithm that are combined with other forms of local search, such as simulated annealing.

Building block hypothesis - Goldberg, - 1989, page 41 talking of binary bit string genetic algorithms says "''Short, low order, and highly fit schemaschemata are sampled, crossover (genetic algorithm)recombined'' (crossed over), ''and resampled to form strings of potentially higher fitness. In a way, by working with these particular schemata (the building blocks), we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings.''" "''Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood'' (building blocks), ''so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks.'' Note Goldberg, - 1989 suggests that building blocks are highly fit schemata with only a few defined bits (low order), and that these are close together (short).

References -

Goldberg, David E (1989), ''Genetic Algorithms in Search, Optimization and Machine Learning,'' Kluwer Academic Publishers, Boston, MA.

Goldberg, David E (2002), ''The Design of Innovation: Lessons from and for Competent Genetic Algorithms,'' Addison-Wesley, Reading, MA.

Harvey, Inman (1992), ''Species Adaptation Genetic Algorithms: A basis for a continuing SAGA'', in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.

Holland, John H (1975), "Adaptation in Natural and Artificial Systems", University of Michigan Press, Ann Arbor

Koza, John (1992), ''Genetic Programming: On the Programming of Computers by Means of Natural Selection''

Michalewicz, Zbigniew (1999), ''Genetic Algorithms + Data Structures = Evolution Programs'', Springer-Verlag.

Mitchell, Melanie, (1996), ''An Introduction to Genetic Algorithms'', MIT Press, Cambridge, MA.

Schmitt, Lothar M (2001), ''Theory of Genetic Algorithms'', Theoretical Computer Science (259), pp. 1-61

Schmitt, Lothar M (2004), ''Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling'', Theoretical Computer Science (310), pp. 181-231

Vose, Michael D (1999), ''The Simple Genetic Algorithm: Foundations and Theory'', MIT Press, Cambridge, MA.

External links -

!http://cs.felk.cvut.cz/~xobitk o/ga/? - An online introduction to genetic algorithms with Java applets

www-illigal.ge.uiuc.edu - IlliGAL - Illinois Genetic Algorithms Laboratory - Download technical reports and code

demo.cs.brandeis.edu - Golem Project - Automatic Design and Manufacture of Robotic Lifeforms

? epcc.ed.ac.uk - Introduction to Genetic Algorithms Using RPL2

talkorigins.org - Talk.Origins FAQ on the uses of genetic algorithms, by Adam Marczyk

fenews.com - Genetic algorithm in search and optimization, by Richard Baker

icsi.berkeley.edu - Differential Evolution using Genetic Algorithm

biometris.nl - Genetic algorithms and Markov Chain Monte Carlo: Differential Evolution makes Bayesian computing easy (genetic algorithm for statistical analysis)

ai-junkie.com - Introduction to Genetic Algorithms and Neural Networks including an example windows program

cut-the-knot.org - Genetic Algorithm Solves the Toads and Frogs Puzzle (requires Java)

marketingprofs.com - Not-So-Mad Science: Genetic Algorithms and Web Page Design for Marketers by Matthew Syrett

ocw.mit.edu - MIT OpenCourseWare Health Sciences and Technology HST.508 Genomics and Computational Biology, Fall 2002 Lecture Notes

samizdat.mines.edu - A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory

lut.fi - Evolutionary computing in search-based software engineering. Leo Rela. How evolutionary computing (specifically GA) is used in software engineering.

geocities.com - Heuristics and artificial intelligence in finance and investment - The use of genetic algorithms in finance and !investment.Category:Cybernetic sCategory:Genetic? !algorithmsCategory:Optimizatio n? !algorithmsCategory:Evolutionar y? !algorithmsar:خوارزميا� �? وراثيةcs:Genetický algoritmusde:Genetischer Algorithmuses:Algoritmos genéticosfr:Algorithme génétiqueit:Algoritmo geneticolt:Genetiniai algoritmainl:Genetisch !algoritmeja:遺伝的アルゴ リズムpl:Algorytm? !genetycznyru:Генетиче� �кий? !алгоритмth:ขั้� �ตอนวิธีเช� �งพันธุกรร� �vi:Giải? thuật di !truyềnzh:遗传算法 DEBUG REDIRECT (genetic algorithm)