PresentG1 LS

Búsqueda Local
Grupo 1:
Verónica Giaudrone
Marcelo Vaccaro
Artículo: “Iterated Local Search”
Lourenço, Martin, Stützle

Agenda


Introducción



Iterando en Búsqueda local

Random Search

Búsqueda en S*

Iterated Local Search
Iterated Local Search

Mejorando Performance

Componentes

Optimización global

Aplicaciones

Relaciones con otras Metaheurísticas

Futuro
Conclusiones



Introducción







Importancia de algoritmos de alta
performance para problemas
difíciles de optimización
Una Metaheurística debe ser:

simple

efectiva

en lo posible general
Caso ideal: Puede ser usada sin ningún
conocimiento del problema
Metaheurísiticas se volvieron más sofisticadas,
y este ideal se dejó de lado por mejor
performance

Introducción (cont)


Incorporación deconocimiento específico del
problema en la metaheurísitca




Hace más difusa la diferencia entre heurística y
metaheurística

Solución: Modularidad y descomposición de
la metaheurística en partes:

Totalmente de
propósito general

Conocimiento específico
del problema

Introducción (cont)


Esencia de Iterated Local Serach:




Construye iterativamente una secuencia de
soluciones generadas por laheurística embebida

Mejores soluciones que repetidas corridas
aleatorias de la heurística

Puntos que hacen a un algoritmo ser un
Iterated local search:




Debe seguir una cadena simple (excluye
algoritmos basados en poblaciones)
La búsqueda de mejores soluciones ocurre en un
espacio reducido definido por la salida de la
heurística de “caja-negra”

Consideraciones





Sea C la función decosto a minimizar
Sea s una solución candidata y S el
conjunto
Asumimos que la búsqueda local es:





Determinística
Sin memoria

La búsqueda local define un mapeo
entre S y S*, siendo S* el conjunto de
soluciones s* localmente óptimas.

Costo




La distribución de costos:

Forma de campana

Media y varianza menor
para las soluciones de
S* que para las de S.
Es mejor utilizar búsquedalocal, que muestrear
aleatoriamente en S si se
buscan soluciones con bajo
costo.

Agenda


Introducción



Iterando en Búsqueda local








Random Search
Búsqueda en S*
Iterated Local Search

Iterated Local Search

Mejorando Performance

Componentes

Optimización global

Aplicaciones

Relaciones con otras Metaheurísticas

Futuro
Conclusiones

Iterando en búsqueda local


Búsquedalocal: Es la heurística embebida
que utilizará la metaheurística.





La búsqueda local mejorada mediante
iteración:







Dependerá del problema a resolver
Puede no ser de hecho una búsqueda local

En la práctica se obtienen mejoras significativas.
Sólo en casos patológicos la mejora es mínima.

Random Restart
Búsqueda en S*
Búsqueda Local Iterada

Búsqueda local como caja negra


Reducir los costos sin modificar la
búsqueda local, utilizándola como
rutina de caja negra
La búsqueda local:


Toma un elemento de S para el cual C
tiene una media alta, hacia S* donde C
tiene un media menor

Búsqueda local




Los movimientos se realizan sólo si se
mejora la solución
Procedure BúsquedaLocal
s = GenerarSoluciónInicial()
repeat
s = Mejorar(s, vecindad(s))

until no hay mejoraposible
N (σ 0 )

Solución inicial

σ0

N (σ1 )

σ1

N (σ 2 )

σ2

σ3

N (σ 4 )

σ4

Óptimo local
N (σ 3 )

Iterando en Búsqueda local




Random Restart
Búsqueda en S*
Búsqueda Local Iterada

Random restart


La forma más simple de mejorar el costo
encontrado por una búsqueda local:





Repetir la búsqueda desde otro punto de
inicio.

Cada s* generado será independiente
Aunque muchas veceses una estrategia
útil, pierde utilidad a medida que crece el
espacio de búsqueda.

Random Restart (cont)


Estudios empíricos indican que en
espacios de búsqueda grandes los
costos de búsqueda local llevan a
costos que:




Media excede el costo óptimo en un
porcentaje fijo.
Distribución extremadamente “en pico”
en la media cuando el tamaño del
espacio tiende a infinito.

Random Restart...