Trabajo Práctico 2

El Trabajo Práctico consta de dos consignas. Para cada una, deberán entregar el código de una implementación en Python que la resuelva y un breve informe con los resultados y las conclusiones obtenidas, así como también cualquier explicación que consideren necesaria para facilitar la lectura del código o relacionada a decisiones que se tomaron durante la implementación.

Puede realizarse en grupos de $n$ personas, con $1\leq n\leq 3$.

Cada una de las consignas debe resolverse con una heurística, que puede ser elegida con libertad. Cada ejercicio debe ser resuelto con una técnica distinta. El objetivo del trabajo es obtener soluciones de buena calidad para ambas consignas de manera eficiente, por lo que no se aceptarán métodos que dependan exclusivamente de la aleatoriedad (es decir, por ejemplo, no está permitido utilizar sólo paseo aleatorio para resolver un problema). Se pueden implementar también heurísticas que no hayamos visto en clase o incluso mezclar algunas heurísticas con los métodos que vimos en la primera parte de la materia.

Fecha límite de entrega: Domingo 07/07 a las 23:59
Fecha límite de reentrega: 10 días después de la correción.

Consigna 1.

La empresa turística Aterrizar está por abrir una sucursal en Berlín y, entre otros, desea ofrecer un servicio de city tour en bicicleta. Se desea diseñar un recorrido de distancia mínima que pase por los $52$ puntos más pintorescos de la ciudad. Se deben visitar todos los puntos sin pasar dos veces por el mismo. Por cuestiones climáticas, obras de tránsito, manifestaciones u otros imponderables, puede ocurrir que la ruta deba ser modificada y, por ende, también las distancias entre los puntos. Como obtener la ruta óptima requiere mucho tiempo de cómputo y las rutas deben ser establecidas a diario, se pide desarrollar un programa que devuelva rutas de buena calidad en, relativamente, poco tiempo.

La matriz de distancia a utilizar para el desarrollo del programa viene dada en el archivo distancias.npy. Para cargarlas en su script pueden usar la función load de numpy:

In [ ]:
import numpy as np

matriz_distancias = np.load('distancias.npy')

Observaciones y sugerencias:

  • Hay 265252859812191058636308480000000 soluciones posibles
  • Es una instancia de TSP (por tanto, es un problema de optimización combinatoria)
  • El recorrido debe ser un ciclo (es decir, debe terminar donde comienza)
  • Una forma de modelar una solución es con una tupla que represente el orden en el que se visitan los puntos de la ciudad. De esta manera, se asegura que todos los puntos sean visitados una única vez. Por ejemplo, supongamos que solamente hay 5 puntos, un recorrido podría ser: $(5,3,1,2,4)$. Al implementar la función que calcula la distancia del recorrido, debe tenerse en cuenta que el último movimiento es desde $4$ a $5$.

Consigna 2.

Como ya hemos visto, algunas funciones que representan una auténtica pesadilla al momento de optimizar son aquéllas con muchos mínimos locales. Veamos el caso de las siguientes dos:

La función conocida en inglés como Holder table (mesa de apoyo (?)): $$f(X)=-\left|\sin\left(x_1\right)\cos\left(x_2\right)e^{\displaystyle\left|1-\frac{\sqrt{x^2_1+x^2_2}}{\pi}\right|}\right|$$

HolderTable.png

La segunda función de Schaffer: $$f(\mathbf{x}) = 0.5 + \frac{\sin^2 (x_1^2 - x_2^2)^2 - 0.5}{1 + 0.001(x_1^2 + x_2^2)^2}$$

Schaffer02.png

Como se puede ver, ambas funciones son multimodales y por ende tienen varios mínimos locales. Notar también que la función Holder Table no es diferenciable en algunos puntos del dominio y, por tanto, el correcto funcionamiento de los métodos de descenso que se apoyan en la derivabilidad de la función objetivo (estudiados en la primera parte de la materia) no está garantizado.

Se desean encontrar buenas soluciones a los problemas de minimizar ambas funciones en la región $[-10,10]\times[-10,10]$.

Sólo para tener como referencia, el mínimo global de la segunda función de Holder Table es $f(x^\ast)\approx −19.2085$ con $x^\ast \approx (\pm 8.05502, \pm 9.66459)$ y el de la segunda función de Shaffer es $f(x^\ast)=0$ siendo $x^\ast = (0,0)$.

Las funciones pueden implementarse de la siguiente manera:

In [1]:
import numpy as np

def holder_table(x):
    return -np.abs(np.sin(x[0])*np.cos(x[1])*np.exp(abs(1-np.sqrt(x[0]**2+x[1]**2)/np.pi)))

def schaffer_2(x):
    return 0.5 + (np.sin(x[0]**2 - x[1]**2)**2-0.5)/(1+0.001*(x[0]**2+x[1]**2)**2)