Trabajo 1: Optimización Heurística

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.41822

1.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.37507

1.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.0001118371

1.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.02810254

1.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.005031305

1.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.01193609

1.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.553212

1.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.057722

1.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.1 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 x₁ y genera curvaturas multiples.

-La segunda parte de la función x₁ y x₂ es un acoplamiento lineal

-La tercera parte de la función x₂ agrega simetría

-Sus dos mínimos globales son (x₁,x₂)=(0.0898, -0.7126) y (x₁,x₂)=(-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.2 Optimización mediante descenso del gradiente:

Para gráficar y un entendimiento más fácil x₁ = x y x₂ = 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.031602

Figura 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.3.1 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.2 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.3.3 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.3.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.3.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.3.6 Optimización con el método GA de algoritmos evolutivos en 3D

Fig 17. Método de algoritmos geneticos (GA) (3D)

2.4 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.

Obtención de datos

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):

1. Bogotá D.C. – Capital del país y principal centro económico, político y cultural.
   
2. Medellín – Capital de Antioquia, reconocida por su innovación y desarrollo industrial.
   
3. Cali – Capital del Valle del Cauca, centro agroindustrial y cultural del suroccidente.
   
4. Barranquilla – Principal puerto del Caribe colombiano y epicentro industrial y logístico.
   
5. Cartagena – Ciudad portuaria y turística clave, con gran valor histórico.
   
6. Cúcuta – Capital de Norte de Santander, zona fronteriza con Venezuela.
   
7. Bucaramanga – Capital de Santander, reconocida por su calidad de vida y desarrollo urbano.
   
8. Pereira – Capital de Risaralda, eje del triángulo cafetero.
   
9. Manizales – Capital de Caldas, centro educativo y cultural del eje cafetero.
   
10. Armenia – Capital de Quindío, parte fundamental del eje cafetero.
    
11. Ibagué – Capital del Tolima, conocida por su tradición musical.
    
12. Santa Marta – Capital del Magdalena, con gran importancia turística y portuaria.
    
13. 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:

## numeric(0)

