Metaheurísticas

Extraido de una versión reducida de "Metaheurísticas: una visión global" (Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial. No.19 (2003),pp. 7-28), de Belén Melián, José A. Moreno Pérez, J. Marcos Moreno Vega

Esta es la primera parte de dos entradas, la segunda parte la puedes encontrar aquí...

En Inteligencia Artificial (IA) se emplea el calificativo heurístico, en un sentido muy genérico, para aplicarlo a todos aquellos aspectos que tienen que ver con el empleo de conocimiento en la realización dinámica de tareas. Se habla de heurística para referirse a una técnica, método o procedimiento inteligente de realizar una tarea que no es producto de un riguroso análisis formal, sino de conocimiento experto sobre la tarea. En especial, se usa el término heurístico para referirse a un procedimiento que trata de aportar soluciones a un problema con un buen rendimiento, en lo referente a la calidad de las soluciones y a los recursos empleados.

En la resolución de problemas específicos han surgido procedimientos heurísticos exitosos, de los que se ha tratado de extraer lo que es esencial en su éxito para aplicarlo a otros problemas o en contextos más extensos. Como ha ocurrido claramente en diversos campos de la IA, en especial con los sistemas expertos, esta línea de investigación ha contribuido al desarrollo científico del campo de las heurísticas y a extender la aplicación de sus resultados. De esta forma, se han obtenido tanto técnicas y recursos computacionales específicos, como estrategias de diseño generales para procedimientos heurísticos de resolución de problemas. Estas estrategias generales para construir algoritmos, que quedan por encima de las heurísticas y van algo más allá, se denominan metaheurísticas.

Las metaheurísticas pueden usarse como un sistema experto para facilitar su uso genérico a la vez que mejorar el rendimiento. En esta entrada se describirán los fundamentos que permiten establecer, partiendo de la noción de heurística, el concepto de metaheurística y mostraremos una primera clasificación de las metaheurísticas a partir de los diferentes tipos de procedimientos heurísticos para los que establecen pautas de diseño.

Concepto de metaheurística

La idea más genérica del término heurístico está relacionada con la tarea de resolver inteligentemente problemas reales usando el conocimiento disponible. El término heurística proviene de una palabra griega con un significado relacionado con el concepto de encontrar, y se vincula a la supuesta exclamación eureka! dada por Arquímedes al descubrir su famoso principio.

La concepción más común en IA es interpretar que heurístico es el calificativo apropiado para los procedimientos que, empleando conocimiento acerca de un problema y de las técnicas aplicables, tratan de aportar soluciones (o acercarse a ellas) usando una cantidad de recursos (generalmente tiempo) razonable. En un problema de optimización, aparte de las condiciones que deben cumplir las soluciones factibles del problema, se busca la que es óptima según algún criterio de comparación entre ellas. En Investigación Operativa, el término heurístico se aplica a un procedimiento de resolución de problemas de optimización con una concepción diferente, ya que se califica de heurístico a un procedimiento para el que se tiene un alto grado de confianza en que encuentra soluciones de alta calidad con un coste computacional razonable, aunque no se garantice su optimalidad o su factibilidad, e incluso, en algunos casos, no se llegue a establecer lo cerca que se está de dicha situación deseable.

En este sentido, se usa el calificativo heurístico en contraposición a exacto, que se aplica a los procedimientos a los que se les exige que la solución aportada sea óptima o factible. Una solución heurística de un problema es la proporcionada por un método heurístico, es decir, aquella solución sobre la que se tiene cierta confianza de que es factible y óptima, o de que alcanza un alto grado de optimalidad y/o factibilidad. También es usual aplicar el término heurística cuando, utilizando el conocimiento que se tiene del problema, se realizan modificaciones en su procedimiento de solución que, aunque no afectan a la complejidad del mismo, mejoran el rendimiento en su comportamiento práctico.

