Optimización heurística - Redes neuronales y algoritmos bio-inspirados
Parte 1: Optimización numérica
La optimización es un área de las matemáticas y la ciencia de la computación que se ocupa de encontrar el mejor valor posible para una función objetivo, sujeto a ciertas restricciones. El objetivo principal es encontrar la solución que maximice o minimice la función objetivo, dependiendo del problema. En este caso, realizaremos optimización sin restricciones, donde buscaremos puntos críticos de la función objetivo, en particular, su mínimo global a partir de su gradiente, y usando métodos más sofisticados como algoritmos genéticos. Las funciones a evaluar son objeto común de optimización debido a su comportamiento, estas son la función Rosenbrock y la función Six-Hump camel function. Se hará uso de diferentes métodos de optimización: Descenso por gradiente, algoritmos evolutivos y optimización de partículas.
Para los casos de estudio se determinan variables de inicialización aleatorias, bien sea en dos o tres dimensiones para ambas funciones, con la particularidad de que la función Six-Hump camel está definida en dos dimensiones.
Descenso por gradiente
En el primer método, correspondiente a la optimización de descenso por gradiente, haciendo uso de la librería SciPy, se crea una función con una sola entrada correspondiente a la dimensión de la función Rosenbrock. De acuerdo a la dimensión ingresada, si es dos o tres dimensiones, se halla el mínimo global dadas condiciones iniciales arbitrarias para las entradas X1, X2, X3, las cuales también serán almacenadas en una variable para la posterior visualización de los datos. El resultado y el numero de iteraciones se almacenan haciendo uso de una función callback. El callback es llamado en el final de cada iteración y se encarga de agregar a una lista el resultado y el número obtenido cada vez que se invoca. Para la visualización de los datos se recurre a los resultados, el numero de iteraciones y las condicione iniciales almacenadas previamente, y se realiza un gráfico en dos y tres dimensiones, donde para la tercera dimensión, es necesario tomar un X3 fijo, inicializado aleatoriamente.
Un proceso similar para el método de descenso por gradiente se hace en la función Six-hump camel, la cual no está incluida en la librería de Scipy, pero recurriendo al código fuente de dicha librería se tuvo un buen ejemplo para definir correctamente la función six_hump(x) de tal manera que la salida de esta fuera compatible con el resto de métodos de la librería Scipy.optimize. También fue necesario tener la consideración de que está definida en dos dimensiones. El resto del proceso para este método es análogo a la función Rosenbrock: Se inicializan las entradas X1, X2 de manera aleatoria, se almacenan las iteraciones y resultados para su posterior visualización.
Algoritmo evolutivo
El algoritmo evolutivo emula la evolución biológica, partiendo de una determinada población, en este caso de 2 individuos, se busca la solución óptima, estableciendo un límite de 200 generaciones, 20 soluciones por población y 2 genes, que mutarán aleatoriamente en cada generación, y estos pueden tomar valores entre -10 y 10. Nuestra función fitness es el negativo de las funciones Rosen y six_hump ya que consiste en un problema de minimización. El método de selección de padres es steady-state-selection, que consiste en seleccionar los peores individuos y los reemplaza por los descendientes para mejorar el resultado posterior. Dados estos hiperparámetros al algoritmo, se crea la instancia y se almacenan los resultados.
A partir de la figura 6 podemos observar la evolución a lo largo de la optimización y ver qué tal se ajusta el fitness a nuestro objetivo.
Los genes corresponden a los resultados, en este histograma encontramos que la población se localiza alrededor del mínimo local, indicando que la optimización fue exitosa.
Finalmente, para el método Particle Swarm Optimization (PSO), se emula un enjambre similar al de unas aves buscando alimento, donde se crea un diccionario de opciones para controlar la velocidad de las particulas, donde c1 y c2 corresponden a las velocidades con las que se dirigen a las posiciones locales y globales respectivamente. Luego, los límites para las variables X, e Y se escogen entre -2,2 y -1,1. Con esto, creamos 100 particulas moviéndose en dos dimensiones, para finalmente ejecutar la simulación y almacenar los resultados para su visualiación.
El fitness muestra una convergencia increíblemente rápida, a comparación de los otros métodos estudiados.
Es de destacar los valores de c1,c2 y w los cuales deben ser escogidos análizando la función y su comportamiento para no caer en mínimos locales.
Discusión:
En cuanto a la función Rosenbrock se puede encontrar una convergencia rápida por el método de descenso por gradiente. Se puede intuir que es dado a su comportamiento y su característica 'banana' que hace fácil la tarea de localizar puntos mínimos no sólo a simple vista, sino también por métodos numéricos. Si bien la convergencia por todos los algoritmos y métodos planteados fue rápida, el descenso por gradiente brilla por su rapidez en la ejecución y eficacia al encontrar el mínimo global para funciones simples que no posean un gran número de mínimos locales. Por otro lado, los métodos heurísticos tuvieron un comportamiento más variable, sujeto a aleatoriedad en sus inicializaciones e iteraciones, lo que podía llegar a afectar el proceso de optimización, pudiendo dar pie a convergencias en mínimos locales. A pesar de esta particularidad, contrario a lo que el lector pueda llegar a intuir, los métodos heurísticos se destacaron en la función de las seis jorobas, donde la convergencia fue más rápida, siempre y cuando se escojan hiperparámetros adecuados. A partir de estos resultados, se puede concluir que el método descenso por gradiente es efectivo para funciones simples, y por otro lado, los métodos heurísticos, bien elaborados, ofrecen una convergencia rápida para funciones más complejas que puedan llegar a presentar un mayor número de mínimos locales.
Parte 2: Optimización combinatoria
El problema del vendedor viajante es un famoso problema de optimización combinatoria que, en esencia, consiste en determinar la ruta más corta posible que un vendedor ambulante puede tomar para visitar un conjunto de ciudades exactamente una vez y luego regresar a su ciudad de origen. La tarea es encontrar el recorrido que minimice la distancia total recorrida. Para el presente caso de estudio se busca hacer una modificación, ya que el interés principal no es encontrar un recorrido el cual minimice la distancia, sino un recorrido que minimice el costo. Como método de solución a este problema se abordaran 2 enfoques bio-inspirados. El método asociado a los algoritmos de colonias de hormigas y otro asociado a los algoritmos genéticos
El algoritmo de colonias de hormigas (ACO) es una metaheurística bio-inspirada que se basa en el comportamiento de las hormigas para encontrar soluciones óptimas o aproximadas a problemas complejos. Se inspira en la capacidad de las hormigas para encontrar la ruta más corta entre su nido y una fuente de alimento, utilizando rastros de feromonas como guía. En relación a la problemática establecida se tiene que con esta aproximación se puede encontrar la ruta mas optima que debe recorrer un vendedor para visitar cada una de las quine (15) ciudades y así reducir los costos lo máximo posible. Para esto se comienza definiendo una matriz 15x15 (Tabla. 1) en la que se encontraran consignadas las distancias entre cada una de las ciudades. Dado que se parte del supuesto que la distancia a recorrer entre ciudad A y ciudad B es igual que la distancia a recorrer entre ciudad B y ciudad A, se obtiene una matriz simétrica con valores en la diagonal igual a cero (distancia entre una misma ciudad), por lo que solo es de interés una de las triangulaciones de la matriz, lo que reduce considerablemente el costo computacional a la hora de resolver el problema.