Trabajo 1: Optimización Heurística
Wesly Zamira Huertas Salinas
Alejandro Torrado Calderón
Juan Pablo Muñoz Jimenez
2025-04-28
1. Función de Prueba: Griewank
La función de Griewank es una función de prueba común en optimización. Se define como:
\[ 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) \]
Su gradiente tiene componentes:
\[ \frac{\partial f}{\partial x_i} = \frac{x_i}{2000} - \frac{\prod_{j=1}^d \cos\left( \frac{x_j}{\sqrt{j}} \right)}{\cos\left( \frac{x_i}{\sqrt{i}} \right)} \times \frac{\sin\left( \frac{x_i}{\sqrt{i}} \right)}{\sqrt{i}} \] Donde: - \(d\) es la cantidad de dimensiones. - El dominio típico es \(x_i \in [-600, 600]\). - El mínimo global está en \(\mathbf{x} = (0,0,\ldots,0)\).
Configuración del entorno y opciones de knitr
En el primer chunk se define las opciones globales de
knitr (para mostrar o no el código, mensajes y warnings),
se crea un directorio temporal para almacenar archivos intermedios y
cargamos todas las librerías que usaremos más adelante (visualización
2D/3D, animaciones, optimización, etc.).
Definición de la función de prueba Griewank
Se implementa la función de Griewank para evaluar el valor objetivo
de cualquier vector x, requisito previo indispensable para
todos los algoritmos de optimización.
Cálculo del gradiente de Griewank
Aquí se define la función que devuelve el gradiente de Griewank, necesario para el descenso por gradiente.
1.1 Definición del método de Descenso por Gradiente para Griewank
Ejecución del Descenso por Gradiente en 2D para Griewank
1.1.1 Conversión de la trayectoria y animación 2D para Griewank*
Fig 1. Descenso de gradiente Griewank (2D)
## Óptimo encontrado en la iteración: 200## Coordenadas (x1, x2): -254.3516 341.9444## Valor Griewank: 45.418221.1.2 Visualización y Descenso por Gradiente en 3D para Griewank
Fig 2. Descenso de gradiente Griewank (3D)
## Óptimo encontrado en la iteración: 1000## Coordenadas (x1, x2, x3): -254.3503 341.9331 -108.7581## Valor Griewank (3D): 48.375071.2 Algoritmo Genético (GA) Griewank
1.2.1 Algoritmo Genético (GA) en 2D para Griewank
Fig 3. Optimización GA Griewank (2D)
## Primer óptimo encontrado en la iteración: 187## Coordenadas (x, y): 0.01274637 0.01105165## Valor Griewank: 0.00011183711.2.2 Algoritmo Genético (GA) en 3D para Griewank
## | Local search = -0.06162464
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.06162464
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Local search = -0.02958663
## | Final local search = -0.00739604
Fig 4. Optimización GA Griewank (3D)
## Primer óptimo encontrado en la iteración: 220## Coordenadas (x, y): -2.962725 -4.329653## Valor Griewank: 0.028102541.3 Optimización de particulas (PSO)
1.3.1 Optimización de particulas (PSO) en 2D para Griewank
Fig 5. Optimización PSO Griewank (2D)
## Primer óptimo encontrado en la iteración: 7051## Coordenadas (x, y): 0.05415174 -0.1194739## Valor Griewank: 0.0050313051.3.2 Optimización de particulas (PSO) en 3D para Griewank
Fig 6. Optimización PSO Griewank (3D)
## Primer óptimo encontrado en la iteración: 7745## Coordenadas (x, y): -3.069045 -4.527993## Valor Griewank: 0.011936091.4 Evolución Diferencial (DE) en 2D para Griewank
1.4.1 Evolución Diferencial (DE)
## Iteration: 1 bestvalit: 1.858679 bestmemit: 52.879230 -33.133094
## Iteration: 2 bestvalit: 1.236365 bestmemit: -38.102280 -19.646541
## Iteration: 3 bestvalit: 1.029369 bestmemit: 7.927455 1.975890
## Iteration: 4 bestvalit: 0.634864 bestmemit: 9.573241 -48.956346
## Iteration: 5 bestvalit: 0.634864 bestmemit: 9.573241 -48.956346
## Iteration: 6 bestvalit: 0.157683 bestmemit: -3.686243 -4.585381
## Iteration: 7 bestvalit: 0.157683 bestmemit: -3.686243 -4.585381
## Iteration: 8 bestvalit: 0.157683 bestmemit: -3.686243 -4.585381
## Iteration: 9 bestvalit: 0.157683 bestmemit: -3.686243 -4.585381
## Iteration: 10 bestvalit: 0.153975 bestmemit: 6.362271 0.760187
## Iteration: 11 bestvalit: 0.153975 bestmemit: 6.362271 0.760187
## Iteration: 12 bestvalit: 0.127702 bestmemit: 6.465113 -18.052020
## Iteration: 13 bestvalit: 0.127702 bestmemit: 6.465113 -18.052020
## Iteration: 14 bestvalit: 0.127702 bestmemit: 6.465113 -18.052020
## Iteration: 15 bestvalit: 0.127702 bestmemit: 6.465113 -18.052020
## Iteration: 16 bestvalit: 0.127702 bestmemit: 6.465113 -18.052020
## Iteration: 17 bestvalit: 0.034531 bestmemit: -9.483555 -4.585381
## Iteration: 18 bestvalit: 0.034531 bestmemit: -9.483555 -4.585381
## Iteration: 19 bestvalit: 0.034531 bestmemit: -9.483555 -4.585381
## Iteration: 20 bestvalit: 0.034531 bestmemit: -9.483555 -4.585381
## Iteration: 21 bestvalit: 0.034531 bestmemit: -9.483555 -4.585381
## Iteration: 22 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 23 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 24 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 25 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 26 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 27 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 28 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 29 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 30 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 31 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 32 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 33 bestvalit: 0.016091 bestmemit: -3.138448 4.624953
## Iteration: 34 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 35 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 36 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 37 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 38 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 39 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 40 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 41 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 42 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 43 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 44 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 45 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 46 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 47 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 48 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 49 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 50 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 51 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 52 bestvalit: 0.014077 bestmemit: -6.192121 0.037358
## Iteration: 53 bestvalit: 0.013877 bestmemit: -3.094796 -4.586258
## Iteration: 54 bestvalit: 0.013877 bestmemit: -3.094796 -4.586258
## Iteration: 55 bestvalit: 0.013850 bestmemit: 3.206400 -4.568935
## Iteration: 56 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 57 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 58 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 59 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 60 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 61 bestvalit: 0.010378 bestmemit: 6.261909 0.037358
## Iteration: 62 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 63 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 64 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 65 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 66 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 67 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 68 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 69 bestvalit: 0.003491 bestmemit: -0.080694 0.030742
## Iteration: 70 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 71 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 72 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 73 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 74 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 75 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 76 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 77 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 78 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 79 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 80 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 81 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 82 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 83 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 84 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 85 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 86 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 87 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 88 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 89 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 90 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 91 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 92 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 93 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 94 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 95 bestvalit: 0.000383 bestmemit: -0.017119 0.030742
## Iteration: 96 bestvalit: 0.000211 bestmemit: -0.017119 -0.015998
## Iteration: 97 bestvalit: 0.000211 bestmemit: -0.017119 -0.015998
## Iteration: 98 bestvalit: 0.000211 bestmemit: -0.017119 -0.015998
## Iteration: 99 bestvalit: 0.000211 bestmemit: -0.017119 -0.015998
## Iteration: 100 bestvalit: 0.000211 bestmemit: -0.017119 -0.015998
Fig 7. Optimización DE Griewank (2D)
## Primer óptimo encontrado en la iteración: 99## Coordenadas (x, y): -4.475499 4.437552## Valor Griewank: 1.5532121.4.2 Evolución Diferencial (DE) en 3D para Griewank
## Iteration: 1 bestvalit: 8.689304 bestmemit: 155.065358 -2.967279 -85.894189
## Iteration: 2 bestvalit: 2.232990 bestmemit: 11.923856 -66.961109 -40.066941
## Iteration: 3 bestvalit: 1.586562 bestmemit: -5.126980 -24.728727 -44.546763
## Iteration: 4 bestvalit: 1.586562 bestmemit: -5.126980 -24.728727 -44.546763
## Iteration: 5 bestvalit: 1.586562 bestmemit: -5.126980 -24.728727 -44.546763
## Iteration: 6 bestvalit: 1.586562 bestmemit: -5.126980 -24.728727 -44.546763
## Iteration: 7 bestvalit: 1.473801 bestmemit: 47.817596 11.643302 20.779680
## Iteration: 8 bestvalit: 1.060696 bestmemit: -25.350653 11.643302 -26.235332
## Iteration: 9 bestvalit: 1.060696 bestmemit: -25.350653 11.643302 -26.235332
## Iteration: 10 bestvalit: 0.947173 bestmemit: -31.195186 8.427949 -34.133964
## Iteration: 11 bestvalit: 0.947173 bestmemit: -31.195186 8.427949 -34.133964
## Iteration: 12 bestvalit: 0.713554 bestmemit: -16.205390 -7.507784 6.655311
## Iteration: 13 bestvalit: 0.298729 bestmemit: -9.278781 21.850400 -0.855794
## Iteration: 14 bestvalit: 0.298729 bestmemit: -9.278781 21.850400 -0.855794
## Iteration: 15 bestvalit: 0.298729 bestmemit: -9.278781 21.850400 -0.855794
## Iteration: 16 bestvalit: 0.298729 bestmemit: -9.278781 21.850400 -0.855794
## Iteration: 17 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 18 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 19 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 20 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 21 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 22 bestvalit: 0.210544 bestmemit: 3.304248 21.656363 0.100311
## Iteration: 23 bestvalit: 0.178214 bestmemit: -3.606848 4.175933 0.577544
## Iteration: 24 bestvalit: 0.178214 bestmemit: -3.606848 4.175933 0.577544
## Iteration: 25 bestvalit: 0.178214 bestmemit: -3.606848 4.175933 0.577544
## Iteration: 26 bestvalit: 0.178214 bestmemit: -3.606848 4.175933 0.577544
## Iteration: 27 bestvalit: 0.134456 bestmemit: 12.911073 8.782467 -0.278942
## Iteration: 28 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 29 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 30 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 31 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 32 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 33 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 34 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 35 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 36 bestvalit: 0.100616 bestmemit: 6.189443 -17.596960 0.100311
## Iteration: 37 bestvalit: 0.080758 bestmemit: 12.445690 8.782467 -0.278942
## Iteration: 38 bestvalit: 0.080758 bestmemit: 12.445690 8.782467 -0.278942
## Iteration: 39 bestvalit: 0.080758 bestmemit: 12.445690 8.782467 -0.278942
## Iteration: 40 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 41 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 42 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 43 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 44 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 45 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 46 bestvalit: 0.050599 bestmemit: -3.227521 -8.932620 5.118431
## Iteration: 47 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 48 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 49 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 50 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 51 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 52 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 53 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 54 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 55 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 56 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 57 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 58 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 59 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 60 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 61 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 62 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 63 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 64 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 65 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 66 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 67 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 68 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 69 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 70 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 71 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 72 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 73 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 74 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 75 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 76 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 77 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 78 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 79 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 80 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 81 bestvalit: 0.039137 bestmemit: 6.170619 -4.647519 -5.459460
## Iteration: 82 bestvalit: 0.032112 bestmemit: 0.101452 -4.320949 5.693730
## Iteration: 83 bestvalit: 0.029383 bestmemit: -6.169287 4.458273 5.356707
## Iteration: 84 bestvalit: 0.029383 bestmemit: -6.169287 4.458273 5.356707
## Iteration: 85 bestvalit: 0.029383 bestmemit: -6.169287 4.458273 5.356707
## Iteration: 86 bestvalit: 0.029383 bestmemit: -6.169287 4.458273 5.356707
## Iteration: 87 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 88 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 89 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 90 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 91 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 92 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 93 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 94 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 95 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 96 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 97 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 98 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 99 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
## Iteration: 100 bestvalit: 0.015271 bestmemit: -3.202881 4.287618 -0.036768
Fig 8. Optimización DE Griewank (3D)
## Primer óptimo encontrado en la iteración: 98## Coordenadas (x, y): -5.469686 -5.335941## Valor Griewank: 2.0577221.5 Análisis de resultados de optimización a la función griewank
1.5.1 Descenso por Gradiente
El descenso por gradiente mostró una gran eficiencia en términos de número de evaluaciones de la función objetivo: con apenas unas pocas miles de llamadas (alrededor de 800 en 2D y 6 000 en 3D, considerando la estimación de evaluaciones necesarias para aproximar numéricamente cada componente del gradiente), alcanzó su criterio de parada. Sin embargo, al aplicarse sobre la superficie altamente multimodal de la función de Griewank, quedó “atrapado” en mínimos locales lejanos al óptimo global, deteniéndose en valores cercanos a 45–48 en lugar de 0. Este comportamiento refleja que el descenso por gradiente explota eficazmente la información local y converge rápidamente cuando la función es suave o casi convexa, pero carece de un mecanismo intrínseco para explorar regiones lejanas en busca del mínimo global a menos que se complemente con reinicios o estrategias de exploración adicionales.
1.5.2 Métodos Heurísticos (GA, PSO y DE)
Los métodos heurísticos sacrificaron parte de la eficiencia local para ganar capacidad exploratoria global. El Algoritmo Genético (GA), con poblaciones de 100 individuos durante 200 generaciones en 2D (≈20 000 evaluaciones) y de 150 durante 300 en 3D (≈45 000 evaluaciones), logró los valores finales más cercanos a cero (f≈1.1×10⁻⁴ en 2D y f≈0.028 en 3D). El PSO, con entre 7 000 y 8 000 evaluaciones, alcanzó también soluciones de alta calidad (f≈0.005 en 2D y f≈0.012 en 3D). La Evolución Diferencial (DE), con un coste moderado de unas 8 000 evaluaciones, obtuvo mejoras sobre el gradiente (f≈1.55 en 2D, f≈2.06 en 3D) pero no tan fino como GA o PSO. En conjunto, estos heurísticos demostraron que su exploración poblacional puede escapar de los pozos locales de Griewank y acercarse al mínimo global, a costa de un mayor presupuesto computacional.
2. Función de las seis jorobas de camello:
La función de las seis jorobas de camello (Six-Hump Camel) es una función frecuentemente utilizada para evaluar el desempeño de algoritmos de optimización en espacios de búsqueda no triviales. es una función no convexa, multimodal y polinómica de grado cuatro.
Se define como:
\[ f(\mathbf{x}) = \left( 4 - 2.1x_1^2 + \frac{x_1^4}{3} \right)x_1^2 + x_1x_2 + \left( -4 + 4x_2^2 \right)x_2^2 \]
La función presenta seis regiones prominentes (jorobas) en su superficie, siendo esta una función no convexa, dando lugar a múltiples mínimos locales y dos mínimos globales bien definidos. Simon Fraser University. (s.f.).
Para esta definición:
-La primera parte de la función, depende de x1 y genera curvaturas multiples.
-La segunda parte de la función x1 y x2 es un acoplamiento lineal
-La tercera parte de la función x2 agrega simetría
-Sus dos mínimos globales son (x1,x2)=(0.0898, -0.7126) y (x1,x2)=(-0.0898, 0.7126) con valor aproximado: \[f(x_1, x_2) \approx -1.0316\]
Representación más gráfica de la función con sus jorobas:
Fig 9. Función Six hump camel (2D)
2.1 Optimización mediante descenso del gradiente:
Para gráficar y un entendimiento más fácil x1 = x y x2 = y
Así:
\[ f(x, y) = \left(4 - 2.1\, x^2 + \frac{x^4}{3}\right)x^2 + x\,y + \left(-4 + 4\, y^2\right)y^2 \]
Gradiente de la función:
El gradiente es el vector de derivadas parciales: \[ \nabla (x, y) = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) \] - La derivada con respecto a x es: \[ \frac{\partial f}{\partial x} = 8x - 8.4x^3 + 2x^5 + y \] - La derivada con respecto a y es: \[ \frac{\partial f}{\partial y} = x + 16y^3 - 8y \]
Método de descenso por gradiente en dos dimensiones:
Fig 10. Descenso por gradiente Six hump camel (2D)
## iter x y f
## 240 239 -0.08709228 0.7123408 -1.031599
## 241 240 -0.08715570 0.7123481 -1.031600
## 242 241 -0.08721767 0.7123552 -1.031602Figura 10:
En la figura podemos observar el método de descenso por gradiente, un algoritmo de optimización iterativo que busca encontrar el mínimo de una función diferenciable. Consiste en calcular el gradiente, que indica la dirección de mayor incremento, y actualizar los parámetros en sentido opuesto, es decir, moviéndose hacia la dirección de mayor descenso—mediante una tasa de aprendizaje que regula el tamaño de cada paso. Este proceso se repite hasta que las actualizaciones son mínimas.(IBM, s.f.)
- En esta representación gráfica podemos observar que partiendo desde un punto aleatorio del plano, el descenso por gradiente generalmente busca el minimo local más cercano, en este caso encontró uno de los dos minimos globales que tiene esta función ubicado en (x,y)=(-0.0898, 0.7126)
- El descenso por gradiente puede o no encontrar el valor óptimo global de la función de las seis jorobas de camello, ya que este se “guiará” por el minimo local más cercano. Así que depende mucho de su condición inicial, en este caso, aleatoria.
Método de descenso por gradiente en tres dimensiones:
Fig 11. Descenso por gradiente Six hump camel (3D)
Figura 11:
- En tres dimensiones podemos ver una condición inicial diferente a la del gráfico en dos dimensiones. Esta condición inicial aleatoria se generó más cerca del minimo local (x,y)=(−0.08984, 0.71266) por lo tanto, el descenso por gradiente va a este punto mínimo local y no a uno de los minimos globales.
“La función Six Hump Camel posee seis mínimos locales, de los cuales dos son mínimos globales. Este comportamiento multimodal la hace especialmente útil como caso de prueba en estudios y algoritmos de optimización, ya que permite evaluar la capacidad de estos para evitar converger únicamente en mínimos locales no globales.” (Simon Fraser University, s.f.).
- La línea azul ilustra el recorrido desde el punto de partida en el plano xyz hasta el mínimo local obtenido por el descenso por gradiente. Aunque es un mínimo, no es el global, lo que significa que existen otros puntos donde la función toma un valor inferior que sí son totalmente óptimos
2.2 Optimización con el método de enjambre de particulas PSO en dos dimensiones:
Fig 12. Método de enjambre de particulas (PSO) (2D)
Figura 12:
En la figura se puede observar el proceso de optimización por enjambre de particulas en dos dimensiones en el cual en este caso se generaron 50 particulas en posiciones aleatorias dentro del dominio y cada particula con una velocidad inicial aleatoria
El algoritmo PSO guía mediante un equilibrio entre exploración y explotación. Es decir, cada partícula se mueve en el espacio de búsqueda basándose en tres componentes:
-Inercia: Conserva una parte de su velocidad actual.
-Atracción personal (pbest): Se dirige hacia la mejor posición que ha encontrado.
-Atracción social (gbest): Se mueve hacia la mejor posición encontrada por todo el enjambre.
En el proceso, cuando alguna partícula descubre una buena solución (un valor bajo de la función en nuestro problema de minimización), esa posición se convierte en el “global best”. Una vez que se determina un gbest, las demás partículas se ven atraídas hacia esa región, lo que provoca que eventualmente converjan entorno a esa solución. Huang, H., Qiu, J., & Riedl, K. (2023).
En este caso el gbest (global best) ubicado en (x,y)=(-0.0898, 0.7126) quien es el que se identifica como el primer óptimo de la función en esta condición aleatoria en especifico.
2.3 Optimización con el método de enjambre de particulas PSO en tres dimensiones:
Fig 13. Método de enjambre de particulas (PSO) (3D)
Figura 13:
En esta representación en tres dimensiones con una condición inicial aleatoria diferente a la de dos dimensiones, las particulas convergen en el segundo minimo global que posee la función de las seis jorobas de camello, exactamente en (x,y,z)=(0.0898, -0.7126, 0) en este caso, el minimo global óptimo. El cambio a tres dimensiones no supuso una diferencia mayor a su comportamiento comparado al de dos dimensiones.
2.4 Optimización con el método de evolución diferencial DE en dos dimensiones:
Fig 14. Método de evolución diferencial (DE) (2D)
Figura 14:
En la figura se usa como método de optimización el algoritmo de evolución diferencial DE el cual se caracteriza por utilizar una población de soluciones candidatas que evolucionan mediante operadores de mutación, cruce (recombinación) y selección. A diferencia de otros algoritmos evolutivos, DE genera nuevas soluciones perturbando vectores existentes mediante diferencias escaladas entre otros miembros de la población. Storn, R., & Price, K. (1997).
Esto quiere decir que el algoritmo de evolución diferencial sirve para encontrar los mejores valores posibles de la función, en este caso sus dos minimos globales que posee.
Para entender la figura y el algoritmo se tiene que: - Primero, se asigna aleatoriamente una población o candidatos dentro del dominio de la función.
- Luego, en cada iteración del algoritmo DE cada agente crea una versión modificada del mismo, que se mezcla con otros tres agentes/miembros de la población al azar en cualquier parte del plano.
- Este agente mutado se mezcla con el agente original, mezclando su información. Si esta información se define como un punto más bajo en el plano, este lo reemplaza, si no, el antiguo se queda.
- El proceso se repite hasta que a través de cada iteración (generaciones) el grupo se va acercando cada vez al punto más bajo, en este caso el minimo global. Storn, R., & Price, K. (1997).
En la figura se puede percibir que en menos de 50 iteraciones se llegó a los dos minimos globales, además de como cada punto rojo (población) se cruzaba y mutaba para encontrar estos mínimos.
De los anteriores algoritmos de optimización DE es el único quien logró encontrar los dos mínimos globales de la función de las seis jorobas de camello.
2.4 Optimización con el método de evolución diferencial DE en tres dimensiones:
Fig 15. Método de evolución diferencial (DE) (3D)
Figura 15:
En tres dimensiones se amplía la búsqueda y adaptación de la Evolución Diferencial a un espacio de mayor dimensión, introduce operaciones vectoriales en tres componentes Cada candidato es ahora un vector (x,y,z) y proporciona una visualización que proyecta información de la tercera dimensión a través del color. Los pasos fundamentales (mutación, cruce y selección) se mantienen, pero se ejecutan en un espacio más complejo. También se nota a medida de cada iteración como cambia el color en los agentes y descienden a los dos minimos globales hasta llegar al 0 en z.
2.5 Optimización con el método GA de algoritmos evolutivos en 2D
Fig 16. Método de algoritmos geneticos (GA) (2D)
Figura 16:
Los Algoritmos Genéticos (Genetic Algorithms) son técnicas de optimización inspiradas en el proceso de evolución natural. Al igual que la selección natural en la biología, simulan cómo evolucionan las soluciones “mejores” con el tiempo. Holland, J. H. (1975).
En este caso, el algoritmo se prueba con 50 individuos dentro de la población los cuales son representados por cada punto generado en la figura de manera aleatoria. A cada punto se le asigna un “valor” evaluando su función de aptitud o “fitness” (en esta situación se usa la función negativa porque se quiere encontrar es el minimo)
- Los “puntos” escogidos son aquellos con menor valor(según esta situación ya que se busca encontrar el minimo)
- Estos “puntos” o individuos dentro de la población que ya fueron elegidos, se cruzan y dan lugar a hijos con mejores caracteristicas, esto, sucediendo de generación en generación mejorando con cada iteración.
Esto da lugar a que el algoritmo encuentre el minimo global optimo según las generaciones.
2.6 Optimización con el método GA de algoritmos evolutivos en 3D
Fig 17. Método de algoritmos geneticos (GA) (3D)
2.7 Conclusiones:
¿Qué aportaron los métodos de descenso por gradiente y qué aportaron los métodos heurísticos?
Método por descenso del gradiente:
En la figura 10 donde se hace el recorrido del método de descenso por gradiente con condición inicial aleatoria en dos dimensiones, se aprecia que para alcanzar el valor objetivo f(x,y)≈−1.0316 tomó 241 iteraciones exactamente, Esto, solo en el caso de esta seed ya que en el caso de recorrido del algoritmo en tres dimensiones (figura 11) el método de descenso por gradiente se atascó en uno de los mínimos locales que posee la función de las seis jorobas de camello. Por lo tanto este método requiere condiciones especiales para que encuentre el valor objetivo óptimo porque depende de que tan cerca la condición aleatoria esté a uno de los dos minimos globales o minimos locales de la función para que descienda a estos.
Métodos heurísticos:
Optimización con el método de algoritmos evolutivos (GA):
Usando el método de algoritmos evolutivos (GA) para una población de 50 individuos, en dos dimensiones y tres dimensiones se llegó a la conclusión que en la generación numero 17 el algoritmo pudo alcanzar el valor objetivo de la función sin atascarse en mínimos locales. Se tiene en cuenta también que no converje al mismo tiempo en los dos minimos globales que tiene la función si no al primero que encuentra.
Optimización con el método de enjambre de particulas (PSO):
Por optimización mediante PSO se alcanzó el valor objetivo por primera vez a partir de la iteración 18 (con una población de 50 y una inercia de 0.5) la cual a partir de esta iteración se presenta un mejor fitness igual a −1.0316. En todos los casos de condición aleatoria el enjambre de particulas llegó a uno de los dos minimos globales.Por lo tanto, se concluye a partir de esto que:
- En dos y tres dimensiones el algoritmo PSO siempre encontró el valor objetivo, pero no los dos mínimos globales al mismo tiempo que presenta la función de las seis jorobas de camello.
- Con un ajuste de la inercia en el algoritmo a 0.5 se logró que todas las particulas converjan al primer minimo global encontrado por una de ellas.
- A comparación del algoritmo de descenso por gradiente, la optimización por PSO si va exactamente a el valor óptimo de la función sin tener en cuenta una condición inicial aleatoria que lo beneficie.
Optimización con el método de evolución diferencial (DE):
Por optimización mediante DE se logró el valor objetivo en alrededor de 43 iteraciones con una población de 50 individuos. Tanto como en dos dimensiones y tres dimensiones el algoritmo encontró los dos mínimos globales de la función de una forma eficiente, dejando pasar mínimos locales y encontrando el valor óptimo de la función. A diferencia de los otros métodos heuristicos y metodo por descenso del gradiente presentados en este trabajo, el algoritmo de evolución diferencial fue el único en encontrar los dos mínimos globales de la función de las seis jorobas de camello.
3. Optimización combinatoria, Problema TSP (Travelling Salesman Problem)
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.
3.1 Obtención de datos
3.1.1 Ciudades principales de Colombia
En primer lugar el análisis de la ruta más óptima para este problema se hará con las siguientes 13 ciudades (DANE, 2020):
- Bogotá D.C. – Capital del país y principal centro
económico, político y cultural.
- Medellín – Capital de Antioquia, reconocida por su
innovación y desarrollo industrial.
- Cali – Capital del Valle del Cauca, centro
agroindustrial y cultural del suroccidente.
- Barranquilla – Principal puerto del Caribe
colombiano y epicentro industrial y logístico.
- Cartagena – Ciudad portuaria y turística clave, con
gran valor histórico.
- Cúcuta – Capital de Norte de Santander, zona
fronteriza con Venezuela.
- Bucaramanga – Capital de Santander, reconocida por
su calidad de vida y desarrollo urbano.
- Pereira – Capital de Risaralda, eje del triángulo
cafetero.
- Manizales – Capital de Caldas, centro educativo y
cultural del eje cafetero.
- Armenia – Capital de Quindío, parte fundamental del
eje cafetero.
- Ibagué – Capital del Tolima, conocida por su
tradición musical.
- Santa Marta – Capital del Magdalena, con gran
importancia turística y portuaria.
- Villavicencio – Capital del Meta, puerta de entrada a los Llanos Orientales.
La ubicación de cada una de estas ciudades se muestra a continuación:
Fig 18. Ciudades principales de Colombia
Teniendo en cuenta que el costo del desplazamiento entre ciudades es la suma del valor de la hora del vendedor, el costo de los peajes y el costo del combustible, se calculó el tiempo entre cada trayecto de acuerdo a datos de Google Maps, el costo de los peajes de acuerdo con INVIAS (2025), y el costo del combustible teniendo en cuenta el vehículo selesccionado para hacer el recorrido.
3.1.2 Salario del vendedor
Para el cálculo del salario del vendedor se creó una matriz con los tiempos de viaje en cada trayecto usando una API de Google Maps, como se muestra a continuación:
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
Luego se multiplicó cada valor de esta matriz por el salario por hora del vendedor, que de acuerdo con (Salario Para Transporte De Carga En Colombia - Salario Medio, n.d.) es de 1’700.000 COP por mes, por lo que la hora sería a aproximadamente 9.700 COP, quedando de la siguiente forma:
\[ Costo_{vendedor} = tiempos \times 9700 \]
Siguiendo lo anterior la matríz de salarios del vendedor en pesos colombianos es la siguiente:
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
3.1.3 Costo del combustible
Para calcular el costo del combustible, primero se creó la matriz de distancias en kilómetros usando una API de Google Maps, como se muestra a continuación:
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
Luego, se seleccionó el modelo de vehículo que conducirá el vendedor, en este caso será una Renault Kangoo 1.5 que tiene un consumo de combustible de 4,5 litros cada 100 km de acuerdo con la empresa Renault. Adicionalmente, teniendo en cuenta que en Colombia el precio de la gasolina es de en promedio 15.827 COP el galón (Creg, 2025), y un galón tiene 3,78 litros, entonces, el precio de la gasolina por litro es de 4.187 COP. Por lo anterior, la ecuación para calcular el costo del combustible en cada ruta es:
\[ Costo_{combustible} = distancia [km] \times \frac{4,5}{100} [l/km] \times 4187 [COP/l] \]
Por lo anterior, la matríz final de costos de combustible se presenta a continuación:
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
3.1.4 Costo de los peajes
Teniendo en cuenta los datos suministrados por (INVIAS, 2025) se creó la siguiente matriz con los costos de peaje en COP por cada ruta:
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
3.1.5 Costo total
Finalmente, la matriz de costos final se calcula de la siguiente forma:
\[ Costo_{total} = Costo_{vendedor} + Costo_{combustible} + Costo_{peajes} \]
| Bogotá | Medellín | Cali | Barranquilla | Bucaramanga | Manizales | Pereira | Cúcuta | Pasto | Ibagué | Montería | Cartagena | Villavicencio | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Bogotá | 0.000000 | 8.557500 | 9.135556 | 18.008889 | 8.939444 | 7.189722 | 6.802222 | 11.56972 | 16.581111 | 3.949444 | 12.461111 | 16.632778 | 3.247778 |
| Medellín | 8.439444 | 0.000000 | 7.083611 | 13.108611 | 6.685278 | 3.825556 | 4.142500 | 11.54972 | 14.999167 | 6.712222 | 7.561111 | 11.732500 | 11.410278 |
| Cali | 8.752222 | 7.009722 | 0.000000 | 19.883333 | 13.174444 | 4.462500 | 3.405833 | 18.03917 | 8.688889 | 4.940556 | 14.335556 | 18.507222 | 10.923333 |
| Barranquilla | 19.876111 | 13.177222 | 20.100278 | 0.000000 | 12.449444 | 16.842222 | 17.159167 | 15.17389 | 28.015833 | 18.227778 | 6.371667 | 2.586667 | 22.038889 |
| Bucaramanga | 8.682500 | 6.710833 | 13.634167 | 12.567222 | 0.000000 | 10.375833 | 10.692778 | 4.96250 | 21.549444 | 10.171111 | 10.161944 | 11.581111 | 11.908611 |
| Manizales | 7.191944 | 3.785833 | 4.464167 | 16.659167 | 9.515556 | 0.000000 | 1.208333 | 14.38028 | 12.379444 | 3.778056 | 11.111667 | 15.283333 | 9.760833 |
| Pereira | 6.500000 | 4.096111 | 3.476111 | 16.969444 | 10.521667 | 1.202222 | 0.000000 | 15.38639 | 11.391667 | 2.688056 | 11.421944 | 15.593333 | 8.670833 |
| Cúcuta | 11.386111 | 11.301667 | 18.224722 | 15.574167 | 4.710278 | 14.966667 | 15.283611 | 0.00000 | 26.140278 | 15.276667 | 14.278611 | 14.587778 | 15.552222 |
| Pasto | 16.324722 | 14.582222 | 8.306667 | 27.455556 | 20.746667 | 12.034722 | 10.978333 | 25.61139 | 0.000000 | 12.512778 | 21.908056 | 26.079444 | 18.495556 |
| Ibagué | 4.151111 | 7.214722 | 5.484444 | 17.342222 | 8.560278 | 4.320833 | 3.151111 | 13.42472 | 13.400000 | 0.000000 | 11.794722 | 15.966111 | 6.321944 |
| Montería | 14.350000 | 7.651111 | 14.574167 | 6.361667 | 10.234444 | 11.316111 | 11.633056 | 13.86306 | 22.489722 | 12.701667 | 0.000000 | 4.524722 | 16.512500 |
| Cartagena | 18.453333 | 11.754444 | 18.677778 | 2.293611 | 11.454167 | 15.419444 | 15.736389 | 14.17833 | 26.593056 | 16.805278 | 4.457222 | 0.000000 | 20.616111 |
| Villavicencio | 3.164444 | 11.491389 | 11.248333 | 20.942778 | 12.105278 | 10.024444 | 8.914722 | 14.73556 | 18.693889 | 6.061944 | 15.395278 | 19.566944 | 0.000000 |
3.2 Algoritmo Ant System aplicado al problema TSP
En este caso se definió un número de 50 hormigas
(K = 50) por iteración, lo cual permite una
diversidad suficiente de soluciones sin generar un alto costo
computacional. El número de iteraciones se fijó en 100
(N = 100), lo cual es adecuado para permitir la
convergencia del algoritmo sin riesgo de sobreajuste. En cuanto a los
pesos de decisión, se asignó un valor de β = 5 para
priorizar la heurística (costos mínimos), y un valor menor de α
= 1 para limitar el efecto de las feromonas en las primeras
etapas del proceso. Finalmente, se utilizó una tasa de
evaporación (ρ = 0.1) baja, permitiendo que las
buenas rutas mantengan influencia durante varias iteraciones sin
provocar una convergencia prematura. Esta combinación de parámetros
busca encontrar soluciones óptimas al problema del viajante (TSP) en un
entorno geográfico como el colombiano, con una matriz de costos
previamente normalizada.
## Ruta óptima (cerrada):## Bogotá → Villavicencio → Ibagué → Pereira → Manizales → Medellín → Bucaramanga → Cúcuta → Cartagena → Barranquilla → Montería → Cali → Pasto → Bogotá## Distancia total en COP## [1] 2259522
Fig 19. Ruta más corta usando Ant System
Fig 20. Animación de la ruta óptima
3.3 Algoritmo genético
Para la implementación del algoritmo genético se seleccionaron
parámetros que equilibran la diversidad de soluciones y la eficiencia
computacional. Se definió una población inicial de 100
individuos (pop_size = 100), suficientemente
amplia para explorar distintas combinaciones de rutas. El número de
generaciones se estableció en 200
(num_generations = 200), lo que permite que el
algoritmo evolucione adecuadamente hacia soluciones óptimas. Se utilizó
una alta tasa de cruce del 80%
(crossover_rate = 0.8) para fomentar la
recombinación de buenos fragmentos de soluciones entre individuos.
Finalmente, se aplicó una tasa de mutación baja del 1%
(mutation_rate = 0.01), con el objetivo de
mantener la diversidad genética sin introducir demasiado ruido. Esta
configuración permite una exploración efectiva del espacio de soluciones
en problemas de optimización como el del viajante (TSP).
## Ruta optima (cerrada):## Cali → Pereira → Manizales → Medellín → Montería → Cartagena → Barranquilla → Cúcuta → Bucaramanga → Bogotá → Villavicencio → Ibagué → Pasto → Cali## [1] 1738924
Fig 21. Ruta óptima usando Algorítmos genéticos
Fig 22. Animación de la ruta más óptima
3.4 Conclusión sobre los algoritmos de Optimización combinatoria
El Algoritmo Genético (GA) y el Ant System (AS) son dos métodos metaheurísticos efectivos para resolver problemas de optimización de rutas, cada uno con sus fortalezas: el GA destaca por su flexibilidad y capacidad de evolución poblacional mediante selección, cruce y mutación, mientras que el AS se basa en la construcción colaborativa de soluciones guiadas por feromonas, especialmente eficiente en problemas de caminos. En la comparación práctica realizada, el GA logró encontrar una solución con un costo total menor, superando al Ant System, evidenciando que GA logra minimizar mucho más el costo en la ruta propuesta.
Bibliografía
Analytics India Magazine. (2021, 8 de abril). Top alternatives to gradient descent. Recuperado de https://analyticsindiamag.com/top-alternatives-to-gradient-descent/
DANE. (2025). DANE. Boletines. Recuperado el 29 de abril de 2025, de https://www.dane.gov.co/files/investigaciones/boletines/ech/ech/pres_web_empleo_rueda_prensa_ene_20.pdf
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics), 26(1), 29–41. https://doi.org/10.1109/3477.484436
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Huang, H., Qiu, J., & Riedl, K. (2023). On the global convergence of particle swarm optimization methods. Applied Mathematics & Optimization, 88(2), Artículo 30. https://doi.org/10.1007/s00245-023-09983-3
IBM. (s.f.). ¿Qué es el descenso del gradiente? Recuperado el 29 de abril de 2025, de https://www.ibm.com/mx-es/think/topics/gradient-descent
Jamil, M., & Yang, X.-S. (2013). A literature survey of benchmark functions for global optimization problems. International Journal of Mathematical Modelling and Numerical Optimization, 4(2), 150–194.
Loshchilov, I., & Hutter, F. (2016). SGDR: Stochastic Gradient Descent with Warm Restarts. arXiv preprint arXiv:1608.03983. https://arxiv.org/abs/1608.03983
INVIAS. (2016, 8 de febrero). Recuperado de https://www.invias.gov.co/index.php/listado-tarifas-peajes-2
Price, K., Storn, R., & Lampinen, J. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer.
Salario para Transporte De Carga en Colombia - Salario Medio. (s.f.). Talent.com. Recuperado de https://co.talent.com/salary?job=transporte+de+carga
Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation.
Simon Fraser University. (s.f.). Six-Hump Camel Function. Recuperado el 29 de abril de 2025, de https://www.sfu.ca/~ssurjano/camel6.html
Storn, R., & Price, K. (1997). Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359. https://doi.org/10.1023/A:1008202821328
Wikipedia. (s.f.). Descenso del gradiente. Recuperado el 29 de abril de 2025, de https://es.wikipedia.org/wiki/Descenso_del_gradiente
Wikipedia contributors. (s.f.). Griewank function. Wikipedia. Recuperado de https://en.wikipedia.org/wiki/Griewank_function
Wikipedia contributors. (2025, 20 de febrero). Problema del viajante. Wikipedia, La Enciclopedia Libre. Recuperado de https://es.wikipedia.org/wiki/Problema_del_viajante
Reporte de contribución individual
- Wesly Zamira Huertas Salinas: Programación y documentación de la segunda parte, y organización del reporte general
- Alejandro Torrado Calderón: Programación y documentación de la función Griewank.
- Juan Pablo Muñoz Jimenez: Programación y documentación de la función de las seis jorobas de camello.
Link del repositorio:
https://github.com/AlejandroTorradoCalderon/Optimizacion-heuristica-RNA