• Genetic Algorithm

Challenge

Solve the knapsack problem with 1,000 items and with a weight limit of 50, in less than a second, with weights and values given between 1 and 30. Only the optimal solution is acceptable!

Features

  • an evolutionary approach to solve an NP-hard/NP-complete problem,
  • chromosome initialization via a greedy algorithm,
  • elitist selection strategy,
  • three different crossover strategies,
  • extremely low memory usage,
  • multithreaded computation,
  • a lot of performance tweaks here and there,
  • … in less than 200 lines of c++!

The algorithm uses ~1,1MB of memory for the 1,000 item, and still less than 3,5MB for the 10,000 item problem sets – compare it to the memory consumption of the dynamic programming approach of the problem. The average time needed to compute the optimum with 1,000 items and a limit of50 is 0.05s – that’s 1/20th of a second.

Download

Code

Feel free to fiddle around with the parameters to achieve better results at different, possibly harder problem sets!

How does it work?