En algunas ocasiones, hemos de enfrentarnos a problemas que no podemos solucionar de forma exacta en márgenes de tiempo razonables o eficientes. En ámbitos como la Inteligencia Artificial o la Optimización, no es una excepción que esto ocurra. Normalmente, sucede por la complejidad o la muy alta dimensión del propio problema. Afortunadamente, los avances en el campo de la computación hacen que cada vez más problemas se sumen al conjunto de aquellos que son resolubles en un tiempo aceptable.
Para los que aún no entran dentro de este grupo, existe un conjunto de procedimientos, métodos y algoritmos que, sin garantizar la consecución de la solución exacta, garantizan un resultado lo suficientemente próximo al óptimo dentro del horizonte temporal disponible. Son los denominados, de forma general, como Heurísticos.
Búsqueda tabú
En la actualidad, no son pocos los procedimientos heurísticos que podemos encontrar. Uno de ellos es el denominado «Búsqueda Tabú«. Se trata de una heurística que guía un procedimiento de búsqueda local con el objetivo de explorar el espacio de soluciones de un problema, modificando adaptativamente el área de búsqueda a medida que ésta avanza. Las modificaciones tratan de evitar óptimos locales o la exploración de regiones con escasas probabilidades de contener la solución óptima.
El nombre «tabú» hace referencia al uso de estructuras de memoria para excluir de la búsqueda a ciertas regiones del espacio de soluciones. La estrategia fundamental de la búsqueda tabú es reforzar acciones que puedan conducir a buenas soluciones y desalentar aquellas otras que se intuyen, en términos de probabilidad, poco prometedoras.
El primer artículo en el que apareció el nombre de búsqueda tabú (tabú search) fue redactado por Fred Glover en 1.986.
Fred Glover
Fred W. Glover nació el 8 de maro de 1.937, en Kansas (Missouri).
Se graduó en Administración de Empresas en la Universidad de Missouri Kansas City. En 1.965, recibió su doctorado en Investigación Operativa en la Universidad de Carnegie Mellon, investigando junto a Gerald L. Thompson. Su tesis introdujo restricciones sustitutivas y una estructura de datos mejorada para la enumeración implícita.
Con posterioridad fue investigador postdoctoral en el Instituto de Investigación Miller en la Universidad de California, Berkeley, asociado con el Centro de Investigación de Operaciones de George Dantzig.
Fue profesor asociado de Investigación de Operaciones y Ciencias de la Computación en la Universidad de Texas, en Austin.
En 1.969 se convirtió en Director de Investigación en Analysis, Research and Computation, Inc.
En 1.970 se convirtió en profesor de Ciencias Administrativas en la Universidad de Colorado. Durante este tiempo mantuvo una estrecha relación con Darwin D. Klingman, trabajando para reducir el tiempo de cálculo y los requisitos de memoria de los algoritmos de optimización de redes.
El Consejo Editorial de la revista Networks creó el premio Glover-Klingman al mejor artículo que aparece en esta publicación, en reconocimiento a su implementación innovadora de algoritmos de optimización en redes.
En la década de 1970, Glover y Kilngman comenzaron un trabajo revolucionario en la optimización de redes. Desarrollaron nuevas estructuras de datos, algoritmos e implementaciones informáticas, que supusieron grandes adelantos en esta campo.
Con posterioridad, Glover desarrolló el concepto de búsqueda tabú, metaheurística de gran impacto en la resolución de problemas combinatorios de alta complejidad. Él acuñó el término en su artículo de 1.986. El algoritmo Búsqueda Tabú ha demostrado una gran aplicabilidad, desde problemas de programación a problemas de planificación financiera. Por esta aportación científica, Glover recibió el John von Neumann Theory Prize en 1.998.
Además de su trabajo como profesor emérito en la Universidad de Colorado, Glover fue Director Fundador de Investigación en el Centro de Inteligencia Artificial Aplicada de la Universidad y Jefe de Investigación en el Centro de Construcción Espacial de la NASA.
En la década de 1.980 y principios de 1.990 fue Director de Desarrollo de Tecnología en Management Robotics y, con posterioridad, Director de Tecnología de OptTek Systems, Inc.
Es autor de más de 450 artículos publicados y 8 libros en los campos de la Optimización Matemática, la Informática y la Inteligencia Artificial.
Glover ha recibido varios reconocimientos a lo largo de su carrera. En 2010, obtuvo (junto a miembros de su equipo) el Premio INFORMS Impact. También recibió el Premio Herbert Simon en 2013, por su Contribución Sobresaliente en Tecnología de la Información y Toma de Decisiones, junto a Gary Kochenberger por su investigación pionera sobre nuevos modelos de optimización para la minería de datos, y en 2022 recibió el premio IJOC Test of Time de INFORMS Journal on Computing en reconocimiento del impacto a lo largo de los años de sus artículos en el campo de la optimización combinatoria.
