« Calificaciones Progra… « || Inicio || » Ejercicios IA »

Examen Bloque II. Diciembre 2016

Última modificación: 13 de Enero de 2017, y ha tenido 129 vistas

Instrucciones

El ejercicio 1 se debe entregar en papel, no olvidéis poner vuestro nombre.

El ejercicio 2 se debe entregar en un único fichero de NetLogo (no se tienen que entregar los ficheros de la librería, solo el principal .nlogo) donde debéis rellenar vuestros datos y cambiar el nombre del fichero por vuestro ApellidosNombre. Podéis encontrar los ficheros aquí en un solo ZIP.

Enunciado del Examen

EJERCICIO 1. (6 ptos) Optimización por Colonias de Hormigas:

  1. (2 ptos) Explica el algoritmo general de Optimización por Colonias de Hormigas, ayudándote para ello de un pseudocódigo que especifique las etapas principales.
  2. (4 ptos) Explica formalmente cómo podrías utilizarlo para resolver el siguiente problema de Optimización de Tareas:
    • Tenemos \(N\) tareas, \(\{T_1,\dots,T_N\}\), que se encargan de procesar datos.
    • Podemos hacer uso de un procesador que NO tiene capacidad paralela. 
    • Cada tarea, \(T_i\), tarda un tiempo \(t_i\) en ejecutarse, y hasta que no termina una tarea, no puede lanzarse otra.
    • Cada tarea solo se puede ejecutar 1 vez.
    • Algunas tareas solo se pueden ejecutar si algunas otras se han ejecutado antes. Para saber cuáles, disponemos de una tabla que indica si una tarea necesita que otra tarea se haya ejecutado antes. Por ejemplo, la siguiente tabla indica que \(T_1\) necesita que \(T_2\) se haya ejecutado antes, \(T_2\) necesita que \(T_4\) se haya ejecutado antes, y \(T_3\) necesita que \(T_1\) se haya ejecutado antes:
  \(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(T_1\) \(0\) \(1\) \(0\) \(0\)
\(T_2\) \(0\) \(0\) \(0\) \(1\)
\(T_3\) \(1\) \(0\) \(0\) \(0\)
\(T_4\) \(0\) \(0\) \(0\) \(0\)
    • Disponemos de un tiempo total, \(T\), para poder usar el procesador. 
    • Además, la ejecución de cada tarea, \(T_i\), consume \(D_i\) datos.

Objetivo: Obtener una secuencia de ejecuciones que consuma la máxima cantidad de datos en el tiempo total permitido.

Solución: 

Para representar este problema podemos usar un grafo dirigido en el que los nodos sean las tareas y las aristas unirán tareas compatibles entre sí. Todas las tareas que no tengan restricciones entre sí estarían por aristas en ambas direcciones.

En el ejemplo que nos proporcionan en el enunciado, comenzaríamos por un grafo dirigido completo que tiene como nodos \(T_1,\ T_2,\ T_3\) y \(T_4\), y que tiene todas las aristas dirigidas posibles (de todos los nodos a todos los nodos). Posteriormente, eliminaríamos las aristas que la matriz nos dice directamente que no son posibles (por ejemplo, si \(T_3\) necesita que \(T_1\) se haya ejecutado antes, la arista \(T_1\rightarrow T_3\) puede estar, pero eliminamos la \(T_3 \rightarrow T_1\)). Se debe tener en cuenta que esto elimina aristas que seguro no deben darse, pero hay recorridos que se pueden dar en el grafo y que siguen sin ser válidos.

Con un grafo así, sabemos que diversos recorridos en el grafo se corresponde con ejecuciones secuenciales de tareas en el procesador. Este es el grafo que usaremos siguiendo la ejecución normal del algoritmo de hormigas para el problema del viajante.

Cada vez que una hormiga acabe un recorrido, hemos de comprobar si es válido o no:

  1. Puede no ser válido porque la suma de los tiempos supere \(T\).
  2. Puede no ser válido porque no cumpla alguna restricción de ejecución.

Aquellas hormigas que proporcionen recorridos válidos dejan feromona en las aristas de sus recorridos, proporcional a la cantidad de datos consumidos en el recorrido (la suma de los datos que procesa cada tarea).

Las hormigas que no proporcionan recorridos válidos simplemente reiniciarán el proceso, pero ahora condicionadas por las nuevas feromonas depositadas por las hormigas que han tenido éxito en sus recorridos.

La ejecución de diversas iteraciones de las hormigas sobre el grafo anterior aproximará soluciones cada vez más eficientes.

EJERCICIO 2. (4 ptos) Haciendo uso de la librería para Algoritmos Genéticos proporcionada en clase, resuelve el problema anterior de Optimización de Tareas para el caso particular que se especifica a continuación (donde la posición i-esima de cada lista corresponde a la información relativa a la tarea i-ésima):

Número de tareas: N = 20
    Tiempos: [t_i] = [8 10 7 11 3 7 4 6 3 13 9 2 9 13 8 7 3 11 14 7]
    Datos consumidos: [D_i] = [65 60 51 30 3 22 31 92 80 57 64 86 50 86 31 89 73 21 11 90]
    Tiempo total disponible: T = 100
    Dependencia entre tareas: No hay (todas son independientes entre sí).

Solución: Descargar aquí.

« Calificaciones Progra… « || Inicio || » Ejercicios IA »