Knapsack Problem: Inheriting from Set¶
Again for this example we will use a very simple problem, the 0-1 Knapsack. The purpose of this example is to show the simplicity of DEAP and the ease to inherit from anything else than a simple list or array.
Many evolutionary algorithm textbooks mention that the best way to have an
efficient algorithm is to have a representation close the problem. Here, what can
be closer to a bag than a set? Lets make our individuals inherit from the
set
class.
creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
creator.create("Individual", set, fitness=creator.Fitness)
That’s it. You now have individuals that are, in fact sets, they have the usual
attribute fitness
. The fitness is a
minimization of the first objective (the weight of the bag) and a maximization
of the second objective (the value of the bag). We will now create a
dictionary of 100 random items to map the values and weights.
# Create the item dictionary: item name is an integer, and value is
# a (weight, value) 2-tuple.
items = {}
# Create random items and store them in the items' dictionary.
for i in range(NBR_ITEMS):
items[i] = (random.randint(1, 10), random.uniform(0, 100))
We now need to initialize a population and the individuals therein. For this,
we will need a Toolbox
to register our generators since
sets can also be created with an input iterable.
toolbox = base.Toolbox()
toolbox.register("attr_item", random.randrange, NBR_ITEMS)
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_item, IND_INIT_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
Voilà! The last thing to do is to define our evaluation function.
def evalKnapsack(individual):
weight = 0.0
value = 0.0
for item in individual:
weight += items[item][0]
value += items[item][1]
if len(individual) > MAX_ITEM or weight > MAX_WEIGHT:
return 10000, 0 # Ensure overweighted bags are dominated
return weight, value
Everything is ready for evolution. Ho no wait, since DEAP’s developers are lazy, there is no crossover and mutation operators that can be applied directly on sets. Lets define some. For example, a crossover, producing two children from two parents, could be that the first child is the intersection of the two sets and the second child their absolute difference.
def cxSet(ind1, ind2):
"""Apply a crossover operation on input sets. The first child is the
intersection of the two sets, the second child is the difference of the
two sets.
"""
temp = set(ind1) # Used in order to keep type
ind1 &= ind2 # Intersection (inplace)
ind2 ^= temp # Symmetric Difference (inplace)
return ind1, ind2
A mutation operator could randomly add or remove an element from the set input individual.
def mutSet(individual):
"""Mutation that pops or add an element."""
if random.random() < 0.5:
if len(individual) > 0: # We cannot pop from an empty set
individual.remove(random.choice(sorted(tuple(individual))))
else:
individual.add(random.randrange(NBR_ITEMS))
return individual,
We then register these operators in the toolbox. Since it is a multi-objective
problem, we have selected the NSGA-II selection scheme :
selNSGA2()
toolbox.register("evaluate", evalKnapsack)
toolbox.register("mate", cxSet)
toolbox.register("mutate", mutSet)
toolbox.register("select", tools.selNSGA2)
From here, all that is left to do is either write the algorithm or use
provided in algorithms
. Here we will use the
eaMuPlusLambda()
algorithm.
def main():
NGEN = 50
MU = 50
LAMBDA = 100
CXPB = 0.7
MUTPB = 0.2
pop = toolbox.population(n=MU)
hof = tools.ParetoFront()
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean, axis=0)
stats.register("std", numpy.std, axis=0)
stats.register("min", numpy.min, axis=0)
stats.register("max", numpy.max, axis=0)
algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
halloffame=hof)
return pop, stats, hof
Finally, a ParetoFront
may be used to retrieve the best
non dominated individuals of the evolution and a
Statistics
object is created for compiling four
different statistics over the generations. The Numpy functions are registered
in the statistics object with the axis=0
argument to compute the
statistics on each objective independently. Otherwise, Numpy would compute
a single mean for both objectives.
The complete examples/%sga/knapsack.