Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Copy of IMPLEMENTACIÓN DE ALGORITMOS INMUNES ARTIFICIALES PARA LA SOLUCIÓN DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS

Presentacion Plan de Proyecto
by

ed f12

on 2 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of IMPLEMENTACIÓN DE ALGORITMOS INMUNES ARTIFICIALES PARA LA SOLUCIÓN DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS

Presentado por:
Ing. Wilfredo Ariel Gómez Bueno
Dirigido por:
Ph.D(c). Lola Xiomara Bautista
Co-Dirigido por:
Ph.D(c). Darío José Delgado Complejidad Computacional INTRODUCCIÓN Optimización Combinatoria Problema de Planificación
de Trabajos(Job Shop Scheduling) Sistemas Inmunes Artificiales SCHEDULING PROBLEM PROBLEMA DE PLANIFICACIÓN Job Shop Scheduling PROBLEMA DE PLANIFICACIÓN DE TRABAJOS “El problema de acomodar los recursos en el tiempo para realizar un conjunto de trabajos“ IMPLEMENTACIÓN DE ALGORITMOS BIOINSPIRADOS PARA LA SOLUCIÓN
DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS GRUPO DE INVESTIGACION EN INGENIERÍA BIOMÉDICA
GIIB •Computacion(Multitarea y Multiprocesamiento)
•Redes de Computadoras(Networking)
•Procesos de Producción y Administración
•Programación Horaria APLICACIONES Una estrategia maestra que guía y modifica otra heurística para producir soluciones más allá de aquellas que son normalmente obtenidas en una búsqueda de optimalidad local.

Glover y Laguna 2001 Las meta-heurísticas son procedimientos para la busqueda de soluciones para problemas de optimización que introducen reglas sistemáticas que les permiten, en la mayoría de los casos, continuar con la búsqueda del valor óptimo dejando de lado los óptimos locales


Handbook of Industrial and systems engineering 2005 Colonias de hormigas de Castro, Leandro N. ; Timmis, Jonathan (2002) "Los sistemas inmunes artificiales son sistemas adaptativos, inspirados en la inmunología teórica y las funciones inmunes, principios y modelos, que se aplican a la resolución de problemas" los anticuerpos son la analogía a las soluciones de un
problema de optimización y la función objetivo es
el antígeno a reconocer Antígenos y Anticuerpos El grado de afinidad entre anticuerpos y antígenos representa el Umbral de error permitido en una solución de un problema de Optimización. Esta afinidad se calcula por medio de la función de Aptitud. Afinidad de la Solución Es el proceso por el cual las posibles soluciones pasan por una serie de operadores de mutación, clonación y selección con el fin de ir mejorando las mismas para llegar al mayor grado de afinidad entre la solución y la función objetivo. Maduración de la Solución de Castro, L. N. & Timmis, J. I. "An Artificial Immune Network for Multimodal Function Optimization", In Proceedings of IEEE CEC'02, 1, pp. 699-674. COMPLEJIDAD INSTANCIA EFICIENCIA PROBLEMA APLICABILIDAD •¿Qué tan eficientes son los algoritmos bioinspirados aplicados al problema de planificación de trabajos? PREGUNTA PROBLEMA SOLUCIÓN APLICABILIDAD •Implementar computacionalmente un algoritmo de colonia de homigas y un algoritmo inmune artificial para resolver una instancia común del problema de planificación de trabajos, contrastando su desempeño frente a un algoritmo de búsqueda global GRASP. OBJETIVO PRINCIPAL 









 •Caracterizar la instancia del problema de planificación de trabajos común a todas las técnicas. •Implementar un algoritmo inmune artificial, y un algoritmo de colonia de hormigas sobre una instancia del problema de Planificación de trabajos. •Contrastar el desempeño de las técnicas bioinspiradas frente a un algoritmo de búsqueda global conocido como GRASP. •Establecer posibles instancias de aplicación de los algoritmos desarrollados sobre problemas de planificación relacionados al área computacional. METODOLOGÍA CALENDARIO PRESUPUESTO GRACIAS ESTUDIO ESTUDIO REFERENCIA Garey y Jonhson en su libro Computers and Intractability: A Guide to the Theory of NP-Completeness en 1979, demostraron que el problema de planificación es un problema NP-duro, y Tapan P. Bagchi en MultiObjective Scheduling by Genetic Algorithms de 1999, describe que de entre esa clase es uno de los menos tratables.
Para un problema de 24 operaciones y 1 recurso




