SI_2020/genetic_algorithm.py
2020-06-15 15:03:47 +02:00

176 lines
7.1 KiB
Python
Executable File

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)