Algoritmo de la BÚSQUEDA TABÚ SIMPLE
Renzo Inga AguilarTarea18 de Diciembre de 2015
6.201 Palabras (25 Páginas)317 Visitas
Objetivos
Objetivo Fundamental:
Antecedentes:
Metodología:
Definición del problema.
Búsqueda Tabú
Características de la búsqueda tabú
Estructuras de la búsqueda tabú
Identificación de las variables.
Limitaciones.
Restricciones
Análisis y Discusión de Resultados:
Algoritmo de la BÚSQUEDA TABÚ SIMPLE
¿Qué se necesita para su implementación?
Tabla 3.1
¿Cuándo se detiene el proceso?
Aplicación del algoritmo de la búsqueda tabú
Selección de la solución inicial:
Conclusiones y Recomendaciones:
“Heurística del Agente viajero aplicado al reparto de couriers”
Objetivos
Objetivo Fundamental:
1. Repartir todos los couriers en su destino respectivo con la mayor eficiencia posible.
B. Objetivos Específicos:
- Elaborar el modelo matemático del problema.
- Encontrar la ruta más corta para repartir todos los couriers mediante la aplicación de un algoritmo de búsqueda tabú.
- Calcular los costos ahorrados por la empresa al aplicar la nueva ruta.
- Analizar y discutir los resultados.
Antecedentes:
Los orígenes de la Bú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). 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 que van desde secuenciación y balance de canales de computación hasta análisis de clusters y planeamiento de espacio”
La primera solución reportada para resolver el problema del Agente Viajero fue en 1954, cuando George Dantzig, Ray Fulkerson, y Selmer Johnson publicaron la descripción de un método de solución del PAV (Problema del Agente Viajero o sus siglas en inglés TSP – Travel Sailsman Problem) titulado “Solutions of a large scale traveling salesman problem“ (Soluciones de gran escala para el problema del agente viajero) para resolver una instancia de 49 ciudades donde un agente viajero desea visitar un conjunto de ciudades, asignándoles un costo por visitar ciudades contiguas (distancia de traslado entre dos ciudades). Para esta solución se propusieron 2 condiciones: regresar a la misma ciudad de la cual partió y no repetir ciudades con el objetivo de encontrar una ruta o un camino con el menor costo posible.
- En 1832 se menciona el problema en un manual del agentes viajeros con ejemplos de tours por Alemania y Suiza, pero sin un tratamiento matemático.
- En 1932 Karl Menger “Das botenproblem” Ergebnisse eines Mathematischen Kolloquiums 2 pp.1112 menciona un problema que enfrentan los mensajeros postales y otros viajeros de encontrar para un número finito de puntos el camino más corto que los une.
- Martin Groetschel (1977) encuentra el tour óptimo para 120 ciudades de Alemania.
[pic 1]
Metodología:
Definición del problema.
El problema del agente viajero, consiste en encontrar la secuencia en que un viajero debe visitar n ciudades, de manera que la distancia recorrida sea mínima. Se trata de un problema NP completo, es decir, la única alternativa para su solución consiste en verificar todas las posibles opciones para encontrar cuál es la óptima, hay que tener en cuenta que si el número de ciudades es n, el número de posibles recorridos a ensayar resulta ser n!/(2n).
Figura 1: Problema del Agente Viajero
[pic 2]
Principales algoritmos para resolver el problema del agente viajero:
- Algoritmos Genéticos(AGs)
- Recocido Simulado(RS)
- Colonias de Hormigas
- Búsqueda Tabú
Para resolver el problema usaremos el algoritmo de Búsqueda Tabú.
Búsqueda Tabú
Surge en un intento de dotar de “inteligencia” a los algoritmos de búsqueda local. Según Fred Glover en 1986. La búsqueda tabú es una metaheurística que guía un procedimiento heurístico de búsqueda local en la búsqueda de optimalidad para su resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje.
El marco de memoria adaptativa de la búsqueda tabú no sólo explotaba 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. De esta forma, los elementos prohibidos en la búsqueda tabú reciben este estatus por la confianza en una memoria evolutiva, que permite alterar este estado en función de tiempo y las circunstancias. En este sentido es posible asumir que la búsqueda tabú está basada en determinados conceptos que unen los campos de la inteligencia artificial y optimización.
El término tabu(taboo) procede de la polinesia, donde es usado por los aborígenes de la isla Tonga para referirse a cosas que no se pueden ser tocadas porque son sagradas, una acepción más moderna la define como “Una prohibición impuesta por costumbres sociales como que constituye 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.
El tamaño de la lista tabú( tabu ternure) es el tiempo o número de iteraciones que un elemento(movimiento o atributo) permanece en la lista tabú. Si todos los elementos tienen la misma ternure, ésta estará identificada por la longitud de la lista tabú, si es variable, es decir, todos los elementos de la lista tabú no tienen la misma ternure, un elemento que entró a la lista tabú antes que otro puede salir mucho después. Esto es, si un movimiento tipo 1 tiene asociada una ternure de 5 y entra a la lista tabú en la iteración 30, (saldrá en la iteración 35) y si un movimiento tipo 2 tiene asociada una ternure de 2 y entra a la lista tabú en la iteración 31, saldrá de la misma en la iteración 33, entró después, pero sale antes.
La lista tabú puede contener:
Soluciones visitadas recientemente.
Movimientos realizados recientemente o
Atributos o características que tenían las soluciones visitadas.
Características de la búsqueda tabú
Utiliza una estrategia basada en el uso de estructuras de memoria para escapar de los óptimos locales, en los que se puede caer al “moverse” de una solución a otra por el espacio de soluciones. La estructura de la memoria en la metaheurística de la búsqueda tabú aplica en relación a cuatro dimensiones principales que son: la calidad, la influencia, la memoria basada en la frecuencia (largo plazo) y la memoria basada en lo creciente (corto plazo).
En este contexto, la memoria se puede utilizar para identificar los elementos que son comunes a las buenas soluciones o caminos que conducen a este tipo de soluciones. Operacionalmente, la calidad se convierte en una base para el aprendizaje basado en incentivos, los incentivos que se proporcionan a reforzar las acciones que conducen a buenas soluciones y de las sanciones previstas son las acciones para desalentar que conducen a las malas soluciones la flexibilidad de estas estructuras de memoria permite la búsqueda a ser guiada en un ambiente objetivo, donde la bondad de una búsqueda de dirección puede estar determinada por más de una función.
La estructura de la memoria en la metaheurística de búsqueda tabú opera en relación a cuatro dimensiones principales
Calidad.
Influencia.
Corto plazo (lo reciente).
Corto plazo (lo frecuente).
Estructuras de la búsqueda tabú
[pic 3]
La calidad se refiere a la habilidad para diferenciar el mérito de las soluciones, identifica que las hace tan buenas e incentiva la búsqueda para reforzar las acciones que conducen a una buena solución y desalienta aquellas que conducen a soluciones pobres.
La flexibilidad de la estructura de memoria permite que la búsqueda sea guiada en un contexto multiobjetivo, donde la bondad de una dirección de búsqueda particular puede estar determinada por más de una función. El concepto de calidad en la búsqueda tabú es más amplio que el usado implícitamente en los métodos de optimización, en los cuales se considera que un movimiento es de mejor calidad que otro porque produce una mejor “mejora” (tal es el caso del descenso más rápido), bajo el enfoque de búsqueda tabú un movimiento puede ser de mejor calidad si, por ejemplo, su frecuencia de ocurrencia en el pasado es baja o no ha ocurrido antes y nos permite explorar nuevas regiones. La definición de la calidad de una solución es flexible y puede ser adaptado a la naturaleza del problema.
...