Licenciado
Páginas: 21 (5191 palabras)
Publicado: 10 de noviembre de 2012
UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
FACULTAD CIENCIAS MATEMATICAS
E.A.P. DE..INVESTIGACIÓN OPERATIVA
Conceptos, algoritmo y aplicación al problema de las N – reinas
Capítulo3. Búsqueda de tabú
MONOGRAFÍA Para optar el Título de Licenciada de Investigación operativa
AUTOR Alicia Cirila Riojas Cañari
LIMA – PERÚ 2005
CAPÍTULO 3 BÚSQUEDA TABÚ La búsqueda Tabú surge, en unintento de dotar de “inteligencia” a los algoritmos de búsqueda local. Según Fred Glover, su primer definidor, espacio de soluciones más allá del óptimo local”. La búsqueda tabú toma de la Inteligencia Artificial el concepto de memoria y lo implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, es decir, el procedimiento trata de extraerinformación de lo sucedido y actuar en consecuencia. En este sentido puede decirse que hay un cierto aprendizaje y que la búsqueda es inteligente. La búsqueda tabú permite moverse a una solución aunque no sea tan buena como la actual, de modo que se pueda escapar de óptimos locales y continuar estratégicamente la búsqueda de soluciones aún mejores[1]. 3.1. Desarrollo histórico Los orígenes de laBúsqueda Tabú (Tabú Search) datan de finales de los 70. Oficialmente el nombre y la metodología fueron introducidos por Fred Glover en dos artículos (1989)[2]. En palabras del autor
“La búsqueda tabú tiene sus orígenes en procedimientos combinatorios aplicados a problemas de cubrimiento no lineales en los finales de los años 70 y aplicada subsecuentemente a una diversa colección de problemas quevan desde secuenciación y balance de canales de computación hasta análisis de clusters y planeamiento de espacio”
“la
búsqueda tabú guía un procedimiento de búsqueda local para explorar el
[1]
Díaz, A., Glover, F., Ghaziri, H.M., et al, Optimización Heurística y Redes Neuronales. Madrid, Glover, Fred. “Tabu Search – Part I”, ORSA Journal on computing ,v. 1, n. 3, pp. 190-206. SummerParaninfo, (1996).
[2]
1989
32
Actualmente Fred Glover trabaja en la Universidad de Colorado (USA) y sus trabajos recientes así como sus publicaciones se pueden ver en la página http://spot.colorado.edu/~glover/. El término tabú (taboo) procede de la Polinesia[11], donde es usado por los aborígenes de la isla Tonga para referirse a cosas que no pueden ser tocadas porque son sagradas,una acepción más moderna la define como “Una prohibición impuesta por costumbres sociales como una medida de protección”, también como “marcada como que constituye un riesgo”, esta acepción es la que está más cerca de la esencia del método donde el riesgo a ser evitado es el de seguir un camino no productivo, incluyendo el de ser conducido a una trampa de la que no se puede salir (óptimo local).Actualmente esta metaheurística tiene un gran campo de aplicación como se puede apreciar en el anexo 3.1 . 3.2. Definiciones Se presentan primero algunos conceptos propios de los métodos de búsqueda y luego los conceptos específicos de la búsqueda tabú Conceptos de los métodos de búsqueda • Dado un problema P de optimización combinatoria utilizaremos x para denotar el conjunto de soluciones posiblesdel problema y c para la función objetivo. • • Cada solución tiene un conjunto de posibles soluciones asociadas, que se denomina entorno o vecindario de x y se denota como N(x). Cada solución del entorno puede obtenerse directamente a partir de x mediante una operación llamada movimiento.
[11]
Glover, Fred & Laguna, Manuel “Tabu search”.http://leeds-faculty.colorado.edu/laguna/articles/ts2.pdf
33
•
La solución Inicial x0 dependerá del algoritmo específico que la genera, se puede usar una heurística para proporcionar una buena solución inicial o se puede partir de una solución obtenida aleatoriamente, lo usual es utilizar el conocimiento que se tiene de dónde podría haber una buena solución, pero, si no se tiene ninguna información puede partirse de cualquier valor y...
FACULTAD CIENCIAS MATEMATICAS
E.A.P. DE..INVESTIGACIÓN OPERATIVA
Conceptos, algoritmo y aplicación al problema de las N – reinas
Capítulo3. Búsqueda de tabú
MONOGRAFÍA Para optar el Título de Licenciada de Investigación operativa
AUTOR Alicia Cirila Riojas Cañari
LIMA – PERÚ 2005
CAPÍTULO 3 BÚSQUEDA TABÚ La búsqueda Tabú surge, en unintento de dotar de “inteligencia” a los algoritmos de búsqueda local. Según Fred Glover, su primer definidor, espacio de soluciones más allá del óptimo local”. La búsqueda tabú toma de la Inteligencia Artificial el concepto de memoria y lo implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, es decir, el procedimiento trata de extraerinformación de lo sucedido y actuar en consecuencia. En este sentido puede decirse que hay un cierto aprendizaje y que la búsqueda es inteligente. La búsqueda tabú permite moverse a una solución aunque no sea tan buena como la actual, de modo que se pueda escapar de óptimos locales y continuar estratégicamente la búsqueda de soluciones aún mejores[1]. 3.1. Desarrollo histórico Los orígenes de laBúsqueda Tabú (Tabú Search) datan de finales de los 70. Oficialmente el nombre y la metodología fueron introducidos por Fred Glover en dos artículos (1989)[2]. En palabras del autor
“La búsqueda tabú tiene sus orígenes en procedimientos combinatorios aplicados a problemas de cubrimiento no lineales en los finales de los años 70 y aplicada subsecuentemente a una diversa colección de problemas quevan desde secuenciación y balance de canales de computación hasta análisis de clusters y planeamiento de espacio”
“la
búsqueda tabú guía un procedimiento de búsqueda local para explorar el
[1]
Díaz, A., Glover, F., Ghaziri, H.M., et al, Optimización Heurística y Redes Neuronales. Madrid, Glover, Fred. “Tabu Search – Part I”, ORSA Journal on computing ,v. 1, n. 3, pp. 190-206. SummerParaninfo, (1996).
[2]
1989
32
Actualmente Fred Glover trabaja en la Universidad de Colorado (USA) y sus trabajos recientes así como sus publicaciones se pueden ver en la página http://spot.colorado.edu/~glover/. El término tabú (taboo) procede de la Polinesia[11], donde es usado por los aborígenes de la isla Tonga para referirse a cosas que no pueden ser tocadas porque son sagradas,una acepción más moderna la define como “Una prohibición impuesta por costumbres sociales como una medida de protección”, también como “marcada como que constituye un riesgo”, esta acepción es la que está más cerca de la esencia del método donde el riesgo a ser evitado es el de seguir un camino no productivo, incluyendo el de ser conducido a una trampa de la que no se puede salir (óptimo local).Actualmente esta metaheurística tiene un gran campo de aplicación como se puede apreciar en el anexo 3.1 . 3.2. Definiciones Se presentan primero algunos conceptos propios de los métodos de búsqueda y luego los conceptos específicos de la búsqueda tabú Conceptos de los métodos de búsqueda • Dado un problema P de optimización combinatoria utilizaremos x para denotar el conjunto de soluciones posiblesdel problema y c para la función objetivo. • • Cada solución tiene un conjunto de posibles soluciones asociadas, que se denomina entorno o vecindario de x y se denota como N(x). Cada solución del entorno puede obtenerse directamente a partir de x mediante una operación llamada movimiento.
[11]
Glover, Fred & Laguna, Manuel “Tabu search”.http://leeds-faculty.colorado.edu/laguna/articles/ts2.pdf
33
•
La solución Inicial x0 dependerá del algoritmo específico que la genera, se puede usar una heurística para proporcionar una buena solución inicial o se puede partir de una solución obtenida aleatoriamente, lo usual es utilizar el conocimiento que se tiene de dónde podría haber una buena solución, pero, si no se tiene ninguna información puede partirse de cualquier valor y...
Leer documento completo
Regístrate para leer el documento completo.