/genetic-knapsack-problem

Heuristic and efficient approach of the famous knapsack problem

Primary LanguagePython

genetic-knapsack-problem

Heuristic and efficient approach of the famous knapsack problem

Usage

First, initialize a Population with the given knapsack items and the max value.

MAX_WEIGHT = 240
w = [20, 30, 40, 50, 60, 20, 70, 2, 100, 90, 80]
v = [17, 33, 8, 12, 36, 9, 30, 30, 50, 45, 22]
p = []

for (a, b) in zip(w, v):
    p.append({'weight': a, 'value': b})

population = Population(p, MAX_WEIGHT)

Then, apply the genetic algorithm by looping over and over during n generations:

for i in range(100):
    population.natural_selection()
    population.new_generation()
    population.c_fitness()
    population.evaluate()

For more details, do not hesitate to check the code.