Genetic Algorithms

What Are Genetic Algorithms?

Genetic Algorithms (GAs) are optimisation techniques inspired by natural selection and biological evolution.

They are commonly used to generate high-quality (not necessarily optimal) solutions in complex problem spaces - especially where traditional methods are too slow or unreliable.

Key Components of Genetic Algorithms

Population

The population is the set of candidate solutions to the problem. Each individual in the population represents a possible solution, often encoded as a list or string. A larger population increases genetic diversity, allowing broader exploration and reducing the risk of premature convergence.

Example 1: In a route optimization problem with 5 cities, each route (like [0, 1, 4, 3, 2]) is an individual in the population.

Example 2: In a feature selection task for machine learning, each individual could be a bit string like [1, 0, 1, 1, 0], where 1 means the feature is selected and 0 means it's excluded.

Fitness Function

The fitness function measures how effective a solution is. This score determines an individual’s chance of being selected for reproduction. The goal is to guide evolution toward more optimal solutions over successive generations.

Example 1: In the travelling salesperson problem (TSP), fitness might be 1 / total_distance to reward shorter routes.

Example 2: In a job scheduling problem, the fitness might be the negative of total idle machine time - lower idle time means higher fitness.

Selection

Selection determines which individuals are chosen to reproduce, usually favoring those with higher fitness. However, occasional selection of lower-fitness individuals preserves diversity and avoids local optima.

Example 1: Tournament selection picks the best from a randomly chosen group (e.g. 2 out of 5).

Example 2: Roulette wheel selection gives each individual a slice of a “probability wheel” proportional to its fitness.

Crossover

Crossover creates offspring by combining parts of two parent solutions. It allows genetic material from both parents to influence the next generation, promoting innovation and recombination of good traits.

Example 1: In one-point crossover, two routes like [0,1,2,3,4] and [4,3,2,1,0] might combine at index 2 into [0,1,2,1,0].

Example 2: In uniform crossover, each gene is chosen randomly from either parent, creating a new mix per gene position.

Mutation

Mutation introduces random changes to individuals. It ensures that the population continues to explore new parts of the solution space, helping prevent stagnation and local optima traps.

Example 1: In a route [0,1,2,3,4], swapping two cities (e.g. 1 and 4) gives [0,4,2,3,1].

Example 2: In a binary string [1,0,1,1,0], flipping a bit (e.g. bit 1 becomes 1) gives [1,1,1,1,0].

Evaluation

After reproduction, each new individual is evaluated to measure its performance using the fitness function. This step helps identify which solutions are improving and should be carried forward.

Example 1: In TSP, the total distance of each new route is calculated after mutation and crossover.

Example 2: In a genetic algorithm optimizing equations, each solution’s result is plugged into the function to measure its accuracy.

Termination

Termination defines when the algorithm stops evolving. It may stop after a fixed number of generations, after reaching a performance threshold, or when progress stalls.

Example 1: Stop after 100 generations regardless of fitness.

Example 2: Stop if the best solution hasn't improved for 20 generations.

Case Studies

Route Planning

Genetic algorithms are commonly applied in logistics to solve the Travelling Salesperson Problem (TSP): find the shortest route that visits each city exactly once and returns to the start. The search space grows extremely fast as cities increase, so GAs evolve good routes rather than exhaustively checking all of them.

Population

A population is a set of candidate routes (permutations of cities). A diverse start increases the chance of finding high-quality regions in the search space. Example: for 5 cities, a route might be [0, 3, 1, 4, 2].

Fitness Function

Fitness = total route distance (shorter is better). Fitter routes are more likely to pass their “genes” (city ordering) to the next generation. Example: 350 km is fitter than 410 km.

Selection

Prefer better routes as parents, but keep some variety to avoid getting stuck early. Example: Tournament selection-pick a few routes at random; choose the shortest as a parent.

Crossover

Combine parents to form a child route while keeping cities unique. Example: With order crossover, Parent A [0,1,2,3,4], Parent B [4,3,2,1,0] → Child might be [4,1,2,3,0].

Mutation

Small random changes (e.g. swap two cities) inject fresh possibilities and reduce premature convergence. Example: Swap 2 and 4 in [0,1,2,3,4] → [0,1,4,3,2].

Evaluation

After crossover/mutation, re-measure route length; keep the better ones for the next generation.

Termination

Stop after a fixed number of generations or if the best distance hasn’t improved recently. Example: No improvement in 30 generations → return current best route.

Outcome: Over many generations, the GA evolves an efficient delivery route-cutting cost, time, and emissions for fleets with dozens or hundreds of stops.

Job Shop Scheduling

