Genetic algorithm

File:ESA JAXA HUMIES Trajectory.png

A search heuristic that mimics the process of natural selection

 This article is about the search heuristic.
   For the broader field of study, see Evolutionary algorithm.

Genetic algorithms (GAs) are a class of evolutionary algorithms that use techniques inspired by natural selection and genetics to solve optimization and search problems. They are particularly useful for problems where the search space is large, complex, or poorly understood.

Overview

Genetic algorithms are based on the principles of Darwinian evolution, where the fittest individuals are selected for reproduction in order to produce the next generation. The process involves the following key steps:

1. Initialization: A population of candidate solutions, called individuals, is generated randomly or heuristically.
2. Selection: Individuals are selected based on their fitness, which is determined by a fitness function that evaluates how well they solve the problem at hand.
3. Crossover (Recombination): Selected individuals are paired and combined to produce offspring. This mimics biological reproduction and allows for the exchange of genetic material.
4. Mutation: Offspring undergo random changes to introduce genetic diversity and explore new areas of the search space.
5. Replacement: The new generation replaces the old one, and the process repeats until a termination condition is met, such as a satisfactory fitness level or a maximum number of generations.

Components

Representation

The choice of representation, or encoding, of the candidate solutions is crucial in genetic algorithms. Common representations include:

• Binary strings: Each individual is represented as a string of binary digits (0s and 1s).
• Real-valued vectors: Useful for problems with continuous parameters.
• Permutations: Often used for ordering problems, such as the traveling salesman problem.

Selection Methods

Several selection methods exist to choose individuals for reproduction:

• Roulette wheel selection: Individuals are selected with a probability proportional to their fitness.
• Tournament selection: A subset of individuals is chosen randomly, and the fittest among them is selected.
• Rank selection: Individuals are ranked based on fitness, and selection is based on this ranking.

Crossover Operators

Crossover operators determine how genetic material is exchanged between parents:

• Single-point crossover: A single crossover point is chosen, and the genetic material is exchanged at this point.
• Two-point crossover: Two points are chosen, and the material between them is swapped.
• Uniform crossover: Each gene is independently chosen from one of the parents.

Mutation Operators

Mutation introduces random changes to individuals:

• Bit-flip mutation: In binary representations, bits are flipped with a certain probability.
• Gaussian mutation: In real-valued vectors, values are altered by adding a Gaussian-distributed random value.

Applications

Genetic algorithms have been applied to a wide range of problems, including:

• Optimization: Finding the best solution in complex search spaces.
• Machine learning: Evolving neural networks or decision trees.
• Scheduling: Solving scheduling problems in manufacturing and logistics.
• Game playing: Developing strategies for games.

Advantages and Limitations

Advantages

• Robustness: GAs are less likely to get stuck in local optima compared to traditional optimization methods.
• Flexibility: They can be applied to a wide variety of problems without requiring gradient information.

Limitations

• Computational cost: GAs can be computationally expensive, especially for large populations and complex fitness evaluations.
• Parameter tuning: The performance of GAs is sensitive to the choice of parameters, such as population size and mutation rate.

Also see

• Evolutionary algorithm
• Simulated annealing
• Particle swarm optimization
• Ant colony optimization
• Neural networks