Investigación tabú: sistemas complejos e inteligencia artificial

Contenido

Investigación tabú

La investigación tabú fue propuesta por Fred Glover en 1986 (cuyos esquemas encontrará en el desarrollo del algoritmo). El método utiliza una memoria (o varias memorias) que se actualiza y explota durante la búsqueda.

La idea básica de la lista tabú es memorizar las configuraciones o regiones visitadas e introducir mecanismos para evitar que la investigación regrese demasiado rápido a estas configuraciones. Estos mecanismos son prohibiciones temporales de determinados movimientos (movimientos tabú).
PARA En cada iteración, el algoritmo tabú elige al mejor vecino no tabú, incluso si esto degrada la función de costo. Por esta razón, se dice que la investigación tabú es un método agresivo.

Lista de tabú

La lista tabú contiene atributos o movimientos prohibidos. Estos últimos son tabú durante un determinado número de iteraciones del algoritmo (infinitas o finitas). Una vez que finaliza el período tabú, el atributo o movimiento vuelve a estar disponible en el busqueda local. Esta lista es una estrategia de diversificación.

Para algunos tipos de problemas, rechazar un atributo puede eliminar configuraciones útiles para escapar de un óptimo local. Un mecanismo, llamado criterio de aspiración, permite relajar la prohibición bajo ciertas condiciones. Es importante notar que un mal criterio de aspiración es hacer ciclar el algoritmo en un ciclo de soluciones.

Ya sea la elección de la prohibición o el criterio de aspiración, estos dos mecanismos deben adaptarse caso por caso en relación con los problemas encontrados.

Flujo de algoritmo

 s ← s0
sBest ← s
tabuList ← []
tiempo (no condición de parada())
   Lista de candidatos ← []
   bestCandidate ← nulo
   por (sCandidato en sVecindario)
      tejo ( (no tabuList.contiene(sCandidato)) 
      y (aptitud física(sCandidato) > aptitud física(bestCandidate)) )
         bestCandidate ← sCandidato
      terminara si
   final para
   s ← bestCandidate
   tejo (aptitud física(bestCandidate) > aptitud física(sBest))
      sBest ← bestCandidate
   terminara si
   tabuList.empujar(bestCandidate);
   tejo (tabuList.Talla > maxTabuSize)
      tabuList.removeFirst()
   terminara si
mind mientras
regreso sBes

Ejemplo de aplicación

Tomaremos el ejemplo del viajante de comercio (TSP). Dado un conjunto de ciudades, conocemos la distancia entre todos los pares de ciudades. El objetivo es visitar cada ciudad, una tras otra hasta volver a la primera, minimizando la distancia total recorrida.

El recorrido está representado por un conjunto de arcos, siendo los vértices los pueblos. Una configuración inicial consiste en elegir un ciclo hamiltoniano (un ciclo que pasa una y solo una vez por cada vértice) arbitrarias, como tomar la siguiente ciudad de la lista.

El barrio se construye con movimiento. Un movimiento consiste en quitar dos arcos para "cruzarlos". Por ejemplo, el par de arcos <(a, c), (e, b)> se convierte en <(a, e), (c, b)>. Así se conserva el ciclo hamiltoniano. Luego hemos "eliminado" arcos y "agregado" arcos.

Para no repetir el mismo movimiento, presentamos dos listas tabú: EN que contiene arcos eliminados (a, c) y (e, b); FUERA que contiene los arcos añadidos (a, e) y (c, b). PARA cada iteración los movimientos prohibidos son: introducir un arco de EN y quita un arco de FUERA. Aquí la prohibición es infinita.