TRABAJO 1: OPTIMIZACIÓN HEURÍSTICA

REDES NEURONALES Y ALGORITMOS BIOINSPIRADOS




Presentado por:

Marcos David Carrillo Builes
Tomás Escobar Rivera
Jose Fernando López Ramírez
Esteban Vásquez Pérez



Profesor: Juan David Ospina Arango

Monitor: Andrés Mauricio Zapata Rincón


University Logo

Universidad Nacional de Colombia
Facultad de Minas
Ingeniería de Sistemas e Informática

07 de July de 2025

Tabla de contenidos

Introducción

En el ámbito de la investigación operativa y la inteligencia artificial, los algoritmos de optimización heurística se han consolidado como herramientas fundamentales para abordar problemas complejos de optimización. Estos algoritmos son particularmente efectivos cuando los métodos exactos resultan inviables debido a la elevada dimensionalidad del espacio de búsqueda o a la naturaleza intrínsecamente combinatoria de los problemas, donde el número de posibles soluciones crece exponencialmente.

A lo largo de las últimas décadas, se han desarrollado y perfeccionado una amplia variedad de algoritmos heurísticos, cada uno con características únicas que los hacen adecuados para diferentes tipos de problemas. Entre estos, se destacan algoritmos como los basados en poblaciones, como los Algoritmos Genéticos (GA) y Optimización de Enjambre de Partículas (PSO), así como las estrategias de optimización basadas en búsquedas locales, como el Algoritmo de Colonia de Hormigas (ACO).

El presente trabajo se enfoca en el análisis comparativo de varios de estos algoritmos para diferentes instancias de problemas de optimización. A través de este estudio, se busca identificar las ventajas, limitaciones y condiciones en las que cada enfoque presenta un mejor desempeño, proporcionando así una visión integral para la selección de métodos de optimización heurística en futuras investigaciones.

De esta forma, se espera contribuir al entendimiento de las fortalezas y debilidades de estas técnicas, facilitando la elección informada de algoritmos para aplicaciones prácticas en campos tan diversos como la ingeniería, la logística y las ciencias computacionales.

Verificación de la carga de paquetes

## Loading required package: gganimate
## Warning in library(package, lib.loc = lib.loc, character.only = TRUE,
## logical.return = TRUE, : there is no package called 'gganimate'
## Loading required package: sf
## Warning in library(package, lib.loc = lib.loc, character.only = TRUE,
## logical.return = TRUE, : there is no package called 'sf'
## No se instalaron los paquetes: gganimate, sf

Parte 1: Optimización Numérica

0. Exploración de las funciones

Función de Schwefel

\[ f(\mathbf{x}) = 418.9829d - \sum_{i=1}^d x_i \sin(\sqrt{|x_i|}) \quad \text{(1)} \]

Descripción:

Dimensiones: \(d\)

La función de Schwefel cuenta con múltiples mínimos locales.

Dominio:

La función se evalúa en el hipercubo: \(x_i \in [-500, 500]\), para todo \(i = 1, \dots, d\).

Mínimo Global:

\(f(\mathbf{x}^*) = 0\), en \(\mathbf{x}^* = (420.9687, \dots, 420.9687)\)

Definición de Función

# Función Schwefel
schwefel <- function(x) {
  A <- 418.9829
  d <- length(x)
  z <- A * d - sum(x * sin(sqrt(abs(x))))

  return(z)
}

Sabemos que la función de Schwefel tiene un mínimo local en \(x^*=(420.9687, \cdots, 420.9687)\)

schwefel(c(420.9687, 420.9687))
## [1] 2.545567e-05
schwefel(c(420.9687, 420.9687, 420.9687))
## [1] 3.818351e-05

Estos resultados representan valores aproximados a cero debido a errores de redondeo introducidos en la programación de la función.

Ahora vamos a visualizar la función:

plot_function(schwefel, highlight_x = 420.9687)
**Fig 1.** _Evaluación de Schwefel (2D)_

Fig 1. Evaluación de Schwefel (2D)

Fig 2. Evaluación de Schwefel (3D)

**Fig 3.** _Curvas de Nivel de Schwefel_

Fig 3. Curvas de Nivel de Schwefel

Función de Griewank

\[ f(\mathbf{x}) = 1 + \frac{1}{4000} \sum_{i=1}^{d} x_i^2 - \prod_{i=1}^{d} \cos\left(\frac{x_i}{\sqrt{i}}\right) \quad \text{(2)} \]

Descripción:

Dimensiones: \(d\)

La función de Griewank tiene una estructura ondulada con múltiples mínimos locales, pero un único mínimo global en el origen.

Dominio:

\(x_i \in [-600, 600]\), para todo \(i = 1, \dots, d\)

Mínimo Global:

\(f(\mathbf{0}) = 0\), en \(\mathbf{x} = (0, \dots, 0)\)

Definición de Función

# Función Griewank (2D y 3D)
griewank <- function(x) {
  sum_term <- sum(x^2) / 4000
  prod_term <- prod(cos(x / sqrt(seq_along(x))))
  return(1 + sum_term - prod_term)
}
griewank(c(0, 0))
## [1] 0
griewank(c(0, 0, 0))
## [1] 0

Estos resultados representan el mínimo global de la función de Griewank, que es 0 en el origen.

plot_function(griewank, x_range = c(-600, 600), highlight_x = 0)
**Fig 4.** *Evaluación de Griewank (2D)*

Fig 4. Evaluación de Griewank (2D)

