Algoritmos genéticos y metaheuristicas

En la tesis doctoral de Luna Valero, publicada el año 2008 con el título “Metaheurísticas avanzadas para problemas reales en redes de telecomunicaciones”, se menciona que la optimización en el sentido de encontrar la mejor solución, o al menos una solución lo suficientemente buena, para un problema es un campo de vital importancia en el mundo real y, en particular, en ingeniería. Constantemente se está resolviendo pequeños problemas de optimización, como el camino más corto para ir de un lugar a otro, la organización de una agenda, etc. En general, estos problemas son lo suficientemente pequeños y es posible resolverlos sin ayuda adicional, pero conforme se hacen más grandes y complejos, el uso de las computadoras para su resolución es inevitable. Debido a la gran importancia de los problemas de optimización, a lo largo de la historia de la informática se han desarrollado múltiples métodos para tratar de resolverlos. Inicialmente, las técnicas se las puede clasificar en exactas y aproximadas. Las técnicas exactas, denominadas también enumerativas o exhaustivas, garantizan encontrar la solución óptima para cualquier instancia de cualquier problema en un tiempo acotado.

El inconveniente de estos métodos es que el tiempo y memoria que se necesitan, aunque acotados, crecen exponencialmente con el tamaño del problema, ya que la mayoría de éstos son problemas no polinomiales duros. Esto supone en muchos casos que el uso de estas técnicas sea inviable, ya que se requiere mucho tiempo, posiblemente miles de años, o una cantidad desorbitada de memoria para la resolución del problema. Por lo tanto, los algoritmos aproximados para resolver estos problemas están recibiendo una atención cada vez mayor por parte de la comunidad internacional desde hace unas décadas. Estos métodos sacrifican la garantía de encontrar el óptimo a cambio de encontrar una solución satisfactoria en un tiempo razonable. Cook y sus colegas, en el libro publicado el año 1997 titulado “Optimización combinatoria”, mencionan que un problema de optimización combinatoria, generalmente, se caracteriza por un conjunto finito de soluciones admisibles, y una función objetivo que asocia un valor a cada solución admisible. La resolución del problema consiste en determinar el conjunto finito de soluciones admisibles, minimizando o maximizando la función objetivo.

El investigador Luna, en la tesis doctoral citada, menciona que se pueden encontrar dos tipos de algoritmos aproximados: Los heurísticos ad hoc y las metaheurísticas. Los heurísticos ad hoc, a su vez, pueden dividirse en heurísticos constructivos y métodos de búsqueda local. Los heurísticos constructivos suelen ser los métodos más rápidos. Construyen una solución desde cero mediante la incorporación de componentes hasta obtener una solución completa, que es el resultado del algoritmo. Aunque en muchos casos encontrar un heurístico constructivo es relativamente sencillo, las soluciones ofrecidas suelen ser de muy baja calidad. Encontrar métodos de esta clase que produzcan buenas soluciones es bastante difícil, ya que dependen mucho del problema, y para su planteamiento se debe tener un conocimiento muy extenso del mismo. Los métodos de búsqueda local o seguimiento del gradiente parten de una solución ya completa y, utilizando el concepto de vecindario, recorren parte del espacio de búsqueda hasta encontrar un óptimo local. El vecindario de una solución es el conjunto de soluciones que se pueden construir a partir de la solución aplicando un operador específico de modificación, generalmente denominado movimiento. Un óptimo local es una solución mejor o igual que cualquier otra solución de su vecindario. Estos métodos, partiendo de una solución inicial, examinan su vecindario y se quedan con el mejor vecino, continuando el proceso hasta que se encuentra un óptimo local. En muchos casos, la exploración completa del vecindario es inabordable y se siguen diversas estrategias, dando lugar a diferentes variaciones del esquema genérico. Según el operador de movimiento elegido, el vecindario cambia y el modo de explorar el espacio de búsqueda también, pudiendo simplificarse o complicarse el proceso de búsqueda.

En los años 1970 surgió una nueva clase de algoritmos aproximados, cuya idea básica era combinar diferentes métodos heurísticos a un nivel más alto para conseguir una exploración del espacio de búsqueda de forma eficiente y efectiva. Estas técnicas se han denominado metaheurísticas. Este término fue introducido por primera vez por Glover, en el artículo publicado el año 1986 titulado “Caminos futuros para la programación entera y vínculos a la inteligencia artificial”. Antes de que el término fuese aceptado completamente por la comunidad científica, estas técnicas eran denominadas heurísticas modernas, tal como se describe en el libro de Reeves publicado el año 1993 con el título “Tecnicas heurísticas modernas para problemas combinatorios”. Esta clase de algoritmos incluye técnicas como colonias de hormigas, algoritmos evolutivos, búsqueda local iterada, enfriamiento simulado y búsqueda tabú. De las diferentes descripciones de metaheurísticas que se encuentran en la literatura se pueden destacar ciertas propiedades fundamentales que caracterizan a este tipo de métodos: (1) Las metaheurísticas son estrategias o plantillas generales que guían el proceso de búsqueda. (2) El objetivo es una exploración eficiente del espacio de búsqueda para encontrar soluciones casi óptimas. (3) Las metaheurísticas son algoritmos no exactos y generalmente son no deterministas. (4) Pueden incorporar mecanismos para evitar regiones no prometedoras del espacio de búsqueda. (5) El esquema básico de cualquier metaheurística tiene una estructura predefinida. (6) Las metaheurísticas pueden hacer uso de conocimiento del problema que se trata de resolver en forma de heurísticos específicos que son controlados por la estrategia de más alto nivel.