En general existe una gran cantidad de problemas que se consideran difíciles de resolver. La dificultad de los problemas está caracterizada por la teoría de complejidad computacional.
Se sabe que muchos problemas son NP-duros, esto es, el tiempo que requieren para resolver una instancia de ese problema crece en el peor de los casos de manera exponencial con respecto al tamaño de la instancia.
Por lo mismo, muchas veces se tienen que solucionar usando métodos de solución aproximados, que regresan buenas soluciones (inclusive a veces óptimas) a bajo costo computacional.
Las heurísticas se pueden usar para resolver problemas de optimización. Muchas de las estrategias de búsqueda podrían usarse, aunque algunas pueden resultar ser demasiado costosas o quedar atrapadas en mínimos locales.
Las metaheurísticas se proponen como métodos, determinísticos o estocásticos para salir de mínimos locales.
Algunas de las propiedades deseables para una metahuerística son:
La mayoría de la metaherísticas cumplen con solo algunas de las propiedades arriba mencionadas.
Se han propuesto una gran cantidad de ellas. En este curso veremos las principales.
Por otro lado, no existe un claro ganador ya que en general dependen de la naturaleza de los problemas y los objetivos buscados.
La mayoría de los métodos aproximados son: algoritmos basados en construcción o algoritmos basados en búsqueda local.
Los basados en construcción trabajan con soluciones parciales que tratan de completar, mientras los de búsqueda local se mueven en el espacio de soluciones completas.
Los algoritmos de construcción encuentran soluciones de manera incremental empezando con una solución vacía, añadiendo componentes de forma incremental hasta completar una solución.
Los algoritmos de construcción glotones o greedy añaden el componente que de acuerdo a cierta heurística produce el máximo beneficio local.
Por ejemplo en el TSP añadir siempre la ciudad más cercana.
Generalmente los algoritmos que construyen soluciones son más rápidos, pero sus soluciones no siempre son buenas.