Una estimación de la edad del universo . J. Blazewicz, K. H. Ecker, G. Schmidt, and J. Weglarz. Scheduling in Computer and Manufacturing System. Springer, 1994. PROBLEMA DE PLANIFICACIÓN DE TRABAJOS DEFINICIÓN MATEMATICA DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS Peña, Víctor. Zumelzu, Lillo Estado del Arte del Job Shop Scheduling Problem Departamento de Informática, Universidad Técnica Federico Santa María Valparaíso, Chile. 2006. INSTANCIA DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS MÉTODOS DE SOLUCION PROBLEMA DE PLANIFICACIÓN DE TRABAJOS EXACTOS APROXIMADOS Backtracking
Branch and Bound
Programación dinámica Algoritmos constructivos Algoritmos de búsqueda local Heuristicas
Greedy Voraces Heuristicas
Iterativas GRASP META
HEURISTICAS COMPUTACIÓN
BIOINSPIRADA RECOCIDO SIMULADO BUSQUEDA TABÚ COMPUTACION BIOINSPIRADA METAHEURISTICAS PARA SOLUCION DE PROBLEMAS DE OPTIMIZACIÓN Emanuel Téllez Enríquez ”Uso de una Colonia de Hormigas para resolver Problemas de programación de Horarios” LINEA DE TIEMPO DE METODOS DE SOLUCIÓN DEL PROBLEMA DE PLANIFICACIÓN COMPLEJIDAD COMPUTACIONAL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS “Los sistemas inmunes artificiales son metodologías inteligentes inspiradas en el sistema inmune, enfocadas a resolver problemas del mundo real"
  Dasgupta, Dipankar (1999) PRINCIPIOS INMUNES ALGORITMO INMUNE PARA OPTIMIZACIÓN Es una metaheurística que engloba un conjunto de técnicas de optimización inspiradas en el comportamiento colectivo de las hormigas, las cuales son capaces de encontrar un camino corto entre el nido y la fuente de alimento; esta técnica nació con la tesis doctoral de Marco Dorigo en Milán, Italia en 1992 Sergio Alonso, Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera “La Metaheurística de Optimización Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques”.
Do While (hasta que el criterio no sea satisfecho)
Do Until (cada hormiga completa un viaje)
Construcción de soluciones por hormigas
Actualización del rastro local feromona
End Do
Servidor de acciones
End Do Se utiliza comunicación indirecta a través de la feromona. Las rutas más cortas tienden a tener una razón más alta de crecimiento del valor de la feromona. Las hormigas tienen preferencia probabilística por las rutas con valores altos de feromona. PRINCIPIOS COLONIA DE
HORMIGAS (Benito Mendoza,2001) Greedy randomized adaptative search procedures Peña, Víctor. Zumelzu, Lillo Estado del Arte del Job Shop Scheduling Problem Departamento de Informática, Universidad Técnica Federico Santa María Valparaíso, Chile. 2006.

De Castro y Von Zuben. “Artificial immune systems: Part I – Basic theory and applications”, Technical Report – RT DCA 01/1999, p. 95.

De Castro y Von Zuben. "Artificial Immune Systems: Part II – A Survey of Applications", Technical Report – RT DCA 02/2000, p. 65.

Martí Rafael. Métodos de resolución heurísticos para problemas aplicados de optimización, Universidad de Valencia. 2007.

Víctor Pena y Lillo Zumelzu, Estado del Arte del Job Shop Scheduling Problem. Universidad Técnica Federico Santa María Valparaíso, Chile 2007.

C. Coello Coello, D. Cortez-Rivera, N. Cruz Cortez, Use of an artificial immune system for job shop scheduling, in: Artificial Immune Systems: Proceedings of ICARIS 2003, Springer, 2003, pp. 1–10.

M. Dorigo, Optimization, Learning and Natural Algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, [in Italian], 1992.

Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. C. Blum and A. Roli. Technical report TR/IRIDIA/2001-13, IRIDIA, Université Libre de Bruxelles,Belgium

Sergio Alonso, Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera (Universidad de Granada, España). La Metaheurística de Optimización Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques. Trabajo realizado en el marco del proyecto Mejora de Metaheurísticas mediante Hibridación y sus Aplicaciones, de la Universidad de Granada, España. 2004. Bibliografía INVESTIGACIÓN M. Dorigo, Optimization, Learning and Natural Algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, [in Italian], 1992. Procedimiento ACO Metaheurística Comb(24)(1) = (24!)= 6.2*〖10〗^23 posibles soluciones; 14* 〖10〗^9 * 365.25 *24 *60 *60 = 4.41 * 〖10〗^17 seg
4.41*10〗^23 µseg. Alan Manne en 1960 Se compone de un conjunto de restricciones lineales y una función objetivo lineal Funcion Objetivo Minimizar el Flujo de Trabajo Maximo Los trabajos pueden iniciar en cualquier instante de tiempo Restricción Inicio Restricción Precedencia Restricciones Disyuntivas Una Operación no podra ser iniciada hasta no finalizar su antecesora Ninguna maquina procesara mas de una operación Ninguna Operación podra ser procesada por mas de una maquina Peña, Víctor. Zumelzu, Lillo Estado del Arte del Job Shop Scheduling Problem Departamento de Informática, Universidad Técnica Federico Santa María Valparaíso, Chile. 2006. DEFINICIÓN MATEMATICA DEL PROBLEMA DE PLANIFICACIÓN DE TRABAJOS
Full transcript