# How Genetic Algorithm Implementation Solves the Diophantine Equation Problem in Python

> Learn how genetic algorithm implementation solves Diophantine equations in Python. Discover its gene vector representation, crossover, mutation, and fitness function for finding integer solutions efficiently.

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

---

**The genetic algorithm implementation solves the Diophantine equation by representing candidate integer solutions as four-element gene vectors, minimizing the absolute deviation from the target sum through iterative crossover and mutation operations, and converging when the fitness function reaches zero.**

The microsoft/AI-For-Beginners repository demonstrates this evolutionary approach in the **Genetic.ipynb** notebook, providing a complete framework for finding integer roots that satisfy linear Diophantine constraints. This implementation treats mathematical solutions as genetic material, applying selection pressure to drive a population toward valid answers without exhaustive search.

## Gene Encoding and Problem Representation

The algorithm addresses the specific assignment from **Diophantine.ipynb**: find integers *a, b, c, d* such that **a + 2b + 3c + 4d = 30**.

Each candidate solution is encoded as a fixed-length integer vector **g** ∈ Γ. The gene representation uses a four-element list `[a, b, c, d]` where each entry is constrained to the interval `[0, 30]` as specified in the assignment hints.

```python
def generate():
    # random integer values in the allowed range [0,30] for a,b,c,d

    return [random.randint(0, 30) for _ in range(4)]

```

This encoding transforms the mathematical search problem into a genetic optimization task where the algorithm manipulates integer arrays rather than solving equations algebraically.

## Fitness Function Design

The fitness function quantifies how far a gene is from satisfying the Diophantine equation. Defined in `Genetic.ipynb`, the function calculates the absolute difference between the weighted sum and the target value:

```python
def fit(g):                     # g = [a, b, c, d]

    return abs(g[0] + 2*g[1] + 3*g[2] + 4*g[3] - 30)

```

The **genetic algorithm implementation** seeks to minimize `fit(g)`; a fitness of **0** indicates a valid solution. This scalar metric provides the selection pressure necessary for evolution, allowing the algorithm to compare candidate solutions and prioritize those closer to satisfying the equation.

## Evolutionary Operators

### Crossover with Binary Masking

The crossover operator combines genetic material from two parent solutions to produce offspring. The implementation uses a random binary mask generated by the `generate` routine to blend parent vectors element-wise:

```python
def xover(g1, g2):
    mask = generate()               # mask ∈ {0,1}⁴

    return g1*mask + g2*(1-mask)     # element-wise blend

```

In list comprehension form as shown in the repository:

```python
def xover(g1, g2):
    mask = generate()
    return [g1[i]*mask[i] + g2[i]*(1-mask[i]) for i in range(4)]

```

This **uniform crossover** approach allows each gene component to inherit independently from either parent, maintaining population diversity while exploring the integer solution space.

### Mutation Strategy

The mutation operator maintains genetic diversity by perturbing individual components. With probability applied during evolution, the function randomly selects one index and resamples it within the valid range:

```python
def mutate(g):
    i = random.randint(0, len(g)-1)   # pick a random index

    g[i] = random.randint(0, 30)     # re-sample within the allowed range

    return g

```

Or using the alternative implementation from the source:

```python
def mutate(g):
    i = random.randrange(4)
    g[i] = random.randint(0, 30)
    return g

```

This prevents premature convergence by introducing novel values into the gene pool, ensuring the algorithm can escape local minima in the fitness landscape.

## The Evolution Loop

The `evolve` function orchestrates the iterative improvement process. Operating on a population `P` of candidate solutions, it applies stochastic operators for a maximum of *n* generations (default 2000):

```python
def evolve(P, n=2000):
    for _ in range(n):
        best = min(fit(g) for g in P)
        if best == 0: break
        
        if random.random() < 0.3:          # mutation step (30%)

            i = random.randrange(len(P))
            mutant = mutate(P[i])
            worst = np.argmax([fit(g) for g in P])
            P[worst] = mutant               # replace worst with mutant

            
        else:                               # crossover step (70%)

            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 min(P, key=fit)                # best gene

```

The evolutionary strategy employs **elitist replacement**: mutated offspring replace the worst-fit individual unconditionally, while crossover results replace parents only if they demonstrate improved fitness. The 70/30 split favors exploitation through crossover but maintains exploration via mutation.

## Complete Implementation Example

The following runnable example integrates all components from `Genetic.ipynb` to solve the Diophantine equation:

```python
import random
import numpy as np

def generate():
    return [random.randint(0, 30) for _ in range(4)]

def fit(g):
    return abs(g[0] + 2*g[1] + 3*g[2] + 4*g[3] - 30)

def mutate(g):
    i = random.randrange(4)
    g[i] = random.randint(0, 30)
    return g

def xover(g1, g2):
    mask = generate()
    return [g1[i]*mask[i] + g2[i]*(1-mask[i]) for i in range(4)]

def evolve(P, n=5000):
    for _ in range(n):
        best = min(fit(g) for g in P)
        if best == 0: break
        
        if random.random() < 0.3:
            i = random.randrange(len(P))
            mutant = mutate(P[i])
            worst = np.argmax([fit(g) for g in P])
            P[worst] = mutant
        else:
            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 min(P, key=fit)

# Execution

pop_size = 50
population = [generate() for _ in range(pop_size)]
solution = evolve(population)

print("Solution:", solution)
print("Fitness:", fit(solution))   # → 0

```

Running this snippet typically yields a valid solution such as `[2, 6, 4, 2]` (where 2 + 2·6 + 3·4 + 4·2 = 30) within a few hundred generations.

## Summary

- The **genetic algorithm implementation** in `lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb` encodes Diophantine solutions as four-element integer vectors with values constrained to `[0, 30]`.

- **Fitness evaluation** uses the absolute deviation from the target sum `a + 2b + 3c + 4d = 30`, driving selection toward zero-error solutions.

- **Evolutionary operators** include uniform crossover with binary masking and single-index mutation, applied with a 70/30 crossover-to-mutation ratio to balance exploration and exploitation.

- The **elitist replacement strategy** upgrades the population by replacing low-fitness individuals with improved offspring, converging efficiently without brute-force enumeration.

## Frequently Asked Questions

### What specific Diophantine equation does the implementation solve?

The code solves the linear equation **a + 2b + 3c + 4d = 30** for non-negative integers, as defined in the **Diophantine.ipynb** assignment. The fitness function specifically calculates `abs(g[0] + 2*g[1] + 3*g[2] + 4*g[3] - 30)` to measure solution validity.

### How does the fitness function guide the genetic algorithm?

The fitness function serves as the optimization objective, returning zero only when the equation is satisfied. By minimizing this absolute difference metric, the **genetic algorithm implementation** can rank candidates and apply selection pressure, allowing the population to evolve toward valid integer roots through iterative improvement.

### Why does the evolution loop use a 30% mutation rate?

The **30% mutation probability** maintains sufficient genetic diversity to prevent premature convergence on local optima while allowing the crossover operator (70% probability) to exploit promising solution regions. This balance ensures the algorithm continues exploring the integer space `[0,30]^4` even as it refines high-fitness candidates.

### Can this genetic algorithm solve other Diophantine equations?

Yes. The modular design in `Genetic.ipynb` allows extension to any integer-based Diophantine equation by modifying the `fit(g)` function to reflect the new mathematical constraint and adjusting the gene length in `generate()`. The evolutionary engine remains generic, requiring only domain-specific fitness evaluation to solve different linear or non-linear integer problems.