sughodke/knapsack.py

## knapsack.py
# SG: Modified to produce Markdown output
#
#    This file is part of DEAP.
#
#    DEAP is free software: you can redistribute it and/or modify
#    it under the terms of the GNU Lesser General Public License as
#    published by the Free Software Foundation, either version 3 of
#    the License, or (at your option) any later version.
#
#    DEAP is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
#    GNU Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with DEAP. If not, see <http://www.gnu.org/licenses/>.

import random

import numpy

from pprint import pprint

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

IND_INIT_SIZE = 5
MAX_ITEM = 50
MAX_WEIGHT = 50
NBR_ITEMS = 20

# To assure reproductibility, the RNG seed is set prior to the items
# dict initialization. It is also seeded in main().
random.seed(64)

# Create the item dictionary: item name is an integer, and value is
# a (weight, value) 2-uple.
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))

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

toolbox = base.Toolbox()

# Attribute generator
toolbox.register("attr_item", random.randrange, NBR_ITEMS)

# Structure initializers
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][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

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

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,

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

def main():
    random.seed(64)
    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

if __name__ == "__main__":
    pop, _, hof = main()
    print('# Items #')
    pprint(items)

    print('# Population #')
    pprint(pop)

    print('# Winners #')
    for i in hof:
        print(i)

## output.md

      
    Raw
  

              output.md
            
          
    gen	nevals	avg                          	std                        	min                        	max                          
0  	50    	[  22.78        210.00877715]	[  5.88316241  71.09309649]	[ 10.          49.69958685]	[  38.          345.35491309]
1  	87    	[   9.96        145.20790666]	[  10.61312395  139.1868852 ]	[ 0.  0.]                  	[  45.          414.48478381]
2  	91    	[  3.26        61.20087478]  	[   7.44797959  125.53892809]	[ 0.  0.]                  	[  28.          414.48478381]
3  	88    	[  4.6         84.51641114]  	[   8.57438044  140.51459866]	[ 0.  0.]                  	[  28.          414.48478381]
4  	92    	[  2.4         52.24310488]  	[   5.82065288  108.88598622]	[ 0.  0.]                  	[  28.          414.48478381]
5  	87    	[  3.66        74.97342258]  	[   6.99316809  127.02866009]	[ 0.  0.]                  	[  28.          414.48478381]
6  	82    	[   5.3         111.43072783]	[   7.61117599  142.76899122]	[ 0.  0.]                  	[  28.          414.48478381]
7  	90    	[  3.38        76.37304048]  	[   6.06593769  116.8118772 ]	[ 0.  0.]                  	[  28.          414.48478381]
8  	86    	[  3.12        71.66806998]  	[   6.50427552  126.61232639]	[ 0.  0.]                  	[  28.          414.48478381]
9  	89    	[  4.28        96.82282974]  	[   7.61587815  140.68614155]	[ 0.  0.]                  	[  28.          414.48478381]
10 	91    	[  4.66        94.20965502]  	[   8.72607586  154.59704209]	[ 0.  0.]                  	[  33.          436.40977463]
11 	94    	[  3.38        82.54801261]  	[   7.42937413  143.83372367]	[ 0.  0.]                  	[  34.         483.3208272]  
12 	92    	[   4.72        112.19978461]	[   8.5370721   164.14270307]	[ 0.  0.]                  	[  34.         483.3208272]  
13 	89    	[  4.14        95.86909694]  	[   8.66258622  165.78275753]	[ 0.  0.]                  	[  34.         483.3208272]  
14 	86    	[   5.7         125.59256851]	[  10.31552228  184.80667754]	[ 0.  0.]                  	[  38.        492.202995]    
15 	86    	[   9.02       201.1503762]  	[  11.73625153  198.65247411]	[ 0.  0.]                  	[  38.        492.202995]    
16 	90    	[   6.          121.10597089]	[  11.05621997  186.00117203]	[ 0.  0.]                  	[  38.        492.202995]    
17 	91    	[   7.02        145.26997395]	[  11.35163424  195.13724753]	[ 0.  0.]                  	[  38.        492.202995]    
18 	87    	[   8.88        176.19932087]	[  12.36064723  206.72218973]	[ 0.  0.]                  	[  38.        492.202995]    
19 	89    	[   9.          185.80512507]	[  13.14990494  205.56098522]	[ 0.  0.]                  	[  38.        492.202995]    
20 	90    	[  14.26        270.31330726]	[  14.86312215  209.42601383]	[ 0.  0.]                  	[  38.        492.202995]    
21 	89    	[  18.56        320.11359043]	[  16.31828422  199.16225476]	[ 0.  0.]                  	[  46.          504.68809431]
22 	92    	[  10.44        224.04582546]	[  13.46723431  208.40787182]	[ 0.  0.]                  	[  46.          504.68809431]
23 	89    	[   7.88        208.66031791]	[   9.97524937  203.26322025]	[ 0.  0.]                  	[  31.          551.23467984]
24 	88    	[   9.48        249.03636129]	[  10.43310117  198.35214182]	[ 0.  0.]                  	[  31.          551.23467984]
25 	89    	[   9.74        259.22144876]	[  10.21921719  193.68124563]	[ 0.  0.]                  	[  31.          551.23467984]
26 	86    	[  12.24        290.69068602]	[  11.2045705  198.7052511]  	[ 0.  0.]                  	[  32.          559.60127088]
27 	87    	[   6.12        200.12601646]	[   7.6305701   188.98511995]	[ 0.  0.]                  	[  32.          559.60127088]
28 	90    	[   5.46        173.68629391]	[   8.35035329  194.13713321]	[ 0.  0.]                  	[  32.          559.60127088]
29 	94    	[   5.14        153.60942869]	[   8.53465875  196.89251588]	[ 0.  0.]                  	[  32.          559.60127088]
30 	93    	[   5.7         160.04836138]	[   9.55667306  202.73012538]	[ 0.  0.]                  	[  36.          568.48343867]
31 	95    	[   5.7         175.36993944]	[   8.74585616  196.02530582]	[ 0.  0.]                  	[  36.          568.48343867]
32 	78    	[   5.74        175.66843167]	[   8.75856153  196.28166654]	[ 0.  0.]                  	[  36.          568.48343867]
33 	91    	[   6.72        192.14030284]	[   9.63335871  208.7809893 ]	[ 0.  0.]                  	[  36.          568.48343867]
34 	92    	[   7.28        196.69424357]	[  10.39815368  216.27735816]	[ 0.  0.]                  	[  36.          568.48343867]
35 	89    	[   8.02        231.63771291]	[   9.80711986  209.75037701]	[ 0.  0.]                  	[  36.          568.48343867]
36 	90    	[   8.04        232.59848901]	[   9.8080783   207.02589326]	[ 0.  0.]                  	[  36.          568.48343867]
37 	85    	[   8.72        254.17230119]	[   9.31244329  204.65321872]	[ 0.  0.]                  	[  36.          568.48343867]
38 	89    	[   7.48        207.61125864]	[   9.98847336  213.49904673]	[ 0.  0.]                  	[  36.          568.48343867]
39 	92    	[   9.36       245.9486636]  	[  11.3256523   215.87109513]	[ 0.  0.]                  	[  42.          637.31948207]
40 	92    	[  10.98        271.16188039]	[  12.40401548  223.61565328]	[ 0.  0.]                  	[  42.          637.31948207]
41 	93    	[  10.8         272.43239273]	[  12.13424905  220.99277855]	[ 0.  0.]                  	[  42.          637.31948207]
42 	91    	[  11.86        304.07117362]	[  12.03995017  211.20576324]	[ 0.  0.]                  	[  42.          637.31948207]
43 	93    	[  11.38       288.3292047]  	[  12.25706327  222.63153571]	[ 0.  0.]                  	[  42.          637.31948207]
44 	87    	[  11.62      302.244937]    	[  12.38691245  217.55803025]	[ 0.  0.]                  	[  42.          637.31948207]
45 	87    	[  11.7         297.43893553]	[  12.64634335  223.48730523]	[ 0.  0.]                  	[  42.          637.31948207]
46 	91    	[  16.7         368.89821598]	[  14.88925787  230.18959314]	[ 0.  0.]                  	[  47.          707.73092646]
47 	88    	[  15.02        344.98372128]	[  14.04776139  235.63811278]	[ 0.  0.]                  	[  47.          707.73092646]
48 	86    	[  12.66        307.94602816]	[  13.67422393  237.85697412]	[ 0.  0.]                  	[  47.          707.73092646]
49 	90    	[  15.78        366.45278023]	[  14.21870599  222.95780236]	[ 0.  0.]                  	[  47.          707.73092646]
50 	87    	[  16.92        386.82265016]	[  14.89005037  220.57801282]	[ 0.  0.]                  	[  47.          707.73092646]

Items

{0: (8, 12.48509930835593),
 1: (10, 40.396096956847295),
 2: (1, 20.351113369770758),
 3: (5, 70.41144439033413),
 4: (4, 69.86574666158654),
 5: (3, 7.981206373372229),
 6: (7, 44.003630577221465),
 7: (1, 8.366591038506865),
 8: (1, 92.7646786450061),
 9: (3, 10.541265149933377),
 10: (1, 95.00359117156347),
 11: (5, 21.924990817330915),
 12: (4, 8.882167797500228),
 13: (1, 76.96797658382238),
 14: (7, 89.16384444665715),
 15: (5, 74.23923323846317),
 16: (9, 42.688343941286256),
 17: (9, 30.701913496381728),
 18: (6, 68.83604339265639),
 19: (9, 17.89634902035938)}

Population

[Individual({3, 4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({3, 4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual(),
 Individual({2, 4, 7, 8, 10, 13, 15}),
 Individual({2, 4, 8, 10, 13, 14, 15, 18}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18}),
 Individual({4, 7, 8, 10, 12, 13, 14, 15, 16, 18}),
 Individual({3, 4, 6, 8, 9, 10, 13, 14, 15}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 18}),
 Individual(),
 Individual({10}),
 Individual({10}),
 Individual({2, 8, 10, 13}),
 Individual({8, 10, 4, 13}),
 Individual({8, 10}),
 Individual({8, 10, 13}),
 Individual({2, 4, 7, 8, 10, 13}),
 Individual({2, 4, 7, 8, 10, 13}),
 Individual({2, 4, 7, 8, 10, 13}),
 Individual({2, 4, 7, 8, 10, 13}),
 Individual({4, 8, 10, 13, 15}),
 Individual({4, 8, 10, 13, 14, 15, 18}),
 Individual({4, 7, 8, 9, 10, 13, 14, 15}),
 Individual({4, 7, 8, 9, 10, 13, 14, 15}),
 Individual({4, 7, 8, 9, 10, 13, 14, 15}),
 Individual({2, 4, 8, 10, 13, 15}),
 Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 18}),
 Individual({8, 10, 2, 13}),
 Individual({8, 10, 13}),
 Individual({8, 10, 4, 13}),
 Individual({4, 8, 10, 13, 15}),
 Individual({4, 8, 10, 13, 14, 15, 18}),
 Individual({2, 4, 8, 10, 13}),
 Individual({4, 7, 8, 10, 13, 14, 15}),
 Individual({4, 7, 8, 9, 10, 13, 14, 15}),
 Individual({4, 8, 9, 10, 13, 14, 15}),
 Individual({4, 8, 10, 13, 14, 15}),
 Individual({4, 8, 10, 13, 14, 15}),
 Individual({2, 4, 8, 10, 13}),
 Individual({4, 7, 8, 10, 13, 14, 15}),
 Individual(),
 Individual(),
 Individual(),
 Individual(),
 Individual(),
 Individual()]

Winners

Individual()
Individual({10})
Individual({8, 10})
Individual({8, 10, 13})
Individual({8, 10, 2, 13})
Individual({8, 10, 4, 13})
Individual({2, 4, 8, 10, 13})
Individual({2, 4, 7, 8, 10, 13})
Individual({4, 8, 10, 13, 15})
Individual({2, 4, 8, 10, 13, 15})
Individual({2, 4, 7, 8, 10, 13, 15})
Individual({4, 8, 10, 13, 14, 15})
Individual({4, 7, 8, 10, 13, 14, 15})
Individual({4, 8, 9, 10, 13, 14, 15})
Individual({4, 7, 8, 9, 10, 13, 14, 15})
Individual({4, 8, 10, 13, 14, 15, 18})
Individual({2, 4, 8, 10, 13, 14, 15, 18})
Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 18})
Individual({3, 4, 6, 8, 9, 10, 13, 14, 15})
Individual({4, 7, 8, 10, 12, 13, 14, 15, 16, 18})
Individual({4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18})
Individual({3, 4, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18})
	# SG: Modified to produce Markdown output
	#
	# This file is part of DEAP.
	#
	# DEAP is free software: you can redistribute it and/or modify
	# it under the terms of the GNU Lesser General Public License as
	# published by the Free Software Foundation, either version 3 of
	# the License, or (at your option) any later version.
	#
	# DEAP is distributed in the hope that it will be useful,
	# but WITHOUT ANY WARRANTY; without even the implied warranty of
	# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	# GNU Lesser General Public License for more details.
	#
	# You should have received a copy of the GNU Lesser General Public
	# License along with DEAP. If not, see <http://www.gnu.org/licenses/>.

	import random

	import numpy

	from pprint import pprint

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

	IND_INIT_SIZE = 5
	MAX_ITEM = 50
	MAX_WEIGHT = 50
	NBR_ITEMS = 20

	# To assure reproductibility, the RNG seed is set prior to the items
	# dict initialization. It is also seeded in main().
	random.seed(64)

	# Create the item dictionary: item name is an integer, and value is
	# a (weight, value) 2-uple.
	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))

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

	toolbox = base.Toolbox()

	# Attribute generator
	toolbox.register("attr_item", random.randrange, NBR_ITEMS)

	# Structure initializers
	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][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

	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

	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,

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

	def main():
	random.seed(64)
	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

	if __name__ == "__main__":
	pop, _, hof = main()
	print('# Items #')
	pprint(items)

	print('# Population #')
	pprint(pop)

	print('# Winners #')
	for i in hof:
	print(i)