Tercera Evaluación - Algoritmo de Optimización Colonia de Hormigas

Juan Jose Villa Ramirez

Juan Felipe Agudelo Sánchez

Prof. Luis Fernando Galindres

Facultad de Ingenierías, Universidad Tecnológica de Pereira

Computación Blanda

12/11/2024
Primer Punto
1. El objetivo es comparar el desempeño del algoritmo realizado por ustedes, basado en el que
hicimos en clase comparándolo con el benchmark existente en la literatura de manera
estandarizada (TSPLIB), para eso se deben realizar los siguientes puntos:

● Usar las instancias para el TSP Simétrico:

○ [Link]

● Las instancias se clasifican en pequeñas (10-20 ciudades),

● medianas(50-100 ciudades)
● grandes (>101 ciudades)
● Escoger aleatoriamente, 3 instancias de cada clasificación (en total 9 instancias)
● Desarrollar un script que cargue las instancias seleccionadas

Código 1 - Comparación Colonia de Hormigas hecho en clase con los resultados reales

import numpy as np
import [Link] as plt
import time

# Definir las instancias de ciudades

bayg29 = [Link]([ #1500 iteraciones y 20 hormigas
[1150.0, 1760.0],[630.0, 1660.0], [40.0, 2090.0],[750.0,
1100.0],[750.0, 2030.0],
[1030.0, 2070.0],[1650.0, 650.0], [1490.0, 1630.0],[790.0,
2260.0],[710.0, 1310.0],
[840.0, 550.0],[1170.0, 2300.0],[970.0, 1340.0],[510.0, 700.0],[750.0,
900.0],[1280.0, 1200.0],
[230.0, 590.0], [460.0, 860.0],[1040.0, 950.0],[590.0, 1390.0],[830.0,
1770.0],[490.0, 500.0],[1840.0, 1240.0],
[1260.0, 1500.0],[1280.0, 790.0], [490.0, 2130.0], [1460.0, 1420.0],
[1260.0, 1910.0],[360.0, 1980.0]])

ulysses16 = [Link]([#1000 iteraciones y 20 hormigas

[38.24, 20.42],[39.57, 26.15],[40.56, 25.32],[36.26, 23.12],[33.48,
10.54],[37.56, 12.19],[38.42, 13.11],
[37.52, 20.44],[41.23, 9.10],[41.17, 13.05],[36.08, -5.21],[38.47,
15.13],[38.15, 15.35],[37.51, 15.17],[35.49, 14.32],
[39.36, 19.56]])
burma14 = [Link]([#1000 iteraciones y 20 hormigas
[16.47, 96.10],[16.47, 94.44],[20.09, 92.54],[22.39, 93.37],[25.23,
97.24],[22.00, 96.05],[20.47, 97.02],[17.20, 96.29],[16.30, 97.38],
[14.05, 98.12],[16.53, 97.38],[21.52, 95.59], [19.41, 97.13],[20.09,
94.55]])

#######################
# Ciudades Medianas (50 - 100 Ciudades)

