Using Genetic Algorithms for Optimization Problems in the AI-For-Beginners Curriculum

The AI-For-Beginners curriculum teaches genetic algorithms through interactive Jupyter notebooks that implement selection, crossover, and mutation to solve optimization problems like the fair treasure split and Diophantine equations.

The microsoft/AI-For-Beginners repository includes a dedicated lesson on evolutionary computation located at lessons/6-Other/21-GeneticAlgorithms. This module demonstrates how to apply genetic algorithms for optimization problems using pure Python and NumPy, bridging the conceptual foundation from the introductory chapter to hands-on implementations that precede deep reinforcement learning content.

Where Genetic Algorithms Fit in the Curriculum

According to the source code structure, the genetic algorithms material resides in the 6-Other lesson series, specifically following the evolutionary approach concepts mentioned in lessons/1-Intro/README.md. The lesson precedes the deep reinforcement learning content found in lessons/6-Other/22-DeepRL, creating a logical progression from population-based search methods to advanced agent-based AI.

The curriculum provides three main resources for this topic:

• README.md – Conceptual overview of GA steps and exercise pointers
• Genetic.ipynb – Interactive implementations for classic problems
• Diophantine.ipynb – Assignment notebook for equation solving

Core GA Components in the Source Code

The implementation in Genetic.ipynb follows the standard evolutionary workflow with five key components that operate on a population of candidate solutions.

Gene Representation and Initialization

Candidate solutions are encoded as vectors. For partition problems like the treasure split, the generate(S) function creates random binary vectors matching the length of the input set:

def generate(S):
    """Create a random binary vector of the same length as S."""
    return np.array([random.randint(0, 1) for _ in S])

Fitness Function Design

The optimizer seeks to minimize fitness values. The fit(B, S) function calculates the absolute difference between partition sums, quantifying how unfair a treasure split is:

def fit(B, S):
    """Compute the cost of a partition encoded by B."""
    sum1 = (B * S).sum()
    sum2 = ((1 - B) * S).sum()
    return abs(sum1 - sum2)

Crossover and Mutation Operators

The xover(b1, b2) function blends parent genes using a random mask, while mutate(b) introduces diversity by flipping random bits to escape local minima:

def xover(b1, b2):
    """Combine two parents using a random mask generated by `generate`."""
    mask = generate(b1)
    return b1 * mask + b2 * (1 - mask)

def mutate(b):
    """Flip one random bit in the binary gene."""
    x = b.copy()
    i = random.randint(0, len(b) - 1)
    x[i] = 1 - x[i]
    return x

The Evolution Loop

The evolve() function orchestrates selection, breeding, and replacement using elitism (keeping the best individual) and generational turnover:

def evolve(pop_size, generations, S):
    # Initialise population

    pop = [generate(S) for _ in range(pop_size)]

    for gen in range(generations):
        # Evaluate fitness of current population

        fitnesses = [fit(ind, S) for ind in pop]
        # Select the best individuals (elitism)

        best_idx = np.argmin(fitnesses)
        best = pop[best_idx]

        # Create new offspring

        parent1, parent2 = random.sample(pop, 2)
        child = xover(parent1, parent2)
        child = mutate(child)

        # Replace the worst individual with the new child

        worst_idx = np.argmax(fitnesses)
        pop[worst_idx] = child

        # Optional: stop early if fitness is zero

        if fit(best, S) == 0:
            break

    return best, fit(best, S)

Practical Optimization Examples

The notebooks demonstrate how to adapt the genetic algorithm framework for different problem domains.

The Fair Treasure Split Problem

The Genetic.ipynb notebook implements a partition problem where the goal is dividing treasure values equally between two parties. The fitness function minimizes the absolute difference between subset sums, converging toward a difference of zero that represents a perfectly fair split.

The Diophantine Equation Assignment

The Diophantine.ipynb notebook adapts the genetic algorithm for solving equations of the form a + 2b + 3c + 4d = 30. Learners modify the gene representation from binary vectors to integer lists and redefine the fitness function to minimize the absolute error |a + 2b + 3c + 4d - 30|.

Integration with Other AI Techniques

The genetic algorithms lesson serves as foundational material for understanding optimization before advancing to lessons/6-Other/22-DeepRL. While deep reinforcement learning uses gradient-based methods, the GA module introduces population-based search strategies that complement the curriculum's coverage of evolutionary approaches.

Summary

• The genetic algorithms module in lessons/6-Other/21-GeneticAlgorithms provides hands-on optimization experience using only the standard Python scientific stack (numpy, random, matplotlib).
• Core functions (generate, fit, mutate, xover) implement the essential evolutionary operators: initialization, fitness evaluation, mutation, and crossover.
• The fair treasure split and Diophantine equation examples demonstrate how to encode different problem types as genes and define appropriate fitness landscapes.
• The curriculum deliberately keeps implementations in single notebooks to focus on algorithmic understanding rather than software engineering complexity.

Frequently Asked Questions

What files contain the genetic algorithm implementations?

The primary implementation files are lessons/6-Other/21-GeneticAlgorithms/Genetic.ipynb for the treasure split and 8-Queens problems, and lessons/6-Other/21-GeneticAlgorithms/Diophantine.ipynb for the equation solving assignment. The conceptual overview resides in README.md within the same directory.

How does the fitness function work in the treasure split example?

The fit(B, S) function computes the absolute difference between the sums of two partitions encoded by binary vector B. The algorithm minimizes this value, seeking a difference of zero that represents a perfectly fair split of the treasure values contained in array S.

Can I adapt the code for non-binary optimization problems?

Yes. The Diophantine.ipynb assignment requires adapting the gene representation from binary vectors to integer lists. You must redefine the generate() function to produce random integers and modify the fitness function to calculate error for your specific equation or constraint satisfaction problem.

Where does this lesson fit in the overall curriculum?

This lesson bridges the evolutionary approach introduced in lessons/1-Intro/README.md and the deep reinforcement learning material in lessons/6-Other/22-DeepRL. It provides practical optimization experience before learners encounter more complex agent training methodologies.

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