Genetic algorithm

From Wikipedia, the free encyclopedia
  (Redirected from Genetic Algorithm)
Jump to: navigation, search
The 2006 NASA ST5 spacecraft antenna. This complicated shape was found by an evolutionary computer design program to create the best radiation pattern. It is known as an Evolved antenna.

In the field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection. This heuristic (also sometimes called a metaheuristic) is routinely used to generate useful solutions to optimization and search problems.[1] Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

In computer science, engineering, computational physics, molecular chemistry, statistics and applied probability, genetic algorithms are a class of interacting and nonlinear Monte Carlo methods to sample from complex high-dimensional probability distributions and to estimate their normalizing constants. Genetic particle algorithms approximate the target probability distributions by a large cloud of random samples termed particles or individuals. During the mutation transition, the particles evolve randomly around the space independently and to each particle is associated a fitness weight function. During the selection transitions, we duplicate particles with high fitness at the expense of particles with low fitness which die. These genetic type particle samplers belong to the class of mean field particle methods.

In signal processing and Bayesian inference genetic algorithms allow to solve the nonlinear filtering problem.[2][3] These algorithms are called particle filters or sequential Monte Carlo methods. In computational physics and molecular simulation, genetic algorithms are also used to compute Feynman-Kac path integrals as the number of individuals tends to infinity.[4][5] These mutation-selection type algorithms are often called Resample or Reconfiguration Monte Carlo. They belong to the class of Quantum Monte Carlo methods and more specifically Diffusion Monte Carlo methodologies.

Genetic algorithms find application in bioinformatics, phylogenetics, computational science, signal and image processing, Bayesian inference, machine learning, risk analysis and rare event sampling, Engineering and robotics, economics, manufacturing, mathematics, mathematical finance, molecular chemistry, computational physics, pharmacokinetic, pharmacometrics, and other fields.

Methodology[edit]

Optimization problems[edit]

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.[6]

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions 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.

A typical genetic algorithm requires:

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

A standard representation of each candidate solution is as an array of bits.[6] 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, which facilitates simple crossover operations. 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; a mix of both linear chromosomes and trees is explored in gene expression programming.

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

Initialization[edit]

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing 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[edit]

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 the former process may be very time-consuming.

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 one wants to maximize the total value of objects that can be 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, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

Genetic operators[edit]

The next step is to generate a second generation population of solutions from those selected through a combination of genetic operators: crossover (also called recombination), and mutation.

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 new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", some research[7][8] suggests that more than two "parents" generate higher quality chromosomes.

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. These less fit solutions ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children.

Opinion is divided over the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization-extinction, or migration in genetic algorithms.[9]

It is worth tuning parameters such as the mutation probability, crossover 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 elitist selection is employed.

Termination[edit]

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

Monte Carlo integration[edit]

A mutation-selection sampler[edit]

Simple genetic algorithms with mutation-selection transitions can also be used as to solve complex path integration problems. Suppose we are given some Markov process X_n evolving in some solution space {\textstyle S} at every time step n\in\mathbb N.

We let {\textstyle G_n~:~x\in S\mapsto G_n(x)\in\mathbb [0,\infty]} be some bounded fitness functions on the solution space {\textstyle S}.

We consider a population of N individuals starting with {\textstyle N} independent copies {\textstyle \left(\xi^i_0\right)_{1\leq i\leq N}} of the random variable X_0 . The genetic algorithm is defined the selection-mutation transitions given by the synthetic diagram

{\displaystyle \xi_n:=\left(\xi^i_{n}\right)_{1\leq i\leq N}\in S^N\stackrel{\mbox{selection}}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!\longrightarrow} ~\widehat{\xi}_n:=\left(\widehat{\xi}^i_{n}\right)_{1\leq i\leq N}\in S^N\stackrel{\mbox{mutation}}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!\longrightarrow} ~\xi_{n+1}:=\left(\xi^i_{n+1}\right)_{1\leq i\leq N}\in S^N}

  • During the selection transition we sample N (conditionally) independent random variables {\textstyle \widehat{\xi}_n:=\left(\widehat{\xi}^i_{n}\right)_{1\leq i\leq N}} with common (conditional) distribution {\displaystyle Proba\left(\widehat{\xi}^i_n=\xi^j_n~|~\xi_n\right)=\frac{G_n(\xi^j_n)}{\sum_{1\leq k\leq N}G_n(\xi^k_n)},~\mbox{for each}~j\in\{1,\ldots,N\}}In other words, if G_n(\xi^j_n) is the fitness of the j -th individual \xi^j_n in the population \xi_n, its probability of being selected in the next generation \widehat{\xi}_n is \frac{G_n(\xi^j_n)}{\sum_{1\leq k\leq N}G_n(\xi^k_n)}. This selection transition is also called the fitness-proportionate selection[10], or the roulette-wheel selection.[11] For [0,1]-valued fitness functions G_n an alternative acceptance-rejection type selection transition can be underlined: For each 1\leq i\leq N, with a probability G_n(\xi^i_n) we accept the individual \xi^i_n ; that is, we set \widehat{\xi}^i_n=\xi^i_n. Otherwise, we sample a new indidual \widetilde{\xi}^i_n in the current population with the probability measure

{\displaystyle Proba\left(\widetilde{\xi}^i_n=\xi^j_n~|~\xi_n\right)=\frac{G_n(\xi^j_n)}{\sum_{1\leq k\leq N}G_n(\xi^k_n)},~\mbox{for each}~j\in\{1,\ldots,N\}}and we set {\textstyle \widehat{\xi}^i_n=\widetilde{\xi}^i_n.} This selection scheme can be interpreted as an acceptance-rejection sampler equipped with a recycling mechanism.[5]

  • During the mutation transition, from each selected particle \widehat{\xi}^i_n we sample independently a transition \widehat{\xi}^i_n~\longrightarrow\xi^i_{n+1} of the Markov chain X_n~\rightarrow~X_{n+1} starting at X_n=\widehat{\xi}^i_n, for i\in\{1,\ldots,N\}.

Convergence results[edit]

When the number of individuals (and the computational power) N\uparrow\infty, for any function f~:~x\in S\mapsto f(x)\in\mathbb R, we have

{\displaystyle \frac{1}{N}\sum_{1\leq i\leq N}~f\left(\xi^i_n\right)~\approx_{N\uparrow}~\frac{E\left(f(X_n)~\prod_{0\leq k< n}G_k(X_k)\right)}{E\left(\prod_{0\leq k< n}G_k(X_k)\right)}\quad\mbox{and}\quad
\frac{1}{N}\sum_{1\leq i\leq N}~f\left(\widehat{\xi}^i_n\right)~\approx_{N\uparrow}~\frac{E\left(f(X_n)~\prod_{0\leq k\leq n}G_k(X_k)\right)}{E\left(\prod_{0\leq k\leq n}G_k(X_k)\right)}}

In addition, we have the unbiased estimate{\displaystyle \prod_{0\leq k\leq n}\frac{1}{N}\sum_{1\leq i\leq N}G_k(\xi^i_k)~\approx_{N\uparrow\infty}~
E\left(\prod_{0\leq k\leq n}G_k(X_k)\right)}In statistics and probability theory the limiting expectations are called Feynman-Kac formulae.

Genealogical tree algorithm[edit]

Tracing back in time the ancestral lines of each individual \widehat{\xi}^i_n in the population after the n-th selection, we define the genealogical tree of the genetic population {\displaystyle \widehat{\xi}^i_{0,n}\longleftarrow~
\widehat{\xi}^i_{1,n}\longleftarrow~\ldots
\widehat{\xi}^i_{k-1,n}\longleftarrow
\widehat{\xi}^i_{k,n}\longleftarrow\ldots
\widehat{\xi}^i_{n-1,n}\longleftarrow\widehat{\xi}^i_{n,n}=\widehat{\xi}^i_{n}}The lower indices (.)_{k,n} represent the level k of the ancestor of \widehat{\xi}^i_n .

When the number of individuals (and the computational power) N\uparrow\infty, for any function f_n~:~(x_0,\ldots,x_n)\in S^{n+1}\mapsto f_n(x_0,\ldots,x_n)\in\mathbb R we have the Monte Carlo approximation
{\displaystyle \frac{1}{N}\sum_{1\leq i\leq N}~f_n\left(\widehat{\xi}^i_{0,n},\widehat{\xi}^i_{1,n},\ldots, \widehat{\xi}^i_{n-1,n},\widehat{\xi}^i_{n,n}\right)~\approx_{N\uparrow\infty}~\frac{E\left(f_n(X_0,\ldots,X_n)~\prod_{0\leq k\leq n}G_k(X_k)\right)}{E\left(\prod_{0\leq k\leq  n}G_k(X_k)\right)}}The mathematical foundations and the first rigorous analysis of genetic algorithms for solving Monte Carlo integration problems are due to Pierre Del Moral[2][3] in 1996. The theory on Feynman-Kac genetic type particle algorithms has been developed in 2000 and 2004 in the books.[4][5]

Illustrations[edit]

These Feynman-Kac path integration models arise a variety of scientific disciplines, including in computational physics, biology, information theory and computer sciences.[4][5][12] Their interpretations depend on the application domain. We illustrate these path integration models with some concrete examples:

  1. If we choose the indicator function G_n(x_n)=1_A(x_n) of some subset of the state space, they represent the conditional distribution of a Markov chain given it stays in a given tube; that is, we have that{\displaystyle E\left(f_n(X_0,\ldots,X_n)~|~X_0\in A,~\ldots, X_n\in A\right)
=\displaystyle\frac{E\left(f_n(X_0,\ldots,X_n)\prod_{0\leq k\leq n}G_k(X_k)\right)}{E\left(\prod_{0\leq k\leq n}G_k(X_k)\right)}
\quad\mbox{and}\quad E\left(\prod_{0\leq k\leq n}G_k(X_k)\right)=P\left(X_0\in A,~\ldots, X_n\in A\right)~} (as soon as the normalizing constant is strictly positive). In addition, we have the unbiased estimate{\displaystyle \prod_{0\leq k\leq n}\frac{1}{N}\sum_{1\leq i\leq N}1_{A}(\xi^i_k)~\approx_{N\uparrow\infty}~
P\left(X_0\in A,\ldots,X_n\in A\right)} where 1_A~x\in S\mapsto 1_A(x)\in \{0,1\} stands for the indicator function of the set A.
  2. In filtering problems the Markov chain X_n represents the signal process. This Markov chain can represent the evolution of some target (missile, plane, boat, and so on). Suppose the state X_n is partially observed by some sensor of the form Y_n=h(X_n)+V_n for some function h~:~x\in S\mapsto h(x)\in\mathbb R and some sequence of random variables with a probability density g(v). We fix the observations Y_n=y_n and we set G_n(x)=g\left(y_n-h(x)\right). In this situation, the Feynman-Kac probability measures defined above coincide with the conditional distributions of the signal given the observation sequence; that is, we have that {\displaystyle E\left(f_n(X_0,\ldots,X_n)~|~Y_0=y_0,~\ldots, Y_n=y_n\right)
=\displaystyle\frac{E\left(f_n(X_0,\ldots,X_n)\prod_{0\leq k\leq n}G_k(X_k)\right)}{E\left(\prod_{0\leq k\leq n}G_k(X_k)\right)}} In addition, we have the unbiased estimate {\displaystyle \prod_{0\leq k\leq n}\frac{1}{N}\sum_{1\leq i\leq N}G_k(\xi^i_k)~\approx_{N\uparrow\infty}~
p(y_0,\ldots,y_n)} where p(y_0,\ldots,y_n) stands for the probability density of the random variable (Y_0,\ldots,Y_n) evaluated at (y_0,\ldots,y_n). In signal processing and Bayesian inference, the mutation-selection genetic algorithm is also called particle filter of Sequential Monte Carlo algorithm.
  3. Consider a sequence of probability measures \pi_{\beta} on a finite solution space S indexed by some inverse temperature parameter \beta>0 and defined by {\displaystyle \pi_{\beta}(x)=\frac{e^{-\beta V(x)}}{\sum_{y\in S}e^{-\beta V(y)}}\quad\mbox{for some function}~V~:~x\in S\mapsto V(x)\in [0,\infty[}These probability measures concentrate to the set of global minima of the function V(.). More precisely, we have{\displaystyle V_{\star}:=\inf_{x\in S}V(x)\quad\mbox{and}\quad\mathcal V:=\{x\in S~:~V(x)=V_{\star}\}\Rightarrow~\forall x\in\mathcal V\quad \pi_{\beta}(x)=\frac{
e^{-\beta \left(V(x)-V_{\star}\right)}
}{\sum_{y\in S}
e^{-\beta \left(V(y)-V_{\star}\right)}}=
\frac{1}{\mbox{Card}(\mathcal V)+\sum_{y\in S-\mathcal V}
e^{-\beta \left(V(y)-V_{\star}\right)}}\approx_{\beta\uparrow\infty}~\frac{1}{\mbox{Card}(\mathcal V)}}and for x\not\in\mathcal V we have \pi_{\beta(x)}\approx_{\beta\uparrow\infty}0. This implies that {\displaystyle \pi_{\beta}(x)~\approx_{\beta\uparrow\infty}~\frac{1}{\mbox{Card}(\mathcal V)}~1_{\mathcal V}(x)} In other words, sampling a random variable with probability distribution \pi_{\beta}(x) is almost equivalent to that of sampling uniformly one of the global minima of the function V(.). Let \beta_{n}\geq \beta_{n-1} be a increasing sequence of parameters with \beta_0=0. Consider a Markov chain X_n starting with the uniform distribution \pi_{0}(x)=1/\mbox{Card}(S) on S and such that \pi_{\beta_n} is an invariant probability measure of the transition X_{n-1}\rightarrow X_{n} at time n; that is, for any n\geq 1 we have that{\displaystyle \pi_{\beta_{n}}(x)=\sum_{y\in S}~Proba(X_n=x~|~X_{n-1}=y)~\pi_{\beta_n}(y)}These Markov transitions can be designed using Markov Chain Monte Carlo (MCMC) methods such as the Metropolis-Hasting algorithm, or the Gibbs sampler. We consider the fitness function {\displaystyle G_n(x)=\exp{\left[-(\beta_{n+1}-\beta_n)V(x)\right]}}In this situation, for any function f~:~x\in S\mapsto f(x)\in\mathbb R, we have{\displaystyle \displaystyle\frac{E\left(f(X_n)\prod_{0\leq k< n}G_k(X_k)\right)}{E\left(\prod_{0\leq k<n}G_k(X_k)\right)}=\sum_{x\in S}~f(x)~\pi_{\beta_n}(x)\quad\mbox{and}\quad
E\left(\prod_{0\leq k<n}G_k(X_k)\right)=\frac{1}{\mbox{Card}(S)}~\sum_{x\in S}~e^{-\beta_n V(x)}}In the above displayed formulae \mbox{Card}(S) stands for the cardinality of the set {\textstyle S}. The corresponding genetic algorithm is defined in terms of MCMC mutations, the selection transitions consists of selecting the particles which are better adapted to the change of temperature. At every time step, we have the particle estimates{\displaystyle \frac{1}{N}\sum_{1\leq i\leq N}~f\left(\xi^i_n\right)~\approx_{N\uparrow\infty}~\sum_{x\in S}~f(x)~\pi_{\beta_n}(x)\quad\mbox{and the unbiased approximation}\quad
\prod_{0\leq k<n}\frac{1}{N}\sum_{1\leq i\leq N}\exp{\left[-(\beta_{k+1}-\beta_k)V(\xi^i_k)\right]}~\approx_{N\uparrow\infty}~\frac{1}{\mbox{Card}(S)}\sum_{x\in S}~e^{-\beta_nV(x)}}In particular, this implies that{\displaystyle \lim_{n\uparrow\infty}\beta_n=\infty~\Rightarrow~\lim_{n\uparrow\infty}\lim_{N\uparrow\infty}\frac{1}{N}\sum_{1\leq i\leq N}~f\left(\xi^i_n\right)=\frac{1}{\mbox{Card}(\mathcal V)}\sum_{x\in \mathcal V}~f(x)~}Further details on these genetic type interacting MCMC methods (a.k.a. Sequential Monte Carlo - SMC) can be found in.[12][13][14]

The building block hypothesis[edit]

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular it is difficult to understand why these algorithms frequently succeed at generating solutions of high fitness when applied to practical problems. The building block hypothesis (BBH) consists of:

  1. A description of a heuristic that performs adaptation by identifying and 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 heuristic.

Goldberg describes the heuristic 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.
"Because highly fit schemata of low defining length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood, so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks."[15]

Limitations[edit]

There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

  • Repeated fitness function evaluation for complex problems is often the most prohibitive and limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex high-dimensional, multimodal problems often requires very expensive fitness function evaluations. In real world problems such as structural optimization problems, a single function evaluation may require several hours to several days of complete simulation. Typical optimization methods can not deal with such types of problem. In this case, it may be necessary to forgo an exact evaluation and use an approximated fitness that is computationally efficient. It is apparent that amalgamation of approximate models may be one of the most promising approaches to convincingly use GA to solve complex real life problems.
  • Genetic algorithms do not scale well with complexity. That is, where the number of elements which are exposed to mutation is large there is often an exponential increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or plane. In order to make such problems tractable to evolutionary search, they must be broken down into the simplest representation possible. Hence we typically see evolutionary algorithms encoding designs for fan blades instead of engines, building shapes instead of detailed construction plans, airfoils instead of whole aircraft designs. The second problem of complexity is the issue of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.
  • The "better" solution is only in comparison to other solutions. As a result, the stop criterion is not clear in every problem.
  • 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,[16] although the No Free Lunch theorem[17] 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. Another possible technique would be to simply replace part of the population with randomly generated individuals, when most of the population is too similar to each other. 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). 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 a single right/wrong measure (like decision problems), 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. However, if the situation allows the success/failure trial to be repeated giving (possibly) different results, then the ratio of successes to failures provides a suitable fitness measure.

Variants[edit]

Chromosome representation[edit]

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 John Henry 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.

When bit-string 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.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation.[18][19]

An expansion of the Genetic Algorithm accessible problem domain can be obtained through more complex encoding of the solution pools by concatenating several types of heterogenously encoded genes into one chromosome.[20] This particular approach allows for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

Elitism[edit]

A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.[21]

Parallel implementations[edit]

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.

Adaptive GAs[edit]

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (pm) greatly determine the degree of solution accuracy and the convergence speed that genetic algorithms can obtain. Instead of using fixed values of pc and pm, AGAs utilize the population information in each generation and adaptively adjust the pc and pm in order to maintain the population diversity as well as to sustain the convergence capacity. In AGA (adaptive genetic algorithm),[22] the adjustment of pc and pm depends on the fitness values of the solutions. In CAGA (clustering-based adaptive genetic algorithm),[23] through the use of clustering analysis to judge the optimization states of the population, the adjustment of pc and pm depends on these optimization states. 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.

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 [24] or example in travelling salesman problem, in particular the use of an edge recombination operator.)

