A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination). Searching is the act of trying to find something or someone. ... For the formal concept of computation, see computation. ... An approximation is an inexact representation of something that is still close enough to be useful. ... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ... Searching is the act of trying to find something or someone. ... Look up Problem in Wiktionary, the free dictionary. ... For Wikipedias categorization projects, see Wikipedia:Categorization. ... Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria. ... In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. ... In computer science evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) involving combinatorial optimization problems. ... This article or section does not cite any references or sources. ... Biological inheritance is the process by which an offspring cell or organism acquires or becomes predisposed to characteristics of its parent cell or organism. ... In genetic algorithms, mutation is a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next. ... It has been suggested that this article or section be merged with Genetic algorithm. ... In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. ... Recombination usually refers to the biological process of genetic recombination and meiosis, a genetic event that occurs during the formation of sperm and egg cells. ...

To meet Wikipedias quality standards, this article or section may require cleanup. ... In computer science, A* (pronounced A star) is a graph/tree search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ... The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ... Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ... Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. ... In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... In computer science, the Floyd–Warshall algorithm (sometimes known as the Roy–Floyd algorithm, since Bernard Roy described this algorithm in 1959) is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. ... Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. ... Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. ... Johnsons algorithm is a way to solve the all-pairs shortest path problem in a sparse, weighted, directed graph. ... In computer science, uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. ...

Methodology

Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached. Look up Implementation in Wiktionary, the free dictionary. ... It has been suggested that simulation software be merged into this article or section. ... Look up abstract, abstraction in Wiktionary, the free dictionary. ... In genetic algorithms, a chromosome (also sometimes called a genome) is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve. ... This article does not cite any references or sources. ... In biology the genome of an organism is the whole hereditary information of an organism that is encoded in the DNA (or, for some viruses, RNA). ... In optimization (a branch of mathematics), a candidate solution is a member of a set of possible solutions to a given problem. ... Individuals in the mollusk species Donax variabilis show diverse coloration and patterning in their phenotypes. ... In the mathematics of probability, a stochastic process can be thought of as a random function. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ...

Genetic algorithms find application in biogenetics, computer science, engineering, economics, chemistry, manufacturing, mathematics, physics and other fields. An iconic image of genetic engineering; this autoluminograph from 1986 of a glowing transgenic tobacco plant bearing the luciferase gene, illustrating the possibilities of genetic engineering. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Engineering is the discipline of acquiring and applying knowledge of design, analysis, and/or construction of works for practical purposes. ... Face-to-face trading interactions on the New York Stock Exchange trading floor. ... For other uses, see Chemistry (disambiguation). ... Manufacturing (from Latin manu factura, making by hand) is the use of tools and labor to make things for use or sale. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ...

A typical genetic algorithm requires two things to be defined:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain.

A standard representation of the solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, that facilitates simple crossover operation. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in Genetic programming and graph-form representations are explored in Evolutionary programming. Genetic representation is a way of representing solutions/individuals in evolutionary computation methods. ... Look up domain in Wiktionary, the free dictionary. ... A fitness function is a particular type of objective function that quantifies the optimality of a solution (that is, a chromosome) in a genetic algorithm so that that particular chromosome may be ranked against all the other chromosomes. ... A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). ... Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. ... It is a subset of Evolutionary algorithm. ...

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem we want to maximize the total value of objects that we can put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise. In some problems, it is hard or even impossible to define the fitness expression; in these cases, interactive genetic algorithms are used. Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under 15 kg? A multi dimensional problem could consider the density or dimensions of the boxes, the latter a typical packing problem. ... Interactive genetic algorithm (IGA) is defined as a genetic algorithm that use human evaluation. ...

Once we have the genetic representation and the fitness function defined, GA proceeds to initialize a population of solutions randomly, then improve it through repetitive application of mutation, crossover, inversion and selection operators.

Initialization

Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

Selection

Main article: Selection (genetic algorithm)

