Búsqueda local (optimización) - Local search (optimization)

En ciencias de la computación , 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 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 ) mediante la aplicación de cambios locales, hasta que se encuentra una solución considerada óptima o 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 (en particular, 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 .

Ejemplos de

Algunos problemas donde se ha aplicado la búsqueda local son:

  1. El problema de la cobertura de vértices , en el que una solución es la cobertura de un vértice de un gráfico , y el objetivo es encontrar una solución con un número mínimo de nodos.
  2. El problema del viajante de comercio , en el que una solución es un ciclo que contiene todos los nodos del gráfico y el objetivo es minimizar la duración total del ciclo.
  3. El problema de satisfacibilidad booleano , en el que una solución candidata es una asignación de verdad, y el objetivo es maximizar el número de cláusulas satisfechas por la asignación; en este caso, la solución final es útil solo si satisface todas las cláusulas
  4. El problema de programación de enfermeras donde una solución es una asignación de enfermeras a turnos que satisfaga todas las restricciones establecidas.
  5. El problema de la agrupación de k-medoides y otros problemas relacionados con la ubicación de las instalaciones para los que la búsqueda local ofrece las relaciones de aproximación más conocidas desde la perspectiva del peor de los casos.
  6. El problema de las redes neuronales de Hopfield para el que se encuentran configuraciones estables en la red de Hopfield .

Descripción

La mayoría de los problemas se pueden formular en términos de espacio de búsqueda y destino de diferentes maneras. Por ejemplo, para el problema del viajante de comercio, una solución puede ser un ciclo y el criterio para maximizar es una combinación del número de nodos y la duración del ciclo. 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 . Esto solo es posible si se define una relación de vecindad en el espacio de búsqueda. Como ejemplo, la vecindad de una cubierta de vértice es otra cubierta de vértice que solo difiere en un nodo. Para la satisfacibilidad booleana, los vecinos de una asignación de verdad suelen ser las asignaciones de verdad que solo difieren de ella por la evaluación de una variable. El mismo problema puede tener múltiples vecindarios diferentes definidos; La optimización local con vecindarios 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 a cuál moverse se toma utilizando solo información sobre las soluciones en la vecindad de la actual, de ahí el nombre búsqueda local . Cuando la elección de la solución vecina se realiza tomando la que maximiza el criterio localmente, la metaheurística toma el nombre de escalada . Cuando no hay configuraciones de mejora presentes en el vecindario, la búsqueda local se bloquea en un punto localmente óptimo . Este problema de óptimos locales se puede solucionar utilizando reinicios (búsqueda local repetida con diferentes condiciones iniciales) o esquemas más complejos basados ​​en iteraciones, como búsqueda local iterada , en memoria, como optimización de búsqueda reactiva, en modificaciones estocásticas sin memoria, como recocido simulado .

La terminación de la búsqueda local puede basarse en un límite de tiempo. Otra opción común es terminar cuando la mejor solución encontrada por el algoritmo no se ha 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 antes de que finalice. Los algoritmos de búsqueda local suelen ser algoritmos de aproximación o incompletos , ya que la búsqueda puede detenerse incluso si la mejor solución encontrada por el algoritmo no es la óptima. Esto puede suceder incluso si la terminación se debe a la imposibilidad de mejorar la solución, ya que la solución óptima puede estar lejos de la vecindad de las soluciones cruzadas por los algoritmos.

Para problemas específicos, es posible idear vecindarios que sean muy grandes, posiblemente de tamaño exponencial. Si la mejor solución dentro del vecindario se puede encontrar de manera eficiente, dichos algoritmos se denominan algoritmos de búsqueda de vecindario a muy gran escala .

Ver también

La búsqueda local es un subcampo de:

Los campos dentro de la búsqueda local incluyen:

Espacios de búsqueda con valor real

Existen varios métodos para realizar búsquedas locales de espacios de búsqueda de valor real :

Referencias

Bibliografía