Resolviendo problemas complejos con técnicas metaheurísticas avanzadas

Abstract

Las meta heurísticas, en su definición original, son métodos de solución que orquestan una interacción entre procedimientos de mejora local y estrategias de nivel superior para crear un proceso capaz de escapar de los óptimos locales y realizar una búsqueda robusta de un espacio de soluciones. Con el tiempo, estos métodos también han llegado a incluir todos los procedimientos que emplean estrategias para evitar caer en óptimos locales en espacios de soluciones complejas. Esto hace que se diferencian de los métodos exactos, ya que permite atacar problemas con espacios de búsqueda muy grandes, entregando soluciones óptimas o casi óptimas en tiempos razonables. Por lo general, las meta heurísticas resuelven problemas de: diseño en general, telecomunicaciones, aprendizaje de máquina y minería de datos en Bioinformática y Biología computacional, modelado de sistemas, planificación de tareas en problemas de enrutamiento y de producción, logística y transporte, entre muchos otros. Si bien un gran número de técnicas, meta heurísticas han surgido desde su creación y han demostrado ser muy eficaces, aún existen aspectos importantes de estas herramientas que no han recibido la atención suficiente por parte de la comunidad científica. Entre estos aspectos podemos encontrar: el basamento teórico de estas herramientas, el análisis de robustez de dichos algoritmos ante datos del problema que contengan errores, el ajuste de los valores paramétricos (tamaño de población, tipos de operadores, probabilidad de aplicación de los operadores, política migratoria, cantidad de iteraciones, etc.), el análisis y desarrollo de representaciones y operadores más eficientes. Además del desarrollo de técnicas de computación paralelas para mejorar la solución de problemas y disminuir los tiempos de procesamiento requeridos. En estos últimos cuatro años, el objetivo principal de nuestro proyecto ha sido analizar, diseñar y desarrollar distintas estrategias que permitan una mejor adaptación y mayor  eficiencia de las meta heurísticas en los siguientes escenarios: el tratamiento de datos que puedan contener errores (ruido), el control adaptativo de parámetros claves como son la probabilidad de mutación y la frecuencia de migración en los Algoritmos Evolutivos (EAs), la selección de operadores que permita un comportamiento más eficiente del GA. Así como también, el estudio sobre el aprovechamiento de los distintos recursos hardwares disponibles en un laboratorio en la ejecución de una metaheurística y el desarrollo de algoritmos evolutivos para hacer uso de las ventajas en velocidad de procesamiento que brindan las unidades de procesamiento gráfico (GPUs). El logro de este objetivo ha permitido cumplir con objetivos secundarios, como son: la formación continúa de los integrantes del proyecto y también la incorporación de estudiantes (becarios) en este campo de investigación científica