METAHEURISTICAS


Materia optativa para la Licenciatura en Ciencias de la Computación y para el Doctorado en Ciencias de la Computación. Abierta a alumnos de grado y posgrado de otras carreras.


Profesora : Dra. Irene Loiseau, irene@dc.uba.ar

Prerrequisitos: es conveniente haber cursado Algoritmos III. En caso de no tener esta materia o ser alumno de otra carrera, comunicarse con la profesora, para determinar si se puede cursar.

Puntaje para la Lic. en Ciencias de la Computación: 3 puntos

Puntaje para el doctorado en Computación: 3 puntos

Puntaje para otras carreras: consultar en sus respectivos departamentos

Carga horaria: 3 horas semanales de clase teórica, 1 hora semanal de práctica/consulta

Horario clases: Martes 17 y 30 a 20 y 30hrs. El martes 15/8 las 18hrs habrá una clase de presentación de la materia en el LABO 6.

Forma de dictado de la materia: La materia tendrá clases teóricas donde se presentarán las principales metaheurísticas y ejemplos de aplicaciones. En la última parte del curso los alumnos de doctorado deberán hacer una presentación de algún trabajo que describa una aplicación de alguna de las metaheurísticas.

Evaluación: Los alumnos tendrán que realizar un trabajo que podrá ser una implementación de la solución de algún problema usando este tipo de algoritmos o una revisión de la literatura referente a alguna de las técnicas metaheurísticas presentadas y sus aplicaciones.

Observación: En el sistema de inscripción la materia figura como METAHEURISTICAS 2014 para los alumnos de licenciatura


******************************************************************************************************************

PROGRAMA:

Hay una gran cantidad de situaciones y problemas de la industria, los servicios y la ciencia que pueden formularse como problemas de optimización. Por ejemplo puede ser necesario minimizar tiempos, costos o riesgos, o maximizar beneficios, calidad o eficiencia. Una gran cantidad de los problemas de optimización se presentan en ingeniería, ciencias, economía, etc. son muy difíciles de resolver. No se puede esperar que sea posible resolverlos en forma exacta en un tiempo razonable.

En estos casos la alternativa es recurrir a algoritmos heurísticos que proveen "buenas soluciones", útiles en la práctica, en tiempos compatibles con la necesidad de tener implementadas las respuestas. Estos algoritmos pueden ser heurísticas específicas , diseñadas para un problema en particular o metaheurísticas. Las técnicas metaheurísticas, también llamadas sistemas inteligentes por autores que vienen del área de Inteligencia Artificial, consisten en sistematizar ideas para desarrollar algoritmos eficientes que encuentran "buenas soluciones" a problemas de optimización de gran importancia práctica, que en la mayoía de los casos son NP-hard. También son de utilidad cuando se desean resolver problemas cuyo modelo matemático no puede ser formulado facilmente. Estos métodos combinan la simplicidad de sus ideas con su gran eficiencia para obtener muy buenas soluciones para problemas díficiles y son relativamente fáciles de diseñar e implementar.

Las primeras metaheurísticas se presentaron a comienzos de la década de los 80. Algunas de sus ideas son más antiguas, pero no eran fácilmente traducibles en algoritmos útiles, si no se contaba con un potencial de cálculo como el actual. A partir de ese momento se propusieron muchas y diversas ideas para para diseñar algoritmos heurísticos.

En la mayoría de los casos estos métodos están basados en imitar situaciones o comportamientos que aparece en la fisica, la biología o la genética, el sistema nervioso, el comportammiento de poblaciones, etc.

En la actualidad es un área muy activa desde el punto de vista de las aplicaciones y de la investigación. Hay revistas y congresos dedicadas específicamente a Metaheurísticas. Al mismo tiempo estos trabajos dan lugar al desarrollo de muy exitosas herramientas computacionales usadas en la industria para resolver diversos problemas de logística, comunicaciones, planificación de la producción y otros problemas de optimización. También forman parte importantes de las herramientas para resolver problemas de otras ciencias, como por ejemplo es el caso de la bioinformática.

Durante el curso:

1- Se presentará la idea general de qué es una metaheurística, y cuándo es conveniente usar este tipo de enfoque para resolver un problema. Se definirá que es un problema de Optimización Combinatoria y como modelarlo.

Se presentán conceptos básicos comunes a todos los métodos: representación de una solución, de la función objetivo y de las restricciones del problema, manejo de parámetros, análisis de la calidad de las soluciones, etc.

2- Se presentarán las ideas básicas de las siguientes técnicas:

  • Simulating annealing
  • Tabu Search
  • GRASP
  • Variable Neighborhood Search
  • Iterated Local Search
  • Algoritmos genéticos y evolutivos.
  • BRKGA (biased random keys genetic algorithms).
  • Scatter Search and Path Relinking
  • Colonias de hormigas
  • Honey-bee mating optimization
  • Particle Swarm Optimization
  • Sistemas Inmunes Artificiales
  • Híbridos.