Cálculo de la matriz de costos

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 ___, y el costo del combustible teniendo en cuenta el vehículo selesccionado para hacer el recorrido.

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
## Bogotá         0.000000  8.577500  9.209167    18.046111    8.977222  7.231389
## Medellín       8.586389  0.000000  7.096389    13.138333    6.698611  3.833056
## Cali           8.832500  7.044167  0.000000    19.933889   13.198333  4.461389
## Barranquilla  19.952778 13.209722 20.148611     0.000000   12.478333 16.885556
## Bucaramanga    8.699444  6.720278 13.659444    12.593889    0.000000 10.396111
## Manizales      7.240000  3.818611  4.466389    16.708333    9.545833  0.000000
## Pereira        6.576111  4.130000  3.477778    17.019722   10.553333  1.204167
## Cúcuta        11.370278 11.300278 18.239167    15.609722    4.702500 14.975833
## Pasto         16.361111 14.572778  8.262222    27.462500   20.726944 11.990000
## Ibagué         4.227778  7.258889  5.499722    17.376389    8.580000  4.333056
## Montería      14.388889  7.683611 14.622778     6.358611   10.275000 11.359444
## Cartagena     18.485278 11.780278 19.018611     2.298333   11.480000 15.755278
## Villavicencio  3.173611 11.503056 11.337222    20.971389   12.076389 10.077222
##                 Pereira    Cúcuta     Pasto    Ibagué  Montería Cartagena
## Bogotá         6.869167 11.558611 16.792778  4.008611 12.503889 16.653611
## Medellín       4.148889 11.557500 14.957778  6.720000  7.596111 11.745556
## Cali           3.403889 18.057500  8.643889  4.945278 14.391667 18.541389
## Barranquilla  17.201389 15.216111 28.010000 18.316667  6.309167  2.563889
## Bucaramanga   10.711944  4.953889 21.520833 10.238056 10.200278 11.596389
## Manizales      1.206944 14.404722 12.327778  3.778056 11.166111 15.315833
## Pereira        0.000000 15.412222 11.339167  2.688889 11.477778 15.627222
## Cúcuta        15.291944  0.000000 26.100556 14.818056 14.325556 14.612222
## Pasto         10.932500 25.586111  0.000000 12.473889 21.920278 26.070000
## Ibagué         3.159722 13.438889 13.360833  0.000000 11.834167 15.983889
## Montería      11.675278 13.914444 22.484167 12.790556  0.000000  4.508611
## Cartagena     16.071111 14.217778 26.880000 16.887222  4.449444  0.000000
## Villavicencio  8.997222 14.657778 18.921111  6.136667 15.429444 19.578889
##               Villavicencio
## Bogotá             2.996111
## Medellín          11.284722
## Cali              10.758056
## Barranquilla      21.958056
## Bucaramanga       11.691944
## Manizales          9.590833
## Pereira            8.501667
## Cúcuta            14.362778
## Pasto             18.286667
## Ibagué             6.153333
## Montería          16.431944
## Cartagena         20.528333
## Villavicencio      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
## Bogotá             0.00  83201.75  89328.92    175047.28    87079.06  70144.47
## Medellín       83287.97      0.00  68834.97    127441.83    64976.53  37180.64
## Cali           85675.25  68328.42      0.00    193358.72   128023.83  43275.47
## Barranquilla  193541.94 128134.31 195441.53         0.00   121039.83 163789.89
## Bucaramanga    84384.61  65186.69 132496.61    122160.72        0.00 100842.28
## Manizales      70228.00  37040.53  43323.97    162070.83    92594.58      0.00
## Pereira        63788.28  40061.00  33734.44    165091.31   102367.33  11680.42
## Cúcuta        110291.69 109612.69 176919.92    151414.31    45614.25 145265.58
## Pasto         158702.78 141355.94  80143.56    266386.25   201051.36 116303.00
## Ibagué         41009.44  70411.22  53347.31    168550.97    83226.00  42030.64
## Montería      139572.22  74531.03 141840.94     61678.53    99667.50 110186.61
## Cartagena     179307.19 114268.69 184480.53     22293.83   111356.00 152826.19
## Villavicencio  30784.03 111579.64 109971.06    203422.47   117140.97  97749.06
##                 Pereira    Cúcuta     Pasto    Ibagué  Montería Cartagena
## Bogotá         66630.92 112118.53 162889.94  38883.53 121287.72 161540.03
## Medellín       40244.22 112107.75 145090.44  65184.00  73682.28 113931.89
## Cali           33017.72 175157.75  83845.72  47969.19 139599.17 179851.47
## Barranquilla  166853.47 147596.28 271697.00 177671.67  61198.92  24869.72
## Bucaramanga   103905.86  48052.72 208752.08  99309.14  98942.69 112484.97
## Manizales      11707.36 139725.81 119579.44  36647.14 108311.28 148563.58
## Pereira            0.00 149498.56 109989.92  26082.22 111334.44 151584.06
## Cúcuta        148331.86      0.00 253175.39 143735.14 138957.89 141738.56
## Pasto         106045.25 248185.28      0.00 120996.72 212626.69 252879.00
## Ibagué         30649.31 130357.22 129600.08      0.00 114791.42 155043.72
## Montería      113250.19 134970.11 218096.42 124068.39      0.00  43733.53
## Cartagena     155889.78 137912.44 260736.00 163806.06  43159.61      0.00
## Villavicencio  87273.06 142180.44 183534.78  59525.67 149665.61 189915.22
##               Villavicencio
## Bogotá             29062.28
## Medellín          109461.81
## Cali              104353.14
## Barranquilla      212993.14
## Bucaramanga       113411.86
## Manizales          93031.08
## Pereira            82466.17
## Cúcuta            139318.94
## Pasto             177380.67
## Ibagué             59687.33
## Montería          159389.86
## Cartagena         199124.83
## Villavicencio          0.00

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
## Bogotá           0.000  417.481  458.065     1031.865     397.691   292.735
## Medellín       417.643    0.000  435.431      757.549     382.925   222.528
## Cali           447.213  436.690    0.000     1190.940     761.751   260.576
## Barranquilla  1084.736  775.897 1209.163        0.000     696.208   996.260
## Bucaramanga    397.323  382.414  815.680      678.754       0.000   602.777
## Manizales      292.816  223.365  258.579      977.615     507.782     0.000
## Pereira        306.893  240.304  209.055      994.553     557.359    53.340
## Cúcuta         567.848  579.058 1012.324      768.323     197.783   799.421
## Pasto          823.277  812.754  385.581     1567.004    1137.814   636.640
## Ibagué         201.412  359.844  261.148     1032.582     509.888   172.881
## Montería       749.832  456.592  889.858      355.453     606.446   676.954
## Cartagena      998.540  705.300 1136.174      128.704     622.505   923.270
## Villavicencio  120.953  532.176  546.401     1146.559     517.879   409.555
##                Pereira   Cúcuta    Pasto   Ibagué Montería Cartagena
## Bogotá         316.705  568.423  779.875  201.485  731.138   980.257
## Medellín       239.279  580.658  808.736  349.545  456.822   705.941
## Cali           208.947  959.483  381.282  252.616  890.213  1139.332
## Barranquilla  1013.011  786.102 1582.468 1028.506  372.461   141.135
## Bucaramanga    619.528  198.492 1188.985  540.293  605.889   623.087
## Manizales       53.264  705.515  631.884  163.530  676.888   926.007
## Pereira          0.000  755.092  582.360  112.296  693.826   942.945
## Cúcuta         816.172    0.000 1385.629  736.937  703.956   712.656
## Pasto          585.011 1335.547    0.000  628.680 1266.277  1515.395
## Ibagué         119.788  707.620  634.453    0.000  731.856   980.974
## Montería       693.706  706.422 1263.163  709.201    0.000   252.270
## Cartagena      940.022  712.400 1509.479  957.909  248.372     0.000
## Villavicencio  405.041  688.611  868.211  289.820  845.833  1094.951
##               Villavicencio
## Bogotá              122.056
## Medellín            532.086
## Cali                535.507
## Barranquilla       1142.977
## Bucaramanga         519.321
## Manizales           446.422
## Pereira             395.188
## Cúcuta              689.846
## Pasto               911.571
## Ibagué              289.706
## Montería            823.672
## Cartagena          1072.379
## Villavicencio         0.000

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
## Bogotá             0.00  78659.68  86306.32    194418.84    74930.95  55155.67
## Medellín       78690.21      0.00  82041.73    142733.59    72148.81  41927.61
## Cali           84261.64  82278.95      0.00    224390.96   143525.31  49096.43
## Barranquilla  204380.53 146190.63 227824.45         0.00   131176.03 187710.33
## Bucaramanga    74861.61  72052.53 153686.35    127887.43        0.00 113572.23
## Manizales      55170.93  42085.32  48720.16    184197.33    95673.75      0.00
## Pereira        57823.24  45276.88  39389.10    187388.70   105014.80  10050.06
## Cúcuta        106991.08 109103.21 190737.03    144763.58    37265.28 150622.91
## Pasto         155117.74 153135.04  72649.24    295247.06   214381.22 119952.53
## Ibagué         37949.04  67800.01  49204.20    194553.94    96070.55  32573.37
## Montería      141279.60  86028.78 167662.60     66972.68   114263.52 127548.29
## Cartagena     188139.91 132889.10 214072.22     24249.76   117289.28 173957.92
## Villavicencio  22789.36 100269.94 102950.14    216028.91    97576.17  77166.31
##                 Pereira    Cúcuta     Pasto    Ibagué  Montería Cartagena
## Bogotá         59671.97 107099.42 146940.15  37962.80 137757.37 184695.12
## Medellín       45083.75 109404.68 152377.99  65859.52  86072.12 133009.87
## Cali           39368.75 180780.99  71839.25  47596.64 167729.48 214667.24
## Barranquilla  190866.47 148113.41 298160.71 193785.96  70177.24  26591.95
## Bucaramanga   116728.37  37398.87 224022.61 101799.31 114158.58 117398.94
## Manizales      10035.74 132929.61 119056.42  30811.50 127535.85 174473.61
## Pereira            0.00 142270.66 109725.36  21158.25 130727.23 177664.98
## Cúcuta        153779.05      0.00 261073.29 138849.98 132635.87 134275.08
## Pasto         110224.85 251637.09      0.00 118452.74 238585.58 285523.15
## Ibagué         22569.86 133326.22 119540.46      0.00 137892.65 184830.22
## Montería      130704.62 133100.50 237998.86 133624.11      0.00  47531.45
## Cartagena     177114.25 134226.85 284408.49 180484.42  46797.01      0.00
## Villavicencio  76315.80 129744.64 163583.98  54606.44 159367.62 206305.19
##               Villavicencio
## Bogotá             22997.18
## Medellín          100252.98
## Cali              100897.55
## Barranquilla      215354.01
## Bucaramanga        97847.87
## Manizales          84112.60
## Pereira            74459.35
## Cúcuta            129977.33
## Pasto             171753.65
## Ibagué             54584.96
## Montería          155192.16
## Cartagena         202052.29
## Villavicencio          0.00

