main.py

import random, string

target = "Now i love genetic Algorithms"


POPULATION_LENGTH = len(target)
GENE_POOL = string.ascii_letters + string.digits + " " + string.punctuation
POPULATION_POOL_SIZE = 1500
MUTATION_RATE = 0.01
NUMBER_OF_INDIVIDUAL_PARENTS = 2
CROSSOVER_PROBABLITY = 1

# Population Pool
def createPopulationPool():
    population = []
    for _ in range(0, POPULATION_POOL_SIZE + 1):
        population.append(''.join([random.choice(GENE_POOL) for _ in range(POPULATION_LENGTH)]))
    return population


# Fitness
def fitness_evaluation(item_str, target):
    score = len([g for position, g in enumerate(item_str) if g == target[position]])
    return float(score)

def getPopulationProbability(population: list):
    population_probability_dictionary = {}

    for item_str in population:
        population_probability_dictionary[item_str] = fitness_evaluation(item_str=item_str, target=target)

    return population_probability_dictionary

# Selection
def get_probablilty_list(population_probability_dictionary: dict):
    fitness = population_probability_dictionary.values()
    total_fit = float(sum(fitness))
    relative_fitness = [f/total_fit for f in fitness]
    probablities = [sum(relative_fitness[:i+1]) for i in range(len(relative_fitness))]
    return probablities


def roulette_wheel_selection(population, probabilities, number):
    chosen = []
    for _ in range(number):
        r = random.random()
        for(i, individual) in enumerate(population):
            if r <= probabilities[i]:
                chosen.append(list(individual))
                break
    return chosen

# Parents Are selected
# ParentA, ParentB = roulette_wheel_selection(population=population, probabilities=probablility_list, number=NUMBER_OF_INDIVIDUAL_PARENTS)


# CrossOver & Mutation
def uniformCrossOver(parentA, parentB):
    assert(len(parentA) == len(parentB))

    child1 = []
    child2 = []

    for gene1, gene2 in zip(parentA, parentB):
        bit = random.randint(0, 1)
        if bit == CROSSOVER_PROBABLITY:
            child1.append(gene2)
            child2.append(gene1)
        else:
            child1.append(gene1)
            child2.append(gene2)

    return child1, child2

# childA , childB = uniformCrossOver(ParentA, ParentB)

def mutateGene(child):
    return [gene if random.random() > MUTATION_RATE else random.choice(GENE_POOL) for gene in child]


# The main Gentic Function
def MainGeneticFunction(target: str):
    population = createPopulationPool()
    generation = 0

    while True:
        population_probability_dictionary = getPopulationProbability(population=population)
        
        best = max(population_probability_dictionary, key=population_probability_dictionary.get)
        if best == target:
            print(f"\nFound in generation {generation} target = {best}")
            break
        print(f"Current generation {generation} found = {best}")

        probablility_list = get_probablilty_list(population_probability_dictionary)
        
        new_population = []
        while len(new_population) < POPULATION_POOL_SIZE:
            ParentA, ParentB = roulette_wheel_selection(population=population, probabilities=probablility_list, number=NUMBER_OF_INDIVIDUAL_PARENTS)
            childA, childB = uniformCrossOver(ParentA, ParentB)
            
            new_population.append(''.join(mutateGene(childA)))
            new_population.append(''.join(mutateGene(childB)))
            
        population = new_population
        generation += 1

MainGeneticFunction(target= target)