Untitled

import random

IdealBag = [(25, 300, 1000)] 
population = 500  # population size
pc = 0.9 # crossover probability 
pm = 0.6  # mutation probability 
knapsack = [] 
generations = 100

# Generates a bag in the form of (a, b, c)
def generateBag():
    Weight = random.randint(0, 100)
    profit = random.randint(0, 100)
    Size = random.randint(0, 10000)
    return Weight, profit, Size

# Performs crossover between two parents
def crossover(parent1, parent2):
    # Choose a crossover point (random index to split the bag tuple)
    crossover_point = random.randint(0, 2)  # 0 for weight, 1 for profit, 2 for size

    # Create offspring by combining genetic material of parents at the crossover point
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]

    return child1, child2

# Calculates fitness score of an individual bag
def fitness(bag, ideal_bag):
    weight_diff = abs(bag[0] - ideal_bag[0][0])
    profit_diff = abs(bag[1] - ideal_bag[0][1])
    size_diff = abs(bag[2] - ideal_bag[0][2])
    total_diff = weight_diff + profit_diff + size_diff
    return 1 / (1 + total_diff)  # Return fitness score

# Performs mutation on two children
def mutation(child1, child2):
    mutated_child1 = list(child1)
    mutated_child2 = list(child2)

    # Randomly select an attribute to mutate
    attribute_index = random.randint(0, 2)  # 0 for weight, 1 for profit, 2 for size

    # Mutate the selected attribute by adding a small random value
    mutation_amount = random.randint(-10, 10)  # Adjust mutation range as needed
    mutated_child1[attribute_index] += mutation_amount
    mutated_child2[attribute_index] += mutation_amount

    # Ensure attribute values stay within valid range
    mutated_child1[attribute_index] = max(0, mutated_child1[attribute_index])
    mutated_child2[attribute_index] = max(0, mutated_child2[attribute_index])

    return tuple(mutated_child1), tuple(mutated_child2)

# Generate initial population
individuals = [generateBag() for _ in range(population)]  # creates a list of each (a,b,c)

best_fitness = 0
best_individual = None

# Evolution loop over generations
for generation in range(generations):
    fitness_scores = [fitness(individual, IdealBag) for individual in individuals]
    
    # Update best fitness and best individual for the generation
    max_fitness = max(fitness_scores)
    max_index = fitness_scores.index(max_fitness)
    if max_fitness > best_fitness:
        best_fitness = max_fitness
        best_individual = individuals[max_index]

    # Print generation number, best individual, and its fitness
    print(f"Generation: {generation + 1}, Best Individual: {best_individual}, Fitness: {best_fitness}")

    # Check for perfect match
    if best_fitness >= 0.98:
        print(f"Perfect match found in generation {generation + 1}!")
        print(f"Best Individual: {best_individual}, Fitness: {best_fitness}")
        break

    # Sort individuals based on fitness scores
    sorted_individuals = [individual for _, individual in sorted(zip(fitness_scores, individuals), reverse=True)]

    # Keep the top population fittest individuals
    individuals = sorted_individuals[:population]

    # Apply crossover and mutation to create new individuals
    new_individuals = []
    for _ in range(population):
        parent1 = random.choice(individuals)
        parent2 = random.choice(individuals)

        # Apply crossover based on the crossover probability (pc)
        if random.random() < pc:
            child1, child2 = crossover(parent1, parent2)
        else:
            child1, child2 = parent1, parent2

        # Apply mutation based on the mutation probability (pm)
        if random.random() < pm:
            child1, child2 = mutation(child1, child2)

        new_individuals.append(child1)
        new_individuals.append(child2)

    # Extend the population with the new individuals
    individuals.extend(new_individuals)

else:
    print("No perfect match found within specified generations.")