Genetic Algorithms: Complete Guide — Principles, Examples, and Python Implementation

Summary — Genetic algorithms are optimization techniques inspired by natural evolution. A population of candidate solutions evolves through selection, crossover, and mutation operators, progressively converging toward optimal or near-optimal solutions. Applicable to continuous, discrete, or combinatorial problems, they excel where classical gradient methods fail.

Mathematical principle

A genetic algorithm models an evolutionary process in four cyclic phases:

1. Individual representation: Each candidate solution is encoded as a chromosome — a vector (binary, integer, real, or permutation) of genes. For example, to optimize a function f(x,y), the chromosome [x, y] contains two real genes.

2. Fitness (evaluation function): Each individual is assigned a fitness score, which measures the quality of its solution. For a maximization of f, fitness = f(x). For a minimization problem, fitness = -f(x) or fitness = 1/(1+f(x)).

3. Evolutionary operators:

a) Selection: Individuals are chosen for reproduction according to their fitness. Two methods dominate:
– Tournament selection: Draw k individuals at random, keep the best. Tournament size = selective pressure.
– Roulette wheel (fitness-proportionate): Probability p_i = fitness_i / Σ fitness_j. The best have more chances but average ones can still be selected.

b) Crossover: Two parents produce children by combining their chromosomes.
– Single-point: Cut chromosomes at a random point, swap halves.
– Two-point: Two cuts, swap the middle segment.
– Blending (real-valued): Child = α·parent1 + (1-α)·parent2.

c) Mutation: Random modification of one or more genes with probability p_m (typically 1-5%). For real-valued chromosomes: add Gaussian noise. For binary: flip the bit.

4. Replacement and elitism: The new generation replaces the old one. Elitism consists of keeping the best individuals intact, ensuring that the best fitness never decreases from one generation to the next.

Convergence: The algorithm is not guaranteed to find the global optimum, but converges asymptotically to it under theoretical conditions (Holland’s schema theorem). In practice, we stop after a fixed number of generations or when the best fitness plateaus.

Intuition

Imagine breeding racing pigeons. You start with a diverse group — some fly fast, others are enduring, others good navigators. Your goal: create the perfect pigeon.

Each generation, you:
1. Select the best breeders (those with the best performance)
2. Cross their characteristics — a fast pigeon × an endurance pigeon might produce a pigeon that is fast AND enduring
3. Mutate occasionally — a pigeon is born with an unexpected characteristic (better night vision?) that could be an advantage

After dozens of generations, you get pigeons far better than the best individual from the initial generation. That’s exactly what a genetic algorithm does — except instead of breeding pigeons over years, it evaluates millions of solutions in seconds on a processor.

The key: unlike gradient methods that follow a local slope, genetic algorithms simultaneously explore multiple regions of the search space. Mutation introduces novelty, crossover combines good ideas, and selection eliminates bad combinations.

Python implementation

Example 1: From-scratch implementation — function optimization

import numpy as np
import matplotlib.pyplot as plt

def fitness(x):
    return np.sin(x*3) + np.cos(x*2) + x/5  # multi-modal function

def genetic_algorithm(pop_size=100, n_gen=50, x_min=-5, x_max=5,
                      mut_prob=0.1, elite_frac=0.1, seed=42):
    np.random.seed(seed)

    # Uniform random initialization
    population = np.random.uniform(x_min, x_max, pop_size)

    best_history = []
    avg_history = []

    for gen in range(n_gen):
        # Evaluation
        scores = fitness(population)

        # History
        best_history.append(scores.max())
        avg_history.append(scores.mean())

        # Tournament selection
        def tournament(pop, scores, k=3):
            idx = np.random.choice(len(pop), k)
            return pop[idx[scores[idx].argmax()]]

        # Elitism
        n_elite = max(1, int(pop_size * elite_frac))
        elite_idx = np.argsort(scores)[-n_elite:]
        new_pop = list(population[elite_idx])

        # Reproduction
        while len(new_pop) < pop_size:
            p1 = tournament(population, scores, k=3)
            p2 = tournament(population, scores, k=3)

            # Blending crossover
            alpha = np.random.uniform(0.2, 0.8)
            child = alpha * p1 + (1 - alpha) * p2

            # Gaussian mutation
            if np.random.random() < mut_prob:
                child += np.random.normal(0, 0.5)
                child = np.clip(child, x_min, x_max)

            new_pop.append(child)

        population = np.array(new_pop)

    best_idx = fitness(population).argmax()
    best_sol = population[best_idx]
    best_fit = fitness(best_sol)
    print(f"Optimal solution: x = {best_sol:.4f}, f(x) = {best_fit:.4f}")
    return best_sol, best_fit, best_history, avg_history

# Execution
solution, optimum, best_hist, avg_hist = genetic_algorithm()

# Convergence visualization
plt.figure(figsize=(8, 4))
plt.plot(best_hist, 'r-', label='Best fitness', linewidth=2)
plt.plot(avg_hist, 'b--', label='Average fitness', linewidth=1)
plt.title('Genetic algorithm convergence')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('genetic_convergence.png', dpi=150)
print(f"Chart saved")

Example 2: Solving the Traveling Salesman Problem (TSP)

import numpy as np

# Cities (coordinates)
cities = np.array([
    [60, 200], [180, 200], [80, 180], [140, 180],
    [20, 160], [100, 160], [200, 160], [140, 140],
    [40, 120], [100, 120], [180, 100], [60, 80],
    [120, 80], [180, 60], [20, 40], [100, 40],
    [200, 40], [20, 20], [60, 20], [160, 20],
])
n_cities = len(cities)

def distance_matrix(cities):
    n = len(cities)
    dist = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist[i, j] = np.linalg.norm(cities[i] - cities[j])
    return dist

dist = distance_matrix(cities)

def tour_length(route):
    return sum(dist[route[i], route[i+1]] for i in range(len(route)-1)) + dist[route[-1], route[0]]

def ga_tsp(pop_size=50, n_gen=200, mut_prob=0.3):
    np.random.seed(42)

    # Initial population of permutations
    population = [np.random.permutation(n_cities) for _ in range(pop_size)]
    best_hist = []

    for gen in range(n_gen):
        scores = [-tour_length(r) for r in population]  # negative for maximization

        best_hist.append(-min(tour_length(r) for r in population))

        # Elitism
        n_elite = 5
        elite_idx = np.argsort(scores)[-n_elite:]
        new_pop = [population[i] for i in elite_idx]

        # Tournament selection
        def tournament(idx_list):
            k = min(3, len(idx_list))
            chosen = np.random.choice(idx_list, k, replace=False)
            return chosen[np.argmax([scores[i] for i in chosen])]

        all_idx = list(range(pop_size))

        while len(new_pop) < pop_size:
            p1 = population[tournament(all_idx)].copy()
            p2 = population[tournament(all_idx)].copy()

            # Order Crossover (OX)
            start, end = sorted(np.random.choice(n_cities, 2, replace=False))
            child = [None] * n_cities
            child[start:end+1] = p1[start:end+1]
            remaining = [g for g in p2 if g not in child[start:end+1]]
            j = 0
            for i in range(n_cities):
                if child[i] is None:
                    child[i] = remaining[j]
                    j += 1

            # Swap mutation
            if np.random.random() < mut_prob:
                i1, i2 = np.random.choice(n_cities, 2, replace=False)
                child[i1], child[i2] = child[i2], child[i1]

            new_pop.append(np.array(child))

        population = new_pop

    best_route = min(population, key=tour_length)
    best_dist = tour_length(best_route)
    print(f"Best TSP distance: {best_dist:.2f}")
    return best_route, best_dist, best_hist

route, distance, history = ga_tsp()

Hyperparameters

Advantages of genetic algorithms

1. No gradient required: They work on non-differentiable, discontinuous, noisy, or black-box functions — where gradient methods are inapplicable.
2. Global search: Multi-point exploration reduces the risk of getting trapped in a local optimum, unlike gradient descent.
3. Extreme flexibility: Applicable to continuous, discrete, combinatorial problems (TSP, scheduling), and even to neural network design (neuroevolution).
4. Natural parallelization: Fitness evaluation is independent — perfectly parallelizable on clusters or GPUs.
5. Conceptual simplicity: The core algorithm fits in a few lines of code, making it accessible and easy to adapt.

Limitations of genetic algorithms

1. No optimality guarantee: No bound on the quality of the final solution — we get a “good” solution, not necessarily the best.
2. Hyperparameter tuning: Performance depends heavily on the choice of population size, mutation and crossover rates — few universal rules.
3. Computational cost: Thousands of fitness evaluations are needed — problematic if each evaluation is expensive (CFD simulation, network training).
4. Premature convergence: If selective pressure is too strong, the population quickly converges to a local optimum and genetic diversity collapses.
5. No real-time response: The iterative process (generations) is inherently sequential — unsuitable for decisions that must be made in milliseconds.

4 concrete use cases

1. Delivery route optimization (logistics)

Delivery companies use genetic algorithms to optimize the routes of their truck fleets — the famous Traveling Salesman Problem (TSP) and its variants (VRP, CVRP). Each chromosome represents a delivery sequence, and fitness is the total distance or cost. Constraints (vehicle capacity, time windows) are incorporated into the fitness function as penalties.

2. Aerospace component design

Airbus and Boeing use evolutionary approaches to optimize the shape of airplane wings. The chromosome encodes the geometry (curvature, thickness, wingspan), and fitness is the lift-to-drag ratio evaluated by CFD simulation. The flexibility of GAs allows exploring counter-intuitive shapes that engineers would not have considered.

3. Machine learning — feature selection and model tuning

Genetic algorithms are used to select the most informative variables in a dataset (each bit of the chromosome = inclusion or exclusion of a feature). Combined with a classifier as the fitness score, they often find feature subsets that perform better than classical forward/backward methods. Frameworks like TPOT even automate the design of entire ML pipelines through a genetic approach.

4. Production scheduling and timetabling

In manufacturing, job scheduling on machines (job-shop scheduling) is an NP-hard problem. Genetic algorithms find near-optimal schedules that minimize total production time and waiting times, while respecting resource and sequencing constraints. Each chromosome encodes an execution order of tasks.

Best practices

• Start with standard parameters: population=100, crossover=0.8, mutation=0.05, elitism=5 — then refine.
• Monitor diversity: If the variance of fitness in the population drops sharply, it is a sign of premature convergence — increase mutation or population size.
• Use elitism systematically: Keeping at least the best individual avoids regression between generations.
• Hybridization: Combine a GA with a local method (gradient, Nelder-Mead) to refine the best solutions — this is the “memetic algorithm” approach.
• Reproducibility: Fix the random seed so that results are reproducible, especially in research or production.

Conclusion

Genetic algorithms represent a powerful and elegant approach for solving complex optimization problems where classical methods fail. Their strength lies in their ability to explore vast search spaces without assumptions about the problem structure — no differentiability, convexity, or continuity required.

They are not, however, a universal solution: for convex, well-conditioned problems, gradient descent will always be faster and more precise. Genetic algorithms shine where the solution landscape is rugged, discontinuous, or combinatorial.

See also

• Multiplying character strings with Python
• Master the Art of Reverse Engineering in Python: Complete Guide for Beginners and Experts