UnidadIII Introduccion a la BusquedaTabu

Introducci´on a la B´usqueda Tab´u

*

Bel´en Meli´an Batista, Fred Glover††
Dpto. de Estad´ıstica, I.O. y Computaci´on
Escuela T´ecnica Superior de Ingenier´ıa Inform´atica
Universidad de La Laguna
mbmelian@ull.es
††

University of Colorado at Boulder
Fred.Glover@Colorado.edu

Resumen
La B´
usqueda Tab´
u (Tabu Search - TS) es un procedimiento metaheur´ıstico cuya caracter´ıstica distintiva esel uso de memoria adaptativa y de estrategias especiales de resoluci´on
de problemas. Su filosof´ıa se basa en la explotaci´on de diversas estrategias inteligentes para
la resoluci´on de problemas, basadas en procedimientos de aprendizaje. El marco de memoria
adaptativa de TS explota la historia del proceso de resoluci´on del problema haciendo referencia
a cuatro dimensiones principales,consistentes en la propiedad de ser reciente, en frecuencia, en
calidad, y en influencia. Para obtener un listado de los elementos a tener en consideraci´on durante el dise˜
no de un procedimiento de b´
usqueda tab´
u, v´ease el ap´endice que aparece al final de
este cap´ıtulo. Para estudiar en profundidad los puntos del mismo refi´erase al cap´ıtulo completo,
as´ı como a las referencias indicadas.

1.Introducci´
on

El t´ermino B´
usqueda Tab´
u (Tabu Search - TS) fue introducido en 1986 por Fred Glover en
el mismo art´ıculo que introdujo el t´ermino metaheur´ıstica [5]. Los principios fundamentales de la
b´
usqueda fueron elaborados en una serie de art´ıculos de finales de los a˜
nos 80 y principios de los
90, que fueron luego unificados en el libro “Tabu Search”en 1997 [8]. El destacado ´exitode la
b´
usqueda tab´
u para resolver problemas de optimizaci´on duros, especialmente aquellos que surgen
en aplicaciones del mundo real, ha causado una explosi´on de nuevas aplicaciones durante los u
´ltimos
a˜
nos, que aparecen resumidas en [9].
La b´
usqueda tab´
u es una metaheru´ıstica que gu´ıa un procedimiento heur´ıstico de b´
usqueda
local en la b´
usqueda de optimalidad global. Sufilosof´ıa se basa en derivar y explotar una colecci´on
de estrategias inteligentes para la resoluci´on de problemas, basadas en procedimientos impl´ıcitos
y expl´ıcitos de aprendizaje. El marco de memoria adaptativa de la b´
usqueda tab´
u no s´olo explota
*
Este trabajo ha sido parcialmente financiado por el Ministerio de Ciencia y Tecnolog´ıa (proyecto TIN2005-08404C04-03 (70 % son fondos FEDER)) ypor el Gobierno de Canarias (proyecto PI042004/088). La actividad desarrollada
se enmarca dentro de los objetivos de la red RedHeur (proyectoTIN2004-20061-E).

1

la historia del proceso de resoluci´on del problema, sino que tambi´en exige la creaci´on de estructuras para hacer posible tal explotaci´on. De esta forma, los elementos prohibidos en la b´
usqueda
tab´
u reciben este estatus por laconfianza en una memoria evolutiva, que permite alterar este
estado en funci´on del tiempo y las circunstancias. En este sentido es posible asumir que la b´
usqueda tab´
u est´a basada en determinados conceptos que unen los campos de inteligencia artificial y
optimizaci´on.
M´as particularmente, la b´
usqueda tab´
u est´a basada en la premisa de que para clasificar un
procedimiento de resoluci´oncomo inteligente, es necesario que ´este incorpore memoria adaptativa
y exploraci´
on responsiva. La memoria adaptativa en b´
usqueda tab´
u permite la implementaci´
on de
procedimientos capaces de realizar la b´
usqueda en el espacio de soluciones eficaz y eficientemente.
Dado que las deciciones locales est´an por tanto guiadas por informaci´on obtenida a lo largo del
proceso de b´
usqueda, la b´usqueda tab´
u contrasta con dise˜
nos que por contra conf´ıan en procesos
semialeatorios, que implementan una forma de muestreo. La memoria adaptativa tambi´en contrasta
con los t´ıpicos dise˜
nos de memoria r´ıgidos tales como las estrategias de ramificaci´on y acotaci´on.
El ´enfasis en la exploraci´on responsiva considerada en la b´
usqueda tab´
u deriva de la suposici´on
de que una mala...