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 se pueden formular como la búsqueda de 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 soluciones candidatas (el espacio de búsqueda ) aplicando cambios locales, hasta que se encuentra una solución considerada óptima o transcurre un tiempo determinado.
Los algoritmos de búsqueda local se aplican ampliamente a numerosos problemas computacionales difíciles, incluidos problemas de informática (en particular inteligencia artificial ), matemáticas , investigación de operaciones , ingeniería y bioinformática . Algunos ejemplos de algoritmos de búsqueda local son WalkSAT, el algoritmo 2-opt 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: si bien 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 soluciones.
Algunos problemas donde se ha aplicado la búsqueda local son:
La mayoría de los problemas se pueden formular en términos de un espacio de búsqueda y un objetivo de varias maneras diferentes. Por ejemplo, para el problema del viajante de comercio, 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 con una solución candidata y luego se mueve iterativamente a una solución vecina ; un vecindario es el conjunto de todas las soluciones potenciales que difieren de la solución actual en la extensión mínima posible. Esto requiere que se defina una relación de vecindad en el espacio de búsqueda. Como ejemplo, el vecindario 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 sola variable en un estado opuesto. El mismo problema puede tener múltiples vecindarios distintos definidos en él; la optimización local con vecindarios que implican cambiar hasta k componentes de la solución a menudo se conoce como k-opt .
Por lo general, cada solución candidata tiene más de una solución vecina; la elección de cuál seleccionar se toma utilizando solo información sobre las soluciones en el vecindario 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 voraz, la metaheurística toma el nombre de escalada de colinas . Cuando no hay vecinos que mejoren presentes, la búsqueda local se atasca en un punto localmente óptimo . Este problema de óptimos locales se puede solucionar utilizando 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 memoria, como la optimización de búsqueda reactiva, en modificaciones estocásticas sin memoria, como el recocido simulado .
La búsqueda local no garantiza que una solución dada sea óptima. La búsqueda puede terminar después de un tiempo determinado o cuando la mejor solución encontrada hasta el momento no haya mejorado en una cantidad determinada de pasos. La búsqueda local es un algoritmo que funciona 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 finalización se produce 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 atravesadas por el algoritmo.
Schuurman y Southey proponen tres medidas de eficacia para la búsqueda local (profundidad, movilidad y cobertura): [2]
Su hipótesis es que los algoritmos de búsqueda local funcionan bien, no porque tengan algún conocimiento del espacio de búsqueda, sino porque se mueven rápidamente hacia 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 con valores reales :