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 ?
From the viewpoint of operation research, the problem of locating base stations is considered a constrained multiobjective optimization problem and can be solved using one of the famous evolutionary algorithms such as the genetic algorithms.
Genetic algorithms are stochastic optimization techniques invented by John Holland [Holland, 1975].
2012) were discussed the advanced novel heuristic search with genetic algorithm, which is used to identify an optimum feature subset and to increase the classification accuracy and scalability in credit risk assessment.
2011) artificial neural network is combined with genetic algorithm.
A comparison of genetic algorithms for the static job shop scheduling problem," in Parallel Problem Solving from Nature PPSN VI, pp: 303-312.
Genetic algorithms consider that a candidate solution of a problem exists in a population of chromosomes (Hegazy 1999; Leu, Hung 2002).
In the next section we discuss using a genetic algorithm to learn the weight distribution vector.
In this paper, we will redefine the fitness of genetic algorithm and population fitness.
We recommend that a genetic algorithm solver (see further discussion) be used because the user can select the number of alternatives to be considered, and genetic algorithms provide a good estimate of the optimal solution set.
Genetic Algorithms (GAs) is one of the Evolutionary Computation (EC) approaches.
0 is the introduction of the new comprehensive empirical forecast model which optimizes forecast signals through the usage of a genetic algorithm.

Full browser ?