What is a genetic algorithm? Process and ap­plic­a­tions

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

What are genetic al­gorithms?

Genetic al­gorithms (GAs) are a global heuristic for solving decision problems, grounded in the prin­ciples of natural selection and genetics. A type of evol­u­tion­ary algorithm, GAs simulate natural selection processes to pro­gress­ively improve solutions to complex problems. At their core, GAs embody the concept of ‘survival of the fittest’, drawing on the following prin­ciples:

1. In­di­vidu­als compete for resources and re­pro­duc­tion op­por­tun­it­ies.
2. The most suc­cess­ful or strongest in­di­vidu­als produce more offspring than others.
3. The genes of the ‘fittest’ parents are passed on across gen­er­a­tions, often resulting in offspring with better genetic sequences than their parents.
4. Over time, as the best genes are per­petu­ated, each gen­er­a­tion becomes better adapted to its en­vir­on­ment than the previous one.

Genetic al­gorithms generate a pop­u­la­tion of in­di­vidu­als, each rep­res­ent­ing a potential solution to a given problem. Those in­di­vidu­als that best adapt to their en­vir­on­ment survive and reproduce. Each in­di­vidu­al is rep­res­en­ted by chro­mo­somes encoded as strings (char­ac­ters, bits, floats, or integers). These chro­mo­somes can be divided into genes that specify par­tic­u­lar traits (e.g., hair color), and each gene’s vari­ations—such as blonde, brown, or black—are referred to as alleles.

To gradually approach the optimal solution, genetic al­gorithms execute a multi-step process involving com­pu­ta­tion and re­pro­duc­tion. Chro­mo­somes are modified and combined through several gen­er­a­tions or it­er­a­tions using genetic operators—selection, crossover (re­com­bin­a­tion), and mutation—to find better solutions pro­gress­ively. This approach enables genetic al­gorithms to combine strong partial solutions into a high-quality global solution.

How do genetic al­gorithms work?

The iterative process typically includes the following sub­routines:

1. The op­tim­isa­tion problem is encoded and mapped to a binary-coded chro­mo­some.
2. The genetic algorithm generates and ini­tial­ises a pop­u­la­tion of in­di­vidu­als randomly. This initial pop­u­la­tion is called Gen­er­a­tion 0.
3. A fitness score, expressed as a real number, is assigned to each in­di­vidu­al.
4. Using a pre­defined selection method, the genetic algorithm selects parents from the pop­u­la­tion.
5. Offspring are generated based on the genetic in­form­a­tion of both parents.
6. The offspring’s genetic traits (alleles) may undergo mutation, leading to inverted values.
7. The pop­u­la­tion grows to include the newly generated offspring. If the pop­u­la­tion size exceeds a set limit, a re­place­ment scheme de­term­ines which in­di­vidu­als are removed from the solution pool.
8. Steps 3 to 7 are repeated until a ter­min­a­tion criterion is met, bringing the algorithm closer to the optimal solution. Ter­min­a­tion criteria can vary widely: some al­gorithms run for a set number of gen­er­a­tions, while others continue until no im­prove­ment is observed between gen­er­a­tions.

Fitness score

Fitness measures an in­di­vidu­al’s ad­apt­ab­il­ity. The fitness score indicates its com­pet­it­ive­ness, and the genetic algorithm aims to identify the in­di­vidu­al with the ideal (or nearly ideal) fitness. In­di­vidu­als with better scores are more likely to be selected for re­pro­duc­tion, ensuring that new gen­er­a­tions average stronger solutions than previous ones.

What operators do genetic al­gorithms use?

Genetic al­gorithms utilise several operators to evolve the initial pop­u­la­tion. The primary mech­an­isms enabling evolution are selection, re­com­bin­a­tion, and mutation. These operators are explained below:

Selection operator

Selection de­term­ines which in­di­vidu­als are allowed to reproduce and how many offspring they are permitted to have. The selection process is based on fitness scores, with in­di­vidu­als boasting higher scores being favored.

Crossover operator

New in­di­vidu­als are created through re­com­bin­a­tion. 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 demon­strates re­com­bin­a­tion:

• 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 pop­u­la­tion and prevents premature con­ver­gence. 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 al­gorithms used?

Genetic al­gorithms are par­tic­u­larly useful in areas where tra­di­tion­al ana­lyt­ic­al methods fall short—primarily for problems with large, complex solution spaces. A central ap­plic­a­tion is in deep learning, where GAs optimise the weights of neural networks.

Beyond that, genetic al­gorithms are widely used in pro­duc­tion planning to optimise schedules and resource al­loc­a­tions. In business and finance, they assist with portfolio op­tim­isa­tion and the de­vel­op­ment of complex trading strategies. Another area of ap­plic­a­tion is hy­per­para­met­er tuning for machine learning models. Although not always the most efficient method, GAs are valued for their flex­ib­il­ity as a versatile op­tim­isa­tion technique.

Practical example of genetic al­gorithms

Consider a genetic algorithm tasked with gen­er­at­ing a target string, such as ‘the fittest survive’, starting from a random string of the same length. In this case, in­di­vidu­al char­ac­ters (A–Z, a–z, 0–9, and special char­ac­ters) represent genes, while the string as a whole is the chro­mo­some or solution. The fitness score cor­res­ponds to the number of char­ac­ters that differ from the target string, with lower scores being prefer­able. Below is an example of how the output might look:

Note that the output may vary because genetic al­gorithms begin with random strings.