import array import numpy as np import random from deap import algorithms, base, creator, tools num_servicios = 10 num_clientes = 64 tam_poblacion = 100000 #definiendo número de funciones objetivo num_func_objetivo = 2 distancia_max = 1000.0 #Valor en KM max_iteraciones = 20 #porcentaje de cruza p_crossover = 0.99 p_mutate = 0.01 distancia_matrix = [ [0.450,0.450,0.450,0.450,37.5,37.5,37.5,37.5,34.6,34.6,34.6,34.6,40.4,40.4,40.4,40.4,25,25,25,25,28.6,28.6,28.6,28.6,40.1,40.1,40.1,40.1,37.6,37.6,37.6,37.6,39.3,39.3,39.3,39.3,36.9,36.9,36.9,36.9,33.1,33.1,33.1,33.1,31.7,31.7,31.7,31.7,43.3,43.3,43.3,43.3,17.2,17.2,17.2,17.2,37.6,37.6,37.6,37.6,12.7,12.7,12.7,12.7], [35.1,35.1,35.1,35.1,24.8,24.8,24.8,24.8,14.9,14.9,14.9,14.9,0.4,0.4,0.4,0.4,13.4,13.4,13.4,13.4,16.4,16.4,16.4,16.4,6.8,6.8,6.8,6.8,23.5,23.5,23.5,23.5,24.7,24.7,24.7,24.7,22.6,22.6,22.6,22.6,5.5,5.5,5.5,5.5,32.9,32.9,32.9,32.9,30.2,30.2,30.2,30.2,18.4,18.4,18.4,18.4,23.3,23.3,23.3,23.3,27,27,27,27], [24.9,24.9,24.9,24.9,18,18,18,18,16,16,16,16,11.7,11.7,11.7,11.7,5.1,5.1,5.1,5.1,9.9,9.9,9.9,9.9,17.3,17.3,17.3,17.3,23.2,23.2,23.2,23.2,18.2,18.2,18.2,18.2,16,16,16,16,10.2,10.2,10.2,10.2,32.5,32.5,32.5,32.5,23.5,23.5,23.5,23.5,7.9,7.9,7.9,7.9,22.9,22.9,22.9,22.9,15.8,15.8,15.8,15.8], [34,34,34,34,17.7,17.7,17.7,17.7,8.6,8.6,8.6,8.6,5.2,5.2,5.2,5.2,8.6,8.6,8.6,8.6,9.7,9.7,9.7,9.7,8.3,8.3,8.3,8.3,24.3,24.3,24.3,24.3,20.8,20.8,20.8,20.8,18.7,18.7,18.7,18.7,0.550,0.550,0.550,0.550,33.7,33.7,33.7,33.7,26.3,26.3,26.3,26.3,17.1,17.1,17.1,17.1,23.8,23.8,23.8,23.8,24.5,24.5,24.5,24.5], [31.1,31.1,31.1,31.1,41.7,41.7,41.7,41.7,35.7,35.7,35.7,35.7,30.4,30.4,30.4,30.4,33.6,33.6,33.6,33.6,33.4,33.4,33.4,33.4,38.3,38.3,38.3,38.3,9.5,9.5,9.5,9.5,41.7,41.7,41.7,41.7,39.5,39.5,39.5,39.5,31,31,31,31,0.170,0.170,0.170,0.170,47.1,47.1,47.1,47.1,24,24,24,24,12.8,12.8,12.8,12.8,34.9,34.9,34.9,34.9], [42.7,42.7,42.7,42.7,7.7,7.7,7.7,7.7,15.9,15.9,15.9,15.9,30.6,30.6,30.6,30.6,19.5,19.5,19.5,19.5,14.7,14.7,14.7,14.7,30.5,30.5,30.5,30.5,43.9,43.9,43.9,43.9,6,6,6,6,7.9,7.9,7.9,7.9,26.6,26.6,26.6,26.6,47.2,47.2,47.2,47.2,0.35,0.35,0.35,0.35,25.4,25.4,25.4,25.4,43.6,43.6,43.6,43.6,34.5,34.5,34.5,34.5], [16.3,16.3,16.3,16.3,18.3,18.3,18.3,18.3,19.6,19.6,19.6,19.6,16.9,16.9,16.9,16.9,9.5,9.5,9.5,9.5,13.5,13.5,13.5,13.5,23.2,23.2,23.2,23.2,21.2,21.2,21.2,21.2,22.1,22.1,22.1,22.1,19.6,19.6,19.6,19.6,17.5,17.5,17.5,17.5,24,24,24,24,27.2,27.2,27.2,27.2,2.1,2.1,2.1,2.1,21,21,21,21,9.1,9.1,9.1,9.1], [18.9,18.9,18.9,18.9,19.4,19.4,19.4,19.4,17.2,17.2,17.2,17.2,15.1,15.1,15.1,15.1,7.2,7.2,7.2,7.2,11.1,11.1,11.1,11.1,21.4,21.4,21.4,21.4,20.8,20.8,20.8,20.8,19.7,19.7,19.7,19.7,17.3,17.3,17.3,17.3,15.7,15.7,15.7,15.7,23.6,23.6,23.6,23.6,24.9,24.9,24.9,24.9,1.6,1.6,1.6,1.6,20.6,20.6,20.6,20.6,12.5,12.5,12.5,12.5], [31.9,31.9,31.9,31.9,37.6,37.6,37.6,37.6,27.3,27.3,27.3,27.3,22,22,22,22,25.2,25.2,25.2,25.2,29.3,29.3,29.3,29.3,25.7,25.7,25.7,25.7,5.4,5.4,5.4,5.4,37.9,37.9,37.9,37.9,35.4,35.4,35.4,35.4,22.6,22.6,22.6,22.6,13.7,13.7,13.7,13.7,43.1,43.1,43.1,43.1,20,20,20,20,1.2,1.2,1.2,1.2,29.6,29.6,29.6,29.6], [12.7,12.7,12.7,12.7,27.9,27.9,27.9,27.9,25.7,25.7,25.7,25.7,25.8,25.8,25.8,25.8,15.7,15.7,15.7,15.7,19.6,19.6,19.6,19.6,31.3,31.3,31.3,31.3,32.1,32.1,32.1,32.1,28.2,28.2,28.2,28.2,25.7,25.7,25.7,25.7,27.5,27.5,27.5,27.5,24.2,24.2,24.2,24.2,33.3,33.3,33.3,33.3,9.4,9.4,9.4,9.4,31.8,31.8,31.8,31.8,1.6,1.6,1.6,1.6] ] # Matriz de costos, el costo es la distancia en kilometros solicitudes_matrix = [ [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124], [8204,8204,8204,8203,2062,2062,2062,2062,2026,2026,2026,2027,1687,1687,1687,1687,1630,1630,1630,1631,1067,1067,1067,1068,951,951,951,950,921,921,921,921,861,861,861,861,688,688,688,688,661,661,661,662,531,531,531,529,321,321,321,322,156,156,156,157,136,136,136,135,125,125,124,124] ] max_capacidades = [28512,18144,10692,9072,7128,6804,5346,4536,3564,3402] #Capacidad máxima de los modulos del INEs max_capacidades2 = [28512,18144,10692,9072,7128,6804,5346,4536,3564,3402] def funcion1(vector): #Funcion que minimiza el costo total Min (f1) = dijαXij suma = 0 #asignaciones = np.zeros(len(clientes)) for k in range(0,len(vector)): aux = distancia_matrix[vector[k]][k] alpha =1 X_ij = 1 aux = aux * alpha * X_ij suma = suma + aux return suma def funcion2(vector): #Función que maximiza las capacidades de atencion de los servicios aux_cap = max_capacidades suma = 0 for k in range(0,len(vector)): aux = solicitudes_matrix[vector[k]][k] aux_cap[vector[k]] = aux_cap[vector[k]] - aux Yij = 0 Dmij = 0 if (aux_cap[vector[k]] >= 0): Yij = 1 else: Yij = 0 if (distancia_matrix[vector[k]][k] <= distancia_max): Dmij = 1 else: Dmij = 0 suma = suma + (aux*Yij*Dmij) return suma # Definir la función de evaluación def evaluate(individual): individual = [round(x) for x in individual] #print("Individuo:",individual) #input("") #Evaluando cada funcion objetivo #Evaluando respecto a funcion objetivo 1 res1 = funcion1(individual) #Evaluando respecto a funcion objetivo 2 res2 = funcion2(individual) return res1,res2 def existe_solucion(poblacion): #haciendo enteros los valores de la poblacion inicial for i in range(0, len(poblacion)): poblacion[i] = [int(round(x)) for x in poblacion[i]] aux_cap = max_capacidades2 for individuo in poblacion: matriz_cargas = [[] for i in range(num_servicios) ] print("Individuo evaluado: ",individuo) for i in range(0,len(individuo)): servicio_asignado = individuo[i] carga_asignada = solicitudes_matrix[servicio_asignado][i] matriz_cargas[servicio_asignado].append(carga_asignada) print("Matriz cargas:",matriz_cargas) print("Longitud Matriz cargas:",len(matriz_cargas)) #Sumando las peticiones realizadas a cada modulo para verificar que no se exceda la capacidad cont = 0 for j in range(0,len(matriz_cargas)): carga_servicio = sum(matriz_cargas[j]) print("Carga solicitada al servicio: ",carga_servicio) print("Capacidad mx del servicio: ",aux_cap[j]) #input("") if(carga_servicio <= aux_cap[j]): cont = cont + 1 if(cont>9): valido = True print("INDIVIDUO VALIDO:",matriz_cargas) print("SERVICIOS VALIDOS:",cont) input("") break else: print("SERVICIOS VALIDOS:",cont) valido = False return valido creator.create("FitnessMulti", base.Fitness, weights=(-1.0, 1.0)) creator.create("Individual", list, fitness=creator.FitnessMulti) toolbox = base.Toolbox() toolbox.register("attr_int", random.randint, 0, num_servicios-1) #toolbox.register("attr_int", random.uniform, 0, 9): Se registra la función random.uniform de la biblioteca estándar de Python como una herramienta de DEAP. Esta función genera números aleatorios de punto flotante entre -5.0 y 5.0. La herramienta se registra bajo el nombre "attr_int". toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_int, num_clientes) #toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, 2): Se registra la función tools.initRepeat de DEAP como una herramienta para inicializar individuos. Esta función toma tres argumentos: el tipo de individuo que se quiere crear (en este caso, el tipo creado anteriormente con creator.Individual), la herramienta para crear genes (en este caso, la herramienta registrada anteriormente como "attr_float"), y el número de genes que se quiere tener en el individuo (en este caso, 64 clientes). toolbox.register("population", tools.initRepeat, list, toolbox.individual, n=tam_poblacion) #toolbox.register("mate", tools.cxSimulatedBinaryBounded, eta=7.0, low=0, up=num_servicios-1, cxpb=p_crossover) toolbox.register("evaluate", evaluate) toolbox.register("mate", tools.cxSimulatedBinaryBounded, eta=20.0, low=0, up=num_servicios-1) #toolbox.register("mutate", tools.mutGaussian, eta=7.0, low=0, up=num_servicios-1, indpb=p_mutate) toolbox.register("mutate", tools.mutUniformInt, eta=20.0, low=0, up=num_servicios-1, indpb=1.0/tam_poblacion) toolbox.register("select", tools.selNSGA2, nd="standard", fit_attr='fitness', k=100) population_size = 100000 max_generations = 10 population = toolbox.population(n=population_size) # Ejecutar el algoritmo NSGA-II '''for gen in range(population_size): offspring = algorithms.varAnd(population, toolbox, cxpb=0.9, mutpb=0.1) fits = toolbox.map(toolbox.evaluate, offspring) for fit, ind in zip(fits, offspring): ind.fitness.values = fit population = toolbox.select(offspring, k=len(population))''' #algorithms.eaMuPlusLambda(population, toolbox, mu=50, lambda_=100, mutpb=p_mutate, cxpb=p_crossover, ngen=50) for generation in range(max_generations): #while (True): # Evalúa la aptitud de cada individuo en la población fitnesses = toolbox.map(toolbox.evaluate, population) for ind, fit in zip(population, fitnesses): ind.fitness.values = fit print("VALIDANDO QUE EXISTA AL MENOS UNA SOLUCION ACEPTABLE") if(existe_solucion(population)): print("SOLUCION FACTIBLE ENCONTRADA") print("IMPRIMIENDO LOS VALORES DE POBLACION DE LA TOOLBOX") print(population) else: print("NINGUNA SOLUCION FACTIBLE ENCONTRADA") print(population)