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

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:

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:

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:

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:

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:

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:

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:

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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}