Documentación automática

Módulos generales

Optimizar

Clase para utilizar como un modulo de optimizacion, los problemas se deben definir en la carpeta Problemas, cada problema debera tener definida dos clases, una generica para poder extraer las funciones del problema en orden y una clase que define al problema, el nombre del archivo debera ser igual al nombre de la clase que define al problema, esta segunda condicion tambien es necesaria para el caso de los algoritmos, los cuales se deben definir en la carpeta Algoritmos y mantener una estructura aproximada a los algoritmos ya definidos.

Algoritmos:

• “AFSA”
• “GA”

*Nota 1: En la carpeta config_files se pueden modificar los parametros para cada algoritmo, en la misma carpeta se pueden encontrar ejemplos para cada algoritmo.

*Nota 2: A la hora de cargar los parametros del GA, se deben escoger los operadores geneticos adecuadamente segun el tipo de problema, i.e., si el problema es combinatorio o si es continuo.

Ejemplos:

Para problemas combinatorios:

ga_operators=(“proportional_selection”,”ordered_crossover”,”swap_mutation”,”elitism”)

Para problemas continuos:

ga_operators=(“proportional_selection”,”heuristic_crossover”,”continuous_mutation”,”elitism”)

Problemas:

Combinatorios:

• “TSP” -> Travelling salesman problem
• “Nqns” -> N queens

*Nota 3: vector_len debe ser > 1, pues indica el numero de ciudades o reinas.

Continuos:

• “Ackley” -> Funcion Ackley
• “Rosenbrock” -> Funcion Rosenbrock
• “Rastrigin” -> Funcion Rastrigin

*Nota 4: Para dimension=3, se graficá la superficie en 3D, se recomienda un size_space bajo no mayor de 30 para apreciar mejor la grafica.

class Optimizar.Optimizar

Clase para definir al “modulo” Optimizar

procesar(fitness_data: List[float], best_finded: object, metrica: int, algoritmo: str) → None

Funcion de uso opcional, se utiliza para graficar la evolucion del fitness, especialmente util para comparar varios algoritmos, ver ejemplo en Ejecucion_multiple.py

Parámetros:

• fitness_data – Lista con la evolucion del fitness.
• best_finded – Objeto con la mejor solucion encontrada, actualmente sin uso.
• metrica – Unidad metrica para el eje de las X, actualmente iteraciones * poblacion.
• algoritmo – Nombre del algoritmo para la leyenda.

Devuelve:

None

static set_algorithm(class_object: str) → Tuple[Callable, str]

Funcion para establecer el algoritmo a utilizar, esta funcion puede ser llamada varias veces para instanciar varios algoritmos.

Parámetros:class_object – Nombre de la clase que define al algoritmo. Devuelve:Un Callable del algoritmo escogido, i.g., AFSA.AFSA, ademas, retorna le nombre del algoritmo.

static set_parameters(archivo: str = None) → Dict[str, float]

Funcion extraer los parametros de un archivo de texto.

Formato:

param1=value1 param2=value2 param3=value3

Parámetros:archivo – Nombre del archivo que contiene los parametros del algoritmo Devuelve:Diccionario con los parametros del algoritmo

static set_problem(elproblema: str, vector_len: int, size_space: int, dimension: int) → Any

Funcion para establecer el problema base y las funciones asociadas a la clase de dicho problema.

Parámetros:

• elproblema – Nombre de la clase que define al problema.
• vector_len – Tamaño del problema combinatorio ig. numero de ciudades para TSP.
• size_space – Espacio del problema, para ciertos problemas puede que no se use.
• dimension – Dimension del problema, i.g., 2 para TSP

Devuelve:

Diccionario con el problema base y las funciones de la clase del problema

Clase con métodos de uso general

Funciones de uso general, se puede heredar para los algoritmos o usar como modulo de funciones

class funciones_generales.General

Clase de funciones de uso general

static calcular_centroide(grupo: object, problema_base: List[Tuple[int, int]], vector_len: int, vecinos: List[Tuple[int, int]]) → List[Tuple[float, float]]

Metodo para calcular el centroide

Parámetros:grupo – Grupo de candidatos Devuelve:xc, el centroide

static calcular_vecinos(index: int, candidato: List[Tuple[float]], visual: int, grupo: List[object]) → List[object]

Metodo para calcular los vecinos dado el rango visual

Parámetros:

• index – Indice del pez actual
• candidato – candidato actual
• visual – Rango visual a utilizar para el calculo de los vecinos
• grupo – Grupo de candidatos

Devuelve:

vecinos, una lista con los vecinos obtenidos