During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as this process may be very time-consuming. It has been suggested that this article or section be merged with Genetic algorithm. ... It has been suggested that this article or section be merged with Genetic algorithm. ... Fitness (often denoted in population genetics models) is a central concept in evolutionary theory. ... A fitness function is a particular type of objective function that quantifies the optimality of a solution (that is, a chromosome) in a genetic algorithm so that that particular chromosome may be ranked against all the other chromosomes. ...

Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. This helps keep the diversity of the population large, preventing premature convergence on poor solutions. Popular and well-studied selection methods include roulette wheel selection and tournament selection. Stochastic, from the Greek stochos or goal, means of, relating to, or characterized by conjecture; conjectural; random. ... Fitness proportionate selection, also known as roulette-wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination. ... Tournament selection is one of many methods of selection in genetic algorithms which runs a tournament among a few individuals chosen at random from the population and selects the winner (the one with the best fitness) for crossover. ...

Reproduction

Main articles: crossover (genetic algorithm) and mutation (genetic algorithm)

The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation. In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. ... In genetic algorithms, mutation is a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next. ... A genetic operator is a process used in genetic algorithms to maintain genetic diversity. ... In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. ... In genetic algorithms, mutation is a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next. ...

For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each child, and the process continues until a new population of solutions of appropriate size is generated.

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, along with a small proportion of less fit solutions, for reasons already mentioned above.

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.

Pseudo-code algorithm

1. Choose initial population
2. Evaluate the fitness of each individual in the population
3. Repeat
   1. Select best-ranking individuals to reproduce
   2. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring
   3. Evaluate the individual fitnesses of the offspring
   4. Replace worst ranked part of population with offspring
4. Until termination

Fitness (often denoted in population genetics models) is a central concept in evolutionary theory. ... As commonly used, individual refers to a person or to any specific object in a collection. ... Reproduction is the creation of one thing as a copy of, product of, or replacement for a similar thing, e. ... A breed is a domesticated subspecies or infrasubspecies of an animal. ... Generation (From the Greek γιγνμαι), also known as procreation, is the act of producing offspring. ... In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. ... In genetic algorithms, mutation is a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next. ... In biology, offspring are the product of reproduction, a new organism produced by one or more parents. ... An interpreter is a computer program that executes other programs. ...

Observations

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

• In many problems, GAs may have a tendency to converge towards local optima or even arbitrary points rather than the global optimum of the problem. This means that it does not "know how" to sacrifice short-term fitness to gain longer-term fitness. The likelihood of this occurring depends on the shape of the fitness landscape: certain problems may provide an easy ascent towards a global optimum, others may make it easier for the function to find the local optima. This problem may be alleviated by using a different fitness function, increasing the rate of mutation, or by using selection techniques that maintain a diverse population of solutions, although the No Free Lunch theorem proves that there is no general solution to this problem. A common technique to maintain diversity is to impose a "niche penalty", wherein, any group of individuals of sufficient similarity (niche radius) have a penalty added, which will reduce the representation of that group in subsequent generations, permitting other (less similar) individuals to be maintained in the population. This trick, however, may not be effective, depending on the landscape of the problem. Diversity is important in genetic algorithms (and genetic programming) because crossing over a homogeneous population does not yield new solutions. In evolution strategies and evolutionary programming, diversity is not essential because of a greater reliance on mutation.
• 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). Recent research has also shown the benefits of using biological exaptation (or preadaptation) in solving this problem. Again, evolution strategies and evolutionary programming can be implemented with a so-called "comma strategy" in which parents are not maintained and new parents are selected only from offspring. This can be more effective on dynamic problems.
• GAs cannot effectively solve problems in which the only fitness measure is right/wrong, as there is no way to converge on the solution. (No hill to climb.) In these cases, a random search may find a solution as quickly as a GA.
• 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). There are many references in Fogel (2006) that support the importance of mutation-based search, but across all problems the No Free Lunch theorem holds, so these opinions are without merit unless the discussion is restricted to a particular problem.
• Often, GAs can rapidly locate good solutions, even for difficult search spaces. The same is of course also true for evolution strategies and evolutionary programming.
• For specific optimization problems and problem instantiations, simpler optimization algorithms may find better solutions than genetic algorithms (given the same amount of computation time). Alternative and complementary algorithms include evolution strategies, evolutionary programming, simulated annealing, Gaussian adaptation, hill climbing, and swarm intelligence (e.g.: ant colony optimization, particle swarm optimization).
• 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 being worked on. A very small mutation rate may lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions unless there is elitist selection. There are theoretical but not yet practical upper and lower bounds for these parameters that can help guide selection.
• The implementation and evaluation of the fitness function is an important factor in the speed and efficiency of the algorithm.

