# How Genetic Algorithms Solve Diophantine Equations in Genetic.ipynb from Microsoft AI-For-Beginners

> Learn how genetic algorithms solve Diophantine equations by evolving integer vectors through selection, crossover, and mutation until a solution is found.

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

---

**Genetic algorithms solve Diophantine equations by evolving integer vectors through selection, crossover, and mutation until a candidate's fitness—the absolute difference between the equation's left-hand side and target value—reaches zero.**

The Microsoft AI-For-Beginners repository (`microsoft/AI-For-Beginners`) provides a complete, reusable genetic algorithm implementation in `Genetic.ipynb` that demonstrates this optimization technique. The notebook frames Diophantine solving as an evolutionary search problem where integer solutions emerge from successive generations of candidate vectors.

## Encoding Integer Solutions as Genes

Each candidate solution is encoded as a fixed-length integer vector **g** ∈ ℕᴺ. For the classic example equation `a + 2b + 3c + 4d = 30`, the gene representation is straightforward:

```python
g = [a, b, c, d]  # each element is an integer in [0, 30]

```

The encoding decouples the search mechanism from the specific equation, making the GA generic. `lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb` uses `numpy` arrays for vectorized operations.

## Defining the Fitness Function for Diophantine Equations

The fitness function measures how close a gene is to satisfying the target equation. According to the source code in `Genetic.ipynb`:

```python
def fit(g, coeffs=np.array([1, 2, 3, 4]), target=30):
    lhs = (g * coeffs).sum()
    return abs(lhs - target)          # 0 → perfect solution

```

Key properties of this fitness landscape:

- **Fitness of 0** indicates an exact Diophantine solution
- **Linear penalty** for deviation from the target
- **Vectorized computation** using `numpy` dot products

The smaller the fitness value, the closer the candidate is to solving the equation.

## Population Initialization and Evolution Loop

The GA generates an initial population of random integer vectors within feasible bounds:

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

pop = [generate(np.zeros(4)) for _ in range(pop_size)]

```

The evolution loop in `Genetic.ipynb` implements a hybrid operator strategy with 30% mutation probability and 70% crossover:

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

            i = random.randint(0, len(P) - 1)
            P[i] = mutate(P[i])
        else:                                      # 70% crossover

            i, j = random.sample(range(len(P)), 2)
            child = xover(P[i], P[j])
            if fit(child) < fit(P[i]):  P[i] = child
            elif fit(child) < fit(P[j]): P[j] = child
    return P, history

```

The loop tracks `best` fitness per generation and terminates early when a solution is found.

## Selection, Crossover, and Mutation Operators

### Selection Strategies

`Genetic.ipynb` implements two parent selection mechanisms:

- **Tournament selection** – Randomly pick two individuals, retain the fitter one
- **Fitness-proportionate selection** – Compute weights `w = (max_fit - fit) / total` and sample parents accordingly

### Crossover Operation

The `xover` function combines two parents using a random binary mask:

```python
def xover(p1, p2):
    mask = generate(p1)                # mask of 0/1 of same length

    return p1 * mask + p2 * (1 - mask)

```

This creates offspring that inherit mixed components from both parents.

### Mutation Operation

Mutation maintains diversity by randomly replacing one gene component:

```python
def mutate(g):
    i = random.randint(0, len(g) - 1)
    g[i] = random.randint(0, 30)       # keep within feasible range

    return g

```

## Complete Working Example

This runnable example from the `microsoft/AI-For-Beginners` source solves `a + 2b + 3c + 4d = 30`:

