Pasted

import random
 
def calculate_fitness(bits, items, threshold):
    total_cost = 0
    total_weight = 0
 
    #print("Items in fitness check:", items)
 
    for i, bit in enumerate(bits):
        if bit == 1:
            item = items[i]
            total_cost += item[1][0]
            total_weight += item[1][1]
    
    if total_weight <= threshold:
        return total_cost
    
    return 0
 
def perform_selection(items):
    backpack = []
 
    for _ in range(len(items)):
        if random.random() > 0.5:
            backpack.append(1)
        else:
            backpack.append(0)
 
    return backpack
 
def crossover_split(parent_a, parent_b):
    """ Single point crossover split """
    split_index = 3
 
    parent_1, splice_1 = parent_a[:split_index], parent_a[split_index:]
    parent_2, splice_2 = parent_b[:split_index], parent_b[split_index:]
    parent_1.extend(splice_2)
    parent_2.extend(splice_1)
 
    return parent_1, parent_2
 
def mutate(bits):
    """ Mutate by flipping bits pseudo-randomly """
    output = ''
    threshold = 0.9
 
    for bit in bits:
        if random.random() > threshold:
            if bit == 1:
                output += '0'
            else:
                output += '1'
        else:
            output += str(bit)
 
    #print("I:", ''.join([str(bit) for bit in bits]))
    #print("O:", output)
    return [int(bit) for bit in output]
 
def generate_population(items, n):
    selections = []
 
    for _ in range(n):
        selections.append(perform_selection(items))
 
    return selections
 
generations = 5
population_size = 10
 
items = {
    0: ("laptop", (500, 2200)),
    1: ("headphones", (150, 160)),
    2: ("coffee mug", (60, 350)),
    3: ("notepad", (40, 333)),
    4: ("water bottle", (30, 192))
}
 
# The initial population is entirely random
population = generate_population(items, 10)
 
# Apply the algorithm
for generation in range(generations):
    print(f"Generation {generation + 1}.")
 
    # calculate the fitness score for each of the members of the population
    fitness_scores = []
 
    for entry in population:
        fitness_scores.append((entry, calculate_fitness(entry, items, 3000))) 
 
    best = sorted(fitness_scores, key=lambda xy: xy[1])[::-1]
    
    elitism_count = 2
    elite = best[0:elitism_count]
    next_population = []
 
    for entry in elite:
        bits, score = entry
        next_population.append(bits)
 
    while len(next_population) < population_size:
        index_a = random.randint(0, len(items))
        index_b = random.randint(0, len(items))
 
        while index_b == index_a:
            index_b = random.randint(0, len(items))
 
        results = crossover_split(
            population[index_a], population[index_b])
 
        next_population.extend(results)
 
    print("Next population:", next_population)
    mutated_population = []
 
    for entry in next_population:
        mutation = mutate(entry)
        mutated_population.append(mutation)
 
    population = mutated_population
 
print("Finished.")