# Using Genetic Algorithms for Optimization Problems in the AI-For-Beginners Curriculum

> Learn to solve optimization problems using genetic algorithms with the AI-For-Beginners curriculum. Explore interactive Jupyter notebooks implementing selection, crossover, and mutation.

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

---

**The AI-For-Beginners curriculum teaches genetic algorithms through interactive Jupyter notebooks that implement selection, crossover, and mutation to solve optimization problems like the fair treasure split and Diophantine equations.**

The microsoft/AI-For-Beginners repository includes a dedicated lesson on evolutionary computation located at `lessons/6-Other/21-GeneticAlgorithms`. This module demonstrates how to apply genetic algorithms for optimization problems using pure Python and NumPy, bridging the conceptual foundation from the introductory chapter to hands-on implementations that precede deep reinforcement learning content.

## Where Genetic Algorithms Fit in the Curriculum

According to the source code structure, the genetic algorithms material resides in the **6-Other** lesson series, specifically following the evolutionary approach concepts mentioned in [`lessons/1-Intro/README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/lessons/1-Intro/README.md). The lesson precedes the deep reinforcement learning content found in `lessons/6-Other/22-DeepRL`, creating a logical progression from population-based search methods to advanced agent-based AI.

The curriculum provides three main resources for this topic:

- [`README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/README.md) – Conceptual overview of GA steps and exercise pointers
- `Genetic.ipynb` – Interactive implementations for classic problems
- `Diophantine.ipynb` – Assignment notebook for equation solving

## Core GA Components in the Source Code

The implementation in `Genetic.ipynb` follows the standard evolutionary workflow with five key components that operate on a population of candidate solutions.

### Gene Representation and Initialization

Candidate solutions are encoded as vectors. For partition problems like the treasure split, the `generate(S)` function creates random binary vectors matching the length of the input set:

```python
def generate(S):
    """Create a random binary vector of the same length as S."""
    return np.array([random.randint(0, 1) for _ in S])

```

### Fitness Function Design

The optimizer seeks to **minimize** fitness values. The `fit(B, S)` function calculates the absolute difference between partition sums, quantifying how unfair a treasure split is:

```python
def fit(B, S):
    """Compute the cost of a partition encoded by B."""
    sum1 = (B * S).sum()
    sum2 = ((1 - B) * S).sum()
    return abs(sum1 - sum2)

```

### Crossover and Mutation Operators

The `xover(b1, b2)` function blends parent genes using a random mask, while `mutate(b)` introduces diversity by flipping random bits to escape local minima:

```python
def xover(b1, b2):
    """Combine two parents using a random mask generated by `generate`."""
    mask = generate(b1)
    return b1 * mask + b2 * (1 - mask)

def mutate(b):
    """Flip one random bit in the binary gene."""
    x = b.copy()
    i = random.randint(0, len(b) - 1)
    x[i] = 1 - x[i]
    return x

```

### The Evolution Loop

The `evolve()` function orchestrates selection, breeding, and replacement using elitism (keeping the best individual) and generational turnover:

```python
def evolve(pop_size, generations, S):
    # Initialise population

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

    for gen in range(generations):
        # Evaluate fitness of current population

        fitnesses = [fit(ind, S) for ind in pop]
        # Select the best individuals (elitism)

        best_idx = np.argmin(fitnesses)
        best = pop[best_idx]

        # Create new offspring

        parent1, parent2 = random.sample(pop, 2)
        child = xover(parent1, parent2)
        child = mutate(child)

        # Replace the worst individual with the new child

        worst_idx = np.argmax(fitnesses)
        pop[worst_idx] = child

        # Optional: stop early if fitness is zero

        if fit(best, S) == 0:
            break

    return best, fit(best, S)

```

## Practical Optimization Examples

The notebooks demonstrate how to adapt the genetic algorithm framework for different problem domains.

### The Fair Treasure Split Problem

The `Genetic.ipynb` notebook implements a **partition problem** where the goal is dividing treasure values equally between two parties. The fitness function minimizes the absolute difference between subset sums, converging toward a difference of zero that represents a perfectly fair split.

### The Diophantine Equation Assignment

The `Diophantine.ipynb` notebook adapts the genetic algorithm for solving equations of the form `a + 2b + 3c + 4d = 30`. Learners modify the gene representation from binary vectors to integer lists and redefine the fitness function to minimize the absolute error `|a + 2b + 3c + 4d - 30|`.

## Integration with Other AI Techniques

The genetic algorithms lesson serves as foundational material for understanding optimization before advancing to `lessons/6-Other/22-DeepRL`. While deep reinforcement learning uses gradient-based methods, the GA module introduces population-based search strategies that complement the curriculum's coverage of evolutionary approaches.

## Summary

- The genetic algorithms module in `lessons/6-Other/21-GeneticAlgorithms` provides hands-on optimization experience using only the standard Python scientific stack (`numpy`, `random`, `matplotlib`).
- **Core functions** (`generate`, `fit`, `mutate`, `xover`) implement the essential evolutionary operators: initialization, fitness evaluation, mutation, and crossover.
- The **fair treasure split** and **Diophantine equation** examples demonstrate how to encode different problem types as genes and define appropriate fitness landscapes.
- The curriculum deliberately keeps implementations in single notebooks to focus on algorithmic understanding rather than software engineering complexity.

## Frequently Asked Questions

### What files contain the genetic algorithm implementations?

The primary implementation files are `lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb` for the treasure split and 8-Queens problems, and `lessons/6-Other/21-GeneticAlgorithms/Diophantine.ipynb` for the equation solving assignment. The conceptual overview resides in [`README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/README.md) within the same directory.

### How does the fitness function work in the treasure split example?

The `fit(B, S)` function computes the absolute difference between the sums of two partitions encoded by binary vector `B`. The algorithm minimizes this value, seeking a difference of zero that represents a perfectly fair split of the treasure values contained in array `S`.

### Can I adapt the code for non-binary optimization problems?

Yes. The `Diophantine.ipynb` assignment requires adapting the gene representation from binary vectors to integer lists. You must redefine the `generate()` function to produce random integers and modify the fitness function to calculate error for your specific equation or constraint satisfaction problem.

### Where does this lesson fit in the overall curriculum?

This lesson bridges the evolutionary approach introduced in [`lessons/1-Intro/README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/lessons/1-Intro/README.md) and the deep reinforcement learning material in `lessons/6-Other/22-DeepRL`. It provides practical optimization experience before learners encounter more complex agent training methodologies.