Tópicos de Optimización Avanzada

# Tópicos de Optimización Avanzada ## Algoritmo _ACO_ para resolver problemas _TSP_ **Estudiantes:** Santiago Battezatti, Sebastián Cadavid-Sánchez, Rafael Ortega, Laura Tejada ### Índice 0. Objetivo 1. Problema de optimización a resolver: Traveller Salesman Problem 1.1. Algoritmo Greedy 1.2. Algoritmo Ant Colony Optimization 2. Desarrollo y Optimización de código 3. Implementacion del algoritmo con un problema real 3.1. Conjunto de datos 3.2. Solución del problema TSP 4. Conclusiones 5. Referencias ## 0. Objetivo El objetivo de este proyecto fue estudiar el problema de optimización del viajero (_Travelling Salesman Problem - TSP_) y su solución por medio del algoritmo de colonia de hormigas (_Ant Colony-ACO_). Realizar la implementación del algoritmo ACO en lenguaje `Python` en la librería [![ACO-TSP](https://gist.githack.com/C1587S/6f2fccb2473f9c9c8a093db7a03f9ab3/raw/f895b41f3ea45fd26c529b7e80ea4a3c69b0e0a5/ACO%20TSP%20pkg.svg)](https://github.com/optimizacion-2-2021-1-gh-classroom/practica-1-segunda-parte-ltejadal) para la solución de problemas TSP con conjuntos de datos reales. En las fases de desarrollo del proyecto se busca robustecer las implementaciones de la librería por medio de cómputo en paralelo y métodos de selección de hiper-parámetros. Así como probar la librería en lanzamientos de _pipelines_ con `kubeflow`y `kale`. En la sección 1 de este documento se describe el problema de optimización TSP a resolver y el algoritmo ACO. En la sección 2 se presenta una descripción general de la implementación de la librería `ACO-TSP`. En la sección 3 se presenta el uso de la librería para solucionar un problema TSP con una base de de datos utilizando un enfoque de _pipeline_. Finalmente, en la sección 4 se presentan las conclusiones. ### 1. Problema de Optimización a resolver: Traveller Salesman Problem (TSP) El problema de optimización a resolver consistió en el del Traveller Salesman Problem (TSP) que consiste en hallar el recorrido más corto para recorrer una serie de nodos interconectados entre sí. Así, dada una matriz de distancias entre cada nodo y todos los demás, se busca encontrar el mejor recorrido posible. Podemos formular el TSP como un problema de programación lineal en enteros, como sigue: $$\displaystyle \min_{0 \leq x_{ij} \leq 1} \sum\limits_{i=0}^{n} \sum\limits_{j\neq i, j=0}^{n} c_{ij} x_{ij}$$$$\text{sujeto a:}$$$$\sum\limits_{i=0, i \neq j}^{n} x_{ij} = 1, j = 0, ..., n$$$$\sum\limits_{j=0, j \neq i}^{n} x_{ij} = 1, i = 0, ..., n$$$$ u_i - u_j + nx_{ij} \leq n - 1, 1 \leq i \neq j \leq n $$ Donde: - $x_{ij}$ es igual a 1 si existe un camino de la ciudad $i$ a la ciudad $j$, y cero en otro caso. - $c_i$ es la distancia desde la ciudad $i$ hasta la ciudad $j$. - $n$ el número total de ciudades. - $u_i$ son variables artificiales para definir las restricciones del problema. En primer lugar, es necesario señalar que la opción de “fuerza bruta”, calcular todos los caminos posibles y elegir el que minimice el costo (la distancia total recorrida) es una opción que no se encuentra disponible por su costo computacional, especialmente a medida que el tamaño del conjunto de datos empieza a aumentar. En otras palabras, la solución por *fuerza bruta* no es escalable. Así, se procedió a investigar algunos algoritmos que permitieran resolver este problema. En particular, se investigaron dos algoritmos, el algoritmo *Greedy* y el algoritmo *Ant Colony Optimization*. ### 1.1. Algoritmo Greedy El algoritmo *Greedy* (avaricioso) es un algoritmo que consiste en elegir la opción menos costosa (o la que otorga una mayor ganancia en el corto plazo, de ahí su nombre) en cada iteración. Por su facilidad de implementación, este algoritmo suele ser utilizado como *baseline*; es decir, como una forma para determinar un punto de partida que debe ser mejorado al resolver un problema de optimización. Asimismo, es preciso señalar que el algoritmo *greedy* no fue diseñado específicamente para resolver el *Traveller Salesman Problem*, sino que se trata de una familia de algoritmos que pueden ser aplicados (replicando el razonamiento iterativo que se acaba de mencionar) a varios problemas de optimización. ### 1.2. Ant Colony Optimization En segundo lugar, investigamos el algoritmo *Ant Colony Optimization*, el cual decidimos implementar. Este algoritmo recibe su nombre porque imita el funcionamiento de una colonia de hormigas. Para ello, el algoritmo envía hormigas que eligen diferentes caminos, y en su trayectoría dejan feromonas. Esto imita lo que sucede en la realidad, ya que las hormigas son animales ciegos, que para elegir su camino se guían principalmente por el olor de feromonas dejado por otras hormigas. En la práctica, a medida que un camino se toma con mayor frecuencia, empiza a contar con una mayor cantidad de feromonas, aumentando la probabilidad de que las siguientes hormigas tomen ese mismo camino. Por medio de esta iteración de homigas, que de manera secuencial van recorriendo diferentes caminos (dejando feromonas y guiándose en parte por las feromonas previas que encuentran en su camino), el algoritmo realiza el proceso de encontrar el mejor camino para resolver el TSP. En otras palabras, al momento de decidir qué paso dar de un nodo al siguiente, cada hormiga se guía parcialmente por la cantidad de feromonas que hay en cada arista. En la implementación concreta del algoritmo, la cantidad de feronomas dejada por cada hormiga en su recorrido tiene una relación proporcional a qué tan bueno ha sido el performance de su tour (es decir el costo total de su recorrido, medido con la distancia). A su vez, el algoritmo cuenta con una propiedad de “evaporación” de las feromonas en el tiempo, que es fundamental para el proceso de optimización porque, a medida que se van encontrando nuevos caminos mejores que los anteriores, es preciso que estos cobren mayor peso para cada hormiga en sus decisiones, en comparación de los viejos caminos subóptimos. A continuación, describimos la implementación de este algoritmo y cómo buscamos mejorar y optimizar su código. ## 2. Desarrollo y Optimización de código En esta sección se describe de forma general el proceso de implementación de la librería [![ACO-TSP](https://gist.githack.com/C1587S/6f2fccb2473f9c9c8a093db7a03f9ab3/raw/f895b41f3ea45fd26c529b7e80ea4a3c69b0e0a5/ACO%20TSP%20pkg.svg)](https://github.com/optimizacion-2-2021-1-gh-classroom/practica-1-segunda-parte-ltejadal), y algunos de sus ḿetodos y funciones principales. La documentación detallada de la misma está disponible en la siguiente referencia: [![Documentation](https://gist.githack.com/C1587S/ccc36b3d60edb8329464588177bae5d2/raw/f91c3226a4e9627a1eef7c40d0356df75d114a30/ACO%20TSP%20Documentation.svg)](https://c1587s.github.io/ACO-TSP/index.html). ### 2.1 Implementación La implementación del algoritmo se dividió en distintas etapas, dirigidas a la solución de problemas TSP que se pueden enmarcar en un flujo (_pipeline_) dirigido, desde la carga de la base de datos, hasta la solución del problema y su visualización como se presenta en la Figura 1. ```flow st=>inputoutput: Lectura de datos op1=>operation: Grafo op2=>operation: Inicialización ACO op3=>operation: Selección de hiper-parámetros op4=>operation: Solución TSP op5=>operation: Visualización st->op1->op2->op3->op4->op5 ``` _**Figura 1** Diagrama de flujo de la implementación de la librería `ACO-TSP`. Donde _TSP_ es _Travelling Salesman Problem_ y `ACO` es el algoritmo _Ant-Colony_._ Inicialmente se abordó un enfoque funcional para cumplir todas las tareas del flujo anterior. Con el fin de robustecer la librería, se adoptó un enfoque orientado a objetos. Luego de realizar ejercicios de perfilamiento, se identificaron secciones del código donde el tiempo de ejecución podría reducirse, especialmente para problemas que implicaran más nodos en el grafo analizado. Para lo anterior se re-implementó el algoritmo incluyendo cómputo en paralelo. Las implementaciones de la librería `ACO-TSP` se realizaron en lenguaje `Python`, y el flujo de trabajo llevado a cabo se presenta en la Figura 2. ```mermaid gantt title Cronograma de implementación de código section Etapa 1 Estudio previo:a1, 2021-03-10, 13d Enfoque funcional:a2, 2021-03-15 , 15d section Etapa 2 Enfoque POO:2021-04-01 , 20d Optimización HP:2021-04-11 , 10d Perfilamiento:2021-04-15 , 10d Computo paralelo:2021-04-15 , 18d section Etapa 3 Visualización:2021-05-01 , 10d ``` _**Figura 2** Cronograma de implementaciones en la librería `ACO-TSP`._ ### 2.2 Clases, métodos y funciones La librería `ACO-TSP` tiene tres clases principales que ayudan a resolver problemas **TSP** con el algoritmo de colonia de hormigas: `ant`, `colony`, y `colony_mtw`. Dichas clases implementan diferentes métodos y funciones, cuyos elementos más relevantes se presentarán en esta sección. #### Clase `ant` Esta clase representa una hormiga de la colonia y su labor principal es realizar recorridos por el grafo, `G`, que representa la matriz de distancias. Para inicializarse se le debe proporcionar el grafo asociado al problema, un diccionario de distancias entre los nodos, e indicar por cuál nodo iniciará su recorrido. **Método _`walk_over_graph`_** Este es el único método de la clase `ant`, y busca que la hormiga recorra todo el grafo, `G`, iniciando y terminando en el mismo nodo, sin repetir ninguno. Al final de su recorrido, la hormiga reporta la ruta recorrida y su distancia asociada. Para poder decidir los caminos por donde se llevará a cabo su recorrido, la hormiga es provista de un nivel de atracción de cada nodo, el cual depende del nivel de atracción inicial (que depende de las distancias entre nodos) y el nivel de feromonas por los distintos caminos del grafo. En este sentido, cada vez que la hormiga llega a un nodo, la probabilidad de que decida hacia cuál vecino ir es afectada por los pesos asignados a cada uno por medio del diccionario de atracción. #### Clase `colony` La clase `colony` es una composición de varias hormigas, provenientes de la clase `ant` que van recorriendo grafo `G`. En particular, los diferentes recorridos que realizan las hormigas afectan los niveles de feromonas del grafo, y por lo tanto, también los niveles de atracción de cada nodo. Para iniciar una colonia se debe proporcionar el grafo, `G`, y dónde deben iniciar las hormigas. Adicionalmente, se puede indicar el número de hormigas que incluye la colonia, `n_ants`, y el número de iteraciones que se deben realizar, `max_iter`. **Metodo _`solve_tsp`_** Es el principal método de la clase `colony`, y obtiene la ruta más corta de la colonia encontrada por las hormigas y su distancia asociada. A continuación se enlistan los pasos que ejecuta la colonia de hormigas en cada iteración para resolver el problema TSP y el método (met) o función (func) que utiliza para la ejecución. 1. Computa el diccionario de atracción de los nodos (`atraccion_nodos` [func]). 2. Todas las hormigas de la colonia recorren `G` <u>secuencialmente</u> (`_colony_run` [met]). 2.1. Cada hormiga recorre el grafo y reporta la ruta y distancia encontradas (`walk_over_graph` [met]) 2.1. Se actualizan los niveles de feromonas de `G` (`_update_many_pheromone_levels` [met]). 3. Se ajustan los niveles de feromonas de acuerdo a una tasa de evaporación (`_evaporates_pheromone` [met]). En cada iteración la colonia guarda la mejor ruta y distancias obtenidas como atributos (`best_route` y `best_dist`, respectivamente), y en caso de que se obtenga una mejor, son reemplazados. Una vez ejecutado este método, es posible extraer dichos atributos para obtener la solución del problema obtenida por el algoritmo. #### Clase `colony_multiw` La clase `colony_multiw` se deriva de `colony`, e implementa cómputo en paralelo haciendo multiprocesamiento en el ḿetodo `solve_tsp`. Dicha implementación surgió de los ejercicios de perfilamiento realizados, los cuales indicaron que el mayor tiempo de cómputo se explicaba por la secuencialidad en el recorrido del grafo de las hormigas de la colonia en el método mencionado. La nueva implementación del método se logró utilizando la librería [`multiprocessing`](https://docs.python.org/3/library/multiprocessing.html) de `Python`. En particular, la principal diferencia con respecto a `colony`, es que en cada iteración `colony_multiw` crea un _Pool_ de sub-procesos, y a cada uno le asigna un número aproximadamente equitativo de hormigas. Así, simultáneamente en cada sub-proceso un número de hormigas determinado recorre el grafo secuencialmente. Al final de la iteración, un proceso principal reune las rutas y las distancias obtenidas por todas las hormigas en todos los procesos, y la colonia almacena el mejor par como un atributo. A modo de ejemplo, en la Figura 3 se presenta un grafo dirigido para mostrar el procedimiento que se realiza en cada iteración el método `solve_tsp` en la clase `colony_multiw`. En esta representación se utilizan **3 procesos** y se seleccionan **4 hormigas**. Dado lo anterior, a un proceso se le asignan 2 hormigas, y una a los dos restantes. ```graphviz digraph hierarchy { nodesep=1 node [color=Blue, fontname=Courier, shape=box] edge [color=Black] colony_multiw->asignar_hormigas->{SP1 SP2 SP3} SP1->{h1 h2} h1->h1_recorre_G h2->h2_recorre_G SP2->{h3} h3->h3_recorre_G SP3->{h4} h4->h4_recorre_G {rank=same;SP1 SP2 SP3} {rank=same;h1 h2 h3 h4} {h1_recorre_G h2_recorre_G h3_recorre_G h4_recorre_G}->recolectar_soluciones recolectar_soluciones-> MejorSolucion->colony_multiw } ``` _**Figura 3** Representación del cómputo del método `solve_tsp` de la clase `colony_mtw` en cada iteración. Donde SP denota un subproceso. h_i denota a una hormiga con identificador i._ **Mejoras en tiempo de ejecución** La mejora en el tiempo de ejecución depende del _hardware_ en que es ejecutado el algoritmo. A continuación se presenta el desempeño en tiempo total de ejecución del algoritmo en dos máquinas con diferentes características, y se compara la mejora en tiempo con respecto a la ejecución secuencial. En particular, se resuelve problema TSP de $100$ ciudades chinas, elegidas aleatoriamente del conjunto de la [base de datos](https://www.math.uwaterloo.ca/tsp/world/countries.html) de *National Traveling Salesman Problems* de la Universidad de Waterloo. Se utilizan $100$ iteraciones, $1000$ hormigas, y valores de $1$, $5$, y $0.5$ para los parámetros de importancia del nivel inicial de atracción, importancia del nivel de feromonas, y nivel de evaporación, respectivamente. <center> | CPU(s) | CPU(s) utilizados | Computo | Tiempo (segs/mins) | Mejora en tiempo | |--------------------------------------------------|----------|--------------|--------------------|------------------| | Intel(R) Xeon(R) Platinum 8259CL CPU @ 2.50GHz | 1 | Secuencial | 2699.36 s / 45 m | x1 | | Intel(R) Xeon(R) Platinum 8259CL CPU @ 2.50GHz | 4 | Paralelo | 452.37 s / 7.5 m | x5.97 | | Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz | 1 | Secuencial | 794.74 s / 13.24 | x1 | | Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz | 12 | Paralelo | 21.60 s / 0.36 m | x36.79 | </center> _**Tabla 1** Comparación del tiempo de cómputo de la implementación secuencial y con cómputo en paralelo de `ACO-TSP` para diferentes arquitecturas._ ### 2.3 Optimización de hiper-parámetros El algoritmo de colonia de hormigas implementado incluye cinco hiper-parámetros: - Número de hormigas en la colonia (`n_ants`) - Máximo número de iteraciones (`max_iter`) - Importancia del nivel de atracción inicial (`rho`) - Importancia del nivel de las feromonas (`beta`) - Grado de evaporación de las feromonas (`alpha`) Para robustecer la librería, se implementó la rutina `optim_h_params` que utiliza la librería [`optuna`](https://optuna.org/), con el fin de utilizar técnicas de optimización bayesiana para buscar eficientemente los parámetros que maximizan una función objetivo en un "hiper-espacio". Seleccionamos un subconjunto de los datos a analizar, y los utilizamos para realizar dicho ejercicio de optimización, para el cual se debe definir una función objetivo. En este caso, queremos que el algoritmo encuentre la distancia de la ruta más corta que recorra todos los nodos del grafo, y que a su vez, sea lo más rápido posible en tiempo de ejecución. Para lo anterior, se propone minimizar la siguiente función objetivo: $$ obj = t + d^2 $$ Donde $t$ es el tiempo de ejecución en minutos, y $d$ es la distancia de la ruta encontrada por el algoritmo. Las clases `colony` y `colony_multiw` incluyen el método `optim_h_params`, el cual permite definir el número de intentos (`trials`) sobre los cuales se va a realizar muestreo sobre el espacio de hiper-espacio, y devuelve el conjunto de mejores hiperparámetros para el problema estudiado. ## 3. Implementación del algoritmo en un conjunto de datos En esta sección se utiliza la librería [`ACO-TSP`](https://github.com/C1587S/ACO-TSP/) para resolver el problema TSP en un conjunto de datos reales utilizando un enfoque de _pipeline_ que es ejecutado en [`kale`](https://github.com/kubeflow-kale/kale) en una instancia de AWS. En las siguientes subsecciones se explicarán: el conjunto de datos, los pasos incorporados en el _pipeline_, las caracaterísticas de la máquina utilizada, y los resultados asociados al ejercicio. ### 3.1. Descripción de la base de datos Se utilizó un conjunto de datos de la base de datos [National Traveling Salesman Problems](http://www.math.uwaterloo.ca/tsp/world/countries.html) de la Universidad de Waterloo que contiene las coordenadas de 71,009 ciudades en China, y se encuentra disponible en la siguiente [liga](http://www.math.uwaterloo.ca/tsp/world/ch71009.tsp). Este conjunto de datos contiene latitud y longitud para dichas ciudades, con lo cual se calcula la matriz de distancias, considerándolas como el costo asociado de ir de un nodo a otro. En este ejercicio se seleccionan 150 ciudades para el problema TSP y se utiliza un subconjunto de 50 para la selección de los mejores hiper-parámetros. ### 3.2 Arquitectura **Instancia EC2** El ejercicio de implementación se ejecutó en una instancia de EC2 de AWS con las características presentadas en la Tabla 2: <div align="center"> | Architecture | x86_64 | |---------------------|------------------------------------------------| | CPU op-mode(s) | 32-bit, 64-bit | | Byte Order | Little Endian | | CPU(s) | 4 | | On-line CPU(s) list | 0-3 | | Thread(s) per core | 2 | | Core(s) per socket | 2 | | Socket(s) | 1 | | Model name | Intel(R) Xeon(R) Platinum 8259CL CPU @ 2.50GHz | | CPU MHz | 3099.932 | | BogoMIPS | 4999.99 | </div> ``` _**Tabla 2** Características de la instancia EC2 de AWS para la implementación de de ACO-TSP en un conjunto de datos real._ **Imagen de [`Docker`](https://www.docker.com/)** La librería cuenta con una imagen de Docker disponible en [Dockerhub](https://hub.docker.com/r/santibatte/ant_colony_jupyter/tags?page=1&ordering=last_updated) que permite instalar de forma estable todas las dependencias requeridas. Dicha imagen es utilizada en la instancia de AWS para ejecutar la implementación. ### 3.3 _Pipeline_ El _pipeline_ implementado en ésta ejecución se puede representar en la Figura 4. Los pasos se describen a continuación: - `imports`: se `ACO-TSP` y dependencias adicionales - `parametros`: Se definen los parámetros a utilizar durante la ejecución. - lectura de datos (`grafo_datos_hp`): Se extrae el grafo correspondiente a un subconjunto de la totalidad de los datos del problema, para realizar la optimización de hiper-parámetros. - lectura de datos (`grafo_datos_principales`): Se extrae el grafo asociado a la totalidad de ciudades (nodos) del problema. - lectura de datos (`coord_datos_principales`): Se extrae un `dataframe` con las coordenadas de cada uno de los nodos del problema. - `mapa_nodos`: Se grafica el mapa con la ubicación de cada nodo utilizando sus coordenadas. - `seleccion_hp`: Se realiza el estudio y selección de los mejores hiper-parámetros. - `hp_disco`: Se guardan los mejores hiper-parámetros en disco con formato de base de datos, `.db`. - `colonia_mtw`: Se instancía una colonia que utiliza computo en paralelo con los mejores hiper-paŕametros encontrados qe incorpora el grafo con la totalidad de los nodos. - `colonia`: Se instancía una colonia (sin cómputo en paralelo) con los mejores hiper-paŕametros encontrados qe incorpora el grafo con la totalidad de los nodos. (se utiliza para comparar con la implementación de `colonia_mtw`) - `resolver_TSP`: La colonia obtiene una solución al problema TSP para las especificaciones asignadas. - `distancia`: Se extrae la distancia ḿas baja de la solución. - `ruta`: Se extrae la ruta asociada a la distancia más baja. - `guardar_sln`: Guardar solución en disco con formato `.json` - `mapa_ruta`: Se grafica el mapa con la ubicación de cada nodo utilizando sus coordenadas y la ruta con la solución encontrada por la colonia. ```graphviz digraph hierarchy { nodesep=1 node [color=red, fontname=Courier, shape=box] edge [color=Black] imports->parametros->lectura_datos lectura_datos->{grafo_datos_hp grafo_datos_principales coord_datos_principales} coord_datos_principales->mapa_nodos grafo_datos_hp->seleccion_hp->hp_disco {grafo_datos_principales hp_disco}->{colonia_mtw, colonia} colonia_mtw->resolver_TSP colonia->resolver_TSP resolver_TSP->distancia resolver_TSP->ruta {distancia, ruta}->guardar_sln {coord_datos_principales, ruta}->mapa_ruta {rank=same;grafo_datos_principales coord_datos_principales grafo_datos_hp} edge[style=invis] # grafo_datos_principales->colonia_mtw } ``` _**Figura 4** _Pipeline_ para la implentación de la librería `ACO-TSP` con un conjunto de datos real._ ### 3.4. Implementación del código y resultados obtenidos En esta sección se presenta la implementación en `Python` y los resultados obtenidos, con el fin de ilustrar el uso de la librería. ```python # instalar libreria !pip install "git+https://github.com/C1587S/ACO-TSP#egg=ant-colony&subdirectory=src" &> /dev/null" &> /dev/null ``` - Importación de librerías a utilizar ```python import ant_colony as ac import json from multiprocessing import cpu_count import time import timeit ``` En este caso, las librerías `time` y `timeit` fueron importadas para mostrar los tiempos de ejecución del programa. - Definición de los paŕametros de la ejecución ```python ## parametros del algoritmo data_path = '../datasets/ch71009.tsp' init_node_ex = 0 hp_trials = 50 save_hp = True seed = 19519159 n_cities = 150 n_cities_hp = 50 n_cpu = cpu_count() ``` De los parámetros anteriores: * `data_path`: hace referencia al lugar donde se encuentra el conjunto de datos. * `init_node_ex`: indica el nodo en donde iniciaremos la implementación. * `hp_trials` es la cantidad de veces que se muestrea para buscar en el espacio de hiper-parámetros. * `save_hp` indica si los mejores hiper-parámetros encontrados serán guardados en un archivo con el nombre de "best_hiper_parameters.db" * `n_cities` es el número de ciudades sobre las cuales se realizará la ejecución. * `n_cities_hp` es la cantidad de ciudades que se usarán para el meustreo de hiper-parámetros. * `n_cpu` indica el número de CPU's disponibles en la computadora de ejecución. En este caso son 4. - Lectura y separación de datos Como se mencionó inicialmente, se utiliza un conjunto de datos principal para el problema TSP asociado a 150 ciudades, y se selecciona un subconjunto de 50 para la elección de los mejores hiper-parámetros. Por otro lado, se extrae el `dataframe` asociado a las coordenadas de los nodos del problema. ```python # lectura de datos ## 150 ciudades - coordenadas y grafo coord_df = ac.read_coord_data(data_path, n_cities=n_cities, seed=seed, coord_df=True) G = ac.read_coord_data(data_path, n_cities=n_cities, seed=seed, coord_df=False) ## 50 ciudades - grafo hp G_hp = ac.read_coord_data(data_path, n_cities=n_cities_hp, seed=seed, coord_df=False) ``` La función `read_coord_data` nos ayuda a leer la información que viene en formato de coordenadas, y transformarla en un grafo de `networkx`, si se utiliza el parámetro `coord_df=False`. Lo anterior, dado que la clase `colony_mtw` requiere el mismo para el funcionamiento de sus ḿetodos. Por otro lado, si se requieren obtener únicamente los datos de las coordenadas de los nodos se puede utilizar `read_coord_data` con el parámetro `coord_df=True`. - Mapa con los nodos del problema Para problemas que incluyen coordenadas resulta útil visualizar los nodos en un mapa con el fin de realizar una validación previa de los mismos. Para lo anterior, se incluyó la función `plot_nodes_map`, que se puede utilizar de la siguiente forma: ```python # visualizar y guardar mapa map_nodes = ac.plot_nodes_map(coord_df, save=True, save_as='map_nodes') map_nodes ``` ![mapa_nodos](https://i.imgur.com/Qf6L2ZX.png) _**Figura 5** Representación estática de los nodos en un mapa._ Una visualización ḿas no-estática del anterior mapa se encuentra disponible [aquí](http://acotspcities.s3-website-us-east-1.amazonaws.com/). - Estudio para selección de hiper-parámetros Para la selección de los mejores hiper-paŕametros se implementó la función `optim_h_params_mp`, cuyo funcionamiento se explica en secciones anteriores. Para este caso se utiliza el grafo destinado a esta parte del ejercicio, `G_hp`, y se especificó un muestreo de 10 intentos (`hp_trials=10`) en el "hiper-espacio". Para iniciar el estudio, se ejecuta: ```python # optimizacion de hiper-parametros y guardar en disco study = ac.optim_h_params_mp(G_hp, init_node = init_node_ex, trials = hp_trials, save = save_hp) ``` Ejecutándolo con `timeit`, mostró los siguientes resultados: ``` The slowest run took 13.82 times longer than the fastest. This could mean that an intermediate result is being cached. 2min 41s ± 4min 17s per loop (mean ± std. dev. of 15 runs, 10 loops each) ``` Al finalizar, los mejores hiper-parámetros se guardan como `best_hiper_params.db`. - Crear colonia con los mejores hiper-parámetros Una vez se han seleccionado los mejores hiper-parámetros, se instancía la clase `colony_multiw` con los mismos, y el grafo asociado al problema principal con 150 nodos, `G`. Adicionalmente, se selecciona el número de `subprocesos` como el total de CPU de la EC2, es decir, 4. ```python # cargar mejores hp best_params = ac.load_params('best_hiper_params.db') # instanciar colony_multiw con mejores hp colony_mw = ac.colony_multiw(G, init_node=0, n_workers = n_cpu, verbose=True, k_verbose=10, **best_params) ``` - Resolver problema TSP Para que la colonia solucione el problema TSP se utiliza el método `solve_tsp` de la misma: ```python # Nota: start_time y end_time no son necesarios para # la implementación de la paquetería, pero fueron utilizados # solamente con la finalidad de mostrar el tiempo de ejecución. start_time = time.time() colony_mw.solve_tsp() end_time = time.time() ``` Se obtienen los siguientes resultados para la solución del problema: La mejor ruta encontrada fue la siguiente: ``` Resumen: Nro. de hormigas: 4 Iteraciones: 10 Distancia: 470.2663138277652 Nodo inicial: 0 Ruta: [0, 86, 85, 60, 135, 8, 79, 109, 35, 56, 10, 15, 91, 128, 94, 105, 20, 2, 33, 41, 69, 93, 123, 59, 67, 118, 68, 114, 107, 75, 62, 108, 106, 149, 145, 4, 46, 19, 32, 148, 43, 36, 141, 88, 64, 66, 16, 17, 37, 99, 52, 12, 104, 127, 129, 26, 130, 24, 87, 78, 31, 25, 45, 55, 101, 116, 5, 136, 74, 147, 111, 51, 90, 50, 132, 47, 117, 126, 27, 58, 80, 125, 63, 11, 121, 122, 76, 40, 119, 61, 48, 23, 72, 96, 44, 81, 3, 6, 57, 53, 115, 103, 95, 89, 29, 1, 9, 14, 34, 70, 13, 139, 143, 84, 133, 21, 134, 146, 22, 92, 39, 110, 54, 137, 18, 124, 71, 83, 30, 65, 131, 138, 7, 112, 140, 82, 98, 120, 49, 97, 100, 77, 144, 102, 113, 28, 142, 42, 38, 73, 0] ``` ``` La solución con pool de workers tomó 14.3951 segundos. ``` Al ejecutar estos mismo resultados con `timeit`, se obtuvierons los siguientes tiempos: ``` 13.6 s ± 8.41 s per loop (mean ± std. dev. of 15 runs, 10 loops each) ``` - Visualizar solución Para observar la ruta con la mejor solución encontrada se incluyó la función `plot_rout_map`, la cual se puede utilizar de la siguiente forma: ```python # visualizar solución y guardar mapa como html map_route = ac.plot_rout_map(coord_df, colony_mw.best_route, path_type='ants', save=True, save_as='map_aco_route') map_route ``` ![map_route](https://i.imgur.com/Ve9eXUj.jpg) _**Figura 6** Representación de los nodos y la ruta solución en un mapa._ Una mejor visualización del mapa que permite el flujo ordenado del viajero entre nodos se encuentra disponible [aquí](http://acotspslnroute.s3-website-us-east-1.amazonaws.com/). - Guardar solución en disco Posteriormente, se guarda la solución encontrada por la colonia en forma de diccionario en un archivo `JSON`: ```python # extraer mejor ruta sln_r = colony_mw.best_route # extraer mejor distancia sln_d = colony_mw.best_dist # diccionario con soluciones sln_dic = {'route': sln_r, 'distance': float(sln_d)} # guardar solución en disco with open("aco_sln.json", "w") as outfile: json.dump(sln_dic, outfile) outfile.close() ``` ### Comparación con la clase `colony` Adicionalmente, para comparar el desempeño con la clase `ant_colony` (que no incluye cómputo en paralelo), se instancía una clase `colony` con los mejores hiperparámetros encontrados en el problema. ```python # instanciar colony con mejores hp colony_old = ac.colony(G, init_node=0, verbose=True, k_verbose=10, **best_params) ``` A continuación se resuelve el problema: ```python start_time = time.time() colony_old.solve_tsp() end_time = time.time() ``` Con esto, se obtuvieron los siguientes resultados: ``` Resumen: Nro. de hormigas: 4 Iteraciones: 10 Distancia: 515.1653410440995 Nodo inicial: 0 Ruta: [0, 86, 85, 71, 83, 30, 135, 60, 79, 8, 35, 109, 56, 139, 74, 11, 63, 5, 147, 125, 80, 58, 27, 126, 117, 47, 90, 51, 132, 50, 112, 23, 48, 39, 92, 54, 110, 122, 121, 76, 40, 22, 119, 61, 96, 44, 72, 127, 12, 129, 26, 104, 66, 16, 17, 37, 99, 52, 133, 84, 143, 134, 21, 95, 46, 4, 43, 32, 19, 148, 36, 149, 145, 62, 75, 107, 108, 106, 123, 93, 115, 103, 53, 3, 81, 57, 6, 138, 7, 144, 14, 59, 67, 114, 68, 34, 70, 13, 118, 137, 18, 124, 65, 136, 101, 116, 31, 25, 130, 24, 87, 78, 120, 98, 140, 82, 94, 91, 128, 69, 41, 2, 33, 20, 105, 29, 1, 9, 73, 146, 142, 42, 141, 88, 64, 111, 45, 55, 15, 10, 77, 49, 100, 97, 131, 113, 38, 102, 89, 28, 0] ``` Al ejecutar con `timeit`, se obtuvo lo siguiente: ``` 1.43 s ± 524 ms per loop (mean ± std. dev. of 15 runs, 10 loops each) ``` **Conclusiones de la comparación:** De la anterior sección es importante notar dos resultados. Para la implementación que no incorpora cómputo en paralelo se obtiene una distancia mayor y un menor tiempo de cómputo. Esto es explicado por dos mecanismos que se explican a continuación. Primero, la selección de hiper-parámetros seleccionó un número de 10 iteraciones luego de muestrear 50 veces sobre el hiper-espacio. En este sentido, al ser un número reducido de iteraciones, resulta costoso en términos de tiempo de ejecución el levantamiento de los 4 sub-procesos utilizados en `colony_mtw`, y esto le permite a `colony` mejorar el tiempo de ejecución. Cuando se incrementa el número de iteraciones, es posible observar las ganancias en tiempo de ejecución de la implementación en paralelo como se explica en la sección 2.2. Por otro lado, al ser un problema que incorpora 150 nodos, hay $150!$ posibles rutas. En este sentido, existe un componente aleatorio que le permitió a la clase `colony_mtw` encontrar una mejor ruta que a la clase `colony`. Sin embargo, poder buscar en un número razonable de posibilidades implica un elevado número de iteraciones y/o de hormigas en la colonia. Dado lo anterior, es posible que se deba escalar la búsqueda de hiper-parámetros con que incorpore lo anterior y permita a las colonias hacer una búsqueda más detallada de rutas para esperar convergencia en las soluciones. ### Conclusiones generales y trabajo futuro Se implementó la librería ACO-TSP que es aplicable a la solución de problemas del viajero (TSP) utilizando conjuntos de datos reales. La librería se implementó en tres etapas: implementación con enfoque funcional, implementación con programación orientada a objetos, y robustecimiento (computo en paralelo, optimización de hiperparámetros, y visualización). Adicionalmente, implementó ACO-TSP utilizando `kale` y `kubeflow` con el fin de demostar su utilización en un flujo de trabajo que incorpore _pipelines_. Por otro lado, cabe mencionar que es posible incorporar en la librería como ejercicios de robustecimiento dos mejoras inmediatas. Inicialmente, el uso de cómputo asíncrono podría mejorar la implementación con computo en paralelo que utiliza sub-procesos. Por otro lado, la solución de problemas con datos geo-espaciales introduce otro tipo de restricciones, como el uso de rutas con ciertas características especiales. Por ejemplo, el uso de carreteras terrestres. En ese sentido, es necesario ajustar el algoritmo y la forma en que procesa los datos con rescursos adicionales al grafo y matriz de distancias asociados al problema. ## 4. Referencias 1. [Problema del Viajante](https://es.wikipedia.org/wiki/Problema_del_viajante) (2021) Wikipedia 2. [Programación Lineal (PL) y Método Símplex](https://itam-ds.github.io/analisis-numerico-computo-cientifico/IV.optimizacion_en_redes_y_prog_lineal/4.2/Programacion_lineal_y_metodo_simplex.html) (2021) Erick Palacios 3. [Data for the Traveling Salesperson Problem](https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html) (2019) People Sc 4. [Kochenderfer, M. J., & Wheeler, T. A. (2019). Algorithms for Optimization. Mit Press.](https://mitpress.mit.edu/books/algorithms-optimization) 5. [Cómputo en paralelo usando CPUs en un sistema de memoria compartida (SMC)](https://itam-ds.github.io/analisis-numerico-computo-cientifico/V.optimizacion_de_codigo/5.4/Computo_en_paralelo_usando_CPUS_en_SMC.html#multiprocessing) (2021) Erick Palacios

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.