Fig 5. Evaluación de Griewank (3D)

**Fig 6.** _Curvas de Nivel de Griewank_

Fig 6. Curvas de Nivel de Griewank

1. Optimización por descenso del gradiente o métodos Quasi-Newton

Como podemos ver, las funciones cuentan con varios mínimos locales que pueden hacer que un método numérico basado en el gradiente sea propenso a errores. Para ello vamos a ver cómo se comporta la solución del método optim(method = "BFGS") que es el más parecido al que vimos en clase. Este método Quasi-Newton optimiza la función utilizando una aproximación del gradiente y la matriz Hessiana, sin calcularlos directamente.

Antes de esto vamos a crear vectores para seguir las soluciones halladas.

## initial  value 790.168681 
## iter   2 value 765.448307
## iter   3 value 729.639629
## iter   4 value 679.713597
## iter   5 value 613.806275
## iter   6 value 533.106774
## iter   7 value 443.514431
## iter   8 value 355.131538
## iter   9 value 138.514178
## iter  10 value 122.084251
## iter  11 value 120.486081
## iter  12 value 118.438625
## iter  13 value 118.438347
## iter  13 value 118.438347
## final  value 118.438347 
## converged
## initial  value 34.562163 
## iter   2 value 33.384366
## iter   3 value 33.254622
## iter   4 value 33.184890
## iter   5 value 33.184711
## iter   5 value 33.184711
## iter   5 value 33.184711
## final  value 33.184711 
## converged
Tabla 1: Comparación de Óptimos en 2D
Función Óptimo_Global Óptimo_Obtenido
Schwefel f(420.9687, 420.9687) ≈ 0 (-302.5247) con valor 118.4383
Griewank f(0, 0) = 0 (364.2416) con valor 33.1847 
## initial  value 1508.888943 
## iter   2 value 1483.707203
## iter   3 value 1447.173577
## iter   4 value 1396.108891
## iter   5 value 1328.414538
## iter   6 value 1244.914455
## iter   7 value 1150.944012
## iter   8 value 1055.745413
## iter   9 value 473.273255
## iter  10 value 398.813939
## iter  11 value 398.132357
## iter  12 value 394.929298
## iter  13 value 394.916344
## iter  14 value 394.899954
## iter  14 value 394.899953
## iter  14 value 394.899953
## final  value 394.899953 
## converged
## initial  value 10.534395 
## iter   2 value 10.045718
## iter   3 value 9.513138
## iter   4 value 8.933348
## iter   5 value 8.884195
## iter   6 value 8.883244
## iter   7 value 8.883223
## iter   8 value 8.883221
## iter   8 value 8.883221
## iter   8 value 8.883221
## final  value 8.883221 
## converged
Tabla 2: Comparación de Óptimos en 3D
Función Óptimo_Global Óptimo_Obtenido
Schwefel f(420.9687, 420.9687) ≈ 0 (-25.8788, 420.9689) con valor 394.9
Griewank f(0, 0) = 0 (128.7406, -137.5913) con valor 8.8832

Más adelante vamos a visualizar estos métodos para tener una mejor forma de interpretar los resultados obtenidos. Además vamos a explicar por qué no se llega al óptimo global.

2. Métodos Heurísticos

Nos enfocaremos en tres poderosos métodos heurísticos inspirados en la naturaleza:

Algoritmos Evolutivos (GA), que emulan el proceso de selección natural para encontrar soluciones óptimas.

Optimización por Enjambre de Partículas (PSO), basada en el comportamiento colectivo de animales como aves o peces.

Estrategias de Evolución Diferencial (DE), un método robusto de optimización global que combina mutación, cruce y selección.

2.1 Algoritmo Genético (GA)

Creamos una tabla para ver los resultados con varios valores posibles y comparar las soluciones para así elegir los mejores parámetros. De una vez la generalizamos para los otros métodos.

Schwefel 2D
optimizer_test("GA", schwefel, "Schwefel", 2, -500, 500)
Tabla 3 . Resultados de GA para Schwefel 2 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
7 0.0000 200 30 200 0.1860
8 0.0005 200 50 200 0.2425
6 0.0007 100 100 100 0.1851
3 0.0009 50 100 50 0.1018
9 0.0087 200 100 200 0.3776
5 0.0089 100 50 100 0.1237
4 0.7756 100 30 100 0.1022
2 7.0688 50 50 50 0.0777
1 116.1439 50 30 50 0.0700

Elegimos el mejor resultado que obtenemos y llamamos a la función para guardar su historial y poder graficarlo después.

