Búsqueda local guiada

La búsqueda local guiada es un método de búsqueda metaheurístico . Un método metaheurístico es un método que se basa en un algoritmo de búsqueda local para modificar su comportamiento.

La búsqueda local guiada (GLS) acumula penalizaciones durante la búsqueda. Estas penalizaciones ayudan a los algoritmos de búsqueda local a escapar de mínimos y estancamientos locales. Cuando el algoritmo de búsqueda local se estanca en un óptimo local, GLS modifica la función objetivo mediante un esquema específico (que se explica más adelante). A continuación, la búsqueda local opera con una función objetivo aumentada, diseñada para sacar al algoritmo del óptimo local. La clave reside en la forma en que se modifica la función objetivo.

El método en su forma actual fue desarrollado por el Dr. Christos Voudouris y detallado en su tesis doctoral. ^{[ 1 ]} GLS se inspiró en GENET, una arquitectura de red neuronal para resolver problemas de satisfacción de restricciones, desarrollada por Chang Wang, Edward Tsang y Andrew Davenport, y la extendió. El mecanismo de escape de mínimos locales tanto de GLS como de GENET se asemeja al aprendizaje por refuerzo .

Para aplicar GLS, es necesario definir características de la solución para el problema dado. Estas características se definen para distinguir entre soluciones con características diferentes, de modo que se puedan identificar y evitar regiones de similitud alrededor de los óptimos locales. La elección de las características de la solución depende del tipo de problema y, en cierta medida, del algoritmo de búsqueda local. Para cada característica se define una función de coste . ${\displaystyle f_{i}}$${\displaystyle c_{i}}$

Cada característica también está asociada a una penalización (inicialmente establecida en 0) para registrar el número de ocurrencias de la característica en mínimos locales. ${\displaystyle p_{i}}$

Las características y los costos suelen derivarse directamente de la función objetivo. Por ejemplo, en el problema del viajante, una característica puede ser si el recorrido va directamente de la ciudad X a la ciudad Y. El costo puede ser la distancia entre X e Y. En los problemas SAT y MAX-SAT ponderado, las características pueden ser si la cláusula C se cumple con las asignaciones actuales.

A nivel de implementación, definimos para cada característica una función indicadora que señala si la característica está presente en la solución actual o no. es 1 cuando la solución presenta la propiedad , 0 en caso contrario. ${\displaystyle i}$${\displaystyle I_{i}}$${\displaystyle I_{i}}$${\displaystyle x}$${\displaystyle i}$

GLS calcula la utilidad de penalizar cada característica. Cuando el algoritmo de búsqueda local devuelve un mínimo local x, GLS penaliza todas aquellas características (mediante incrementos en la penalización de las características) presentes en esa solución que tienen la máxima utilidad, , como se define a continuación. ${\displaystyle \operatorname {util} (x,i)}$

${\displaystyle \operatorname {util} (x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.}$

La idea es penalizar las características que tienen costes elevados, aunque la utilidad de hacerlo disminuye a medida que la característica se penaliza con mayor frecuencia.

GLS utiliza una función de coste aumentada (definida más adelante) para guiar el algoritmo de búsqueda local fuera del mínimo local, penalizando las características presentes en dicho mínimo. La idea es que el mínimo local resulte más costoso que el espacio de búsqueda circundante, donde estas características no están presentes.

${\displaystyle g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}}$