In manufacturing and services, genetic algorithms help assign jobs to machines and order them to minimise total completion time (makespan) while avoiding conflicts. The problem quickly becomes complex as jobs/machines grow.

Population

Each individual encodes a possible schedule (a sequence of job steps on machines). Diversity lets the GA explore different strategies. Example: For jobs A–D on 2 machines: [A1, B1, C2, A2, D1, B2, C1, D2].

Fitness Function

Evaluate schedules by makespan and utilisation; shorter time and fewer idle gaps are fitter. Example: 8 hours is fitter than 10 hours (if both respect constraints).

Selection

Prefer faster schedules as parents, but keep some weaker ones to preserve diversity. Example: Roulette wheel-shorter makespan → higher chance to be picked.

Crossover

Mix parent schedules while preserving job order constraints to form valid offspring. Example: Precedence-preserving crossover can combine patterns like [A,B,C,D] and [D,C,A,B] → [A,B,D,C].

Mutation

Small changes (swap/move a job step) can unlock better timing and reduce machine idle periods. Example: [A1, B2, C1, D2] → swap B and C → [A1, C2, B1, D2].

Evaluation

Re-check feasibility (no machine conflicts) and recompute makespan; keep valid, high-performing schedules.

Termination

Stop after a set number of generations, after reaching a target makespan, or when improvements plateau. Example: Best schedule unchanged for 50 generations → stop and return it.

Outcome: Iterative evolution yields efficient production schedules: lower makespan, less idle time, and better utilisation-vital for meeting deadlines and controlling costs.

Python Example: Genetic Algorithm

Scenario: Solving the "Travelling Salesperson Problem" (TSP) using a genetic algorithm. This version includes progress updates and final results.

            import numpy as np

            import random

            # Fitness function

            def fitness(route, distances):

                return sum(distances[route[i], route[i+1]] for i in range(len(route)-1)) + distances[route[-1], route[0]]

            # Create initial population

            def create_population(size, num_cities):

                print(f"Creating initial population of {size} routes...")

                return [random.sample(range(num_cities), num_cities) for _ in range(size)]

            # Crossover function

            def crossover(parent1, parent2):

                cut = random.randint(0, len(parent1) - 1)

                child = parent1[:cut] + [gene for gene in parent2 if gene not in parent1[:cut]]

                return child

            # Mutation function

            def mutate(route):

                idx1, idx2 = random.sample(range(len(route)), 2)

                route[idx1], route[idx2] = route[idx2], route[idx1]

            # Evolve population

            def evolve_population(population, distances, mutation_rate=0.1):

                population = sorted(population, key=lambda x: fitness(x, distances))

                best_fitness = fitness(population[0], distances)

                print(f"Best fitness in generation: {best_fitness}")

                new_population = [population[0]]

                for _ in range(len(population) - 1):

                    parent1, parent2 = random.sample(population[:10], 2)

                    child = crossover(parent1, parent2)

                    if random.random() < mutation_rate:

                        mutate(child)

                    new_population.append(child)

                return new_population

            # Parameters

            num_cities = 5

            population_size = 10

            generations = 20

            # Create symmetric distance matrix

            distances = np.random.randint(10, 100, (num_cities, num_cities))

            distances = (distances + distances.T) // 2

            np.fill_diagonal(distances, 0)

            print("City Distance Matrix:\n", distances)

            population = create_population(population_size, num_cities)

            print("\nStarting evolution...\n")

            for generation in range(generations):

                print(f"--- Generation {generation + 1} ---")

                population = evolve_population(population, distances)

            best_route = population[0]

            print("\nBest Route Found:", best_route)

            print("Total Distance:", fitness(best_route, distances))

Run this script a few times ... do you get the same route every time?

Other Real-World Applications of Genetic Algorithms

Genetic algorithms are useful when the search space is large, and traditional approaches are too slow or fail to find good enough solutions.

Route Optimisation: In logistics, GAs are used to minimise travel distances or costs - e.g. planning delivery paths for trucks or couriers.
Portfolio Management: In finance, GAs help select asset combinations that balance risk and return more effectively.
Engineering Design: Optimising shapes, layouts, or materials to meet design constraints (e.g. weight vs. strength).

Challenges of Genetic Algorithms

Performance Cost: GAs often need many generations and evaluations to find good results.
Convergence: Populations can get stuck in suboptimal solutions (local minima).
Parameter Tuning: Mutation rate, population size, and selection method all need to be chosen carefully.

Key Takeaways

Genetic Algorithms mimic natural evolution to solve complex optimisation problems.
Key steps include selection, crossover, mutation, evaluation, and termination.
They are effective in areas like logistics, engineering, finance, and AI training.
They work best when traditional methods are too slow or fail in large or complex solution spaces.