ga_schwefel_2d <- genetic_optimizer_with_history(schwefel, -500, 500, dim = 2, popSize = 30, maxiter = 200)
Schwefel 3D
optimizer_test("GA", schwefel, "Schwefel", 3, -500, 500)
Tabla 4 . Resultados de GA para Schwefel 3 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
9 0.0037 200 100 200 0.4275
7 0.1020 200 30 200 0.2083
8 0.2948 200 50 200 0.2701
1 0.6273 50 30 50 0.0545
5 0.6758 100 50 100 0.1397
6 1.0476 100 100 100 0.2114
4 2.3853 100 30 100 0.1034
3 21.9866 50 100 50 0.1129
2 128.1358 50 50 50 0.0666 
ga_schwefel_3d <- genetic_optimizer_with_history(schwefel, -500, 500, dim = 3, popSize = 30, maxiter = 200)
Griewank 2D
optimizer_test("GA", griewank, "Griewank", 2, -500, 500)
Tabla 5 . Resultados de GA para Griewank 2 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
1 0.0004 50 30 50 0.0573
5 0.0011 100 50 100 0.1340
2 0.0049 50 50 50 0.0695
7 0.0071 200 30 200 0.2138
9 0.0076 200 100 200 0.4287
6 0.0076 100 100 100 0.2204
4 0.0081 100 30 100 0.1050
8 0.0099 200 50 200 0.2718
3 0.0107 50 100 50 0.1134 
ga_griewank_2d <- genetic_optimizer_with_history(griewank, -600, 600, dim = 2, popSize = 100, maxiter = 100)
Griewank 3D
optimizer_test("GA", griewank, "Griewank", 3, -500, 500)
Tabla 6 . Resultados de GA para Griewank 3 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
7 0.0152 200 30 200 0.2166
3 0.0169 50 100 50 0.1049
6 0.0219 100 100 100 0.2349
9 0.0328 200 100 200 0.4418
8 0.0345 200 50 200 0.2872
5 0.0475 100 50 100 0.1341
2 0.1013 50 50 50 0.0658
4 0.1079 100 30 100 0.0968
1 0.1513 50 30 50 0.0498 
ga_griewank_3d <- genetic_optimizer_with_history(griewank, -600, 600, dim = 3, popSize = 100, maxiter = 100)

2.2 Optimización por Enjambre (PSO)

Schwefel 2D
optimizer_test("PSO", schwefel, "Schwefel", 2, -500, 500)
Tabla 7 . Resultados de PSO para Schwefel 2 D
Mejor Valor Iter Convergencia Tamaño Enjambre Máx Iteraciones Tiempo (s)
7 0.0000 3373 20 200 0.1310
9 0.0000 11963 60 200 0.3996
8 0.0000 7693 40 200 0.2521
4 0.0000 1831 20 100 0.0649
6 0.0000 5772 60 100 0.1930
2 0.0001 1975 40 50 0.0789
1 0.0003 987 20 50 0.0371
3 0.0044 2609 60 50 0.1041
5 118.4384 3830 40 100 0.1205 
pso_schwefel_2d <- pso_optimizer_with_history(schwefel, -500, 500, dim = 3, maxit = 200, s = 20)
Schwefel 3D
optimizer_test("PSO", schwefel, "Schwefel", 3, -500, 500)
Tabla 8 . Resultados de PSO para Schwefel 3 D
Mejor Valor Iter Convergencia Tamaño Enjambre Máx Iteraciones Tiempo (s)
9 0.0000 11285 60 200 0.4191
8 0.0000 7956 40 200 0.2926
6 0.0001 5408 60 100 0.1961
5 0.0015 3996 40 100 0.1219
1 0.6164 943 20 50 0.0298
3 1.7939 2951 60 50 0.0900
2 11.3273 1888 40 50 0.0630
7 118.4384 3949 20 200 0.1321
4 118.4385 1997 20 100 0.0697 
pso_schwefel_3d <- pso_optimizer_with_history(schwefel, -500, 500, dim = 3, maxit = 200, s = 40)
Griewank 2D
optimizer_test("PSO", griewank, "Griewank", 2, -600, 600)
Tabla 9 . Resultados de PSO para Griewank 2 D
Mejor Valor Iter Convergencia Tamaño Enjambre Máx Iteraciones Tiempo (s)
7 0.0000 3966 20 200 0.1660
9 0.0001 11039 60 200 0.4674
8 0.0048 7975 40 200 0.3729
4 0.0060 1997 20 100 0.0765
2 0.0074 1518 40 50 0.0644
5 0.0074 3692 40 100 0.1406
6 0.0087 5289 60 100 0.2406
3 0.0234 2552 60 50 0.1019
1 0.0400 928 20 50 0.0528 
pso_griewank_2d <- pso_optimizer_with_history(griewank, -600, 600, dim = 2, maxit = 200, s = 40)
Griewank 3D
optimizer_test("PSO", griewank, "Griewank", 3, -600, 600)
Tabla 10 . Resultados de PSO para Griewank 3 D
Mejor Valor Iter Convergencia Tamaño Enjambre Máx Iteraciones Tiempo (s)
7 0.0211 3961 20 200 0.1451
9 0.0218 11974 60 200 0.5213
5 0.0229 3934 40 100 0.1817
8 0.0298 7963 40 200 0.3199
4 0.0366 1990 20 100 0.0931
6 0.0561 5935 60 100 0.2474
1 0.1320 942 20 50 0.0879
3 0.1413 2653 60 50 0.1133
2 0.1713 1310 40 50 0.1162 
pso_griewank_3d <- pso_optimizer_with_history(griewank, -600, 600, dim = 2, maxit = 200, s = 60)

2.3 Evolución Diferencial (DE)

