Local Search

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 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 considerada óptima.

El procedimiento de ejecución del algoritmo se rige por las siguientes operaciones:

1. Se genera una solución inicial, denominada como solucion actual (s), la cual a su vez será considerada la mejor solución (s*).
2. Luego se limita el espacio de búsqueda a los vecinos de la solución, llamado movimiento del espacio de búsqueda.
3. Se genera una solucion vecina (s') a partir de la solución actual (s).
4. Se comprueba que el nuevo vecino (s’) sea una mejor solución que la actual (s), se presentan dos situaciones:
   1. Si el vecino (s’) es peor solución a la actual (s), se genera un nuevo vecino de la solución actual (s). En caso de no poder generar mas soluciones vecinas (s’), se devuelve la mejor solución encontrada (s*).
   2. Si el vecino (s’) es mejor que la solución actual (s), el vecino se convierte en la solución actual (s) y además en la mejor solución (s*).
5. Cuando la mejor solución encontrada (s*) es la mejor solución entre los vecinos generados de la solución actual (s) se le considera una solución Best Improvement:
   1. En caso de que se cumpla esta condición, se vuelve al paso 2, repitiendo el proceso.
   2. En caso de no cumplir esta condición, se vuelve al paso 3, hasta encontrar la mejor solución entre los posibles vecinos.
6. La ejecución finaliza cuando ya no es posible encontrar un mejor vecino (s´) de la solución actual (s) o por condición de término (iteraciones máximas, evaluaciones máximas o tiempo de ejecución).

Con el fin de facilitar la comprensión del algoritmo, se presenta un diagrama de flujo: