template-browser-not-supported

Grado en Ciencia e Ingeniería de Datos

Back Back

Búsqueda Inteligente y Metaheurísticas

Código asignatura
GCINGD01-2-009
Curso
Segundo
Temporalidad
Segundo Semestre
Carácter
Obligatoria
Créditos
6
Pertenece al itinerario Bilingüe
No
Actividades
  • Prácticas de Laboratorio (14 Hours)
  • Docencia On Line (30 Hours)
  • Clases Expositivas (16 Hours)
Guía docente

La asignatura de Búsqueda Inteligente y Metaheurísticas se encuadra en la materia de Análisis y visualización de datos. Se desarrolla en el segundo semestre del segundo curso del Grado, y tiene como objetivo introducir las técnicas de resolución de problemas complejos propias de la inteligencia artificial, como son la búsqueda heurística, las técnicas de razonamiento con restricciones y las metaheurísticas. Estas técnicas se utilizarán para resolver problemas de optimización con uno o varios objetivos. La asignatura de Búsqueda Inteligente y Metaheurísticas es básica para otras asignaturas del plan de estudios, en particular para la asignatura de Métodos Heurísticos de Planificación y Scheduling (optativa de tercer curso), y en general para las asignaturas de Aprendizaje Automático ya que muchos de los algoritmos de aprendizaje son en realidad variantes de los algoritmos de búsqueda heurística o metaheurísticas que se estudian en esta asignatura.

Para abordar esta asignatura con posibilidades de éxito, los alumnos deberán haber cursado con aprovechamiento otras asignaturas previas del plan de estudios en las que se proporcionan los conocimientos básicos de programación, diseño de algoritmos, estructuras de datos y teoría de grafos, necesarios para el modelado y programación de sistemas inteligentes de resolución de problemas. Las más relevantes de estas asignaturas son Metodología de la Programación, Estructuras Discretas y Análisis de Algoritmos, Algoritmia y Programación Avanzada. También es aconsejable haber cursado la asignatura Inferencia Estadística, en la que se explican conceptos para poder evaluar de forma estadística los resultados obtenidos por los métodos que se verán en esta asignatura.

Según la memoria de verificación, las competencias a alcanzar por los estudiantes en cuyo desarrollo colabora la asignatura de Búsqueda Inteligente y Metaheurísticas son las siguientes:

Competencias básicas

CB2:   Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio

CB3: Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética

CB4:  Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado

Competencias generales

CG1:   Elegir y aplicar los métodos y técnicas más adecuados para analizar y resolver problemas definidos por datos que representen un reto por su volumen, velocidad, variedad o heterogeneidad, incluidos métodos informáticos, matemáticos, estadísticos y de procesado de la señal.

CG2:  Tener las habilidades experimentales y analíticas para trabajar con autonomía siendo capaz de plantear experimentos y de describir, analizar, evaluar e interpretar la información resultante para proponer soluciones alternativas y novedosas frente a problemas conocidos y/o emergentes.

CG3:   Crear modelos y tomar decisiones basadas en los datos disponibles combinando los conocimientos adquiridos y siendo capaz de aplicar otros nuevos para la resolución de problemas.

CG4:  Capacidad de integrarse en un equipo multidisciplinar en el marco de un proyecto de ciencia de datos.

CG6:   Capacidad de acceso y gestión de la información en diferentes formatos para su posterior análisis con el fin de obtener conocimiento a partir de datos.

CG8:   Conocer y aplicar los aspectos éticos y legales relacionados con el tratamiento de los datos y la aplicación del conocimiento obtenido.

CG9:   Capacidad para expresar los resultados del procesamiento de datos de manera clara y convincente tanto por escrito como oralmente.

Competencias específicas

CE8:  Conocer las técnicas de optimización discreta y continua que se aplican en la ciencia e ingeniería de datos.

Resultados de aprendizaje

Los resultados de aprendizaje esperados relacionados con la asignatura son los siguientes:

RBUS1: Conocer el paradigma de búsqueda en espacios de estados y saber cómo utilizarlo para resolver problemas de optimización combinatoria. Saber cómo modelar espacios de búsqueda para problemas concretos y cómo incorporar conocimiento del dominio del problema en los algoritmos para mejorar su eficiencia.

RBUS2: Conocer los problemas de satisfacción de restricciones y optimización (CSOP). Saber cómo formular este tipo de problemas y cómo resolverlos utilizando técnicas de búsqueda e inferencia (propagación de restricciones).

RBUS3: Conocer las metaheurísticas y saber cómo utilizarlas para resolver problemas de optimización combinatoria y numérica, con una o varias funciones objetivo.

RBUS4: Saber cómo aplicar los métodos anteriores a problemas propios de la ciencia e ingeniería de datos, como por ejemplo el cálculo de árboles de decisión, los métodos de agrupamiento, el entrenamiento de redes neuronales, etc.