Costo de los peajes

Teniendo en cuenta los datos suministrados por (Peajes, 2025) se creó la siguiente matriz con los costos de peaje en COP por cada ruta:

##           Tiempo Bogotá Medellín  Cali Barranquilla Bucaramanga Manizales
## 1         Bogotá      0    23800 21400        17900       16200     14400
## 2       Medellín  23800        0 20200        19200       18500     12600
## 3           Cali  21400    20200     0        10400       10900     10400
## 4   Barranquilla  17900    19200 10400            0       10900     10600
## 5    Bucaramanga  16200    18500 10900        10900           0     10800
## 6      Manizales  14400    12600 10400        10600       10800         0
## 7        Pereira  15200    14200 10500        10600       10800     10500
## 8         Cúcuta  11700    17000 10300        10600       10800     10500
## 9          Pasto  13300    19800 12700        12700       10800     10500
## 10        Ibagué  11700    15200 10400        10600       10800     10500
## 11      Montería  15900    20200 10500        10600       10800     10500
## 12     Cartagena  19400    21400 10400        10600       10800     10500
## 13 Villavicencio  13900    12600 10400        10600       10800     10500
##    Pereira Cúcuta Pasto Ibagué Montería Cartagena Villavicencio
## 1    15200  11700 13300  11700    15900     19400         13900
## 2    14200  17000 19800  15200    20200     21400         12600
## 3    10500  10300 12700  10400    10500     10400         10400
## 4    10600  10600 12700  10600    10600     10600         10600
## 5    10800  10800 10800  10800    10800     10800         10800
## 6    10500  10500 10500  10500    10500     10500         10500
## 7        0  10300 10300  10300    10300     10300         10300
## 8    10300      0 10300  10300    10300     10300         10300
## 9    10300  10300     0  10300    10300     10300         10300
## 10   10300  10300 10300      0    10300     10300         10300
## 11   10300  10300 10300  10300        0     10300         10300
## 12   10300  10300 10300  10300    10300         0         10300
## 13   10300  10300 10300  10300    10300     10300             0