Schwefel 2D
optimizer_test("DE", schwefel, "Schwefel", 2, -500, 500)
Tabla 11 . Resultados de DE para Schwefel 2 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
7 0.0000 200 30 200 0.0356
8 0.0000 200 50 200 0.0444
9 0.0000 200 70 200 0.0598
4 0.0000 100 30 100 0.0156
5 0.0000 100 50 100 0.0225
6 0.0000 100 70 100 0.0489
3 0.0001 50 70 50 0.0154
2 0.0004 50 50 50 0.0123
1 0.0061 50 30 50 0.0233 
de_schwefel_2d <- de_optimizer_with_history(schwefel, -500, 500, dim = 2, NP = 30, itermax = 200)
Schwefel 3D
optimizer_test("DE", schwefel, "Schwefel", 3, -500, 500)
Tabla 12 . Resultados de DE para Schwefel 3 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
8 0.0000 200 50 200 0.0439
9 0.0000 200 70 200 0.0801
7 0.0000 200 30 200 0.0300
6 0.0000 100 70 100 0.0302
5 0.0003 100 50 100 0.0212
4 0.0035 100 30 100 0.0166
3 0.3471 50 70 50 0.0185
2 0.5456 50 50 50 0.0230
1 18.0467 50 30 50 0.0233 
de_schwefel_3d <- de_optimizer_with_history(schwefel, -500, 500, dim = 3, NP = 30, itermax = 200)
Griewank 2D
optimizer_test("DE", griewank, "Griewank", 2, -600, 600)
Tabla 13 . Resultados de DE para Griewank 2 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
9 0.0000 200 70 200 0.0724
8 0.0000 200 50 200 0.0578
7 0.0000 200 30 200 0.0437
6 0.0001 100 70 100 0.0592
2 0.0013 50 50 50 0.0150
5 0.0032 100 50 100 0.0268
4 0.0068 100 30 100 0.0186
1 0.0152 50 30 50 0.0098
3 0.0264 50 70 50 0.0200 
de_griewank_2d <- de_optimizer_with_history(griewank, -600, 600, dim = 2, NP = 70, itermax = 200)
Griewank 3D
optimizer_test("DE", griewank, "Griewank", 3, -600, 600)
Tabla 14 . Resultados de DE para Griewank 3 D
Mejor Valor Iter Convergencia Tamaño Población Máx Iteraciones Tiempo (s)
8 0.0077 200 50 200 0.0531
7 0.0079 200 30 200 0.0439
9 0.0080 200 70 200 0.0686
5 0.0171 100 50 100 0.0248
6 0.0229 100 70 100 0.0569
4 0.0439 100 30 100 0.0169
3 0.0592 50 70 50 0.0177
1 0.0671 50 30 50 0.0094
2 0.0701 50 50 50 0.0143 
de_griewank_3d <- de_optimizer_with_history(griewank, -600, 600, dim = 3, NP = 30, itermax = 200)

Nótese que a diferencia de los métodos clásicos como el descenso del gradiente, cada uno de los métodos heurísticos logra llegar al valor óptimo de 0.

Además, se puede observar que los resultados de Evolución Diferencial tienden a ser más eficientes y llegan a los óptimos en pocas iteraciones. Más adelante entraremos en detalle para comparar a estos algoritmos evolutivos.

3. Visualización de Resultados

3.1 Animación del Descenso de Gradiente

Para crear la animación debemos generar múltiples imágenes usando el historial de soluciones evaluadas en la función objetivo.

Schwefel

Camino de la solución en Schwefel 2D

**Fig 7.** *Camino de la solución en Schwefel 2D*

Fig 7. Camino de la solución en Schwefel 2D

Como podemos notar, los algoritmos numéricos dependen altamente de la elección del punto inicial \(x_0^*\). En el GIF se ve además que la solución se desplaza por fuera de la gráfica, esto se debe a que el optimizador podría estar explorando soluciones que se mueven en \(c(x1)\), pero al graficar los frames se pueden ver puntos intermedios en la solución. Sin embargo finalmente se vuelve a la gráfica cuando se está estabilizando el óptimo.

Camino de la solución en Schwefel 3D con curvas de nivel

**Fig 8.** *Camino de la solución en Schwefel 3D*

Fig 8. Camino de la solución en Schwefel 3D

Griewank

Camino de la solución en Griewank 2D

**Fig 9.** *Camino de la solución en Griewank 2D*

Fig 9. Camino de la solución en Griewank 2D

Camino de la solución en Griewank 3D con curvas de nivel

**Fig 10.** *Camino de la solución en Griewank 3D*

Fig 10. Camino de la solución en Griewank 3D

3.2 Animación de Métodos Heurísticos

**Fig 11.** *GA Schwefel 2D*

Fig 11. GA Schwefel 2D

**Fig 12.** *GA Schwefel 3D*

Fig 12. GA Schwefel 3D

**Fig 13.** *GA Griewank 2D*

Fig 13. GA Griewank 2D

**Fig 14.** *GA Griewank 3D*

Fig 14. GA Griewank 3D

**Fig 15.** *PSO Schwefel 2D*

Fig 15. PSO Schwefel 2D

**Fig 16.** *PSO Schwefel 3D*

Fig 16. PSO Schwefel 3D

**Fig 17.** *PSO Griewank 2D*

Fig 17. PSO Griewank 2D

**Fig 18.** *PSO Griewank 3D*

Fig 18. PSO Griewank 3D

**Fig 19.** *DE Schwefel 2D*

Fig 19. DE Schwefel 2D

**Fig 20.** *DE Schwefel 3D*

Fig 20. DE Schwefel 3D

**Fig 21.** *DE Griewank 2D*

Fig 21. DE Griewank 2D

**Fig 22.** *DE Griewank 3D*

Fig 22. DE Griewank 3D

4. Conclusiones

4.1. Métodos Clásicos (Descenso del Gradiente)

