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 |