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)