Unas heurísticas para resolver un problema de optimización pueden ser más generales o específicas que otras. Los métodos heurísticos específicos deben ser diseñados a propósito para cada problema, utilizando toda la información disponible y el análisis teórico del modelo. Los procedimientos específicos bien diseñados suelen tener un rendimiento significativamente más alto que las heurísticas generales. Las heurísticas más generales, por el contrario, presentan otro tipo de ventajas, como la sencillez, adaptabilidad y robustez de los procedimientos. Sin embargo, las heurísticas generales emanadas de las metaheurísticas pueden mejorar su rendimiento utilizando recursos computacionales y estrategias inteligentes.

El término metaheurística se obtiene de anteponer a heurística el sufijo meta que significa "más allá" o "a un nivel superior". Los conceptos actuales de lo que es una metaheurística están basados en las diferentes interpretaciones de lo que es una forma inteligente de resolver un problema. Las metaheurísticas son estrategias inteligentes para diseñar o mejorar procedimientos heurísticos muy generales con un alto rendimiento. El término metaheurística apareció por primera vez en el artículo seminal sobre búsqueda tabú de Fred Glover en 1986. A partir de entonces han surgido multitud de propuestas de pautas para diseñar buenos procedimientos para resolver ciertos problemas que, al ampliar su campo de aplicación, han adoptado la denominación de metaheurísticas.

La relevancia de las metaheurísticas se refleja en el elevado número de publicaciones sobre este campo desde entonces.

Tipos de metaheurísticas

 Las metaheurísticas son estrategias para diseñar procedimientos heurísticos. Por tanto, los tipos de metaheurísticas se establecen, en primer lugar, en función del tipo de procedimientos a los que se refiere. Algunos de los tipos fundamentales son:

• Las metaheurísticas de relajación se refieren a procedimientos de resolución de problemas que utilizan relajaciones del modelo original (es decir, modificaciones del modelo que hacen al problema más fácil de resolver), cuya solución facilita la solución del problema original (más complicado).
• Las metaheurísticas constructivas se orientan a los procedimientos que tratan de obtener una solución a partir del análisis y selección paulatina de las componentes que la forman.
• Las metaheurísticas de búsqueda guían los procedimientos que usan transformaciones o movimientos para recorrer el espacio de soluciones alternativas y explotar las estructuras de entornos asociadas.
• Las metaheurísticas evolutivas están enfocadas a los procedimientos basados en conjuntos de soluciones que evolucionan sobre el espacio de soluciones para acercarse a la solución deseada.

Algunas metaheurísticas surgen combinando metaheurísticas de distinto tipo, como la metaheurística GRASP (Greedy Randomized Adaptive Search Procedure), que combina una fase constructiva con una fase de búsqueda de mejora. Otras metaheurísticas se centran en el uso de algún tipo de recurso computacional o formal especial como las redes neuronales, los sistemas de hormigas o la programación por restricciones y no se incluyen claramente en ninguno de los cuatro tipos anteriores.

Por otro lado, de una u otra forma, todas las metaheurísticas se pueden concebir como estrategias aplicadas a procesos de búsqueda, donde todas las situaciones intermedias en el proceso de resolución del problema se interpretan como elementos de un espacio de búsqueda, que se van modificando a medida que se aplican las distintas operaciones diseñadas para llegar a la resolución definitiva. Por ello, y porque los procesos de búsqueda heurística constituyen el paradigma central de las metaheurísticas, es frecuente interpretar que el término metaheurística es aplicable esencialmente a los procedimientos de búsqueda sobre un espacio de soluciones alternativas.

En las siguientes subsecciones vamos a profundizar un poco la explicación de las metaheurísticas anteriores:

Metaheurísticas de Relajación

Una cuestión relevante al abordar un problema real es la obtención de un modelo que permita emplear una técnica de resolución apropiada. Si con este modelo el problema resulta difícil de resolver se acude a modelos modificados en los que es más sencillo encontrar buenas soluciones o en los que los procedimientos son más eficientes. Una relajación de un problema es un modelo simplificado obtenido al eliminar, debilitar, o modificar restricciones (u objetivos) del problema real. En cualquier formulación siempre existe algún grado de simplificación, lo que puede afectar en mayor o menor medida al ajuste a la realidad de los procedimientos de resolución y de las soluciones del problema propuestas. Los modelos muy ajustados a la realidad suelen ser muy difíciles de resolver, y sus soluciones difíciles de implementar exactamente, por lo que se acude a modelos relajados.