3- De acuerdo al interés de los alumnos se presentarán aplicaciones a varias de las numerosas áreas en las cuales cada una de estas técnicas han demostrado su utilidad. Estas incluyen entre otras problemas de:

  • Ruteo de vehículos y distribución de mercadería

  • Planificación de la producción
  • Secuenciamiento de tareas
  • Asignación de personal y de tripulaciones en empresas de transporte aéreo o terrestre
  • Diseño de redes de comunicaciones y ruteo
  • Diseño de plaquetas y chips (VLSI)
  • Asignación de frecuencias en telefonía celular
  • Problemas de horarios en instituciones educativas
  • Análisis financiero
  • Problemas de control
  • Robótica
  • Diseño de torneos deportivos
  • Estrategias de juegos
  • Genómica y otros temas de bioinfomática
  • Data Mining

  • ******************************************************************************************************************

    BIBLIOGRAFÍA

    La bibiografía para estos temas es muy abundante. Sólo se consignan algunos libros que podrán servir de referencia para los distintos temas. Se seleccionarán de algunos de ellos los capítulos que sirvan de base para cada uno. Todos los libros estarán disponibles para los alumnos.

    Los libros de Gendreau & Potvin (ver 9 abajo) y de Talbi (26) presentan un panorama bastante completo y actualizado de la mayoría las técnicas metaheurísticas.

    1. Aarts,E.,Korst,J.,"Simulated Annealing and Boltzmann Machines", Wiley, 1989.
    2. Aarts,E.,Lenstra,J.,(eds),"Local Search in Combinatorial Optimization", Wiley, 1997.
    3. Alba,E.,"Parallel Metaheuristics:A New Class of Algorithms", Wiley, 2005.
    4. Bonabeu,E., Dorigo, M.,Theraulaz, G:, "Swarm Intrelligence; from natural to artificial systems", Oxford Univesity Press,1999.
    5. Blum, C., Roli,A., "Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison", ACM Computing Surveys, vol. 35,no 3, 2003, pp268-308.
    6. Corne, D., Dorigo,M., Glover,F.,(eds)"New ideas in Optimization", McGraw Hill, 1999.
    7. Davis,L.(ed),"Handbook of genetic algorithms", Reinhold, 1991.
    8. Dorigo, M and Stutzle., "Ant colony optimization",MIT Press, 2004.
    9. Gendreau,M., Potvin,J., "Handbook of Metaheuristics", Springer, 2010.
    10. Glover, F., De Werra, D., (eds), "Tabu search", Annals of Operations Research 41, Baltzer, 1993.
    11. Glover,F., Laguna,M., "Tabu Search", Kluwer Academic Pub., 1997.
    12. Glover,F., Kochenberger,G., "Handbook of Metaheuristics", Kluwer Academic Pub., 2003.
    13. Goldberg, D." Genetic Algorithms in Search, Optimization and Machine learning", Addison-Wesley, 1989.
    14. Haupt,R., Haupt,S., "Practical Genetic Algorithms", Willey, 1998.
    15. Hertz, A., "Les Méta-heuristiques: quelques conseils pour en faire bon usage", en "Gestion de Production e Ressources Humaines: méthodes de planification dans les systèms productifs", 2005, pp 205-222.
    16. Hertz,J., Krog,A., Palmer,R., "Introduction to the theory of neural computacion", Addison Wesley, 1991.
    17. Holland, J. "Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control and Artificial Inteligence", Bradford, 1992.
    18. Laporte, G., Osman,I., (eds), "Mateheuristics in Combinatorial Optimization", Annals of Operations Research 63, Baltzer, 1996.
    19. Michalewicz, Z.,"Genetic algorithms + Data Structures = Evolution programs", Springer Verlag, 1996.
    20. Mitchell,M.,"An introduction to genetic algorithms (complex adaptive systems)", MIT Press, 1996.
    21. Osman,I.H., Kelly,J.,(eds) "Metaheuristics: theory and applications", Kluwer Academic Pub., 1996.
    22. Pham,D.,Karaboga,D." Intelligent Optimization Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing, and Neural Networks", Springer Verlag, 1998.
    23. Rayward-Smith,V.J., Osman,I.H., Reeves,C.R., "Modern Heuristic Search Methods", Wiley, 1996.
    24. Reeves, C. (ed), "Modern heuristics techniques for combinatorial Problems", Blackwell,1993.
    25. Resende, M., Ribeiro, C., "Optimization by GRASP", Springer,2016.
    26. Talbi, E.G. "Metaheuristics:from design to implementation", Wiley, 2009.
    27. Van Laarhoven,P., Aarts,E. "Simulated Annealing: theory and applications", Kluwer, 1988.

    ******************************************************************************************************************

    Otros cursos y tutoriales de Metaheuristicas

      ******************************************************************************************************************

      Software

        ******************************************************************************************************************

        CLASES segundo cuatrimestre 2017

        Las clases de este cuatrimestre se irán agregando a medida que se dicten, junto con los principales trabajos comentados en las mismas

        ******************************************************************************************************************

        CLASES segundo cuatrimestre 2016

        A continuación van las clases y los trabajos presentados en el 2do cuatrimestre de 2016, que pueden servir para completar la información sobre la materia.