Ipsos Encyclopedia - Genetic Algorithms (aka Evolutionary Algorithms)

Genetic algorithms are derivative-free and stochastic-optimization method based loosely on the concept of natural selection and evolutionary process by means of simulated evolution.

Definition

​Genetic algorithms are derivative-free and stochastic-optimization method based loosely on the concept of natural selection and evolutionary process by means of simulated evolution. They were developed by John Holland at University of Michigan in 1975.

Since it is optimization algorithm, there are always two components. One is the goal (e.g. minimize the total gap between predicted scores and observed scores) and the other is the model which is typically described by a mathematical equation (e.g. f(x)=ax2+bx+c, here f(x) is predicted scores). For optimization (to achieve the goal), we can have a certain combination of coefficients (e.g. a, b, and c as in above example equation).

The algorithm will start with a population of any size, for example 100 individuals(combination of coefficients), such that the individuals are randomly scattered throughout the population. For example application, fitness or natural selection for survival of each individual the population could be assessed using an r-squared measure (to be maximized) or a sum of squared errors (to be minimized). The genetic algorithm focuses on those few most fit individuals (e.g. having the strongest fitness value as in survival of the fittest). These selected subgroup (elite) of population reproduce partly reproduce themselves, partly crossover their chromosome (scores are encoded into binary scores and formed into chromosomes and exchange part of binary codes each other through elite population mating procedure) and some are mutated, which is completely a new and randomly different combination of coefficients. The new generation of population is born through the reproduction and crossover by elite population, and mutation. And this new generation will become a parent generation population and this generation evolution keep going on until there is not much improvement of achieving goal or fitness.

This is more efficient and faster process than random or Monte-Carlo search method and also keeping the merit of it which is more about exhaustive search that tries to avoid the local minima(stop searching at one of small hill, even though there is a lot larger mountain) that is often a typical problem of methods, such as Newton's Method or Gradient Descent Method.

New Services