ant_colony package

Submodules

ant_colony.aco_tsp module

ant_colony.aco_tsp.ant_colony(G, lenghts, init=0, graph=True, ants=200, max_iter=100, alpha=1, beta=5, rho=0.5, verbose=10)

Computa el algoritmo ant-colony para encontra la ruta con menor distancia en el problema TSP.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• lenghts (dic) – Diccionario de distancias

• init (int, optional) – Nodo inicial del recorrido. Defaults to 0.

• graph (bool, optional) – Grafica la mejor ruta encontrada. Default es True.

• ants (int, optional) – Número de hormigas por iteracion. Defaults to 200.

• max_iter (int, optional) – Número máximo de iteraciones. Defaults to 100.

• alpha (int, optional) – Factor de influencia de tau. Defaults to 1.

• beta (int, optional) – Factor de influencia de eta. Defaults to 5.

• rho (float, optional) – Tasa de evaporación de las feromonas. Defaults to .5.

• verbose (int, optional) – Imprime progreso del algoritmo cada K iteraciones. Defaults to 10.

Returns

Mejor ruta, mejor distancia

Return type

list, float

ant_colony.aco_tsp.hormiga_recorre(G, lenghts, dic_attr, tau, init_point, x_best, y_best)

Calcula la ruta y distancia más cortas con respecto al benchmark provisto, luego del recorrido (o su intento) de una hormiga por la red.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• lenghts (dic) – Diccionario de distancias

• dic_attr (dic) – [description]

• tau (dic) – Diccionario con niveles de feromonas de los vecinos de cada nodo

• init_point (int) – Nodo inicial del recorrido

• x_best (list) – Ruta con respecto a la cual se quiere mejorar

• y_best (float) – Distancia total del recorrido x_best

Returns

Mejor ruta, mejor distancia

Return type

list, float

ant_colony.aco_tsp_oo module

class ant_colony.aco_tsp_oo.ant(G, r_len=inf, route=[])

Bases: object

Clase que representa una hormiga de la colonia y realizará recorridos por el grafo.

Parameters

G (networkx graph) – Grafo con relaciones asociadas entre nodos

plot_route(plt_size)

Grafica la trayectoria encontrada por la colonia en el grafo.

Parameters

plt_size (tuple, optional) – Tamaño del gŕafico (ancho x altura). Defaults es (12, 8).

walk_over_graph(init_node, dist, atrac)

La hormiga intenta recorrer el grafo y volver al origen sin repetir otros nodos.

Parameters

• init_node (int) – Nodo inicial del recorrido.

• dist (dic) – Diccionario de distancias de las trayectorias.

• atrac (dic) – Diccionario de atracción de los nodos con

• a sus vecinos. (relación) –

class ant_colony.aco_tsp_oo.colony(G, init_node, best_route=[], best_dist=inf, n_ants=2, max_iter=100, alpha=1, beta=5, rho=0.5, verbose=False, k_verbose=100)

Bases: object

Clase que representa una colonia de hormigas que recorren el grafo asignado para resolver el problema TSP.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• init_node (int) – Nodo inicial del recorrido.

• best_route (list, optional) – Ruta con respecto a la cual se quiere mejorar.

• best_dist ([type], optional) – Distancia total del recorrido x_best.

• n_ants (int, optional) – Número de hormigas. Default es 2.

• max_iter (int, optional) – [description]. Default es 100.

• alpha (int, optional) – Factor de influencia de tau. Defaults to 1.

• beta (int, optional) – Factor de influencia de eta. Defaults to 5.

• rho (float, optional) – Tasa de evaporación de las feromonas. Defaults to .5.

• verbose (int, optional) – Imprime progreso del algoritmo cada K iteraciones. Defaults to 10.

plot_route(plt_size=(12, 8))

Grafica la trayectoria encontrada por la colonia en el grafo.

Parameters

plt_size (tuple, optional) – Tamaño del gŕafico (ancho x altura). Defaults es (12, 8).

solve_tsp()

Resuelve el problema TSP.

