genetic algorithms


A Genetic Algorithm (GA) is an Evolutionary Algorithm (EA). GAs are general-purpose search algorithms that use principles inspired by natural population genetics to evolve solutions to problems. GAs are theoretically and empirically proven to provide a robust search in complex spaces, thereby offering a valid approach to problems requiring efficient and effective searches.

An EA (GA) processes a population of genetic variants from one generation to the next. A particular chromosome encodes a candidate solution of the optimisation problem. The fitness of an inidividual with respect to the optimisation task is described by a scalar objective function. According to Darwin’s principle, highly fit individuals are more likely to be selected to reproduce offspring to the next generation. Genetic operators such as recombination and mutation are applied to the parents in order to generate new candidate solutions. As a result of this evolutionary cycle of selection, recombination and mutation, more and more suitable solutions to the optimisation problem emerge within the population.

According to the evolutionary cycle, the major components and structure of a generic EA (GA) are:

    1. initialise P(t=0)
    2. evaluate P(t)
    3. select parents from P(t)
    4. recombine parents into offspring
    5. mutate offspring
    6. replace P(t) with offspring
    7. t = t + 1
    8. check if termination criteria fulfilled (Yes/No)
    9. If not 8 then go to 2
    10. finish

During generation t, the EA (GA) mantains a population P(t) of chromosomes. The population at time t=0 is initialised at random. Each individual is evaluated by means of the scalar objective function giving some measure of fitness (depending on the chromosome phenotype, this operation can be very costly) Then a set of parents is selected from the current population in a way that more fit individuals obtain a higher chance of reproduction. Recombination then merges two chromosomes of two (or more!) parents to form an offspring. In this way, recombination fosters the exchange of genetic information among individual members of the population. The offspings are subject to mutations (the mutation rate usually is very low) which randomly modify a gene in order to create new variants (keeping gene variance and avoiding premature convergence is very important to success!) The current population is replaced by the newly generated offspring, which forms the new generation (sometimes the best individual of the former generation is kept) The evolutionary cycle of evaluation, selection, recombination, mutation and replacement continues until a termination criterion is fulfilled. The stopping condition can be either defined by the maximum number of generations (time/space computation limit) or in terms of a desired fitness to be achieved by the best individual un the population.

So a GA operates on a population of randomly generated solutions, chromosomes often represented by binary strings with a suitable coding scheme (although modern extensions to GA allow more complex representations suited to the problem) The population advances toward better solutions by applying genetic operators, such as crossover and mutation (theoretically supported in the binary chromosome case by Schema Theory and Building Block Hypothesis) In each generation, favourable solutions generate offspring that replace the inferior individuals. Crossover hybridises the genes of two (or more) parent chromosomes in order to exploit the search space and constitutes the main genetic operator in GAs. The purpose of mutation is to maintain the diversity of the gene pool. An evaluation of fitness function plays the role of the enironment to distinghish between good and bad solutions.

Solving a particular optimisation task using a GA, requires the human designer to address the five following issues:

  1. A genetic representation of candidate solutions (binary?, real?, more complex?),
  2. a way to create an initial population of solutions (random?, deterministic?),
  3. an evaluation function which describes the quality of each individual (sometimes not so obvious),
  4. genetic operators that generate new variants during reproduction (depend on representation, rate of application must be stablished), and
  5. values for the parameters of the GA, such as population size, number of generations and probabilities of applying genetic operators

The simple genetic algorithm uses binary representation and one-point crossover (the chromosome of the parents split in one point and each slice is exchanged with the partner) This configuration allow simple GAs to be applied with more or less good results in a broad range of problems, but suffering from a number of risks/drawbacks such as premature convergence, biased search and inadequate mapping from genotype to phenotype space (producing offspring which are not valid solutions) To avoid those risks the designer of the solver can use extensions to the genetic representations, selection schemes and genetic operators, thus improving the behaviour of the GAs.

Examples of extensions:

  1. Gray-coded binary strings to avoid Hamming cliffs and focus the search on solutions that are located close to the parents in phenotype space;
  2. fitness scaling (linear or sigma truncation) to avoid super indivivual (high dominating fitness) premature convergence and also have a guarantee of positive fitness;
  3. different sampling methods for the selection of parents (stochastic universal sampling, ranking selection, replacement as a complementary operator to selection: generational replacement, overlapping populations in which only a subset of the current population is replaced in steady-state GAs, incremental GAs)
  4. dealing with multimodal (multiple peaks of unequal values) functions which causes genetic drift that are dealt with niche species and indivivual fitness sharing …

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s