Guía docente de la asignatura

Metaheurísticas

Curso 2021 / 2022
Fecha última actualización: 21/06/2021
Fecha de aprobación: 21/06/2021

Grado

Grado en Ingeniería Informática (Ceuta)

Rama

Ingeniería y Arquitectura

Módulo

Optativas Otras Especialidades

Materia

Modelos de Computación

Curso

4

Semestre

2

Créditos

6

Tipo

Optativa

Profesorado

Teoría

  • Salvador Gutierrez Salcedo. Grupos: A

Tutorías

Salvador Gutierrez Salcedo

salvaguti@ugr.es
  • Primer semestre
    • Lunes de 15:30 a 17:30 (Ceuta)
    • Martes de 10:00 a 14:00 (Ceuta)
  • Segundo semestre
    • Martes de 10:00 a 13:00 (Ceuta)
    • Miércoles de 10:00 a 13:00 (Ceuta)

Prerrequisitos y/o Recomendaciones

Los alumnos no tendrán que tener asignaturas, materias o módulos aprobados como requisito indispensable para cursar el módulo. No obstante se recomienda la superación de los contenidos y habilidades de programación.

Breve descripción de contenidos (Según memoria de verificación del Grado)

  • Algoritmos avanzados de optimización y búsqueda.
  • Técnicas de diseño de algoritmos basados en trayectorias y poblaciones.
  • Metaheurísticas paralelas.

Competencias asociadas a materia/asignatura

Competencias generales

  • CG08 - Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
  • CG09 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.

Resultados de aprendizaje (Objetivos)

Objetivos formativos particulares:

  • Identificar las distintas clases (en términos de complejidad computacional) de problemas de optimización y búsqueda.
  • Comprender la conveniencia de soluciones aproximadas para problemas complejos.
  • Comprender el concepto de metaheurística. Identificar las componentes y propiedades más relevantes de una metaheurística.
  • Conocer la búsqueda local. Saber cómo aplicarla en la resolución de problemas de optimización y búsqueda. Identificar sus principales inconvenientes.
  • Conocer los principales mecanismos para solventar o paliar los inconvenientes de la búsqueda local.
  • Conocer las principales formas de representación de soluciones para problemas de búsqueda: binario, permutaciones, real.
  • Conocer las principales metaheurísticas basadas en trayectorias. En particular, enfriamiento simulado y búsqueda tabú. Conocer bien sus componentes y cómo aplicarlas a un problema dado.
  • Conocer las principales metaheurísticas basadas en poblaciones. En particular Algoritmos Genéticos. Conocer bien sus componentes y cómo aplicarlos a un problema dado.
  • Conocer las ventajas que los sistemas paralelos y/o distribuidos ofrecen en la resolución de problemas de optimización y búsqueda. Saber explotar la estructuración espacial frente a la temporal.
  • Dado un problema, identificar sus principales características y tener la madurez para decidir qué tipo de metaheurística es la más adecuada para su resolución.
  • Conocer las distintas técnicas con la suficiente pericia para encontrar las soluciones de la mejor calidad con restricciones de tiempo.

Objetivos formativos de carácter general (competencias según BOE de 4 de agosto de 2009)

  • Ser capaz de evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

Programa de contenidos teóricos y prácticos

Teórico

  • Tema 1: Introducción a las metaheurísticas
    • Complejidad de los problemas.
    • Algoritmos aproximados.
    • Concepto de metaheurística.
  • Tema 2: Modelos de Búsqueda
    • Búsqueda por Entornos.
    • Trayectorias vs Poblaciones.
  • Tema 3: Metaheurísticas basadas en poblaciones
    • Concepto y elementos de los algoritmos basados en poblaciones.
    • Algoritmos genéticos y programación genética.
    • Evolución diferencial y otros algoritmos de optimización continua.
    • Aplicación a problemas.
  • Tema 4: Algoritmos Meméticos
    • Hibridación de metaheurísticas.
    • Algoritmos meméticos.
  • Tema 5: Metaheurísticas basadas en trayectorias
    • Búsqueda local. Inconvenientes: Convergencia a óptimos locales.
    • Concepto y elementos de los algoritmos basados en trayectorias simples.
    • Concepto y elementos del enfriamiento simulado. Aplicación a problemas.
    • Concepto y elementos de la búsqueda tabú. Aplicación a problemas.
    • Concepto y elementos de los algoritmos basados en trayectorias múltiples.
    • Algoritmos basados en trayectorias múltiples: GRASP, ILS y VNS.
  • Tema 6: Metaheurísticas basadas en adaptación social
    • Introducción a la adaptación social.
    • Cooperación de agentes en problemas de optimización.
    • Algoritmos basados en colonias de hormigas.
    • Algoritmos basados en nubes de partículas.
    • Aplicación a problemas.
  • Tema 7: Aspectos Avanzados en Metaheurísticas
    • Diversidad versus convergencia.
    • Múltiples soluciones: algoritmos basados en nichos.
    • Nuevos algoritmos basados en la naturaleza y bioinspirados.
  • Tema 8: Metaheurísticas paralelas
    • Objetivos de la paralelización.
    • Enfoques de paralelización.
    • Taxonomía de metaheurísticas paralelas.
  • Tema 9: Aprendizaje Evolutivo
    • Aprendizaje como problema de optimización.
    • Modelos de aprendizaje basado en metaheurísticas.
    • Aprendizaje evolutivo de reglas.