_

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
## Bogotá             0.00 185661.43 197035.23     387366.1   178210.01 139700.14
## Medellín      185778.18      0.00 171076.70     289375.4   155625.34  91708.25
## Cali          191336.89 170807.36      0.00     428149.7   282449.15 102771.90
## Barranquilla  415822.48 293524.94 433665.97          0.0   263115.86 362100.22
## Bucaramanga   175446.22 155739.23 297082.96     260948.2        0.00 225214.51
## Manizales     139798.93  91725.84 102444.13     356868.2   199068.33      0.00
## Pereira       136811.52  99537.88  83623.54     363080.0   218182.13  32230.47
## Cúcuta        228982.78 235715.91 377956.94     306777.9    93679.53 306388.49
## Pasto         327120.51 314290.99 165492.80     574333.3   426232.59 246755.53
## Ibagué         90658.49 153411.23 112951.51     373704.9   190096.55  85104.01
## Montería      296751.82 180759.81 320003.54     139251.2   224731.02 248234.90
## Cartagena     386847.11 268557.79 408952.75      57143.6   239445.28 337284.11
## Villavicencio  67473.39 224449.58 223321.20     430051.4   225517.14 185415.36
##                 Pereira    Cúcuta    Pasto    Ibagué Montería Cartagena
## Bogotá        141502.89 230917.95 323130.1  88546.32 274945.1 365635.15
## Medellín       99527.98 238512.43 317268.4 146243.52 179954.4 268341.76
## Cali           82886.47 366238.74 168385.0 105965.84 317828.6 404918.71
## Barranquilla  368319.94 306309.69 582557.7 382057.62 141976.2  62061.67
## Bucaramanga   231434.23  96251.59 443574.7 211908.44 223901.3 240683.91
## Manizales      32243.10 283155.41 249135.9  77958.64 246347.1 333537.19
## Pereira            0.00 302069.21 230015.3  57540.47 252361.7 339549.04
## Cúcuta        312410.91      0.00 524548.7 292885.12 281893.8 286313.64
## Pasto         226570.10 510122.37      0.0 249749.46 461512.3 548702.15
## Ibagué         63519.16 273983.44 259440.5      0.00 262984.1 350173.94
## Montería      254254.81 278370.61 466395.3 267992.50      0.0 101564.98
## Cartagena     343304.02 282439.29 555444.5 354590.48 100256.6      0.00
## Villavicencio 173888.86 282225.09 357418.8 124432.10 319333.2 406520.41
##               Villavicencio
## Bogotá             65959.46
## Medellín          222314.79
## Cali              215650.69
## Barranquilla      438947.15
## Bucaramanga       222059.73
## Manizales         187643.68
## Pereira           167225.51
## Cúcuta            279596.28
## Pasto             359434.32
## Ibagué            124572.29
## Montería          324882.02
## Cartagena         411477.12
## Villavicencio          0.00

