Proyecto Hyperion
Investigación Algorítmica
1
LogycSystems
Agenda
Algoritmos Investigados Conclusiones Preguntas
2Proyecto Hyperion - Presentación de Investigación Algorítmica
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 3
Algoritmos Investigados
3Proyecto Hyperion - Presentación de Investigación Algorítmica
Descripción del conjunto de algoritmos que pueden servir como base para la construcción de una solución para el problema de la Programación de Tareas
Voraces (greedy) GRASP Búsqueda Tabú
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 4
Algoritmos Voraces
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 5
Algoritmos Voraces
Descripción
Normalmente usados en problemas de optimización. Aplica a problemas donde se busca maximizar o
minimizar una función objetivo Dado un conjunto de elementos de entrada se van
seleccionando o desechando estos para formar un conjunto de elementos que cumplan con la restricciones.
La solución final no tiene porque ser optima siempre
Proyecto Hyperion - Presentación de Investigación Algorítmica 6
Algoritmos Voraces
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 7
Algoritmos VoracesVentajas y Desventajas
Rapidez en hallar una solución, cuando la
encuentran
Fácil implementación y realización de pruebas
Moderado costo computacional
× Toma de decisiones sin tomar en cuenta lo que
pueda ocurrir mas adelante
× Pueden caer en ciclos
Proyecto Hyperion - Presentación de Investigación Algorítmica 8
Problemas con velocidad de respuesta vital Problemas con árboles de decisiones muy grandes,
donde es casi imposible analizar la totalidad de posibilidades
Ejemplos: Búsqueda de caminos mínimos sobre grafos Búsqueda de árbol mínimo recubridor Selección de proyectos simple
Algoritmos Voraces
Aplicaciones
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 9
GRASP
Proyecto Hyperion - Presentación de Investigación Algorítmica 10
Algoritmo GRASP
Descripción• Algoritmo de Búsqueda meta-heurística.• Combina métodos de optimización
determinísticos y estocásticos.• Etapas: Construcción y Procedimiento de
búsqueda local.
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 11
Algoritmo GRASP Algoritmo – Problema de cortes en Láminas
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 12
Ventajas y Desventajas
Algoritmo GRASP
Los algoritmos GRASP son recomendables cuando el conjunto de datos a trabajar es muy grande.
La solución obtenida no es la óptima, pero es altamente aceptable.
Este algoritmo se puede utilizar con gran éxito en sectores que tengan que ver con empaquetamientos.
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 13
Aplicaciones
Algoritmo GRASP
Para resolver el problema de Multi-Agente
Viajero: Una aplicación en la Distribución de
Mercaderías.
La localización multiobjetivo de Molinos de
Vientos
Corte 2D con agrupamiento tipo guillotina con
rotación para tableros
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 14
Búsqueda Tabú
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 15
Descripción
• Algoritmo de Búsqueda Meta heurístico que guía un procedimiento heurístico de búsqueda local en la búsqueda de optimalidad global.
Búsqueda Tabú
Proyecto Hyperion - Presentación de Investigacion Algoritmica 16
Limitante: se detiene al encontrar un mínimo local
“Local Search”
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 17
Búsqueda Tabú = Búsqueda local + Memoria a corto plazo
Lista Tabú
Búsqueda Tabú
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 18
Procedimiento de resolución inteligente
Memoria adaptativa
Exploración responsiva
Búsqueda Tabú
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 19
Restricciones Tabú
Criterio de aspiración
Elementos Claves
Evita Ciclos
Escapa de un pobre óptimo
local
Evita movidas hacia atrás
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 20
Ejemplo Programación de Tareas
[Introducción a la Búsqueda Tabú]
T1
T2
T3
T4
T5
T6
Maquina
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 21
Ejemplo
Permutación Inicial
Solución Adyacente
Valor Función Objetivo = 39
Valor Función Objetivo = 47
15 posibles intercambios
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 22
Iteración 1Iteración 0
Estructura Lista Tabú
Nota: Las Restricciones Tabú no son inviolables.
Ejemplo
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 23
Iteración 2 Iteración 3
Movimiento de no Mejora
Iteración 4
Iteración 6 Iteración 5
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 24
Factores
Vecinos.
Tamaño de la Lista Tabú.
Numero de Vecinos No tabúes generados en una
Iteración.
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 25
Estructuras de Memoria Tabú Complementarias
Veces que cada par de tareas ha sido intercambiado
… 14 Iteraciones después
Ejemplo
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 26
Ventajas y Desventajas
Supera las limitaciones de los algoritmos heurísticos :
Miopía y voracidad
Evita movimientos hacia atrás (Lista Tabú)
Su enfoque es mas determinista.
× Difícil de Implementar
× Alto Costo Computacional
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 27
Aplicaciones
Problemas de Planificación (Horarios)
Diseño (Espacios arquitectónicos, redes tolerantes a
errores)
Lógica e Inteligencia artificial (Reconocimiento de
patrones)
Telecomunicaciones (asignación de rutas)
Producción, inventario e inversión (planeación de
inventarios)
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 28
Conclusiones
Preguntas
Proyecto Hyperion - Presentacion de Investigacion Algoritmica 29