Genetic Algorithm - The Nature of Code Python Example

main.py

"""
Genetic Algorithm Implementation

This script is an implementation of a simple genetic algorithm (GA), inspired by the principles
of biological evolution. The concepts outlined in Daniel Shiffman's book "Nature of Code" have 
been followed to create this. The main concepts involved are:

    1. Initialization: Start with a population of individuals, each of which is a potential solution.
    2. Fitness Function: Each individual is evaluated using a fitness function.
    3. Selection: The individuals with higher fitness are more likely to be selected for reproduction.
    4. Crossover (Reproduction): New individuals are created by combining parts of two parent individuals.
    5. Mutation: There's a small chance that some parts of an individual might randomly change.
    6. Loop: The process of selection, crossover, and mutation is repeated for many generations.

The goal of this GA implementation is to evolve a population of random strings towards a predefined target string.

This code was authored by Kevin Saltarelli (github.com/kevinqz).

"""

import random
import string
from termcolor import colored
import os

# Define the target string and the size of the population.
# Each string in the population represents an individual in the context of the genetic algorithm.
# Concept 1: Initialization
TARGET = "Hello, World!"
POP_SIZE = 100
MUTATION_RATE = 0.01
population = [''.join(random.choices(string.printable, k=len(TARGET))) for _ in range(POP_SIZE)]


def fitness(individual):
    """
    Function to calculate the fitness of an individual.
    In this context, fitness is determined by how many characters in the string match the target.
    Concept 2: Fitness Function
    
    :param individual: a string from the population
    :return: number of characters in individual string that match the TARGET
    """
    return sum(i == j for i, j in zip(individual, TARGET))


def weighted_random_choice(population):
    """
    Function to select an individual from the population, favoring fitter individuals.
    Concept 3: Selection
    
    :param population: list of individuals
    :return: an individual from the population
    """
    max = sum(fitness(ch) for ch in population)
    pick = random.uniform(0, max)
    current = 0
    for individual in population:
        current += fitness(individual)
        if current > pick:
            return individual


def reproduce(mother, father):
    """
    Function to create a new individual by combining two parent individuals.
    Also introduces a chance of mutation, representing random changes in the new individual.
    Concept 4: Crossover (Reproduction)
    Concept 5: Mutation
    
    :param mother: a string from the population
    :param father: a string from the population
    :return: a new individual combining characteristics from mother and father with a chance of mutation
    """
    child = ''.join(m if random.random() < 0.5 else f for m, f in zip(mother, father))
    child = ''.join(c if random.random() > MUTATION_RATE else random.choice(string.printable) for c in child)
    return child


# Main loop for the Genetic Algorithm
generation = 0
while True:
    # This is the main loop of the GA, where selection, crossover and mutation take place over generations.
    # Concept 6: Loop
    
    generation += 1
    population.sort(key=fitness, reverse=True)
    print(colored("Generation:", "yellow"), colored(f"{generation}", "white"), 
          colored("Best:", "yellow"), colored(f"{population[0]}", "white"), 
          colored("Fitness:", "yellow"), colored(f"{fitness(population[0])}", "white"))
    if fitness(population[0]) == len(TARGET):
        break
    next_gen = population[:2]
    for _ in range(POP_SIZE - 2):
        parent1 = weighted_random_choice(population)
        parent2 = weighted_random_choice(population)
        next_gen.append(reproduce(parent1, parent2))
    population = next_gen

print(colored(f"Final: {population[0]}", "green"))
clear = input(colored("\nDo you want to clear console? [Y/n]", "cyan"))
if clear.lower() != 'n' and clear.lower() != 'no':
    os.system('cls' if os.name == 'nt' else 'clear')