si2

from itertools import compress
import random
import time
import matplotlib.pyplot as plt
import copy

from data import *

def initial_population(individual_size, population_size):
    return [[random.choice([True, False]) for _ in range(individual_size)] for _ in range(population_size)]

def fitness(items, knapsack_max_capacity, individual):
    total_weight = sum(compress(items['Weight'], individual))
    if total_weight > knapsack_max_capacity:
        return 0
    return sum(compress(items['Value'], individual))

def population_best(items, knapsack_max_capacity, population):
    best_individual = None
    best_individual_fitness = -1
    for individual in population:
        individual_fitness = fitness(items, knapsack_max_capacity, individual)
        if individual_fitness > best_individual_fitness:
            best_individual = individual
            best_individual_fitness = individual_fitness
    return best_individual, best_individual_fitness

def smiglo(items, knapsack_max_capacity, population):
  ruletka = []
  szansa = 0
  sum_fitness = 0
  for individual2 in population:
    sum_fitness += fitness(items, knapsack_max_capacity, individual2)
  for individual in population:
    individual_fitness = fitness(items, knapsack_max_capacity, individual)
    szansa += individual_fitness/sum_fitness
    ruletka.append((individual, szansa))

  wylosowana_liczba = random.random()
  for individual, szansa in ruletka:
        if szansa >= wylosowana_liczba:
            return individual

def mutate(individual):
  i = int(random.random() * len(individual))
  individual[i] = not individual[i]

def crossover(pierwszy, drugi):
    polowa_dlugosci = len(pierwszy) // 2

    nowy_pierwszy = pierwszy[:polowa_dlugosci] + drugi[polowa_dlugosci:]
    nowy_drugi = drugi[:polowa_dlugosci] + pierwszy[polowa_dlugosci:]

    mutate(nowy_pierwszy)
    mutate(nowy_drugi)

    return nowy_pierwszy, nowy_drugi


items, knapsack_max_capacity = get_big()
print(items)

population = initial_population(len(items), population_size)
smiglo(items, knapsack_max_capacity, population)
population_size = 100
generations = 300
n_selection = 20
n_elite = 2
start_time = time.time()
best_solution = None
best_fitness = 0
population_history = []
best_history = []
population = initial_population(len(items), population_size)
for _ in range(generations):
    population_history.append(copy.deepcopy(population))

    # TODO: implement genetic algorithm
    posortowane = sorted(population, key=lambda ind: fitness(items, knapsack_max_capacity, ind))
    nowa_populacja = posortowane[::-1][:n_elite]
    while population_size > len(nowa_populacja):
      pierwszy = smiglo(items, knapsack_max_capacity, posortowane[::-1][:n_selection])
      drugi = smiglo(items, knapsack_max_capacity, posortowane[::-1][:n_selection])
      nowy_pierwszy, nowy_drugi = crossover(pierwszy, drugi)
      nowa_populacja.append(nowy_pierwszy)
      nowa_populacja.append(nowy_drugi)

    population = nowa_populacja
    best_individual, best_individual_fitness = population_best(items, knapsack_max_capacity, population)
    if best_individual_fitness > best_fitness:
        best_solution = best_individual
        best_fitness = best_individual_fitness
    best_history.append(best_fitness)

end_time = time.time()
total_time = end_time - start_time
print('Best solution:', list(compress(items['Name'], best_solution)))
print('Best solution value:', best_fitness)
print('Time: ', total_time)

# plot generations
x = []
y = []
top_best = 10
for i, population in enumerate(population_history):
    plotted_individuals = min(len(population), top_best)
    x.extend([i] * plotted_individuals)
    population_fitnesses = [fitness(items, knapsack_max_capacity, individual) for individual in population]
    population_fitnesses.sort(reverse=True)
    y.extend(population_fitnesses[:plotted_individuals])
plt.scatter(x, y, marker='.')
plt.plot(best_history, 'r')
plt.xlabel('Generation')
plt.ylabel('Fitness')
plt.show()