What is a genetic algorithm? Process and applications

A genetic algorithm is an optimization technique inspired by the process of natural selection, designed to gradually enhance groups of possible solutions. These algorithms are used in a wide range of areas, from improving technical systems to advancing machine learning.

What are genetic algorithms?

Genetic algorithms (GAs) are a global heuristic for solving decision problems, grounded in the principles of natural selection and genetics. A type of evolutionary algorithm, GAs simulate natural selection processes to progressively improve solutions to complex problems. At their core, GAs embody the concept of “survival of the fittest,” drawing on the following principles:

1. Individuals compete for resources and reproduction opportunities.
2. The most successful or strongest individuals produce more offspring than others.
3. The genes of the “fittest” parents are passed on across generations, often resulting in offspring with better genetic sequences than their parents.
4. Over time, as the best genes are perpetuated, each generation becomes better adapted to its environment than the previous one.

Genetic algorithms generate a population of individuals, each representing a potential solution to a given problem. Those individuals that best adapt to their environment survive and reproduce. Each individual is represented by chromosomes encoded as strings (characters, bits, floats, or integers). These chromosomes can be divided into genes that specify particular traits (e.g., hair color), and each gene’s variations—such as blonde, brown, or black—are referred to as alleles.

To gradually approach the optimal solution, genetic algorithms execute a multi-step process involving computation and reproduction. Chromosomes are modified and combined through several generations or iterations using genetic operators—selection, crossover (recombination), and mutation—to find better solutions progressively. This approach enables genetic algorithms to combine strong partial solutions into a high-quality global solution.

How do genetic algorithms work?

The iterative process typically includes the following subroutines:

1. The optimization problem is encoded and mapped to a binary-coded chromosome.
2. The genetic algorithm generates and initializes a population of individuals randomly. This initial population is called Generation 0.
3. A fitness score, expressed as a real number, is assigned to each individual.
4. Using a predefined selection method, the genetic algorithm selects parents from the population.
5. Offspring are generated based on the genetic information of both parents.
6. The offspring’s genetic traits (alleles) may undergo mutation, leading to inverted values.
7. The population grows to include the newly generated offspring. If the population size exceeds a set limit, a replacement scheme determines which individuals are removed from the solution pool.
8. Steps 3 to 7 are repeated until a termination criterion is met, bringing the algorithm closer to the optimal solution. Termination criteria can vary widely: some algorithms run for a set number of generations, while others continue until no improvement is observed between generations.

Fitness score

Fitness measures an individual’s adaptability. The fitness score indicates its competitiveness, and the genetic algorithm aims to identify the individual with the ideal (or nearly ideal) fitness. Individuals with better scores are more likely to be selected for reproduction, ensuring that new generations average stronger solutions than previous ones.

What operators do genetic algorithms use?

Genetic algorithms utilize several operators to evolve the initial population. The primary mechanisms enabling evolution are selection, recombination, and mutation. These operators are explained below:

Selection operator

Selection determines which individuals are allowed to reproduce and how many offspring they are permitted to have. The selection process is based on fitness scores, with individuals boasting higher scores being favored.

Crossover operator

New individuals are created through recombination. Crossover points are chosen randomly by the genetic algorithm, and at these points, genes are exchanged between parents, producing offspring with new traits. The following example demonstrates recombination:

• Genes of Parent 1: A|B|C|D|E|F
• Genes of Parent 2: G|H|I|J|K|L
• Genes of Offspring: A|B|I|J|K|F

Mutation operator

Mutations introduce random changes to the offspring’s genes, altering the potential solution to a decision problem. This maintains diversity within the population and prevents premature convergence. Here’s an example of mutation:

• Genes before mutation: A|B|C|D|E|F
• Genes after mutation: A|B|L|D|T|F

Where are genetic algorithms used?

Genetic algorithms are particularly useful in areas where traditional analytical methods fall short—primarily for problems with large, complex solution spaces. A central application is in deep learning, where GAs optimize the weights of neural networks.

Beyond that, genetic algorithms are widely used in production planning to optimize schedules and resource allocations. In business and finance, they assist with portfolio optimization and the development of complex trading strategies. Another area of application is hyperparameter tuning for machine learning models. Although not always the most efficient method, GAs are valued for their flexibility as a versatile optimization technique.

Practical example of genetic algorithms

Consider a genetic algorithm tasked with generating a target string, such as “the fittest survive,” starting from a random string of the same length. In this case, individual characters (A–Z, a–z, 0–9, and special characters) represent genes, while the string as a whole is the chromosome or solution. The fitness score corresponds to the number of characters that differ from the target string, with lower scores being preferable. Below is an example of how the output might look:

Note that the output may vary because genetic algorithms begin with random strings.