Los métodos clásicos presentan limitaciones importantes en escenarios complejos. Para funciones con múltiples mínimos locales o derivadas de difícil cálculo, como Schwefel y Griewank, el descenso del gradiente tiende a quedarse atrapado en óptimos locales que pueden estar lejos del global. En nuestras funciones de prueba, observamos que para Schwefel las soluciones halladas estaban muy alejadas del óptimo, mientras que en Griewank, aunque los resultados fueron algo mejores debido a su forma semi-cuadrática, el método también se asentó en mínimos no globales. Por este motivo, en optimización de funciones no convexas se suele preferir el uso de métodos heurísticos, los cuales analizamos a continuación.

En las visualizaciones (Figuras 7, 8, 9 y 10) se aprecia que, en Schwefel, el optimizador se mueve inicialmente pero pronto queda atrapado en un óptimo local. En Griewank, el punto apenas se desplaza desde su solución inicial debido a la naturaleza ondulada del paisaje de la función.

Nota: Aunque es posible encontrar mejores resultados seleccionando cuidadosamente la semilla inicial, un optimizador robusto no debería depender de esta elección.

4.2. Métodos Heurísticos

Nótese que el paso en cada gif es simplemente un medidor de tiempo de fotograma para referencia y no representa el paso del optimizador

4.2.1. Algoritmos Genéticos

En las Tablas 3, 4, 5 y 6 se presentan los resultados para la optimización de Schwefel y Griewank en 2D y 3D. Estos resultados muestran que los algoritmos genéticos logran alcanzar valores cercanos o iguales al mínimo esperado. Aunque en algunas animaciones el movimiento hacia el óptimo no se muestra completamente, los resultados numéricos evidencian el éxito del algoritmo. Esta discrepancia puede deberse a limitaciones en la resolución de los gráficos, la construcción de los frames o a la dinámica propia del algoritmo.

En las Figuras 11, 12, 13 y 14 se observa que, con poblaciones de 30 y 100 individuos, los algoritmos genéticos obtienen soluciones consistentes en tiempos de ejecución razonables.

4.2.2. Optimización por Enjambre de Partículas (PSO)

En la optimización mediante PSO se utilizaron tamaños de enjambre entre 20 y 60 partículas y máximos de 50 a 200 iteraciones, buscando balancear el tiempo de cómputo con la calidad de las soluciones.

Se observó que, en funciones como Schwefel, PSO puede requerir miles de iteraciones para llegar al óptimo global debido a la complejidad del paisaje de la función. Así, en algunos casos, las trayectorias de las partículas no alcanzan completamente el óptimo dentro del límite de iteraciones establecido, lo cual es un comportamiento esperado.

No se realizaron ajustes manuales de hiperparámetros, pues el objetivo era analizar el desempeño del algoritmo bajo configuraciones estándar.

A pesar de ello, los resultados numéricos en las Tablas 7, 8, 9 y 10 demuestran que PSO es capaz de encontrar el óptimo global, a cambio de un mayor número de iteraciones, sin comprometer gravemente la eficiencia del método.

4.2.3. Evolución Diferencial

Los métodos de Evolución Diferencial mostraron el mejor desempeño entre los métodos analizados. Según las Tablas 11, 12, 13 y 14, este algoritmo encontró consistentemente el óptimo global en Schwefel y Griewank, tanto en 2D como en 3D, utilizando poblaciones de entre 30 y 70 individuos.

Aunque en algunas visualizaciones no se observa claramente el desplazamiento progresivo hacia el óptimo, esto se debe a la dinámica exploratoria del algoritmo, que prueba soluciones diversas antes de converger. Sin embargo, los resultados numéricos avalan que el algoritmo logra alcanzar el óptimo en todos los casos.

Esto resalta la importancia de utilizar las visualizaciones como una herramienta de apoyo para entender la dinámica del algoritmo, pero siempre confirmando los resultados a través de los valores numéricos obtenidos.

4.3. Conclusión General

La comparación entre métodos clásicos y heurísticos en la optimización de funciones complejas como Schwefel y Griewank muestra una clara ventaja de los métodos heurísticos. Mientras que el descenso del gradiente tiende a quedarse atrapado en óptimos locales, los algoritmos evolutivos y de enjambre, como los algoritmos genéticos, PSO y evolución diferencial, logran encontrar soluciones globales con alta efectividad.

Aunque las visualizaciones no siempre muestran de manera explícita el camino completo hacia el óptimo debido a limitaciones gráficas o a la propia naturaleza de los algoritmos, los resultados numéricos confirman la eficacia de los métodos heurísticos. Esto subraya la importancia de complementar las herramientas visuales con un análisis riguroso de los datos obtenidos.

En resumen, para problemas de optimización de alta complejidad y con múltiples óptimos locales, los métodos heurísticos se presentan como la mejor alternativa frente a los métodos clásicos de optimización.

Parte 2: Optimización Combinatoria

Un vendedor debe hacer un recorrido por todas y cada de las 13 ciudades principales de Colombia.

Utilice colonias de hormigas y algoritmos genéticos para encontrar el orden óptimo. El costo de desplazamiento entre ciudades es la suma del valor de la hora del vendedor (es un parámetro que debe estudiarse), el costo de los peajes y el costo del combustible. Cada equipo debe definir en qué carro hace el recorrido el vendedor y de allí extraer el costo del combustible.

Adicionalmente represente con un gif animado o un video cómo se comporta la mejor solución usando un gráfico del recorrido en el mapa de Colombia.

Procedimiento de levantamiento de datos

Definición de ciudades principales

