Tarea 0 Fecha de entrega: 10 de octubre de 2012 8 de octubre de 2012

1.

Consideraciones pertinentes La tarea se entrega en una u ´nica exhibici´on. Se pide un documento general que incluya la respuesta de todos los puntos realizados. Se pide una estructura de directorios donde se incluya (como directorio) cada punto de la tarea. Dentro de estos directorios, se deber´an incluir los c´odigos fuente, un archivo leeme.txt que indique como ejecutar dichos c´odigos y todos los ejemplos pertinentes con los que se prob´o el programa.

2.

Optimizaci´ on cl´ asica

1. Encuentre los valores de θ para el problema inmobiliario de Boston (encontrar los par´ ametros (θ) de una recta de una recta, tal que, minimice su distancia a los puntos brindados). El archivo “featuresX.dat” contiene la informaci´on de los metros cuadrados de las casas evaluadas. El archivo “priceY.dat” contiene la informaci´on de los precios de dichas casas. a) (5 puntos) Genere 1000 valores diferentes para θ (usando la informaci´ on que contienen los archivos featuresX.dat y priceY.dat) ue Pym eval´ en la funci´on de costo J (recuerde que que J(θ0 , θ1 ) = 1/2( i=0 (θ0 + θ1 ∗ xi − y i )2 )). Muestre la grafica resultante. De preferencia tambi´en proyecte su gr´ afica de contornos (http://matplotlib.org/mpl_toolkits/ mplot3d/tutorial.html). b) (10 puntos) Muestre procedimiento an´alitico utilizado para obtener θ de forma cerrada. c) (10 puntos) Implemente el Gradiente Descendente en Python para resolver dicho problema. Por favor use una longitud de paso fija (determ´ınela ud. mismo). d ) (5 puntos) Muestre la gr´ afica de convergencia (una vez que obtenga el nuevo valor de theta, eval´ ue dicho valor en la funci´on original -J) obtenida por el programa implementado (en el punto anterior). 1

e) (5 puntos) Muestre una gr´ afica que incluya 1) la recta que representa theta, obtenida mediante su forma cerrada, y 2) la recta que representa θ, obtenida mediante el programa implementado del Gradiente Descendente. 2. Minimice la funci´on f (x1 , x2 ) = x1 − x2 + 2x21 + 2x1 x2 + x22 : a) (15 puntos) Muestre los pasos del m´etodo de Gradiente descendente para optimizar f . El puntos inicial ser´a (0, 0). Indique claramente d´onde est´ a el ´ optimo y todo el procedimiento requerido (al menos 5 iteraciones). b) (15 puntos) Realice un programa en Python que implemente el Gradiente Descendente para minimizar f . Use una longitud de paso f´ıja (determ´ınela ud. mismo) y comience en el punto inicial (0, 0) 3. (20 puntos) Dos escaleras se cruzan en un pasillo, tal y como se muestra en la Figura 1. Cada escalera est´ a colocada de la base de una pared a alg´ un punto de la pared opuesta. Las escaleras se cruzan a una altura H arriba del m, y que pavimento. Dado que las longitudes de las escaleras son x1 = 20m y x2 = 30m H = 8m, encontrar A, que es el ancho del pasillo, usando alg´ un programa de m´etodos num´ericos. Muestre el procedimiento anal´ıtico utilizado para derivar la ecuaci´ on correspondiente, la cual se resolver´ a usando cualquier m´etodo num´erico. Imprima las iteraciones efectuadas por su programa al resolver este problema.

3.

B´ usqueda

1. (50 puntos) Primero en profundidad vs primero en anchura Realice dos programas de b´ usqueda, uno de primero en profundidad y otro de primero en anchura que encuentren la ruta m´as corta desde T imisoara hasta Bucharest, de acuerdo al mapa mostrado en la figura 2. Nota: ninguno de ambos algoritmos toma en cuenta las distancias para realizar la expansi´ on de la b´ usqueda. Por lo tanto, lo que regresan ambos algoritmos ser´a un camino que permite llegar desde T imisoara hasta Bucharest tomando en cuenta los saltos entre nodos. El primero en anchura es optimal con respecto a este criterio (n´ umeros de nodos o saltos), mientras que el primero en profundidad no. Finalmente, ud. decide si quiere limitar la profundidad del algoritmo de primero en profundidad, si lo hace expr´eselo en el documento. La entrega deber´ a contener: a) El c´odigo fuente de ambos programas, con comentarios. El programa deber´ a ser capaz de interpretarse bajo Python versi´on 2.7 y, de ser necesario, podr´ıa requerirse al autor que demuestre el uso del programa personalmente al instructor.

2

Figura 1: Escaleras entrecurzadas

Figura 2: Problema a resolver de primero mediante primero en anchura y primero en profundidad.

3

2. (Bonificaci´ on: 30 puntos ) Resuelva el problema de ir desde T imisoara hasta Bucharest usando el algoritmo del A∗ . Sea creativo y cree su propia heur´ıstica. Se recibir´ a el c´odigo fuente del programa con comentarios. 3. (100 puntos m´ aximo) Resuelva el problema de 8-puzzle usando el algoritmo del A*. La inicializaci´on deber´ a ser aleatoria y deber´a de mostrar todos los pasos a seguir para llegar al objetivo. La entrega deber´ a contener: a) (90 puntos) El c´odigo fuente del programa, con comentarios. El programa deber´ a ser capaz de interpretarse bajo Python versi´on 2.7 y, de ser necesario, podr´ıa requerirse al autor que demuestre el uso del programa personalmente al instructor. b) (Bonificaci´ on : 10 puntos) Comparaci´ on entre A* y la b´ usqueda de primero en profundidad limitada para resolver este problema

4.

Inteligencia colectiva

4. (110 puntos m´ aximo) El objetivo de este punto es que el estudiante se familiarice con el funcionamiento de las metaheur´ısticas bioinspiradas. Para ello, tendr´ a que implementar la metaheur´ıstica denominada Optimizaci´on Mediante C´ umulos de Part´ıculas (PSO por sus s´ıglas en Ingl´es): Escriba un programa en Python (preferentemente usando numpy) que implemente la versi´on GBest (el algoritmo visto en clase) y util´ıcelo para minimizar: f (x1, x2) = [1.5−x1 (1−x2 )]2 +[2.25−x1 (1−x22 )]2 +[2.625−x1 (1−x32 )]2 (1) donde −5 ≤ x1 , x2 ≤ 10. La entrega deber´ a contener: a) (60 puntos) El c´odigo fuente del programa, con comentarios. El programa deber´ a ser capaz de interpretarse bajo Python versi´on 2.7 y, de ser necesario, podr´ıa requerirse al autor que demuestre el uso del programa personalmente al instructor. b) (10 puntos) Una gr´ afica de la funci´on a optimizarse dentro de los rangos permisibles para las variables. De preferencia tambi´en incluya una gr´ afica de contorno. c) (30 puntos) Graficas de caja (Box-plots) de al menos 30 corridas diferentes en las que se use el mismo valor para C1 , C2 y W de Gmax, pero utilizando diferentes valores para la semilla de aleatorios y para las variables de inicio x ¯. d ) (Bonificaci´ on : 10 puntos) Muestre una corrida del PSO que obtenga el ´ optimo de esta funci´on (la gr´ afica le sugerir´a d´onde se encuentra). No olvide incluir todos los par´ ametros utilizados por dicho algoritmo. 4

e) (Bonificaci´ on: 5 puntos) Minimice la funci´on f (x1 , x2 ) = x1 − x2 + 2x21 + 2x1 x2 + x22 donde −5 ≤ x1 , x2 ≤ 5, y compare ventajas y desventajas de implementaci´ on y resultados obtenidos, con respecto a su implementaci´ on del gradiente descendente (que obtiene los valores m´ınimos de la misma funci´on). Fecha de entrega: 10 de octubre de 2012 a las 8:00hrs. Toda tarea entregada tarde ser´a penalizada con 10 % (sobre la calificaci´on obtenida) por cada periodo de 24 horas que se retrase su entrega.

5