solver.py

import json
import random
import numpy as np
from deap import algorithms
from deap import base
from deap import creator
from deap import tools

class Evaluator(object):
    def __init__(self, items, goal):
        self.items = items
        self.goal = goal
    def __call__(self, candidate):
        total_price = 0

        for i in xrange(len(candidate)):
            total_price += candidate[i] * self.items[i]['price']

        if total_price > self.goal :
            overspending = total_price - self.goal
        else:
            overspending = 0

        return (overspending, total_price)

with open('items.json') as f:
    items = json.load(f)

with open('goal.json') as f:
    goal = json.load(f)

evaluator = Evaluator(items, goal)
upper_limit = 6

# Objectives are decreasing overspending and increasing total profit, in that
# order
creator.create('FitnessMulti', base.Fitness, weights=(-1, 1))
creator.create('Individual', list, fitness=creator.FitnessMulti)

toolbox = base.Toolbox()
toolbox.register('random_integer', lambda: random.randint(0, upper_limit))
toolbox.register('individual',
                 tools.initRepeat,
                 creator.Individual,
                 toolbox.random_integer,
                 n = len(items))
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
toolbox.register('evaluate', evaluator)
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutUniformInt, low=0, up=upper_limit, indpb=0.05)
toolbox.register('select', tools.selTournament, tournsize=3)

# random.seed(42)

NGEN = 1000
CXPB = 0.5
MUTPB = 0.2

pop = toolbox.population(n=100)
hof = tools.ParetoFront()

pop, log = algorithms.eaSimple(pop, toolbox,
                               cxpb=CXPB,
                               mutpb=MUTPB,
                               ngen=NGEN,
                               halloffame=hof,
                               verbose=True)

total_price = 0
best_solution = hof[0]

print 'Items ordered:'

for i in xrange(len(best_solution)):
    if best_solution[i] != 0:
        print '%dx %s' % (best_solution[i], items[i]['name'])
        total_price += best_solution[i] * items[i]['price']

print
print 'Total price: $%.2f' % total_price