class ant_colony.aco_tsp_oo.colony_multiw(G, init_node, best_route=[], best_dist=inf, n_ants=2, max_iter=10, alpha=1, beta=5, rho=0.5, n_workers=1, verbose=False, k_verbose=10)

Bases: object

Clase que representa una colonia de hormigas que recorren el grafo asignado para resolver el problema TSP. A diferencia de la clase colony(), esta clase implementa multiprocesamiento para computar la solución del problema utilizando un pool de workers.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• init_node (int) – Nodo inicial del recorrido.

• best_route (list, optional) – Ruta con respecto a la cual se quiere mejorar.

• best_dist ([type], optional) – Distancia total del recorrido x_best.

• n_ants (int, optional) – Número de hormigas. Default es 2.

• max_iter (int, optional) – [description]. Default es 100.

• alpha (int, optional) – Factor de influencia de tau. Defaults to 1.

• beta (int, optional) – Factor de influencia de eta. Defaults to 5.

• rho (float, optional) – Tasa de evaporación de las feromonas. Defaults to .5.

• verbose (int, optional) – Imprime progreso del algoritmo cada K iteraciones. Defaults to 10.

plot_route(plt_size=(12, 8))

Grafica la trayectoria encontrada por la colonia en el grafo.

Parameters

plt_size (tuple, optional) – Tamaño del gŕafico (ancho x altura). Defaults es (12, 8).

solve_tsp()

Resuelve el problema TSP.

ant_colony.optim_hyper module

class ant_colony.optim_hyper.Objective(G, init_node)

Bases: object

Clase para definir la función objetivo a optimizar en la búsqueda de los mejores

hiper-parámetros del algoritmo. Minimiza tiempo + (distancia)^2.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos.

• init_node (int) – Nodo inicial del recorrido.

class ant_colony.optim_hyper.Objective_mp(G, init_node)

Bases: object

Clase para definir la función objetivo a optimizar en la búsqueda de los mejores

hiper-parámetros del algoritmo. Minimiza tiempo + (distancia)^2.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos.

• init_node (int) – Nodo inicial del recorrido.

ant_colony.optim_hyper.load_params(file)

Carga los mejores parámetros de un estudio previo.

Parameters

• file (db) – Base de datos con el estudio previo, correspondiente

• best_hiper_params. (a) –

Returns

Lista con los mejores hiperparámetros encontrados

Return type

[lst]

ant_colony.optim_hyper.optim_h_params(G, init_node, trials, save=False)

Genera estudio de optimización para buscar los mejores hiper-parámetros del algoritmo.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos.

• init_node (int) – Nodo inicial del recorrido.

• trials (int) – Numero de intentos para hacer el muestreo.

• save (bool, optional) – Se especifica si se quiere guardar el estudio en disco. Default es False.

Returns

Diccionario con la información del estudio de optimización

Return type

[dict]

ant_colony.optim_hyper.optim_h_params_mp(G, init_node, trials, save=False)

Genera estudio de optimización para buscar los mejores hiper-parámetros del algoritmo.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos.

• init_node (int) – Nodo inicial del recorrido.

• trials (int) – Numero de intentos para hacer el muestreo.

• save (bool, optional) – Se especifica si se quiere guardar el estudio en disco. Default es False.

Returns

Diccionario con la información del estudio de optimización

Return type

[dict]

ant_colony.optim_hyper.sample_params(trial)

Define el modo en que se va a hacer el meustro de los hiper-parametros del algoritmo en optuna. No está disponible para los usuarios.

Parameters

trial (optuna trial) – Ninguno

ant_colony.test_aco module

ant_colony.test_aco.revisar_ceros_diagonal(matriz)

Revisa si una matriz tiene ceros en la diagonal.

Parameters

matriz ([numpy matrix]) – [Matriz que se quiere revisar]

Returns

[Si la matriz posee solo ceros en la diagonal, regresa True, de lo contrario False]

Return type

[boolean]

ant_colony.test_aco.revisar_simetria(matriz, rtol=1e-05, atol=1e-08)

Revisa si la matriz ingresada es simétrica o no

Parameters

• matriz ([numpy matrix]) – Matriz a revisar.

• rtol ([float], optional) – [Parámetro de tolerancia relativa]. Defaults to 1e-05.