Para el presente trabajo, se seleccionaron las 15 ciudades principales de Colombia que forman parte del recorrido del vendedor:

  • Palmira
  • Pasto
  • Tuluá
  • Bogotá
  • Pereira
  • Armenia
  • Manizales
  • Valledupar
  • Montería
  • Soledad
  • Cartagena
  • Barranquilla
  • Medellín
  • Bucaramanga
  • Cúcuta

Construcción de la matriz de costos

Con el fin de modelar correctamente el problema, se procedió a levantar los datos de desplazamiento entre cada par de ciudades.
Se creó una matriz origen-destino que contempla para cada trayecto:

  • Tiempo estimado de viaje (en horas).
  • Distancia recorrida (en kilómetros).
  • Costo de peajes (en pesos colombianos - COP).
  • Costo total estimado de desplazamiento, calculado como la suma de:
    • Costo de la hora del vendedor multiplicado por el tiempo de viaje.
    • Costo de los peajes entre ciudades.
    • Costo de combustible estimado a partir de la distancia recorrida y el rendimiento del vehículo seleccionado.

Un ejemplo parcial de esta matriz es el siguiente:

Posteriormente, esta información se reorganizó en una matriz de costos finales que resume el costo total de desplazamiento entre las ciudades principales, como se muestra a continuación:

Esta matriz servirá como entrada para los algoritmos de optimización (Colonias de Hormigas y Algoritmos Genéticos) para determinar el recorrido óptimo.

Vehículo seleccionado

Para modelar el desplazamiento del vendedor, se seleccionó un Jeep Wrangler de características similares a las especificadas en el sitio oficial (Jeep, n.d.):

Este vehículo fue elegido por su robustez, fiabilidad para trayectos largos y condiciones variables de carretera.

El consumo promedio de combustible reportado para este tipo de vehículo es de aproximadamente 0,117 litros por kilómetro como máximo.

Cálculo del costo del combustible

El precio de la gasolina en Colombia, actualizado para el momento del análisis, es de (Ministerio de Minas y Energía de Colombia, 2024):

  • 15.827 COP por galón.

Dado que:

  • 1 galón equivale a 3,78541 litros,

el precio de la gasolina por litro se calcula como:

\[ \text{Precio por litro} = \frac{15.827 \, \text{COP}}{3.78541 \, \text{litros}} \approx 4181,05 \, \text{COP/litro} \quad \text{(3)} \]

El Jeep Wrangler seleccionado presenta un consumo promedio de:

  • 0,117 litros por kilómetro recorrido

Así, el costo de combustible para cada trayecto se determina como:

\[ \text{Costo de combustible} = \text{Distancia recorrida (km)} \times 0.117 \times 4181.05\quad \text{(4)} \]

Simplificando:

\[ \text{Costo de combustible} = \text{Distancia recorrida (km)} \times 489.18 \, \text{COP/km}\quad \text{(5)} \]

donde:

\[ 489.18 \, \text{COP/km} = 0.117 \times 4181.05 \quad \text{(6)} \]

Este valor representa el costo de combustible por cada kilómetro recorrido.

Cálculo del costo de la hora del vendedor

Supuestos considerados

Para calcular el costo por hora del vendedor, se tuvieron en cuenta los siguientes conceptos:

  • Salario mínimo por hora:
    Se consideró el salario mínimo dividido entre una jornada laboral de 8 horas diarias (Ministerio de Trabajo de Colombia, 2025):

    \[ \text{Salario mínimo por hora} = 6.189 \, \text{COP/hora} \quad \text{(7)} \]

  • Costo de alimentación diario:
    Se estimó un costo promedio de alimentación de 30.000 COP, y se asumieron tres comidas diarias, por lo que (DANE, n.d.):

    \[ \text{Costo alimentación diaria} = 30.000 \times 3 = 90.000 \, \text{COP/día} \quad \text{(8)} \]

  • Costo de hospedaje diario:
    Se asignó un costo estimado de hospedaje de 150.000 COP por noche (DANE, n.d.):

    \[ \text{Costo hospedaje diario} = 150.000 \, \text{COP/día} \quad \text{(9)} \]

Suma total de costos diarios

La suma total de costos asociados por día es:

\[ \text{Costo total diario} = (6.189 \times 8) + 90.000 + 150.000 \quad \text{(10)} \]

Calculando:

\[ \text{Costo total diario} = 49.512 + 90.000 + 150.000 = 289.512 \, \text{COP} \quad \text{(11)} \]

Cálculo del costo de hora real

Dado que en un día hay 24 horas, el costo de la hora del vendedor considerando todos los factores es:

\[ \text{Costo hora vendedor} = \frac{289.512}{24} \approx 12.063 \, \text{COP/hora} \quad \text{(12)} \]

Así, para cada trayecto entre ciudades, el costo asociado al tiempo del vendedor será:

\[ \text{Costo asociado al tiempo} = \text{Duración del trayecto (horas)} \times 12.063 \, \text{COP} \quad \text{(13)} \]

Este componente se sumará al costo de los peajes y al costo del combustible para determinar el costo total del recorrido.

\[ \text{Costo total} = \text{Tiempo viaje (hr)} \cdot \text{Costo hora vendedor (COP)} + \text{Distancia (km)} \cdot \text{Costo gasolina (COP/km)} + \text{Peajes (COP)} \quad \text{(14)} \]

Obtención de tiempos y distancias