```python
import numpy as np
import random

coeffs = np.array([1, 2, 3, 4])
target = 30
pop_size = 50

def fit_gene(g):
    return abs((g * coeffs).sum() - target)

def generate_gene():
    return np.array([random.randint(0, target) for _ in coeffs])

def mutate(g):
    i = random.randint(0, len(g) - 1)
    g[i] = random.randint(0, target)
    return g

def crossover(p1, p2):
    mask = np.array([random.randint(0, 1) for _ in coeffs])
    return p1 * mask + p2 * (1 - mask)

def evolve(pop, max_gen=2000):
    history = []
    for _ in range(max_gen):
        best_fit = min(fit_gene(g) for g in pop)
        history.append(best_fit)
        if best_fit == 0:
            break
        if random.random() < 0.3:          # mutation

            i = random.randint(0, len(pop) - 1)
            pop[i] = mutate(pop[i])
        else:                               # crossover

            i, j = random.sample(range(len(pop)), 2)
            child = crossover(pop[i], pop[j])
            if fit_gene(child) < fit_gene(pop[i]): pop[i] = child
            elif fit_gene(child) < fit_gene(pop[j]): pop[j] = child
    return pop, history

# initialise and run

population = [generate_gene() for _ in range(pop_size)]
final_pop, hist = evolve(population)
best = min(final_pop, key=fit_gene)

print("Solution:", best, "fitness:", fit_gene(best))

# Typical output: Solution: [2 4 6 2] fitness: 0

# Verifies: 2 + 2*4 + 3*6 + 4*2 = 2 + 8 + 18 + 8 = 30

```

## Adapting the GA to Other Diophantine Problems

The `Genetic.ipynb` implementation is intentionally generic. To apply it to a different Diophantine equation, modify three parameters as implemented in the source:

| Parameter | Purpose | Example |
|-----------|---------|---------|
| `coeffs` | Equation coefficients | `np.array([2, 5, 3])` for `2a + 5b + 3c = N` |
| `target` | Right-hand side constant | `100` |
| Domain bounds | Feasible integer range | `[0, target]` or problem-specific limits |

The companion notebook `lessons/6-Other/21-GeneticAlgorithms/Diophantine.ipynb` provides structured exercises for this adaptation.

## Summary

- **Gene encoding**: Integer vectors represent candidate solutions to Diophantine equations
- **Fitness function**: Absolute residual `|Σ(coeffs × gene) - target|` drives selection
- **Evolutionary operators**: 30% mutation, 70% crossover with elitist insertion
- **Termination condition**: Fitness reaches zero, indicating an exact solution
- **Reusable design**: Adjust `coeffs`, `target`, and bounds for new problems

## Frequently Asked Questions

### What makes genetic algorithms suitable for Diophantine equations?

Genetic algorithms excel at discrete optimization where traditional gradient-based methods fail. Diophantine equations require integer solutions, creating a non-differentiable, combinatorial search space. The GA's population-based approach explores multiple regions simultaneously, avoiding local optima that trap hill-climbing methods.

### How does the fitness function guarantee finding exact solutions?

The fitness function `abs(lhs - target)` has a global minimum of zero reachable only by exact solutions. While the GA doesn't guarantee convergence in finite time, the elitist replacement strategy—only accepting offspring that improve parent fitness—ensures the population never degrades. Early termination on `fit == 0` confirms solution discovery.

### Can this implementation handle negative coefficients or larger search spaces?

Yes, with modifications to `generate_gene()` and `mutate()`. For negative coefficients, expand the domain bounds to include negative integers (e.g., `random.randint(-target, target)`). For larger spaces, increase `pop_size` and `max_gen`, or implement adaptive mutation rates. The core `fit` function remains valid for any integer coefficients.

### Where does Microsoft AI-For-Beginners explain the theory behind genetic algorithms?

The repository's [`translations/en/lessons/6-Other/21-GeneticAlgorithms/README.md`](https://github.com/microsoft/AI-For-Beginners/blob/main/translations/en/lessons/6-Other/21-GeneticAlgorithms/README.md) provides conceptual background, while `Genetic.ipynb` focuses on implementation. The `Diophantine.ipynb` assignment bridges theory to practice, asking students to apply the GA to specific equation instances and analyze convergence behavior.