Algoritmo Ant System aplicado al problema TSP

## [1] "Ruta cerrada:"

## $tour
##  [1]  1 13 10  7  6  3  9  2  5  8 12  4 11
## 
## $distance
## [1] 190.5323
## 
## $tour
##  [1]  1 13 10  7  6  3  9  2  5  8 12  4 11

Gráfico

Algoritmo evolutivo

## Generación 1 : Mejor costo = 2172297.71238833 
## Generación 2 : Mejor costo = 2430026.47026944 
## Generación 3 : Mejor costo = 2724549.76080778 
## Generación 4 : Mejor costo = 2283951.24055667 
## Generación 5 : Mejor costo = 2457936.6816 
## Generación 6 : Mejor costo = 2311094.81782222 
## Generación 7 : Mejor costo = 2271320.55635222 
## Generación 8 : Mejor costo = 2271320.55635222 
## Generación 9 : Mejor costo = 2271320.55635222 
## Generación 10 : Mejor costo = 2271320.55635222 
## Generación 11 : Mejor costo = 2271320.55635222 
## Generación 12 : Mejor costo = 2271320.55635222 
## Generación 13 : Mejor costo = 2436313.77227 
## Generación 14 : Mejor costo = 2436313.77227 
## Generación 15 : Mejor costo = 2672225.46690167 
## Generación 16 : Mejor costo = 2525578.29092444 
## Generación 17 : Mejor costo = 2525578.29092444 
## Generación 18 : Mejor costo = 2402621.31950333 
## Generación 19 : Mejor costo = 2742172.97034667 
## Generación 20 : Mejor costo = 2584812.55708611 
## Generación 21 : Mejor costo = 2330499.20682333 
## Generación 22 : Mejor costo = 2330499.20682333 
## Generación 23 : Mejor costo = 2309728.00835778 
## Generación 24 : Mejor costo = 2429482.03772611 
## Generación 25 : Mejor costo = 2612827.49839389 
## Generación 26 : Mejor costo = 2695556.69052833 
## Generación 27 : Mejor costo = 2721071.56136278 
## Generación 28 : Mejor costo = 2755857.86579778 
## Generación 29 : Mejor costo = 2755857.86579778 
## Generación 30 : Mejor costo = 2729571.06832833 
## Generación 31 : Mejor costo = 2501453.04112944 
## Generación 32 : Mejor costo = 2603863.89988833 
## Generación 33 : Mejor costo = 2559922.39429889 
## Generación 34 : Mejor costo = 2559922.39429889 
## Generación 35 : Mejor costo = 2505598.60077056 
## Generación 36 : Mejor costo = 2398641.14848611 
## Generación 37 : Mejor costo = 2428795.25626556 
## Generación 38 : Mejor costo = 2351145.54617833 
## Generación 39 : Mejor costo = 2214879.00741056 
## Generación 40 : Mejor costo = 2509816.68121667 
## Generación 41 : Mejor costo = 2400193.65343833 
## Generación 42 : Mejor costo = 2324145.24431556 
## Generación 43 : Mejor costo = 2400193.65343833 
## Generación 44 : Mejor costo = 2335291.47796556 
## Generación 45 : Mejor costo = 2400193.65343833 
## Generación 46 : Mejor costo = 2411591.59586222 
## Generación 47 : Mejor costo = 2325476.32788833 
## Generación 48 : Mejor costo = 2217604.61174056 
## Generación 49 : Mejor costo = 2408631.75130556 
## Generación 50 : Mejor costo = 2306235.61877833 
## Generación 51 : Mejor costo = 2306235.61877833 
## Generación 52 : Mejor costo = 2450244.48298444 
## Generación 53 : Mejor costo = 2675889.96988722 
## Generación 54 : Mejor costo = 2544403.29188278 
## Generación 55 : Mejor costo = 2491042.00198778 
## Generación 56 : Mejor costo = 2441207.76716833 
## Generación 57 : Mejor costo = 2791340.78917778 
## Generación 58 : Mejor costo = 2603047.44081111 
## Generación 59 : Mejor costo = 2411310.10088444 
## Generación 60 : Mejor costo = 2001761.04675722 
## Generación 61 : Mejor costo = 2001761.04675722 
## Generación 62 : Mejor costo = 1959353.66140167 
## Generación 63 : Mejor costo = 2610038.82732278 
## Generación 64 : Mejor costo = 2509600.38266111 
## Generación 65 : Mejor costo = 2557451.39110944 
## Generación 66 : Mejor costo = 2398578.86016222 
## Generación 67 : Mejor costo = 2387192.21744611 
## Generación 68 : Mejor costo = 2288813.802705 
## Generación 69 : Mejor costo = 2291674.74942222 
## Generación 70 : Mejor costo = 2291674.74942222 
## Generación 71 : Mejor costo = 2238903.90452056 
## Generación 72 : Mejor costo = 2394554.33708944 
## Generación 73 : Mejor costo = 2394554.33708944 
## Generación 74 : Mejor costo = 2489654.21374222 
## Generación 75 : Mejor costo = 2595765.93301278 
## Generación 76 : Mejor costo = 2523240.93455556 
## Generación 77 : Mejor costo = 2523240.93455556 
## Generación 78 : Mejor costo = 2266468.062765 
## Generación 79 : Mejor costo = 2449438.46253944 
## Generación 80 : Mejor costo = 2481580.80852444 
## Generación 81 : Mejor costo = 2481580.80852444 
## Generación 82 : Mejor costo = 2127427.28114056 
## Generación 83 : Mejor costo = 2424300.29277111 
## Generación 84 : Mejor costo = 2581559.58724722 
## Generación 85 : Mejor costo = 2638411.27599667 
## Generación 86 : Mejor costo = 2846617.22092833 
## Generación 87 : Mejor costo = 2749982.49894556 
## Generación 88 : Mejor costo = 2559087.42223167 
## Generación 89 : Mejor costo = 2147754.18716611 
## Generación 90 : Mejor costo = 2147754.18716611 
## Generación 91 : Mejor costo = 2600515.58346944 
## Generación 92 : Mejor costo = 2602883.89923889 
## Generación 93 : Mejor costo = 2536886.36828222 
## Generación 94 : Mejor costo = 2460103.11892111 
## Generación 95 : Mejor costo = 2460103.11892111 
## Generación 96 : Mejor costo = 2460103.11892111 
## Generación 97 : Mejor costo = 2366585.86915222 
## Generación 98 : Mejor costo = 2609407.53325167 
## Generación 99 : Mejor costo = 2556917.91184833 
## Generación 100 : Mejor costo = 2609407.53325167

## Mejor ruta encontrada: 1 11 3 8 2 6 5 7 12 13 4 10 9

## Costo total de la ruta: 1959354

## Generación en la que se encontró el mejor costo: 62

Bibliofía

1. DANE. (2025). DANE. Boletines. Recuperado 29 de abril de 2025, de https://www.dane.gov.co/files/investigaciones/boletines/ech/ech/pres_web_empleo_rueda_prensa_ene_20.pdf
2. 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
3. Huang, H., Qiu, J., & Riedl, K. (2023). On the global convergence of particle swarm optimization methods. Applied Mathematics & Optimization, 88(2), Article 30. https://doi.org/10.1007/s00245-023-09983-3
4. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
5. IBM. (n.d.). ¿Qué es el descenso del gradiente?. Recuperado el 29 de abril de 2025, de https://www.ibm.com/mx-es/think/topics/gradient-descent
6. 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.
7. Peajes. (2016, February 8). https://www.invias.gov.co/index.php/listado-tarifas-peajes-2
8. Salario para Transporte De Carga en Colombia - Salario Medio. (n.d.). Talent.com. https://co.talent.com/salary?job=transporte+de+carga
9. Simon Fraser University. (s.f.). Six-Hump Camel Function. Recuperado el 29 de abril de 2025, de https://www.sfu.ca/~ssurjano/camel6.html
10. 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
11. Wikipedia. (s.f.). Descenso del gradiente. Recuperado el 29 de abril de 2025, de https://es.wikipedia.org/wiki/Descenso_del_gradiente
12. Wikipedia contributors. (s.f.). Griewank function. Wikipedia. https://en.wikipedia.org/wiki/Griewank_function
13. Wikipedia contributors. (2025, February 20). Problema del viajante. Wikipedia, La Enciclopedia Libre. https://es.wikipedia.org/wiki/Problema_del_viajante

Repositorio Github: https://github.com/AlejandroTorradoCalderon/Optimizacion-heuristica-RNA

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.