local optimum is a term in Applied mathematics and Computer Science. ... Polynomial of degree 4, on the right one finds a local optimum, on the left is the global optimum. ... In evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between genotypes (or phenotypes) and replicatory success. ... Many computational problems are solved by searching for good solutions in a space of candidates. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ... Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... An exaptation is a biological adaptation where the biological function currently performed by the adaptation was not the function performed while the adaptation evolved under earlier pressures of natural selection. ... In evolutionary biology, preadaptation describes a situation where an organism uses a preexisting anatomical structure inherited from an ancestor for a potentially unrelated purpose. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... Many computational problems are solved by searching for good solutions in a space of candidates. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... For other uses, see Annealing. ... The creator of or main contributor to this page may have a conflict of interest with the subject of this article. ... Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. ... Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems. ... The ant colony optimization algorithm (ACO), introduced by Marco Dorigo [Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ... Particle swarm optimization (PSO) is a stochastic, population-based computer problem-solving algorithm; it is a kind of swarm intelligence that is based on social-psychological principles and provides insights into social behavior, as well as contributing to engineering applications. ... For linguistic mutation, see Apophony. ... Recombination usually refers to the biological process of genetic recombination and meiosis, a genetic event that occurs during the formation of sperm and egg cells. ... In population genetics, genetic drift is the statistical effect that results from the influence that chance has on the success of alleles (variants of a gene). ...

Variants

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). 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, hashes, 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. This article is about the unit of information. ... The integers are commonly denoted by the above symbol. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... In strictly mathematical branches of computer science the term object is used in a purely mathematical sense to refer to any thing. While this interpretation is useful in the discussion of abstract theory, it is not concrete enough to serve as a primitive datatype in the discussion of more concrete... A binary tree, a simple type of branching linked data structure. ...

When bit strings representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily effected through mutations or crossovers. This has been found to help prevent premature convergence at so called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution. A Gray code is a binary numeral system where two successive values differ in only one digit, originally designed to prevent spurious output from electromechanical switches. ...

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Theoretically, the smaller the alphabet, the better the performance, but paradoxically, good results have been obtained from using real-valued chromosomes.

A very successful (slight) 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.

It can be quite effective to combine GA with other optimization methods. GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA while overcoming the lack of robustness of hill climbing.

An algorithm that maximizes mean fitness (without any need for the definition of mean fitness as a criterion function) is Gaussian adaptation, See Kjellström 1970^[1], provided that the ontogeny of an individual may be seen as a modified recapitulation of evolutionary random steps in the past and that the sum of many random steps tend to become Gaussian distributed (according to the central limit theorem). The creator of or main contributor to this page may have a conflict of interest with the subject of this article. ... A central limit theorem is any of a set of weak-convergence results in probability theory. ...

This means that the rules of genetic variation may have a different meaning in the natural case. For instance - provided that steps are stored in consecutive order - crossing over may sum a number of steps from maternal DNA adding a number of steps from paternal DNA and so on. This is like adding vectors that more probably may follow a ridge in the phenotypic landscape. Thus, the efficiency of the process may be increased by many orders of magnitude. Moreover, the inversion operator has the opportunity to place steps in consecutive order or any other suitable order in favour of survival or efficiency. (See for instance [1] or example in travelling salesman problem.) In the mathematics, inversion operator can refer to: the operator which assigns the inverse element to an element of a group Inversion in a point Chromosomal inversion, reordering of genes in a DNA-sequence. ... If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A? The traveling salesman problem (TSP) is a problem in discrete or combinatorial optimization. ...

Gaussian adaptation is able to approximate the natural process by an adaptation of the moment matrix of the Gaussian. So, because very many quantitative characters are Gaussian distributed in a large population, Gaussian adaptation may serve as a genetic algorithm replacing the rules of genetic variation by a Gaussian random number generator working on the phenotypic level. See Kjellström 1996^[2]

Population-based incremental learning is a variation where the population as a whole is evolved rather than its individual members. In machine learning and soft computing, population-based incremental learning (PBIL) is a type of genetic algorithm where the genotype of an entire population is evolved rather than individual members[1]. // In PBIL, genes are represented as real values in the range [0,1], indicating the probability that any particular...

Problem domains

Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling 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. A timetable is an organized list or schedule, usually set out in tabular form, providing information about a series of arranged events: in particular, the time at which it is planned these events will take place. ... Look up scheduling in Wiktionary, the free dictionary. ... Engineering is the discipline of acquiring and applying knowledge of design, analysis, and/or construction of works for practical purposes. ... Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria. ...

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 optima that a traditional hill climbing algorithm might get stuck in. In evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between genotypes (or phenotypes) and replicatory success. ... Recombination usually refers to the biological process of genetic recombination and meiosis, a genetic event that occurs during the formation of sperm and egg cells. ... Local optimum is a term in applied mathematics and computer science. ... Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. ...

History

Computer simulations of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey.^{[3] [4]} His 1954 publication was not widely noticed. Starting in 1957 ^[5], the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970)^[6] and Crosby (1973)^[7]. Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms. Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998).^[8] Fuld Hall The Institute for Advanced Study, located in Princeton, New Jersey, United States, is one of the world’s leading centers for theoretical research and intellectual inquiry. ... Nassau Street, Princetons main street. ... Alex Fraser (1923-2002) was a major innovator in the development of the computer modeling of population genetics and his work has stimulated many advances in genetic research over the past decades. ... This Chihuahua mix and Great Dane show the wide range of dog breed sizes created using artificial selection. ...

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game,^[9] artificial evolution became a widely recognized optimization method as a result of the work of Ingo Rechenberg and Hans-Paul Schwefel in the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies ^{[10] [11] [12]}. Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland's Schema Theorem. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania. An evolutionary algorithm (also EA, evolutionary computation, artificial evolution) is a generic term used to indicate any population-based optimization algorithm that uses mechanisms inspired by biological evolution, such as reproduction, mutation and recombination (see genetic operators). ... Ingo Rechenberg is a pioneer of the fields of evolutionary computation and artificial evolution. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... Dr. Lawrence J. Fogel (March 2, 1928 - February 18, 2007), was a pioneer in evolutionary computation and human factors analysis. ... It is a subset of Evolutionary algorithm. ... Dr. John Henry Holland (February 2, 1929) is known as the father of genetic algorithms. ... A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory and mathematics. ... Dr. John Henry Holland (February 2, 1929) is known as the father of genetic algorithms. ... The University of Michigan, Ann Arbor (U of M, UM or simply Michigan) is a coeducational public research university in the state of Michigan. ... Hollands schema theorem is widely taken to be the foundation for explanations of the power of genetic algorithms. ... Pittsburgh redirects here. ...

