Corresponde a un proceso de toma de decisiones basado en experiencias previas en problemas similares, pueden simular o emular procesos de la naturaleza. Permiten obtener un resultado pero no se garantiza que el mismo sea la solución óptima de la instancia analizada (o inclusive una solución factible). Intenta acercarse lo más posible a la solución factible/óptima y se espera que se desarrolle en tiempo razonable.
No garantizan encontrar la solución óptima. La resolución del problema se realiza explorando el conjunto de soluciones del mismo en un recorrido en el grafo de estados del problema. Se sigue un criterio para la elección del próximo estado. En raras ocaciones la exploración es completa, el tamaño de la misma lo hace prohibitivo si se desea una complejidad temporal polinomial.
Comenzamos en un posible estado de solución inicial que puede corresponder a una solución factible o parcial. Se evalúan un subconjunto de estados para buscar otro que mejore la situación actual y se elige el siguiente según un criterio. Realizamos esta tarea de evaluación y selección de un nuevo estado de forma iterativa. Debe establecerse un criterio de finalización de la ejecución (puede ser una cantidad determinada de iteraciones o llegar a un estaod donde sea imposible mejorar la solución encontrada).
En problemas combinatorios puede corresponder a:
También hay problemas donde se puede representar la solución como un conjunto de variables cuantitativas.
Dado un estado del problema calculará el valor costo que caracterize a un estado del problema. Suelen estar explicitadas y es posible utilizarla en conjunto con las restricciones implícitas. Para problemas de exploración donde no hay que maximizar/minimizar un valor se pueden construir contabilizando la cantidad de restricciones violadas por la solución.
Determina aquellos estados a los que puedo acceder desde el estado actual (sucesores). Generalmente se busca que el próximo estado sea una variación del anterior aceptando una cantidad acotada de modificaciones. Se la suele definir como el subconjunto de estados que no se encuentran a una mayor distancia que el estado actual.
Su elección condiciona la porción del estado de soluciones explorado al finalizar el algoritmo. Puede ser seleccionado aleatoriamente o mediante algún algoritmo previo. Generalmente en problemas de optimización corresponden a una solución factible o parcial que cumple las restricciones del problema.
En ocaciones por la naturaleza de la instacia se puede llegar a un estado donde sea imposible encontrar un estado vecino superador, este valor será el máximo o mínimo local y solo uno de ellos o un subconjunto corresponde al máximo o mínimo global del problema.