In this repository, I implement several heuristic and metaheuristic algorithms to solve a random instance of the knapsack problem. In this particular instance of the problem, I used 150 items to choose from and a maximum weight limit of 1500 kg for the knapsack. The objective is to maximize the total value in the knapsack. The weights and values of each item is randomly generated using Python's random library.

The algorithms I implement are -

1. Neighborhood-Based Heuristics
   • Hill Climbing and variations (HC)
     • Steepest ascent
     • First accept
     • Random restarts
     • Random walk
     • Local beam search
     • Stochastic beam search
   • Simulated Annealing (SA)
   • Variable Neighborhood Search (VNS)
     • Using variable neighborhhod descent (VND)
     • Using HC with steepest ascent
     • Implementing reduced variable neighborhood search (RVNS)
   • Tabu Search (TS)
     • Implementing long-term memory
     • Implementing path relinking
   • Guided Local Search
2. Population-Based Metaheuristics
   • Genetic Algorithm (GA)
   • Particle Swarm Optimization (PSO)

This readme page is under construction and I have not implemented every algorithm yet. So here is an incomplete table of results -

In the table above, Algorithm column is name of the algorithm, Iteration column is the number of iterations it took to find the solution, Time column is the program running time in seconds, Items column is the number of items chosen in the optimal solution, Weight column is the total weight in kg of the knapsack after choosing the items in optimal solution and finally, the Objective column is the total value in dollar of all the items selected in optimal solution, i.e. the quantity we're trying to maximize in this problem.