Tema 1. Búsqueda en Espacios de Estados

  1. Modelado de espacios de búsqueda
  2. Algoritmos de búsqueda no informada
  3. Algoritmos de búsqueda informada o heurística
  4. Técnicas de diseño de funciones heurísticas

Tema 2. Resolución de problemas de satisfacción de restricciones y optimización

  1. Formalización de problemas CSOP
  2. Resolución de CSOPs mediante búsqueda
  3. Técnicas de Inferencia. Propagación de restricciones

Tema 3. Metaheurísticas

  1. Introducción y clasificación de metaheurísticas
  2. Metaheurísticas bio-inspiradas basadas en poblaciones. Algoritmos Genéticos
  3. Metaheurísticas basadas en trayectorias. Búsqueda local y enfriamiento simulado

Tema 4. Optimización Multiobjetivo

  1. Clasificación. Optimización lexicográfica y optimización de Pareto
  2. Algoritmos evolutivos multiobjetivo

La asignatura se desarrollará en modalidad semipresencial, combinando actividades presenciales, actividades de formación online asíncrona y trabajo autónomo del estudiante.

Las actividades presenciales son aquellas en las que estará siempre presente el profesor. Se dividen en clases expositivas, prácticas de laboratorio y sesiones de evaluación.

  • Clases expositivas: Impartidas al grupo completo, no necesariamente como lección magistral, sino procurando una participación activa del alumno en la dinámica de las mismas. En estas clases se desarrollarán contenidos teóricos de la asignatura, combinados con alguna resolución de pequeños ejercicios. Se utilizará la pizarra y los diferentes medios audiovisuales.
  • Prácticas de Laboratorio: Dedicadas a resolver ejercicios y problemas, poniendo en práctica lo impartido en las clases expositivas.  Se desarrollarán en varios grupos, de manera eminentemente participativa.
  • Sesiones de evaluación: Se dedicarán a la realización de pruebas escritas o bien con un ordenador, con las que se pueda valorar de forma objetiva el nivel alcanzado por los estudiantes en la adquisición de algunas de las competencias previstas.

Las actividades de formación online asíncrona son aquellas en las que el profesor impartirá los contenidos utilizando distintos medios audiovisuales tales como vídeos, y otros materiales docentes, que quedarán a disposición del estudiantado para su estudio. Se dividen en clases expositivas y prácticas de laboratorio.

  • Clases expositivas: El contenido de cada hora lectiva se dividirá en el visionado de pequeños vídeos explicativos sobre conceptos de la materia, completados, en ocasiones, con lecturas recomendadas o el estudio de ejemplos resueltos. Se utilizarán distintos medios audiovisuales y repositorios institucionales de la Universidad de Oviedo.
  • Prácticas de Laboratorio: Se realizarán vídeos explicativos con la resolución de distintos problemas y se propondrán ejercicios y tareas para que los estudiantes los aborden por su cuenta en base a los contenidos de las clases expositivas presenciales y no presenciales.

Por su parte, a fin de cumplir los principios referentes a ECTS, establecidos en el Real Decreto 1393/2007, el estudiante deberá desarrollar un trabajo autónomo paralelo (actividades no presenciales), dirigido por el profesor. Este trabajo incluye el visionado de las clases online, aunque no se limita únicamente a ello.

La metodología docente que se empleará tratará de fomentar la participación activa del alumnado. Para ello se plantearán actividades y ejercicios que impliquen al alumno y propicien su participación, ya sea resolviendo tareas de manera autónoma o colaborativa en el aula. Se motivará al alumnado a preguntar las dudas que les surjan durante las clases online mediante e-mail, tutorías virtuales o durante el transcurso de las prácticas de laboratorio presenciales.

Asimismo, se realizarán, si a juicio de los profesores se estima conveniente, controles con objeto de conocer el grado de adquisición de las competencias más relacionadas con los contenidos de la asignatura.

Con respecto a las prácticas de laboratorio, tanto presenciales como online, podrían plantearse ejercicios para entregar al final de cada sesión de prácticas o bien al final de cada uno de los temas de la asignatura.

Se utilizarán metodologías docentes acordes con el tamaño de cada grupo.

A continuación, se presentan unas tablas que especifican la temporalidad de las actividades tanto presenciales como no presenciales:

Volumen de trabajo estimado para el estudiante

MODALIDADES

Horas

%

Presencial

Clases expositivas presenciales

14

9.3%

Prácticas de Laboratorio presenciales

14

9.3%

Sesiones de evaluación

2

1.3%

Total

30

20%

No presencial

Clases expositivas online

15

10.0%

Prácticas de Laboratorio online

15

10.0%

Estudio autónomo de teoría

30

20.0%

Resolución de Ejercicios de Forma Autónoma

20

13.3%

Estudio y preparación de prácticas de Laboratorio

40

26.6%

Total

120