Muchas heurísticas de relajación modifican elementos del problema para proponer la solución de estas modificaciones como solución heurística del problema original. Las buenas relajaciones son las que simplifican el problema y hacen más eficientes los procedimientos de solución, pero cuya resolución proporciona muy buenas soluciones del problema original. Por ejemplo, para un problema de programación lineal entera, su relajación lineal consiste en ignorar la restricción de que las variables sean enteras. Se utiliza frecuentemente para aplicar procedimientos eficientes de programación lineal, como el método del Simplex, a dicha relajación y proponer una solución entera muy próxima a la solución del problema relajado.

Entre las metaheurísticas de relajación se encuentran los métodos de relajación lagrangiana o de restricciones subordinadas. Otras metaheurísticas de relajación alteran las restricciones o los objetivos del problema para usar su solución en la conducción de la búsqueda de la solución del problema original. Esta modificación puede estar encaminada a relajar las restricciones a las que debe estar sometida la solución, permitiendo que el recorrido bordee la región factible para acercarse al óptimo global incluso desde la región no factible. Otras estrategias modifican la función objetivo para obtener, de forma más rápida, valoraciones aproximadas (por exceso o por defecto) de la calidad de la solución que orientan la búsqueda, al menos en los estados iniciales. Es frecuente encontrar problemas en los que evaluar la función objetivo puede significar resolver otro problema de gran dificultad, realizar un proceso de simulación o realizar algún tipo de inversión o consumo de recursos. Para estos problemas es muy útil encontrar funciones sencillas de calcular que den una idea aproximada de la calidad de las soluciones sin necesidad de una evaluación ajustada de la función objetivo. Por ejemplo, en juegos complicados, como el ajedrez, encontrar una función que evalúe correctamente la bondad de una posición determinada (que puede depender de los movimientos futuros que esa posición permite) puede llegar a ser excesivamente complicado y costoso, por lo que muchas veces se usa una función de evaluación hace un simple cálculo acerca de dónde está cada pieza en la posición considerada... no es perfecta, pero permite hacer muchas más evaluaciones por segundo y explorar más los posibles futuros para encontrar un buen movimiento (quizás no el mejor) en una cantidad de tiempo razonable.

Metaheurísticas Constructivas

Las heurísticas constructivas aportan soluciones del problema por medio de un procedimiento que incorpora iterativamente elementos a una estructura, inicialmente vacía, que representa a la solución. Las metaheurísticas constructivas establecen estrategias para seleccionar las componentes con las que se construye una buena solución del problema. Entre las metaheurísticas primitivas en este contexto se encuentra la popular estrategia voraz o greedy, que implica la elección que da mejores resultados inmediatos, sin tener en cuenta una perspectiva más amplia. Dentro de este tipo de metaheurística, destaca la aportación de la metaheurística GRASP que, en la primera de sus dos fases, incorpora a la estrategia greedy pasos aleatorios con criterios adaptativos para la selección de los elementos a incluir en la solución.

Por ejemplo, se usa una metaheurística constructiva de este tipo cuando se construye un camino mínimo en un mapa usando la opción de cambio más cercana al objetivo... no asegura un camino mínimo final, pero al menos reduce la complejidad de la decisión en cada paso confiando en que los puntos más cercanos nos llevarán más rápido al objetivo final.

Metaheurísticas de búsqueda

El tipo de metaheurística más importante es el de las metaheurísticas de búsqueda, que establecen estrategias para recorrer el espacio de soluciones del problema transformando de forma iterativa soluciones de partida. 

La concepción primaria de heurística más frecuente era la de alguna regla inteligente para mejorar la solución de un problema que se aplicaba iterativamente mientras fuera posible obtener nuevas mejoras. Tales procesos se conocen como búsquedas monótonas (descendentes o ascendentes), algoritmos escaladores (hill-climbing) o búsquedas locales.

Esta última denominación obedece a que la mejora se obtiene en base al análisis de soluciones similares a la que realiza la búsqueda; denominadas soluciones vecinas. Estrictamente hablando, una búsqueda local es la que basa su estrategia en el estudio de soluciones del vecindario o entorno de la solución que realiza el recorrido. Las metaheurísticas de búsqueda local son las estrategias o pautas generales para diseñar métodos de búsqueda local, como la estrategia voraz o greedy. Esta metaheurística establece como pauta, una vez consideradas cuales son las soluciones que intervienen en el análisis local, elegir iterativamente la mejor de tales soluciones mientras exista alguna mejora posible.

Sin embargo, se suele asumir que las búsquedas locales sólo modifican la solución que realiza el recorrido mediante una mejora en su propio entorno. El principal inconveniente de estas búsquedas locales es que se quedan atrapadas en un óptimo local, una solución que no puede ser mejorada por un análisis local. Por ello, el propósito fundamental de las primeras metaheurísticas era extender una búsqueda local para continuarla más allá de los óptimos locales, denominándose Búsqueda Global.

Las metaheurísticas de búsqueda global incorporan pautas para tres formas básicas de escapar de los óptimos locales de baja calidad: volver a iniciar la búsqueda desde otra solución de arranque, modificar la estructura de entornos que se está aplicando, y permitir movimientos o transformaciones de la solución de búsqueda que no sean de mejora. Surgen así, respectivamente, las metaheurísticas de arranque múltiple, de entorno variable y de búsqueda no monótona. Estos últimos controlan los posibles movimientos de empeoramiento de la solución mediante criterios de aceptación estocáticos o utilizando la memoria del proceso de búsqueda.

Las metaheurísticas de búsqueda estocásticas establecen pautas para regular la probabilidad de aceptar transformaciones que no mejoren la solución. El Templado Simulado es el exponente más importante de este tipo de metaheurísticas donde la probabilidad de aceptación es una función exponencial del empeoramiento producido. Las metaheurísticas de búsqueda con memoria utilizan información sobre el recorrido realizado para evitar que la búsqueda se concentre en una misma zona del espacio. Fundamentalmente se trata de la Búsqueda Tabú, cuya propuesta original prohíbe temporalmente soluciones muy parecidas a las últimas soluciones del recorrido.

Metaheurísticas evolutivas

Las metaheurísticas evolutivas establecen estrategias para conducir la evolución en el espacio de búsqueda de conjuntos de soluciones (usualmente llamados poblaciones en este contexto) con la intención de acercarse a la solución óptima con sus elementos. El aspecto fundamental de las heurísticas evolutivas consiste en la interacción entre los miembros de la población, frente a las de búsqueda que se guían por la información de soluciones individuales.

Las diferentes metaheurísticas evolutivas se distinguen por la forma en que combinan la información proporcionada por los elementos de la población para hacerla evolucionar mediante la obtención de nuevas soluciones. Los algoritmos genéticos y meméticos, y los de estimación de distribuciones emplean fundamentalmente procedimientos aleatorios, mientras que las metaheurísticas de búsqueda dispersa o de re-encadenamiento de caminos (Path Relinking) emplean procedimientos sistemáticos.

Otros tipos de metaheurísticas

Otras metaheurísticas que aparecen en varias clasificaciones corresponden a tipos intermedios entre los anteriores. Entre ellas destacan las metaheurísticas de descomposición (entre las de relajación y las constructivas) y las de memoria a largo plazo (entre las de arranque múltiple y la tabú).

Propiedades deseables

Son propiedades deseables todas aquellas que favorezcan el interés práctico y teórico de las metaheurísticas. Indicarán direcciones a las que dirigir los esfuerzos para contribuir al desarrollo científico e ingenieril, pero no será posible mejorar todas las propiedades a la vez, dado que algunas son parcialmente contrapuestas. Una relación de tales propiedades debe incluir las siguientes:

• Simple. La metaheurística debe estar basada en un principio sencillo y claro, fácil de comprender.
• Precisa. Los pasos y fases de la metaheurística deben estar formulados en términos concretos.
• Coherente. Los elementos de la metaheurística deben deducirse naturalmente de sus principios.
• Efectiva. Los algoritmos derivados de la metaheurística deben proporcionar soluciones de muy alta calidad; óptimas o muy cercanas a las óptimas.
• Eficaz. La probabilidad de alcanzar soluciones óptimas de casos realistas con la metaheurística debe ser alta.
• Eficiente. La metaheurística debe realizar un buen aprovechamiento de recursos computacionales; tiempo de ejecución y espacio de memoria.
• General. La metaheurística debe ser utilizable con buen rendimiento en una amplia variedad de problemas.
• Adaptable. La metaheurística debe ser capaz de adaptarse a diferentes contextos de aplicación o modificaciones importantes del modelo.
• Robusta. El comportamiento de la metaheurística debe ser poco sensible a pequeñas alteraciones del modelo o contexto de aplicación.
• Interactiva. La metaheurística debe permitir que el usuario pueda aplicar sus conocimientos del problema para mejorar el rendimiento del procedimiento.
• Múltiple. La metaheurística debe suministrar diferentes soluciones alternativas de alta calidad entre las que el usuario pueda elegir.
• Autónoma. La metaheurística debe permitir un funcionamiento autónomo, libre de parámetros, o que se puedan establecer automáticamente.

Varias de estas propiedades están muy relacionadas y apuntan en la misma dirección, como la simplicidad, la precisión y la coherencia. Otras pueden ser valoradas en mayor profundidad cuando se trabaja con metaheurísticas concretas y se ponen a prueba.

Conclusiones

Para la resolución práctica de una proporción cada vez mayor de problemas de interés no resulta apropiado utilizar procedimientos diseñados a propósito para cada modelo y dependientes de su estructura particular. Ante la necesidad de utilizar algoritmos heurísticos para dar soluciones, las metaheurísticas proporcionan pautas y estrategias generales de diseño para obtener heurísticas con un alto rendimiento. Las metaheurísticas proporcionan métodos para escaparse de los óptimos locales de mala calidad por lo que, dado que el valor de tales óptimos locales frecuentemente difiere considerablemente del valor del óptimo global, el impacto práctico de las metaheurísticas ha sido inmenso.

Se observan diversas tendencias en las investigaciones sobre técnicas metaheurísticas. Unas tratan de mantener la pureza de los métodos y comprobar su efectividad en nuevos problemas, sin incorporar herramientas de otras metaheurísticas. Otras investigaciones, desde una perspectiva más ingenieril, tratan de aprovechar los recursos proporcionados por cada una de ellas. Para estas últimas, la única cuestión relevante es conocer si el beneficio en el rendimiento, proporcionado por la inclusión de tales herramientas, compensa al esfuerzo de su implementación y al incremento de la complejidad de los códigos resultantes (y su mantenimiento futuro).

El campo de investigación sobre metaheurísticas ofrece más oportunidades para aplicar la intuición que la deducción. En contraste con el éxito práctico de muchas metaheurísticas, el estudio teórico está más retrasado. Frecuentemente se obtienen buenas nuevas heurísticas, con algo de inventiva y gran esfuerzo en el ajuste de numerosos parámetros, pero las razones de por qué funcionan tan bien permanecen desconocidas. La situación es incluso peor para los híbridos, donde las aportaciones de las metaheurísticas implicadas y el beneficio de la interacción raramente son objetos de un estudio experimental bien diseñado.

Algunas propuestas encaminadas a una mejor comprensión de estos aspectos son el estudio de la influencia de la topografía de los óptimos locales y de las trayectorias seguidas por los procesos de búsqueda heurística. El análisis de la evolución de las distancias al óptimo frecuentemente se centran exclusivamente en la desviación del objetivo alcanzado frente al mejor posible. Se puede obtener información más útil si se consideran distancias entre las propias soluciones y no sólo su valor. Los intentos por organizar este campo son numerosos, pero los conceptos principales son raramente definidos con precisión y hay todavía muy pocos teoremas significativos. Ninguna estructura ha conseguido una aceptación general. Más bien, cada grupo de investigación inspirador de una metaheurística tiene su propio punto de vista y habilidad para explicar muchas heurísticas en su propio vocabulario así como para absorber ideas de todo el campo (generalmente bajo la forma de híbridos).