Profiling

[jlrzarcor]

• [x] Realizar perfilamiento de nuestro código robustecido (en la parte 1, práctica 2) en instancias de AWS para hacer que los métodos sean más eficientes.
• [x] Incluir características de la instancia en la que se perfila (integrar en carpeta de AWS esta descripcioón).
• [x] Integrar notebook de trabajo del perfilamiento.

[jlrzarcor]

Sprint Review:

@Carlosrlpzi @Lobolc , el paquete utilizado en la práctica anterior para realizar los test (en esta práctica #5 ) python-tsp es ineficiente para un conjunto de datos muy grande.

Se estuvo realizando una investigación observando que no existe una amplia variedad de paquetes desarrollados en Python. Se sustituye por OR-Tools.

[jlrzarcor]

Sprint Review:

De acuerdo a lo que hemos podido revisar, parece ser que el solver del paquete OR tools resuelve de forma precisa el TSP y en nuestro algoritmo de Hill Climbing no tenemos consistencia en la solución de óptima encontrada y en comparación.

Nos encontramos ante un momento sumamente desconcertante, pues pon un lado se tienen los mayores avances en las prácticas anteriores y de cara a la final pero esto nos ha frenado completamente.

Se tomará una decisión sobre finalizar la actividad utilizando el método alterno que se había desarrollado Conjugate Gradient (aunque se tiene una consideración por parte del Prof Erick de que ese método corresponde a una práctica de optimización 1) o continuar con el método de Hill Climbing y buscar si se resuelve más precisio por medio de cómputo en paralelo.

@Carlosrlpzi @Lobolc .

[jlrzarcor]

Sprint Review, Bug Fixed:

Se relaciona con el issue #4.

Durante el Perfilamiento se revisó OR Tools de Google como una paquetería para validar la consistencia aproximada de nuestra solución con nuestro paquete Opt_HC.CG.hill. Observamos que nuestra solución era inestable para un gran numero de ciudades y que estaba alejada de la solución de OR Tools. Si bien es cierto que HC es un método metaheurístico y por lo tanto la solución no es necesariamente el mínimo global e incluso uno de los problemas que indican en la literatura es que te puedes "atorar" en un mínimo local, no esperábamos una solución tan alejada de la paquetería de comparación.

Se decide analizar el Bug y re-implementar nuestro código para corregir tal situación:

• HC toma una solución inicial aleatoria y busca la mejor ruta dentro del "vecindario"; el problema era que nuestra solución estaba analizando únicamente una propuesta inicial en la que obtenía la mejor "ruta" del vecindario de esa inicial pero no exploraba otras posibles soluciones aleatorias. Por esta razón, fue necesario integrar un conjunto de iteraciones reiniciando el proceso de selección de propuesta inicial aleatoria con el objetivo de ampliar la búsqueda en el espacio de posibles soluciones factibles.

EUREKA, esto nos permitió encontrar soluciones más estables (pueden existir pequeñas variaciones derivado de la parte aleatoria en la solución inicial) y hasta 50 ciudades considerando 100 reinicios tenemos una muy buena aproximación.

Por lo anterior, concluimos que las mejores soluciones las vamos a obtener por paralelización, que es en lo que actualmente estamos trabajando para finalizar nuestra entrega.

[jlrzarcor]

@Carlosrlpzi @Lobolc , porfa feedback para el Statement que estoy integrando para el programa de OT-Tools que estamos utilizando para los Test.

"""Disclaimer: This Python module belongs to Google and was taken from: https://developers.google.com/optimization/routing/tsp and the main purpose of use is completely Educative.

ITAM, Optimization Course, 2021-1 TEAM: 05 """

[Carlosrlpzi]

El perfilamiento cumple con los requerimientos y nos da una buena perspectiva de nuestro código. Adelante con el cierre.