Hispanopedia Wiki
La búsqueda local iterada [ 1 ] [ 2 ] ( ILS ) es un término en matemáticas aplicadas y ciencias de la computación que define una modificación de los métodos de búsqueda local o ascenso de colinas para resolver problemas de optimización discreta .
Los métodos de búsqueda local pueden quedarse atascados en un mínimo local , donde no hay vecinos que mejoren.
Una modificación sencilla consiste en repetir las llamadas a la rutina de búsqueda local, partiendo cada vez de una configuración inicial diferente. Esto se denomina búsqueda local repetida e implica que no se utiliza el conocimiento adquirido durante las fases previas de búsqueda local. El aprendizaje implica que se aprovecha el historial previo, por ejemplo, la memoria sobre los mínimos locales encontrados anteriormente, para generar puntos de partida cada vez mejores para la búsqueda local.
La suposición implícita es la de una distribución agrupada de mínimos locales : al minimizar una función, determinar buenos mínimos locales es más fácil partiendo de un mínimo local con un valor bajo que partiendo de un punto aleatorio. La única salvedad es evitar el confinamiento en una cuenca de atracción determinada, de modo que el impulso para transformar un minimizador local en el punto de partida para la siguiente ejecución debe ser suficientemente fuerte, pero no tanto como para evitar volver a reinicios aleatorios sin memoria.
La búsqueda local iterativa se basa en la construcción de una secuencia de soluciones localmente óptimas mediante:
- perturbando el mínimo local actual;
- Aplicar la búsqueda local después de partir de la solución modificada.
La intensidad de la perturbación debe ser suficiente para llevar la trayectoria a una cuenca de atracción diferente que conduzca a un óptimo local diferente .
Algoritmo de perturbación
Encontrar el algoritmo de perturbación para ILS no es tarea fácil. El objetivo principal es no quedarse atascado en el mismo mínimo local y, para garantizar esta propiedad, la operación de deshacer está prohibida. A pesar de esto, una buena perturbación debe considerar muchos valores, ya que existen dos tipos de perturbaciones malas:
- demasiado débil: volver al mismo mínimo local
- demasiado fuerte: reinicio aleatorio
Perturbación de referencia
El procedimiento consiste en fijar una serie de valores para la perturbación, de manera que estos valores sean significativos para la instancia: con una probabilidad promedio y no poco frecuente. Posteriormente, durante la ejecución, será posible consultar el gráfico de referencia para obtener una idea general de las instancias procesadas.
Perturbación adaptativa
Dado que no existe una función a priori que indique cuál es el valor más adecuado para una perturbación dada, el mejor criterio es lograr que sea adaptativo. Por ejemplo, Battiti y Protasi propusieron [ 3 ] un algoritmo de búsqueda reactiva para MAX-SAT que se ajusta perfectamente al marco ILS. Realizan un esquema de perturbación "dirigida" implementado 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 determinísticamente su intensidad durante la búsqueda.
Optimización de la perturbación
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 tras las perturbaciones tienden a ser muy buenas. Además, las nuevas partes también se optimizan.
Aplicaciones
El método se ha aplicado a varios problemas de optimización combinatoria , incluidos los problemas de programación de talleres de trabajo , [ 4 ] [ 5 ] problemas de flujo de taller, [ 6 ] problemas de enrutamiento de vehículos [ 7 ] así como muchos otros.
Referencias
- ↑ Lourenço, HR; Martin O.; Stützle T. (2010). "Búsqueda local iterada: marco y aplicaciones". Manual de metaheurísticas . Kluwer Academic Publishers, Serie internacional en investigación operativa y ciencias de la gestión. Vol. 146 (2.ª ed.). pp. 363–397 . CiteSeerX 10.1.1.187.2089 . doi : 10.1007/978-1-4419-1665-5_12 . ISBN 978-1-4419-1663-1.
- ↑ Lourenço, HR; Martin O.; Stützle T. (2003). "Búsqueda local iterada" . Manual de metaheurísticas . Serie internacional en investigación operativa y ciencias de la gestión. Vol. 57. Kluwer Academic Publishers. págs. 321–353 .
- ↑ Battiti, Roberto; Protasi, Marco (1997-01-01). "Búsqueda reactiva, una heurística sensible al historial para MAX-SAT" . ACM Journal of Experimental Algorithmics . 2 : 2–es. doi : 10.1145/264216.264220 . ISSN 1084-6654 .
- ↑ Lourenço, HR; Zwijnenburg M. (1996). «Combinación de la optimización de pasos grandes con la búsqueda tabú: aplicación al problema de programación de talleres». Metaheurísticas: teoría y aplicaciones . Kluwer Academic Publishers. Springer. pp. 219–236 . doi : 10.1007/978-1-4613-1361-8_14 . ISBN 9780792397007.
- ↑ Lourenço, HR (1995). "Programación de talleres: estudio computacional de métodos de búsqueda local y optimización de pasos grandes". European Journal of Operational Research . 83 (2): 347– 364. doi : 10.1016/0377-2217(95)00012-F .
- ↑ Juan, AA; Lourenço, H.; Mateo, M.; Luo, R.; Castella, Q. (2013). "Uso de la búsqueda local iterada para resolver el problema del taller de flujo: cuestiones de parametrización, aleatorización y paralelización" . International Transactions in Operational Research . Archivado del original el 2 de diciembre de 2012. Consultado el 20 de mayo de 2013 .
- ↑ Penna, Puca HV; Satori Ochi, L.; Subramanian, A. (2013). "Una heurística de búsqueda local iterada para el problema de enrutamiento de vehículos de flota heterogénea". Journal of Heuristics . 19 (2): 201– 232. doi : 10.1007/s10732-011-9186-y .
- ↑ «Roberto Cordone - Corsi - Algoritmi euristici (AA 2016/17)» .
- Algoritmos y métodos de optimización