static getbestsolution(soluciones: List[object], cantidad: int = 1) → object

Metodo para obtener la mejor solucion del grupo de soluciones actuales.

Parámetros:

• soluciones – Grupo de soluciones al que se le obtendra la mejor respuesta basado en el fitness
• cantidad – Numero de soluciones a retornar

Devuelve:

La mejor o mejores soluciones, ie. la solucion o soluciones con menor fitness

Algoritmos

Algoritmo de la escuela de peces artificiales

Algoritmo de escuela de peces artificiales (AFSA). Se puede utilizar por medio de la clase Optimizar, para mas detalles estudiar el ejemplo Ejecucion_simple.py o Ejecucion_multiple.py

*Nota 1: El AFSA se modifico ligeramente para el caso de los problemas continuos dado que esta planteado para problemas combinatorios, si se quiere un mejor desempeño para estos casos, se recomienda plantear el AFSA para problemas continuos.

class AFSA.AFSA(maxiteration: str = 5000, visual: str = 4, crowfactor: str = 0.83, n_fish: str = 10, step: str = 1, try_numbers: str = 10, problema: List[Tuple[int, int]] = None, funciones: List[Callable] = None)

Clase base de la escuela de peces artificiales, incluye los movimientos necesarios para el algoritmo.

empezar(queue: None = None, show_results: bool = True, position: int = 0) → Tuple[List[float], AFSA.Fish, int]

Empieza el proceso de optimizacion, hace el llamado para guardar el mejor pez despues de cada iteracion y llama a la funcion de imprimir respuesta.

Parámetros:

• queue – Variable de multiproceso (cola), se utiliza para devolver informacion al thread principal.
• show_results – Bandera para escoger el llamado a imprimir_respuesta().

Devuelve:

Lista con la evolucion del fitness, objeto Fish con la mejor solucion encontrada, numero de

operaciones realizadas (iteraciones * n_fish).

follow_behavior(index: int, fish: AFSA.Fish) → int

Se obtiene el mejor pez dentro de los vecinos del pez actual, se asigna su posicion en caso de que el fitness sea mejor y que no haya mucha congestion.

Parámetros:

• index – Indice del pez actual
• fish – Pez actual

Devuelve:

0, con fines de acabar la funcion

move_behavior_modificado(index: int, fish: AFSA.Fish) → int

Se modifico el move_behavior() original propuesto por Yun Cai (2010) el cual consistia en obtener una posicion random y sustituir la posicion del pez actual si dicha posicion generaba un mejor fitness.

Dado que en las pruebas este metodo no genero buenos resultados se opto por realizar un numero step de swaps entre posiciones random, el mejor valor conseguido para step fue de 1 y 2, para mayores valores de step, se tiende a generar una respuesta parecida al move_behavior() original, dado que se termina obteniendo una posicion random

Por otro lado, se agrego una version alterna en caso de que el problema a resolver sea de tipo continuo.

Parámetros:

• index – Indice del pez actual
• fish – Pez actual

Devuelve:

0, con fines de acabar la funcion

prey_behavior(index: int, fish: AFSA.Fish, visual: int) → int

Se escoge de manera random un pez vecino, si su fitness es mejor, la posicion del pez actual se reemplaza con la de dicho pez, este proceso se repite try_numbers veces.

Parámetros:

• index – Indice del pez actual
• fish – Pez actual
• visual – Rango visual del pez actual

Devuelve:

0, con fines de acabar la funcion

swarm_behavior(index: int, fish: AFSA.Fish) → int

Se calcula el centroide entre los vecinos, al pez actual se le asigna la posicion dada por el centroide si el fitness en dicha posicion es mejor y si la posicion no esta muy congestionada.

Parámetros:

• index – Indice del pez actual
• fish – Pez actual

Devuelve:

0, con fines de acabar la funcion

class AFSA.Fish(p: List[Tuple[float, float]], f: float)

Clase para definir los objetos tipo pez(Fish)

Algoritmo Genético

Algoritmo Genetico. Se puede utilizar por medio de la clase Optimizar, para mas detalles estudiar el ejemplo Ejecucion_simple.py o Ejecucion_multiple.py.

*Nota 1: A la hora de cargar los parametros del GA, se deben escoger los operadores geneticos adecuadamente segun el tipo de problema, i.e., si el problema es combinatorio o si es continuo.

Ejemplos:

Para problemas combinatorios:

ga_operators=(“proportional_selection”,”ordered_crossover”,”swap_mutation”,”elitism”)

Para problemas continuos:

ga_operators=(“proportional_selection”,”heuristic_crossover”,”continuous_mutation”,”elitism”)