• atol ([float], optional) – [Parámetro de tolerancia absoluta]. Defaults to 1e-08.

Returns

[si la matriz es simétrica, regresará True, de lo contrario False]

Return type

[boolean]

ant_colony.test_aco.test_atracciones_por_nodo()

Revisa si existen n-1 atracciones para cada nodo, pues se quita el nodo actual.

ant_colony.test_aco.test_colony_multiw()

ant_colony.test_aco.test_compara_tiempos_colony_multiw_vs_colony()

ant_colony.test_aco.test_creacion_llaves_de_diccionario()

Prueba si existe una llave para cada nodo.

ant_colony.test_aco.test_diagonal_ceros()

Prueba si la matriz que genera la función “utils.rand_dist_matrix” tiene ceros en la diagonal.

ant_colony.test_aco.test_distancia_hormiga_dif_de_cero()

Revisa que la distancia de la hormiga sea distinta de cero.

ant_colony.test_aco.test_ejemplo_completo()

Revisa el ejemplo completo para ver si la distancia es cero. Pasa la prueba si es distinto a cero.

ant_colony.test_aco.test_feromonas_por_nodo()

Prueba si existe una feromona para cada nodo.

ant_colony.test_aco.test_hormiga_por_todo_nodo()

Prueba si la ruta de la hormiga cubre todos los nodos y regresa al nodo inicial.

ant_colony.test_aco.test_probar_matriz_cuadrada()

Prueba si la matriz que genera la función propia es cuadrada.

ant_colony.test_aco.test_solve_distance()

Revisa el ejemplo para resolver el TSP para el dataset de distancias de 17 ciudades.

ant_colony.utils module

ant_colony.utils.assign_ants_threats(n_ants, n_cpu=2)

Crea una lista para asignar el número de hormigas que procesará cada uno de los workers seleccionados. :param n_ants: Número de hormigas seleccionado para el algoritmo ACO-TSP. :type n_ants: int :param n_cpu: Número de cpu (s) o workers. Defaults es todos los cores. :type n_cpu: int, optional

Returns

Lista con la asignación de hormigas de cada worker.

Return type

[lst]

ant_colony.utils.atraccion_nodos(G, tau, eta, alpha=1, beta=5)

Calcula el grado de atracción de todos los nodos pertenicientes al grafo G.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• tau (dic) – Diccionario con niveles de feromonas de los vecinos de

• nodo (cada) –

• eta (dic) – Diccionario con nivel de atracción inicial de los vecinos

• cada nodo (de) –

• alpha (int, optional) – Factor de influencia de tau. Defaults to 1.

• beta (int, optional) – Factor de influencia de eta. Defaults to 5.

Returns

Diccionario con los valores de atracción de los vecinos del nodo j

Return type

(dic)

ant_colony.utils.create_dic_dist(dist)

Crea diccionario de distancias entre nodos a partir de la versión numérica de la matriz de distancias.

Parameters

dist (np.array) – Arreglo con la matriz de distancias

Returns

Diccionario de distancias de los nodos

Return type

(dic)

ant_colony.utils.create_dic_dist_from_graph(G)

Crea diccionario de distancias entre nodos a partir de un grafo.

Parameters

G (networkx graph) – Grafo con relaciones asociadas entre nodos

Returns

Diccionario de distancias de los nodos

Return type

(dic)

ant_colony.utils.flatten_list_of_list(list_of_list)

Convierte una lista de listas anidada en una lista simple.

Parameters

list_of_list (lst of lst) – Lista de listas.

Returns

Lista original removiendo un nivel de anidación.

Return type

[lst]

ant_colony.utils.graph_optim_path(G, route, dist, plt_size=(15, 6))

Grafica la ruta direccionada de un grafo asociado a una ruta

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• route (list) – Ruta con la direccion a graficar.

• dist (float) – Distancia asociada a la ruta.

• plt_size (tpl) – Tamaño de la gráfica en matplotlib.

ant_colony.utils.init_atrac(G, lenghts)

Inicialización de diccionario con nivel de atracción a priori de los nodos utilizando la inversa de las distancias.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• lenghts (dic) – Diccionario de distancias

