Búsqueda local gestionada

La búsqueda local guiada ( GLS) es un método de búsqueda metaheurística  , es decir, un método sobre el algoritmo de búsqueda local para cambiar su comportamiento.

La búsqueda local guiada genera penalizaciones durante la búsqueda y las usa para ayudar a los algoritmos de búsqueda local a alejarse de los mínimos locales y las regiones (casi) horizontales. Cuando el algoritmo de búsqueda local alcanza un mínimo local, el GLS modifica la función objetivo con un esquema especial (explicado a continuación). La búsqueda local trabaja entonces sobre esta función objetivo aumentada, que se construye para sacarla del óptimo local. La pregunta clave es cómo modificar la función objetivo.

La búsqueda local guiada fue propuesta por  Voudouris y Tsang [1] .

Resumen

Propiedades de la solución

Para aplicar GLS, las propiedades de la solución deben definirse para un problema dado. Las propiedades de la solución se definen para distinguir entre soluciones con diferentes características, de modo que las áreas de similitud alrededor del óptimo puedan reconocerse y excluirse. La elección de las propiedades de la solución depende del tipo de problema y también de los algoritmos de búsqueda. Para cada propiedad , se define una función de precio .

Cada propiedad está asociada con una penalización (inicialmente 0) que representa el número de veces que la propiedad alcanza el mínimo local.

Las propiedades y los precios a menudo vienen junto con la función objetivo. Por ejemplo, en el problema del viajante de comercio , "la ruta desde la ciudad X va directamente a la ciudad Y" puede considerarse como una propiedad. La distancia entre X e Y se puede definir como el precio. En los problemas SAT y MAX-SAT ponderados las propiedades pueden ser "la declaración C satisface las asignaciones de variables actuales".

A nivel de implementación, definimos para cada propiedad una función característica que indica si la propiedad está presente en la solución actual o no. es 1 si la solución contiene la propiedad , 0 en caso contrario.

Cambios de penalización selectiva

GLS calcula las multas por servicios públicos para cada propiedad. Cuando el algoritmo de búsqueda local devuelve el mínimo local x, el GLS penaliza todas aquellas propiedades (aumentando la penalización de la propiedad) presentes en la solución que tienen la máxima utilidad , como se define a continuación.

La idea es penalizar las propiedades que tienen precios altos, aunque la utilidad de hacerlo disminuye cuando la propiedad es penalizada con frecuencia.

Encontrar una función de costo aumentada

El GLS utiliza el aumento de la función de costo (definido a continuación) para permitir que el control del algoritmo de búsqueda local salga del mínimo local al penalizar las propiedades representadas en el mínimo local. La idea es hacer que el mínimo local sea más caro que el espacio de búsqueda circundante donde estas propiedades no están presentes.

El parámetro se puede utilizar para cambiar la intensidad de la búsqueda de soluciones. Los valores más altos darán como resultado una búsqueda más amplia, y las áreas horizontales y los valles se verán de manera más aproximada. Un valor bajo dará como resultado una búsqueda más detallada en áreas horizontales y valles. El coeficiente se utiliza para equilibrar la parte de penalización de la función objetivo con respecto a los cambios en la función objetivo, y depende de la tarea. Una heurística simple para la asignación es simplemente registrar el cambio promedio en la función objetivo hasta el primer mínimo local y luego establecer ese valor dividido por el número de propiedades GLS en el problema.

Extensiones de búsqueda locales administradas

Mills (2002) describió una búsqueda local guiada extendida (EGLS) que utiliza movimientos aleatorios y un criterio de uso diseñado específicamente para esquemas basados ​​en sanciones. El algoritmo resultante mejora la estabilidad del GLS con respecto a la dispersión de parámetros, especialmente en el caso de un problema de asignación cuadrática . En el proyecto de Programación de Restricciones Asistida por Computadora se implementó una versión principal del algoritmo GLS, que utiliza un ascenso de conflicto mínimo [2] y se basa en parte en GENET para la satisfacción y optimización de restricciones .

Alsheddy (2011) amplió la búsqueda local guiada para la optimización multiobjetivo y demostró su uso en la planificación.

Obras relacionadas

GLS se basó en el sistema GENET desarrollado por Chang Wang, Edward Tsang y Andrew Davenport.

El método de ruptura es muy similar a GENET. Fue diseñado para cumplir con las restricciones de [3] [4] .

La búsqueda denegada es una clase de métodos de búsqueda que se pueden implementar para métodos específicos. GLS se puede considerar como un caso especial de búsqueda tabú .

Usando GLS sobre un algoritmo genético, Tung-leng Lau introdujo la Programación Genética Guiada (GGA) .  Se ha aplicado con éxito a la asignación general (para horarios), la configuración del procesador y la asignación de RF (militar).

Choi, Lee y Stucky [5] presentaron GENET como una búsqueda lagrangiana.

Notas

  1. ↑ Skobtsov y Fedorov ( Skobtsov, Fedorov 2013 , 28) hacen referencia al artículo ( Voudouris 29-39), aunque el propio Tsang escribe:,, Tsang 2001 Comenzando con GENET, desarrollamos muchos algoritmos intermedios, como el algoritmo de tunelización, y terminamos con el algoritmo de búsqueda local administrado que se presenta en este artículo”. Estamos hablando de un artículo de 1995 ( Voudouris, Tsang 1995 )
  2. ↑ Minton, Johnston, Philips, Laird, 1992 , pág. 161-205.
  3. ↑ Yokoo, Hirayama, 1996 , pág. 401-408.
  4. ↑ Zhang, Wittenburg, 2002 .
  5. ↑ Choi, Lee, Stuckey, 2000 , pág. 1-39.

Literatura

Enlaces