Buscar con prohibiciones

La búsqueda tabú o búsqueda tabú es un algoritmo de metabúsqueda que utiliza métodos de búsqueda locales utilizados para la optimización matemática . El algoritmo fue creado por Fred W. Glover en 1986 [1] y formalizado en 1989 [2] [3]

La búsqueda local (por vecinos) toma una posible solución a un problema y comprueba sus vecinos inmediatos (es decir, soluciones que son similares excepto por algunos detalles muy pequeños) con la esperanza de encontrar una solución mejorada. Los métodos de búsqueda local tienden a quedar atrapados en regiones subóptimas o mesetas donde muchas soluciones son igualmente adecuadas.

La búsqueda denegada mejora el rendimiento de la búsqueda local al relajar su regla básica. Para empezar, se puede suponer un deterioro en cada paso si no hay mejora (similar al caso en el que la búsqueda se atasca en un mínimo local ). Además, se introducen prohibiciones (también conocidas como tabúes ) para evitar la búsqueda de soluciones que ya se han visitado.

La implementación de la búsqueda de denegación utiliza estructuras que describen decisiones visitadas o conjuntos de reglas de usuario [2] . Si una posible solución ha sido visitada durante un breve período de tiempo o viola una regla, se marca como " tabú " para que el algoritmo no reconsidere la solución.

La palabra tabú proviene de una palabra tongana que significa cosas que no se deben tocar porque son sagradas [4] .

La búsqueda tabú es un metaalgoritmo que se puede utilizar para resolver problemas de optimización combinatoria (problemas en los que es necesario encontrar el orden y la elección de opciones óptimos).

Las aplicaciones actuales de búsqueda prohibida se extienden a áreas como la planificación de recursos , las telecomunicaciones, la ingeniería VLSI , el análisis financiero, la programación, la planificación espacial, la distribución de energía, la ingeniería molecular, la logística, la clasificación de patrones , la fabricación flexible, la gestión de residuos, la prospección de minerales, el análisis biomédico y la protección del medio ambiente. y muchos otros. En los últimos años, las revistas en muchos campos de la ciencia han publicado artículos académicos y estudios computacionales que muestran el éxito de la búsqueda tabú en la expansión de los límites de los problemas que se pueden resolver de manera eficiente, produciendo soluciones que a menudo son de calidad muy superior a las obtenidas por métodos hasta ahora. . Una extensa lista de aplicaciones, incluyendo un resumen del resultado obtenido de la aplicación práctica, se puede encontrar en el artículo de Glover y Laguna [5] . Los desarrollos y aplicaciones modernos de búsqueda tabú se pueden encontrar en el artículo Viñetas de búsqueda tabú .

Fundamentos

La búsqueda tabú utiliza un procedimiento de búsqueda local o de búsqueda de vecinos para pasar iterativamente de una solución potencial a una solución mejor en el vecindario hasta que se cumpla algún criterio de parada (normalmente el número de iteraciones o un umbral de puntuación objetivo). Las rutinas de búsqueda local a menudo se atascan en áreas con estimaciones de objetivos deficientes o en áreas donde la estimación forma una meseta (superficie horizontal suave). Para evitar estas trampas y explorar regiones del espacio de búsqueda que otros procedimientos de búsqueda dejarían sin explorar, la búsqueda tabú examina cuidadosamente la vecindad de cada solución en el proceso de búsqueda. Las soluciones reconocidas por los nuevos vecinos, , se determinan utilizando estructuras en memoria. Usando estas estructuras, la búsqueda progresa moviéndose iterativamente desde la solución actual a la solución mejorada de la lista .

Estas estructuras forman las denominadas listas tabú, un conjunto de reglas y soluciones etiquetadas que se utilizan para filtrar qué soluciones vecinas procesar al buscar. En su forma más simple, una lista tabú es un conjunto de decisiones a corto plazo que se han visitado en las últimas iteraciones (menos de iteraciones, donde es igual al número de decisiones recordadas y este número se denomina tiempo de vida tabú). Más a menudo, la lista tabú consta de decisiones que se han cambiado en el proceso de pasar de una decisión a otra. Es conveniente por facilidad de presentación comprender la "solución" codificada y representada por algunos atributos.

Tipos de memoria

Las estructuras de memoria utilizadas en la búsqueda tabú se pueden dividir aproximadamente en tres categorías [6] :