As academic interest grew, the dramatic increase in desktop computational power allowed for practical application of the new technique. In the late 1980s, General Electric started selling the world's first genetic algorithm product, a mainframe-based toolkit designed for industrial processes. In 1989, Axcelis, Inc. released Evolver, the world's second GA product and the first for desktop computers. The New York Times technology writer John Markoff wrote^[13] about Evolver in 1990. Evolver is a software package that allows users to solve a wide variety of optimization problems using a genetic algorithm. ... The New York Times is a daily newspaper published in New York City and distributed internationally. ... John Markoff (born October 24, 1949) is an American writer and journalist. ...

Related techniques

• 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.^{[citation needed]}

• Bacteriologic Algorithms (BA) inspired by evolutionary ecology and, more particularly, bacteriologic adaptation. Evolutionary ecology is the study of living organisms in the context of their environment, with the aim of discovering how they adapt. Its basic concept is that in a heterogeneous environment, you can’t find one individual that fits the whole environment. So, you need to reason at the population level. BAs have shown better results than GAs on problems such as complex positioning problems (antennas for cell phones, urban planning, and so on) or data mining.^[14]

• Cross-entropy method The Cross-entropy (CE) method generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.

• Cultural algorithm (CA) consists of the population component almost indentical to that of the genetic algorithm and, in addition, a knowledge component called the belief space.

• Evolution strategies (ES, see Rechenberg, 1971) evolve individuals by means of mutation and intermediate and discrete recombination. ES algorithms are designed particularly to solve problems in the real-value domain. They use self-adaptation to adjust control parameters of the search.

• Evolutionary programming (EP) involves populations of solutions with primarily mutation and selection and arbitrary representations. They use self-adaptation to adjust parameters, and can include other variation operations such as combining information from multiple parents.

• Extremal optimization (EO) Unlike GAs, which work with a population of candidate solutions, EO evolves a single solution and makes local modifications to the worst components. This requires that a suitable representation be selected which permits individual solution components to be assigned a quality measure ("fitness"). The governing principle behind this algorithm is that of emergent improvement through selectively removing low-quality components and replacing them with a randomly selected component. This is decidedly at odds with a GA that selects good solutions in an attempt to make better solutions.

• Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended for the maximisation of manufacturing yield of signal processing systems. It may also be used for ordinary parametric optimisation. It relies on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA relies on information theory and a certain theorem of efficiency. Its efficiency is defined as information divided by the work needed to get the information^[15]. Because NA maximises mean fitness rather than the fitness of the individual, the landscape is smoothed such that valleys between peaks may disappear. Therefore it has a certain “ambition” to avoid local peaks in the fitness landscape. NA is also good at climbing sharp crests by adaptation of the moment matrix, because NA may maximise the disorder (average information) of the Gaussian simultaneously keeping the mean fitness constant.

• 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-based internal data structures to represent the computer programs for adaptation instead of the list structures typical of genetic algorithms.

• Grouping Genetic Algorithm (GGA) is an evolution of the GA where the focus is shifted from individual items, like in classical GAs, to groups or subset of items.^[16] The idea behind this GA evolution proposed by Emanuel Falkenauer is that solving some complex problems, a.k.a. clustering or partitioning problems where a set of items must be split into disjoint group of items in an optimal way, would better be achieved by making characteristics of the groups of items equivalent to genes. These kind of problems include Bin Packing, Line Balancing, Clustering w.r.t. a distance measure, Equal Piles, etc., on which classic GAs proved to perform poorly. Making genes equivalent to groups implies chromosomes that are in general of variable length, and special genetic operators that manipulate whole groups of items. For Bin Packing in particular, a GGA hybridized with the Dominance Criterion of Martello and Toth, is arguably the best technique to date.

• Harmony search (HS) is an algorithm mimicking musicians behaviors in improvisation process.

• Interactive evolutionary algorithms are evolutionary 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.

• Memetic algorithm (MA), also called hybrid genetic algorithm among others, is a relatively new evolutionary method where local search is applied during the evolutionary cycle. The idea of memetic algorithms comes from memes, which–unlike genes–can adapt themselves. In some problem areas they are shown to be more efficient than traditional evolutionary algorithms.

