import string
from deap_er import Fitness, Toolbox, creator, tools
tools.rng.seed(1234) # disables randomization
IND_INIT_SIZE = 5
MAX_ITEM = 50
MAX_WEIGHT = 50
NBR_ITEMS = 20
NAME_LEN = 3
items = {}
def create_items():
alphabet = list(string.ascii_uppercase)
for _ in range(NBR_ITEMS):
while True:
name = "".join(tools.rng.choice(alphabet) for _ in range(NAME_LEN))
if name not in items:
break
weight = tools.rng.randint(1, 10)
value = tools.rng.uniform(0, 100)
items.update({name: (weight, value)})
def evaluate(individual: set) -> tuple[int, int]:
if len(individual) <= MAX_ITEM:
_weight, _value = 0, 0
for item in individual:
_weight += items[item][0]
_value += items[item][1]
if _weight <= MAX_WEIGHT:
return _weight, _value
return 10000, 0
def mate(ind1: set, ind2: set) -> tuple[set, set]:
temp = set(ind1)
ind1 &= ind2
ind2 ^= temp
return ind1, ind2
def mutate(individual: set) -> tuple[set]:
if tools.rng.random() < 0.5:
if len(individual) > 0:
items_ = sorted(individual)
choice = tools.rng.choice(items_)
individual.remove(choice)
else:
names = list(items.keys())
individual.add(tools.rng.choice(names))
return (individual,) # The comma is essential here.
def setup():
creator.create_type("Fitness", Fitness, weights=(-1.0, 1.0))
creator.create_type("Individual", set, fitness=creator.Fitness)
toolbox = Toolbox()
toolbox.register("attr_item", tools.rng.choice, list(items.keys()))
toolbox.register(
"individual", tools.init_repeat, creator.Individual, toolbox.attr_item, IND_INIT_SIZE
)
toolbox.register("population", tools.init_repeat, list, toolbox.individual)
toolbox.register("mate", mate)
toolbox.register("mutate", mutate)
toolbox.register("select", tools.sel_nsga_2)
toolbox.register("evaluate", evaluate)
return toolbox
def print_results(hof):
best_ind = sorted(hof[-1])
best_weight, best_value = 0, 0
for idx in best_ind:
best_weight += items[idx][0]
best_value += round(items[idx][1], 2)
keys = sorted(items.keys())
for key in tuple(keys):
if key not in best_ind:
keys.remove(key)
keys.append(key)
print("\nAvailable items to choose from:")
print("Names:\t\t" + "\t\t".join([str(k) for k in keys]))
print("Weights:\t" + "\t\t".join([str(items[k][0]) for k in keys]))
print("Values:\t\t" + "\t".join([str(round(items[k][1], 2)) for k in keys]))
print(f"\nItems chosen: {best_ind}")
print(f"Total weight of chosen items: {best_weight}")
print(f"Total value of chosen items: {best_value:.3f}.")
def main():
create_items()
toolbox = setup()
pop = toolbox.population(size=100)
hof = tools.ParetoFront()
args = {
"toolbox": toolbox,
"population": pop,
"generations": 50,
"offsprings": 100,
"survivors": 50,
"cx_prob": 0.5,
"mut_prob": 0.2,
"hof": hof,
}
tools.ea_mu_plus_lambda(**args)
print_results(hof)
if __name__ == "__main__":
main()