Perturbaciones adaptativas
La experiencia muestra que no existe a priori un mejor tamaño para la perturbación
Motiva a modificar la fuerza de la perturbación y adaptarla durante la corrida:
Explotando la historia de la búsqueda
Cambiar determinísticamente la fuerza durante la búsqueda (oscilaciones estratégicas)
Velocidad
Empíricamente ILS tiene mayor velocidad para ejecutar búsquedas locales que random restart
Componentes
Generar solución inicial
Búsqueda local
Perturbación
Criterio de aceptación
Criterio de aceptación
La perturbación junto con la búsqueda local definen las posibles transiciones entre la solución actual s* y una solución vecina s*’
El criterio de aceptación determina cuando s*’ es aceptado o no
Puede usarse para controlar el balance entre intensificación y diversificación de la búsqueda
Criterios de aceptación
Better:
Logra fuerte intensificación
Solo acepta mejores soluciones
Criterios de aceptación
Random Walk
Siempre aplica la perturbación al óptimo local más recientemente visitado, sin considerar su costo
Favorece diversificación sobre intensificación
Muchas otras opciones intermedias son posibles
Criterios de aceptación
Restart
Cuando la intensificación parece inefectiva se debería re-comenzar completamente el algoritmo de ILS
Ej: recomenzar cuando no se obtienen mejoras para un número determinado de iteraciones
Ejemplo: TSP
Se comparó ILS utilizando RW y Better contra Random Restart
ILS alcanzó mejores soluciones utilizando la misma búsqueda local
Para TSP las buenas soluciones están clustereadas
Buena estrategia: incorporar intensificación
Better: Mejores resultados (corridas cortas)
Optimización global de ILS
Al focalizarnos en un componente, consideramos fijos todos los demás.
La optimización de un componente depende de las elecciones en los otros.
Ignoramos en la optimización la generación de la solución inicial
Optimización global de ILS (cont)
La Perturbación depende de la Búsqueda local elegida.
El Criterio de aceptación depende de la Búsqueda local y la Perturbación.
Aproximación al problema de optimización global: optimizar sucesivamente cada componente, hasta no obtener mejoras en ninguno de ellos.
Optimización iterativa.
Optimización global de ILS (cont)
El algoritmo ILS deberá ser robusto
Los investigadores implementan versiones de búsquedas locales iteradas con cierto nivel de optimización global y luego se testea el éxito de performance con ciertos benchmarks estandarizados.
Características del espacio de búsqueda
Si las mejores soluciones están clustereadas en S* (TSP), será útil la intensificación mejorando la probabilidad de encontrar el óptimo global.
Si el clustering es incompleto (QAP, MAX-SAT, graph bi-section), será útil luego de una fase de intensificación, explorar otras regiones de S*.
El balance entre intensificación y diversificación es importante y desafiante.
Aplicaciones
TSP
Problemas de planificación
Bipartición de grafos
MAX-SAT
Es crítica la elección del algoritmo de búsqueda local para obtener muy buena performance
Optimizar globalmente los demás componentes
Utilizar propiedades específicas del problema a resolver
ILS
Es una metaheurística versátil que puede adaptarse a diferentes tipos de problemas de optimización combinatoria
Perturbaciones sofisticadas y búsqueda diversificada son esenciales para alcanzar la mejor performance posible
Relación con otras metaheurísticas
Metaheurísticas basadas en vecindades
Recocido simulado (SA)
Búsqueda Tabú (TS)
Búsqueda local guiada (GLS)
Metaheurísticas basadas en multi-comienzo (multi-start)
GRASP
Colonia de hormigas (ACO)
Algoritmos evolutivos (EA)
Búsqueda dispersa
Búsqueda en vecindades variables
ILS
Metaheurísticas basadas en vecindades
Evitan quedarse en óptimos locales, permitiendo peores soluciones en su vecindad
Las metaheurísticas difieren principalmente en las estrategias de movimiento
Para usarlas como algoritmo de búsqueda local en ILS debemos limitar el tiempo de corrida, en gral. obtienen buenas soluciones, pero con largo tiempo de computación
Metaheurísticas basadas en multi-comienzo
Clasificación en
Constructivas: GRASP, ACO
Basadas en perturbación
ILS no construye soluciones
ILS puede ser usado embebida en lugar de una búsqueda local en algoritmos como ACO o GRASP
Relación con otras metaheurísticas (cont)
Otra clasificación:
Basadas en poblaciones:
EA
Búsqueda dispersa
ACO
Basadas en una sola solución actual:
ILS
Relación con otras metaheurísticas (cont)
En general las basadas en poblaciones son más complejas que las de una solución
La complejidad se justifica al mejorar la performance
Se han propuesto algunas extensiones de ILS basadas en poblaciones y logrado soluciones de gran calidad
Relación con otras metaheurísticas (cont)
La búsqueda de vecindades variables (VNS) es la metaheurística más cercana a ILS:
VNS básica puede verse como una ILS con Better como criterio de aceptación y con una forma sistemática de variar la fuerza de la perturbación
Las fronteras de las distintas metaheurísticas no están claramente definidas, y hay métodos híbridos que las combinan, pudiendo ir de una metaheurística a otra
En el futuro…
ILS podría aplicarse a
Problemas donde las restricciones son muy severas
Problemas multi-objetivo
Problemas dinámicos o de tiempo real
Aún debe mejorarse:
Entendimiento de la relación de sus componentes
Uso de la memoria
Intensificación y diversificación explícita
Mayor inclusión de conocimiento de cada problema específico.
Conclusiones
ILS tiene varias características deseables
Simple
Fácil de implementar
Robusta
Altamente efectiva
Idea esencial: Focalizar la búsqueda en el espacio de soluciones localmente óptimas.
Conclusiones (cont)
El éxito se basa en el muestreo parcial del conjunto de óptimos locales
La efectividad depende de la elección de la búsqueda local, perturbación y criterio de aceptación.
Aunque las implementaciones de las partes sean muy simples, ILS se comporta mejor que Random Restart
Conclusiones (cont)
Si ILS se optimiza adaptándola al problema se torna un algoritmo competitivo.
ILS se puede optimizar progresivamente, manteniendo el nivel de simplicidad deseado
Su naturaleza modular conlleva a menores tiempos de desarrollo
Al tratar a su heurística embebida como caja negra, puede utilizar una nueva y mejor búsqueda local casi inmediatamente
Aplicación de ILS a TSP
Problema de prueba reconocido
Buena performance permite valorar las ideas de la metaheurística que se proponen
Se logró buena performance utilizando
Como búsqueda local la heurística Lin-Kernighan (la mejor para TSP)
Como perturbación double-bridge move
Como criterio de aceptación el algoritmo uno del tipo de SA (LSMC)
Para la generación de la solución inicial se obtuvo peor performance con tours iniciales aleatorios que con generados por heurísticas greedy
Aplicación de ILS a TSP (cont)
Un estudio concluye que el criterio de aceptación Better muestra estancamiento, luego de largo rato de corrida, debido a gran intensificación.
Propuso un criterio para diversificar, buscando soluciones que estén a cierta distancia mínima de la posición actual -> Mostró ser muy efectivo
Otra perturbación propuesta es llamada genetic transformation
Utiliza dos tours, el mejor encontrado y otro previamente encontrado. Perturba al mejor encontrado y se buscan los subtours en común. Luego éstos son reconectados empleando un algoritmo greedy -> Resultó muy efectivo
Relación con otras metaheurísticas (cont)
La búsqueda de vecindades variables (VNS) es la metaheurística más cercana a ILS:
VNS básica puede verse como una ILS con Better como criterio de aceptación y con una forma sistemática de variar la fuerza de la perturbación
La mayor diferencia se encuentra en que:
ILS tiene el objetivo de generar un camino en el conjunto de soluciones óptimas locales
VNS se deriva de cambiar sistemáticamente las vecindades durante la búsqueda
Metaheurísticas basadas en vecindades (cont)
Cuánto tiempo debemos correr la búsqueda embebida para alcanzar un buen balance entre el tiempo de computación y la calidad de la solución?
Depende del tiempo de computación que disponemos y cómo mejoran los costos con el tiempo.
Otra conexión entre los ILS, SA y TS parte de ciertas similaridades:
SA puede ser visto como un ILS sin la fase de búsqueda local
TS utiliza memoria como característica principal, aprovechando la historia, se espera que esto se incorpore en aplicaciones de ILS futuras.
 Página anterior | Volver al principio del trabajo | Página siguiente  |