Búsqueda tabú

Búsqueda tabú (algoritmo metaheurístico) una forma de optimizar los objetivos de tu vida sin recurrir a la famosa frase milenaria “Te lo dije”.

Digamos que estamos en una montaña la cual cuenta con neblina y el objetivo es llegar a la cumbre, para esto contamos con un altímetro, una forma de hacerlo sería subir, siempre caminando al punto mas alto, pero podría pasar que llegáramos a un punto donde no podamos avanzar y está sería nuestra máxima altitud, es decir, muy probablemente tendríamos que bajar y buscar otra ruta. Creo que en este punto ya nos dimos cuenta de que seriamos muy afortunados si llegamos a la cima con esta metodología;

La búsqueda tabú básicamente es una forma de excluir datos erróneos. En realidad, el objetivo principal de la exclusión de opciones en una búsqueda, es  evitar  que la búsqueda sea cíclica. La búsqueda tabú se puede aplicar a problemas como el “Problema del Viajero” , donde el objetivo es, producir un camino optimo.

He aquí un resumen de la búsqueda tabú heurística básica. En primer lugar la notación:

f es una función de maximizar en un espacio de búsqueda X.  M es una lista de todos los movimientos posibles (por ejemplo, Norte, Sur, Este, Oeste), cada movimiento tiene un movimiento inverso, la variable q da nuestra posición actual en el espacio de busqueda de X y P el punto donde  valor en f es el máximo en ese instante .
El algoritmo:

  1. Comience en un punto p al azar del espacio de búsqueda, o en un punto que podría estar cerca de una buena solución. Sea q = p y P = p.
  2. N denota el conjunto de puntos de X que se puede llegar desde q por un solo movimiento en M que no está en la lista tabú L.
  3. Calcular el valor de cada elemento de M en f.
  4. Cambiar q para ser el punto de mayor valor en el paso anterior.
  5. Añadir el movimiento inverso que acaba de tomar el máximo  de la lista tabú L. Si la lista tabú es mayor que la longitud,  entonces eliminar la última entrada de L.
  6. Si f (q)> f (P), el cambio de P a Q: hemos encontrado una nueva solución.
  7. Vuelva al paso 2.

El algoritmo de búsqueda tabú nos podría llevar a la cima de una forma optima.

Quien este pensando en buscar caminos halmitonianos puede ayudarse de este algoritmo, y que mejor el problema del viajero aunque es NP-Completo se puede aplicar

Anuncios

Un comentario en “Búsqueda tabú

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s