Overview of Genetic Algorithms

Hello, this is the live document on genetic algorithms. I plan to edit this post as I gather more information about it.

This post was last updated September 23rd 2025.

What is a Genetic Algorithm

A genetic algorithm (GA) is a type of search based algorithm where solutions ‘evolve’ towards an optimal or sub-optimal solution using a simplified model of natural evolution. A genetic algorithm starts by randomly generating a set (“population”) of potential solutions (“individuals” or “chromosomes”) and evaluating how well they preform based on some “fitness function.” During each step (“generation”) of the algorithm, individuals from the population are randomly chosen as “parents” weighted by their fitness using a selection function (higher fitness individuals are chosen at a higher rate then less fit individuals). These parents are randomly modified (“mutated”) and combined (“cross-over”) to produce “children” that are added to the population to be chosen as parents for the next generation. Overtime the population consists of more fit individuals, due to high fitness individuals being chosen at a higher rate.

Terms

Here are the key terms that are used in Genetic Algorithms

• Individual: This is also referred to as a “chromosome” in some works. An individual is a single potential solution to the problem being solved. The representation of an individual is dependant on the problem space, but has to have certain qualities: it must be able to be evaluated by a fitness function, it must has sub-parts that are able to be randomly changed and combined with other individuals (see mutation and cross-over), it must be able to be randomly generated.
• Mutation: Mutation is the process of randomly changing an individual. How exactly mutation works depends on the representation of an individual. Mutation often involves randomly substituting a sub-part of the individual with another potential sub-part. GAs will also often define a “mutation-rate” as a hyper parameters, which defines that probability of any individual sup-part being mutated.
• Cross-Over: Cross-over is the process of randomly combining two parent individuals. This will often look like selecting a “cross-over” point in both parent individuals and producing two child individuals, where the first child as the first part of parent one and the second part of parent two. The second child will have the opposite: the first part of parent one and the second part of parent two. This way both children produced have ‘genetic material’ (sub-components) from each parent. GAs will often define a “cross-over rate” which is the probability that any two selected parents individuals will have the cross-over algorithm applied to them.
• Fitness Function: This is a function that takes in an individual as input and returns the “quality” of the individual as a numeric value. The fitness function is dependant on the problem you are trying to solve.
• Selection Function: This is the function that chooses which parent to select from the population. There are many possible selection functions, but they must be biased towards high fitness individuals
• Generation: In a genetic algorithm, one “generation” refers to one cycle of replacing the parent population with new children. GAs will often have “number of generations” as a hyper-parameters, which defines how many generations will be completed before the algorithm stops. There are alternative stopping criteria such as reaching a certain top fitness value, or the amount fitness increases between generations being below a certain value.
• Population: This is list the of individuals produced in the last generation. The population is used to select parents for the next generation.

Fundamental Example

In this section I will go into depth on a simple example genetic algorithm to demonstrate the key concepts. Note that most GAs are more complex than this example, and GA should only be implemented for more complex problem spaces.

Problem Space

For this example we will look at evolving bit strings to maximize the number of 1s in the string.

• Individual: Each individual is a n-sized bit string, that is a string of characters made up of 0s and 1s (ex: “10001110”). Bit strings are randomly generated by selected 1 or 0 for each character with equal chance of either character.
• Mutation: To mutate a bit-string, we go through each character in the string. At a pre-defined rate (e.x: 10%), we will flip the bit (change a 0 into a 1 or change a 1 into a 0). For example let’s mutate the string “10001110”
  • Roll a ten sided dice 8 times. Record each time it lands on 1.
    • Dice roll outcomes: 3 , 10, 1, 9, 7, 4, 2, 1
  • Flip the bit for each time we rolled a one
    • 1000 1110 -> 1010 1111
  • Our new mutated string is “10101111”
• Cross-over: First randomly select an integer, i, between 0 and n-1. Create child one by concatenating the first i characters of parent one and the last n-i characters of parent two. For example let’s mutate the strings: “0000 0000” and “1111 1111”
  • Roll a 8 sided dice to determine where to cross over
    • Dice roll outcome: 2
  • Splice the parent string at this point
    • 00 000000 and 11 111111
  • Combine to make two children
    • “00111111” and “1100000”
• Fitness function: The fitness function simply returns the number of 1s in our string. For example the fitness of “10001110” is 4.
• Selection function: We will use Roulette Wheel as our selection criteria. In this function, individuals are selected based on their proportional fitness. That is the probability of selecting an individual with fitness f is f divided by the sum of fitness for all individuals in the population.

Algorithms

Below I will provide pseudo-code for the algorithms used in this example

Generate Random

def generate():
    str = "" 
    for i in range(N):
        char = choose(from =[0, 1], weights=[0.5, 0.5])
        str += char 
    return str 

Mutation

def mutate(individual, mut_rate): 
    child = ""
    for char in individual: 
        if coin_flip(mut_rate): 
           char = flip(char)
        
        child += char 
    return child

Cross Over