berlin52 = [Link]([
[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0,
655.0], [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0],
[580.0, 1175.0], [650.0, 1130.0], [1605.0, 620.0], [1220.0, 580.0],
[1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0], [725.0, 370.0],
[145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
[300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0],
[975.0, 580.0], [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0],
[660.0, 180.0], [410.0, 250.0], [420.0, 555.0], [575.0, 665.0], [1150.0,
1160.0],
[700.0, 580.0], [685.0, 595.0], [685.0, 610.0], [770.0, 610.0],
[795.0, 645.0], [720.0, 635.0], [760.0, 650.0], [475.0, 960.0], [95.0,
260.0],
[875.0, 920.0], [700.0, 500.0], [555.0, 815.0], [830.0, 485.0],
[1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0], [1340.0,
725.0],
[1740.0, 245.0]
])

pr76 = [Link]([
[3600, 2300],[3100, 3300],[4700, 5750],[5400, 5750],[5608,
7103],[4493, 7102],[3600, 6950],[3100, 7250],[4700, 8450],[5400, 8450],
[5610, 10053],[4492, 10052],[3600, 10800],[3100, 10950],[4700,
11650],[5400, 11650],[6650, 10800],[7300, 10950],[7300, 7250],[6650,
6950],
[7300, 3300],[6650, 2300],[5400, 1600],[8350, 2300],[7850,
3300],[9450, 5750],[10150, 5750],[10358, 7103],[9243, 7102],[8350, 6950],
[7850, 7250],[9450, 8450],[10150, 8450],[10360, 10053],[9242,
10052],[8350, 10800],[7850, 10950],[9450, 11650],[10150, 11650],
 [11400, 10800],[12050, 10950],[12050, 7250],[11400, 6950],[12050,
3300],[11400, 2300],[10150, 1600],[13100, 2300],[12600, 3300],
[14200, 5750],[14900, 5750],[15108, 7103],[13993, 7102],[13100,
6950],[12600, 7250],[14200, 8450],[14900, 8450],[15110, 10053],
[13992, 10052],[13100, 10800],[12600, 10950],[14200, 11650],[14900,
11650],[16150, 10800],[16800, 10950],[16800, 7250],[16150, 6950],
[16800, 3300],[16150, 2300],[14900, 1600],[19800, 800],[19800,
10000],[19800, 11900],[19800, 12200],[200, 12200],[200, 1100],[200, 800]])

st70 = [Link]([
[3600, 2300],[3100, 3300],[4700, 5750],[5400, 5750],[5608,
7103],[4493, 7102],[3600, 6950],[3100, 7250],[4700, 8450],[5400, 8450],
[5610, 10053],[4492, 10052],[3600, 10800],[3100, 10950],[4700,
11650],[5400, 11650],[6650, 10800],[7300, 10950],[7300, 7250],[6650,
6950],
[7300, 3300],[6650, 2300],[5400, 1600],[8350, 2300],[7850,
3300],[9450, 5750],[10150, 5750],[10358, 7103],[9243, 7102],[8350, 6950],
[7850, 7250],[9450, 8450],[10150, 8450],[10360, 10053],[9242,
10052],[8350, 10800],[7850, 10950],[9450, 11650],[10150, 11650],[11400,
10800],
[12050, 10950],[12050, 7250],[11400, 6950],[12050, 3300],[11400,
2300],[10150, 1600],[13100, 2300],[12600, 3300],[14200, 5750],
[14900, 5750],[15108, 7103],[13993, 7102],[13100, 6950],[12600,
7250],[14200, 8450],[14900, 8450],[15110, 10053],[13992, 10052],
[13100, 10800],[12600, 10950],[14200, 11650],[14900, 11650],[16150,
10800],[16800, 10950],[16800, 7250],[16150, 6950],[16800, 3300],
[16150, 2300],[14900, 1600],[19800, 800],[19800, 10000],[19800,
11900],[19800, 12200],[200, 12200],[200, 1100],[200, 800]])

############################
# Ciudades Grandes (101+)

rd100 = [Link]([
[143.775, 862.63],[881.78, 1.18319],[545.244, 735.005],[502.813,
876.001],[204.876, 345.225],[701.637, 576.987],[147.167, 164.286],
[135.382, 807.91],[628.999, 976.971],[674.999, 731.447],[313.696,
299.126],[445.689, 981.97],[354.793, 765.215],[398.129, 976.034],
[273.041, 853.944],[666.295, 312.27],[876.942, 925.39],[134.026,
949.816],[966.825, 726.799],[659.346, 889.08],[400.34, 874.489],
 [118.041, 312.04],[809.87, 50.8555],[16.2821, 114.161],[12.6192,
48.2407],[650.039, 940.261],[791.189, 758.951],[907.194, 612.605],
[510.857, 25.8629],[31.6366, 431.221],[776.763, 253.781],[531.819,
906.89],[654.965, 767.759],[186.06, 206.527],[564.595, 2.99685],
[410.816, 437.921],[930.189, 639.817],[941.392, 889.979],[341.538,
39.4141],[162.622, 95.1969],[107.558, 262.746],[82.6398, 131.129],
[43.0137, 77.901],[554.45, 99.7819],[608.618, 227.863],[889.589,
760.96],[559.461, 508.125],[13.6027, 508.467],[402.567, 839.178],
[886.156, 764.31],[84.6462, 629.068],[486.783, 259.062],[647.516,
553.517],[967.65, 824.246],[236.623, 1.52397],[879.518, 737.584],
[509.84, 420.787],[936.134, 303.893],[872.343, 499.018],[142.996,
840.984],[233.102, 303.929],[199.819, 937.721],[302.123, 847.44],
[365.531, 566.229],[107.593, 549.471],[802.657, 344.868],[319.486,
813.104],[3.24542, 701.539],[180.027, 766.307],[977.601, 968.843],
[14.6301, 842.383],[922.626, 954.285],[896.272, 789.067],[667.952,
906.108],[425.058, 869.541],[865.918, 369.61],[898.572, 539.108],
[621.689, 878.159],[673.73, 613.117],[89.2979, 491.923],[147.858,
459.84],[428.293, 905.37],[51.7499, 636.336],[826.458, 231.701],
[426.249, 946.357],[316.069, 853.389],[275.713, 973.754],[835.293,
247.974],[970.187, 63.5213],[123.616, 644.17],[226.668, 562.456],
[808.92, 791.39],[942.256, 531.023],[705.831, 455.757],[856.231,
509.763],[352.477, 1.16433],[308.882, 842.792],[750.979, 394.934],
[610.775, 584.408],[483.637, 116.325]])

u159 = [Link]([
[3300.00, 2200.00],[3500.00, 2900.00],[3300.00, 2900.00],[3500.00,
3100.00],[3500.00, 3300.00],[3300.00, 3500.00],[3500.00, 3700.00],
[3500.00, 3900.00],[3500.00, 4000.00],[3500.00, 4100.00],[3500.00,
4300.00],[3300.00, 4300.00],[3500.00, 4500.00],[3500.00, 4700.00],
[3500.00, 4800.00],[3300.00, 4900.00],[3500.00, 5000.00],[3800.00,
5500.00],[3900.00, 5700.00],[3800.00, 5800.00],[3700.00, 5800.00],
[3500.00, 5600.00],[3500.00, 5700.00],[3300.00, 5900.00],[3500.00,
6100.00],[3300.00, 6500.00],[3500.00, 6400.00],[3800.00, 6600.00],
[4500.00, 6500.00],[4700.00, 6100.00],[4300.00, 5700.00],[4500.00,
5400.00],[5100.00, 5300.00],[5100.00, 5000.00],[5000.00, 5000.00],
[5100.00, 4700.00],[5000.00, 4700.00],[5200.00, 4500.00],[5500.00,
4400.00],[5600.00, 4400.00],[5500.00, 4100.00],[5700.00, 3900.00],
[5900.00, 4100.00],[6100.00, 3900.00],[6300.00, 4100.00],[6500.00,
4100.00],[6700.00, 4100.00],[6900.00, 4100.00],[7000.00, 4500.00],
 [7300.00, 4500.00],[7300.00, 4700.00],[7400.00, 5100.00],[7700.00,
5500.00],[7800.00, 5700.00],[7300.00, 6200.00],[7300.00, 6500.00],
[7600.00, 6500.00],[7700.00, 6600.00],[8100.00, 6600.00],[8500.00,
6300.00],[8500.00, 6000.00],[8500.00, 5700.00],[8200.00, 5700.00],
[8500.00, 5300.00],[8500.00, 5200.00],[8500.00, 5100.00],[8500.00,
5000.00],[8500.00, 4900.00],[8500.00, 4800.00],[8500.00, 4700.00],
[8500.00, 4600.00],[8500.00, 4500.00],[8200.00, 4600.00],[7800.00,
4600.00],[7700.00, 4300.00],[8000.00, 4300.00],[8100.00, 4000.00],
[8500.00, 4200.00],[8500.00, 4100.00],[8500.00, 4000.00],[8500.00,
3900.00],[8500.00, 3800.00],[8500.00, 3700.00],[8500.00, 3600.00],
[8500.00, 3500.00],[8500.00, 3400.00],[8200.00, 3200.00],[8000.00,
3200.00],[7800.00, 3400.00],[7600.00, 3400.00],[7400.00, 3400.00],
[7300.00, 3000.00],[7300.00, 2800.00],[7700.00, 3200.00],[8000.00,
2900.00],[8100.00, 3000.00],[8500.00, 3100.00],[8500.00, 3000.00],
[8500.00, 2900.00],[8500.00, 2800.00],[8500.00, 2700.00],[8500.00,
2600.00],[8500.00, 2500.00],[8500.00, 2400.00],[8500.00, 2300.00],
[8200.00, 2100.00],[7800.00, 2100.00],[6900.00, 2200.00],[6700.00,
2300.00],[6500.00, 2300.00],[6300.00, 2300.00],[6100.00, 2300.00],
[5900.00, 2300.00],[5900.00, 2900.00],[6100.00, 2900.00],[6300.00,
2900.00],[6500.00, 2900.00],[6700.00, 2900.00],[6700.00, 3500.00],
[6500.00, 3500.00],[6300.00, 3500.00],[6100.00, 3500.00],[5900.00,
3500.00],[5300.00, 2800.00],[4700.00, 2100.00],[4300.00, 2600.00],
[4700.00, 2900.00],[5000.00, 3100.00],[5100.00, 2900.00],[5300.00,
3100.00],[5000.00, 3400.00],[5200.00, 3700.00],[5000.00, 3900.00],
[5100.00, 3900.00],[5100.00, 4200.00],[5000.00, 4200.00],[4700.00,
4400.00],[4700.00, 4700.00],[4300.00, 4400.00],[4300.00, 4600.00],
[4100.00, 4400.00],[3900.00, 4600.00],[3700.00, 4400.00],[3700.00,
4300.00],[3800.00, 4300.00],[3700.00, 4100.00],[3700.00, 4000.00],
[3700.00, 3900.00],[3800.00, 4000.00],[3900.00, 3800.00],[3700.00,
3700.00],[3500.00, 3600.00],[3500.00, 3500.00],[3700.00, 3500.00],
[3800.00, 3500.00],[3700.00, 3200.00],[3800.00, 3200.00],[3900.00,
3000.00],[3500.00, 2400.00]])

p107 = [Link]([
[8375, 4700],[8775, 4700],[8375, 4900],[8175, 4900],[8775,
4900],[8575, 4900],[8775, 5400],[8375, 5450],[8775, 5600],[8575, 5600],
[8375, 5650],[8175, 5650],[8375, 6200],[8775, 6200],[8375,
6400],[8175, 6400],[8775, 6400],[8575, 6400],[8375, 7000],[8775, 7000],
[8375, 7200],[8175, 7200],[8775, 7200],[8575, 7200],[8375,
7800],[8775, 7800],[8375, 8000],[8175, 8000],[8775, 8000],[8575, 8000],
 [8375, 8700],[8775, 8700],[8375, 8900],[8175, 8900],[8775,
8900],[8575, 8900],[8375, 9600],[8775, 9600],[8375, 9800],[8175, 9800],
[8775, 9800],[8575, 9800],[8375, 10500],[8775, 10450],[8375,
10700],[8175, 10700],[8775, 10650],[8575, 10650],[8375, 11300],[8775,
11300],
[8375, 11500],[8175, 11500],[8775, 11500],[8575, 11500],[15825,
11500],[15825, 10700],[15825, 9800],[15825, 8900],[15825, 8000],
[15825, 7200],[15825, 6400],[15825, 5650],[15825, 4900],[16025,
4700],[16425, 4700],[16025, 4900],[16225, 4900],[16425, 4900],
[16425, 5400],[16025, 5450],[16225, 5600],[16425, 5600],[16025,
5650],[16025, 6200],[16425, 6200],[16025, 6400],[16225, 6400],
[16425, 6400],[16025, 7000],[16425, 7000],[16025, 7200],[16225,
7200],[16425, 7200],[16025, 7800],[16425, 7800],[16025, 8000],
[16225, 8000],[16425, 8000],[16025, 8700],[16425, 8700],[16025,
8900],[16225, 8900],[16425, 8900],[16025, 9600],[16425, 9600],
[16025, 9800],[16225, 9800],[16425, 9800],[16025, 10500],[16425,
10450],[16025, 10700],[16225, 10650],[16425, 10650],[16025, 11300],
[16425, 11300],[16025, 11500],[16225, 11500]])

instancias = [burma14, ulysses16, bayg29, berlin52, pr76, st70, u159,

p107, rd100]
nombres_instancias = ["burma14", "ulysses16", "bayg29", "berlin52",
"pr76", "st70", "u159", "p107", "rd100"]

# Funciones para calcular matriz de distancia, two_opt y el algoritmo ACO

def matriz_d(nodos):
n = [Link][0]
matriz = [Link]([n, n])
for i in range(n):
for j in range(n):
matriz[i, j] = [Link]((nodos[i, 0] - nodos[j, 0]) ** 2 +
(nodos[i, 1] - nodos[j, 1]) ** 2)
return matriz

def distance(c1, c2):

return [Link]([Link]((c1 - c2) ** 2))

def two_opt(path, distance_matrix):

best_path = path
improved = True
 while improved:
improved = False
for i in range(1, len(path) - 2):
for j in range(i + 1, len(path)):
if j - i == 1:
continue
new_path = path[:i] + path[i:j][::-1] + path[j:]
new_path_len = sum(distance_matrix[new_path[k], new_path[k
+ 1]] for k in range(len(new_path) - 1)) + distance_matrix[new_path[-1],
new_path[0]]
best_path_len = sum(distance_matrix[best_path[k],
best_path[k + 1]] for k in range(len(best_path) - 1)) +
distance_matrix[best_path[-1], best_path[0]]

if new_path_len < best_path_len:

best_path = new_path
improved = True
path = best_path
return best_path

# Función para ejecutar el ACO con parámetros predeterminados

def aco_tsp(nombre, nodos):
cities = nodos
ncities = len(cities)
tho = [Link]((ncities, ncities), 0.1) # Inicializar feromonas en 0.1

best_path = []
bestplength = [Link]
dij = matriz_d(cities)
alpha = beta = 1
ro = 0.3
delta = 0.5
maxiter = 1000
nants = 20

# Ciclo principal del ACO

for iter in range(maxiter):

paths = []
pathlens = []
 for ant in range(nants):

s = [Link](ncities)
currentcity = [Link](ncities)
s[currentcity] = True
path = [currentcity]
pathlen = 0

while False in s:

unvisited = [Link](s == False)[0]

pij = [Link](len(unvisited))

for j, unvisitedcity in enumerate(unvisited):

pij[j] = tho[currentcity, unvisitedcity] * alpha * (1
/ dij[currentcity, unvisitedcity]) ** beta

pij /= [Link](pij)
nextcity = [Link](unvisited, p=pij)
[Link](nextcity)
pathlen += distance(cities[currentcity], cities[nextcity])
currentcity = nextcity
s[currentcity] = True

[Link](path)
[Link](pathlen)

if pathlen < bestplength:

bestplength = pathlen
best_path = path

tho *= (1 - ro)
for path, pathlen in zip(paths, pathlens):
for i in range(ncities - 1):
tho[path[i], path[i + 1]] += delta / pathlen
tho[path[-1], path[0]] += delta / pathlen

# Aplicamos two_opt para mejorar el mejor camino encontrado

best_path = two_opt(best_path, dij)
 # Recalcular la longitud del camino optimizado
best_path_length_original = 0
for i in range(len(best_path) - 1):
best_path_length_original += distance(nodos[best_path[i]],
nodos[best_path[i + 1]])
best_path_length_original += distance(nodos[best_path[-1]],
nodos[best_path[0]])

print(f"Best path length after 2-opt optimization for {nombre}:

{best_path_length_original}")

# Visualización final del camino optimizado

fig = [Link](figsize=(8, 6))
ax = fig.add_subplot(111)

[Link](cities[:, 0], cities[:, 1], c='r', marker='o')

for i in range(ncities - 1):
[Link]([cities[best_path[i], 0], cities[best_path[i + 1], 0]],
[cities[best_path[i], 1], cities[best_path[i + 1], 1]],
c='g', linestyle='-', linewidth=2, marker='o')

[Link]([cities[best_path[0], 0], cities[best_path[-1], 0]],

[cities[best_path[0], 1], cities[best_path[-1], 1]],
c='g', linestyle='-', linewidth=2, marker='o')

ax.set_title(f"Optimized Path for {nombre}")

ax.set_xlabel('X Coordinate')
ax.set_ylabel('Y Coordinate')
[Link]()
[Link]()

# Menú de selección
def Menu():
while True:
print("Instancias Cargadas:")
for i, nombre in enumerate(nombres_instancias,1):
print(f" {i}. {nombre}")

try:
 opcion = int(input("Ingrese el número correspondiente a la
instancia (o '0' para salir): "))

if opcion == 0:
print("Saliendo del menú.")
break
elif 1 <= opcion <= len(instancias):
nodos = instancias[opcion - 1] # Ajustar índice (0-based)
print(f"Has seleccionado la instancia
'{nombres_instancias[opcion - 1]}'")
aco_tsp(nombres_instancias[opcion - 1], instancias[opcion
- 1])
else:
print("Opción no válida. Por favor, elige un número de la
lista.")
except ValueError:
print("Entrada inválida. Por favor, ingresa un número.")

# Iniciar el programa
Menu()

Punto Dos
2. Diseñar un experimento que permita encontrar los valores de los parámetros adecuados
con los que se obtiene la mejor solución para cada instancia, para eso definir las siguientes
variables (independientes) experimentales:

● Número de hormigas (10, 20, 30, etc)

● Alpha (0.5, 1.0, 1.5, etc)
● Beta (0.5, 1.0, 1.5, etc)
● Rho (0.1, 0.3, 0.5, etc)
● N (20, 50, 200, etc)
● Establecer el número máximo de iteraciones (1000, 2000)

Código 2 - Experimento para Solución Óptima

import numpy as np
import [Link] as plt
import pandas as pd
import time
from itertools import product

# Definir las instancias de ciudades

bayg29 = [Link]([ #1500 iteraciones y 20 hormigas
[1150.0, 1760.0],[630.0, 1660.0], [40.0, 2090.0],[750.0,
1100.0],[750.0, 2030.0],
[1030.0, 2070.0],[1650.0, 650.0], [1490.0, 1630.0],[790.0,
2260.0],[710.0, 1310.0],
[840.0, 550.0],[1170.0, 2300.0],[970.0, 1340.0],[510.0, 700.0],[750.0,
900.0],[1280.0, 1200.0],
[230.0, 590.0], [460.0, 860.0],[1040.0, 950.0],[590.0, 1390.0],[830.0,
1770.0],[490.0, 500.0],[1840.0, 1240.0],
[1260.0, 1500.0],[1280.0, 790.0], [490.0, 2130.0], [1460.0, 1420.0],
[1260.0, 1910.0],[360.0, 1980.0]])

ulysses16 = [Link]([#1000 iteraciones y 20 hormigas

[38.24, 20.42],[39.57, 26.15],[40.56, 25.32],[36.26, 23.12],[33.48,
10.54],[37.56, 12.19],[38.42, 13.11],
[37.52, 20.44],[41.23, 9.10],[41.17, 13.05],[36.08, -5.21],[38.47,
15.13],[38.15, 15.35],[37.51, 15.17],[35.49, 14.32],
[39.36, 19.56]])

burma14 = [Link]([#1000 iteraciones y 20 hormigas

[16.47, 96.10],[16.47, 94.44],[20.09, 92.54],[22.39, 93.37],[25.23,
97.24],[22.00, 96.05],[20.47, 97.02],[17.20, 96.29],[16.30, 97.38],
[14.05, 98.12],[16.53, 97.38],[21.52, 95.59], [19.41, 97.13],[20.09,
94.55]])

#######################
# Ciudades Medianas (50 - 100 Ciudades)

berlin52 = [Link]([
[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0,
655.0], [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0],
[580.0, 1175.0], [650.0, 1130.0], [1605.0, 620.0], [1220.0, 580.0],
[1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0], [725.0, 370.0],
[145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
[300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0],
 [975.0, 580.0], [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0],
[660.0, 180.0], [410.0, 250.0], [420.0, 555.0], [575.0, 665.0], [1150.0,
1160.0],
[700.0, 580.0], [685.0, 595.0], [685.0, 610.0], [770.0, 610.0],
[795.0, 645.0], [720.0, 635.0], [760.0, 650.0], [475.0, 960.0], [95.0,
260.0],
[875.0, 920.0], [700.0, 500.0], [555.0, 815.0], [830.0, 485.0],
[1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0], [1340.0,
725.0],
[1740.0, 245.0]
])

pr76 = [Link]([
[3600, 2300],[3100, 3300],[4700, 5750],[5400, 5750],[5608,
7103],[4493, 7102],[3600, 6950],[3100, 7250],[4700, 8450],[5400, 8450],
[5610, 10053],[4492, 10052],[3600, 10800],[3100, 10950],[4700,
11650],[5400, 11650],[6650, 10800],[7300, 10950],[7300, 7250],[6650,
6950],
[7300, 3300],[6650, 2300],[5400, 1600],[8350, 2300],[7850,
3300],[9450, 5750],[10150, 5750],[10358, 7103],[9243, 7102],[8350, 6950],
[7850, 7250],[9450, 8450],[10150, 8450],[10360, 10053],[9242,
10052],[8350, 10800],[7850, 10950],[9450, 11650],[10150, 11650],
[11400, 10800],[12050, 10950],[12050, 7250],[11400, 6950],[12050,
3300],[11400, 2300],[10150, 1600],[13100, 2300],[12600, 3300],
[14200, 5750],[14900, 5750],[15108, 7103],[13993, 7102],[13100,
6950],[12600, 7250],[14200, 8450],[14900, 8450],[15110, 10053],
[13992, 10052],[13100, 10800],[12600, 10950],[14200, 11650],[14900,
11650],[16150, 10800],[16800, 10950],[16800, 7250],[16150, 6950],
[16800, 3300],[16150, 2300],[14900, 1600],[19800, 800],[19800,
10000],[19800, 11900],[19800, 12200],[200, 12200],[200, 1100],[200, 800]])

st70 = [Link]([
[3600, 2300],[3100, 3300],[4700, 5750],[5400, 5750],[5608,
7103],[4493, 7102],[3600, 6950],[3100, 7250],[4700, 8450],[5400, 8450],
[5610, 10053],[4492, 10052],[3600, 10800],[3100, 10950],[4700,
11650],[5400, 11650],[6650, 10800],[7300, 10950],[7300, 7250],[6650,
6950],
[7300, 3300],[6650, 2300],[5400, 1600],[8350, 2300],[7850,
3300],[9450, 5750],[10150, 5750],[10358, 7103],[9243, 7102],[8350, 6950],
 [7850, 7250],[9450, 8450],[10150, 8450],[10360, 10053],[9242,
10052],[8350, 10800],[7850, 10950],[9450, 11650],[10150, 11650],[11400,
10800],
[12050, 10950],[12050, 7250],[11400, 6950],[12050, 3300],[11400,
2300],[10150, 1600],[13100, 2300],[12600, 3300],[14200, 5750],
[14900, 5750],[15108, 7103],[13993, 7102],[13100, 6950],[12600,
7250],[14200, 8450],[14900, 8450],[15110, 10053],[13992, 10052],
[13100, 10800],[12600, 10950],[14200, 11650],[14900, 11650],[16150,
10800],[16800, 10950],[16800, 7250],[16150, 6950],[16800, 3300],
[16150, 2300],[14900, 1600],[19800, 800],[19800, 10000],[19800,
11900],[19800, 12200],[200, 12200],[200, 1100],[200, 800]])

############################
# Ciudades Grandes (101+)

rd100 = [Link]([
[143.775, 862.63],[881.78, 1.18319],[545.244, 735.005],[502.813,
876.001],[204.876, 345.225],[701.637, 576.987],[147.167, 164.286],
[135.382, 807.91],[628.999, 976.971],[674.999, 731.447],[313.696,
299.126],[445.689, 981.97],[354.793, 765.215],[398.129, 976.034],
[273.041, 853.944],[666.295, 312.27],[876.942, 925.39],[134.026,
949.816],[966.825, 726.799],[659.346, 889.08],[400.34, 874.489],
[118.041, 312.04],[809.87, 50.8555],[16.2821, 114.161],[12.6192,
48.2407],[650.039, 940.261],[791.189, 758.951],[907.194, 612.605],
[510.857, 25.8629],[31.6366, 431.221],[776.763, 253.781],[531.819,
906.89],[654.965, 767.759],[186.06, 206.527],[564.595, 2.99685],
[410.816, 437.921],[930.189, 639.817],[941.392, 889.979],[341.538,
39.4141],[162.622, 95.1969],[107.558, 262.746],[82.6398, 131.129],
[43.0137, 77.901],[554.45, 99.7819],[608.618, 227.863],[889.589,
760.96],[559.461, 508.125],[13.6027, 508.467],[402.567, 839.178],
[886.156, 764.31],[84.6462, 629.068],[486.783, 259.062],[647.516,
553.517],[967.65, 824.246],[236.623, 1.52397],[879.518, 737.584],
[509.84, 420.787],[936.134, 303.893],[872.343, 499.018],[142.996,
840.984],[233.102, 303.929],[199.819, 937.721],[302.123, 847.44],
[365.531, 566.229],[107.593, 549.471],[802.657, 344.868],[319.486,
813.104],[3.24542, 701.539],[180.027, 766.307],[977.601, 968.843],
[14.6301, 842.383],[922.626, 954.285],[896.272, 789.067],[667.952,
906.108],[425.058, 869.541],[865.918, 369.61],[898.572, 539.108],
[621.689, 878.159],[673.73, 613.117],[89.2979, 491.923],[147.858,
459.84],[428.293, 905.37],[51.7499, 636.336],[826.458, 231.701],
 [426.249, 946.357],[316.069, 853.389],[275.713, 973.754],[835.293,
247.974],[970.187, 63.5213],[123.616, 644.17],[226.668, 562.456],
[808.92, 791.39],[942.256, 531.023],[705.831, 455.757],[856.231,
509.763],[352.477, 1.16433],[308.882, 842.792],[750.979, 394.934],
[610.775, 584.408],[483.637, 116.325]])

u159 = [Link]([
[3300.00, 2200.00],[3500.00, 2900.00],[3300.00, 2900.00],[3500.00,
3100.00],[3500.00, 3300.00],[3300.00, 3500.00],[3500.00, 3700.00],
[3500.00, 3900.00],[3500.00, 4000.00],[3500.00, 4100.00],[3500.00,
4300.00],[3300.00, 4300.00],[3500.00, 4500.00],[3500.00, 4700.00],
[3500.00, 4800.00],[3300.00, 4900.00],[3500.00, 5000.00],[3800.00,
5500.00],[3900.00, 5700.00],[3800.00, 5800.00],[3700.00, 5800.00],
[3500.00, 5600.00],[3500.00, 5700.00],[3300.00, 5900.00],[3500.00,
6100.00],[3300.00, 6500.00],[3500.00, 6400.00],[3800.00, 6600.00],
[4500.00, 6500.00],[4700.00, 6100.00],[4300.00, 5700.00],[4500.00,
5400.00],[5100.00, 5300.00],[5100.00, 5000.00],[5000.00, 5000.00],
[5100.00, 4700.00],[5000.00, 4700.00],[5200.00, 4500.00],[5500.00,
4400.00],[5600.00, 4400.00],[5500.00, 4100.00],[5700.00, 3900.00],
[5900.00, 4100.00],[6100.00, 3900.00],[6300.00, 4100.00],[6500.00,
4100.00],[6700.00, 4100.00],[6900.00, 4100.00],[7000.00, 4500.00],
[7300.00, 4500.00],[7300.00, 4700.00],[7400.00, 5100.00],[7700.00,
5500.00],[7800.00, 5700.00],[7300.00, 6200.00],[7300.00, 6500.00],
[7600.00, 6500.00],[7700.00, 6600.00],[8100.00, 6600.00],[8500.00,
6300.00],[8500.00, 6000.00],[8500.00, 5700.00],[8200.00, 5700.00],
[8500.00, 5300.00],[8500.00, 5200.00],[8500.00, 5100.00],[8500.00,
5000.00],[8500.00, 4900.00],[8500.00, 4800.00],[8500.00, 4700.00],
[8500.00, 4600.00],[8500.00, 4500.00],[8200.00, 4600.00],[7800.00,
4600.00],[7700.00, 4300.00],[8000.00, 4300.00],[8100.00, 4000.00],
[8500.00, 4200.00],[8500.00, 4100.00],[8500.00, 4000.00],[8500.00,
3900.00],[8500.00, 3800.00],[8500.00, 3700.00],[8500.00, 3600.00],
[8500.00, 3500.00],[8500.00, 3400.00],[8200.00, 3200.00],[8000.00,
3200.00],[7800.00, 3400.00],[7600.00, 3400.00],[7400.00, 3400.00],
[7300.00, 3000.00],[7300.00, 2800.00],[7700.00, 3200.00],[8000.00,
2900.00],[8100.00, 3000.00],[8500.00, 3100.00],[8500.00, 3000.00],
[8500.00, 2900.00],[8500.00, 2800.00],[8500.00, 2700.00],[8500.00,
2600.00],[8500.00, 2500.00],[8500.00, 2400.00],[8500.00, 2300.00],
[8200.00, 2100.00],[7800.00, 2100.00],[6900.00, 2200.00],[6700.00,
2300.00],[6500.00, 2300.00],[6300.00, 2300.00],[6100.00, 2300.00],
 [5900.00, 2300.00],[5900.00, 2900.00],[6100.00, 2900.00],[6300.00,
2900.00],[6500.00, 2900.00],[6700.00, 2900.00],[6700.00, 3500.00],
[6500.00, 3500.00],[6300.00, 3500.00],[6100.00, 3500.00],[5900.00,
3500.00],[5300.00, 2800.00],[4700.00, 2100.00],[4300.00, 2600.00],
[4700.00, 2900.00],[5000.00, 3100.00],[5100.00, 2900.00],[5300.00,
3100.00],[5000.00, 3400.00],[5200.00, 3700.00],[5000.00, 3900.00],
[5100.00, 3900.00],[5100.00, 4200.00],[5000.00, 4200.00],[4700.00,
4400.00],[4700.00, 4700.00],[4300.00, 4400.00],[4300.00, 4600.00],
[4100.00, 4400.00],[3900.00, 4600.00],[3700.00, 4400.00],[3700.00,
4300.00],[3800.00, 4300.00],[3700.00, 4100.00],[3700.00, 4000.00],
[3700.00, 3900.00],[3800.00, 4000.00],[3900.00, 3800.00],[3700.00,
3700.00],[3500.00, 3600.00],[3500.00, 3500.00],[3700.00, 3500.00],
[3800.00, 3500.00],[3700.00, 3200.00],[3800.00, 3200.00],[3900.00,
3000.00],[3500.00, 2400.00]])

p107 = [Link]([
[8375, 4700],[8775, 4700],[8375, 4900],[8175, 4900],[8775,
4900],[8575, 4900],[8775, 5400],[8375, 5450],[8775, 5600],[8575, 5600],
[8375, 5650],[8175, 5650],[8375, 6200],[8775, 6200],[8375,
6400],[8175, 6400],[8775, 6400],[8575, 6400],[8375, 7000],[8775, 7000],
[8375, 7200],[8175, 7200],[8775, 7200],[8575, 7200],[8375,
7800],[8775, 7800],[8375, 8000],[8175, 8000],[8775, 8000],[8575, 8000],
[8375, 8700],[8775, 8700],[8375, 8900],[8175, 8900],[8775,
8900],[8575, 8900],[8375, 9600],[8775, 9600],[8375, 9800],[8175, 9800],
[8775, 9800],[8575, 9800],[8375, 10500],[8775, 10450],[8375,
10700],[8175, 10700],[8775, 10650],[8575, 10650],[8375, 11300],[8775,
11300],
[8375, 11500],[8175, 11500],[8775, 11500],[8575, 11500],[15825,
11500],[15825, 10700],[15825, 9800],[15825, 8900],[15825, 8000],
[15825, 7200],[15825, 6400],[15825, 5650],[15825, 4900],[16025,
4700],[16425, 4700],[16025, 4900],[16225, 4900],[16425, 4900],
[16425, 5400],[16025, 5450],[16225, 5600],[16425, 5600],[16025,
5650],[16025, 6200],[16425, 6200],[16025, 6400],[16225, 6400],
[16425, 6400],[16025, 7000],[16425, 7000],[16025, 7200],[16225,
7200],[16425, 7200],[16025, 7800],[16425, 7800],[16025, 8000],
[16225, 8000],[16425, 8000],[16025, 8700],[16425, 8700],[16025,
8900],[16225, 8900],[16425, 8900],[16025, 9600],[16425, 9600],
[16025, 9800],[16225, 9800],[16425, 9800],[16025, 10500],[16425,
10450],[16025, 10700],[16225, 10650],[16425, 10650],[16025, 11300],
[16425, 11300],[16025, 11500],[16225, 11500]])
instancias = [burma14, ulysses16, bayg29, berlin52, pr76, st70, u159,
p107, rd100]
nombres_instancias = ["burma14", "ulysses16", "bayg29", "berlin52",
"pr76", "st70", "u159", "p107", "rd100"]

# Función para calcular la matriz de distancias entre todas las ciudades

def matriz_d(nodos):
n = [Link][0]
matriz = [Link]([n, n])
for i in range(n):
for j in range(n):
matriz[i, j] = [Link]((nodos[i, 0] - nodos[j, 0])**2 +
(nodos[i, 1] - nodos[j, 1])**2)
return matriz

# Algoritmo 2-opt para optimización

def two_opt(path, distance_matrix):
best_path = path
improved = True
while improved:
improved = False
for i in range(1, len(path) - 2):
for j in range(i + 1, len(path)):
if j - i == 1:
continue
new_path = path[:i] + path[i:j][::-1] + path[j:]
new_path_len = sum(distance_matrix[new_path[k], new_path[k
+ 1]] for k in range(len(new_path) - 1)) + distance_matrix[new_path[-1],
new_path[0]]
best_path_len = sum(distance_matrix[best_path[k],
best_path[k + 1]] for k in range(len(best_path) - 1)) +
distance_matrix[best_path[-1], best_path[0]]

if new_path_len < best_path_len:

best_path = new_path
improved = True
path = best_path
return best_path
# Modificación en la construcción del camino de la hormiga dentro de la
función aco_tsp
def aco_tsp(nodos, nants, alpha, beta, rho, maxiter):
ncities = len(nodos)
tho = [Link]((ncities, ncities), 0.1) # Inicializar feromonas en 0.1
best_path = []
best_path_length = [Link]
dij = matriz_d(nodos) # Matriz de distancias

for iteration in range(maxiter):

paths = []
path_lengths = []

# Para cada hormiga

for ant in range(nants):
s = [Link](ncities)
current_city = [Link](ncities)
s[current_city] = True
path = [current_city]
path_length = 0

# Construcción del camino de la hormiga

while False in s:
unvisited = [Link](s == False)[0]
pij = [Link](len(unvisited))

for j, unvisited_city in enumerate(unvisited):

pij[j] = tho[current_city, unvisited_city]**alpha * (1
/ dij[current_city, unvisited_city])**beta

# Verificar si la suma de probabilidades es cero

if [Link](pij) == 0:
pij = [Link](len(unvisited)) / len(unvisited)
else:
pij /= [Link](pij)

next_city = [Link](unvisited, p=pij)

[Link](next_city)
path_length += [Link]([Link]((nodos[current_city] -
nodos[next_city])**2))
 current_city = next_city
s[current_city] = True

[Link](path)
path_lengths.append(path_length)

# Actualizar mejor solución

if path_length < best_path_length:
best_path_length = path_length
best_path = path

# Evaporación de feromonas
tho *= (1 - rho)

# Reforzar feromonas en cada camino encontrado

for path, path_length in zip(paths, path_lengths):
for i in range(ncities - 1):
tho[path[i], path[i + 1]] += 1.0 / path_length
tho[path[-1], path[0]] += 1.0 / path_length

# Aplicar two_opt para optimización final

best_path = two_opt(best_path, dij)
best_path_length = sum(dij[best_path[i], best_path[i + 1]] for i in
range(len(best_path) - 1)) + dij[best_path[-1], best_path[0]]

return best_path, best_path_length

# Parámetros para el experimento

num_hormigas = [10, 20, 30]
alphas = [0.5, 1.0, 1.5]
betas = [0.5, 1.0, 1.5]
rhos = [0.1, 0.3, 0.5]
max_iters = [500,1000,1500]

# Almacenar resultados
resultados = []

for nants, alpha, beta, rho, maxiter in product(num_hormigas, alphas,

betas, rhos, max_iters):
start_time = [Link]()
 best_path, best_path_length = aco_tsp(burma14, nants, alpha, beta,
rho, maxiter)
end_time = [Link]()

[Link]({
'Número de Hormigas': nants,
'Alpha': alpha,
'Beta': beta,
'Rho': rho,
'Iteraciones': maxiter,
'Longitud del Mejor Camino': best_path_length,
'Tiempo de Ejecución (s)': end_time - start_time
})

# Convertir los resultados a DataFrame y mostrar

df_resultados = [Link](resultados)
print(df_resultados)

# Visualización del mejor camino

mejor_resultado = df_resultados.loc[df_resultados['Longitud del Mejor
Camino'].idxmin()]
print("Mejor longitud de camino encontrada:", mejor_resultado['Longitud
del Mejor Camino'])
print("Parámetros con los que se encontró la mejor solución:")
print(mejor_resultado)

fig = [Link](figsize=(8, 6))

ax = fig.add_subplot(111)
[Link](pr76[:, 0], pr76[:, 1], c='r', marker='o')

mejor_camino, _ = aco_tsp(pr76, int(mejor_resultado['Número de

Hormigas']), mejor_resultado['Alpha'],
mejor_resultado['Beta'], mejor_resultado['Rho'],
int(mejor_resultado['Iteraciones']))

for i in range(len(mejor_camino) - 1):

[Link]([pr76[mejor_camino[i], 0], pr76[mejor_camino[i + 1], 0]],
[pr76[mejor_camino[i], 1], pr76[mejor_camino[i + 1], 1]],
c='g', linestyle='-', linewidth=2, marker='o')
# Conectar el último punto al primero para cerrar el ciclo
[Link]([pr76[mejor_camino[0], 0], pr76[mejor_camino[-1], 0]],
[pr76[mejor_camino[0], 1], pr76[mejor_camino[-1], 1]],
c='g', linestyle='-', linewidth=2, marker='o')

ax.set_xlabel('X Coordinate')
ax.set_ylabel('Y Coordinate')
[Link]("Mejor Camino con Parámetros Óptimos")
[Link]()
[Link]()
Conclusiones:

● La implementación del algoritmo de colonia de hormigas ha proporcionado una base

sólida para abordar problemas de optimización combinatoria, aprovechando su enfoque
inspirado en el comportamiento de las hormigas reales al encontrar caminos óptimos.

● Este algoritmo usa elementos clave, como la evaporación de feromonas y la heurística

basada en parámetros como alpha, beta, rho, etc., que afectan la forma en que las
hormigas encuentran y refuerzan rutas.

● Utilizar combinaciones de num_hormigas, alpha, beta, rho, N y max_iteraciones ha

permitido analizar la sensibilidad del algoritmo a estos valores y observar patrones de
comportamiento, como la convergencia y la rapidez en la optimización.

● Este enfoque de experimentación ha revelado la importancia de equilibrar ciertos

parámetros: por ejemplo, valores altos de alpha tienden a favorecer el enfoque en rutas
previamente exploradas, mientras que valores altos de beta promueven la exploración
basada en la heurística del problema. Ajustar rho ha sido importante para controlar la
evaporación de feromonas, evitando así la sobresaturación y el estancamiento en
soluciones subóptimas.

● El algoritmo ACO es sensible al número de iteraciones y al tamaño del problema. Las

pruebas experimentales con distintos valores de max_iteraciones y N han mostrado
cómo el algoritmo puede beneficiarse de un número de iteraciones suficientemente alto
para mejorar la precisión de las soluciones.

Posibles Mejoras

● Se podría explorar el uso de variantes del ACO que optimicen el rendimiento en

diferentes escenarios, como el uso de enfoques de colonia de hormigas paralelizados,
los cuales podrían reducir significativamente el tiempo de ejecución en instancias
grandes.