Optimización miope
ARTÍCULO ESCRITO POR
Como curar la miopía de los algoritmos de optimización tradicionales
La optimización es una rama de la Investigación Operativa, que se encarga de resolver problemas de toma de decisiones. De forma muy resumida, podemos decir que la optimización consiste en minimizar o maximizar una función objetivo, cuyos valores están restringidos por unas desigualdades (restricciones).
Aplicados a la práctica, se trata de desarrollar algoritmos o programas, que resuelvan un problema (planificar los turnos de un servicio, planificar la producción, asignar cargas a flotas de vehículos, planificar las rutas de reparto, determinar la ubicación de centros logísticos, y un largo etcétera. La ‘función objetivo’ aquí sería maximizar el servicio al cliente, minimizar los recorridos con el vehículo vacío, minimizar los costes, maximizar la productividad… Y las restricciones serían cumplir con la regulación laboral en cuanto a jornadas y descansos, cumplir con la regulación del tacógrafo, cumplir con las restricciones de accesibilidad en las ciudades y los horarios de entrega, con la compatibilidad entre los productos y las máquinas, y un larguísimo etcétera.
Para resolver éstos, y muchos otros problemas, existen una inmensa cantidad de algoritmos, pero hay muchos que sufren de miopía. Y sí, no es una errata, los algoritmos también pueden ser miopes.
Veamos qué es esto de la miopía de los algoritmos y cómo curarla.
La miopía de los algoritmos de optimización
De todos los algoritmos existentes, los constructivos son los más utilizados. A menudo se utilizan de forma inconsciente, y tienen el inconveniente de que sufren una severa miopía.
Un ejemplo muy fácil de entender es el algoritmo del vecino más próximo para los problemas de rutas. En este caso, el constructivo sigue una estrategia para encontrar la ruta más corta. La estrategia consiste en, desde cada punto, elegir al punto más próximo como siguiente punto a visitar.
En el ejemplo de la figura partimos de Valencia, vamos a Castellón que es el más cercano, y de ahí a Alicante. Naturalmente si vemos todo el mapa no tiene sentido volver hacía el sur, lo lógico es ir desde Castellón a Barcelona. Por eso se dice que es miope, ya que toma decisiones viendo solo el siguiente paso. Y en este caso, fijándonos solo en el siguiente, sí que tiene sentido ir a Alicante.
Pero la miopía no afecta solo a los constructivos, otros algoritmos muy utilizados, como son los de búsqueda local, también la sufren.
Cambiemos de ejemplo, ahora supongamos que debemos encontrar la cima de la montaña más alta en la cordillera de la segunda imagen. Imaginemos que partimos desde el punto verde, y, aplicando la búsqueda local, vamos subiendo por el camino marcado en azul, hasta llegar a un punto para el cual si damos un paso en cualquier dirección tendríamos que descender, nuestro punto rojo. De este modo habríamos alcanzado un óptimo local, pero fijándonos en la imagen vemos que está muy lejos de la mejor solución posible, el óptimo global. Por tanto, estamos otra vez ante un algoritmo miope, ya que si pudiera ver más allá del siguiente paso no le importaría bajar un poco para después volver a subir.
Curar la miopía de los algoritmos
El problema expuesto anteriormente ni mucho menos ha pasado desapercibido para los investigadores, lo que ha supuesto que se hayan ido desarrollando nuevos algoritmos y mejoras de los ya existentes para sobreponerse al problema. En otras palabras, han encontrado la cura para la miopía.
Una de las primeras “curas” fue un algoritmo conocido como GRASP (Greedy Randomized Adaptive Randomized Search Procedure), Feo y Resendre 1989.
Una forma de escapar de los óptimos locales es dar cierta aleatoriedad a la construcción de la solución inicial. Así se obtiene una población de soluciones iniciales que se mejora aplicando una búsqueda local a cada una. Finalmente, la solución será la mejor de todas las que se hayan probado.
Este algoritmo no garantiza que la solución obtenida sea la óptima, pero es evidente que ve más a lo lejos que si solo se aplicara una búsqueda local y en consecuencia es capaz de proporcionar mejores soluciones.
Otra cura para la miopía la encontramos en la búsqueda tabú, Fred Glover 1989. La idea básica es que no importa descender un poco si finalmente se alcanza una cima más alta. Esto no significa, en absoluto, que vayamos a chospar montaña arriba y abajo como cabritillos. Ya que como sucede con otras metaheurísticas, la búsqueda tabú también consta de unos criterios para explorar y de parada perfectamente definidos.
- Lista tabú: es una estructura de memoria en la que se guardan n soluciones ya exploradas. Mientras la solución esté en la lista no se podrá volver a ese punto. Así evitamos entrar en bucle yendo y viniendo siempre al mismo punto.
- Criterios de parada: Los más comunes son llegar a un máximo de iteraciones o alcanzar una cota.
Como vemos en la imagen, la búsqueda tabú no se para cuando llega a un óptimo local, sino que sigue avanzando hasta encontrar un criterio de parada, como podría ser alcanzar una altitud de n metros o realizar m iteraciones. Por eso, tampoco presenta garantías de hallar el óptimo.
Un caso particular de la búsqueda tabú es el conocido Simulated Annealing, donde se aplica una determinada probabilidad para que un movimiento se convierta en tabú.
Ya hemos visto algunos ejemplos, pero hay muchos más: algoritmos genéticos, Iterated Greedy, … Además, hay que tener en cuenta que de los descritos anteriormente hay muchas versiones, nosotros solo hemos dado la más general y común a todos.
Conclusión
Muchos algoritmos tradicionales carecen de una visión global, son miopes ante el problema. Esto nos lleva a que cuando los utilizamos acabemos cayendo en óptimos locales que pueden estar muy alejados de la solución óptima.
Para solventar este problema se crearon los algoritmos metaheurísticos, los que van más allá. Con ellos se obtiene una visión más global, se acaban los problemas de miopía, y en definitiva se obtienen mejores soluciones, que es lo que realmente nos interesa.
Referencias:
Feo, T., & Resendre, M. (1995). Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 109-115.
Rajkumar, M., Asokan, P., Page, T., & Arunachalam, S. (2010). A GRASP algorithm for the Integration of Process Planning and Scheduling in a flexible job-shop. Int. J. Manufacturing Research, Vol. 5, No. 2, 230-251.
Glover, F. (1989) Tabu Search–Part I. ORSA Journal on Computing. Volume 1 Issue 3, 135-206.
Glover, F. (1989) Tabu Search–Part 2. ORSA Journal on Computing. Volume 2 Issue 1, 1-97.
Ruiz, R. et al. (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, Volume 177. Issue 3, 2033-2049
Webinar de Rubén Ruiz para el ITI, Optimización de rutas y logística El problema del viajante de comercio: https://www.youtube.com/watch?v=MyAzHZCtYU4&t=1818s
