Guía docente de Metaheurísticas (496113E)

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.

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

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.

Tema 1: Introducción a las metaheurísticas

• Complejidad de los problemas.
• Algoritmos aproximados.
• Concepto de metaheurística.

Tema 2: Optimización y Búsqueda en Inteligencia Artificial.

• Modelos de optimización en Inteligencia artificial
• Búsqueda por Entornos.
• Trayectorias versus 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 los algoritmos basados en trayectorias múltiples.
• Algoritmos basados en trayectorias múltiples: GRASP e ILS.

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, paralelización.

• Diversidad versus convergencia.
• Modelos evolutivos con componentes de equilibrio de diversidad y convergencia
• Múltiples soluciones: algoritmos basados en nichos.
• Nuevos algoritmos basados en la naturaleza y bioinspirados.
• Metaheurísticas paralelas.

Tema 8: Aprendizaje Evolutivo: Problemas y modelos

• Aprendizaje como problema de optimización.
• Modelos de aprendizaje basado en metaheurísticas.
• Aprendizaje evolutivo de reglas.
• Aprendizaje evolutivo de parámetros y modelos

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.

• E. Alba (ed.), “Parallel Metaheuristics”, John Wiley & Sons, 2005.
• P.M. Pardalos, M.G.C. Resende, “Handbook of Applied Optimization”, Oxford University Press, 2002.
• M. Dorigo, T. Stützle, “Ant Colony Optimization”. The MIT Press, 2004.
• A.E. Eiben, J.E. Smith, “Introduction to Evolutionary Computing”. Springer, Second edition, 2015.
• K-L Du, M.N.S. Swarry, Search and Optimization by Metaheuristics. Springer, 2016.
• B. Chopard, M. Tomassini, An Introduction to Metaheuristics for Optimization. Springer, 2018.

• El-Ghazali Talbi, “Metaheuristics: From Design to Implementation”, Wiley, 2009,

• Metaheurística. Wikipedia
• Computación evolutiva. Wikipedia
• Graduate Courses: E.T.S.I.I.T.
• Particle Swarm Optimization

• 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. 

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 resolviendo los problemas planteados con implementaciones algorítmicas.
• 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 las siguientes ponderaciones:

• Para la parte teórica se realizarán exámenes finales o parciales y/o 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 asociados al uso de los algoritmos para los problemas de prácticas, 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-

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.

Es un examen de preguntas múltiples para que se garantice que el estudiantado ha adquirido la totalidad de las competencias descritas en la presente guía docente, tanto de la parte teórica como práctica.

Para aprobar la asignatura es necesario tener una calificación numérica superior o igual a 5 (sobre 10).

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.

Es un examen de preguntas múltiples para que se garantice que el estudiantado ha adquirido la totalidad de las competencias descritas en la presente guía docente, tanto de la parte teórica como práctica.

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, tanto de la parte teórica como práctica.

Para aprobar la asignatura es necesario tener una calificación numérica superior o igual a 5 (sobre 10).