# Knapshack problem

Drug discovery project is multi objective optimization process. It’s difficult to solve you know.
There are many approaches to solve the problem and one is genetic algorithm.
Recently, deap is active library of GA for python.
I used deap for knapsack problem.
You know….
the knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
From wikipedia.

Code is following. ( Almost same as default example code. )
Deap has default function for mutation and cross over. But following code use set for individual, so define cxSet / cxMut.

```import random
import numpy as np

from deap import algorithms
from deap import base, creator, tools

IND_INIT_SIZE = 5
MAX_ITEM = 50
MAX_WEIGHT = 50

random.seed( 123 )
items = {}
# itembox ( weight, price )
for i in range( NBR_ITEMS ):
items[ i ] = ( random.randint(1,10), random.uniform(0,100) )

creator.create( "Fitness", base.Fitness, weights=(-1.0,1.0) )
creator.create("Individual", set, fitness = creator.Fitness )

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 )

def evalKnapsack( individual ):
weight = 0.0
value = 0.0
for item in individual:
weight += items[ item ]
value += items[ item ]
if len( individual ) > MAX_ITEM or weight > MAX_WEIGHT:
return 10000, 0
return weight, value

def cxSet( ind1, ind2 ):
temp = set( ind1)
ind1 &= ind2
ind2 ^= temp
return ind1, ind2

def mutSet( individual ):
if random.random() < 0.5:
if len(individual)>0:
individual.remove( random.choice( sorted(tuple(individual)) ) )
else:
return individual,

toolbox.register("evaluate", evalKnapsack)
toolbox.register( "mate", cxSet )
toolbox.register( "mutate", mutSet )
toolbox.register( 'select', tools.selNSGA2 )

def main():
random.seed(123)
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", np.mean, axis=0)
stats.register("std", np.std, axis=0)
stats.register("min", np.min, axis=0)
stats.register("max", np.max, axis=0)

algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
halloffame=hof)

return pop, stats, hof
main()
```
```gen	nevals	avg                          	std                        	min                        	max
0  	50    	[  21.92        199.47169802]	[  6.24768757  63.6981168 ]	[ 10.          63.12779453]	[  36.          326.38666121]
..........
50 	88    	[  17.58        447.32874335]	[  11.69630711  180.42873947]	[ 0.  0.]                  	[  42.         706.3663599]
Out:
([{1, 2, 3, 4, 7, 8, 10, 13, 14, 15, 18},
{1, 2, 3, 4, 7, 8, 10, 13, 14, 15, 18},
........
{2, 8, 10, 13, 14, 15}],
```

Deap has many function. I try to use Deap more and more.