How to Implement Genetic Algorithms for Optimization Problems: From Theory to Python Code

Genetic algorithms optimize solutions by evolving a population of candidate genes through selection, crossover, and mutation operators until the fitness function converges to an optimal value.

The microsoft/AI-For-Beginners curriculum provides a practical framework for building these evolutionary algorithms from scratch. In lesson 6, you will learn how to implement genetic algorithms for optimization problems using pure Python and NumPy, with concrete implementations covering binary and permutation encodings.

Core Concepts of Genetic Algorithms

A genetic algorithm (GA) is an evolutionary search heuristic that mimics natural selection. According to the source code in lessons/6-Other/21-GeneticAlgorithms/README.md, the algorithm maintains a population of candidate solutions called genes, iteratively improving them through three core operators.

Population and Genes

The algorithm starts by initializing a random population. Each individual, or gene, represents a potential solution encoded as a data structure appropriate for the problem—such as a binary vector for subset selection or a permutation for ordering problems.

Fitness Function

Every gene is evaluated by a fitness function that returns a scalar value indicating solution quality. Lower values typically represent better solutions (minimization), though the logic can be inverted for maximization problems. The fitness score drives the selection process.

Evolutionary Operators

The GA progresses by repeatedly applying these operators:

• Selection: Probabilistically choosing parents based on fitness (e.g., roulette-wheel selection where higher fitness increases selection probability).
• Crossover: Combining two parent genes to create offspring. The repository implements this via xover using a random mask: child = parent1 * mask + parent2 * (1 - mask).
• Mutation: Introducing random variation to escape local optima. The mutate function typically flips a random bit or swaps elements to maintain genetic diversity.

Step-by-Step Implementation

The evolutionary loop follows a standardized pipeline implemented in Genetic.ipynb. The core logic alternates between mutation and crossover paths based on a probability threshold:

def evolve(population, steps):
    for _ in range(steps):
        fitnesses = [fit(gene) for gene in population]
        
        # Termination condition

        if min(fitnesses) == 0:
            break
            
        if random.random() < mutation_prob:
            # Mutation path: modify random individual, replace worst

            i = random.randrange(len(population))
            mutated = mutate(population[i])
            worst = np.argmax(fitnesses)
            population[worst] = mutated
        else:
            # Crossover path: combine two parents, keep if better

            i, j = random.sample(range(len(population)), 2)
            child = xover(population[i], population[j])
            if fit(child) < min(fitnesses[i], fitnesses[j]):
                population[i if fitnesses[i] > fitnesses[j] else j] = child
                
    return min(population, key=fit)

This structure initializes the population, evaluates fitness, applies genetic operators, and replaces low-fitness members with offspring until reaching a termination condition—either finding a perfect solution (fitness equals zero) or exceeding the maximum generation count.

Complete Code Examples

The Genetic.ipynb notebook provides two fully functional implementations demonstrating different encoding strategies.

Example 1: Fair Treasure Split (Binary Encoding)

This example uses a binary vector to partition a set of treasures into two piles with equal sums. Each gene is a mask where 1 and 0 represent assignment to different piles.

import numpy as np
import random

N = 200
S = np.array([random.randint(1, 10_000) for _ in range(N)])

def generate(S):
    """Random binary mask indicating pile assignment."""
    return np.array([random.randint(0, 1) for _ in S])

def fit(mask, S=S):
    """Absolute difference between pile sums."""
    left = (mask * S).sum()
    right = ((1 - mask) * S).sum()
    return abs(left - right)

def mutate(mask):
    """Flip a random bit."""
    mutated = mask.copy()
    i = random.randint(0, len(mask) - 1)
    mutated[i] = 1 - mutated[i]
    return mutated

def xover(m1, m2):
    """Random crossover mask."""
    mask = generate(m1)
    return m1 * mask + m2 * (1 - mask)

# GA execution

pop_size = 30
population = [generate(S) for _ in range(pop_size)]

def evolve(pop, steps=2000):
    history = []
    for _ in range(steps):
        best = min(fit(ind) for ind in pop)
        history.append(best)
        if best == 0:
            break
        if random.random() < 0.3:  # Mutation probability

            i = random.randrange(len(pop))
            pop[i] = mutate(pop[i])
        else:
            i, j = random.sample(range(len(pop)), 2)
            child = xover(pop[i], pop[j])
            if fit(child) < min(fit(pop[i]), fit(pop[j])):
                pop[i] = child
    return min(pop, key=fit), history

solution, history = evolve(population)
print("Best fitness:", fit(solution))

Example 2: N-Queens Puzzle (Permutation Encoding)

The N-Queens problem requires placing queens on a chessboard such that none attack each other. This implementation uses a permutation encoding where the array index represents the row and the value represents the column, ensuring exactly one queen per row and column by construction.

import numpy as np
import random

def fitness(board):
    """Count pairs of queens that attack each other."""
    attacks = 0
    for i, col_i in enumerate(board, start=1):
        for j, col_j in enumerate(board, start=1):
            if j > i:
                if col_i == col_j or abs(col_i - col_j) == j - i:
                    attacks += 1
    return attacks

def generate_one(N):
    """Random permutation of columns 1..N."""
    perm = np.arange(1, N + 1)
    np.random.shuffle(perm)
    return perm, fitness(perm)

def crossover(p1, p2):
    """Single-point crossover preserving permutation validity."""
    cut = random.randint(0, len(p1))
    child = np.concatenate((p1[:cut], p2[cut:]))
    # Fix duplicates by filling missing numbers

    missing = [x for x in range(1, len(p1) + 1) if x not in child]
    for i, val in enumerate(child):
        if child[i] in child[:i]:
            child[i] = missing.pop(0)
    return child

def mutate(board):
    """Swap two random positions."""
    a, b = random.sample(range(len(board)), 2)
    board[a], board[b] = board[b], board[a]
    return board

def genetic_queens(N, pop_size=100, max_gen=500):
    pop = [generate_one(N) for _ in range(pop_size)]
    for gen in range(max_gen):
        fitnesses = np.array([fit for _, fit in pop])
        # Fitness-proportional selection (lower fitness = higher probability)

        probs = (fitnesses.max() - fitnesses) / (fitnesses.max() - fitnesses.min())
        probs /= probs.sum()
        parents = np.random.choice(len(pop), size=2, replace=False, p=probs)
        
        child = crossover(pop[parents[0]][0], pop[parents[1]][0])
        if random.random() < 0.1:
            child = mutate(child)
            
        child_fit = fitness(child)
        # Replace worst individual

        worst = max(range(len(pop)), key=lambda i: pop[i][1])
        pop[worst] = (child, child_fit)
        
        if child_fit == 0:
            return child
    return None

solution = genetic_queens(8)
print("Solution board (column positions):", solution)

Key Files in the Repository

File	Purpose
lessons/6-Other/21-GeneticAlgorithms/README.md	Conceptual overview, biological terminology, and algorithm pseudocode.
lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb	Complete Jupyter notebook containing the treasure split and N-Queens implementations with visualization code.
lessons/6-Other/21-GeneticAlgorithms/Diophantine.ipynb	Practice assignment applying GA techniques to solve Diophantine equations.

Summary

• Genetic algorithms require three components: a population of encoded solutions, a fitness evaluation metric, and evolutionary operators (selection, crossover, mutation).
• The binary encoding in the fair treasure split example demonstrates how to handle subset optimization problems using bit-flip mutation and mask-based crossover.
• The permutation encoding in the N-Queens solution illustrates constraint satisfaction via valid-permutation preservation and swap mutation.
• Always implement elitism or replacement strategies (such as replacing the worst individual) to ensure population quality improves over generations.
• The evolve function structure from Genetic.ipynb provides a reusable template for any combinatorial optimization where exhaustive search is infeasible.

Frequently Asked Questions

What is the difference between crossover and mutation in genetic algorithms?

Crossover combines genetic material from two parent solutions to create offspring, exploiting known good regions of the search space, while mutation introduces random changes to a single individual to maintain diversity and escape local optima. In the microsoft/AI-For-Beginners implementation, crossover occurs with probability 0.7 and mutation with probability 0.3.

How do I choose the right fitness function for my optimization problem?

The fitness function must quantitatively measure how close a solution is to the objective, returning lower values for better solutions (in minimization contexts). For the treasure split problem, fitness is the absolute difference between pile sums; for N-Queens, it counts attacking queen pairs. The function should be computationally efficient since it runs once per gene per generation.

Why does the N-Queens example use permutation encoding instead of binary?

Permutation encoding ensures exactly one queen occupies each row and column by construction, drastically reducing the search space from all possible board configurations to valid permutations only. This encoding requires specialized crossover operators that fix duplicate values to maintain permutation validity, as implemented in the crossover function.

What termination conditions should I use for the evolutionary loop?

Common termination criteria include reaching a maximum generation count, finding a solution with zero fitness (perfect solution), or observing that the population's best fitness has not improved for a specified number of generations. The treasure split example checks if best == 0 to stop immediately upon finding an exact split.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}