Genetic algorithm

genetic.py

from collections import namedtuple
from functools import partial
from random import choices, randint, random, randrange
import time
from typing import Callable, List, Tuple

Genome = List[int]
Population = List[Genome]
FitnessFunc = Callable[[Genome], int]
PopulationFunc = Callable[[], Population]
SelectionFunc = Callable[[Population, FitnessFunc], Tuple[Genome, Genome]]
CrossoverFunc = Callable[[Genome, Genome], Tuple[Genome, Genome]]
MutationFunc = Callable[[Genome], Genome]
Thing = namedtuple("Thing", ["name", "value", "weight"])

things = [
    Thing("Laptop", 500, 2200),
    Thing("Headphones", 150, 160),
    Thing("Mug", 60, 350),
    Thing("Notepad", 40, 333),
    Thing("Water bottle", 30, 192),
]

more_things = [
    Thing("Mints", 5, 25),
    Thing("Socks", 10, 38),
    Thing("Tissues", 15, 80),
    Thing("Phone", 500, 200),
    Thing("Cap", 100, 70),
]


# Genetic representation of a solution
def generate_genome(
    length: int,
) -> Genome:
    return choices([0, 1], k=length)


# A function to generate new solutions
def generate_population(
    size: int,
    genome_length: int,
) -> Population:
    return [generate_genome(genome_length) for _ in range(size)]


# Fitness function to evaluate solutions
def fitness(
    genome: Genome,
    things: List[Thing],
    weight_limit: int,
) -> int:
    if len(genome) != len(things):
        raise ValueError("genome and things must be of the same length")

    weight = 0
    value = 0

    for i, thing in enumerate(things):
        if genome[i] == 1:
            weight += thing.weight
            value += thing.value

            if weight > weight_limit:
                return 0

    return value


# Selection function for the new generation
def selection_function(
    population: Population,
    fitness_funct: FitnessFunc,
) -> Population:
    return choices(
        population=population,
        weights=[fitness_funct(genome) for genome in population],
        k=2,
    )


# Crossover function to create new solution for future generations
def single_point_crossover(
    a: Genome,
    b: Genome,
) -> Tuple[Genome, Genome]:
    if len(a) != len(b):
        raise ValueError("genomes a and b must have same length")

    length = len(a)
    if length < 2:
        return a, b

    p = randint(1, length - 1)
    return a[0:p] + b[p:], b[0:p] + a[p:]


# Mutation function
def mutation(
    genome: Genome,
    num: int = 1,
    probability: float = 0.5,
) -> Genome:
    for _ in range(num):
        index = randrange(len(genome))
        genome[index] = (
            genome[index] if random() > probability else abs(genome[index] - 1)
        )
    return genome


# Runs
def run_evolution(
    populate_func: PopulationFunc,
    fitness_func: FitnessFunc,
    fitness_limit: int,
    selection_func: SelectionFunc = selection_function,
    crossover_func: CrossoverFunc = single_point_crossover,
    mutation_func: MutationFunc = mutation,
    generation_limit: int = 100,
) -> Tuple[Population, int]:
    population = populate_func()

    for i in range(generation_limit):
        # Elitism sort
        population = sorted(
            population,
            key=lambda genome: fitness_func(genome),
            reverse=True,
        )

        # When elite genome reaches limite, break
        if fitness_func(population[0]) >= fitness_limit:
            break

        # Elite genomes
        next_generation = population[0:2]

        for j in range(int(len(population) / 2) - 1):
            parents = selection_func(population, fitness_func)
            offspring_a, offspring_b = crossover_func(parents[0], parents[1])
            offspring_a = mutation_func(offspring_a)
            offspring_b = mutation_func(offspring_b)
            next_generation += [offspring_a, offspring_b]

        population = next_generation

    population = sorted(
        population,
        key=lambda genome: fitness_func(genome),
        reverse=True,
    )

    return population, i


# Wrapping up
start = time.time()
population, generations = run_evolution(
    populate_func=partial(
        generate_population,
        size=10,
        genome_length=len(more_things),
    ),
    fitness_func=partial(
        fitness,
        things=more_things,
        weight_limit=3000,
    ),
    # fitness_limit=740, # for things
    fitness_limit=1310,
    generation_limit=100,
)
end = time.time()

# Helper
def genome_to_things(genome: Genome, things: List[Thing]) -> List[Thing]:
    result = []
    for i, thing in enumerate(things):
        if genome[i] == 1:
            result += [thing.name]
    return result


# Running
print(f"number of generations: {generations}")
print(f"time: {end - start} seconds")
print(f"best solution: {genome_to_things(population[0], more_things)}")