# DEAP_generico.py
#
# esempio di utilizzo della libreria per la computazione genetica evolutiva
# dei problemi denominata DEAP.
# in questo caso ho utilizzato lo scheletro della risoluzione di un
# problema generico per risolvere il problema di ottimizzazione
# noto come Knapsack Problem.
# documentazione su : https://deap.readthedocs.io/en/master/index.html
#
# by Andrea Bianchini (2021)
import random
from deap import base
from deap import creator
from deap import tools
IND_SIZE = 50
C = 10000
MIN_WEIGHT = int(C*0.01)
MAX_WEIGHT = int(C*0.07)
MAX=0
sol=[]
items=[random.randint(MIN_WEIGHT,MAX_WEIGHT) for _ in range(IND_SIZE)]
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
toolbox = base.Toolbox()
# Attribute generator
toolbox.register("attr_bool", random.randint, 0, 1)
# Structure initializers
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_bool, IND_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalOneMax(individual):
global sol
global MAX
e1 = sum([items[i]*individual[i] for i in range(len(individual))])
if e1>MAX and e1<=C:
MAX = e1
sol=individual
return e1,
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
summa=0
def main():
global summa
pop = toolbox.population(n=300)
# Evaluate the entire population
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
# CXPB is the probability with which two individuals
# are crossed
#
# MUTPB is the probability for mutating an individual
CXPB, MUTPB = 0.5, 0.2
# Extracting all the fitnesses of
fits = [ind.fitness.values[0] for ind in pop]
# Variable keeping track of the number of generations
g = 0
# Begin the evolution
while max(fits) < C and g < 1000:
# A new generation
g = g + 1
print("-- Generation %i --" % g)
# Select the next generation individuals
offspring = toolbox.select(pop, len(pop))
# Clone the selected individuals
offspring = list(map(toolbox.clone, offspring))
# Apply crossover and mutation on the offspring
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CXPB:
toolbox.mate(child1, child2)
del child1.fitness.values
del child2.fitness.values
for mutant in offspring:
if random.random() < MUTPB:
toolbox.mutate(mutant)
del mutant.fitness.values
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
pop[:] = offspring
# Gather all the fitnesses in one list and print the stats
fits = [ind.fitness.values[0] for ind in pop]
length = len(pop)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print(" Min %s" % min(fits))
print(" Max %s" % max(fits))
print(" Avg %s" % mean)
print(" Std %s" % std)
if max(fits) <=C and summa<max(fits):
summa = max(fits)
main()
print()
print("Soluzione ottima = %d" %MAX)
print("Lista items completa :")
print(items)
print("Lista items soluzione :")
osol = [items[i]*sol[i] for i in range(IND_SIZE)]
print(osol)Esempio:
Soluzione ottima = 10000
Lista items completa :
[481, 167, 361, 111, 670, 602, 119, 331, 654, 155, 400, 227, 651, 531, 413, 134, 409, 140, 488, 457, 495, 628, 153, 632, 327, 159, 593, 633, 682, 392, 368, 526, 599, 478, 408, 315, 466, 582, 302, 172, 427, 173, 551, 673, 272, 158, 502, 269, 685, 588]
Lista items soluzione :
[0, 0, 361, 0, 670, 0, 0, 331, 654, 0, 0, 0, 651, 0, 0, 0, 409, 140, 488, 0, 0, 628, 0, 632, 327, 0, 593, 0, 682, 0, 368, 0, 0, 478, 0, 315, 0, 582, 0, 172, 427, 0, 551, 0, 272, 0, 0, 269, 0, 0]
>>>