La abundancia de problemas de optimización de alto grado de dificultad en el mundo real ha sido una de las causas principales por la que en los últimos años se ha desarrollado un número considerable de técnicas heurísticas que permiten obtener al menos un resultado sub-óptimo en un período de tiempo relativamente corto en problemas que resultaría impráctico resolver mediante "fuerza bruta", es decir enumerando todas las posibles soluciones para escoger de entre ellas a la mejor.
La búsqueda tabú tiene sus antecedentes en métodos diseñados para cruzar cotas de factibilidad u optimalidad local tratadas como barreras en procedimientos clásicos, e imponer y eliminar cotas sistemáticamente para permitir la exploración de regiones no consideradas en otro caso.. Una característica distintiva de este procedimiento es el uso de memoria adaptativa y de estrategias especiales de resolución de problemas. La búsqueda tabú es el origen del enfoque basado en memoria y estrategia intensiva en la literatura de la meta-heurística, en contraposición con los métodos que no tienen memoria o que sólo usan una memoria débil basada en herencia. La búsqueda tabú es también responsable de enfatizar el uso de los diseños estructurados para explotar los patrones históricos de la búsqueda, de forma opuesta a los procesos que confían casi exclusivamente en la aleatorización.
Los principios fundamentales de la búsqueda tabú fueron elaborados en una serie de artículos a finales de los años 1980 y principios de los años 1990. El destacable éxito de la búsqueda tabú para resolver problemas de optimización duros, especialmente aquellos que surgen en aplicaciones del mundo real, ha causado una explosión de nuevas aplicaciones de este tipo de búsqueda durante los últimos años. La filosofía de la búsqueda tabú es derivar y explotar una colección de estrategias inteligentes para la resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje.
Las técnicas heurísticas más conocidas hoy en día no hacen más que adaptar ideas conocidas desde hace mucho tiempo en otras disciplinas. Por ejemplo, los algoritmos genéticos emulan los mecanismos de la evolución; los métodos de flujo de redes se fundamentan en ideas de la electricidad y la hidráulica, y el "templado simulado" se basa en un proceso físico de la industria metalúrgica. Similarmente, la técnica conocida como búsqueda tabú se basa en ciertos conceptos tomados de la Inteligencia Artificial y se utiliza como una meta-heurística, o una heurística de "alto nivel", para resolver problemas de optimización combinatoria. Esto significa que la técnica tiene que combinarse con algún otro mecanismo de búsqueda, y lo que hace, básicamente, es evitar que dicho mecanismo quede atrapado en algún óptimo local.
Los orígenes de la búsqueda tabú se ubican a fines de los años 1960 y principios de los años 1970, y se atribuye a Fred Glover, quien desarrolló esta heurística para tratar de resolver problemas de cubierta no lineal, aunque varios de sus principios también fueron delineados independientemente por P. Hansen. La búsqueda tabú surgió como un dispositivo que permitiría implementar una estrategia para resolver problemas de programación entera con restricciones sustitutas, y aunque su planteamiento original ha sufrido varios cambios a través de los años, la idea básica propuesta por Glover ha permanecido intacta desde sus orígenes.
La búsqueda tabú puede verse como una meta-heurística que se superpone a una técnica de búsqueda y que se encarga de evitar que dicha técnica caiga en óptimos locales prohibiendo, o en un sentido más general penalizando, ciertos movimientos. El propósito de clasificar ciertos movimientos como prohibidos es para evitar que se caiga en ciclos durante la búsqueda. Debido a esto, Glover sugiere como nombre alternativo para su método el de búsqueda con "inhibición débil", ya que los movimientos que se consideran prohibidos constituyen generalmente una pequeña fracción del total de movimientos disponibles, y un movimiento pierde su status de prohibido después de un período de tiempo relativamente corto, volviéndose después nuevamente accesible. A este respecto, este método puede contrastarse con la técnica de ramificación y límites que también prohíbe ciertos movimientos para evitar ciclos, pero lo hace de una manera más rígida, por lo que se le considera como una forma de búsqueda con "inhibición fuerte". Desde la perspectiva de la inteligencia artificial, la búsqueda tabú trata de emular, de manera somera, el comportamiento de una persona.
Es bastante aceptado que los seres humanos poseen un avanzado mecanismo de intuición que permite operar aún con información mínima o nula, pero por lo general suelen introducir un elemento aleatorio en dichas decisiones, lo cual promueve un cierto grado de "inconsistencia" en su comportamiento. La tendencia resultante en estos casos suele desviarse de una cierta trayectoria pre-establecida, lo cual algunas veces puede ser una fuente de errores, pero en otras ocasiones puede llevar a una solución mejor. La búsqueda tabú intenta emular este mecanismo fundamental de la ingenuidad humana, pero sin utilizar elementos aleatorios, sino más bien asumiendo que no hay razón para escoger un movimiento que conduzca a una peor solución, a menos que se esté tratando de evitar recorrer una ruta que ya se examinó previamente. Con esta sola excepción, la técnica buscará, a cada paso, el mejor movimiento posible de acuerdo a la métrica utilizada por el problema en cuestión. Esto hace que la técnica se envíe inicialmente de forma directa hacia un óptimo local, pero eso no importa porque la búsqueda no se detendrá ahí, sino que se reinicializará manteniendo la capacidad inicial de identificación del mejor movimiento posible. Además, se mantiene información referente a los movimientos más recientes en una o más listas tabú, a fin de evitar que una cierta trayectoria previamente recorrida se repita, aunque esta prohibición es generalmente condicional y no absoluta.
La búsqueda tabú se encuentra fundamentada en tres elementos principales: (1) El uso de estructuras flexibles de memoria basadas en atributos. Estas estructuras se encuentran diseñadas para permitir una mejor explotación de los criterios de evaluación y la información histórica de la búsqueda que lo que se conseguiría con estructuras rígidas de memoria, o con sistemas carentes de memoria. (2) Un mecanismo asociado de control. Que se utiliza para emplear las estructuras de memoria, basado en la interacción entre las condiciones que limitan y hacen más flexible el proceso de búsqueda. Este mecanismo se encuentra inmerso en la técnica en forma de restricciones y criterios de aspiración, un criterio de aspiración es aquél que permite que un movimiento pierda su status de "tabú" debido a que proporciona una mejor solución que la actual. (3) La incorporación de memorias de diferente duración. Denominadas de corto a largo plazo, se emplean para implementar estrategias que intensifiquen y diversifiquen la búsqueda. Las estrategias de intensificación refuerzan las propiedades de las combinaciones de movimientos que han demostrado, históricamente, ser buenas, mientras que las estrategias de diversificación dirigen la búsqueda hacia nuevas regiones del espacio de soluciones factibles. Se debe observar que estos dos mecanismos son muy similares al apareamiento y la mutación en los algoritmos genéticos, ya que la primera permite delimitar una cierta región del espacio de búsqueda, mientras que la segunda permite saltar a nuevas regiones del mismo, evitando quedar atrapado en un óptimo local. La parte medular de la búsqueda tabú se localiza en el proceso de memoria de corto plazo, y muchas de las consideraciones estratégicas en las que se fundamenta este proceso reaparecen, amplificadas pero sin mayores modificaciones, en los procesos de memoria de largo plazo.
El marco de memoria adaptativa de la búsqueda tabú no sólo explota la historia del proceso de resolución del problema, sino que también exige la creación de estructuras para hacer posible tal explotación. La historia de resolución del problema se extiende a la experiencia ganada tras resolver múltiples instancias de una clase de problema uniendo la búsqueda tabú con un enfoque de aprendizaje asociado llamado “análisis de objetivo”.
Las listas tabú que contienen atributos pueden ser más efectivas para algunos dominios, pese a que presentan un nuevo problema. Cuando sólo un atributo es marcado como tabú, esto por lo general resulta en que más de una solución es marcada como tabú. Algunas de estas soluciones, que ahora deben ser evitadas, podrían ser de excelente calidad y no serían visitadas. Para mitigar este problema, se introducen los "criterios de aspiración": estos pueden modificar el estado de tabú de una solución, por lo tanto incluyendo la antes excluida solución en el conjunto de soluciones permitidas. Un criterio de aspiración muy utilizado es admitir soluciones que son mejores que la mejor solución conocida al momento.
La búsqueda tabú tiene sus antecedentes en métodos diseñados para cruzar cotas de factibilidad u optimalidad local tratadas como barreras en procedimientos clásicos, e imponer y eliminar cotas sistemáticamente para permitir la exploración de regiones no consideradas en otro caso.. Una característica distintiva de este procedimiento es el uso de memoria adaptativa y de estrategias especiales de resolución de problemas. La búsqueda tabú es el origen del enfoque basado en memoria y estrategia intensiva en la literatura de la meta-heurística, en contraposición con los métodos que no tienen memoria o que sólo usan una memoria débil basada en herencia. La búsqueda tabú es también responsable de enfatizar el uso de los diseños estructurados para explotar los patrones históricos de la búsqueda, de forma opuesta a los procesos que confían casi exclusivamente en la aleatorización.
Los principios fundamentales de la búsqueda tabú fueron elaborados en una serie de artículos a finales de los años 1980 y principios de los años 1990. El destacable éxito de la búsqueda tabú para resolver problemas de optimización duros, especialmente aquellos que surgen en aplicaciones del mundo real, ha causado una explosión de nuevas aplicaciones de este tipo de búsqueda durante los últimos años. La filosofía de la búsqueda tabú es derivar y explotar una colección de estrategias inteligentes para la resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje.
Las técnicas heurísticas más conocidas hoy en día no hacen más que adaptar ideas conocidas desde hace mucho tiempo en otras disciplinas. Por ejemplo, los algoritmos genéticos emulan los mecanismos de la evolución; los métodos de flujo de redes se fundamentan en ideas de la electricidad y la hidráulica, y el "templado simulado" se basa en un proceso físico de la industria metalúrgica. Similarmente, la técnica conocida como búsqueda tabú se basa en ciertos conceptos tomados de la Inteligencia Artificial y se utiliza como una meta-heurística, o una heurística de "alto nivel", para resolver problemas de optimización combinatoria. Esto significa que la técnica tiene que combinarse con algún otro mecanismo de búsqueda, y lo que hace, básicamente, es evitar que dicho mecanismo quede atrapado en algún óptimo local.
Los orígenes de la búsqueda tabú se ubican a fines de los años 1960 y principios de los años 1970, y se atribuye a Fred Glover, quien desarrolló esta heurística para tratar de resolver problemas de cubierta no lineal, aunque varios de sus principios también fueron delineados independientemente por P. Hansen. La búsqueda tabú surgió como un dispositivo que permitiría implementar una estrategia para resolver problemas de programación entera con restricciones sustitutas, y aunque su planteamiento original ha sufrido varios cambios a través de los años, la idea básica propuesta por Glover ha permanecido intacta desde sus orígenes.
La búsqueda tabú puede verse como una meta-heurística que se superpone a una técnica de búsqueda y que se encarga de evitar que dicha técnica caiga en óptimos locales prohibiendo, o en un sentido más general penalizando, ciertos movimientos. El propósito de clasificar ciertos movimientos como prohibidos es para evitar que se caiga en ciclos durante la búsqueda. Debido a esto, Glover sugiere como nombre alternativo para su método el de búsqueda con "inhibición débil", ya que los movimientos que se consideran prohibidos constituyen generalmente una pequeña fracción del total de movimientos disponibles, y un movimiento pierde su status de prohibido después de un período de tiempo relativamente corto, volviéndose después nuevamente accesible. A este respecto, este método puede contrastarse con la técnica de ramificación y límites que también prohíbe ciertos movimientos para evitar ciclos, pero lo hace de una manera más rígida, por lo que se le considera como una forma de búsqueda con "inhibición fuerte". Desde la perspectiva de la inteligencia artificial, la búsqueda tabú trata de emular, de manera somera, el comportamiento de una persona.
Es bastante aceptado que los seres humanos poseen un avanzado mecanismo de intuición que permite operar aún con información mínima o nula, pero por lo general suelen introducir un elemento aleatorio en dichas decisiones, lo cual promueve un cierto grado de "inconsistencia" en su comportamiento. La tendencia resultante en estos casos suele desviarse de una cierta trayectoria pre-establecida, lo cual algunas veces puede ser una fuente de errores, pero en otras ocasiones puede llevar a una solución mejor. La búsqueda tabú intenta emular este mecanismo fundamental de la ingenuidad humana, pero sin utilizar elementos aleatorios, sino más bien asumiendo que no hay razón para escoger un movimiento que conduzca a una peor solución, a menos que se esté tratando de evitar recorrer una ruta que ya se examinó previamente. Con esta sola excepción, la técnica buscará, a cada paso, el mejor movimiento posible de acuerdo a la métrica utilizada por el problema en cuestión. Esto hace que la técnica se envíe inicialmente de forma directa hacia un óptimo local, pero eso no importa porque la búsqueda no se detendrá ahí, sino que se reinicializará manteniendo la capacidad inicial de identificación del mejor movimiento posible. Además, se mantiene información referente a los movimientos más recientes en una o más listas tabú, a fin de evitar que una cierta trayectoria previamente recorrida se repita, aunque esta prohibición es generalmente condicional y no absoluta.
La búsqueda tabú se encuentra fundamentada en tres elementos principales: (1) El uso de estructuras flexibles de memoria basadas en atributos. Estas estructuras se encuentran diseñadas para permitir una mejor explotación de los criterios de evaluación y la información histórica de la búsqueda que lo que se conseguiría con estructuras rígidas de memoria, o con sistemas carentes de memoria. (2) Un mecanismo asociado de control. Que se utiliza para emplear las estructuras de memoria, basado en la interacción entre las condiciones que limitan y hacen más flexible el proceso de búsqueda. Este mecanismo se encuentra inmerso en la técnica en forma de restricciones y criterios de aspiración, un criterio de aspiración es aquél que permite que un movimiento pierda su status de "tabú" debido a que proporciona una mejor solución que la actual. (3) La incorporación de memorias de diferente duración. Denominadas de corto a largo plazo, se emplean para implementar estrategias que intensifiquen y diversifiquen la búsqueda. Las estrategias de intensificación refuerzan las propiedades de las combinaciones de movimientos que han demostrado, históricamente, ser buenas, mientras que las estrategias de diversificación dirigen la búsqueda hacia nuevas regiones del espacio de soluciones factibles. Se debe observar que estos dos mecanismos son muy similares al apareamiento y la mutación en los algoritmos genéticos, ya que la primera permite delimitar una cierta región del espacio de búsqueda, mientras que la segunda permite saltar a nuevas regiones del mismo, evitando quedar atrapado en un óptimo local. La parte medular de la búsqueda tabú se localiza en el proceso de memoria de corto plazo, y muchas de las consideraciones estratégicas en las que se fundamenta este proceso reaparecen, amplificadas pero sin mayores modificaciones, en los procesos de memoria de largo plazo.
El marco de memoria adaptativa de la búsqueda tabú no sólo explota la historia del proceso de resolución del problema, sino que también exige la creación de estructuras para hacer posible tal explotación. La historia de resolución del problema se extiende a la experiencia ganada tras resolver múltiples instancias de una clase de problema uniendo la búsqueda tabú con un enfoque de aprendizaje asociado llamado “análisis de objetivo”.
Las listas tabú que contienen atributos pueden ser más efectivas para algunos dominios, pese a que presentan un nuevo problema. Cuando sólo un atributo es marcado como tabú, esto por lo general resulta en que más de una solución es marcada como tabú. Algunas de estas soluciones, que ahora deben ser evitadas, podrían ser de excelente calidad y no serían visitadas. Para mitigar este problema, se introducen los "criterios de aspiración": estos pueden modificar el estado de tabú de una solución, por lo tanto incluyendo la antes excluida solución en el conjunto de soluciones permitidas. Un criterio de aspiración muy utilizado es admitir soluciones que son mejores que la mejor solución conocida al momento.
Guillermo Choque Aspiazu
http://www.eldiario.net/
Junio 21 de 2010
No hay comentarios:
Publicar un comentario