a fast genetic algorithm for
the 0-1 knapsack problem

by károly zsolnai - zsolnai@cs.bme.hu

 

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]

features

• 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++!

performance

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!