Iterated Local Search

Método de búsqueda soluciones basado en Local Search, pero a diferencia de este, se generan vecinos a partir de la solución encontrada en el método mencionado anteriormente. De esta forma se evita el estancamiento en óptimos locales, favoreciendo la exploración de soluciones.

Para llevar a cabo esta exploración, se realizan perturbaciones de la solución encontrada, usando movimiento swap, 2opt o 3opt aleatorio.

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. Se aplica el método Local Search a la solución actual (s), con el fin de encontrar la mejor solución en el espacio de búsqueda local. Además, se restablece el ciclo o número de perturbación (N) al valor 0.
3. Se realiza un procedimiento de perturbación a elección (swap, 2opt o 3opt aleatorio) a la solución actual (s) y se aumenta el contador de numero de perturbación (N) en 1.
4. Mientras el contador de numero de perturbación (N) no supere el valor máximo de perturbaciones (Nmax) configurado al inicio de la ejecución, se repite el proceso 3.
5. Cuando el número de perturbaciones (N) supere el valor máximo (Nmax), se comprueba si la solución actual (s) generada por las perturbaciones tiene un valor optimo en comparación a la mejor solución (s*). En caso de que se cumpla la validación, se reemplaza el valor de s* con el de s.
6. Si se cumple la condición de termino (iteraciones máximas, evaluaciones máximas o tiempo de ejecución), se retorna el valor de la mejor solución (s*). En caso contrario, se repite el proceso desde el punto 2.

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