Búsqueda tabú

Investigación tabú

La investigación tabú fue propuesta por Fred Glover en 1986 (cuyos diagramas encontrará en el flujo 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 liste taboue contient des attributs ou des mouvements interdits. Ces derniers sont tabous durant un nombre d’itérations de l’algorithme déterminée (infini ou fini). Une fois la période taboue terminée, l’attribut ou le mouvement est de nouveau disponible dans la busqueda local. Cette liste est une stratégie de diversification.

Para ciertos tipos de problemas, la prohibición de un atributo puede eliminar configuraciones útiles para escapar de un óptimo local. Un mecanismo, llamado criterio de aspiración, permite relajar la prohibición en determinadas condiciones. Es importante señalar que un mal criterio de aspiración es hacer un bucle del 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.

Secuencia del algoritmo

investigación tabú

investigación tabú

 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 aplicacion

Tomaremos el ejemplo del viajero comercial (TSP). Considere 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 ciudad, minimizando la distancia total recorrida.

Le parcours est représenté par un ensemble d’arcs, les sommets étant les villes. Une configuration initiale consiste à choisir un cycle hamiltoniano (un cycle qui passe une et une seule fois par chaque sommet) arbitraire, comme par exemple prendre la prochaine ville dans la liste.

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 interminable.

Investigación tabú de TSP

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: