SI_2020/genetic_algorithm.py

import random
import math
### prawdopodobieństwo mutacji
mutation_prob = 0.03
### ilość osobników w pokoleniu, powinna być parzysta
# generation_size = 40
### liczba pokoleń
# number_of_generations = 30
### jak bardzo promowane są osobniki wykorzystujące całą pojemność regału
amount_of_promotion = 5


def first_gen(number_of_packages, number_of_racks, generation_size):
    first_generation = []
    for individual in range(generation_size):
        individual = []
        for pack in range(number_of_packages):
            r = random.randint(0,number_of_racks-1)
            individual.append(r)
        first_generation.append(individual)
    return first_generation

# def evaluation(individual, packages, racks, number_of_packages, number_of_racks, tree_predictor):
#     # im większy fitness tym lepszy osobnik
#     # print("regały: ",racks)
#     rest_of_capacity = [rack.capacity for rack in racks]
#     # print("początkowa pojemność: ",rest_of_capacity)
#     for i in range(number_of_packages):
#         can_place = tree_predictor.check_if_can_place(packages[i], racks[i])
#         if not can_place:
#             rest_of_capacity[individual[i]] -= packages[i].size * 5
#         else:
#             rest_of_capacity[individual[i]] -= packages[i].size
#     # print("pozostała pojemność: ",rest_of_capacity)
#     # pdb.set_trace()
#     fitness = 0
#     for i in range(number_of_racks):
#         # jak regał jest przepełniony, zmniejsza fitness osobnika
#         if rest_of_capacity[i] < 0:
#             fitness += rest_of_capacity[i]
#             # delikane promowanie osobników wykorzystujących regały w pełni
#         elif rest_of_capacity[i] == 0:
#             fitness += 2
#         else:
#             fitness += 1
#     return fitness


def evaluation(individual, packages, racks, number_of_packages, number_of_racks, tree_predictor):
    # im większy fitness tym lepszy osobnik
    # print("regały: ",racks)
    rest_of_capacity = [rack.capacity for rack in racks]
    # print("początkowa pojemność: ",rest_of_capacity)
    bad_placed = 0
    for i in range(number_of_packages):
        rest_of_capacity[individual[i]] -= packages[i].size
        can_place = tree_predictor.check_if_can_place(packages[i], racks[i])
        if not can_place:
            bad_placed +=1
    # print("pozostała pojemność: ",rest_of_capacity)
    # pdb.set_trace()
    fitness = 0
    for i in range(number_of_racks):
        # jak regał jest przepełniony, zmniejsza fitness osobnika
        if rest_of_capacity[i] < 0:
            fitness += rest_of_capacity[i]
            # delikane promowanie osobników wykorzystujących regały w pełni
        elif rest_of_capacity[i] == 0:
            fitness += amount_of_promotion
    fitness -= 5*bad_placed
    return fitness

def roulette(generation, packages, generation_size ,racks, number_of_packages, number_of_racks, tree_predictor):
    # print('pokolenie: ', generation)
    evaluations = []
    for i in range(generation_size):
        individual_fitness = evaluation(generation[i], packages, racks, number_of_packages, number_of_racks, tree_predictor)
        evaluations.append(individual_fitness)
    # print("tablica dopasowań: ", evaluations)
    maximum = min(evaluations)
    # dodaję tą 1 żeby nie wywalać najgorszego osobnika
    normalized = [x+(-1*maximum)+1 for x in evaluations]
    # print(normalized)
    sum_of_normalized = sum(normalized)
    roulette_tab = [x/sum_of_normalized for x in normalized]
    # print(roulette_tab)
    for i in range(1,generation_size-1):
        roulette_tab[i] += roulette_tab[i-1]
        # wpisuję 1 ręcznie, bo czasem liczby nie sumowały się idealnie do 1
        #(niedokładność komputera)
    roulette_tab[generation_size-1] = 1
    # print("ruletka: ", roulette_tab)
    survivors = []
    for individual in range(generation_size):
        random_number = random.random()
        interval_number = 0
        while random_number > roulette_tab[interval_number]:
            interval_number += 1
        survivors.append(generation[interval_number])
    # print('przetrwali: ',survivors)
    return survivors

def crossover(individual1, individual2, number_of_packages):
    cut = random.randint(1,number_of_packages-1)
    new1 = individual1[:cut]
    new2 = individual2[:cut]
    new1 = new1 + individual2[cut:]
    new2 = new2 + individual1[cut:]
    # print(individual1)
    # print(individual2)
    # print(new1)
    # print(new2)
    # print(cut)
    return new1, new2

def mutation(individual, number_of_packages, number_of_racks):
    # print(individual)
    locus = random.randint(0,number_of_packages-1)
    individual[locus] = random.randint(0,number_of_racks-1)
    return individual


def gen_alg(packages, racks, number_of_generations, generation_size, mutation_prob, amount_of_promotion, tree_predictor):
    number_of_packages = len(packages)
    number_of_racks = len(racks)

    ### WŁAŚCIWY ALGORYTM
    generation = first_gen(number_of_packages, number_of_racks, generation_size)
    global_maximum = -math.inf

    # pętla znajdująca najlepszy fitness w pierwszym pokoleniu
    for i in range(generation_size):
        evaluation_of_individual = evaluation(generation[i], packages, racks, number_of_packages, number_of_racks, tree_predictor)
        if evaluation_of_individual > global_maximum:
            global_maximum = evaluation_of_individual
            best_individual = generation[i].copy()

    #właściwa pętla programu
    for generation_index in range(number_of_generations):
        # print('pokolenie numer: ', generation_index)
        # print(generation)

        ### RULETKA
        survivors = roulette(generation, packages, generation_size, racks, number_of_packages, number_of_racks, tree_predictor)
        # print('przetrwali: ',survivors)

        ### KRZYŻOWANIE
        descendants = []
        for individual in range(0,generation_size,2):
            pair = crossover(survivors[individual],survivors[individual+1], number_of_packages)
            for each in pair:
                descendants.append(each)
        # print('potomkowie: ', descendants)

        ### MUTACJA
        for individual in range(generation_size):
            if random.random() <= mutation_prob:
                mutation(descendants[individual], number_of_packages, number_of_racks)
        # print('potomkowie po mutacji: ', descendants)

        ### NAJLEPSZE DOPASOWANIE
        local_maximum = -math.inf
        for each in range(generation_size):
            specific_fitness = evaluation(descendants[each], packages, racks, number_of_packages, number_of_racks, tree_predictor)
            if specific_fitness > local_maximum:
                local_maximum = specific_fitness
                generation_best_individual = descendants[each].copy()
        print('maksimum w pokoleniu: ',local_maximum)
        if local_maximum > global_maximum:
            global_maximum = local_maximum
            best_individual = generation_best_individual.copy()
        generation = descendants
    print('maksimum globalne: ', global_maximum)
    # print("jeśli maksimum globalne wynosi 0, każda paczka ma swój regał")
    print("najlepsze dopasowanie: ", best_individual)