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 de conocimiento 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íficodel problema
Introducción (cont)
Esencia de Iterated Local Serach:
Construye iterativamente una secuencia de soluciones generadas por la heurí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 de costo 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úsqueda local, que muestrear aleatoriamente en S si se buscan soluciones con bajo costo.
Iterando en búsqueda local
Búsqueda local: Es la heurística embebida que utilizará la metaheurística.
Dependerá del problema a resolver
Puede no ser de hecho una búsqueda local
La búsqueda local mejorada mediante iteración:
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 mejora posible
(Gp:) Solución inicial
(Gp:) Óptimo local
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 veces es 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 (cont)
Muestreo aleatorio tiene cada vez más baja probabilidad de encontrar soluciones de bajo costo a medida que crece el tamaño del espacio de búsqueda
Se necesita entonces una muestra parcial
Iterando en Búsqueda local
Random Restart
Búsqueda en S*
Búsqueda Local Iterada
Búsqueda en S*
Para evitar el problema de los grandes espacios de búsqueda
Invocar recursivamente
Utilizar búsqueda local para ir desde S* a S** donde la media del costo sería aún menor.
Generaríamos una jerarquía de búsquedas locales anidadas
Búsqueda en S* (cont)
¿Cómo formulamos la búsqueda local en el nivel más bajo de la jerarquía?
Búsqueda local requiere una estructura de vecindad que no viene dada a priori.
Difícil definir vecinos en S* que puedan ser enumerados y accedidos eficientemente.
Noción de cercanía y luego aplicar búsqueda estocástica en S*.
Iterando en Búsqueda local
Random Restart
Búsqueda en S*
Búsqueda Local Iterada
Página siguiente  |