genetic.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import random
from math import ceil, floor
from typing import Any, List

import numpy as np
from scipy.stats import truncnorm

######################### HYPERPARAMETERS ###################################

MUTATION_RATE = 0.7
POPULATION_SIZE = 100
NUM_PARENTS = min(5, POPULATION_SIZE)
SURVIVAL_RATE = 0.3  # What percentage of population is saved for next generation.
REPRIEVE_RATE = 0.1  # What percent of the population is spared each generation.
MAX_ITERS = 1 * 1e4
EPSILON = 1e-3

N: int = 1
BOUND = 5.12  # The bounds of the box we optimize over.

#############################################################################

Individual = np.ndarray
Population = List[Individual]
Real = float

# BENCHMARK FUNCTIONS


def rastrigin(x, A=10):
    return 10 * len(x) + sum((i ** 2 - A * np.cos(2 * np.pi * i)) for i in x)


def sphere(x):
    return sum(i ** 2 for i in x)


def booth_fn(x):
    return (x[0] + 2 * x[1] - 7) ** 2 + (2 * x[0] + x[1] - 5) ** 2


f = rastrigin


def individual(bound: float=BOUND) -> Individual:

    return np.random.uniform(low=-bound, high=bound, size=N)


def fitness(individual) -> Real:
    return f(individual)


def create_population() -> Population:

    return [individual() for _ in range(POPULATION_SIZE)]


def avg_fitness(population):
    return sum(fitness(individual) for individual in population) / len(population)


def cull(population) -> Population:

    population.sort(key=fitness)
    split_idx = ceil(SURVIVAL_RATE * len(population))

    # They survive.
    fittest = population[:split_idx]
    reprieved = random.sample(
        population[split_idx:], floor(REPRIEVE_RATE * len(population[split_idx:])))

    return fittest + reprieved


def breed(parents: Population, mutation_rate: float=MUTATION_RATE) -> Individual:

    child = min(
        random.sample(parents, NUM_PARENTS),
        key=fitness, )

    # Clip to avoid out of bounds issues.
    if random.random() < MUTATION_RATE:
        child += np.clip(
            np.random.uniform(low=-EPSILON, high=EPSILON, size=N),
            a_min=-BOUND,
            a_max=BOUND, )

    return child


def create_new_generation(population) -> Population:

    num_children = POPULATION_SIZE - len(population)
    num_parents = min(len(population), NUM_PARENTS)

    population += [breed(random.sample(population, k=num_parents)) for _ in range(num_children)]
    return population


def evolve():
    population = create_population()
    FITNESS = avg_fitness(population)

    iter = 0

    while FITNESS > 1e-7 and iter < MAX_ITERS:
        population = create_new_generation(cull(population))
        FITNESS = avg_fitness(population)

        iter += 1

        if iter % 1000 == 0:
            best = min(population, key=fitness)
            print('--------------------------------------------------------------')
            print(f'FITNESS = {FITNESS}, iter = {iter}, BEST = {fitness(best)}')

    print(f'iter = {iter}')
    best = min(population, key=fitness)
    return best


if __name__ == '__main__':
    best = evolve()
    print(best)
    print(fitness(best))