Genetic Algorithm

genetic.py

import operator
import random


# an individual with bigger fitness is more likely to succeed.
def fitness(password, test_word):
    if len(test_word) != len(password):
        return
    score = 0
    for i in range(len(password)):
        if password[i] == test_word[i]:
            score += 1
    return score * 100 / len(password)


# creating individuals (population)
# motivation: DNA is composed of genes and each of them come from different alleles (versions of genes)
# in this case each character is a gene and value of the letter is the allele
# criteria: each individual has a good shape (word of size N) and population can cover all posibilities of words of size N
# first population: should cover all possibilities and shouldn't be biased.


def generate_first_population(size, password):
    def generate_word(length):
        alphabet = "abcdefghijklmnopqrstuvwxyz! "
        return "".join([random.choice(alphabet) for item in [0] * len(target)])

    return [generate_word(len(password)) for i in range(size)]


# Selection: From one generation to the next
# 1. select a specific part of previous generatic
# 2. combine breeders into next batch


def sort_population_by_fitness(population, password):
    performance = {}
    for individual in population:
        performance[individual] = fitness(password, individual)
    return sorted(performance.items(), key=operator.itemgetter(1), reverse=True)


def select_breeders(sorted_population, take_best, take_lucky):
    next_generation = []
    for i in range(take_best):
        next_generation.append(sorted_population[i][0])
    for i in range(take_lucky):
        next_generation.append(random.choice(sorted_population)[0])
    random.shuffle(next_generation)
    return next_generation


# Breeding


def create_children(breeders, num_children):
    def create_child(individual_1, individual_2):
        child = ""
        for i in range(len(individual_1)):
            if int(100 * random.random()) < 50:
                child += individual_1[i]
            else:
                child += individual_2[i]
        return child

    next_population = []
    for i in range(len(breeders) // 2):
        for j in range(num_children):
            next_population.append(
                create_child(breeders[i], breeders[len(breeders) - 1 - i])
            )
    return next_population


# Mutation


def mutate_population(population, chance_of_mutation):
    def mutate_word(word):
        index_modification = int(random.random() * len(word))
        if index_modification == 0:
            word = chr(97 + int(26 * random.random())) + word[1:]
        else:
            word = (
                word[:index_modification]
                + chr(97 + int(26 * random.random()))
                + word[index_modification + 1 :]
            )
        return word

    for i in range(len(population)):
        if random.random() * 100 < chance_of_mutation:
            population[i] = mutate_word(population[i])
    return population


target = "im from honduras"
population_size = 300
num_children = 8
mutation_rate = 25
population = generate_first_population(population_size, target)


def genetic_algorithm(population, target, num_children, mutation_rate):
    iterations, i = 200, 0
    take_best, take_lucky = len(population) // 2, len(population) // 10
    output = [("", 0)]
    while target != output[0][0] and i < iterations:
        sorted_population = sort_population_by_fitness(population, target)
        breeders = select_breeders(sorted_population, take_best, take_lucky)
        population = create_children(breeders, num_children)
        population = mutate_population(population, mutation_rate)
        output = sort_population_by_fitness(population, target)
        i += 1
    return output[0]


print(genetic_algorithm(population, target, num_children, mutation_rate))