aumentar disminuir original

Metaheurísticas

DOCENTE

Cristian Martínez. Doctor en Ciencias de la Computación, UBA. Profesor Adjunto “Algoritmos y Estructuras de Datos” y Jefe de Trabajos Prácticos “Investigación Operativa”, Carrera Licenciatura en Análisis de Sistemas, U.N.Sa. Autor de publicaciones. Investigador. Docente de posgrado

DESTINATARIOS

Graduados de carreras de informática y profesionales interesados en la temática.

REQUISITOS

Título universitario o de nivel superior de cuatro años de duración como mínimo, en carreras afines.
Conocimientos sobre Programación, Métodos Numéricos y Estadística.

FUNDAMENTACIÓN

Muchos problemas de decisión existentes en el mundo real, en particular aquellos relacionados con la producción, ruteo de vehículos, logística, planificación, entre otros, pueden ser formulados como problemas de optimización. En este curso, nos centraremos en los de optimización combinatoria, los cuales son una clase dentro de los problemas de optimización. En éstos, las soluciones a los mismos se codifican usando variables discretas, y el proceso de búsqueda de soluciones consiste en explorar el espacio de soluciones (del problema) representado mediante listas, conjuntos, matrices o grafos. Considerando las soluciones alcanzadas sobre diferentes problemas reales y el avance en el estudio teórico-práctico en diferentes áreas dentro de la Investigación de Operaciones, la Optimización Combinatoria ha logrado un creciente interés motivado por los logros alcanzados.

El Curso se centrará en el estudio de problemas de tipo NP-Hard, para los cuales no se conocen técnicas que resuelvan de manera exacta, cualquier instancia de los mismos en tiempo polinomial. Sobre estos problemas, se aplicarán diferentes metaheurísticas. Definidas como técnicas generales usadas para guiar o controlar un método heurístico y específico del problema, con el objetivo de mejorar el rendimiento o robustez de los métodos subordinados, las mismas han sido aplicadas a diferentes problemas de optimización, gracias a su versatilidad para adaptarse a nuevos problemas, como también su sencillez de implementación, calidad de las soluciones logradas y bajo esfuerzo computacional asociado.

La versatilidad de las metaheurísticas para adaptarse a nuevos problemas de optimización y su sencillez de implementación, las convierten en una herramienta valiosa para el desarrollo de sistemas de información inteligentes.

OBJETIVOS

Objetivo General

  • Adquirir conocimientos teóricos y prácticos sólidos sobre metaheurísticas.

Objetivos Específicos

  • Modelar problemas lineales.
  • Introducir conceptos de algoritmos clásicos para problemas lineales.
  • Analizar problemas de optimización clásicos.
  • Revisar aspectos teóricos de las metaheurísticas.
  • Implementar algoritmos basados en metaheurísticas.
  • Manejar bibliografía actualizada y específica de metaheurísticas y sus aplicaciones.

PROGRAMA

Programación Lineal
Modelización de problemas lineales
Algoritmos exactos
Metaheurísticas:

  • Estado del Arte
  • Tabu Search
  • Variable Neighborhood Search (VNS)
  • Greedy Randomized Adaptive Procedure (GRASP)
  • Honey-bee Mating Optimization (HBMO)
  • Ant Colony Optimization (ACO)
  • Otras

Aplicaciones:

  • Set Covering Problem (SCP)
  • Clustering Problem
  • Travelling Salesman Problem (TSP)
  • School Bus Routing Problem (SBRP)
  • Otras

Práctica en laboratorio

BIBLIOGRAFÍA

  • Abbass, H. A. MBO: Marriage in honey bees optimization: A haplometrosis polygynous swarming approach. Congress on Evolutionary Computation (2001), 207-214.
  • Dorigo, M., and Stützle, T. Ant Colony Optimization. MIT Press, Massachusetts, 2004
  • Feo, T., and Resende, M. Greedy randomized adaptive search procedure. Journal of Global Computing 6 (1995), 109-133.
  • Garey, M., and Johnson, D. Computers and Intractability: a guide to the theory of NP-Completeness. H. Freeman and Company, New York, 1979.
  • Glover, F., and Laguna, M. Tabu Search. Kluwer Academic Publishers, Boston, 1997.
  • Gonçalves, J., and Resende, M. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics published Online (2010).
  • Hansen, P., and Mladenovic, N. Variable Neighborhood Search. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds., vol. 57 of Operations Research and Management Science. Kluwer Academic Publishers, 2003, 145-184.
  • Lourenço, H., and Serra, D. Adaptive search heuristics for the generalized assignment problem. Matware and Soft Computing 7 (2000), 1-15.
  • Mills, P., Tsang, E., Zhang, Q., and Ford, J. A survey of AI-based metaheuristics for dealing with local optima in local search. Technical Report Series CSM-416, University of Essex, Department of Computer Science, 2004.
  • Voss, S. Meta-heuristics: The state of the art. Local Search for Planning and Scheduling 2148 (2001), 1-23.
  • Wolsey, L. Integer Programming. Wiley-Interscience, New York, 1998.

CARGA HORARIA

30 horas teóricas y prácticas en Laboratorio.

CRONOGRAMA DE ACTIVIDADES

Fecha de inicio: lunes 5 de septiembre
Cinco clases, los días 5, 6, 7, 8 y 9 de septiembre de 14 a 20 H.
Sede: Junín

MODALIDAD DE EVALUACIÓN

Para aprobar el curso, los asistentes deben presentar un trabajo final de aplicación, el cual podrá realizarse en forma grupal (máximo de 2 personas).
Puede consistir en la modelización de un problema de optimización o en la implementación de un algoritmo basado en metaheurísticas (a definir con el Docente Responsable). En el primer caso, el problema debe ser de interés y deben disponerse de varias instancias para las cuales se obtendrán las soluciones exactas mediante uso de software específico (CPLEX, GLPK, etc.). El segundo caso, consiste en la implementación de un algoritmo (Python, Java) para un problema de optimización que alcance soluciones de calidad a bajo tiempo computacional.

INFORMES

Por mail a: cursosposgrado@unnoba.edu.ar
Teléfonos: 0236-4407750 (interno 12500/12502) – Sede Junín | 02477-409500 (interno 21201) – Sede Pergamino