Ilustración de las Colonias de Hormigas

En este documento ilustramos en un ejemplo sintético el uso de colonias de hormigas.

library(gor)

Generemos ciudades sintéticas en el plano cartesiano

set.seed(1983)
n_ciudades <- 15

coordenadas <- runif(2*n_ciudades)
coordenadas <- matrix(coordenadas, ncol = 2)
colnames(coordenadas) <- c("x", "y")
print(coordenadas)
##                x          y
##  [1,] 0.49319755 0.70236259
##  [2,] 0.15261823 0.31818244
##  [3,] 0.21661634 0.68486914
##  [4,] 0.74725932 0.29570244
##  [5,] 0.90768396 0.38514283
##  [6,] 0.22101631 0.55308640
##  [7,] 0.40837886 0.49382173
##  [8,] 0.24202834 0.17677996
##  [9,] 0.04808401 0.24457210
## [10,] 0.29068538 0.98635836
## [11,] 0.97708322 0.06421638
## [12,] 0.77338029 0.30696297
## [13,] 0.51691657 0.74022191
## [14,] 0.77302817 0.23343207
## [15,] 0.49504537 0.01622783

Veamos las ciudades en el plano cartesiano:

plot(coordenadas, las = 1, main = "Ubicación de las ciudades", xlim = c(0,2))
grid()

distancias <- compute_distance_matrix(coordenadas)
print(distancias)
##             [,1]      [,2]      [,3]       [,4]      [,5]      [,6]      [,7]
##  [1,] 0.00000000 0.5134089 0.2771339 0.47949959 0.5219457 0.3104287 0.2251300
##  [2,] 0.51340886 0.0000000 0.3722296 0.59506586 0.7580290 0.2446593 0.3102622
##  [3,] 0.27713387 0.3722296 0.0000000 0.65805219 0.7532664 0.1318562 0.2706880
##  [4,] 0.47949959 0.5950659 0.6580522 0.00000000 0.1836727 0.5858141 0.3925445
##  [5,] 0.52194575 0.7580290 0.7532664 0.18367267 0.0000000 0.7069070 0.5109958
##  [6,] 0.31042875 0.2446593 0.1318562 0.58581414 0.7069070 0.0000000 0.1965122
##  [7,] 0.22512996 0.3102622 0.2706880 0.39254454 0.5109958 0.1965122 0.0000000
##  [8,] 0.58251444 0.1672986 0.5087243 0.51903843 0.6975045 0.3768926 0.3580335
##  [9,] 0.63851249 0.1278510 0.4714495 0.70104238 0.8710179 0.3536759 0.4381070
## [10,] 0.34880478 0.6822914 0.3104545 0.82792836 0.8614798 0.4388375 0.5064031
## [11,] 0.80085949 0.8626942 0.9815904 0.32619752 0.3283444 0.9003505 0.7127310
## [12,] 0.48460626 0.6208634 0.6729035 0.02844477 0.1554013 0.6047171 0.4100515
## [13,] 0.04467572 0.5575218 0.3053591 0.50065492 0.5279965 0.3501095 0.2692461
## [14,] 0.54607784 0.6261718 0.7165121 0.06739163 0.2028505 0.6378840 0.4480758
## [15,] 0.68613725 0.4565446 0.7242955 0.37645442 0.5535060 0.6027512 0.4853937
##            [,8]      [,9]     [,10]     [,11]      [,12]      [,13]      [,14]
##  [1,] 0.5825144 0.6385125 0.3488048 0.8008595 0.48460626 0.04467572 0.54607784
##  [2,] 0.1672986 0.1278510 0.6822914 0.8626942 0.62086344 0.55752183 0.62617179
##  [3,] 0.5087243 0.4714495 0.3104545 0.9815904 0.67290353 0.30535906 0.71651206
##  [4,] 0.5190384 0.7010424 0.8279284 0.3261975 0.02844477 0.50065492 0.06739163
##  [5,] 0.6975045 0.8710179 0.8614798 0.3283444 0.15540131 0.52799651 0.20285053
##  [6,] 0.3768926 0.3536759 0.4388375 0.9003505 0.60471705 0.35010950 0.63788398
##  [7,] 0.3580335 0.4381070 0.5064031 0.7127310 0.41005151 0.26924614 0.44807577
##  [8,] 0.0000000 0.2054512 0.8110393 0.7436237 0.54706719 0.62692134 0.53401337
##  [9,] 0.2054512 0.0000000 0.7804500 0.9463444 0.72797481 0.68225560 0.72502975
## [10,] 0.8110393 0.7804500 0.0000000 1.1495598 0.83341015 0.33431079 0.89417703
## [11,] 0.7436237 0.9463444 1.1495598 0.0000000 0.31689239 0.81776331 0.26508945
## [12,] 0.5470672 0.7279748 0.8334102 0.3168924 0.00000000 0.50347488 0.07353173
## [13,] 0.6269213 0.6822556 0.3343108 0.8177633 0.50347488 0.00000000 0.56782840
## [14,] 0.5340134 0.7250297 0.8941770 0.2650895 0.07353173 0.56782840 0.00000000
## [15,] 0.2996575 0.5019119 0.9914213 0.4844207 0.40248882 0.72432436 0.35277772
##           [,15]
##  [1,] 0.6861372
##  [2,] 0.4565446
##  [3,] 0.7242955
##  [4,] 0.3764544
##  [5,] 0.5535060
##  [6,] 0.6027512
##  [7,] 0.4853937
##  [8,] 0.2996575
##  [9,] 0.5019119
## [10,] 0.9914213
## [11,] 0.4844207
## [12,] 0.4024888
## [13,] 0.7243244
## [14,] 0.3527777
## [15,] 0.0000000

Generemos el recorrido óptimo

recorrido_optimizado <- search_tour_ants(distancias, n_ciudades)

Veamos la solución con el menor costo:

print(recorrido_optimizado$tour)
##  [1]  1  7  4 14 12  5 11 15  8  9  2  6  3 10 13

El menor costo fue:

print(recorrido_optimizado$distance)
## [1] 3.42568

Veamos la mejor solución en el plano cartesiano

plot_tour_2(coordenadas, recorrido_optimizado, xlim = c(0,1))
grid()