En informática , la búsqueda local es un método heurístico para resolver problemas de optimización computacionalmente difíciles . La búsqueda local se puede utilizar en problemas que pueden formularse como encontrar una solución que maximice un criterio entre varias soluciones candidatas . Los algoritmos de búsqueda local se mueven de una solución a otra en el espacio de las soluciones candidatas (el espacio de búsqueda ) aplicando cambios locales, hasta que se encuentra una solución considerada óptima o hasta que transcurre un límite de tiempo.
Los algoritmos de búsqueda local se aplican ampliamente a numerosos problemas computacionales difíciles, incluidos problemas de informática (particularmente inteligencia artificial ), matemáticas , investigación de operaciones , ingeniería y bioinformática . Ejemplos de algoritmos de búsqueda local son WalkSAT , el algoritmo de 2 opciones para el problema del viajante y el algoritmo Metropolis-Hastings . [1]
Si bien a veces es posible sustituir el descenso de gradiente por un algoritmo de búsqueda local, el descenso de gradiente no pertenece a la misma familia: aunque es un método iterativo para la optimización local , se basa en el gradiente de una función objetivo en lugar de una exploración explícita del espacio de solución. .
Algunos problemas donde se ha aplicado la búsqueda local son:
La mayoría de los problemas pueden formularse en términos de un espacio de búsqueda y un objetivo de varias maneras diferentes. Por ejemplo, para el problema del viajante, una solución puede ser una ruta que visite todas las ciudades y el objetivo es encontrar la ruta más corta. Pero una solución también puede ser un camino, y ser un ciclo es parte del objetivo.
Un algoritmo de búsqueda local comienza a partir de una solución candidata y luego se mueve iterativamente a una solución vecina ; siendo una vecindad el conjunto de todas las soluciones potenciales que difieren de la solución actual en la mínima medida posible. Esto requiere que se defina una relación de vecindad en el espacio de búsqueda. Como ejemplo, la vecindad de la cobertura de vértices es otra cobertura de vértices que solo difiere en un nodo. Para la satisfacibilidad booleana , los vecinos de una asignación booleana son aquellos que tienen una única variable en estado opuesto. El mismo problema puede tener múltiples vecindarios distintos definidos; La optimización local con vecindades que implican cambiar hasta k componentes de la solución a menudo se denomina k-opt .
Normalmente, cada solución candidata tiene más de una solución vecina; la elección de cuál seleccionar se realiza utilizando únicamente información sobre las soluciones en la vecindad de la asignación actual, de ahí el nombre de búsqueda local . Cuando la elección de la solución vecina se realiza tomando la que maximiza localmente el criterio, es decir: una búsqueda codiciosa, la metaheurística toma el nombre de escalada de colinas . Cuando no hay vecinos que mejoren, la búsqueda local se detiene en un punto localmente óptimo . Este problema de óptimo local se puede solucionar mediante el uso de reinicios (búsqueda local repetida con diferentes condiciones iniciales), aleatorización o esquemas más complejos basados en iteraciones, como la búsqueda local iterada , en la memoria, como la optimización de la búsqueda reactiva, en modificaciones estocásticas sin memoria. , como recocido simulado .
La búsqueda local no ofrece garantía de que una solución determinada sea óptima. La búsqueda puede finalizar después de un tiempo determinado, o cuando la mejor solución encontrada hasta el momento no haya mejorado en un número determinado de pasos. La búsqueda local es un algoritmo en cualquier momento : puede devolver una solución válida incluso si se interrumpe en cualquier momento después de encontrar la primera solución válida. La búsqueda local suele ser una aproximación o un algoritmo incompleto, porque la búsqueda puede detenerse incluso si la mejor solución actual encontrada no es óptima. Esto puede suceder incluso si la terminación ocurre porque la mejor solución actual no se pudo mejorar, ya que la solución óptima puede estar lejos de la vecindad de las soluciones cruzadas por el algoritmo.
Schuurman y Southey proponen tres medidas de eficacia para la búsqueda local (profundidad, movilidad y cobertura): [2]
Plantean la hipótesis de que los algoritmos de búsqueda local funcionan bien, no porque tengan cierto conocimiento del espacio de búsqueda, sino porque se desplazan rápidamente a regiones prometedoras y exploran el espacio de búsqueda a bajas profundidades de la forma más rápida, amplia y sistemática posible.
La búsqueda local es un subcampo de:
Los campos dentro de la búsqueda local incluyen:
Existen varios métodos para realizar búsquedas locales de espacios de búsqueda de valor real :