Autores:
Mtro. Óscar A. González-Sánchez*, Dr. Erik Cuevas y Dr. Daniel Zaldívar
Los humanos tenemos un impulso natural hacia la optimización de nuestras actividades. Esta característica se remonta a nuestros orígenes y surge como una estrategia evolutiva para asegurar nuestra supervivencia. Desde los primeros homínidos que buscaban cazar la mayor cantidad de alimentos con el mínimo esfuerzo y la mayor seguridad posible, hasta las sociedades modernas que desean maximizar los rendimientos con la menor inversión y mínimos riesgos. En su esencia, la optimización surge como un medio para encontrar la mejor solución entre un conjunto de opciones [1], para muchos casos, esto implica hacer más, con menos.
Fig. 1 Ilustración de un académico analizando las propiedades de una función matemática.
Así, estos desarrollos han permitido que surjan sistemas cada vez más complejos, facilitando la tarea de construir elaboradas redes de logística, entrenar o ajustar sistemas de Inteligencia artificial, optimizar carteras de inversión financiera, procesar información médica, o diseñar piezas mecánicas con máxima resistencia y mínimo peso [2].
Sin embargo, aunque todos estos problemas cuentan con un conjunto de entradas que se desea calibrar para obtener el máximo o mínimo puntaje en una salida, debido a sus características, no todos los problemas de optimización pueden ser solucionados con las mismas herramientas matemáticas.
Fig. 2 diagrama ilustrativo de una función matemática compleja en un espacio tridimensional.
Métodos para solucionar un problema de optimización
Existen diversas estrategias para solucionar un problema de optimización, ya sea este de minimización o maximización, sin embargo, estos pueden ser categorizados en tres estrategias
- Métodos exactos.
- Métodos numéricos basados en el gradiente.
- Métodos metaheurísticos.
Métodos exactos
Los métodos exactos emplean principios matemáticos, despejes, formulas, derivadas u observaciones particulares para determinar las condiciones donde un sistema ofrece una solución óptima (ya sea máximo o mínimo) y retornan soluciones exactas [3]. Por ejemplo, un método exacto podría usarse para encontrar la máxima altura que alcanza un proyectil al ser lanzado conociendo algunos detalles de su trayectoria. Así, empleando una fórmula de física, algunos datos de la trayectoria y algunos despejes podría obtenerse con certeza una solución exacta del sistema.
Fig. 3 Diagrama de la trayectoria trazada por un objeto proyectado por una catapulta con indicadores en su posición de altura máxima.
Métodos numéricos
Los métodos numéricos basados en gradiente son métodos que se emplean cuando no se conoce el modelo matemático del sistema, pero si se pueden conocer muestras o evaluaciones del sistema y, además, se conoce que el sistema es unimodal [4]. Así, un método numérico basado en gradiente podría usarse para encontrar un objeto al jugar frio o caliente. Observando hacía que dirección el jugador se acerca al punto caliente (dirección que fomenta la mínima distancia al objeto) es posible determinar la posición aproximada del objeto rápidamente y generar una solución aproximada.
Fig. 4 Ilustración de una función solucionable mediante un método numérico basado en el gradiente.
Métodos metaheurísticos
Los métodos metaheurísticos son una clase de método numérico empleado en los problemas más complejos, donde el problema posee muchas regiones promisorias, evaluaciones «ruidosas» o inexactas y un espacio de búsqueda amplio [2]. Un ejemplo podría encontrarse al buscar la mejor formulación para un concreto. En dicho ejemplo, se buscaría ajustar los porcentajes de cemento, arena, grava, aditivos y agua en una mezcla, buscando maximizar la resistencia final del concreto. En este caso, no es posible determinar un modelo matemático exacto, el espacio de búsqueda es amplio (se requiere ajustar varios parámetros), mas aún, las evaluaciones de resistencia de alguna prueba en laboratorio tienen variaciones, por lo que, en ocasiones, no es posible determinar la dirección de mejora de forma precisa.
Fig. 5 Ilustración de una prensa y un conjunto de cilindros de concreto con diferentes formulaciones empleados en pruebas destructivas de evaluación de resistencia.
Así, considerando las tres categorías anteriores, no es infrecuente encontrar problemas de optimización que por sus características no puedan ser solucionados mediante técnicas tradicionales como los métodos exactos o basados en gradiente. En dichos casos, los métodos metaheurísticos son una herramienta robusta y eficiente para lograr encontrar soluciones promisorias en problemas difíciles de analizar mediante otras estrategias.
Convencionalmente, los métodos metaheurísticos generan un conjunto de soluciones candidato aleatorias y observan su desempeño. Después, dichas soluciones son modificadas con la información disponible de esta primera etapa de evaluaciones con objeto de propiciar la aparición de mejores soluciones candidato. Este proceso se repite de forma iterativa permitiendo que las soluciones mejoren poco a poco hasta alcanzar una aproximación aceptable de la solución real.
Fig. 6 Ilustración de una función matemática compleja de dos dimensiones.
Ejemplo de aplicación de un método metaheurístico
Un ejemplo del uso de estos métodos puede observarse en las animaciones del siguiente problema: «Se desea visitar todas las capitales de los 32 estados de México partiendo de Guadalajara y retornando allí tras las visitas. Asumiendo que todas las capitales poseen aeropuertos y que no se desea repetir visitas: ¿Cuál ruta debería de emplearse para minimizar la distancia recorrida?»
Como se puede observar, en este problema no existe un modelo matemático directo que permita obtener una solución exacta, y es un problema con soluciones discretas, por lo que no existe una derivada o algún elemento que permita usar un método basado en el gradiente tradicional. Dado lo anterior, los métodos metaheurísticos son una alternativa factible para solucionar este problema.
Así, en las animaciones se presenta el proceso de optimización de la ruta sugerida (líneas negras) para transitar todas las capitales (puntos rojos) sin repetición y volviendo al lugar de partida, empleando un Algoritmo Genético [5] y el Optimizador del Lobo Gris [6].
Fig. 7 Animación del proceso de optimización de una ruta mediante un algoritmo genético.
Fig. 8 Animación del proceso de optimización de una ruta mediante el algoritmo del lobo gris.
En dichas figuras puede observarse como se parte de una ruta aleatoria, para subsecuentemente mejorar el trayecto hasta converger en una solución aceptable. Además, puede observarse como las respuestas de cada algoritmo son distintas y algunas convergen más rápidamente que otras. Así, dependiendo el tipo de problema de optimización, alguna herramienta será más apropiada que otra, siendo los métodos metaheurísticos una estrategia robusta y eficiente cuando se carece de un modelo exacto, o cuando este posee algunas características que dificulten su solución mediante un gradiente simple y donde una solución aproximada es aceptable.
Referencias:
[1] R. Baldick, “Applied Optimization: Formulation and Algorithms for Engineering Systems,” 2008. doi: 10.1109/MCS.2008.920952.
[2] E. Cuevas and A. Rodríguez, Metaheuristic Computation with MATLAB®. First edition. | Boca Raton: CRC Press, 2020.: Chapman and Hall/CRC, 2020. doi: 10.1201/9781003006312.
[3] A. Creosteanu, G. Gavrila, and L. Creosteanu, “Comparison between an analytical method and two numerical methods on a given electrostatic potential determination problem,” in _2012 15th International Symposium on Antenna Technology and Applied Electromagnetics, ANTEM 2012_, 2012. doi: 10.1109/ANTEM.2012.6262310.
[4] S. Ruder, “An Overview Optimization Gradients,” 2017.
[5] M. Mitchell, “Genetic algorithms: An overview,” Complexity, vol. 1, no. 1, 1995, doi: 10.1002/cplx.6130010108.
[6] S. Mirjalili, S. M. Mirjalili, and A. Lewis, “Grey Wolf Optimizer,” Advances in Engineering Software, vol. 69, pp. 46–61, 2014, doi: 10.1016/j.advengsoft.2013.12.007.
Descarga de responsabilidad
Este artículo emplea imágenes generadas mediante IA (Fig. 1-6)
