How Genetic Algorithm Implementation Solves the Diophantine Equation Problem in Python

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.

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:

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:

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:

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:

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:

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):

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:

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.

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