Búsqueda local es la base de muchos de los métodos usados en problemas de optimización.
Se puede ver como un proceso iterativo que empieza en una solución y la mejora realizando modificaciones locales.
Básicamente empieza con una solución inicial y busca en su vecindad por una mejor solución. Si la encuentra, reemplaza su solución actual por la nueva y continua con el proceso, hasta que no se pueda mejorar la solución actual (ver tabla 4.1).
Cláramente el diseño de la vecindad es crucial para el desempeño de éste, y de muchos otros, algoritmos.
La vecindad son todas las posibilidades de soluciones que se consideran en cada punto.
El cómo se busca la vecindad y cuál vecino se usa en el reemplazo a veces se conoce como la regla de pivoteo (pivoting rule), que en general puede ser:
Búsqueda local tiene la ventaja de encontrar soluciones muy rápidamente.
Su principal desventaja es que queda atrapada fácilmente en mínimos locales y su solución final depende fuertemente de la solución inicial.
Búsqueda local es un método determinístico y sin memoria. Dada una misma entrada, regresa la misma salida.
De hecho un conjunto de entradas nos generan la misma salida (mínimo local). Esto se puede ver como un pozo de atracción.
Esto sigue siendo muy superior a búsqueda aleatoria y el ingrediente principal es la definición de vecindad que permite moverse de una cierta solución a una mejor solución.
