Click or drag to resize

Genetic Algorithm

Genetic algorithm is a method for solving optimization problems, which is based on natural selection, i.e. represents a certain analogy to biological evolution. Genetic algorithm can be applied to various optimization problems that are not always easily solved with standard optimization algorithms. First of all this method is used to solve problems when the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

This topic contains the following sections:

Overview

Genetic Algorithm is a heuristic algorithm that simulates the natural process of evolution. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover. See Basic Terms And Steps.

It's important to understand that the functioning of such an algorithm does not guarantee success. We are in a stochastic system and a genetic pool may be too far from the solution, or for example, a too fast convergence may halt the process of evolution. These algorithms are nevertheless extremely efficient.

The algorithm must have these elements to be "genetic":

  • A mathematical representation for the solutions.

  • A method of creating the initial population.

  • A method for measuring the fitness.

  • Genetic functions: cross-over and mutation.

  • A number of parameters: the size of the population, the mutation rate, etc.

Advantages and disadvantages

A GA has a number of advantages:

  • Fast scan of a vast solution set

  • Bad proposals do not affect the end solution negatively as they are simply discarded.

  • The inductive nature of the GA. It doesn't have to know any rules of the problem - it works by its own internal rules. This is very useful for complex or loosely defined problems.

GA has drawbacks too, of course. In nature life does not evolve towards a good solution - it evolves away from bad circumstances. This can cause a species to evolve into an evolutionary dead end. Likewise, GA risks finding a suboptimal solution and we may not even know it.

See Also