Assignment 3 - Genetic Algorithms
CS131 Spring 2025
March 16, 2025
Rachel Snyder

This program solves the knapsack problem by implementing a genetic algorithm.

Run the program by running "python3 knapsack.py". The output includes the final
selected chromosome, the amount of generations gone through, and the boxes that
should be included in the chosen solution.

I tested the program by creating small tests for each of the helper functions
and classes I wrote and then combining all the functionality together, testing
along the way where possible.

-----------

Chromosome: Each chromosome represents a potential state of the knapsack where
            each of the 12 boxes is either included or not. A 1 represents the 
            inclusion of the box numbered with the index of the array + 1 
            (since the array is 0-indexed). So the value at the array index 4 is
            representative of box #5.

Initial Population: The initial population consists of 80 chromosomes with a
                    randomely selected combination of boxes. 80 is somewhat
                    arbitrary but after testing different options, it seemed like 
                    a reasonable middle ground.

Fitness Function: The fitness function is the total value of the boxes included
                  in the state the chromosome represents. However, if the weight
                  of the boxes exceeds the maximum of 250, then the fitness is 0.

Selection Process: This solution uses truncated rank-based selected (culling).
                   The least fit 50% of the population is culled at each generation.

Genetic Operators (Fringe Operations): 
        Mutation: This solution uses single-point mutation. A single box is either
                  put in or taken out of the knapsack with each mutation (i.e. 
                  a single random bit is flipped).
        Recombination: This solution uses one-point crossover. A random point on 
                       the chromosomes are selected and genetic material from 
                       each of the parents is divided around this point.
            
When to Stop Searching: The algorithm stops searching for a more optimal 
                        solution when there is less than 3 changes to the 
                        optimal value over 5 generations. This is meant to 
                        indicate when there is not much movement happening in
                        the population anymore.