LinkedIn Google+

Antes siquiera de entrar a definir qué son las metaheurísticas, debemos dar un poco de contexto sobre qué es una heurística y en qué marco de conocimiento encaja.

Una heurística no es más que una forma de actuar, o un conjunto de criterios que permita llegar a una solución válida de un problema.

Sin ir más lejos, una heurística comúnmente conocida es la simple “prueba y error” pues puede ser útil en cualquier campo del conocimiento, aunque no sea el método más rápido ni el que aporte mejores resultados soluciones. Por ejemplo, para planificar las tareas y horarios de una plantilla de trabajadores se podrían probar infinidad de alternativas y analizar la validez de estas.

Una heurística define cómo se va a acercar nuestro programa a la resolución del problema.

A partir de esta información, podríamos decir que una metaheurística (meta – heurística), es un conjunto de patrones que podemos seguir para facilitar la selección o creación de una heurística.

En este sentido, podríamos interpretarlas como los distintos modelos de gestión de proyectos (ágil, tradicional, etc.), en el que cada modelo tiene sus ventajas e inconvenientes, y su uso depende del contexto del problema y de la capacidad del equipo de llevarlo a cabo.

Más concretamente, GRASP o ILS son metaheurísticas (o enfoques posibles para atacar un problema complejo) pero la implementación final para un problema concreto usando estas metaheurísticas serían ya heurísticas.

En el mundo actual, en el que se busca la automatización de todos los procesos que se realizan a mano, los algoritmos de optimización son una solución cada vez más factible gracias a metaheurísticas de búsqueda aproximada, que encuentran soluciones cercanas al óptimo en tiempos razonables.

Clasificación

Todos estos diferentes modelos se pueden clasificar conforme a diversas métricas:

Clasificación de las principales metaheurísticas en un diagrama de Euler.
Fuente: Classification of metaheuristics

Además de la clasificación anterior, podemos diferenciar entre:

  • Algoritmos constructivos, que crean una solución factible y después la intentan mejorar (por ejemplo, GRASP)
  • Algoritmos centrados en búsquedas locales, que comienzan con una solución arbitraria, válida o no, y a partir de esa, alterándola o destruyéndola parcialmente, encontrar una mejor solución (Tabu Search sería un buen ejemplo).

Si nos basamos en la popularidad de uso para seleccionar una metodología, esta sería sin duda los algoritmos genéticos, pues hay muchísimas librerías desde las que partir (Jenetics, DEAP, Genetic Sharp) e incluso frameworks muy cómodos (jMetal) con los que avanzar rápidamente.

El principal factor para que esta metodología sea tan popular es que es relativamente sencilla, una vez comprendido cómo tiene que implementarse el algoritmo, para llegar a buenas soluciones en un tiempo razonable, solo es necesario modelar el problema y especificar una función objetivo razonable. A partir de ahí solo hace falta experimentar para ir mejorando los resultados tanto en tiempo de cálculo como en calidad.

No obstante, los algoritmos genéticos no son siempre válidos para ciertos problemas por la complejidad a la hora de codificar la solución o el manejo de las restricciones (que suelen ser muchas y muy variadas en los problemas reales). Así, se puede utilizar la complejidad del problema para ayudarnos a escoger una metaheurística:

  • Si un problema tiene unas características que restringen mucho lo que se puede considerar una solución válida, o factible. Personalmente, aunque por mi edad aún no he podido implementar todas ellas, escogería un algoritmo de tipo constructivo (como GRASP, ILS o Iterated Greedy), pues se pueden diseñar generadores de soluciones que controlen y garanticen la factibilidad. De esta forma, en todas las iteraciones tendríamos soluciones aptas, que posteriormente iríamos mejorando hasta encontrar una óptima o una muy cercana a la óptima.
  • Si el problema no es tan complejo, podríamos seleccionar algoritmos (casi) de cualquier tipo, pero si queremos dedicar poco tiempo tanto al estudio como al desarrollo del esqueleto del algoritmo, un algoritmo genético podría ser, tal como se ha comentado, una muy buena opción.

A modo de bibliografía, estos son los estudios que he usado para documentarme en la comparativa de metaheurísticas en problemas combinatorios:

¿Qué pensáis vosotros? ¿Habéis trabajado alguna vez con metaheurísticas? ¿Cómo ha sido vuestra experiencia?

Artículo anterior

Inteligencia Artificial, Machine Learning & Deep Learning

Artículo siguiente

Inteligencia emocional, sonría por favor…

Sin Comentarios

Responder

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *