Genetic Algorithms

History

Genetic Algorithms were invented to mimic some of the processes observed in natural evolution. Many people, biologists included, are astonished that life at the level of complexity that we observe could have evolved in the relatively short time suggested by the fossil record. The idea with GA is to use this power of evolution to solve optimization problems. The father of the original Genetic Algorithm was John Holland who invented it in the early 1970's.

Contents

What is Genetic Algorithms
Why Genetic Algorithms
Genetics Algorithms Overview
Implementation Details
Summary

What is Genetic Algorithms?

Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. As such they represent an intelligent exploitation of a random search used to solve optimization problems. Although randomised, GAs are by no means random, instead they exploit historical information to direct the search into the region of better performance within the search space. The basic techniques of the GAs are designed to simulate processes in natural systems necessary for evolution, specially those follow the principles first laid down by Charles Darwin of "survival of the fittest.". Since in nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones.


Why Genetic Algorithms?

It is better than conventional AI in that it is more robust. Unlike older AI systems, they do not break easily even if the inputs changed slightly, or in the presence of reasonable noise. Also, in searching a large state-space, multi-modal state-space, or n-dimensional surface, a genetic algorithm may offer significant benefits over more typical search of optimization techniques. (linear programming, heuristic, depth-first, breath-first, and praxis.)


Genetic Algorithms Overview

GAs simulate the survival of the fittest among individuals over consecutive generation for solving a problem. Each generation consists of a population of character strings that are analogous to the chromosome that we see in our DNA. Each individual represents a point in a search space and a possible solution. The individuals in the population are then made to go through a process of evolution.

GAs are based on an analogy with the genetic structure and behaviour of chromosomes within a population of individuals using the following foundations:


Search Space

A population of individualsare is maintained within search space for a GA, each representing a possible solution to a given problem. Each individual is coded as a finite length vector of components, or variables, in terms of some alphabet, usually the binary alphabet {0,1}. To continue the genetic analogy these individuals are likened to chromosomes and the variables are analogous to genes. Thus a chromosome (solution) is composed of several genes (variables). A fitness score is assigned to each solution representing the abilities of an individual to `compete'. The individual with the optimal (or generally near optimal) fitness score is sought. The GA aims to use selective `breeding' of the solutions to produce `offspring' better than the parents by combining information from the chromosomes.




The GA maintains a population of n chromosomes (solutions) with associated fitness values. Parents are selected to mate, on the basis of their fitness, producing offspring via a reproductive plan. Consequently highly fit solutions are given more opportunities to reproduce, so that offspring inherit characteristics from each parent. As parents mate and produce offspring, room must be made for the new arrivals since the population is kept at a static size. Individuals in the population die and are replaced by the new solutions, eventually creating a new generation once all mating opportunities in the old population have been exhausted. In this way it is hoped that over successive generations better solutions will thrive while the least fit solutions die out.

New generations of solutions are produced containing, on average, more good genes than a typical solution in a previous generation. Each successive generation will contain more good `partial solutions' than previous generations. Eventually, once the population has converged and is not producing offspring noticeably different from those in previous generations, the algorithm itself is said to have converged to a set of solutions to the problem at hand.


Implementation Details

Based on Natural Selection

After an initial population is randomly generated, the algorithm evolves the through three operators:
  1. selection which equates to survival of the fittest;
  2. crossover which represents mating between individuals;
  3. mutation which introduces random modifications.


1. Selection Operator

2. Crossover Operator



3. Mutation Operator



Effects of Genetic Operators

The Algorithms

  1. randomly initialize population(t)
  2. determine fitness of population(t)
  3. repeat
    1. select parents from population(t)
    2. perform crossover on parents creating population(t+1)
    3. perform mutation of population(t+1)
    4. determine fitness of population(t+1)
  4. until best individual is good enough


Summary

In previous subsection it has been claimed that via the operations of selection, crossover, and mutation the GA will converge over successive generations towards the global (or near global) optium. why these simple operation should produce a fast, useful and robust techiques is largely due to the fact that GAs combine direction and chance in the search in an effective and efficient manner. Since population implicitly contain much more information than simply the individual fitness scores, GAs combine the good information hidden in a solution with good information from another solution to produce new solutions with good indormation inherited from both parents, inevitably (hopefully) leading towrads optimality.

The ability of the algorithm to explore and exploit simultaneously, a growing amount of theoretical justification, and successful application to real-world problems strengthens the conclusion that GAs are a powerful, robust optimisation technique.

An introduction to Genetic Algorithms. mit press edited by Melanie Mitchell

Genetic algorithms in engineering and computer science / edited by G. Winter ... [et al.]. c1995

Foundations of genetic algorithms edited by Gregory J.E. Rawlins. c1991

The Genetic Algorithms Archive



For details of applications of genetics algorithms, please refer to my partner, Chun's article.