The Knapsack problem is another NP-complete optimization problem, involving the determining of the most efficient way to place a set of objects with weights and values into a ‘knapsack’ with a specified weight limit. Again, as there’s no known polynomial solver for this problem, we are forced to rely on optimization to approximate a solution. Below, we will determine the best algorithm for doing so. We follow the same system of experiments used previously; one to determine the algorithm’s performance under increased complexity, and another to determine its fitness over increased iterations. Our optimization algorithms will utilize the hyperparameters predetermined by ABAGAIL, which are listed in Table 6. Further, we will assign a knapsack item’s max value and max weight to be 50, creating 4 copies of each to attempt to place in the bag. SA Starting Temp Cooling Factor 100 0.95 GA Pop. Size # to Mate # to Mutate 200 150 25 MIMIC Sample Count # to Keep 200 100 Table 6. Optimization algorithm hyperparameters, pulled from ABAGAIL’s Knapsack testing implementation. Randomized Hill Climbing not listed, as no hyperparameters are applicable. For our first experiment, we vary the number of possible knapsack items from 40 to 200 in steps of 40, and for each case, ran each optimization algorithm for 2 seconds (Figure 9). While the results show a clear positive association between fitness and the problem’s complexity, this again can be misleading, as the fitness function evaluates based on the total value of the items placed in the knapsack (which will obviously scale with the number of possible items). However, it appears that the MIMIC curve begins to diverge from the others as it approaches the higher item counts; this suggests that MIMIC’s solution space optimization gives it an advantage over the other algorithms. Figure 9. Optimization algorithm fitness compared to Knapsack problem item count (N). Using hyperparameters listed in Table 6 and 2 seconds of iterations. Finally, we ran our efficiency experiment, using a fixed item count (N) of 40 over 5,000 iterations (Figure 10). Here, Knapsack dominates the other three algorithms, quickly converging to a fitness result of roughly 4,000. Interestingly, all the algorithms converge rather fast, suggesting this problem consists of>