• Simulated annealing (SA) is a related global optimization technique that traverses the search space by testing random mutations on an individual solution. A mutation that increases fitness is always accepted. A mutation that 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 by starting with a relatively high rate of mutation and decreasing it over time along a given schedule.

• Stochastic optimization is an umbrella set of methods that includes GAs and numerous other approaches.

• 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 energy 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.

The ant colony optimization algorithm (ACO), introduced by Marco Dorigo [Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ... Evolutionary ecology lies at the intersection ecology and evolutionary biology. ... The cross-entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. ... Cultural algorithms are a branch of evolutionary computation where there is a knowledge component that is called the belief space in addition to the population component. ... In computer science, evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... It is a subset of Evolutionary algorithm. ... Extremal Optimization (EO) is an optimization heuristic inspired by the Bak-Sneppen model of self-organized criticality from the field of statistical physics. ... Local search is a metaheuristic for solving computationally hard optimization problems. ... The creator of or main contributor to this page may have a conflict of interest with the subject of this article. ... Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... Fitness (often denoted in population genetics models) is a central concept in evolutionary theory. ... Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. ... John R. Koza is a computer scientist and a consulting professor at Stanford University, most notable for his work in pioneering the use of genetic programming for the optimization of complex problems, and for the evolution of computer programs which solve them. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... A binary tree, a simple type of branching linked data structure. ... Look up list in Wiktionary, the free dictionary. ... In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ... In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ... This article needs additional references or sources to facilitate its verification. ... Interactive evolutionary computation (IEC) or Aesthetic Selection is a general term for methods of evolutionary computation that use human evaluation. ... Memetic algorithms is a population-based approach for heuristic search in optimization problems. ... For other uses, see Meme (disambiguation). ... For other uses, see Annealing. ... Stochastic optimization (SO) methods are optimization algorithms which incorporate probabilistic (random) elements, either in the problem data (the objective function, the constraints, etc. ... Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ...

Building block hypothesis

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular it is difficult to understand why they are often successful in generating solutions of high fitness. The building block hypothesis (BBH) consists of

1. A description of an abstract adaptive mechanism that performs adaptation by recombining "building blocks", i.e. low order, low defining-length schemata with above average fitness.
2. A hypothesis that a genetic algorithm performs adaptation by implicitly and efficiently implementing this abstract adaptive mechanism.

(Goldberg 1989:41) describes the abstract adaptive mechanism as follows:

Short, low order, and highly fit schemata are sampled, 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.

(Goldberg 1989) claims that the building block hypothesis is supported by Holland's schema theorem. In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. ... Hollands schema theorem is widely taken to be the foundation for explanations of the power of genetic algorithms. ...

The building block hypothesis has been sharply criticized on the grounds that it lacks theoretical justification and experimental results have been published that draw its veracity into question. On the theoretical side, for example, Wright et al. state that

"The various claims about GAs that are traditionally made under the name of the building block hypothesis have, to date, no basis in theory and, in some cases, are simply incoherent"^[17]

On the experimental side uniform crossover was seen to outperform one-point and two-point crossover on many of the fitness functions studied by Syswerda.^[18] Summarizing these results, Fogel remarks that

"Generally, uniform crossover yielded better performance than two-point crossover, which in turn yielded better performance than one-point crossover"^[19]

Syswerda's results contradict the building block hypothesis because uniform crossover is extremely disruptive of short schemata whereas one and two-point crossover are more likely to conserve short schemata and combine their defining bits in children produced during recombination.

The debate over the building block hypothesis demonstrates that the issue of how GAs "work", (i.e. perform adaptation) is currently far from settled. (See the External Links section for more about this)

Applications

• Artificial Creativity
• 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 mechatronic systems using bond graphs and genetic programming (NSF).
• Automated design of industrial equipment using catalogs of exemplar lever patterns.
• Automated design of sophisticated trading systems in the financial sector.
• Calculation of Bound states and Local-density approximations.
• Chemical kinetics (gas and solid phases)
• Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs).
• Container loading optimization.
• Code-breaking, using the GA to search large solution spaces of ciphers for the one correct decryption.
• Design of water distribution systems.
• 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.
• Linguistic analysis, including Grammar Induction and other aspects of Natural Language Processing (NLP) such as word sense disambiguation.
• Marketing Mix Analysis
• Mobile communications infrastructure optimization.
• Molecular Structure Optimization (Chemistry).
• Multiple population topologies and interchange methodologies.
• Optimisation of data compression systems, for example using wavelets.
• Protein folding and protein/ligand docking.
• Plant floor layout.
• Representing rational agents in economic models such as the cobweb model.
• 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.
• Selection of optimal mathematical model to describe biological systems.
• Software engineering
• Solving the machine-component grouping problem required for cellular manufacturing systems.
• Tactical asset allocation and international equity strategies.
• Timetabling 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.
• Finding hardware bugs. ^{[20] [21]}

Artificial Creativity is a branch of Artificial Intelligence based on trying to make computers creative or on trying to understand human creativity by doing research in making computers creative. ... Automation (ancient Greek: = self dictated) or Industrial Automation is the use of computers to control industrial machinery and processes, replacing human operators. ... A cloth of woven carbon fiber filaments, a common element in composite materials Composite materials (or composites for short) are engineered materials made from two or more constituent materials with significantly different physical or chemical properties and which remain separate and distinct on a macroscopic level within the finished structure. ... Crashworthiness is the ability of a structure to protect its occupants during an impact. ... Mechatronics is the synergistic combination of mechanical engineering (mecha for mechanisms, i. ... A bond graph is a graphical description of a physical dynamic system. ... Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. ... In physics, a bound state is a composite of two or more building blocks (particles or bodies) that behaves as a single object. ... The local-density approximation, (LDA), is a density functional model in physics, which approximates the exchange and correlation (XC) energy. ... The Icosahedral Fullerene C540 C60 and C-60 redirect here. ... Cryptanalysis (from the Greek kryptós, hidden, and analýein, to loosen or to untie) is the study of methods for obtaining the meaning of encrypted information without access to the secret information which is normally required to do so. ... This article is about algorithms for encryption and decryption. ... Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with the study of topological spaces. ... Use of evolutionary algorithms (EA) to create electronics. ... This article or section should be merged with Distributed computing In computer science, a distributed system is an application that consists of components running on different computers concurrently. ... Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ... A problem domain is a domain where the parameters defining the boundaries of the domain and sufficient mappings into a set of ranges including itself are not well enough understood to provide a systematic description of the domain. ... Nesting refers to the process of efficiently manufacturing parts from flat raw material. ... Game theory is a branch of applied mathematics that is often used in the context of economics. ... For other uses, see robot (disambiguation). ... Grammatical Induction (using evolutionary algorithms) is the process of evolving a representation of the grammar of a target language through some evolutionary process. ... Natural language processing (NLP) is a subfield of artificial intelligence and computational linguistics. ... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ... Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with the study of topological spaces. ... The word Methodology is used in several ways. ... Protein before and after folding. ... Computational molecular docking, sometimes called virtual screening or ligand docking, is a research technique for predicting whether a small molecule, called a ligand, will bind to a protein. ... The Cobweb model or Cobweb theory explains why prices in certain markets are subject to periodic fluctuation. ... Software engineering (SE) is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software. ... Cellular Manufacturing is a model for workplace design, and is an integral part of lean manufacturing systems. ... Look up Allocation in Wiktionary, the free dictionary. ... A timetable is an organized list or schedule, usually set out in tabular form, providing information about a series of arranged events: in particular, the time at which it is planned these events will take place. ... A neural network is an interconnected group of neurons. ... Neuroevolution, or neuro-evolution, is the use of genetic algorithms to train artificial neural networks. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...

References