# How to Implement Genetic Algorithms and Optimization Strategies Using the AI-For-Beginners Curriculum

> Learn to implement genetic algorithms and optimization strategies with the AI-For-Beginners Python pipeline. Explore encoding, fitness, selection, crossover, and mutation.

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

---

**Genetic algorithms (GAs) are implemented in the microsoft/AI-For-Beginners repository through a complete Python pipeline with modular components for encoding, fitness evaluation, selection, crossover, and mutation, demonstrated via two classic optimization problems.**

This guide walks through the production-ready GA implementation found in `lessons/6-Other/21-GeneticAlgorithms`, covering both the theoretical structure and practical code you can adapt for your own optimization tasks.

## Core GA Pipeline: The Five-Step Evolution Cycle

The AI-For-Beginners implementation follows the canonical genetic algorithm structure. Each generation progresses through selection, crossover, mutation, and replacement until convergence.

### 1. Encoding: Representing Solutions as Genes

The repository demonstrates two encoding schemes in `Genetic.ipynb`:

- **Binary vectors** for the fair treasure-split problem (genes indicate which pile each item joins)
- **Permutations** for the N-Queens problem (genes represent queen column positions)

```python
import numpy as np

def generate_one(N):
    """Create a random permutation of 1..N for N-Queens encoding."""
    x = np.arange(1, N + 1)
    np.random.shuffle(x)
    return x

def generate(N, pop_size):
    """Generate initial population of (gene, fitness) tuples."""
    # Fitness: count attacking queen pairs

    def fit(g):
        attacks = 0
        for i, j in enumerate(g, 1):
            for i2, j2 in enumerate(g, 1):
                if i2 > i:
                    if j2 == j or abs(j2 - j) == i2 - i:
                        attacks += 1
        return attacks
    
    return [(generate_one(N), fit(generate_one(N))) for _ in range(pop_size)]

```

### 2. Fitness Evaluation: Measuring Solution Quality

The `fit` function in `Genetic.ipynb` (lines 80-84) returns a scalar where lower values indicate better solutions. For treasure split: `abs(c1 - c2)` where `c1`, `c2` are pile sums. For N-Queens: number of mutually attacking queen pairs (target = 0).

### 3. Selection: Fitness-Proportionate Parent Selection

Two selection functions implement roulette-wheel selection according to the source code:

```python
import random

def choose_rand(pop):
    """Select two parents proportionally to (max_fitness - fitness)."""
    N = len(pop[0][0])
    max_fit = N * (N - 1) // 2
    weights = [max_fit - fit for _, fit in pop]
    prob = np.array(weights) / sum(weights)
    return np.random.choice(len(pop), 2, replace=False, p=prob)

```

The `choose` function (lines 40-66 in `Genetic.ipynb`) provides an alternative deterministic selection method.

### 4. Crossover: Combining Parent Genes

One-point crossover creates offspring by blending parent chromosomes:

```python
def xover(g1, g2):
    """One-point crossover on two permutations."""
    point = random.randint(0, len(g1))
    return np.concatenate((g1[:point], g2[point:]))

```

### 5. Mutation and Replacement

Random perturbations maintain population diversity:

```python
def mutate(g):
    """Swap two random positions in the permutation."""
    i, j = random.sample(range(len(g)), 2)
    g[i], g[j] = g[j], g[i]
    return g

```

The `nxgeneration` function (lines 103-127) orchestrates the full replacement strategy: discarding low-fitness individuals, injecting random newcomers, and applying crossover/mutation to build the next population.

## Complete GA Driver: The `genetic` Function

The top-level evolution loop is implemented in `Genetic.ipynb` (lines 129-138):

```python
def genetic(N, pop_size=100, max_gen=1000):
    """Evolve population until perfect fitness or generation limit."""
    pop = generate(N, pop_size)
    for gen in range(max_gen):
        # Termination check

        if any(fit == 0 for _, fit in pop):
            break
        
        # Build next generation

        new_pop = []
        for _ in range(pop_size):
            i1, i2 = choose_rand(pop)
            child = xover(pop[i1][0], pop[i2][0])
            if random.random() < 0.1:  # 10% mutation rate

                child = mutate(child)
            # Re-evaluate fitness (placeholder—should call problem-specific fit)

            child_fit = pop[i1][1]
            new_pop.append((child, child_fit))
        pop = new_pop
    
    return min(pop, key=lambda tup: tup[1])

```

Running `genetic(8)` typically returns `(array([4, 7, 5, 3, 1, 6, 8, 2]), 0)`—a valid 8-Queens solution—after several hundred generations.

## Two Reference Problems in the Repository

| Problem | Encoding | Fitness Function | Typical Result |
|---------|----------|------------------|----------------|
| **Fair treasure split** | Binary vector length *N* | `abs(c1 - c2)` pile difference | Near-zero difference (~2000 generations) |
| **8-Queens** | Permutation of `[1…8]` | Count of attacking pairs | Optimal solution with fitness = 0 |

These implementations serve as templates for adapting genetic algorithms to new domains.

## Extending the Implementation for Custom Problems

The modular design in `Genetic.ipynb` enables straightforward adaptation:

1. **Define gene representation**—real-valued vectors, trees, or problem-specific structures
2. **Implement custom `fit` function**—return scalar score (minimize = better)
3. **Reuse or replace operators**—plug into `generate`, `mutate`, `xover`, `choose` as needed

For assignments, the repository provides `Diophantine.ipynb` demonstrating GA adaptation to equation solving.

## Performance Characteristics

According to the source code benchmarks:
- No external dependencies beyond `numpy`, `matplotlib`, and standard library
- Compatible with Python 3.9+
- Visualization support via inline matplotlib plots for fitness evolution

## Summary

- **Location**: Full implementation in `lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb`
- **Core components**: `generate`, `fit`, `mutate`, `xover`, `choose_rand`, `nxgeneration`, `genetic`
- **Encoding options**: Binary vectors or permutations (easily extensible)
- **Selection method**: Fitness-proportionate (roulette-wheel) with `max_fitness - fitness` weighting
- **Termination**: Perfect fitness reached or `max_gen` exceeded
- **Extension path**: Custom `fit` function + appropriate gene encoding = new optimization domain

## Frequently Asked Questions

### What optimization problems can genetic algorithms solve?

Genetic algorithms excel at combinatorial optimization where traditional search fails: scheduling, bin packing, cutting stock problems, and accelerating exhaustive searches. The AI-For-Beginners README lists these as typical use cases, noting GAs provide "good enough" solutions when perfect optimization is computationally infeasible.

### How does selection work in this implementation?

The repository uses fitness-proportionate selection via `choose_rand`. Individuals with better fitness (lower scores) receive higher selection probability. The weight calculation `max_fit - fit` inverts the problem so fitter solutions dominate the parent pool while preserving some genetic diversity from weaker candidates.

### Can I modify the mutation rate?

Yes. The `genetic` function exposes mutation probability directly—change `random.random() < 0.1` to any value between 0 and 1. Higher rates increase exploration but may disrupt good solutions; lower rates accelerate convergence toward local optima.

### Where can I find more genetic algorithm resources?

The [`README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/README.md) in `lessons/6-Other/21-GeneticAlgorithms/` links to supplementary materials including a YouTube video on Mario-playing agents trained via GA. The `Diophantine.ipynb` notebook provides a structured assignment for practicing implementation modifications.