80%

Total

150

100%

Distribución del trabajo por temas

Presencial

No presencial

Temas

Horas totales

Clase Expositiva

Prácticas de laboratorio /aula de  informática

Sesiones de Evaluación

Total

Clase Expositiva

Prácticas de laboratorio

Trabajo autónomo

Total

Presentación y funcionamiento general del curso

1

0

1

1

Búsqueda en espacios de estados

38

4

3

7

4

4

23

31

Resolución de problemas de satisfacción de restricciones y optimización

38

3

4

1

8

3

4

23

30

Metaheurísticas

55

5

5

10

5

5

35

45

Optimización multiobjetivo

18

2

2

1

5

2

2

9

13

Total

150

14

14

2

30

15

15

90

120

Evaluación en la convocatoria ordinaria

En la evaluación ordinaria se utilizarán diversos procedimientos presenciales y no presenciales que permitirán realizar el seguimiento del proceso de aprendizaje del alumno. Los diferentes procedimientos evaluadores serán los siguientes:

  • Asistencia y participación en seminarios o tutorías (presenciales u online) (5%)
  • Participación activa en foros y actividades del campus virtual (10%)
  • Informes/Memorias/Exámenes de prácticas (40%)
  • Exámenes de carácter teórico (45%)

La parte de prácticas (40%) se evaluará de forma continua. Habrá cuatro pruebas, una para cada uno de los temas de la asignatura. Estas pruebas serán de una de las dos siguientes modalidades: o bien mediante la entrega, y posterior defensa a requerimiento de los profesores, de un trabajo que deberán realizar en parte fuera de las horas de clase, o bien mediante la realización de una prueba presencial. Es necesario alcanzar una calificación mínima de 4 sobre 10 en la parte de prácticas.

La evaluación de teoría (45%) se llevará a cabo mediante evaluación continua consistente en la realización de dos controles al finalizar cada uno de los bloques (Tema1+Tema2, y Tema3+Tema4). Estos controles se llevarán a cabo en el aula tras la impartición de los contenidos fijados. También habrá un examen teórico final. Es necesario alcanzar una calificación mínima de 4 sobre 10 en la parte de teoría. La nota final de teoría de cada uno de los dos bloques de la asignatura será la máxima de las calificaciones obtenidas en el correspondiente control y en la parte correspondiente del examen final. Cada alumno decidirá si desea o no presentarse al examen final, y a qué bloques.

El peso en cada ítem de la evaluación de cada uno de los dos bloques se ponderará proporcionalmente al número de horas dedicadas a cada uno de ellos.

Para superar la asignatura, la calificación final deberá ser igual o superior a 5 puntos sobre 10. En caso de no haber llegado al mínimo requerido de 4 sobre 10 en la parte de teoría o en la parte de prácticas, la calificación final de la asignatura será el mínimo entre 4 y la nota obtenida.

Resumen de la evaluación

Procedimientos de evaluación

Valoración en %

 
 

Asistencia y participación en seminarios o tutorías

5

Participación activa en foros y actividades del campus virtual

10

Informes / Memorias / Exámenes de prácticas

40

Exámenes de carácter teórico

45

Evaluación en las convocatorias extraordinarias

En las convocatorias de carácter extraordinario el alumno deberá realizar un examen teórico que representará el 53% de la calificación final. En cuanto a las prácticas, se podrá realizar un examen práctico y/o requerir la entrega de algún trabajo, lo cual representará el 47% de la calificación final. Nótese que el 5% correspondiente a “Asistencia y participación en seminarios y tutorías” y el 10% correspondiente a “Participación activa en foros y actividades del campus virtual” no se evaluarán en la convocatoria extraordinaria. En la evaluación extraordinaria, al igual que en la ordinaria, es necesario obtener una calificación mínima de 4 sobre 10 tanto en la parte teórica como en la parte práctica.

Evaluación diferenciada

Aquellos alumnos con derecho a evaluación diferenciada serán evaluados del mismo modo que en las convocatorias extraordinarias.

Las siguientes tablas incluyen las referencias bibliográficas básicas y complementarias que se utilizan en la asignatura. Sin embargo, los estudiantes dispondrán también de otros recursos en forma de apuntes, transparencias, boletines de problemas, exámenes tipo, etc. que tendrán a su disposición en el Campus Virtual.

Bibliografía básica

Título

Autor

Editorial

Artificial Intelligence: A Modern Approach

Stuart Russell, Peter Norvig

Pearson, 2019

Metaheuristics: From Design to Implementation

El-Ghazali Talbi

Wiley, 2009

Bibliografía complementaria

Título

Autor

Editorial

Heuristics: Intelligent Search Strategies for Computer Problem Solving

Judea Pearl

Addison Wesley, 1984

Handbook of Constraint Programming

Francesca Rossi, Peter van Beek, Toby Walsh

Elsevier, 2006