Algoritmos Metaheurísticos de Optimización
OBJETIVO
Desarrollar e implementar los diferentes algoritmos metaheuristicos en problemas reales de optimización. Desarrollar software que incorpore estos algoritmos. Desarrollar proyectos de investigación donde se utilicen estos algoritmos.
DESCRIPCIÒN
Las técnicas de búsqueda son métodos fundamentales para resolver problemas en ciencias de la computación. Los algoritmos de búsqueda son utilizados para resolver muchas clases de problemas, incluyendo problemas del camino más corto, juegos de dos adversarios y problemas de satisfacción de restricciones. Para problemas de optimización combinatoria, algoritmos de búsqueda exacta, tales como ramificación y cota o programación dinámica, podrían degenerar en enumeración exhaustiva. Debido a esto, aproximaciones exactas limita solo a resolver problemas de talla limitada, ya que se incrementa de manera exponencial los tiempos de CPU y memoria cuando la talla del problema crece. Por lo tanto en la práctica, se necesitan algoritmos de búsqueda heurística para hallar (no necesariamente óptimas) soluciones a estos problemas. Las heurísticas exploran una pequeña porción del espacio solución, donde se cree que buenas soluciones se pueden hallar. La mayoría de las heurísticas para optimización combinatoria hace uso de métodos básicos de búsqueda local llamado mejoramiento iterativo donde la idea es ir buscando soluciones que mejoren en cada iteración a la anterior. Una limitación de la búsqueda local es que puede quedar atrapada en un óptimo local. Par vencer esta limitación, varias estratégicas heurísticas de propósito general se han desarrollado en las ultimas dos décadas. Para problemas grandes, otra limitación es la complejidad computacional exponencial del mejoramiento iterativo. Estas heurísticas se aplican a problemas específicos y explotan las propiedades estructurales del problema a fin de hallar soluciones. Estas a menudos son muy eficientes a ciertos problemas y no pueden fácilmente adaptarse a otros tipos de problemas. No obstante, hay una clase de técnicas heurísticas que son aplicables a varios tipos de problemas y se conocen como metaheurísticas. Entre las metaheurísticas conocidas están: Simulated annealing, búsqueda tabú, búsqueda adaptativa Greedy aleatorizada (GRASP), algoritmos genéticos, colonia de hormigas, etc.