Para obtener los datos de distancia (en kilómetros) y tiempo estimado de recorrido (en horas) entre ciudades, se utilizó Google Maps (Google, n.d.).

  • Google Maps es una de las herramientas más actualizadas en cuanto a redes viales, condiciones del tráfico y estimaciones de viaje en Colombia.
  • Permite calcular la mejor ruta considerando vías principales, velocidades promedio y restricciones actuales en las carreteras (como obras, cierres o desvíos).
  • Es ampliamente confiable y aceptado en trabajos académicos y de ingeniería de transporte para estimaciones realistas de tiempo y distancia.
  • Facilita extraer información de recorridos interurbanos de manera precisa y gratuita.

Obtención de costos de peajes

El valor de los peajes entre ciudades fue obtenido directamente de la plataforma oficial del Instituto Nacional de Vías de Colombia (INVIAS), específicamente a través de su sistema HERMES SIV.

  • INVIAS es el ente oficial encargado del mantenimiento, control y actualización de las tarifas de peajes en el territorio nacional.
  • El sistema HERMES proporciona datos actualizados y categorizados según el tipo de vehículo.
  • Para este estudio, se asumió que el Jeep Wrangler corresponde a la Categoría 1, por lo que se utilizaron los valores de peaje correspondientes a dicha categoría en todas las rutas analizadas.
  • Esta fuente garantiza que los costos de peaje reflejan los valores oficiales y vigentes en Colombia.

Optimización de la obtención de datos

Con el fin de optimizar el proceso de obtención de los datos de distancia y tiempo estimado entre ciudades, se desarrolló un pequeño procedimiento automático utilizando programación en Python.

Lógica seguida para la automatización

  1. Lectura de datos iniciales:
    • Se partió de un archivo CSV que contenía las combinaciones de ciudades origen y destino.
  2. Conexión a Google Maps API:
    • Se utilizó la API de Google Maps Directions para consultar, de manera programática, la distancia y duración de cada trayecto (Google, n.d.).
    • Se configuró el API para realizar búsquedas específicas dentro de Colombia, agregando automáticamente “, Colombia” a las ciudades ingresadas.
  3. Consulta de rutas:
    • Para cada par de ciudades, se realizó una petición a la API de Google Maps (Google, n.d.).
    • Se extrajeron dos datos principales:
      • Tiempo de recorrido: obtenido en segundos y convertido a horas.
      • Distancia recorrida: obtenida en metros y convertida a kilómetros.
  4. Actualización del conjunto de datos:
    • Los valores de tiempo y distancia se incorporaron automáticamente en el mismo DataFrame utilizado en el proceso.
    • Se aplicó una pequeña pausa de 1 segundo entre consultas para evitar sobrecargar la API y respetar sus límites de uso.
  5. Almacenamiento de resultados:
    • El DataFrame final, ya completado con los datos de tiempo y distancia, se guardó en un nuevo archivo CSV para su posterior análisis y modelamiento. Además se guardo el xlsx con la metodología de costos. Todo se encuentra en la carpeta src/files/input.
## [1] "Ruta Vecino más cercano: Palmira -> Tuluá -> Armenia -> Pereira -> Manizales -> Medellín -> Bucaramanga -> Cúcuta -> Valledupar -> Soledad -> Barranquilla -> Cartagena -> Montería -> Bogotá -> Pasto -> Palmira"
## [1] "Costo total: 3887351 $ Pesos"
## [1] "Ruta Colonia de Hormigas: Palmira -> Tuluá -> Armenia -> Pereira -> Manizales -> Medellín -> Montería -> Cartagena -> Barranquilla -> Soledad -> Valledupar -> Cúcuta -> Bucaramanga -> Bogotá -> Pasto -> Palmira"
## [1] "Costo total: 3613332 $ Pesos"

Crear un gráfico que dibuje la ruta óptima.

**Fig 22.** *Mejor Ruta usando Colonia de Hormigas*

Fig 22. Mejor Ruta usando Colonia de Hormigas

**Fig 23.** *Mejor Ruta usando K-Vecino más cercano*

Fig 23. Mejor Ruta usando K-Vecino más cercano

Conclusiones

Modelamiento adecuado del problema:

Se logró representar correctamente el problema del viajante de comercio (TSP), incorporando no solo las distancias entre ciudades, sino también variables contextuales relevantes del territorio colombiano, como el costo de peajes, el consumo de combustible y la tarifa por hora del vendedor. Esta aproximación realista permite obtener soluciones más útiles y aplicables a escenarios logísticos reales.

Importancia de los datos de entrada:

La calidad y precisión de la matriz de costos fue clave para garantizar resultados confiables. Esta matriz fue generada automáticamente a partir de la API de Google Maps, combinando factores económicos como precios de combustible y tarifas, lo que permitió construir una representación detallada y actualizada del problema.

Comparación de algoritmos:

  • El algoritmo de Vecino Más Cercano produjo una ruta con un costo total de 3,887,351 pesos, siendo una heurística determinista y voraz que toma decisiones locales inmediatas, sin considerar el impacto global. Aunque es computacionalmente eficiente, tiende a quedarse atrapado en soluciones subóptimas.

  • Por su parte, el algoritmo de Colonia de Hormigas logró una ruta con un costo total de 3,613,332 pesos, lo que representa una mejora del 7.05% respecto al Vecino Más Cercano. Este enfoque estocástico es capaz de explorar un espacio de soluciones más amplio, evitando óptimos locales mediante el uso de feromonas, memoria colectiva y exploración probabilística.

Consideraciones finales:

Aunque ACO requiere mayor tiempo de cómputo y ajuste de parámetros, su desempeño superior en esta instancia demuestra su potencial en problemas complejos de optimización combinatoria. Con mayor número de iteraciones y calibración, es esperable que supere consistentemente a heurísticas simples como el Vecino Más Cercano.

