What is a genetic algorithm? Process and ap­pli­ca­tions

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

What are genetic al­go­rithms?

Genetic al­go­rithms (GAs) are a global heuristic for solving decision problems, grounded in the prin­ci­ples of natural selection and genetics. A type of evo­lu­tion­ary algorithm, GAs simulate natural selection processes to pro­gres­sive­ly improve solutions to complex problems. At their core, GAs embody the concept of “survival of the fittest,” drawing on the following prin­ci­ples:

1. In­di­vid­u­als compete for resources and re­pro­duc­tion op­por­tu­ni­ties.
2. The most suc­cess­ful or strongest in­di­vid­u­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­pet­u­at­ed, each gen­er­a­tion becomes better adapted to its en­vi­ron­ment than the previous one.

Genetic al­go­rithms generate a pop­u­la­tion of in­di­vid­u­als, each rep­re­sent­ing a potential solution to a given problem. Those in­di­vid­u­als that best adapt to their en­vi­ron­ment survive and reproduce. Each in­di­vid­ual is rep­re­sent­ed 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­a­tions—such as blonde, brown, or black—are referred to as alleles.

To gradually approach the optimal solution, genetic al­go­rithms 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­bi­na­tion), and mutation—to find better solutions pro­gres­sive­ly. This approach enables genetic al­go­rithms to combine strong partial solutions into a high-quality global solution.

How do genetic al­go­rithms work?

The iterative process typically includes the following sub­rou­tines:

1. The op­ti­miza­tion problem is encoded and mapped to a binary-coded chro­mo­some.
2. The genetic algorithm generates and ini­tial­izes a pop­u­la­tion of in­di­vid­u­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­vid­ual.
4. Using a pre­de­fined selection method, the genetic algorithm selects parents from the pop­u­la­tion.
5. Offspring are generated based on the genetic in­for­ma­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­ter­mines which in­di­vid­u­als are removed from the solution pool.
8. Steps 3 to 7 are repeated until a ter­mi­na­tion criterion is met, bringing the algorithm closer to the optimal solution. Ter­mi­na­tion criteria can vary widely: some al­go­rithms 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­vid­ual’s adapt­abil­i­ty. The fitness score indicates its com­pet­i­tive­ness, and the genetic algorithm aims to identify the in­di­vid­ual with the ideal (or nearly ideal) fitness. In­di­vid­u­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­go­rithms use?

Genetic al­go­rithms utilize several operators to evolve the initial pop­u­la­tion. The primary mech­a­nisms enabling evolution are selection, re­com­bi­na­tion, and mutation. These operators are explained below:

Selection operator

Selection de­ter­mines which in­di­vid­u­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­vid­u­als boasting higher scores being favored.

Crossover operator

New in­di­vid­u­als are created through re­com­bi­na­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­bi­na­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­go­rithms used?

Genetic al­go­rithms are par­tic­u­lar­ly useful in areas where tra­di­tion­al an­a­lyt­i­cal methods fall short—primarily for problems with large, complex solution spaces. A central ap­pli­ca­tion is in deep learning, where GAs optimize the weights of neural networks.

Beyond that, genetic al­go­rithms are widely used in pro­duc­tion planning to optimize schedules and resource al­lo­ca­tions. In business and finance, they assist with portfolio op­ti­miza­tion and the de­vel­op­ment of complex trading strate­gies. Another area of ap­pli­ca­tion is hy­per­pa­ra­me­ter tuning for machine learning models. Although not always the most efficient method, GAs are valued for their flex­i­bil­i­ty as a versatile op­ti­miza­tion technique.

Practical example of genetic al­go­rithms

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­vid­ual 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­re­sponds 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­go­rithms begin with random strings.