def cross_over(parent1, parent2): 
    i = random_integer(0, N-1)
    child1 = parent1[0, i] + parent2[i + 1, N -1]
    child2 = parent1[0, i] + parent2[i + 1, N -1]

    return child1, child2 

Fitness

def fitness(individual):
    fit = 0 
    for char in individual: 
        if char == 1: 
            fit += 1 
    
    return fit 

Selection

def select(population):
    total = sum(i.fitness for i in population)
    for i in population: 
        i.weight = i.fitness / total 

    return choose(from=population, weights = [i.weight for i in population]) 

** Genetic Algorithm**

def evolve(gens, popsize, mut_rate, x_rate):
    population = [generate() for i in range(popsize)]

    for gen in gens:
        new_pop = []
        while length(new_pop)  < popsize:
            parent1 = select(population)
            parent2 = select(population)

            if coin_flip(x_rate):
                child1, child2 = cross_over(parent1, parent2)
            else: 
                child1, child2 = parent1, parent2
            new_pop += [child1, child2]

        population = new_pop 
    return population  
        

Genetic Algorithm Variations

There are many different ways to modify this basic version of a genetic algorithm to be better suited for different needs. All parts of the genetic algorithm can be adjusted depending on the problem space you are working in. Here are some example of the most common variations for GAs. Note that many of these variations can, and have, been combined to serve different purposes.

Modifying the Population Structure

• Quality Diversity Algorithms: These algorithm are used when you want to not only find the single best solution, but want many high quality solutions that vary in certain characteristics. The most popular Quality Diversity Algorithm is called MapElites, where the population is represented as a grid where the rows and columns represent ranges of values from specified diversity functions.
• Constrained Evolution: In generic GAs, the fitness function is designed to optimize a particular quality. However, in many situations we want to both optimize a certain quality, but also eliminate infeasible individuals. The most common algorithm in this space is called the Feasible-Infeasible Two Population (FI-2Pop). This algorithm maintains two populations, the infeasible population with feasible individuals that evolve towards becoming feasible and the feasible population which evolve towards some optimization function.

Modifying the Individual Representation

• Genetic Programming: Genetic programming is used when you want to evolve an operation rather then an artifact. In genetic programming, individuals are represented in a tree or graph structure. The nodes in the tree are either operations or terminals. As a simple example, consider representing an arithmetic equation. The operations would be the mathematical operations (e.g -, +, /, *) and the terminals would be either a variable (e.g x,y) or constants (e.g. 1,2,3..).
• NeuroEvolution: In NeuroEvolution the individual is represented as a neural net and the genetic operators modify the weights or structures. NeuroEvolution is often used to generate behaviors, for example for game playing algorithms or robotics.

Modifying the Fitness Function

• Multi-Objective Evolution: Multi-objective GAs seek to evolve individuals that are high quality not just in a single fitness function, but across many fitness functions. There are many different approaches for Multi-objective evolution, but many algorithms use the concept of the Pareto-optimal front. The Pareto-optimal front is the set of solutions within a population that represents the best trade off between all fitness functions.
• Co-Evolution: In generic GAs, the fitness function is completely independent of the population. However, in some instances you don’t have an objective measure of fitness, but instead can only judge fitness relatively. In co-evolution, the fitness of individuals is determined based on the other individuals in the population. For example consider a game-playing algorithm whose fitness is determined by how well it plays against other game playing algorithms.
• Surrogate Models: Often the slowest part of evolution is evaluating the fitness function. One solution to speed up evolution is to learn a surrogate of the fitness function, which in some way approximates the true fitness function but at faster run-times. For example, you could train a machine learning model to predict the fitness function given a dataset of previously calculated values.

MSC.

• Interactive Evolution: Interactive evolution can refer to a wide range of algorithms in which a human participates in some part of the evolution process. In human evolution the human determined fitness, for example by selecting their favorite individual out of the population. Other approaches have humans supplying individuals into the population, or modifying their preference throughout the evolutionary process. Check out the live post for interactive GAs to learn more.

Read More

Here I will collect valuable citations if you want to learn more about Genetic Algorithms

• A review of Genetic Algorithms
  • Katoch, S., Chauhan, S.S. & Kumar, V. A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 (2021). https://doi.org/10.1007/s11042-020-10139-6
  • This paper preformed a systematic review of Genetic Algorithm paper and does a good job describing the variations of GAs and there strengths/disadvantages
• Map Elites
  • Mouret, Jean-Baptiste, and Jeff Clune. “Illuminating search spaces by mapping elites.” arXiv preprint arXiv:1504.04909 (2015).
  • This is paper that introduce the popular MapElites algorithm
• No Free Lunch
  • Wolpert, David H., and William G. Macready. No free lunch theorems for search. Vol. 10. No. 12. Technical Report SFI-TR-95-02-010, Santa Fe Institute, 1995.
  • This fundamental paper outlines the problem with search based algorithms (including GAs): over the space of all problems no one search algorithm can out preform another search algorithm