Práctico

  • Prácticas en laboratorio de ordenadores:
    • P1. Resolución de problemas con técnicas de búsqueda local.
    • P2. Resolución de problemas con metaheurísticas basadas en poblaciones: algoritmos genéticos y algoritmos meméticos.
    • P3. Resolución de problemas con metaheurísticas basadas en trayectorias: enfriamiento simulado, búsqueda multiarranque básica, ILS, GRASP e ILS híbrida.
  • Prácticas en pizarra:
    • Resolución de problemas clásicos de optimización mediante metaheurísticas.
    • Resolución de problemas clásicos de optimización con restricciones mediante metaheurísticas.
  • Seminarios
    • S1. Ejemplos de resolución de problemas con metaheurísticas: problemas clásicos y reales. Software de metaheurísticas.
    • S2. Problemas de optimización con metaheurísticas basadas en búsqueda local.
    • S3. Problemas de optimización con metaheurísticas basadas en poblaciones.
    • S4. Problemas de optimización con técnicas basadas en trayectorias simples y  múltiples.
    • S5. Manejo de restricciones en metaheurísticas.
    • S6. Metaheurísticas Multi-objetivo.

 

Bibliografía

Bibliografía fundamental

  • E. Alba (ed.), “Parallel Metaheuristics”, John Wiley & Sons, 2005.
  • F. Glover, G.A. Kochenberger (eds.) “Handbook of Metaheuristics”, Kluwer Academic Press, 2003.
  • Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs”, Springer-Verlag, 1996.
  • P.M. Pardalos, M.G.C. Resende, “Handbook of Applied Optimization”, Oxford University Press, 2002.
  • C. R. Reeves, “Modern Heuristic Techniques for Combinatorial Problems”, Blackwell Scientific Pub., 1993
  • M. Dorigo, T. Stützle, “Ant Colony Optimization”. The MIT Press, 2004.
  • A.E. Eiben, J.E. Smith, “Introduction to Evolutionary Computing”. Springer, 2003.
  • M. Laguna, R. Martí, “Scatter Search”, Springer, 2003.

Bibliografía complementaria

  • D. Corne, M. Dorigo, F. Glover (Eds.), “New Ideas in Optimization”, McGraw-Hill, 1999.
  • H.H. Hoos, T. Stützle, “Stochastic Local Search”, Morgan Kaufmann, 2004.
  • J.M. Moreno Vega, J.A. Moreno Pérez, “Heurísticas en Optimización”, Consejería de Educación, Cultura y Deportes, Gobierno de Canarias, 1999.

Metodología docente

  • MD01 Lección Magistral (Clases Teóricas-Expositivas) 
  • MD02 Actividades Prácticas (Resolución de Problemas, Resolución de Casos Prácticos, Desarrollo de Proyectos, Prácticas en Laboratorio, Taller de Programación, Aula de Informática, Prácticas de Campo). 
  • MD03  Seminarios (Debates, Demos, Exposición de Trabajos Tutelados, Conferencias, Visitas Guiadas, Monografías). 
  • MD04 Actividades no presenciales Individuales. 
  • MD05 Actividades no presenciales Grupales. 
  • MD06 Tutorías Académicas. 

Evaluación (instrumentos de evaluación, criterios de evaluación y porcentaje sobre la calificación final)

Evaluación ordinaria

Con objeto de evaluar la adquisición de los contenidos y competencias a desarrollar en la asignatura, se utilizará un sistema de evaluación diversificado, seleccionando las técnicas de evaluación más adecuadas en cada momento, que permita poner de manifiesto los diferentes conocimientos y capacidades adquiridos por el alumnado. De entre las técnicas evaluativas a aplicar se utilizarán alguna o algunas de las siguientes:

  • Pruebas escritas: exámenes de desarrollo, exámenes de tipo test, resolución de problemas, casos o supuestos, pruebas de respuesta breve, informes y diarios de clase, trabajos periódicos escritos.
  • Pruebas orales: exposición oral de trabajos en clase, individuales o en grupo, sobre contenidos de la asignatura (seminario) y sobre ejecución de tareas prácticas correspondientes a competencias concretas.
  • Pruebas en los laboratorios de prácticas: elaboración y defensa de supuestos prácticos en el laboratorio de informática.
  • Técnicas basadas en la asistencia y participación activa del alumno en clase, seminarios, tutorías y en el desarrollo y defensa de los trabajos en grupo.

El sistema de calificaciones se expresará mediante calificación numérica de acuerdo con lo establecido en el art. 5 del R.D. 1125/2003, de 5 de septiembre, por el que se establece el sistema europeo de créditos y el sistema de calificaciones en las titulaciones universitarias de carácter oficial y validez en el territorio nacional. Todo lo relativo a la evaluación se regirá por la normativa vigente de la Universidad de Granada./

Se utilizarán las siguientes técnicas de evaluación con la siguientes ponderaciones:

  • Para la parte teórica se realizarán exámenes finales o parciales y entregas de ejercicios sobre el desarrollo y los resultados de las actividades propuestas. La ponderación de este bloque será del 50%.
  • Para la parte práctica se realizarán prácticas de laboratorio, resolución de problemas y desarrollo de proyectos (individuales o en grupo), y se valorarán las entregas de los informes/memorias realizados por los alumnos. La ponderación de este bloque será de 50%.

La calificación global corresponderá por tanto a la puntuación ponderada de los diferentes aspectos y actividades que integran el sistema de evaluación. El resultado de la evaluación será una calificación numérica obtenida mediante la suma ponderada de las calificaciones correspondientes a una parte teórica y una parte práctica.

La asignatura se evalúa con una ponderación de un 50% la nota de teoría y un 50% la nota de prácticas. Para los alumnos que elijan participar en la evaluación continua tendrán entregas de prácticas para optar a los 5 puntos de prácticas mientras que los 5 puntos de teoría se podrán obtener en el examen final. Para poder superar la asignatura será necesario obtener una nota final igual o superior a 5 puntos, habiendo obtenido al menos 1 punto en cada parte, teoría y prácticas

Evaluación extraordinaria

En el examen extraordinario (evaluado de 0 a 10) tanto la parte teórica como práctica será incluida en un único examen que incluirá cuestiones de índole teóricas y problemas de índole práctica.

Evaluación única final

De acuerdo a lo establecido en la Normativa de evaluación y de calificación de los estudiantes de la Universidad de Granada aprobada en Consejo de Gobierno de 20 de mayo de 2013 (NCG71/2), la evaluación será preferentemente continua. No obstante, el estudiante que no pueda acogerse a dicho sistema por motivos laborales, estado de salud, discapacidad o cualquier otra causa debidamente justificada podrá acogerse a la evaluación única final. Para ello deberá solicitarlo al Director del Departamento en las dos primeras semanas de impartición de la asignatura o, excepcionalmente, en las dos primeras semanas tras la matriculación en la asignatura (NCG78/9: Instrucción relativa a la aplicación del artículo 8.2).

La evaluación única final se realizará en un solo acto académico el día de la convocatoria oficial de examen para la asignatura. La prueba será evaluada de 0 a 10 e incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en la presente guía docente.

Información adicional

ESCENARIO A (ENSEÑANZA-APRENDIZAJE PRESENCIAL Y TELE-PRESENCIAL)

Horario (Según lo establecido en el POD)

Los horarios de tutorías del profesorado pueden consultarse en la web: http://decsai.ugr.es/index.php?p=profesores

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

En un escenario de presencialidad reducida, salvo excepciones, se atenderán las tutorías por videoconferencia (GoogleMeet de la cuenta GO de la UGR) o correo electrónico oficial. Las tutorías individuales tendrán lugar previa petición del estudiante. El profesor podrá proponer tutorías grupales, obligatorias u optativas, si lo estima oportuno como herramienta de retorno formativo en caso de que hubiera que impartir clases virtuales en modo asíncrono. Las dudas ser esponderán de forma continua tanto por el profesor como también de forma cooperativa por los estudiantes a través de los foros dispuestos en el espacio de la asignatura en PRADO.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

Si fuera necesario, se aplicarán las siguientes adaptaciones:

  • Las clases virtuales se impartirían utilizando la plataforma Google Meet o las que la UGR dictara en su momento. Se primaría la impartición síncrona, aunque las circunstancias sanitarias (enfermedad del profesor o familiar, conciliación familiar,...) podrían imponer un escenario asíncrono, en cuyo caso se grabarían las clases presenciales, que serían compartidas por Google Drive,y se complementarían con las actuaciones de seguimiento y retorno formativo ya planificadas (tutorías, uso de los foros, seguimiento y entrega de los proyectos,etc.).
  • Dado que las sesiones prácticas se desarrollan habitualmente con el portátil del estudiante, se podrían impartir y desarrollar tanto de forma presencial como virtual sin problema.
  • Se valorará la dedicación de la lección presencial realizada a distancia aplicando una metodología de clase invertida en la que el profesor pondría a disposición del estudiantado y antes de la celebración de la clase síncrona una serie de vídeos de una duración razonable con los conocimientos más importantes. En ese caso, los estudiantes visualizarían los vídeos con antelación y se utilizaría laclase para aclarar dudas y discutir sobre los conceptos.
  • Las plataformas mencionadas(PRADO, Google Meet) así como el resto de herramientas de comunicación con los estudiantes como Consigna UGR, Google Drive a través de cuenta @go.ugr, el correo institucional,etc.son las actualmente autorizadas por la UGR. Podrían verse modificadas si las instrucciones de la UGR al respecto cambiasen durante el curso.

Evaluación ordinaria

La asignatura se evalúa con una ponderación de un 50% la nota de teoría y un 50% la nota de prácticas. Para los alumnos que elijan participar en la evaluación continua tendrán entregas de prácticas para optar a los 5 puntos de prácticas mientras que los 5 puntos de teoría se podrán obtener en el examen final. Para poder superar la asignatura será necesario obtener una nota final igual o superior a 5 puntos, habiendo obtenido al menos 1 punto en cada parte, teoría y prácticas.

Dado el sistema de evaluación considerado, no es necesario ningún cambio con la única salvedad que, si no fuera posible celebrar la defensa de los proyectos o los exámenes de forma presencial, se realizaría a distancia y de forma síncrona haciendo uso de Google Meet o de la herramienta de videoconferencia habilitada por la UGR.

Se planteará una evaluación alternativa al examen basada en realizar una práctica asociada a un algoritmo bioinspirado de una lista proporcionada. Dicha evaluación alternativa constará de un problema a resolver y se debería implementar y analizar los algoritmos para este problema, siguiendo las instrucciones de los documentos que se proporcionarán para ello.

Criterios de evaluación: Se atenderá a la implementación de los algoritmos, la descripción de los mismos, y el análisis práctico de los resultados.

Porcentaje sobre calificación final: Cada parte (teoría y prácticas) estará planteada sobre 5 puntos. Y se sumará la calificación de cada una de ellas.

Evaluación extraordinaria

En el examen extraordinario (evaluado de 0 a 10) tanto la parte teórica como práctica será incluida en un único examen que incluirá cuestiones de índole teóricas y problemas de índole práctica.

Si no fuera posible realizar el examen de forma presencial, se realizaría a distancia, o se plantearía una evaluación similar a la de la convocatoria ordinaria. Los documentos asociados a las prácticas extraordinarias estarán disponibles al día siguiente de la entrega de las prácticas asociadas a la convocatoria ordinaria, y se fijará una fecha de entrega de acuerdo a la programada para el examen extraordinario de la asignatura.

Evaluación única final

La evaluación única final se realizará en un solo acto académico el día de la convocatoria oficial de examen para la asignatura. La prueba será evaluada de 0 a 10 e incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en la presente guía docente.

ESCENARIO B (SUSPENSIÓN DE LA ACTIVIDAD PRESENCIAL)

Horario (Según lo establecido en el POD)

Los horarios de tutorías del profesorado pueden consultarse en la web: http://decsai.ugr.es/index.php?p=profesores

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

