# How to Implement Genetic Algorithms for Optimization Problems in Python

> Implement genetic algorithms for optimization problems in Python with the AI-For-Beginners repository. Explore binary/permutation encodings, fitness functions, and selection strategies for combinatorial problems.

- Repository: [Microsoft/AI-For-Beginners](https://github.com/microsoft/AI-For-Beginners)
- Tags: how-to-guide
- Published: 2026-08-08

---

**The `Genetic.ipynb` notebook in Microsoft's AI-For-Beginners repository demonstrates a complete genetic algorithm workflow using binary and permutation encodings, modular fitness functions, and configurable selection strategies to solve combinatorial optimization problems.**

Implementing genetic algorithms for optimization problems requires a structured pipeline of encoding, evaluation, and evolutionary operations. The `microsoft/AI-For-Beginners` repository provides a comprehensive reference implementation in `lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb` that solves both the "fair treasure split" and N-Queens problems through reusable components. This guide breaks down the notebook's architecture so you can adapt its modular design to custom optimization challenges.

## Genetic Algorithm Pipeline Overview

The implementation follows the classic five-step genetic algorithm workflow. According to the source code in `Genetic.ipynb`, the pipeline consists of **encoding** (genes), **fitness evaluation**, **selection**, **genetic operators** (mutation and crossover), and the **evolution loop**. The notebook provides two distinct tracks: one using binary vectors for subset-based problems and another using permutations for ordering problems.

## Encoding Solutions as Genes

### Binary Encoding for Combinatorial Problems

For subset optimization problems like the fair treasure split, solutions are encoded as binary vectors where each gene represents inclusion (`1`) or exclusion (`0`). The `generate` function creates random initial populations:

```python
def generate(S):
    return np.array([random.randint(0,1) for _ in S])

```

### Permutation Encoding for Ordering Problems

For sequencing challenges like the N-Queens problem, the notebook uses permutation encoding via the `generate_one` function. Here, each gene represents a position in a sequence (e.g., a queen's column in a specific row), ensuring no duplicate values exist within a single chromosome.

## Fitness Evaluation Functions

### Minimizing Subset Difference

The treasure split problem uses the `fit` function to calculate the absolute difference between two subsets. Lower values indicate fairer splits:

```python
def fit(B, S=S):
    c1 = (B*S).sum()
    c2 = ((1-B)*S).sum()
    return abs(c1-c2)

```

### Counting Attacking Queens

For the N-Queens problem, the `fit` function counts pairs of queens attacking each other horizontally or diagonally. A fitness of `0` indicates a valid solution:

```python
def fit(L):
    x = 0
    for i1, j1 in enumerate(L, 1):
        for i2, j2 in enumerate(L, 1):
            if i2 > i1:
                if j2 == j1 or abs(j2 - j1) == i2 - i1:
                    x += 1
    return x

```

## Core Genetic Operators

### Mutation Operators

The notebook implements problem-specific mutation strategies. For binary chromosomes, the `mutate` function performs bit-flipping:

```python
def mutate(b):
    x = b.copy()
    i = random.randint(0, len(b)-1)
    x[i] = 1 - x[i]
    return x

```

For permutations, mutation replaces a queen's column with a random valid position:

```python
def mutate(G):
    x = random.randint(0, len(G)-1)
    G[x] = random.randint(1, len(G))
    return G

```

### Crossover Strategies

Binary crossover uses a random mask generated by the `generate` function to mix parent genes:

```python
def xover(b1, b2):
    mask = generate(b1)
    return b1*mask + b2*(1-mask)

```

Permutation crossover cuts two parent lists at a random index and concatenates the segments:

```python
def xover(G1, G2):
    x = random.randint(0, len(G1))
    return np.concatenate((G1[:x], G2[x:]))

```

## Parent Selection Mechanisms

### Roulette-Wheel Selection (`choose_rand`)

This probabilistic approach samples parents proportionally to their inverse fitness values. Solutions with better fitness scores receive higher selection probability, but low-fitness individuals still have a chance to contribute genetic material.

### Tournament Selection (`choose`)

The deterministic tournament method implemented in the notebook repeatedly draws a random threshold and selects the first chromosome whose normalized fitness exceeds it. This approach applies stronger selection pressure than roulette-wheel, favoring elite solutions more aggressively.

## Executing the Evolution Loop

The `evolve` function manages the binary genetic algorithm, while `genetic` handles permutations. Both implement a generational loop that continues until finding a solution with fitness `0` or reaching a generation limit. The binary version uses a 30/70 mutation-to-crossover ratio and replaces the worst-performing individuals:

```python
def evolve(P, S=S, n=2000):
    res = []
    for _ in range(n):
        f = min([fit(b) for b in P])
        res.append(f)
        if f == 0:
            break
        if random.randint(1, 10) < 3:      # 30% mutation

            i = random.randint(0, len(P)-1)
            b = mutate(P[i])
            worst = np.argmax([fit(z) for z in P])
            P[worst] = b
        else:                               # 70% crossover

            i, j = random.randint(0, len(P)-1), random.randint(0, len(P)-1)
            b = xover(P[i], P[j])
            if fit(b) < fit(P[i]):
                P[i] = b
            elif fit(b) < fit(P[j]):
                P[j] = b
    best = np.argmin([fit(b) for b in P])
    return P[best], res

```

The implementation also includes **population management** strategies such as discarding the least-fit fraction, injecting random newcomers to maintain diversity, and preserving the best individuals across generations. Performance measurement using `%timeit` demonstrates the computational efficiency of each approach.

## Summary

- The `Genetic.ipynb` notebook provides a modular framework for implementing genetic algorithms for optimization problems with minimal boilerplate code.
- **Binary encoding** via `generate` suits subset selection problems, while **permutation encoding** via `generate_one` handles ordering constraints.
- The `fit` function serves as the primary customization point, requiring only a scalar return value where lower is better.
- **Selection strategies** include probabilistic roulette-wheel (`choose_rand`) and deterministic tournament (`choose`) methods.
- The `evolve` and `genetic` functions handle the main optimization loop with built-in elitism, diversity injection, and adaptive operator probabilities.

## Frequently Asked Questions

### What types of optimization problems work best with this implementation?

This implementation excels at **discrete and combinatorial optimization** problems where solutions can be represented as fixed-length vectors or permutations. The notebook specifically demonstrates the "fair treasure split" (subset sum) and N-Queens (constraint satisfaction) problems, but the architecture supports scheduling, routing, and resource allocation problems by modifying the fitness function and encoding scheme.

### How do I adapt the code for a new optimization problem?

To adapt the notebook to a new problem, define a custom `fit` function that quantifies solution quality as a scalar value (minimization objective). Then select the appropriate encoding: use the binary `generate` function for yes/no decisions or permutation `generate_one` for sequencing tasks. The mutation, crossover, and selection operators remain reusable across problem domains.

### What is the difference between the `evolve` and `genetic` functions?

The `evolve` function in `Genetic.ipynb` specializes in **binary chromosome optimization**, handling bit-flip mutations and mask-based crossover with a 30/70 mutation-to-crossover probability split. The `genetic` function manages **permutation-based problems**, ensuring offspring remain valid permutations through specialized crossover and mutation operators that preserve uniqueness constraints.

### Why does the binary implementation use a 30% mutation rate versus 70% crossover?

The 30/70 split reflects a balance between **exploration** (mutation introducing new genetic material) and **exploitation** (crossover combining existing high-fitness traits). As implemented in the source code, this ratio prioritizes recombination of successful parent solutions while maintaining sufficient random perturbation to escape local optima in the treasure split problem's fitness landscape.