Returns

Diccionario con nivel de atracción inicial de las trayectorias de los nodos

Return type

(dic)

ant_colony.utils.init_ferom(G, init_lev=1.0)

Inicialización de diccionario con nivel de feromonas de los nodos.

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• init_lev (float, optional) – Nivel de inicialización de feromona para

• las trayectorias de los nodos. Default es 1.0. (todas) –

Returns

Diccionario con nivel de feronomas de las trayectorias

Return type

(dic)

ant_colony.utils.plot_graph(G, m_plot, seed=19511959)

Grafica red en su versión de coordenadas o de grafo. Fija las posiciones de forma deterministica con una semilla (seed).

Parameters

• G (networkx graph) – Grafo con relaciones asociadas entre nodos

• m_plot (str) – Tipo de gráfico - coordinate: Coordenadas X, Y - graph: Grafo

• seed (int, optional) – Semilla para determinar las posiciones de los

• en la (nodos) – visualización. Default es 19511959.

ant_colony.utils.plot_nodes_map(df, save=False, save_as='path')

Genera gŕafico con nodos numerados.

Parameters

• df (df) – df con coordenadas de cada nodo. Debe incluir cols ‘lat’ y ‘lon’.

• save (bool, optional) – Indica si guardar el mapa como html. Default es False.

• save_as (str, optional) – Nombre del mapa a guardar como html.

Returns

Mapa con los nodos de cada ubicación.

Return type

[folium map]

ant_colony.utils.plot_rout_map(df, route, path_type='ants', nodes=True, save=False, save_as='path')

Genera gŕafico con ruta entre nodos, y nodos numerados.

Parameters

• df (df) – df con coordenadas de cada nodo. Debe incluir cols ‘lat’ y ‘lon’.

• route (lst) – Ruta con identificador de los nodos a graficar en el mapa.

• only_nodes (str, optional) – Indica si solo se quieren graficar los nodos. Default es True.

• path_type (str, optional) – Tipo de línea para la trayectoria. Opciones son ‘plain’ y ‘ants’. Default es ‘ants’.

• nodes (bool, optional) – Indica si graficar los nodos. Default es True.

• save (bool, optional) – Indica si guardar el mapa como html. Default es False.

• save_as (str, optional) – Nombre del mapa a guardar como html.

Returns

Mapa con los nodos conectados por la ruta provista.

Return type

[folium map]

ant_colony.utils.rand_dist_matrix(n_points, graph=True, scale_factor=1, round_factor=4, seed=1951959, int=False)

Crea matriz aleatoria de distancias. Retorna su versión numérica en numpy o su versión en grafo con networksx.

Parameters

• n_points (int) – Número de nodos de la matriz de distancias.

• graph (bool, optional) – Retorna la matriz como un grafo de networkx.

• es True. (Default) –

• scale_factor (int, optional) – Factor de escala de la matriz. Default

• 1. (es) –

• round_factor (int, optional) – Factor de redondeo de la matriz. Default es 4.

• seed (int, optional) – Semilla aleatoria. Default es 1951959.

• int (bool, optional) – Retorna matriz de enteros. Default es False.

Returns

Matrix de distancias o grafo no direccionado

Return type

(mat or graph)

ant_colony.utils.read_coord_data(path, n_cities, seed=1999, coord_df=False)

Basado en la solución propuesta en el siguiente repositorio: https://github.com/DiegoVicen/som-tsp Convierte en grafo datos de matrices de coordenadas leídas desde un archivo .tsp.

Parameters

• path (str) – Ruta del archivo.

• n_cities (int) – número de ciudades a samplear.

• seed (int) – seed para el sampleo.

• coord_df (bool) – Si se quiere retornar df con coordenadas.

Returns

Grafo asociado a la matriz de distancias ó df con coordenadas.

Return type

(graph networkx or df)

ant_colony.utils.read_data(path)

Convierte en grafo datos de matrices de distancias en formato .txt o .tsp

Parameters

path (str) – Ruta del archivo.

Returns

Grafo asociado a la matriz de distancias.

Return type

(graph networkx)

Module contents