import array import numpy as np import random from deap import algorithms, base, creator, tools #A continuación, se crea la matriz de costos/beneficios y la matriz de cobertura utilizando np.random.randint. #En este ejemplo, se utilizan 16 clientes y 10 servicios, pero esto puede ajustarse según el problema específico. # Definir la matriz de costos/beneficios y la matriz de cobertura num_servicios = 10 num_clientes = 64 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] #definiendo numero de individuos en la poblacion tam_poblacion = 200 #definiendo número de funciones objetivo num_func_objetivo = 2 distancia_max = 1000 #Valor en KM max_iteraciones = 20 #porcentaje de cruza p_crossover = 0.3 p_mutate = 0.7 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 if (distancia_matrix[vector[k]][k] <= distancia_max): Dmij = 1 suma = suma + (aux*Yij*Dmij) return suma 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==num_servicios): valido = True print("INDIVIDUO VALIDO:",matriz_cargas) input("") break else: print("SERVICIOS VALIDOS:",cont) valido = False return valido # 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 print("INICIALIZANDO EJECUCIÓN....") ''' En la línea "creator.create("FitnessMulti", base.Fitness, weights=(-1.0, -1.0))", los valores negativos (-1.0, -1.0) pasados como argumento a "weights" indican que se está maximizando ambas funciones objetivo. Si se quisiera minimizar ambas funciones objetivo, se utilizarían valores positivos en su lugar. El argumento "weights" indica la importancia relativa de cada función objetivo en el proceso de optimización multiobjetivo. En este caso, ambas funciones objetivo tienen el mismo peso (-1.0), lo que significa que son igualmente importantes. Si se quisiera dar más importancia a una de las funciones objetivo, se podría asignar un peso negativo mayor a esa función y un peso negativo menor a la otra función. ''' print("CREANDO INSTANCIA (base) DE ALGORITMO NSGA-II") creator.create("FitnessMulti", base.Fitness, weights=(-1.0, 1.0)) ''' Se crea la estructura del individuo: El individuo en NSGA-II es un vector de números reales. Para crear la estructura del individuo, se debe utilizar la clase base. En este caso, se está creando un nuevo tipo de objeto llamado "Individual" que es simplemente una lista, y también se está definiendo su atributo "fitness" como una instancia del tipo de objeto "FitnessMulti" que se creó previamente. Esto significa que cada individuo de la población tendrá asociado un valor de aptitud que se calculará utilizando el algoritmo NSGA-II. ''' creator.create("Individual", list, fitness=creator.FitnessMulti) ''' Se debe crear una población inicial de individuos para comenzar la evolución. Se puede utilizar el módulo tools para generar la población inicial. Aquí, se define una toolbox que contiene las funciones necesarias para crear la población inicial. La función attr_float se utiliza para generar valores aleatorios para los genes de los individuos. La función individual utiliza la función initRepeat para crear un individuo que consiste en una lista de dos valores flotantes. La función population utiliza la función initRepeat para crear una lista de individuos. ''' 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) #print("IMPRIMIENDO LOS VALORES DE LA TOOLBOX") #print("1---",toolbox.individual()) #print("POBLACION:",toolbox.population()) '''La primera línea utiliza la función tools.cxSimulatedBinaryBounded, que se usa para realizar el operador de cruzamiento simulado binario, con una distribución de probabilidad que se ajusta para mantener los valores de los genes dentro de ciertos límites. El parámetro eta representa la intensidad de la distribución de probabilidad utilizada para la generación de nuevos individuos cruzados. ''' toolbox.register("mate", tools.cxSimulatedBinaryBounded, eta=20.0, low=0, up=num_servicios-1) ''' La segunda línea utiliza la función tools.mutPolynomialBounded, que se utiliza para realizar el operador de mutación polinómica, donde cada gen del individuo tiene una cierta probabilidad de mutar, y los nuevos valores de los genes se generan utilizando una distribución de probabilidad polinómica que se ajusta para mantener los valores dentro de ciertos límites. El parámetro eta representa la intensidad de la distribución de probabilidad utilizada para la generación de nuevos valores de genes mutados. Los parámetros low y up representan los límites inferior y superior para los valores de los genes, y indpb representa la probabilidad de que un gen dado mute. La función mate se utiliza para realizar el cruzamiento entre dos individuos. La función mutate se utiliza para ''' toolbox.register("mutate", tools.mutPolynomialBounded, eta=20.0, low=-0, up=num_servicios-1, indpb=p_mutate) ''' La tercera línea utiliza la función tools.selNSGA2, que se utiliza para realizar la selección de individuos en la siguiente generación. Esta función implementa el algoritmo NSGA-II, que selecciona individuos en función de su dominancia y su distancia en el espacio de objetivos. ''' bandera_ciclos = 1 while (True): toolbox.register("select", tools.selNSGA2) toolbox.register("evaluate", evaluate) # Configuración de la población y del algoritmo pop = toolbox.population(n=tam_poblacion) algorithms.eaMuPlusLambda(pop, toolbox, mu=10, lambda_=tam_poblacion, cxpb=p_crossover, mutpb=p_mutate, ngen=max_iteraciones) # Imprimir los resultados front = tools.sortNondominated(pop, k=len(pop), first_front_only=True)[0] #for ind in front: # print(ind.fitness.values) #print("IMPRIMIENDO LOS VALORES DE POBLACION DE LA TOOLBOX") #print("POBLACION:",toolbox.population()) '''SE EVALUAN LAS SOLUCIONES PARA VER SI EXISTE AL MENOS UNA SOLUCION EN LA QUE SE ATIENDEN A TODOS LOS CLIENTES SIN EXCEDER LAS CAPACIDADES DE LOS SERVICIOS''' '''fitnesses = toolbox.map(toolbox.evaluate, pop) for ind, fit in zip(pop, fitnesses): ind.fitness.values = fit''' print("VALIDANDO QUE EXISTA AL MENOS UNA SOLUCION ACEPTABLE") if(existe_solucion(pop)): print("SOLUCION FACTIBLE ENCONTRADA") print("IMPRIMIENDO LOS VALORES DE POBLACION DE LA TOOLBOX") #print("POBLACION:",toolbox.population()) iteraciones = bandera_ciclos * max_iteraciones #print("NUMERO DE ITERACIONES:",iteraciones) break bandera_ciclos = bandera_ciclos + 1