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
| Página siguiente |