Metaheurísticas

Con el fin de comprender el concepto de metaheurística, se debe entender el término de heurística. Conceptualmente, la heurística está relacionada con la capacidad de solucionar inteligentemente problemas reales usando el conocimiento disponible.

A nivel práctico, las heurísticas son técnicas de resolución de problemas, las cuales se conforman por reglas metodológicas con el fin de encontrar la solución que más se acerque al resultado óptimo de un problema en específico, manteniendo un costo de cómputo razonable.

Sin embargo, estos resultados no garantizan una solución que sea factible, por tanto, no se puede determinar qué tan próximo se encuentran a la solución óptima. Además, que la técnica desarrollada para solucionar el problema solo es válida para este, siendo necesario generar otros métodos que satisfagan diversos tipos de problemas.

Es en estos escenarios, que existe otra técnica de solución de problemas, las denominadas metaheurísticas, las cuales son estrategias generales para aplicar una o más heurísticas, y que permiten solucionar problemas de forma general, es decir, que una misma metaheurística tiene la capacidad de encontrar soluciones factibles a diferentes problemáticas. De allí el significado de su nombre, pues meta significa “más allá” o “nivel superior”, haciendo referencia de la capacidad de abarcar mayor número de problemas en contraparte de las heurísticas.

Para lograr esta característica de generalidad, las metaheurísticas generan soluciones usando el concepto de exploración y explotación del espacio de búsqueda, evitando así el estancamiento en los óptimos locales (en un área acotada del total de soluciones posibles).

Cuando se habla de exploración del espacio de búsqueda, se hace referencia a la indagación de soluciones en toda el área de búsqueda, permitiendo encontrar sectores prometedores de mejores soluciones. En el caso de la explotación, se enfoca en intensificar uno de estos sectores prometedores, buscando el óptimo local.

El enfoque del software se centra en el desarrollo de dos metaheurísticas con el fin de solucionar el problema del vendedor viajero, las cuales se basan en las estrategias de búsqueda trayectoria y poblacional.

• Trayectoria: método de búsqueda global, en donde se maneja una sola solución del espacio de búsqueda en cada iteración (solución actual), aplicando heurísticas perturbativas para encontrar la siguiente solución, generando una trayectoria de soluciones, un ejemplo de ello es el Simulated Annealing.
  

• Poblacional: método de búsqueda global, en donde se analiza un conjunto de soluciones del espacio de búsqueda en cada iteración, las cuales son modificadas y refinadas en cada repetición del algoritmo, un ejemplo de ello es el Algoritmo Genético.