A variation, where the population as a whole is evolved rather than its individual members, is known as gene pool recombination.

A number of variations have been developed to attempt to improve performance of GAs on problems with a high degree of fitness epistasis, i.e. where the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the Building Block Hypothesis in adaptively reducing disruptive recombination. Prominent examples of this approach include the mGA,[25] GEMGA[26] and LLGA.[27]

Problem domains[edit]

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[citation needed]. GAs have also been applied to engineering.[28] 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 mixing, i.e., mutation in combination with crossover, is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. Observe that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Examples of problems solved by genetic algorithms include: mirrors designed to funnel sunlight to a solar collector,[29] antennae designed to pick up radio signals in space,[30] and walking methods for computer figures.[31]

In his Algorithm Design Manual, Skiena advises against genetic algorithms for any task:

[I]t is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [...] [T]he analogy with evolution—where significant progress require [sic] millions of years—can be quite appropriate.

[...]

I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.
—Steven Skiena[32]:267

History[edit]

In 1950, Alan Turing proposed a "learning machine" which would parallel the principles of evolution.[33] Computer simulation 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.[34][35] His 1954 publication was not widely noticed. Starting in 1957,[36] 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)[37] and Crosby (1973).[38] Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans-Joachim 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.[39] Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998).[40]

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game,[41] 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 – Rechenberg's group was able to solve complex engineering problems through evolution strategies.[42][43][44][45] 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.

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 first commercial GA product for desktop computers. The New York Times technology writer John Markoff wrote[46] about Evolver in 1990, and it remained the only interactive commercial genetic algorithm until 1995.[47] Evolver was sold to Palisade in 1997, translated into several languages, and is currently in its 6th version.[48]