Enun escenario de suspensión de la actividad presencial, salvo excepciones, se atenderán las tutorías por videoconferencia (GoogleMeet de la cuenta GO de la UGR) o correo electrónico oficial. Las tutorías individuales tendrán lugar previa petición del estudiante. El profesor podrá proponer tutorías grupales, obligatorias u optativas, si lo estima oportuno como herramienta de retorno formativo en caso de que hubiera que impartir clases virtuales en modo asíncrono. Las dudas se responderán de forma continua tanto por el profesor como también de forma cooperativa por los estudiantes a través de los foros dispuestos en el espacio de la asignatura en PRADO.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

Dado el modelo flexible de impartición de la asignatura, la adaptación a un escenario de docencia a distancia es sencilla. En concreto, se aplicarían las siguientes adaptaciones:

  • Todas las clases serían virtuales. Se impartirían utilizando la plataforma Google Meet o las que dictara la UGR en su momento. Se primará la impartición síncrona, aunque las circunstancias sanitarias (enfermedad del profesor o familiar, conciliación familiar,...) podrían imponer un escenario asíncrono, en cuyo caso se grabarían las clases presenciales, que serían compartidas por Google drive y se complementarían con actuaciones de seguimiento y retorno formativo específicas para ese fin (tutorías, tareas, entregas,...).
  • Se puede proporcionar al estudiantado vídeos de apoyo de los temas impartidos de forma no presencial. En la mayoría de los casos serían vídeos resumidos, diseñados expresamente, con los contenidos más importantes del tema y soportados también con presentaciones por transparencias en el propio vídeo. En algunos casos, serían grabaciones directas de las clases impartidas por videoconferencia.
  • Si fuera necesario, se reduciría la importancia de la lección presencial realizada a distancia aplicando una metodología de clase invertida en la que el profesor pondría a disposición del estudiantado, y antes  de  la celebración de la clase síncrona, una serie de vídeos de una duración razonable con los conocimientos más importantes. En ese caso, los estudiantes visualizarían los vídeos con antelación y se utilizaría la clase síncrona para aclarar dudas y discutir sobre los conceptos.
  • El temario práctico no requeriría de ninguna adaptación ya que se usan herramientas de software libre, que el estudiantado tiene disponibles, para su realización.
  • Dado que las sesiones prácticas se desarrollan habitualmente con el portátil del estudiante, se impartirían y desarrollarían de forma virtual sin problema.
  • Las plataformas mencionadas (PRADO, Google Meet) así como el resto de herramientas de comunicación con los estudiantes como Consigna UGR, Google Drive a través de cuenta @go.ugr, el correo institucional, etc. son las actualmente autorizadas por la UGR. Podrían verse modificadas si las instrucciones de la UGR al respecto cambiasen durante el curso.

Evaluación ordinaria

La asignatura se evalúa con una ponderación de un 50% la nota de teoría y un 50% la nota de prácticas. Para los alumnos que elijan participar en la evaluación continua tendrán entregas de prácticas para optar a los 5 puntos de prácticas mientras que los 5 puntos de teoría se podrán obtener en el examen final. Para poder superar la asignatura será necesario obtener una nota final igual o superior a 5 puntos, habiendo obtenido al menos 1 punto en cada parte, teoría y prácticas

Para cada una de las dos partes, teoría y prácticas, se entregará una práctica asociada a los algoritmos discutidos en prácticas y a un algoritmo bioinspirado de una lista proporcionada. Se indicará un problema a resolver y se deben implementar y analizar los algoritmos para este problema, siguiendo las instrucciones de los documentos que se proporcionarán para ello, en la misma línea de los documentos de las prácticas de la convocatoria ordinaria. La entrega sería vía la plataforma PRADO.

Criterios de evaluación: Se atenderá a la implementación de los algoritmos, la descripción de los mismos, y el análisis práctico de los resultados.

Evaluación extraordinaria

En el examen extraordinario (evaluado de 0 a 10) tanto la parte teórica como práctica será incluida en un único examen que incluirá cuestiones de índole teóricas y problemas de índole práctica.

Si no fuera posible realizar el examen de forma presencial, se realizaría a distancia, o se plantearía una evaluación similar a la de la convocatoria ordinaria. Los documentos asociados a las prácticas extraordinarias estarán disponibles al día siguiente de la entrega de las prácticas asociadas a la convocatoria ordinaria, y se fijará una fecha de entrega de acuerdo a la programada para el examen extraordinario de la asignatura.

Evaluación única final

La evaluación única final se realizará en un solo acto académico el día de la convocatoria oficial de examen para la asignatura. La prueba será evaluada de 0 a 10 e incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en la presente guía docente.