Búsqueda local iterada [1] [2] ( ILS ) es un término en matemáticas aplicadas e informática que define una modificación de los métodos de búsqueda local o escalada para resolver problemas de optimización discreta.
Los métodos de búsqueda locales pueden quedarse estancados en un mínimo local , donde no hay vecinos mejorados disponibles.
Una modificación simple consiste en iterar llamadas a la rutina de búsqueda local, partiendo cada vez de una configuración inicial diferente. Esto se llama búsqueda local repetida , e implica que no se utiliza el conocimiento obtenido durante las fases anteriores de búsqueda local. El aprendizaje implica que la historia previa, por ejemplo la memoria sobre los mínimos locales encontrados previamente, se extrae para producir puntos de partida cada vez mejores para la búsqueda local.
El supuesto implícito es el de una distribución agrupada de mínimos locales : al minimizar una función, determinar buenos mínimos locales es más fácil cuando se parte de un mínimo local con un valor bajo que cuando se parte de un punto aleatorio. La única advertencia es evitar el confinamiento en una cuenca de atracción determinada, de modo que la patada para transformar un minimizador local en el punto de partida para la siguiente carrera debe ser apropiadamente fuerte, pero no demasiado fuerte para evitar volver a reinicios aleatorios sin memoria.
La búsqueda local iterada se basa en la construcción de una secuencia de soluciones localmente óptimas mediante:
La fuerza de la perturbación tiene que ser suficiente para llevar la trayectoria a una cuenca de atracción diferente que conduzca a un óptimo local diferente .
Encontrar el algoritmo de perturbación para ILS no es una tarea fácil. El objetivo principal es no quedarse estancado en el mismo mínimo local y, para garantizar esta propiedad, está prohibida la operación de deshacer. A pesar de esto, una buena permutación debe considerar muchos valores, ya que existen dos tipos de malas permutaciones:
El procedimiento consiste en fijar un número de valores para la perturbación tales que sean significativos para el caso: con probabilidad media y no raros. Después de eso, en tiempo de ejecución será posible verificar el gráfico de referencia para tener una idea promedio de las instancias pasadas.
Dado que no existe una función a priori que indique cuál es el valor más adecuado para una perturbación determinada, el mejor criterio es conseguir que sea adaptativo. Por ejemplo, Battiti y Protasi propusieron [3] un algoritmo de búsqueda reactiva para MAX-SAT que encaja perfectamente en el marco ILS. Realizan un esquema de perturbación "dirigido" que se implementa mediante un algoritmo de búsqueda tabú y después de cada perturbación aplican un algoritmo de descenso local estándar. Otra forma de adaptar la perturbación es cambiar de manera determinista su fuerza durante la búsqueda.
Otro procedimiento consiste en optimizar una subparte del problema manteniendo activa la propiedad de no deshacer. Si este procedimiento es posible, todas las soluciones generadas después de las perturbaciones tienden a ser muy buenas. Además, las piezas nuevas también están optimizadas.
El método se ha aplicado a varios problemas de optimización combinatoria, incluidos los problemas de programación de talleres , [4] [5] problemas de taller de flujo, [6] problemas de rutas de vehículos [7] y muchos otros.
{{cite book}}: |journal=ignorado ( ayuda ){{cite book}}: |journal=ignorado ( ayuda )[1]