genetic algorithms


Also found in: Dictionary, Medical, Financial.

genetic algorithms

Genetic algorithms

Search procedures based on the mechanics of natural selection and genetics. Such procedures are known also as evolution strategies, evolutionary programming, genetic programming, and evolutionary computation. Genetic algorithms are increasingly solving difficult search, optimization, and machine-learning problems that have previously resisted automated solution. They can solve hard problems quickly and reliably, are easy to interface to existing simulations and models, are extensible, and are easy to hybridize.

Motivation

Just as natural selection and genetics have filled a variety of niches by creating genotypes (sets of chromosomes) that result in well-adapted phenotypes (or organisms), so too can genetic algorithms solve many artificial problems by creating strings (artificial chromosomes) that result in better solutions. Users ultimately turn to genetic algorithms for robustness, that is, for algorithms that are broadly applicable, relatively quick, and sufficiently reliable. This emphasis on robustness contrasts starkly with the philosophy of operations research, where new algorithms must be tailored to specific problems. The need to invent a new method for each new problem class is daunting, and users look for methods that can solve complex problems without this requirement. See Operations research

Mechanics

For concrete exposition, the discussion is limited to a simple genetic algorithm that processes a finite population of fixed-length, binary strings. A simple genetic algorithm consists of three operators: selection, crossover, and mutation.

Selection is the survival of the fittest within the genetic algorithm. The key notion is to give preference to better individuals. Of course, for selection to function, there must be some way of determining what is good. This evaluation can come from a formal objective function, or it can come from the subjective judgment of a human observer or critic.

If genetic algorithms were to do nothing but selection, the trajectory of populations could contain nothing but changing proportions of the strings in the original population. To do something more sensible, the algorithm needs to explore different structures. A primary exploration operator used in many genetic algorithms is crossover. Simple, one-point crossover proceeds in three steps: (1) two individuals are chosen from the population by using the selection operator, and these two structures are considered to be mated; (2) a cross site along the string length is chosen uniformly at random; and (3) position values are exchanged between the two strings following the cross site.

In a binary-coded genetic algorithm, mutation is the occasional (low probability) alteration of a bit position, and with other codes a variety of diversity-generating operators may be used. When used together with selection and crossover, mutation acts both as an insurance policy against losing needed diversity and as a hill-climbing algorithm.

References in periodicals archive ?
The genetic algorithms approach is usually consisting of the following steps:
Genetic algorithms for the twostage bicriteria flowshop problem.
Performance results show the adaptive mechanism in Genetic Algorithm helps increase capability to converge sooner than the ordinary Genetic Algorithm.
F Danijela Peter [2], compared the tool paths created by CAM software and by Genetic Algorithm.
For the optimization of complex systems, many scholars have used different approaches, for example, the adaptive genetic algorithm [17-18], improved genetic algorithm [19-21], and multi-objective genetic algorithm [22-23].
Siderius, "Predicting underwater ocean noise with genetic algorithms," Physics Letters A, vol.
Genetic algorithms applied to multi-class prediction for the analysis of gene expression data.
Furthermore, statistical tests on the experimental results were applied thus providing ground for tuning the parameters of genetic algorithms and for comparison of various algorithms' performance on the dataset considered.
Genetic algorithms found their use in design of racing and also regular vehicles.
Genetic algorithms consider that a candidate solution of a problem exists in a population of chromosomes (Hegazy 1999; Leu, Hung 2002).
This article uses concepts from ensemble learning and distributed data mining to create a modified and improved version of the stacking learning technique by using a genetic algorithm (GA) for creating the meta-classifier.

Full browser ?