Quantum Monte Carlo, and more specifically Diffusion Monte Carlo methods can also be interpreted as genetic type particle approximations of Feynman-Kac path integrals.[4][49][50][51][52][53][54] The origins of Quantum Monte Carlo methods are often attributed to Enrico Fermi and Robert Richtmyer who developed in 1948 a mean field particle interpretation of neutron-chain reactions,[55] but the first heuristic-like and genetic type particle algorithm (a.k.a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984.[51] We also quote an earlier seminal works of Theodore E. Harris and Herman Kahn in particle physics, published in 1951, using mean field but heuristic-like genetic methods for estimating particle transmission energies.[56] In molecular chemistry, the use of genetic heuristic-like particle methodologies on path spaces (a.k.a. pruning and enrichment strategies) can be traced back to 1955 with the seminal work of Marshall. N. Rosenbluth and Arianna. W. Rosenbluth.[57]

The use of genetic particle algorithms in advanced signal processing and Bayesian inference is more recent. It was in 1993, that Gordon et al., published in their seminal work[58] the first application of genetic type algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state-space or the noise of the system. We also quote another pioneering article in this field of Genshiro Kitagawa on a related "Monte Carlo filter",[59] and the ones by Pierre Del Moral[2] and Himilcon Carvalho, Pierre Del Moral, André Monin and Gérard Salut[60] on genetic type particle filters published in the mid-1990s. Genetic mutation-selection type particle filters were also developed in signal processing in the early 1989-1992 by P. Del Moral, J.C. Noyer, G. Rigal, and G. Salut in the LAAS-CNRS in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the LAAS-CNRS (the Laboratory for Analysis and Architecture of Systems) on RADAR/SONAR and GPS signal processing problems.[33][34][35][36][37][38]

From 1950 to 1996, all the publications on genetic algorithms, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like genetic algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and on genealogical and ancestral tree based algorithms. The mathematical foundations and the first rigorous analysis of these genetic particle algorithms are due to Pierre Del Moral[2][3] in 1996. The article[2] also contains a proof of the unbiased properties of a particle approximations of likelihood functions and unnormalized conditional probability measures. The unbiased particle estimator of the likelihood functions presented in this article is currently used today in Bayesian statistical inference. The theory on Feynman-Kac formulae and their genetic type particle interpretations has been developed in 2000 and 2004 in the books.[4][5] These abstract probabilistic models encapsulate genetic type algorithms, particle and bootstrap filters, interacting Kalman filters (a.k.a. Rao–Blackwellized particle filter [61]), importance sampling and resampling style particle filter techniques, including genealogical tree based and particle backward methodologies for solving filtering and smoothing problems. Other classes of genetic type methodologies includes genealogical tree based models,[5][12][62] backward Markov particle models,[12][63] adaptive genetic algorithms,[64] island type methodologies,[65][66] and the more recent particle Markov chain Monte Carlo methodologies.[67][68]

Related techniques[edit]

Parent fields[edit]

Genetic algorithms are a sub-field of:

Related fields[edit]

Particle filters[edit]

Particle filters or Sequential Monte Carlo methods (SMC) use a simple genetic algorithm with mutation-selection transitions to approximate the prediction-updating transitions of the nonlinear filtering equation. The number of individuals (a.k.a. particle or samples) represents the precision of the numerical algorithm. When the number of particles tends to infinity, the occupation measures of the population converge to the conditional distribution of the internal state of some dynamical system given some noisy and partial observations. In addition, the occupation measure of the ancestral lines of the genetic genealogical tree converge to the conditional distribution of the random trajectories of the system w.r.t. the sequence of observations. In this context, genetic algorithms provide a natural way to learn sequentially a series of observations to estimate the random states of some unknown dynamical process.

Evolutionary algorithms[edit]

Evolutionary algorithms is a sub-field of evolutionary computing.

  • Evolution strategies (ES, see Rechenberg, 1994) evolve individuals by means of mutation and intermediate or 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. De-randomization of self-adaptation has led to the contemporary Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
  • 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.
  • Gene expression programming (GEP) also uses populations of computer programs. These complex computer programs are encoded in simpler linear chromosomes of fixed length, which are afterwards expressed as expression trees. Expression trees or computer programs evolve because the chromosomes undergo mutation and recombination in a manner similar to the canonical GA. But thanks to the special organization of GEP chromosomes, these genetic modifications always result in valid computer programs.[69]
  • 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.[70] 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 with respect to 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.
  • 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.

Swarm intelligence[edit]

Swarm intelligence is a sub-field of evolutionary computing.

  • 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]
  • Particle swarm optimization (PSO) is a computational method for multi-parameter optimization which also uses population-based approach. A population (swarm) of candidate solutions (particles) moves in the search space, and the movement of the particles is influenced both by their own best known position and swarm's global best known position. Like genetic algorithms, the PSO method depends on information sharing among population members. In some problems the PSO is often more computationally efficient than the GAs, especially in unconstrained problems with continuous variables.[71]
  • Intelligent Water Drops or the IWD algorithm [72] is a nature-inspired optimization algorithm inspired from natural water drops which change their environment to find the near optimal or optimal path to their destination. The memory is the river's bed and what is modified by the water drops is the amount of soil on the river's bed.

