Knapsack Problem

  1from deap_er import creator
  2from deap_er import tools
  3from deap_er import base
  4import string
  5import random
  6
  7
  8random.seed(1234)  # disables randomization
  9
 10IND_INIT_SIZE = 5
 11MAX_ITEM = 50
 12MAX_WEIGHT = 50
 13NBR_ITEMS = 20
 14NAME_LEN = 3
 15
 16items = dict()
 17
 18
 19def create_items():
 20    alphabet = list(string.ascii_uppercase)
 21    for _ in range(NBR_ITEMS):
 22        while True:
 23            name = ''.join(random.choice(alphabet) for _ in range(NAME_LEN))
 24            if name not in items:
 25                break
 26        weight = random.randint(1, 10)
 27        value = random.uniform(0, 100)
 28        items.update(
 29            {name: (weight, value)}
 30        )
 31
 32
 33def evaluate(individual: set) -> tuple[int, int]:
 34    if len(individual) <= MAX_ITEM:
 35        _weight, _value = 0, 0
 36        for item in individual:
 37            _weight += items[item][0]
 38            _value += items[item][1]
 39        if _weight <= MAX_WEIGHT:
 40            return _weight, _value
 41    return 10000, 0
 42
 43
 44def mate(ind1: set, ind2: set) -> tuple[set, set]:
 45    temp = set(ind1)
 46    ind1 &= ind2
 47    ind2 ^= temp
 48    return ind1, ind2
 49
 50
 51def mutate(individual: set) -> tuple[set]:
 52    if random.random() < 0.5:
 53        if len(individual) > 0:
 54            items_ = sorted(tuple(individual))
 55            choice = random.choice(items_)
 56            individual.remove(choice)
 57    else:
 58        names = list(items.keys())
 59        individual.add(random.choice(names))
 60    return individual,  # The comma is essential here.
 61
 62
 63def setup():
 64    creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
 65    creator.create("Individual", set, fitness=creator.Fitness)
 66
 67    toolbox = base.Toolbox()
 68    toolbox.register("attr_item", random.choice, list(items.keys()))
 69    toolbox.register("individual", tools.init_repeat, creator.Individual, toolbox.attr_item, IND_INIT_SIZE)
 70    toolbox.register("population", tools.init_repeat, list, toolbox.individual)
 71    toolbox.register("mate", mate)
 72    toolbox.register("mutate", mutate)
 73    toolbox.register("select", tools.sel_nsga_2)
 74    toolbox.register("evaluate", evaluate)
 75
 76    return toolbox
 77
 78
 79def print_results(hof):
 80    best_ind = sorted(list(hof[-1]))
 81    best_weight, best_value = 0, 0
 82    for idx in best_ind:
 83        best_weight += items[idx][0]
 84        best_value += round(items[idx][1], 2)
 85
 86    keys = sorted(list(items.keys()))
 87    for key in tuple(keys):
 88        if key not in best_ind:
 89            keys.remove(key)
 90            keys.append(key)
 91
 92    print('\nAvailable items to choose from:')
 93    print('Names:\t\t' + '\t\t'.join([str(k) for k in keys]))
 94    print('Weights:\t' + '\t\t'.join([str(items[k][0]) for k in keys]))
 95    print('Values:\t\t' + '\t'.join([str(round(items[k][1], 2)) for k in keys]))
 96    print(f'\nItems chosen: {best_ind}')
 97    print(f'Total weight of chosen items: {best_weight}')
 98    print(f'Total value of chosen items: {best_value:.3f}.')
 99
100
101def main():
102    create_items()
103    toolbox = setup()
104    pop = toolbox.population(size=100)
105    hof = tools.ParetoFront()
106    args = dict(
107        toolbox=toolbox,
108        population=pop,
109        generations=50,
110        offsprings=100,
111        survivors=50,
112        cx_prob=0.5,
113        mut_prob=0.2,
114        hof=hof
115    )
116    tools.ea_mu_plus_lambda(**args)
117    print_results(hof)
118
119
120if __name__ == "__main__":
121    main()