tiny_ga_v2.py

# tiny genetic algorithm by moshe sipper, www.moshesipper.com
import random
import numpy as np


def init_population(pop_size, genome_size):  # initialize the population of bit vectors
    return [random.choices(range(2), k=genome_size) for _ in range(pop_size)]


def fitness(individual):  # an individual's fitness is the number of 1s
    return sum(individual)


def selection(population, fitnesses):  # tournament selection
    tournament = random.sample(range(len(population)), k=3)
    tournament_fitnesses = [fitnesses[i] for i in tournament]
    winner_index = tournament[np.argmax(tournament_fitnesses)]
    return population[winner_index]


def crossover(parent1, parent2):  # single-point crossover
    xo_point = random.randint(1, len(parent1) - 1)
    return ([parent1[:xo_point] + parent2[xo_point:],
             parent2[:xo_point] + parent1[xo_point:]])


def mutation(individual):  # bitwise mutation with probability 0.1
    for i in range(len(individual)):
        if random.random() < 0.1:
            individual = individual[:i] + [1-individual[i]] + individual[i + 1:]
    return individual


pop_size, genome_size = 6, 5
population = init_population(pop_size, genome_size)  # generation 0

for gen in range(10):
    fitnesses = [fitness(individual) for individual in population]
    print('Generation ', gen, '\n', list(zip(population, fitnesses)))
    nextgen_population = []
    for i in range(int(pop_size / 2)):
        parent1 = selection(population, fitnesses)  # select first parent
        parent2 = selection(population, fitnesses)  # select second parent
        offspring1, offspring2 = crossover(parent1, parent2)  # perform crossover between both parents
        nextgen_population += [mutation(offspring1), mutation(offspring2)]  # mutate offspring
    population = nextgen_population