Algoritmos de Búsqueda Local (página 2)

Partes: 1, 2, 3

Iterated Local Search – ILS(Búsqueda local iterada)
Explorar S* recorriendo desde un s* hacia otro cercano sin necesidad de la noción de vecindad
Iterated local search logra esto heurísticamente

Iterated Local Search
Dado s* aplicamos una perturbación que genera un estado intermedio s’ (perteneciente a S)
Aplicamos búsqueda local a s’ y alcanzamos una solución s*’ en S*
Si s*’ supera el test de aceptación entonces será el próximo elemento del camino en S*, si no se retorna a s*.
Camino resultante es un caso de búsqueda estocástica sobre S*

Metaheurística
Procedure Iterated Local Search
s0 = GenerateInitialSolution
s* = LocalSearch(s0)
repeat
s’ = Perturbation(s*, history)
s*’ = LocalSearch(s’)
s* = AcceptanceCriterion(s*, s*’, history)
until termination condition met
end

ILS con o sin memoria
Mucha complejidad del ILS puede estar escondida en el uso de la historia.
Mayoría de los trabajos hasta ahora NO utilizan memoria
Perturbación y criterio de aceptación no utilizan soluciones previamente visitadas. Caminos “Markovianos”
Si la perturbación depende de algún s* anterior, entonces el camino en S* es con memoria.
Trabajos recientes que la incorporan han obtenido mejoras en la performance.

Resumiendo…
Poder de ILS proviene de la guía que ofrece en el muestreo del conjunto de óptimos locales.
Eficiencia del muestreo depende de:
Tipo de perturbación
Criterio de aceptación
A pesar de contar con implementaciones muy simples de esas partes, ILS es mucho mejor que RR

Resumiendo…(cont)
Mejores resultados si se optimizan los módulos que la componen.
La complejidad puede agregarse de forma modular
Es rápido: se pueden realizar k búsquedas locales embebidas en ILS más rápido que realizar las k búsquedas locales con RR

Obteniendo mejor performance
Existen 4 componentes a considerar:
Generar solución inicial
Búsqueda local
Perturbación
Criterio de aceptación

Obteniendo mejor performanceConsideraciones
Se puede comenzar con:
Solución aleatoria
Solución de alguna heurística de construcción “greedy”
Para la mayoría de los problemas existe un algoritmo de búsqueda local ya disponible
Para la perturbación, un movimiento aleatorio de mayor orden que el usado en la búsqueda local puede ser muy efectivo
Primera idea: forzar que el costo decrezca

Obteniendo mejor performance (cont)
Fácil mejorar la performance, mejorando cada uno de los 4 módulos
Debido a:
Complejidad se reduce por la modularidad
Función de cada componente es fácil de entender
Optimización global de ILS: como cada componente afecta al siguiente, se debe entender la interacción entre ellos
Conclusión: El desarrollador puede elegir el nivel de optimización que quiera aplicar

Componentes
Generar solución inicial
Búsqueda local
Perturbación
Criterio de aceptación

Solución inicial
La búsqueda local aplicada a la solución inicial s0 da el punto de partida s0*
Soluciones standard para s0:
Solución inicial aleatoria
Solución retornada por heurística constructiva “greedy” Ventajas contra la solución aleatoria:
Combinada con la búsqueda local resulta en soluciones s0* de mejor calidad
Una búsqueda local a partir de una solución “greedy”, en promedio requiere menos tiempo de CPU

Solución inicial (cont)
Tiempos de computación cortos:
La solución inicial es muy importante para obtener soluciones de alta calidad
Tiempos de computación largos:
La dependencia de la solución final respecto de s0 se pierde cuando se realiza el recorrido en S*
No hay siempre una opción clara acerca de cual es la mejor solución inicial
Pocas corridas: soluciones greedy parecen obtener soluciones de bajo costo rápidamente.
Muchas corridas: solución inicial parece ser menos relevante.

Componentes
Generar solución inicial
Búsqueda local
Perturbación
Criterio de aceptación

Búsqueda Local
Búsqueda local iterada sensible a la elección de su heurística embebida
Debe optimizarse la elección lo más posible.
No siempre la mejor búsqueda local lleva a una mejora en ILS
Si el tiempo de computación es fijo, puede ser mejor aplicar con más frecuencia un algoritmo de búsqueda local más rápido aunque menos efectivo, que uno más lento y más poderoso.

Búsqueda Local (cont)
La elección debe basarse en cuánto más tiempo de computación se necesita para correr la mejor heurística
Sin sentido utilizar una búsqueda local excelente si sistemáticamente deshace la perturbación
Por esto se requiere una optimización global de ILS
Para TSP el algoritmo de búsqueda local que se comporta mejor y más rápido es el de Lin-Kernighan.

Componentes
Generar solución inicial
Búsqueda local
Perturbación
Criterio de aceptación

Perturbación
Fuerza de la perturbación: Número de componentes de la solución que son modificados
La búsqueda local no debería ser capaz de deshacer la perturbación, ya que se caería en un óptimo local ya visitado
Se pueden obtener mejores resultados si las perturbaciones tienen en cuenta propiedades del problema

Perturbación (cont)
Cuanto debe cambiar la perturbación a la solución inicial?
Muy fuerte:
ILS se comporta como random restart y mejores soluciones solo se encuentran con una baja probabilidad
Muy suave:
La búsqueda local cae frecuentemente en un óptimo local ya visitado y la diversificación de la búsqueda queda muy limitada

Perturbación (cont)
Problemas simples (como TSP):
Se puede obtener resultados satisfactorios usando perturbaciones de tamaño fijo
Ej.: Perturbación exitosapara TSP es eldouble-bridge move

Perturbación (cont)
Problemas más complejos:
Usar perturbaciones de largo fijo puede llevar a una pobre performance
Regla general: Perturbaciones suaves usualmente llevan a ejecuciones más rápidas de la búsqueda local, como desventaja se puede caer en el mismo óptimo local