Other evolutionary computing algorithms[edit]

Evolutionary computation is a sub-field of the metaheuristic methods.

  • Harmony search (HS) is an algorithm mimicking the behaviour of musicians in the process of improvisation.
  • Memetic algorithm (MA), often called hybrid genetic algorithm among others, is a population-based method in which solutions are also subject to local improvement phases. 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.
  • 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. It is also believed BAs could be successfully applied to complex positioning problems (antennas for cell phones, urban planning, and so on) or data mining.[73]
  • Cultural algorithm (CA) consists of the population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space.
  • 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.[75] 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.

Other metaheuristic methods[edit]

Metaheuristic methods broadly fall within stochastic optimisation methods.

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

Other stochastic optimisation methods[edit]

  • 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.
  • Reactive search optimization (RSO) advocates the integration of sub-symbolic machine learning techniques into search heuristics for solving complex optimization problems. The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. Methodologies of interest for Reactive Search include machine learning and statistics, in particular reinforcement learning, active or query learning, neural networks, and meta-heuristics.

See also[edit]

References[edit]

  1. ^ Mitchell 1996, p. 2.
  2. ^ a b c d e Del Moral, Pierre (1996). "Non Linear Filtering: Interacting Particle Solution." (PDF). Markov Processes and Related Fields 2 (4): 555–580. 
  3. ^ a b c Del Moral, Pierre (1998). "Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems". Annals of Applied Probability (Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996) ed.) 8 (2): 438–495. doi:10.1214/aoap/1028903535. 
  4. ^ a b c d e Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering. (PDF). Lecture Notes in Mathematics 1729. pp. 1–145. doi:10.1007/bfb0103798. 
  5. ^ a b c d e f Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. http://www.springer.com/gp/book/9780387202686: Springer. Series: Probability and Applications. p. 556. ISBN 978-0-387-20268-6. 
  6. ^ a b Whitley 1994, p. 66.
  7. ^ Eiben, A. E. et al (1994). "Genetic algorithms with multi-parent recombination". PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: 78–87. ISBN 3-540-58484-6.
  8. ^ Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. ISBN 978-3-540-28848-0.
  9. ^ Akbari, Ziarati (2010). "A multilevel evolutionary algorithm for optimizing numerical functions" IJIEC 2 (2011): 419–430 [1]
  10. ^ Bäck, Thomas (1996). Evolutionary Algorithms in Theory and Practice. Oxford Univ. Press. 
  11. ^ Lipowski, Adam; Lipowska, Dorota (2012). "Roulette-wheel selection via stochastic acceptance". Physica A: Statistical Mechanics and its Applications 391 (6): 2193–2196. doi:10.1016/j.physa.2011.12.004. ISSN 0378-4371. 
  12. ^ a b c d Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. p. 626. Monographs on Statistics & Applied Probability 
  13. ^ "Sequential Monte Carlo samplers - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library". onlinelibrary.wiley.com. Retrieved 2015-06-08. 
  14. ^ Del Moral, Pierre; Hu, Peng; Wu, Liming (2012). On the Concentration Properties of Interacting Particle Processes. Hanover, MA, USA: Now Publishers Inc. ISBN 1601985126. 
  15. ^ Goldberg 1989, p. 41.
  16. ^ Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad Hadi (19 November 2012). "An efficient algorithm for function optimization: modified stem cells algorithm". Central European Journal of Engineering 3 (1): 36–50. doi:10.2478/s13531-012-0047-8. 
  17. ^ Wolpert, D.H., Macready, W.G., 1995. No Free Lunch Theorems for Optimisation. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  18. ^ Goldberg, David E. (1991). "The theory of virtual alphabets". Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496: 13–22. doi:10.1007/BFb0029726. Retrieved 2 July 2013. 
  19. ^ Janikow, C. Z.; Michalewicz, Z. (1991). "An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms" (PDF). Proceedings of the Fourth International Conference on Genetic Algorithms: 31–36. Retrieved 2 July 2013. 
  20. ^ Patrascu, M.; Stancu, A.F.; Pop, F. (2014). "HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation". Soft Computing 18: 2565–2576. 
  21. ^ Baluja, Shumeet; Caruana, Rich (1995). Removing the genetics from the standard genetic algorithm (PDF). ICML. 
  22. ^ Srinivas. M and Patnaik. L, "Adaptive probabilities of crossover and mutation in genetic algorithms," IEEE Transactions on System, Man and Cybernetics, vol.24, no.4, pp.656–667, 1994.
  23. ^ ZHANG. J, Chung. H and Lo. W. L, “Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms”, IEEE Transactions on Evolutionary Computation vol.11, no.3, pp. 326–335, 2007.
  24. ^ Evolution-in-a-nutshell
  25. ^ D.E. Goldberg, B. Korb, and K. Deb. "Messy genetic algorithms: Motivation, analysis, and first results". Complex Systems, 5(3):493–530, October 1989.
  26. ^ Gene expression: The missing link in evolutionary computation
  27. ^ G. Harik. Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, Dept. Computer Science, University of Michigan, Ann Arbour, 1997
  28. ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. Energies. 2013; 6(3):1439-1455.
  29. ^ Gross, Bill. "A solar energy system that tracks the sun". TED. Retrieved 20 November 2013. 
  30. ^ Hornby, G. S.; Linden, D. S.; Lohn, J. D., Automated Antenna Design with Evolutionary Algorithms (PDF) 
  31. ^ http://goatstream.com/research/papers/SA2013/index.html
  32. ^ Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. ISBN 1-849-96720-2. 
  33. ^ a b Turing, Alan M. "Computing machinery and intelligence". Mind LIX (238): 433–460. doi:10.1093/mind/LIX.236.433. 
  34. ^ a b Barricelli, Nils Aall (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68. 
  35. ^ a b Barricelli, Nils Aall (1957). "Symbiogenetic evolution processes realized by artificial methods". Methodos: 143–182. 
  36. ^ a b Fraser, Alex (1957). "Simulation of genetic systems by automatic digital computers. I. Introduction". Aust. J. Biol. Sci. 10: 484–491. 
  37. ^ a b Fraser, Alex; Burnell, Donald (1970). Computer Models in Genetics. New York: McGraw-Hill. ISBN 0-07-021904-4. 
  38. ^ a b Crosby, Jack L. (1973). Computer Simulation in Genetics. London: John Wiley & Sons. ISBN 0-471-18880-8. 
  39. ^ 02.27.96 - UC Berkeley's Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69
  40. ^ Fogel, David B. (editor) (1998). Evolutionary Computation: The Fossil Record. New York: IEEE Press. ISBN 0-7803-3481-7. 
  41. ^ Barricelli, Nils Aall (1963). "Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life". Acta Biotheoretica (16): 99–126. 
  42. ^ Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 3-7728-0373-3. 
  43. ^ Schwefel, Hans-Paul (1974). Numerische Optimierung von Computer-Modellen (PhD thesis). 
  44. ^ Schwefel, Hans-Paul (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Basel; Stuttgart: Birkhäuser. ISBN 3-7643-0876-1. 
  45. ^ Schwefel, Hans-Paul (1981). Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie. Chichester ; New York: Wiley. ISBN 0-471-09988-0. 
  46. ^ Markoff, John (29 August 1990). "What's the Best Answer? It's Survival of the Fittest". New York Times. Retrieved 9 August 2009.  Check date values in: |year= / |date= mismatch (help)
  47. ^ Ruggiero, Murray A.. (2009-08-01) Fifteen years and counting. Futuresmag.com. Retrieved on 2013-08-07.
  48. ^ Evolver: Sophisticated Optimization for Spreadsheets. Palisade. Retrieved on 2013-08-07.
  49. ^ Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. p. 575. Series: Probability and Applications 
  50. ^ Del Moral, Pierre; Miclo, Laurent (2000). "A Moran particle system approximation of Feynman-Kac formulae.". Stochastic Processes and their Applications 86 (2): 193–216. doi:10.1016/S0304-4149(99)00094-0. 
  51. ^ a b Hetherington, Jack, H. (1984). "Observations on the statistical iteration of matrices". Phys. Rev. A. 30 (2713): 2713–2719. doi:10.1103/PhysRevA.30.2713. 
  52. ^ Del Moral, Pierre (2003). "Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups" (PDF). ESAIM Probability & Statistics 7: 171–208. doi:10.1051/ps:2003001. 
  53. ^ Assaraf, Roland; Caffarel, Michel; Khelif, Anatole (2000). "Diffusion Monte Carlo Methods with a fixed number of walkers" (PDF). Phys. Rev. E 61: 4566–4575. doi:10.1103/physreve.61.4566. 
  54. ^ Caffarel, Michel; Ceperley, David; Kalos, Malvin (1993). "Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms". Phys. Rev. Lett. 71. doi:10.1103/physrevlett.71.2159. 
  55. ^ Fermi, Enrique; Richtmyer, Robert, D. (1948). "Note on census-taking in Monte Carlo calculations" (PDF). LAM 805 (A). Declassified report Los Alamos Archive 
  56. ^ Herman, Kahn; Harris, Theodore, E. (1951). "Estimation of particle transmission by random sampling" (PDF). Natl. Bur. Stand. Appl. Math. Ser. 12: 27–30. 
  57. ^ Rosenbluth, Marshall, N.; Rosenbluth, Arianna, W. (1955). "Monte-Carlo calculations of the average extension of macromolecular chains". J. Chem. Phys 23: 356–359. 
  58. ^ Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. (April 1993). "Novel approach to nonlinear/non-Gaussian Bayesian state estimation". Radar and Signal Processing, IEE Proceedings F 140 (2): 107–113. ISSN 0956-375X. 
  59. ^ Kitagawa, G. (1996). "Monte carlo filter and smoother for non-Gaussian nonlinear state space models". Journal of Computational and Graphical Statistics 5 (1): 1–25. doi:10.2307/1390750. JSTOR 1390750. 
  60. ^ Carvalho, Himilcon; Del Moral, Pierre; Monin, André; Salut, Gérard (July 1997). "Optimal Non-linear Filtering in GPS/INS Integration." (PDF). IEEE-Trans. on Aerospace and electronic systems 33 (3). 
  61. ^ Doucet, A.; De Freitas, N. and Murphy, K. and Russell, S. (2000). Rao–Blackwellised particle filtering for dynamic Bayesian networks. Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence. pp. 176–183. CiteSeerX: 10.1.1.137.5199. 
  62. ^ Del Moral, Pierre; Miclo, Laurent (2001). "Genealogies and Increasing Propagations of Chaos for Feynman-Kac and Genetic Models". Annals of Applied Probability 11 (4): 1166–1198. 
  63. ^ Del Moral, Pierre; Doucet, Arnaud; Singh, Sumeetpal, S. (2010). "A Backward Particle Interpretation of Feynman-Kac Formulae" (PDF). M2AN 44 (5): 947–976. doi:10.1051/m2an/2010048. 
  64. ^ Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2012). "On Adaptive Resampling Procedures for Sequential Monte Carlo Methods" (PDF). Bernoulli 18 (1): 252–278. doi:10.3150/10-bej335. 
  65. ^ Vergé, Christelle; Dubarry, Cyrille; Del Moral, Pierre; Moulines, Eric (2013). "On parallel implementation of Sequential Monte Carlo methods: the island particle model". Statistics and Computing 25: 243–260. doi:10.1007/s11222-013-9429-x. 
  66. ^ Chopin, Nicolas; Jacob, Pierre, E.; Papaspiliopoulos, Omiros. "SMC^2: an efficient algorithm for sequential analysis of state-space models" (PDF). arXiv:1101.1528v3. 
  67. ^ Andrieu, Christophe; Doucet, Arnaud; Holenstein, Roman (2010). "Particle Markov chain Monte Carlo methods". Journal Royal Statistical Society B 72 (3): 269–342. doi:10.1111/j.1467-9868.2009.00736.x. 
  68. ^ Del Moral, Pierre; Patras, Frédéric; Kohn, Robert (2014). "On Feynman-Kac and particle Markov chain Monte Carlo models" (PDF). arXiv preprint arXiv:1404.5733. 
  69. ^ Ferreira, C. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems" (PDF). Complex Systems, Vol. 13, issue 2: 87-129. 
  70. ^ Falkenauer, Emanuel (1997). Genetic Algorithms and Grouping Problems. Chichester, England: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4. 
  71. ^ Rania Hassan, Babak Cohanim, Olivier de Weck, Gerhard Vente r (2005) A comparison of particle swarm optimization and the genetic algorithm
  72. ^ Hamed Shah-Hosseini, The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm, International Journal of Bio-Inspired Computation (IJBIC), vol. 1, no. ½, 2009, [2][dead link]
  73. ^ Baudry, Benoit; Franck Fleurey; Jean-Marc Jézéquel; Yves Le Traon (March–April 2005). "Automatic Test Case Optimization: A Bacteriologic Algorithm" (PDF). IEEE Software (IEEE Computer Society) 22 (2): 76–82. doi:10.1109/MS.2005.30. Retrieved 9 August 2009. 
  74. ^ Civicioglu, P. (2012). "Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm". Computers &Geosciences 46: 229–247. doi:10.1016/j.cageo.2011.12.011. 
  75. ^ Kjellström, G. (December 1991). "On the Efficiency of Gaussian Adaptation". Journal of Optimization Theory and Applications 71 (3): 589–597. doi:10.1007/BF00941405. 

Bibliography[edit]

  • Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming – An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107. 
  • Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". Journal of Pharmacokinetics and Pharmacodynamics (Netherlands: Springer): 196–221. 
  • Cha, Sung-Hyuk; Tappert, Charles C. (2009). "A Genetic Algorithm for Constructing Compact Binary Decision Trees". Journal of Pattern Recognition Research 4 (1): 1–13. doi:10.13176/11.44. 
  • Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences 10: 484–491. 
  • Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673. 
  • Goldberg, David (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983. 
  • Fogel, David. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (3rd ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517. 
  • Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110. 
  • Koza, John (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press. ISBN 978-0262111706. 
  • Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. ISBN 978-3540606765. 
  • Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. ISBN 9780585030944. 
  • Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. 
  • Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.
  • Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Linear analysis of genetic algorithms, Theoretical Computer Science 208: 111–148
  • Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science 259: 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: 181–231
  • Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
  • Vose, Michael (1999). The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA: MIT Press. ISBN 978-0262220583. 
  • Whitley, Darrell (1994). "A genetic algorithm tutorial". Statistics and Computing 4 (2): 65–85. doi:10.1007/BF00175354. 
  • Hingston, Philip; Barone, Luigi; Michalewicz, Zbigniew (2008). Design by Evolution: Advances in Evolutionary Design. Springer. ISBN 978-3540741091. 
  • Eiben, Agoston; Smith, James (2003). Introduction to Evolutionary Computing. Springer. ISBN 978-3540401841. 

External links[edit]

Resources[edit]

Tutorials[edit]