Las listas de corto, mediano y largo plazo pueden superponerse. Dentro de estas categorías, la memoria se puede diferenciar aún más por criterios como la frecuencia y el impacto de los cambios realizados. Un ejemplo de estructura de mediano plazo es la prohibición o fomento de decisiones que contienen algunos atributos (por ejemplo, decisiones que incluyen valores indeseables o deseables de algunas variables determinadas) o una estructura de memoria que impide o genera algunos movimientos (por ejemplo , basado en la frecuencia de ocurrencia de características en soluciones prospectivas y poco prometedoras encontradas anteriormente). En la memoria a corto plazo, los atributos seleccionados en las soluciones visitadas recientemente se marcan como "tabú activo". Está prohibido el uso de soluciones con elementos activos tabú. Para cambiar el estado tabú de una solución, se utiliza un criterio de eliminación, incluyendo las soluciones excluidas en la lista permitida (la solución es “suficientemente buena” según la medida de calidad o diferencia). Un criterio de eliminación simple y comúnmente utilizado es permitir el uso de soluciones que son mejores que la mejor solución actualmente conocida.

La memoria a corto plazo por sí sola puede ser suficiente para producir una solución superior a la encontrada por los métodos de búsqueda locales convencionales, pero a menudo se necesitan estructuras a medio y largo plazo para resolver problemas más complejos [7] . La búsqueda tabú a menudo se compara con otros métodos metaalgorítmicos, como el algoritmo de recocido simulado , los algoritmos genéticos , los algoritmos de colonias de hormigas , la búsqueda reactiva, la búsqueda local supervisada o la búsqueda aleatoria adaptativa codiciosa . Además, la búsqueda tabú a veces se combina con otros metaalgoritmos para crear métodos híbridos. El híbrido de búsqueda tabby más común surge al combinarlo con la búsqueda dispersa [  8 ] [ 9] , una clase de procedimientos que tienen raíces comunes con la búsqueda tabú y que a menudo se usan para resolver problemas de optimización no lineal a gran escala.

Pseudocódigo

El siguiente pseudocódigo representa una versión simplificada del algoritmo de búsqueda tabú descrito anteriormente. Esta implementación tiene la versión más simple de la memoria a corto plazo y no contiene estructuras a mediano o largo plazo. El término "aptitud" se refiere al cálculo de una función objetivo para una solución candidata.

sMejor ← s0 mejorcandidato ← s0 tabulista ← [] tabuLista . empujar ( s0 ) while ( sin condición de parada ()) sNeighborhood ← getNeighbors ( mejorCandidato ) para ( sCandidate en sNeighborhood ) if ( ( no tabuList . contiene ( sCandidate )) y ( fitness ( sCandidate ) > fitness ( bestCandidate )) ) mejorCandidato ← sCandidato final final if ( aptitud ( mejorCandidato ) > aptitud ( sBest )) sBest ← mejorcandidato final tabuLista . empujar ( mejor candidato ) if ( listatabu . tamaño > maxTabuSize ) tabuLista . removeFirst () final final volver sBest

Las líneas 1 a 4 hacen asignaciones iniciales, creando una solución inicial (quizás obtenida mediante métodos de búsqueda aleatorios), estableciendo la solución resultante como la primera vista e inicializando la lista tabú con esta solución. En este ejemplo, la lista tabú es solo una estructura de corta duración que contiene un registro de los elementos visitados.

El bucle principal comienza en la línea 5. Este bucle continúa buscando la mejor solución hasta que alcanza un criterio de parada especificado por el usuario (dos ejemplos de dicho criterio son simplemente un límite de tiempo o un umbral de puntuación de aptitud). Las soluciones vecinas se verifican en busca de tabúes en la línea 8. Además, el algoritmo almacena las mejores soluciones no prohibidas de los vecinos.

La función de objetivo de aptitud suele ser una función matemática que devuelve una puntuación o criterio objetivo; por ejemplo, encontrar un nuevo espacio de búsqueda [4] puede considerarse el criterio objetivo . Si el mejor candidato local tiene un valor de aptitud más alto, entonces el valor actual es el mejor (línea 12), ahora se acepta como el mejor (línea 13). El mejor candidato local siempre se agrega a la lista tabú (línea 15) y si la lista tabú está llena (línea 16), se considera que el tabú de algún elemento ha expirado (línea 17). Por lo general, los elementos se eliminan de la lista en el orden en que se agregaron. El procedimiento elige al mejor candidato local (aunque tiene un valor de aptitud peor que sBest) para saltar fuera del óptimo local.

Este proceso continúa hasta que se obtiene un criterio de parada definido por el usuario, en cuyo punto se devuelve la mejor solución encontrada en el proceso (línea 20).

Ejemplo: el problema del viajante de comercio