Reporte de Contribución Individual

  • Marcos David Carrillo Builes: Participó en la implementación del algoritmo de colonia de hormigas para la búsqueda de rutas óptimas entre las principales ciudades de Colombia. Realizó la recolección de coordenadas geográficas, la búsqueda de mapas base, y elaboró visualizaciones gráficas de las rutas obtenidas. Además, contribuyó en la documentación correspondiente a esta sección.

  • Tomás Escobar Rivera: Desarrolló e implementó diversos algoritmos heurísticos para abordar el problema de optimización planteado en el punto 1. Se encargó de la modularización y limpieza del código, la creación de funciones de visualización, el ajuste de hiperparámetros, y la elaboración de gráficos que ilustran el desempeño de los optimizadores. Redactó las conclusiones y documentó detalladamente el proceso de optimización heurística y elaboró las conclusiones de colonia de hormigas.

  • Jose Fernando López Ramírez: Fue responsable de la investigación bibliográfica y metodológica necesaria para construir la matriz de costos empleada en el análisis. Documentó su proceso de obtención y su aplicación dentro del marco general del proyecto.

  • Esteban Vásquez Pérez: Coordinó el formato general del informe, la gestión de paquetes y dependencias, así como la administración del repositorio y la publicación del trabajo. Implementó la optimización de la función de Schwefel mediante el método de descenso, y elaboró gráficos 2D, 3D y curvas de nivel. Además, redactó las conclusiones y documentación matemática del punto 1, construyó la matriz de costos en Excel y organizó la bibliografía del informe.

Bibliografía

  • R Core Team. (2024). R: A language and environment for statistical computing. R Foundation for Statistical Computing. https://www.r-project.org/

  • Scrucca, L. (2013). GA: A Package for Genetic Algorithms in R. Journal of Statistical Software, 53(4), 1–37. https://cran.r-project.org/package=GA ↳ Utilizado para implementar el algoritmo genético (GA) y guardar el historial de soluciones en cada iteración.

  • Bendtsen, C. (2012). DEoptim: An R Package for Global Optimization by Differential Evolution. Retrieved April 2025, from https://cran.r-project.org/package=DEoptim ↳ Usado para aplicar el método de evolución diferencial y extraer la mejor solución por iteración.

  • Bendtsen, C. (2012). pso: Particle Swarm Optimization. Retrieved April 2025, from https://cran.r-project.org/package=pso ↳ Herramienta utilizada para implementar la optimización por enjambre de partículas (PSO) en 2 y 3 dimensiones.

  • Surjanovic, S., & Bingham, D. (n.d.). Schwefel Function (schwef). Simon Fraser University. Retrieved April 2025, from https://www.sfu.ca/~ssurjano/schwef.html ↳ Fuente utilizada para la definición matemática, dominio y mínimo global de la función de Schwefel.

  • Surjanovic, S., & Bingham, D. (n.d.). Griewank Function (griewank). Simon Fraser University. Retrieved April 2025, from https://www.sfu.ca/~ssurjano/griewank.html ↳ Fuente utilizada para la descripción formal, propiedades y representación de la función de Griewank.

  • R Documentation. https://www.rdocumentation.org/

  • Simon Fraser University. (s.f.). Home. https://www.sfu.ca/

  • Google. (n.d.). Google Maps Directions API. Retrieved April 2025, from https://developers.google.com/maps/documentation/directions/start
    ↳ Fuente utilizada para obtener el tiempo y distancia entre ciudades principales de Colombia.

  • Instituto Nacional de Vías de Colombia (INVIAS). (n.d.). Sistema de Información de Peajes HERMES SIV. Retrieved April 2025, from https://hermes2.invias.gov.co/SIV/
    ↳ Fuente oficial para la consulta de tarifas de peajes por categoría vehicular en Colombia.

  • Jeep. (n.d.). Jeep Wrangler - Gasoline Capabilities. Retrieved April 2025, from https://www.jeep.es/jeep-wrangler/gasolina/capacidad
    ↳ Especificaciones del vehículo seleccionado, incluyendo consumo de combustible por kilómetro.

  • Ministerio de Minas y Energía de Colombia. (2024). Precios de la gasolina por galón en Colombia. Retrieved April 2025, from https://www.minenergia.gov.co/
    ↳ Fuente del precio actualizado de la gasolina para cálculo del costo por litro.

  • Ministerio de Trabajo de Colombia. (2025). Salario mínimo legal vigente 2025. Retrieved April 2025, from https://www.mintrabajo.gov.co/
    ↳ Fuente del salario mínimo legal mensual utilizado para estimar el costo de la hora del vendedor.

  • DANE. (n.d.). Encuesta Nacional de Presupuestos de los Hogares (ENPH). Retrieved April 2025, from https://www.dane.gov.co/
    ↳ Utilizada como referencia para estimaciones de gasto en alimentación y hospedaje diarios.

  • Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2–3), 243–278. https://doi.org/10.1016/j.tcs.2005.05.020 ↳ Fuente académica que describe el algoritmo de optimización por colonia de hormigas (ACO), utilizado como base para la implementación en este trabajo.

  • OpenAI. (2025). ChatGPT (versión GPT-4.5) [Modelo de lenguaje grande]. https://chat.openai.com/

  • DeepSeek. (2024). DeepSeek: LLM. https://chat.deepseek.com/