knapsack.py

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# Assignment 3 - Genetic Algorithms                                           #
# CS 131 - Artificial Intelligence                                            #
# Rachel Snyder - March 2025                                                  #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

import random
from boxes import boxes
from chromosome import Chromosome
from fitness_func import fitness_func
from helper_funcs import cull_bottom_half, choose_and_use_parents

def main():
    population = []
    initial_pop_size = 80

    # Create an initial population of 80 random chromosomes
    for _ in range(initial_pop_size):
        chrom = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        for i in range(len(chrom)):
            chrom[i] = random.choice([0, 1])
        new_chrom = Chromosome(chrom)
        population.append(new_chrom)

    # Sort the population based on the fitness of each chromosome
    population.sort(key=lambda x: fitness_func(x))

    done = False
    counter = 0

    # Indicative of how much movement is happening across 5 generations
    change_over_5_iters = 0

    while not done:
        counter += 1
        most_fit = fitness_func(population[-1])

        population = cull_bottom_half(population) # Cull population
        new_children = []

        for _ in range(len(population)): # Rebuild population
            new_child = choose_and_use_parents(population)
            new_children.append(new_child)
        population.extend(new_children)
        population.sort(key=lambda x: fitness_func(x))

        new_most_fit = fitness_func(population[-1])
        change_over_5_iters += abs(new_most_fit - most_fit)
        
        if counter % 5 == 0: # check whether sufficient movemement over 
                             # 5 iterations
            if change_over_5_iters <= 3:
                done = True
            change_over_5_iters = 0

    print(f"Final Selected Chromosome: {population[-1]}")
    print(f"New Generations: {counter}")
    print(f"Items to put in the knapsack:")
    for i, genotype in enumerate(population[-1].chromosome):
        if genotype == 1:
            print(f"Box {i + 1} | Weight: {boxes[i + 1][0]} | Value: {boxes[i + 1][1]}")


if __name__ == "__main__":
    main()