Búsqueda local (optimización)

En informática, la búsqueda local es un método heurístico para resolver problemas de optimización computacionalmente complicados. La búsqueda local se puede utilizar en problemas que se pueden formular como encontrar una solución que maximiza 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) mediante la aplicación de cambios locales, hasta que se encuentra una solución que se considera óptima o transcurre un límite de tiempo.

Los algoritmos de búsqueda local se aplican ampliamente a numerosos problemas informáticos complejos, 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 de comercio y el algoritmo Metropolis-Hastings.

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 objetiva en lugar de una exploración explícita de el espacio de solución.

Ejemplos

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

1. El problema de la cubierta de vértice, en el que una solución es una cubierta de 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 vendedor de viajes, en el que una solución es un ciclo que contiene todos los nodos del gráfico y el objetivo es minimizar la longitud total del ciclo
3. El problema de satisfiabilidad booleana, 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 de uso solamente si satisface Todos cláusulas
4. El problema de programación de enfermeras donde una solución es una asignación de enfermeras a turnos que satisfacen todas las restricciones establecidas
5. El problema de agrupación k-medoid y otros problemas relacionados con la ubicación de las instalaciones para los cuales la búsqueda local ofrece las mejores relaciones de aproximación conocidas desde una perspectiva peor de casos
6. El problema Hopfield Neural Networks para el cual encontrar configuraciones estables en la red Hopfield.

Descripción

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 sea 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; siendo un vecindario 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 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 implica 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 toma utilizando solo 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 hace tomando localmente la que maximiza el criterio, es decir: una búsqueda codiciosa, 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 ó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 búsqueda local iterada, en memoria, como optimización de búsqueda reactiva, en modificaciones estocásticas sin memoria., como recocido simulado.

La búsqueda local no garantiza que una solución dada sea óptima. La búsqueda puede terminar después de un límite de tiempo dado, o cuando la mejor solución encontrada hasta el momento no 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 después de encontrar la primera solución válida. La búsqueda local suele ser una aproximación o un algoritmo incompleto, ya que la búsqueda puede detenerse incluso si la mejor solución actual encontrada no es la ó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 & Southey propone tres medidas de efectividad para la búsqueda local (profundidad, movilidad y cobertura):

• profundidad: el costo de la solución actual (mejor);
• movilidad: la capacidad de moverse rápidamente a diferentes áreas del espacio de búsqueda (conservar el costo bajo);
• cobertura: cómo sistemáticamente la búsqueda cubre el espacio de búsqueda, la distancia máxima entre cualquier asignación sin explotar y todas las asignaciones visitadas.

Suponen 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 a regiones prometedoras y exploran el espacio de búsqueda a poca profundidad de la manera más rápida, amplia y sistemática posible.