El parámetro λ puede utilizarse para modificar la intensificación de la búsqueda de soluciones. Un valor mayor de λ dará lugar a una búsqueda más diversa, donde las mesetas y cuencas se exploran de forma menos exhaustiva; un valor menor dará lugar a una búsqueda más intensiva de la solución, donde las mesetas y cuencas del paisaje de búsqueda se exploran con mayor detalle. El coeficiente se utiliza para equilibrar la parte de penalización de la función objetivo en relación con los cambios en dicha función y es específico del problema. Una heurística sencilla para su configuración consiste simplemente en registrar el cambio promedio en la función objetivo hasta el primer mínimo local y, a continuación, establecer este valor dividido por el número de características GLS en la instancia del problema. ${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$

Mills (2002) describió una búsqueda local guiada extendida (EGLS) que utiliza movimientos aleatorios y un criterio de aspiración diseñado específicamente para esquemas basados ​​en penalizaciones. El algoritmo resultante mejoró la robustez de GLS en un rango de configuraciones de parámetros, particularmente en el caso del problema de asignación cuadrática . Una versión general del algoritmo GLS, que utiliza un algoritmo de ascenso de colinas basado en conflictos mínimos (Minton et al. 1992) y se basa parcialmente en GENET para la satisfacción de restricciones y la optimización, también se ha implementado en el proyecto de Programación de Restricciones Asistida por Computadora.

Alsheddy (2011) extendió la búsqueda local guiada a la optimización multiobjetivo y demostró su uso en el empoderamiento del personal en la planificación.

GLS se construyó sobre GENET, que fue desarrollado por Chang Wang, Edward Tsang y Andrew Davenport.

El método de ruptura es muy similar a GENET. Fue diseñado para la satisfacción de restricciones .

La búsqueda tabú es una clase de métodos de búsqueda que pueden instanciarse en métodos específicos. GLS puede considerarse un caso especial de búsqueda tabú .

Al combinar GLS con un algoritmo genético , Tung-leng Lau introdujo el algoritmo de programación genética guiada (GGA). Este algoritmo se aplicó con éxito al problema de asignación general (en planificación), al problema de configuración de procesadores (en diseño electrónico) y a un conjunto de problemas de asignación de frecuencias de enlaces de radio (una aplicación militar abstracta).

Choi et al. plantearon GENET como una búsqueda lagrangiana.

• Alsheddy, A., Programación de empoderamiento: un enfoque de optimización multiobjetivo mediante búsqueda local guiada, Tesis doctoral, Escuela de Informática e Ingeniería Electrónica, Universidad de Essex, 2011
• Choi, KMF, Lee, JHM y Stuckey, PJ, Una reconstrucción lagrangiana de GENET, Inteligencia Artificial, 2000, 123(1-2), 1-39
• Davenport A., Tsang EPK, Kangmin Zhu y CJ Wang, GENET: Una arquitectura conexionista para resolver problemas de satisfacción de restricciones mediante mejora iterativa, Actas de la AAAI, 1994, págs. 325-330.
• Lau, TL y Tsang, EPK, Resolución del problema de configuración del procesador con un algoritmo genético basado en mutaciones, International Journal on Artificial Intelligence Tools (IJAIT), World Scientific, Vol. 6, No. 4, diciembre de 1997, 567-585
• Lau, TL y Tsang, EPK, Algoritmo genético guiado y su aplicación a problemas de asignación de frecuencias de enlaces de radio, Constraints, Vol. 6, No. 4, 2001, 373-398
• Lau, TL y Tsang, EPK, El algoritmo genético guiado y su aplicación a los problemas de asignación general, 10.ª Conferencia Internacional IEEE sobre Herramientas con Inteligencia Artificial (ICTAI'98), Taiwán, noviembre de 1998.
• Mills, P. y Tsang, EPK, Búsqueda local guiada para la resolución de problemas SAT y MAX-SAT ponderados, Journal of Automated Reasoning, Número especial sobre problemas de satisfacibilidad, Kluwer, Vol. 24, 2000, 205-223
• Mills, P. & Tsang, EPK & Ford, J., Aplicación de una búsqueda local guiada extendida al problema de asignación cuadrática, Annals of Operations Research, Kluwer Academic Publishers, Vol. 118, 2003, 121-135
• Minton, S., Johnston, M., Philips, AB y Laird, P., Minimización de conflictos: un método heurístico de reparación para la satisfacción de restricciones y problemas de programación, Inteligencia Artificial (Volumen especial sobre razonamiento basado en restricciones), Vol. 58, Nos. 1-3, 1992, 161-205
• Tsang, EPK y Voudouris, C., Búsqueda local rápida y búsqueda local guiada y su aplicación al problema de programación de la fuerza laboral de British Telecom, Operations Research Letters, Elsevier Science Publishers, Ámsterdam, vol. 20, n.º 3, marzo de 1997, 119-127.
• Voudouris, C., Tsang, EPK, Problemas de satisfacción de restricciones parciales y búsqueda local guiada, Actas de la Segunda Conferencia Internacional sobre la Aplicación Práctica de la Tecnología de Restricciones (PACT'96), págs. 337-356, Londres, Reino Unido, 1996
• Voudouris, C., Búsqueda local guiada para problemas de optimización combinatoria, Tesis doctoral, Departamento de Informática, Universidad de Essex, Colchester, Reino Unido, julio de 1997.
• Voudouris, C., Búsqueda local guiada: un ejemplo ilustrativo en la optimización de funciones, BT Technology Journal, vol. 16, n.º 3, julio de 1998, 46-50
• Voudouris, C., Tsang, E., Resolución de problemas de asignación de frecuencias de enlaces de radio mediante búsqueda local guiada, en Actas del simposio de la OTAN sobre asignación, compartición y conservación de frecuencias en sistemas (AEROSPACE), AGARD, documento n.º 14, Aalborg, Dinamarca, 5-7 de octubre de 1998.
• Voudouris, C. y Tsang, EPK, Búsqueda local guiada y su aplicación al problema del viajante, European Journal of Operational Research, Anbar Publishing, Vol. 113, número 2, marzo de 1999, 469-499
• Voudouris, C. y Tsang, EPK, La búsqueda local guiada se une a la élite en optimización discreta, Serie DIMACS en Matemáticas Discretas y Ciencias de la Computación Teórica, Volumen 57, 2001, 29-39
• Voudouris, C. y Tsang, EPK, Búsqueda local guiada, en F. Glover (ed.), Manual de metaheurísticas, Kluwer, 2003, 185-218
• Voudouris, C., Tsang, EPK y Alsheddy, A., Búsqueda local guiada, Capítulo 11, en M. Gendreau y JY Potvin (eds.), Manual de metaheurísticas, Springer, 2010, 321-361
• Voudouris, C., Tsang, E., Alsheddy, A., Búsqueda local guiada, Enciclopedia Wiley de investigación operativa y ciencias de la gestión, Wiley, 2010
• Voudouris, C., Tsang, E., Alsheddy, A., Aplicación efectiva de la búsqueda local guiada, Enciclopedia Wiley de investigación operativa y ciencias de la gestión, Wiley, 2010

• Página principal de búsqueda local guiada
• Recursos de búsqueda local guiada
• Google OR-Tools - Búsqueda local guiada