Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Introducción a la búsqueda tabú

No description
by

Marcela Guzmán García

on 25 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Introducción a la búsqueda tabú

Búsqueda tabú
Marcela Guzmán

Cristhian E. Castaño
Joaquín A. García
Ejemplo
Conceptos básicos
Aplicaciones
Búsqueda tabú
Atributos principales
Metaheurística
: "Más allá", la metaheurística está diseñada principalmente para escapar del atrapamiento en el óptimo local, al permitir movimientos inferiores, si es necesario.


1.Solución inicial.
La búsqueda debe
comenzar desde una solución inicial que
podría ser cualquier solución admisible que
satisfaga las restricciones del problema.






4.Lista tabú.
Es un mecanismo de
memoria adaptativa que trata de evitar
que la búsqueda entre en un ciclo o quede
atrapada en un óptimo local.


5.Criterio de parada
. En general, la búsqueda
termina después de un número determinado de
iteraciones, después de un tiempo de computación
predefinido.


6. Criterio de aspiración:
Es cuando ocurre una
excepción a la lista tabu, ya que un movimiento
imposibilitado conduce a una condición
mejorada.

Diseño, lógica e inteligencia artificial, tecnología, optimización de gráficas, telecomunicaciones; planificación, localización, producción, inventario e inversión , entre otras.
*Glover, F., Laguna, M. and Mart´ı R. (2006) Principles of Tabu Search. To appear in Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
*Valeiras Reina, Gerardo; Martín García Elena, (2004) Sistemas evolutivos y selección de indicadores. 135 páginas
*TAHA HAMDY A. Investigación de operaciones. Alfaomega. 5 Ed. 1995
*HILLIER, F.S Y LIEBERMAN G.J. Introducción a la investigación de Operaciones. 9 Ed. 2010. Mc Graw Hill

Heurística
: Heuriskein, está diseñada para encontrar buenas soluciones aproximadas de problemas difíciles que de lo contrario no pueden resolverse mediante los algoritmos de optimización disponibles.

La búsqueda tabú o TS (Tabu Search)
se puede considerar como un procedimiento de búsqueda local dotado de una memoria que le permite escapar de óptimos locales.


La información guardada en esta memoria se usa para comenzar con la búsqueda desde otra solución inicial de acuerdo a dos filosofías distintas:

Intensificar la búsqueda
, volviendo a visitar zonas del espacio prometedoras (que contenían buenas soluciones), ya exploradas parcialmente.

Diversificar la búsqueda
, visitando nuevas zonas no exploradas aún.

En búsqueda de obtener una solución óptima para complejos problemas de programación lineal aparece la heurística

Metaheuristicas
evolutiva
• Evolución estocástica (AG, Meméticos, EDAs)
• Evolución determinística (Scatter Search, Path-Relin king)


Metaheuristicas
de relajación:
(Lagrangiana, Restricciones surrogadas)


Metaheuristicas


de búsqueda
Búsqueda: Local y Global
MultiStart (MS)
Entorno Variable (VNS)
Memoria (Tabú Search)
Estocásticas
(Recocido simulado)

Metaheuristicas
constructivas
(Greedy, Aleatoria, GRASP)


-Búsqueda sensible:
La operación de movimiento se
produce después de sacar conclusiones de lo acontecido anteriormente.
-Memoria adaptativa:
La memoria se actualiza en función del tiempo y el análisis de la vecindad, “recuerda” los
movimientos de la búsqueda anterior y los deshabilita durante un periodo de tenencia especificada.
2.Movimiento.
Es un procedimiento aleatorio o determinístico por el que se genera una solución admisible a partir de la solución inicial
3.Vecindad.
Dada una solución S, la vecindad N(S)
es el conjunto de todas la soluciones admisibles
que pueden ser generadas por la ejecución de
un movimiento sobre la solución actual S.

Algoritmo
de búsqueda tabú
Paso 0.
Seleccione una solución de inicio so € S. Inicie la lista tabú Lo = , y seleccione un esquema para especificar el tamaño de la lista tabú. Establezca k= 0
Paso 1.
Determine la vecindad factible N(s_k) que excluya miembros (inferiores) de la lista tabú l_k

Paso 2.
Seleccione el siguiente movimiento s_(k+1) a partir de
N(s_k) (o de l_k, si proporciona una mejor solución ),
y actualice la lista tabú l_(k+1)
Paso 3
. Si se llega a una condición de terminación, deténgase. Si no, establezca k= k+1 y vaya al paso 1
Introducción
Árbol de expansión mínima
con restricciones
Objetivo: Conectar todos los nodos al mínimo costo.
Restricción 1: El nodo AD puede incluirse sólo si el nodo DE también se incluye. (penalización: 100)
Restricción 2: Al menos uno de los tres enlaces - AD, CD y AB - pueden ser incluidos. (Multa de 100 si dos de los
tres seleccionados, 200 si se seleccionan los tres.)
Solución óptima
Costo = 70
Iteraciones adicionales sólo
encuentran costos mayores.

Referencias
Full transcript