Vamos a presentar un problema interesante y computacionalmente difícil de resolver: el problema del "agente viajero". Un agente viajero desea encontrar la ruta óptima para visitar exactamente "n" ciudades. Esto es, encontrar la secuencia ordenada de ciudades que minimice el costo sobre la ruta. El tamaño del espacio de posibles rutas es muy grande, es "n" factorial. En la parte superior izquierda vemos una ruta arbitraria para un problema con 30 ciudades. Tiene un costo alto, pues hay muchos cruces con distancias muy grandes. Una buena ruta no tiene cruces, como la mostrada en la gráfica inferior. El algoritmo SA teóricamente puede encontrar la solución óptima, sin embargo, en la práctica, el tiempo que le tomaría encontrar la ruta óptima es muy grande,; por lo que sólo podemos garantizar que la solución será subóptima. En el problema del agente viajero, una solución candidata es una permutación de ciudades. En este ejemplo identificamos cada ciudad con una letra distinta. Para encontrar soluciones vecinas, podemos definir un operador de intercambio de ciudades. Aleatoriamente, seleccionamos dos ciudades e intercambiamos su posición en la ruta. Esta operación también la podemos restringir para ciudades que son adyacentes en la ruta. Otra estrategia para generar permutaciones vecinas es invertir el orden de la secuencia en una subruta aleatoria. Finalmente, la energía de la solución es la suma de los costos sobre la trayectoria, en este caso, la suma de los costos de cada una de las transiciones. El término "metaheurística" nombra a un número muy amplio de algoritmos de búsqueda. Gendrao y Pová definen la metaheurística como métodos de solución que combinan procedimientos de mejora local con estrategias de alto nivel, para evitar la convergencia de las soluciones a regiones subóptimas en el espacio de soluciones. El nombre "metaheurística" fue acuñado por Fred Glover en su artículo de 1986 "Future paths for integer programming and links to artificial intelligence", en el cual se refiere al algoritmo de "tabu search" o "búsqueda tabú". Glover describe a la búsqueda tabú como una metaheurística superimpuesta en otra heurística. En la búsqueda tabú se prohíbe volver a visitar estados que ya existen en una memoria, esto le permite al algoritmo poder escapar de óptimos locales. En la práctica, la mayoría de los problemas interesantes a resolver en inteligencia artificial no admite la utilización de algoritmos para su solución exacta. Muchos de los problemas caen dentro de la categoría de problemas NP-completos. Esto significa que no se pueden resolver en un tiempo razonable. El diseño de algoritmos metaheurísticos tiene un enfoque pragmático. Generalmente, combina resultados teóricos formales con estrategias de solución informales. Muchas veces, los algoritmos están inspirados en la naturaleza, tal es el caso del algoritmo que vimos previamente, el algoritmo de recocido o templado simulado. Una estrategia comúnmente utilizada en la práctica, consiste en la hibridación de los algoritmos, esto es, en la combinación de dos o más metaheurísticas. Por ejemplo, el algoritmo memético combina la evolución de una población de soluciones con el aprendizaje individual. Los algoritmos metaheurísticos, sin embargo, pueden consumir muchos recursos computacionales, además de que no hay garantía de que vamos a encontrar una solución. En este sentido, son algoritmos incompletos, no siempre nos van a dar una respuesta y, de darnos una respuesta, ésta generalmente va a ser subóptima. En palabras del investigador Carlos Coello Coello, del Cinvestav, los algoritmos metaheurísticos son la última línea de defensa en optimización.