class GA.Chromosome(p: List[Tuple[int, int]], f: float)

Clase para definir los objetos tipo cromosoma(Chromosome)

class GA.GA(maxgenerations: str = 1000, poppulation_size: str = 100, mutation_rate: str = 0.01, selection_rate: str = 0.5, ga_operators: str = ('proportional_selection', 'ordered_crossover', 'swap_mutation', 'elitism'), problema: List[Tuple[int, int]] = None, funciones: List[Callable] = None)

Clase base del Algoritmo Genetico, incluye los operadores geneticos necesarios para el algoritmo.

continuous_mutation(individuo: GA.Chromosome, mutation_rate: float = 0.01) → GA.Chromosome

Funcion para realizar mutacion agregando un valor random entre -1 y 1 si se cumple la probabilidad de que suceda dicha mutacion dado por el mutation_rate. Esta mutacion solo puede suceder a una posicion del genoma.

Parámetros:

• individuo – Cromosoma que posiblemente mutará.
• mutation_rate – Porcentaje relativo de mutaciones a realizar para una posicion en el genoma del cromosoma.

Devuelve:

Cromosoma mutado.

elitism(old_generation: List[GA.Chromosome]) → List[GA.Chromosome]

Funcion para reducir la poblacion basado en el principio de elitismo, donde solo los cromosomas con mejor fitness sobreviven. EL tamaño de la poblacion luego del crossover se reduce a al tamaño de la poblacion antes del crossover.

Parámetros:old_generation – Generation anterior + hijos generados del crossover Devuelve:Nueva generacion de un tamaño igual a population_size

empezar(queue: None = None, show_results: bool = True, position: int = 0) → Tuple[List[float], GA.Chromosome, int]

Empieza el proceso de optimizacion, hace el llamado para guardar el mejor cromosoma despues de cada iteracion y llama a la funcion de imprimir respuesta.

Parámetros:

• queue – Variable de multiproceso (cola), se utiliza para devolver informacion al thread principal.
• show_results – Bandera para escoger el llamado a imprimir_respuesta().

Devuelve:

Lista con la evolucion del fitness, objeto Chromosome con la mejor solucion encontrada, numero de

operaciones realizadas (iteraciones * population_size).

heuristic_crossover(parent1: GA.Chromosome, parent2: GA.Chromosome) → Tuple[GA.Chromosome, GA.Chromosome]

Funcion para calcular el crossover en el caso de problemas continuos. Se selecciona una posicion random dentro de la dimension del problema, luego, se modifica dicha posicion para el padre y para la madre tomando informacion de ambos y utilizando un factor beta que tomara valores entre 0 y 1.

Formula:

Padre Madre

P(N1, N2, N3,…, Nn) y M(N1, N2, N3,…, Nn)

Ni_pnew = Ni_p - beta*(Ni_p - Ni_m) Ni_mnew = Ni_m + beta*(Ni_p - Ni_m)

Con Ni como la posicion a modificar con i € Naturales y 0 <= i < dimension

Parámetros:

• parent1 – Cromosoma correspondiente al padre.
• parent2 – Cromosoma correspondiente a la madre.

Devuelve:

Cromosomas correspondientes a los hijos generados.

ordered_crossover(parent1: GA.Chromosome, parent2: GA.Chromosome) → Tuple[GA.Chromosome, GA.Chromosome]

Funcion para generar los hijos, quienes seran los candidatos a formar la siguiente generacion. El proceso consta de tomar dos puntos de cortes en el padre y la madre, la informacion rodeada de dichos cortes se preserva para para los hijos, y el resto se rellena de manera secuencial con la data faltante, si el corte es tomado del padre, el resto de la data se rellena con informacion de la madre, y viceversa.

Ejemplo: cuts = [2, 5)

padre 1 2 |3 4 5| 6 7 madre 5 6 |7 4 3| 2 1 ———————–

x x |3 4 5| x x x x |7 4 3| x x

child1 6 7 |3 4 5| 2 1 child2 1 2 |7 4 3| 5 6

Parámetros:

• parent1 – Cromosoma correspondiente al padre.
• parent2 – Cromosoma correspondiente a la madre.

Devuelve:

Cromosomas correspondientes a los hijos generados.

static proportional_selection(chromosomes: List[GA.Chromosome], max_value: float) → GA.Chromosome

Funcion para seleccionar los padres, los padres con un mejor fitness tienen una probabilidad mayor de ser escogidos.

Parámetros:

• chromosomes – Lista de cromosomas correspondiente a la generacion actual.
• max_value – sumatoria total de fitness de la generacion actual.

Devuelve:

Padre seleccionado.

swap_mutation(individuo: GA.Chromosome, mutation_rate: float = 0.01) → GA.Chromosome

Funcion para realizar mutacion por medio de un swap, dicho swap se ejecuta para cada posicion del genoma, si se cumple la probabilidad de que suceda dada por el mutation_rate.

Parámetros:

• individuo – Cromosoma que posiblemente mutará.
• mutation_rate – Porcentaje relativo de mutaciones a realizar por cada posicion en el genoma del cromosoma.

Devuelve:

Cromosoma mutado.

Problemas

Problema del agente viajero

Problema del agente viajero

class TSP.OrderedClassMembers

Meta clase para poder extraer funciones de manera ordenada

class TSP.TSP

Clase para definir el problema del agente viajero.

calcular_fitness(recorrido: List[Tuple[int, int]], _) → float

Metodo para calcular el fitness, para este problema de TSP se plantea como funcion fitness la suma de distancias euclidianas entre cada ciudad de manera secuencial partiendo de la ciudad fija y finalizando en la misma.

Parámetros:

• recorrido – Recorrido a seguir entre las ciudades.
• _ – None

Devuelve:

fitness

static crear_recorrido(cities: List[Tuple[int, int]]) → List[Tuple[int, int]]

Genera el recorrido a realizar

Parámetros:cities – Ciudades base menos la ciudad inicial, el recorrido de crea a partir de esta. Devuelve:recorrido random

distancia_euclidean

Metodo para el calculo de la distancia euclidiana

Parámetros:

• punto1 – se explica solo
• punto2 – se explica solo

Devuelve:

distancia entre el punto 1 y el punto 2

imprimir_respuesta(problema_base: List[Tuple[int, int]], bestfitnes: object, cola: None = None) → None

Metodo para imprimir una representacion de los resultados obtenidos

Parámetros:

• problema_base – Ciudades base y por tanto, el problema a resolver
• bestfitnes – objeto con el mejor fitness encontrado junto con la posicion para dicho fitness
• cola – Para determinar el mostrado de las figuras.

Devuelve:

None

ini_tsp(n_ciudades: int, size_space: int, dimension: int, _) → List[Tuple[int, int]]

Inicializa las ciudades base a resolver. La creacion de las ciudades posee dos formas, uno de manera random, una con forma de circunferencia + ruido, ademas, se agrega en comentarios un set de ciudades fijo para probar el algoritmo de manera mas consistente.

Parámetros:

• n_ciudades – Numero de ciudades a recorrer
• size_space – Tamaño del espacio en el que se ubican las ciudades ig. 100x100
• dimension – dimension del problema (x1, x2, x3,…,x_dimension)
• _ – None

Devuelve:

Las ciudades generadas

static points_on_circumference(center=(50, 50), r=40, n=20)

Metodo para general las ciudades en un patron circular

Parámetros:

• center – Centro de la circunferencia
• r – Radio de la circunferencia
• n – Numero de puntos, o sea, numero de ciudades

Devuelve:

ciudades generadas

Problema de las N reinas

Problema de las N reinas

class Nqns.Nqns

Clase para definir el problema de las N reinas.

static calcular_fitness(reinas_position: List[int], n_reinas: int) → int

Calculo del fitness para el problema de las N reinas.

Parámetros:

• reinas_position – Posicion actual en el tablero.
• n_reinas – Numero de reinas.

Devuelve:

fitness dado por el numero total de colisiones.

static crear_tablero(reinas: List[int]) → List[int]

Genera la respuesta inicial random.

Parámetros:reinas – Tablero base. Devuelve:Respuesta inicial random.

static imprimir_respuesta(tablero: List[int], mejor_posicion: object, cola: None = None) → None

Metodo para impirmir la mejor posicion en funcion del mejor fitness, ademas, grafica un tablero con la posicion de las reinas.

Parámetros:

• tablero – Problema base.
• mejor_posicion – Mejor posicion encontrada.
• cola – Para determinar el mostrado de las figuras.

Devuelve:

None

static ini_nqns(n_reinas: int, _, __, ___) → List[int]

Inicializa el tablero tomando el numero de reinas.

Parámetros:

• n_reinas – Numero de reinas.
• _ – None
• __ – None
• ___ – None

Devuelve:

lista desde 0 hasta n_reinas.

class Nqns.OrderedClassMembers

Meta clase para poder extraer funciones de manera ordenada

Función Ackley

Funcion Ackley

class Ackley.Ackley

Clase para definir el problema de la funcion Ackley.

static calcular_fitness_ackley(x: List[Tuple[float, float,...,dimension]], _) → float

Genera el valor f(x) correspondiente a la funcion Ackley.

Parámetros:

• x – Punto x que contiene (x1, x2, x3,…,x_n) con n = self.dimension
• _ – None

Devuelve:

Ackley(x)

crear_x(_) → List[Tuple[float, float,...,dimension]]

Genera un valor real aleatorio en el rango +/- size_space/2 de dimension igual a dimension.

Parámetros:_ – None Devuelve:valor real aleatorio.

imprimir_respuesta(_, mejor_posicion: object, cola: None = None) → None

Imprime la mejor respuesta encontrada, ademas, en caso de dimension=3 (self.dimension = 2), grafica la superficie en 3D y el punto encontrado.

Parámetros:

• _ – None
• mejor_posicion – Mejor valor encontrado para la funcion Ackley.
• cola – Para determinar el mostrado de las figuras.

Devuelve:

None

ini_funcionesmath(_, size_space: int, dimension: int, problema: str) → List[int]

Para guardar las variables necesarias para el resto de funciones.

Parámetros:

• _ – None
• dimension – Numero de demensiones a resolver.
• size_space – Tamaño del espacio.
• problema – Nombre del problema.

Devuelve:

Lista con len = 1 para establecer el problema como continuo.

class Ackley.OrderedClassMembers

Meta clase para poder extraer funciones de manera ordenada

Función Rosenbrock

Funcion Rosenbrock

class Rosenbrock.OrderedClassMembers

Meta clase para poder extraer funciones de manera ordenada

class Rosenbrock.Rosenbrock

Clase para definir el problema de la funcion Rosenbrock.

static calcular_fitness_rosen(x: List[Tuple[float, float,...,dimension]], _) → float

Genera el valor f(x) correspondiente a la funcion Rosenbrock.

Parámetros:

• x – Punto x que contiene (x1, x2, x3,…,x_n) con n = self.dimension
• _ – None

Devuelve:

Rosenbrock(x)

crear_x(_) → List[Tuple[float, float,...,dimension]]

Genera un valor real aleatorio en el rango +/- size_space/2 de dimension igual a dimension.

Parámetros:_ – None Devuelve:valor real aleatorio.

imprimir_respuesta(_, mejor_posicion: object, cola: None = None) → None

Imprime la mejor respuesta encontrada, ademas, en caso de dimension=3 (self.dimension = 2), grafica la superficie en 3D y el punto encontrado.

Parámetros:

• _ – None
• mejor_posicion – Mejor valor encontrado para la funcion Rosenbrock.
• cola – Para determinar el mostrado de las figuras.

Devuelve:

None

ini_funcionesmath(_, size_space: int, dimension: int, problema: str) → List[int]

Para guardar las variables necesarias para el resto de funciones.

Parámetros:

• _ – None
• dimension – Numero de demensiones a resolver.
• size_space – Tamaño del espacio.
• problema – Nombre del problema.

Devuelve:

Lista con len = 1 para establecer el problema como continuo.

Función Rastrigin

Funcion Rastrigin

class Rastrigin.OrderedClassMembers

Meta clase para poder extraer funciones de manera ordenada

class Rastrigin.Rastrigin

Clase para definir el problema de la funcion Rastrigin.

static calcular_fitness_rastrigin(x: List[Tuple[float, float,...,dimension]], _) → float

Genera el valor f(x) correspondiente a la funcion Rastrigin.

Parámetros:

• x – Punto x que contiene (x1, x2, x3,…,x_n) con n = self.dimension
• _ – None

Devuelve:

Rastrigin(x)

crear_x(_) → List[Tuple[float, float,...,dimension]]

Genera un valor real aleatorio en el rango +/- size_space/2 de dimension igual a dimension.

Parámetros:_ – None Devuelve:valor real aleatorio.

imprimir_respuesta(_, mejor_posicion: object, cola: None = None) → None

Imprime la mejor respuesta encontrada, ademas, en caso de dimension=3 (self.dimension = 2), grafica la superficie en 3D y el punto encontrado.

Parámetros:

• _ – None
• mejor_posicion – Mejor valor encontrado para la funcion Rastrigin.
• cola – Para determinar el mostrado de las figuras.

Devuelve:

None

ini_funcionesmath(_, size_space: int, dimension: int, problema: str) → List[int]

Para guardar las variables necesarias para el resto de funciones.

Parámetros:

• _ – None
• dimension – Numero de demensiones a resolver.
• size_space – Tamaño del espacio.
• problema – Nombre del problema.

Devuelve:

Lista con len = 1 para establecer el problema como continuo.