El problema del vendedor ambulante se utiliza a veces para mostrar el funcionamiento de una búsqueda tabú [7] . Este problema pregunta, dada una lista de ciudades, ¿cuál es la ruta más corta para visitar todas las ciudades? Por ejemplo, si la ciudad A y la ciudad B están cerca, pero la ciudad C está lejos, la longitud total de la ruta será más corta si primero visitamos A y B, y luego vamos a la ciudad C. Dado que encontrar la solución óptima es NP-hard , los métodos de aproximación basados ​​en heurística (como la búsqueda local) son útiles para obtener una solución casi óptima. Para obtener buenas soluciones al problema del viajante de comercio, es importante examinar la estructura del gráfico. El valor de la exploración de la estructura del problema es un tema recurrente en los métodos metaalgorítmicos, y la búsqueda tabú se adapta bien a esto. La clase de estrategias asociadas a la búsqueda tabú y denominadas métodos de cadena de eyección  permite obtener soluciones de alta calidad al problema del viajante de manera eficiente [10] .

Por otra parte, se puede utilizar la búsqueda tabú simple para encontrar una solución satisfactoria al problema del viajante de comercio (es decir, una solución que satisfaga el criterio de aptitud, aunque de baja calidad, que se obtiene tras examinar la estructura del grafo) La búsqueda comienza con una solución inicial, que puede obtenerse aleatoriamente o de acuerdo con algún tipo de algoritmo de vecino más cercano . Para crear nuevas soluciones, el orden en que se visitan las ciudades se intercambia en la solución potencial. La distancia total de la ruta entre todas las ciudades se usa para comparar qué tan mejor es una solución que otra. Para evitar bucles, es decir, volver a obtener un determinado conjunto de soluciones y quedarse atascado en el óptimo local , se agrega una solución a la lista de soluciones prohibidas si se acepta al buscar entre vecinos .

Se crean nuevas soluciones hasta que alcanzamos algún criterio de parada, como el número de iteraciones. Tan pronto como se detiene la búsqueda tabú simple, devuelve la mejor solución que encontró durante la ejecución.

Notas

  1. ↑ Glover, 1986 , pág. 533–549.
  2. ↑ 1 2 Glover, 1989 , pág. 190–206.
  3. ↑ Glover, 1990 , pág. 4–32.
  4. ↑ 1 2 Cursos | Grupo Fuzzy-Neural | ISE del estado de Carolina del Norte . Consultado el 16 de enero de 2019. Archivado desde el original el 12 de enero de 2014.
  5. ↑ Glover, Laguna, 1997 .
  6. ↑ Tutorial de Glover/A, 1990 .
  7. ↑ 1 2 Malek, Huruswamy, Owens, Pandya, 1989 .
  8. ↑ Glover, Laguna, Martí, 2000 , p. 653–684.
  9. ↑ Laguna, Martí, 2003 .
  10. ↑ Gamboa, Rego, Glover, 2005 , p. 154–171.

Literatura

  • Fred Glover. Caminos futuros para la programación entera y enlaces a la inteligencia artificial // Computadoras e investigación de operaciones. - 1986. - T. 13 , núm. 5 . - doi : 10.1016/0305-0548(86)90048-1 .
  • Fred Glover. Búsqueda tabú - Parte 1 // ORSA Journal on Computing. - 1989. - Vol. 1 , número. 2 . -doi : 10.1287/ ijoc.1.3.190 .
  • Fred Glover. Búsqueda tabú - Parte 2 // ORSA Journal on Computing. - 1990. - Vol. 2 , número. 1 . -doi : 10.1287/ ijoc.2.1.4 .
  • Gamboa D., Rego C., Glover F. Estructuras de datos y cadenas de eyección para resolver problemas de vendedores ambulantes a gran escala // European Journal of Operational Research. - 2005. - T. 160 , núm. 1 . -doi : 10.1016/ j.ejor.2004.04.023 .
  • Glover F., Laguna M. Tabú Búsqueda. — Editores académicos de Kluwer. — 1997.
  • Fred Glover. Búsqueda tabú: un tutorial // Interfaces. — 1990.
  • Malek M., Huruswamy M., Owens H., Pandya M. Técnicas de búsqueda en serie y en paralelo para el problema del viajante de comercio. Annals of OR: vínculos con la inteligencia artificial. — 1989.
  • Glover F., Laguna M., Marti R. Fundamentos de la búsqueda de dispersión y la vinculación de rutas. — Control y Cibernética. - 2000. - T. 29. - S. 653-684.
  • Laguna M., Marti R. Búsqueda de dispersión: metodología e implementaciones en C. - Kluwer Academic Publishers, Boston. — 2003.

Enlaces