a fast genetic algorithm for
the 0-1 knapsack problem
by károly zsolnai - firstname.lastname@example.org
this is a project for the following 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!
if you are curious about how an evolutionary approach could solve an np-hard/np-complete problem, this is the place for you. let's take a look at what it's capable of at the features and performance sections!
there was also a talk about genetic algorithms at BME CS you might be interested in reading. / hu: [pdf]
- 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 of 50 is 0.05s - that's 1/20th of a second!