0. Introdución

La optimización es un arquetipo en multitud de ramas científicas e ingenieriles que se muestra a la búsqueda de las “mejores” soluciones posibles dentro de un conjunto de respuestas alternativas. En términos más generales, es una atenuación o la maximización de una función objetivo cunado se fijan condiciones en unas y a otras variables. Este enfoque es imperativo para la toma de decisiones rentables, la planificación de sistemas y la administración de problemas consolidados en campos que van desde la economía y la logística hasta la IA y el sendo aprendizaje.

Este proyecto consiste en estudiar y analizar distintas metodologías de optimización, ya sean numéricas o por combinatoria. En este caso, se comenzará explorando la optimización de funciones continuas y luego se avanzará a un problema clásico de optimización discreta.

En la Parte 1: Optimización Numérica, se analizará el desempeño de los métodos que utilizan el descenso por gradiente frente a heurísticas y metaheurísticas, tales como algoritmos evolutivos, optimización por enjambre de partículas y evolución diferencial en el cálculo de mínimos globales en funciones de prueba. Dos funciones de prueba representativas, la Función de Rosenbrock y la Función de Rastrigin, serán seleccionadas debido a la presencia de mínimos locales y valles angostos, lo que constituye un rigoroso desafío para los algoritmos. La optimización se llevará a cabo en 2D y 3D, considerando distintos niveles de complejidad del espacio de búsqueda. La visualización de la trayectoria de búsqueda de cada método, así como el análisis de su efectividad, permitirá valorar estos métodos respecto al valor final de la función objetivo y el número de evaluaciones.

En la Parte 2: Optimización Combinatoria, se verá el conocido Problema del Viajante de Comercio, que es un reto NP-hard en logística y planificación de rutas. El propósito es encontrar la ruta más eficiente que un vendedor use para visitar las 13 ciudades principales de Colombia, su costo debe ser el mínimo posible. Para este fin, se acudir propuesto seis sesiones que se relacionan con el uso de colonias artificiales de hormigas y algoritmos genéticos, dos técnicas metaheurísticas de resolución de problemas complejos a gran escala basadas en la naturaleza. Los costes a tener en cuenta incluyen tiempo del vendedor, peajes y combustible. Posteriormente, se mostrará la solución más óptima encontrada en un mapa de la República de Colombia.

Con este estudio, se espera que el participante haya comprendido los aspectos positivos y negativos de cada uno de los métodos de optimización utilizados, así como conocer el orden en el que son más útiles para problemas reales. La investigación y propuesta brindan evaluación exhaustiva a los resultados y diferentes metodologías de optimización a partir de la visualización conseguirán expresar el alcance y convergencia del trabajo realizado.

1. Optimización numérica

En este primer punto se estudian y comparan distintos métodos de optimización aplicados a funciones no lineales. El objetivo es analizar el desempeño de algoritmos clásicos como el descenso por gradiente frente a métodos heurísticos inspirados en procesos evolutivos y naturales. Para ello, se seleccionaron dos funciones de prueba con características distintas que permiten evaluar la eficacia y eficiencia de cada enfoque. Se realizarán optimizaciones en espacios de dos y tres dimensiones, partiendo de condiciones iniciales aleatorias. Además, se visualizará el proceso de búsqueda de soluciones mediante animaciones.Para finalmente comparar como fue el comportamiento de los métodos y como el tipo de función impacta en la elección del método.

1.1 Función de Rastrigin

La función Rastrigin es una función comúnmente utilizada para evaluar algoritmos de optimización, ya que presenta múltiples mínimos locales. Se define matemáticamente como:

\[ f(\mathbf{x}) = A n + \sum_{i=1}^{n} \left[ x_i^2 - A \cos(2 \pi x_i) \right] \] Fórmula 1 - Función de Rastrigin

Donde:

  • 𝐴 es una constante (por lo general 10),
  • 𝑛 es la dimensión del vector 𝑥,
  • 𝑥 es el vector de entrada.

\(\mathbf{x} = (x_1, x_2, \ldots, x_n) \in \mathbb{R}^n\)

Propiedades de la Función Rastrigin:

  • Por convención A toma el valor de 10.
  • Mínimo Global en \(\mathbf{x} = (0, 0, \ldots, 0)\) valor mínimo \(f(\mathbf{x}) = 0\)
  • Multimodalidad: Tiene múltiples mínimos locales.
  • Dominio típico \(x_i \in [-5.12,\ 5.12],\quad \text{para } i = 1, 2, \ldots, n\)
  • Continuidad: Es continua y suave (diferenciable).
  • Separabilidad: Es separable, porque puede expresarse como la suma de funciones de una sola variable.

Visualización de la función Rastrigin en 1D

La función Rastrigin es ampliamente utilizada en la optimización heurística para evaluar algoritmos debido a su estructura multimodal: contiene un gran número de mínimos locales repartidos en todo el espacio de búsqueda. Esta gráfica representa la versión unidimensional de dicha función.

  • El eje X representa los valores de entrada x.
  • El eje Y muestra los valores evaluados de la función f(x).
  • Los puntos rojos marcan los mínimos locales situados en cada número entero entre −5 y +5.
  • El patrón de ondulación refleja la naturaleza periódica de la función, lo que la convierte en un reto ideal para técnicas como algoritmos genéticos, ACO, PSO, entre otros.

Esta figura permite intuir el reto que supone encontrar el mínimo global, ya que un algoritmo puede quedar atrapado fácilmente en un mínimo local si no está bien diseñado.

**Fig 1.** Visualización de la función Rastrigin f(x1) (1D)

Fig 1. Visualización de la función Rastrigin f(x1) (1D)

Análisis del gráfico “Rastrigin 1-D — campo de pozos periódicos”

Elemento visual Observación Interpretación
Línea negra dentada Ondas regulares de amplitud creciente al alejarse del centro. Resultado de la combinación \(x^2+cos(2\pi x)\). El término cuadrático empuja hacia arriba (crece como cuenco), el coseno introduce la ondulación periódica.
Puntos rojos (11) Un punto rojo en cada entero desde −5 hasta 5. Representan los mínimos locales: los pozos donde un optimizador basado solo en gradientes podría quedar atrapado.
Valle más profundo en \(x=0\) Punto rojo más bajo (\(f(x)=0\)). Mínimo global de la función.
Simetría izquierda-derecha La curva es espejo respecto a \(x=0\). Tanto \(x^2\) como \(cos(2\pi x)\) son funciones pares → la función es simétrica.
Incremento de altura hacia los extremos Las puntas laterales alcanzan \(f(x)\approx40\) . Dominio del término \(x^2\). Cuanto más lejos del centro, más alto el coste.

  1. Alta multimodalidad
    Once pozos en un intervalo de solo 10 unidades indican que la función está plagada de óptimos locales.

  2. Periodocidad
    La distancia constante entre picos (\(\approx 1\)) viene del \(cos(2\pi x)\); cada ciclo completo genera un pozo.

Grafico de la función de Rastrigin (2D)

**Fig 2** Visualización de la función Rastrigin f(x1) (2D)

Fig 2 Visualización de la función Rastrigin f(x1) (2D)

Análisis del gráfico “Rastrigin 2-D — campo de minas”

Elemento visual

Gradiente de color (barra a la derecha)

Qué se observa

Verde muy oscuro → Valores cercanos a 0.
Amarillo → \(f(\mathbf{x})\approx40\).
Rosa-blanco → \(f(\mathbf{x})\approx80\) (más alto).

Qué significa

Indica la altura de la función \(f(x_1,x_2)\). Los colores claros son “cerros”; los oscuros, “valles”.
Estrella negra en (0, 0) Único punto marcado en el centro. Mínimo global: \(f(0,0) = 0\). Cualquier optimizador querrá llegar aquí.
Malla gris punteada Líneas cada unidad en ambos ejes. Subraya que la función es separable y periódica: los mínimos locales se repiten exactamente en cada entero.
Óvalos verdes/amarillos repetidos Patrón regular horizontal y vertical. Cada óvalo es un pozo local; la cuadrícula entera corresponde a la estructura \(cos(2\pi x_i)\) de Rastrigin.

  1. Alta multimodalidad
    Hay decenas de valles; un descenso por gradiente típico corre riesgo de quedar atrapado en cualquiera de ellos.

  2. Separabilidad
    Las líneas punteadas muestran que los mínimos están exactamente en los cruces de enteros (x1,x2)∈Z2. La función puede verse como la suma de dos copias 1-D independientes.

  3. Incremento radial suave
    A medida que nos alejamos del centro, los colores se vuelven lentamente rosados

  4. “Campo de minas”
    Optimizar aquí es como cruzar un terreno lleno de cráteres: cada cuadrícula contiene un pozo que puede atrapar al algoritmo.

Grafico de la función de Rastrigin (3D)

**Fig 3.** Visualización de la función Rastrigin f(x1, x2, x3) (3D)

Fig 3. Visualización de la función Rastrigin f(x1, x2, x3) (3D)

Superficie 3-D de la función Rastrigin en dos dimensiones.

Se aprecia un cuenco global con un mosaico de mínimos locales periódicos.

El mínimo global está en (0,0) y las crestas alcanzan valores de \(f(\mathbf{x})=80\).

  • Implicaciones para la optimización

    • Gradiente “traicionero”
      Desde un punto alto, el gradiente guía hacia el valle más cercano, no el global; por eso un descenso por gradiente sencillo suele frenarse en uno de esos cráteres periféricos.

    • Incremento radial suave + oscilación fina
      La combinación hace que los valles laterales sean relativamente profundos: un algoritmo necesita capacidad de exploración para saltar varias crestas y acercarse al centro.

    • Métodos locales (GD, Newton) requieren muchos reinicios o mejoras (momentum, annealing).

    • Estrategias bioinspiradas (PSO, hormigas) o cuasi-Newton (L-BFGS-B) suelen rendir mejor, porque pueden escapar de pozos.

1.1.1 Gradiente de la función Rastrigin(GD)

Para aplicar métodos de optimización basados en gradientes (como el descenso del gradiente), es fundamental calcular la derivada de la función objetivo. En este caso, definimos el gradiente de la función Rastrigin, una función no convexa ampliamente usada como benchmark debido a su gran cantidad de mínimos locales.

  • Esta derivada parcial nos indica la dirección de máxima pendiente.
  • El algoritmo de optimización usará esta información para “bajar” hacia un mínimo (local o global).
  • El gradiente de Rastrigin se deriva analíticamente y se expresa como:

\[ \nabla f(x) = 2x + 2\pi A \cdot \sin(2\pi x) \]

donde: - \(A\) es una constante (típicamente 10), - \(x\) es el vector de entrada.

A continuación, definimos este gradiente como una función vectorial en R.

Descenso del Gradiente (Gradient Descent) sobre la función Rastrigin

El descenso del gradiente (GD) es uno de los algoritmos fundamentales de optimización. A partir de una posición inicial \(\mathbf{x}_0\), el algoritmo actualiza esa posición en la dirección opuesta al gradiente, con el objetivo de minimizar la función.

En cada iteración \(k\), el algoritmo realiza:

\[ \mathbf{x}_{k+1} = \mathbf{x}_k - \eta \cdot \nabla f(\mathbf{x}_k) \]

donde: - \(\eta\) es la tasa de aprendizaje (learning rate), - \(\nabla f(\mathbf{x}_k)\) es el gradiente en la posición actual, - \(\mathbf{x}_{k+1}\) es la nueva posición.

En esta sección: - Implementamos GD para la función Rastrigin, - Almacenamos el historial de posiciones y valores \(f(\mathbf{x})\) en cada iteración, - Permitimos controlar el número de iteraciones y el tamaño de paso \(\eta\).

Esta versión aún no reinicia desde distintos puntos, pero sirve para visualizar cómo se comporta el descenso desde una posición dada.

Trayectoria de GD puro sobre Rastringin (1D)

En este experimento aplicamos el descenso del gradiente puro sobre la función Rastrigin en 1 dimensión, comenzando desde un punto inicial \(x_0 = 3\).

Objetivos: - Observar cómo evoluciona el algoritmo hacia un mínimo local. - Visualizar la trayectoria del descenso sobre la gráfica de la función. - Identificar el punto de inicio y el punto final del algoritmo.

Detalles clave: - Se usó una tasa de aprendizaje \(\eta = 0.01\). - Se grafican las evaluaciones sucesivas \(f(x_k)\) como una curva azul. - El punto inicial se marca en rojo y el final en negro.

Este gráfico nos permite ver si el algoritmo converge al mínimo esperado, y cómo desciende el valor de la función a lo largo de las iteraciones.

**Fig 4.** Visualización de la función Rastrigin óptimo en f(x1) (1D)

Fig 4. Visualización de la función Rastrigin óptimo en f(x1) (1D)

Color / Símbolo

▲ Negro

Significado correcto

Punto inicial \(\mathbf{x_0}\approx2.9\). El descenso por gradiente parte aquí, en la ladera alta del valle.
🔴 Rojo Punto final: mínimo local alcanzado tras 200 iteraciones, \(x\approx2.8\)x≈2.8 con \(14\lessapprox f(\mathbf{x})\lessapprox15\)
Zona azul Todos los pasos intermedios; muestra cómo GD oscila dentro del mismo valle hasta estabilizarse en el punto rojo.

Análisis

  1. Descenso rápido
    El algoritmo parte del punto negro (valor f≈27) y se desliza cuesta abajo siguiendo el gradiente.

  2. Oscilaciones amortiguadas
    En azul se ve cómo va rebotando a ambos lados del eje del valle. Cada rebote es más pequeño porque el gradiente se reduce a medida que se acerca al fondo.

  3. Convergencia local, fracaso global:
    El algoritmo se detiene en el punto rojo, el fondo del pozo local. Allí la pendiente es prácticamente nula y se cumple el criterio de paro. Queda atrapado en el primer mínimo local encontrado.

  4. Influencia del punto de partida: cualquier inicio en el intervalo \([2.5,\ 3.5]\) produciría resultados parecidos; reiniciar desde zonas distintas sólo trasladaría el problema a otros pozos.

  5. Distancia al óptimo global
    El óptimo global de Rastrigin (\(\mathbf{x}=0, f=0\)) queda fuera de la zona azul; GD nunca lo “visita”. Esto evidencia la limitación de los métodos locales en funciones multimodales.

  6. Necesidad de estrategias complementarias: para alcanzar el óptimo global en Rastrigin se requieren técnicas que permitan “saltar” valles (momentum, tasa de aprendizaje adaptativa, meta-heurísticas globales).

1.1.2 Trayectoria del Gradiente Descendente en Rastrigin 2D

En esta sección visualizamos cómo se comporta el algoritmo de Gradiente Descendente (GD) al intentar minimizar la función Rastrigin en dos dimensiones.

  • La función Rastrigin es altamente no convexa y está plagada de mínimos locales, lo que representa un desafío para algoritmos que siguen únicamente el gradiente.
  • Partimos desde el punto inicial (3, 3) y realizamos 200 iteraciones con una tasa de aprendizaje constante.
  • Se representa la superficie de la función mediante un mapa de calor y curvas de nivel, y sobre ella se traza el camino recorrido por GD.
  • El punto negro representa el inicio, mientras que el rojo indica el punto final, típicamente atrapado en un mínimo local.

Esta visualización ayuda a entender por qué GD puro puede ser insuficiente en funciones con topologías complejas como Rastrigin.

**Fig 5.** Visualización de la función Rastrigin óptimo f(x1, x2) (2D)

Fig 5. Visualización de la función Rastrigin óptimo f(x1, x2) (2D)

Trayectoria de GD puro sobre Rastringin (2D)

Descripción del gráfico

Elemento Significado
🔵 Trayectoria azul Secuencia de pasos que toma Gradient Descent desde el punto inicial.
⚫ Círculo negro (Inicio) Posición de partida \((3,\ 3)\) del algoritmo.
🔺 Triángulo rojo (Fin) Mínimo local donde GD queda atrapado tras 200 iteraciones.
Mapa de colores (f(x)) Valor de la función Rastrigin; violeta oscuro (\(\approx0\)) (valles), amarillo (\(\approx 80\)) (picos).

Análisis del comportamiento del algoritmo

Observación Interpretación
El recorrido es muy corto y se queda en la parte superior-derecha. GD se vio atraído por el valle local más próximo y no dispuso de mecanismos para “saltar” la siguiente cresta.
Valor final (\(f(\mathbf{x})=17\)) frente al mínimo global \(f(\mathbf{x})=0\). Confirma el estancamiento prematuro en un óptimo local.
Trayectoria casi rectilínea hacia un solo pozo. El gradiente inicial apunta con fuerza a la depresión más cercana; tras llegar al fondo la norma del gradiente se vuelve pequeña y el algoritmo se detiene.

En funciones altamente multimodales como Rastrigin, el número de valles hace muy improbable que GD, partiendo lejos del origen, alcance el mínimo global.

Animacion de la trayectoria de GD puro sobre Rastringin (2D)

A continuación, presentamos una animación que muestra paso a paso cómo el algoritmo de Gradiente Descendente puro recorre el paisaje de la función Rastrigin en dos dimensiones:

  • Se parte desde el punto inicial (3, 3), con una tasa de aprendizaje fija y sin reinicios.
  • Cada punto negro representa una posición evaluada por el algoritmo en una iteración.
  • La línea roja muestra la trayectoria seguida.
  • El fondo es una superficie coloreada según los valores de la función (mapa de calor con curvas de nivel).

Esta visualización dinámica permite observar cómo el gradiente guía la búsqueda hacia un mínimo cercano, pero también ilustra la tendencia del GD a quedarse atrapado en mínimos locales, lo que refuerza la necesidad de métodos más robustos como los algoritmos evolutivos o de enjambre en problemas no convexos.

Dinámica observada

  1. Inicio en un pico elevado
    Al “play”, el punto negro parte en una zona amarilla (valor alto de \(f(\mathbf{x})\)), indicando un punto inicial lejos del mínimo.

  2. Descenso pronunciado
    En las primeras iteraciones, el punto negro se desplaza rápidamente hacia regiones más oscuras (valores de f decrecientes), cayendo dentro de un pozo local.

  3. Estabilización
    Una vez dentro del valle, la trayectoria azul rodea el fondo con pequeños vaivenes, reflejando zig-zags de GD puro en un entorno multimodal.

  4. Sin escape del mínimo local
    A pesar de varias decenas de iteraciones, el punto nunca atraviesa la cresta que llevaría al valle central

1.1.3 Implementación de GD en Rastrigin 3D

Animacion de la trayectoria de GD puro sobre Rastringin (3D)

La siguiente animación 3D muestra cómo se comporta el Gradiente Descendente (GD) en una versión bidimensional de la función Rastrigin (representada en 3D con los ejes x₁, x₂ y f(x)).

  • La superficie ondulada representa el paisaje de la función objetivo, caracterizado por numerosos mínimos locales.
  • La línea de colores muestra la trayectoria seguida por el algoritmo desde el punto inicial (3, 3).
  • El punto negro se mueve en cada iteración y representa la posición actual del algoritmo.
  • El rombo amarillo indica el mínimo local alcanzado en el recorrido (el mejor punto encontrado).
  • Esta animación permite observar cómo el GD puede descender rápidamente hacia un valle, pero puede quedar atrapado en óptimos locales sin alcanzar la mejor solución global.

Este tipo de visualización es clave para entender por qué el Gradiente Descendente puro necesita ser complementado con otras estrategias en problemas no convexos.

Fig 7. Visualización de la función Rastrigin óptimo f(x1, x2, x3) (3D)

Elemento Significado
Superficie translúcida (Viridis) Muestra el paisaje completo de la función Rastrigin: valles profundos (violeta) y picos altos (amarillo).
🟠 Línea multicolor (“Trayectoria”) Cada tonalidad marca un paso de GD: del azul al naranja conforme avanza la iteración.
⚫ Punto negro (“Punto actual”) Indica la posición de GD en la iteración mostrada.
Diamante amarillo (“Óptimo encontrado”) Señala el mínimo local donde el algoritmo quedó atrapado.
▶️⏸️ Controles Play/Pause + slider | Permiten navegar interactivamente por las iteraciones. | | | | | | | | | | | | | | | | | | |

Comportamiento de GD en 3D

  1. Descenso inicial:
    Desde el punto \((3,\ 3)\), GD baja rápidamente por la “pared” del valle, capturado por el gradiente pronunciado.

  2. Ingreso en un cráter local:
    Tras unas pocas iteraciones, la trayectoria desciende al fondo de un pozo lateral, lejos del centro \((0,\ 0)\).

  3. Estancamiento y micro-oscillaciones:
    Dentro de ese cráter, GD gira en pequeños zig-zags alrededor de un mínimo que no es el global.

  4. No alcanza el mínimo global:
    El diamante amarillo permanece alejado del valle central de la superficie, confirmando la captura en un mínimo local.

1.1.4 Algoritmos evolutivos

En esta sección aplicamos un Algoritmo Genético (GA) para encontrar el mínimo global de la función Rastrigin en dos dimensiones.

El GA es un algoritmo inspirado en la evolución biológica que utiliza procesos como selección natural, cruces (recombinación) y mutaciones para explorar el espacio de búsqueda. A diferencia del Gradiente Descendente, los GAs no necesitan derivadas, lo que los hace ideales para funciones no derivables o con múltiples mínimos locales como Rastrigin.

Parámetros configurados:

  • type = "real-valued": cada individuo es un vector de números reales.
  • fitness = -rastrigin(x): usamos el negativo porque GA maximiza por defecto.
  • lower y upper: definen los límites del dominio.
  • popSize = 50: la población inicial tiene 50 soluciones candidatas.
  • maxiter = 100: el algoritmo se ejecuta por un máximo de 100 generaciones.
  • run = 50: detención temprana si no hay mejora durante 50 generaciones consecutivas.

A continuación, se ejecuta el algoritmo y se muestra un resumen del mejor resultado obtenido.

Dos dimensiones

## ── Genetic Algorithm ─────────────────── 
## 
## GA settings: 
## Type                  =  real-valued 
## Population size       =  50 
## Number of generations =  100 
## Elitism               =  2 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## Search domain = 
##          x1    x2
## lower -5.12 -5.12
## upper  5.12  5.12
## 
## GA results: 
## Iterations             = 100 
## Fitness function value = -4.038806e-05 
## Solution = 
##                 x1           x2
## [1,] -2.041459e-05 0.0004507303

Animación del Algoritmo Genético sobre Rastrigin 2D

Para entender mejor el comportamiento del Algoritmo Genético (GA) durante la optimización de la función Rastrigin en dos dimensiones, hemos generado una animación que muestra la evolución de la población a lo largo de las generaciones:

  • En cada iteración, se guarda la posición de todos los individuos de la población sobre el plano (x₁, x₂).
  • Cada punto azul semitransparente representa una solución candidata evaluada por el algoritmo.
  • Las poblaciones sucesivas tienden a concentrarse en las regiones más prometedoras, lo cual permite visualizar el proceso de convergencia hacia un mínimo global.

Este tipo de animación es útil para observar: - La diversidad poblacional a lo largo del tiempo, - La velocidad de convergencia, - Y posibles atascos en óptimos locales.

En este chunk se genera el GIF de forma automática, guardando los frames en una carpeta temporal y combinándolos con magick en un archivo GIF animado, el cual se almacena como rastrigin_ga_animation.gif dentro de la carpeta Trabajo1_files/.

**Fig 8.** Animación Algoritmos evolutivos 2D

Fig 8. Animación Algoritmos evolutivos 2D

Tres dimensiones

**Fig 9.** Animación Algoritmos evolutivos 3D

Fig 9. Animación Algoritmos evolutivos 3D

1.1.5 Optimización de partículas

**Fig 10.** Animación Optimización de particulas 2D

Fig 10. Animación Optimización de particulas 2D

1.1.6 Evolución diferencial

**Fig 11.** Animación Optimización de particulas 2D de la Función Rastrigin

Fig 11. Animación Optimización de particulas 2D de la Función Rastrigin

1.2 Función de Rosenbrock

La función de Rosenbrock de forma generalizada para para n variables se define como:

\[ f(\mathbf{x}) = \sum_{i=1}^{n-1} \left[ a - x_i \right]^2 + b \left( x_{i+1} - x_i^2 \right)^2 \] Fórmula 2 - Función de Rosenbrock Donde, \(\mathbf{x} = (x_1, x_2, \ldots, x_n) \in \mathbb{R}^n\)

Propiedades de la Función Rosenbrock:

  • \(a\) y \(b\) son parámetros que controlan la forma de la función. Típicamente, \(a = 1\) y \(b=100\).
  • Para estos parámetros comunes el mínimo global se va encontrar en el conjunto de coordenadas \((x_1, x_2, \ldots, x_n) = (1, 1, \ldots, 1)\) donde \(f(\mathbf{x^*}) = 0\)
  • Tipo de función: No convexa, suave (diferenciable) y unimodal.
  • Dominio típico \(x_i \in (-\infty, \infty), \quad \text{para } i = 1, 2, \ldots, n\)
  • Tiene una forma de valle largo, estrecho y curvado.El gradiente es pequeño en muchas partes, lo que hace difícil que métodos de gradiente converjan rápidamente.
  • Separabilidad: Es separable, porque puede expresarse como la suma de funciones de una sola variable.

Probamos los minimos globales, para distintos números de variables:

rosenbrock_n(c(1,1)) 
## [1] 0
rosenbrock_n(c(1,1,1)) 
## [1] 0
rosenbrock_n(c(1,1,1,1))
## [1] 0

Procedemos a visualizar la función para los casos de dos y tres variables, ya que con una sola variable esta se reduce a una parábola convexa simple. Esta forma trivial no representa un reto significativo para los métodos de optimización, por lo que no resulta adecuada para los fines de este análisis.

Visualización en 3d para dos variables (x1,x2)

Fig 12. Visualización de la función Rosenbrock f(x1,x2) (3D)

En la visualización 3D de la función de Rosenbrock en dos dimensiones, con variables (x1,x2), se observa un paisaje caracterizado por un valle estrecho, curvado y alargado. El mínimo global se encuentra en el punto (x1,x2)=(1,1), pero el camino hacia este mínimo no es directo.

La superficie tiene una pendiente suave que desciende hacia el fondo del valle, mientras que los bordes laterales presentan pendientes pronunciadas, formando una especie de “canal en forma de U” que se curva a lo largo del plano. Esta topografía hace que, aunque el gradiente siempre apunte hacia el mínimo, los métodos de optimización puedan desviarse, oscilar o converger lentamente si no están bien ajustados.También da la sensación de que la función es simétrica alrededor de x2=0, teniendo así dos mínimos globales, lo cual en verdad no es cierto.

Visualización en 2d del mapa de calor, vista superior para dos variables (x1,x2)

**Fig 13.** Mapa de Calor de la Función Rosenbrock

Fig 13. Mapa de Calor de la Función Rosenbrock

Optimización de la Función de Rosenbrock para dos y tres dimensiones

1.2.1 Optimización por descenso del gradiente

Se utiliza un punto inicial aleatorio dentro del rango [−3,3] y [3,-3,3] y a partir de allí el algoritmo busca aproximarse al mínimo global de la función, se utiliza el método BFGS (Broyden–Fletcher–Goldfarb–Shanno) ya que es un algoritmo de optimización mucho eficiente y robusto para funciones suaves y no lineales, como es el caso de la función Rosenbrock.

1.2.2 Optimización con Algorimos Genéticos (GA)

En este caso se define un espacio de búsqueda continuo en el rango [−3,3] para x1,x2 y x3 y se configura una población inicial de 50 individuos. El algoritmo evoluciona durante un máximo de 100 iteraciones o hasta que no se observe mejora en 50 generaciones consecutivas.

1.2.3 Optimización por enjambre de partículas (PSO)

De nuevo comenzamos con una posición aleatoria en el rango [−3,3] para cada una de las variables variables y se realiza hasta 100 iteraciones para encontrar el mínimo.

1.2.4 Evolución Diferencial (DE)

En este caso establecemos una población inicial de 50 individuos (NP = 50) y se permiten hasta 100 iteraciones (itermax = 100) para la optimización. En este caso también se busca el mínimo de la función dentro del rango [−3,3] para todas las variables.

A continuación observamos los resultados obtenidos, de la optimización de la función de Rosenbrock para dos variables, con los cuatro métodos.

Resultados Optimización de Rosenbrock para dos dimensiones (x1,x2)
Método Valor de x1 Valor de x2 Valor Función Objetivo Número de Evaluaciones
Descenso por gradiente 0.9998331 0.9996662 0.00e+00 53
Algoritmos evolutivos 0.9856456 0.9707295 -2.65e-04 2500
Optimización de partículas 1.0037167 1.0074443 1.38e-05 1200
Evolución Diferencial 1.0000652 1.0001343 0.00e+00 3500

Para dos dimensiones los resultados nos muestran que todos los métodos lograron aproximarse al mínimo global de la función de Rosenbrock, aunque con diferencias significativas en eficiencia y precisión. El método de descenso por gradiente (BFGS) fue el más eficiente, alcanzando un valor prácticamente óptimo con solo 53 evaluaciones. En contraste, los métodos heurísticos requirieron muchas más evaluaciones: evolución diferencial logró un valor casi perfecto con 3500 evaluaciones, mientras que PSO alcanzó un resultado muy cercano al óptimo con 1200 evaluaciones. Por su parte, el algoritmo evolutivo fue el menos preciso, con un valor ligeramente más alejado del óptimo y un costo computacional alto (2500 evaluaciones). En resumen, los métodos tradicionales como el gradiente descendente son más eficientes cuando la función es suave y bien comportada, mientras que los métodos heurísticos ofrecen robustez frente a funciones complejas, aunque con mayor costo computacional. Es importante recordar que en el caso de métodos basados en gradiente as condiciones iniciales juegan un papel crucial en la optimización, ya que pueden determinar si el algoritmo converge rápidamente o queda atrapado en regiones poco prometedoras.

Resultados Optimización de Rosenbrock en tres dimensiones (x1,x2,x3)
Método Valor de x1* Valor de x2* Valor de x3* Valor Óptimo de la Función Objetivo Número de Evaluaciones
Descenso por gradiente 0.9998799 0.9997602 0.9995203 0.0000001 143
Algoritmos evolutivos 0.5741961 0.3335581 0.1089820 -0.6274608 2500
Optimización de partículas 0.7731997 0.5999325 0.5999325 0.2178242 1300
Evolución Diferencial 1.0347233 1.0661181 1.0661181 0.0110632 3500

El descenso por gradiente (BFGS) es el método más eficiente, logrando el valor óptimo con solo 143 evaluaciones. Los algoritmos evolutivos requieren 2500 evaluaciones, pero terminan con un valor de función objetivo significativamente más alejado del mínimo. La optimización por partículas (PSO) logra un valor positivo con 1300 evaluaciones, pero no se aproxima tanto al óptimo como el descenso por gradiente. Finalmente, la evolución diferencial con 3500 evaluaciones también se queda cerca del óptimo, pero no supera al gradiente. En general, los métodos heurísticos necesitan más evaluaciones y no alcanzan la precisión del descenso por gradiente.

1.2.5 Animación del Descenso del Gradiente.

**Fig 14.** Animación Descenso del gradiente 2D

Fig 14. Animación Descenso del gradiente 2D

1.2.6 Animación Evolución Diferencial

**Fig 15.** Animación Evolución Diferencial 2D

Fig 15. Animación Evolución Diferencial 2D

1.2.7 Animación Algoritmos Evolutivos

**Fig 16.** Animación Algoritmos Evolutivos 2D

Fig 16. Animación Algoritmos Evolutivos 2D

1.2.8 Animación Optimización por enjambre de Particulas

**Fig 17.** Animación Optimización PSO 2D

Fig 17. Animación Optimización PSO 2D

Conclusión Final

Los métodos de descenso por gradiente, como BFGS, mostraron una gran eficiencia y precisión al optimizar funciones suaves y bien comportadas como Rosenbrock, alcanzando el mínimo global con un número muy reducido de evaluaciones. Su capacidad para aprovechar la derivada y la curvatura de la función les permite converger rápidamente cuando se parte de condiciones iniciales razonables. No obstante, su principal desventaja es la dependencia del punto de inicio: si se inicia en una región poco favorable, el algoritmo puede no converger al mínimo global o hacerlo muy lentamente.

Por otro lado, los métodos heurísticos —como algoritmos genéticos, enjambre de partículas y evolución diferencial— aportan robustez frente a funciones no convexas y multimodales, como la función Rastrigin, donde los métodos de gradiente frecuentemente quedan atrapados en mínimos locales. En este contexto, los heurísticos son capaces de explorar mejor el espacio de búsqueda, gracias a su componente estocástico y su capacidad para escapar de óptimos locales. Sin embargo, su mayor fortaleza —la exploración— implica también un mayor costo computacional y, en muchos casos, una menor precisión final comparada con los métodos basados en gradiente.

En resumen, los métodos de gradiente son ideales cuando se conoce que la función es suave y tiene una topografía favorable, mientras que los métodos heurísticos resultan más apropiados para problemas con múltiples óptimos locales o funciones no diferenciables, aunque a un mayor costo computacional. El uso conjunto o híbrido de ambos enfoques puede ofrecer lo mejor de ambos mundos: eficiencia local y exploración global.

2. Optimización combinatoria

2.2 🐜 ¿Cómo funciona el algoritmo de colonia de hormigas?

En la naturaleza, las hormigas encuentran caminos óptimos hacia fuentes de comida gracias a un mecanismo simple pero poderoso: feromonas.

¿Cómo funciona en la naturaleza?

  1. Una hormiga sale a explorar y elige un camino al azar.
  2. Si encuentra comida, regresa dejando un rastro químico (feromona).
  3. Otras hormigas detectan ese rastro y tienen mayor probabilidad de seguirlo.
  4. Cuantas más lo sigan, más feromona se acumula, reforzando ese camino.
  5. El camino más corto se refuerza naturalmente, porque se recorre más veces en menos tiempo.

¿Cómo se traduce eso en el algoritmo?

Elemento natural Equivalente en algoritmo
Hormiga Individuo que genera una ruta completa
Camino entre ciudades Arista entre nodos en el grafo
Feromona Valor en una matriz de feromonas
Decisión de ruta Selección probabilística basada en feromona y distancia
Evaporación Reducción periódica del valor de feromonas
Reforzamiento Aumento de feromonas según calidad de ruta
Tabla 3: Equivalencia del algoritmo de la hormiga viajera

Fórmula clásica de decisión (simplificada):

\[ \text{Probabilidad de ir a ciudad } j = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{k \in \text{no visitadas}} [\tau_{ik}]^\alpha \cdot [\eta_{ik}]^\beta} \]

Formula 3: Fórmula clásica de decisión
  • \(\tau_{ij}\): nivel de feromona entre ciudad \(i\) y \(j\)
  • \(\eta_{ij}\): heurística (usualmente \(1/\text{distancia}_{ij}\))
  • \(\alpha\): peso de la feromona
  • \(\beta\): peso de la heurística

Esta metáfora permite que las hormigas artificiales encuentren rutas cortas y eficientes, reforzando caminos que producen soluciones buenas.

2.1 Definición del conjunto de ciudades y fórmula del costo total

Antes de aplicar el algoritmo de optimización (Colonia de Hormigas), se define el conjunto de ciudades colombianas que serán los nodos del problema del viajante (TSP). Estas ciudades corresponden a centros urbanos relevantes desde el punto de vista económico y geográfico.

A continuación, se muestra el vector ciudades que contiene los 13 puntos de interés del recorrido:

  • Bogotá
  • Medellín
  • Cali
  • Barranquilla
  • Cartagena
  • Bucaramanga
  • Cúcuta
  • Pereira
  • Manizales
  • Ibagué
  • Santa Marta
  • Villavicencio
  • Neiva

Para evaluar cada posible recorrido entre dos ciudades \(i\) y \(j\), se define una función de costo total realista, que toma en cuenta tres componentes fundamentales:

  1. Costo de los peajes en la vía entre \(i\) y \(j\)
  2. Costo de la gasolina, calculado a partir de la distancia entre las ciudades y un precio estimado por kilómetro
  3. Valor del tiempo invertido, usando una estimación del salario por hora multiplicado por el tiempo de viaje

La fórmula usada para calcular este costo total es la siguiente:

\[ CT_{ij} = PrecioPeajes_{ij} + Distancia_{ij}(km) \times PrecioGasolina\text{ por km} + Salario\text{ (Horas)} \times Tiempo_{ij}\text{ (Horas)} \]

Formula 4: Fórmula Costo total

Esta función permite crear una matriz de costos \(C \in \mathbb{R}^{13 \times 13}\), que servirá como base para evaluar la calidad de cada ruta generada por las hormigas artificiales.

2.2 Lectura de matrices de insumo para el cálculo de costos

Una vez definido el conjunto de ciudades, se procede a cargar tres matrices fundamentales que contienen la información base para calcular los costos de viaje entre pares de ciudades. Estos datos fueron obtenidos previamente mediante web scraping desde el sistema Hermes del Instituto Nacional de Vías (Invías) o construidos manualmente a partir de fuentes oficiales.

Archivos cargados:

  1. matriz_distancia.csv
    Contiene la distancia en kilómetros entre cada par de ciudades.
    Cada celda \((i, j)\) representa la distancia estimada entre la ciudad \(i\) y la ciudad \(j\).

  2. matriz_tiempos.csv
    Contiene el tiempo promedio estimado de viaje en horas entre ciudades.
    Este valor se usará para calcular el costo por tiempo laboral.

  3. matriz_peajes.csv
    Contiene el valor total de los peajes en la ruta más frecuente o directa entre las ciudades.
    Se expresa en pesos colombianos (COP).

Estas matrices conforman la base para calcular el costo total de traslado entre ciudades. Todas son de dimensión \(13 \times 13\), correspondientes al número de ciudades consideradas.

A continuación, se cargan usando la función read.csv(), y se establece la primera columna como nombres de fila (ciudades).

2.3 Asignación de nombres a filas y columnas de las matrices

Después de cargar las matrices de distancias, tiempos y peajes, es esencial asegurarse de que sus filas y columnas estén correctamente etiquetadas con los nombres de las ciudades involucradas.

Este paso garantiza que:

  • Se puedan identificar correctamente los pares de ciudades al consultar las matrices.
  • Se mantenga la consistencia semántica cuando se accede a los datos con matriz[i, j], sabiendo que i y j representan nombres de ciudades y no solo índices numéricos.

Se realiza la asignación usando el vector ciudades, previamente definido, de la siguiente forma:

  • colnames(...) <- ciudades: asigna los nombres de ciudades a las columnas (destinos).
  • rownames(...) <- ciudades: asigna los nombres a las filas (orígenes).

Esto aplica a las tres matrices:

  • matriz_distancia
  • matriz_tiempos
  • matriz_peajes

Este paso es clave para asegurar que, al momento de combinar los datos en el cálculo del costo total, se referencien correctamente los trayectos entre pares de ciudades por nombre.

2.4 Cálculo de matrices de costo: gasolina y tiempo laboral

Con las matrices de distancia y tiempo ya organizadas y etiquetadas, se procede a calcular los dos primeros componentes del costo total asociado a un viaje entre dos ciudades.

1. Costo de gasolina

Se estima a partir de la distancia entre ciudades y un costo promedio por kilómetro de recorrido, asumiendo un rendimiento promedio del vehículo y un precio fijo por galón de gasolina.

matriz_costo_gasolina <- 191 * matriz_distancia

Se asume un valor de 191 COP por kilómetro, calculado a partir de:

  • Precio de gasolina: 16,000 COP/galón
  • Rendimiento del vehículo: 83.66 km/galón

\[ \frac{16,\!000}{83.66} \approx 191 \, \text{COP/km} \]

Calculo 1: Costo de gasolina

2. Costo por tiempo laboral

Se estima el valor económico del tiempo que toma realizar cada trayecto, calculado con base en un salario mínimo diario y una jornada laboral estándar.

matriz_costo_salario <- 5416 * matriz_tiempos

Se asume un valor de 5,416 COP por hora, que se obtiene a partir de:

  • Salario mínimo diario: 54,116 COP
  • Jornada laboral: 10 horas

\[ \frac{54,\!116}{10} = 5,\!416 \, \text{COP/hora} \]

Calculo 2: Costo por tiempo laboral

Este valor busca reflejar el costo de oportunidad del tiempo invertido en el traslado, importante en contextos donde el tiempo laboral tiene un valor económico directo (por ejemplo, logística, transporte, comercio).

Las dos matrices obtenidas (matriz_costo_gasolina y matriz_costo_salario) serán combinadas con la matriz de peajes para formar la matriz final de costos totales entre ciudades, la cual alimentará al algoritmo de optimización basado en colonia de hormigas.

2.5 Construcción de la matriz de costo total entre ciudades

En esta etapa se integran los tres componentes del costo de viaje para cada trayecto entre ciudades, con el objetivo de construir una matriz única y coherente de costos totales.

Esta matriz será utilizada como entrada directa del algoritmo de colonia de hormigas para resolver el problema del viajante (TSP), optimizando el recorrido de menor costo.

Fórmula aplicada:

La matriz total se construye sumando:

  • Costo por peajes (matriz_peajes)
  • Costo de gasolina (matriz_costo_gasolina)
  • Costo de tiempo laboral (matriz_costo_salario)
matriz_costo_total <- matriz_peajes + matriz_costo_gasolina + matriz_costo_salario

Finalmente, se asegura que el resultado se exprese como una matriz numérica bien definida mediante:

matriz_costo_total <- as.matrix(matriz_costo_total)

Resultado:

La matriz matriz_costo_total tiene dimensión \(13 \times 13\) y representa el costo total estimado (en pesos COP) de trasladarse entre todas las combinaciones posibles de ciudades.

Esta matriz es la base del problema de optimización, ya que permite calcular el costo total de cada ruta propuesta por el algoritmo de colonia de hormigas.

2.6 Implementación del algoritmo de colonia de hormigas (ACO)

En esta sección se implementa el algoritmo de optimización basado en la colonia de hormigas (Ant Colony Optimization, ACO), una metaheurística inspirada en el comportamiento colectivo de las hormigas reales cuando buscan caminos eficientes entre su nido y fuentes de alimento.

Inicialización de parámetros

Se definen los parámetros clave del algoritmo:

  • cities_count = 13: número de ciudades (nodos en el grafo)
  • eroso_influence = 1: influencia de la feromona en la toma de decisiones (\(\alpha\))
  • visibility_influence = 2: influencia de la visibilidad (inversa del costo, \(\beta\))
  • evap_rate = 0.5: tasa de evaporación de las feromonas
  • pheromone_strength = 100: intensidad del refuerzo de feromonas por ruta
  • ants_count = 13: una hormiga por ciudad
  • cities_names: nombres de las ciudades según rownames de la matriz de costos

También se inicializan las dos matrices clave:

  • tau_matrix: matriz de feromonas, con valores iniciales en 1
  • eta_matrix: matriz de visibilidad, definida como la inversa del costo total

Bucle principal de búsqueda (100 iteraciones)

El algoritmo se ejecuta durante 100 iteraciones. En cada una:

  1. Cada hormiga construye una ruta comenzando desde una ciudad aleatoria.

  2. En cada paso, elige la siguiente ciudad de forma probabilística según:

    \[ P_{ij} \propto [\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta \]

    Formula 5: Siguiente ciudad

    Donde:

    • \(\tau_{ij}\) es la feromona acumulada entre ciudad \(i\) y ciudad \(j\)
    • \(\eta_{ij} = 1 / \text{Costo}_{ij}\), es la visibilidad
    • \(\alpha = 1\), \(\beta = 2\)

  3. Se calcula el costo total del recorrido incluyendo el regreso a la ciudad de origen.

  4. Se actualiza la mejor ruta encontrada hasta el momento si se obtiene un menor costo.

Evaporación y refuerzo de feromonas

Al finalizar cada iteración:

  • Se evapora un porcentaje fijo de todas las feromonas:

    tau_matrix <- tau_matrix * (1 - evap_rate)

  • Cada hormiga deposita feromona en su ruta proporcional a la calidad de la solución:

    tau_matrix[i, j] <- tau_matrix[i, j] + Q / costo

    Esto refuerza los caminos más eficientes, favoreciendo su elección en futuras iteraciones.

Resultado

Al finalizar el bucle:

  • Se obtiene best_path: la mejor ruta encontrada
  • Se transforma best_path_names a nombres de ciudades, incluyendo el retorno al origen
  • Se imprime el costo mínimo por iteración

Este procedimiento permite encontrar una solución aproximada al problema del viajante usando un enfoque inspirado en inteligencia colectiva.

Esta es una poderosa técnica para resolver problemas NP-duros donde no se puede garantizar una solución exacta en tiempo razonable, pero se puede obtener una solución cercana al óptimo con eficiencia práctica.

2.7 Resultados finales: mejor ruta y análisis de costos

Una vez finalizadas las 100 iteraciones del algoritmo ACO, se procede a imprimir los resultados de la mejor solución encontrada.

Mejor ruta encontrada

Se presenta la secuencia de ciudades que conforma la ruta de menor costo total, según el criterio del algoritmo. Esta secuencia incluye el regreso a la ciudad de origen, completando el circuito.

El resultado se imprime con flechas (→) entre ciudades para facilitar su lectura.

Detalle de costos por tramo

Para cada par de ciudades consecutivas en la ruta, se muestra:

  • Origen
  • Destino
  • Costo del trayecto individual, según la matriz de costo total

Esta sección permite descomponer el total en segmentos y analizar qué tramos son más costosos o representan cuellos de botella.

Estadísticas resumen

Se imprimen al final las siguientes métricas globales del recorrido:

  • Número total de ciudades visitadas, incluyendo el retorno
  • Costo total del recorrido
  • Costo promedio por tramo
  • Iteración en la que se encontró la mejor ruta

Estas estadísticas permiten validar la eficiencia del resultado, compararlo con otras ejecuciones del algoritmo, y usarlo como base para visualizaciones, informes o decisiones logísticas.

💡 Este reporte final es ideal tanto para evaluación académica como para aplicaciones prácticas (por ejemplo, en logística, distribución, rutas comerciales o planificación territorial).

2.8 Análisis final de resultados

Luego de 100 iteraciones del algoritmo de colonia de hormigas (ACO), se obtuvo la ruta de menor costo total para visitar todas las ciudades, incluyendo el retorno al punto de partida.

Mejor ruta encontrada

La secuencia óptima de ciudades es la siguiente:

Cúcuta → Bucaramanga → Santa Marta → Barranquilla → Cartagena → Medellín → 
Manizales → Ibagué → Pereira → Cali → Neiva → Bogotá → Villavicencio → Cúcuta

Esta ruta minimiza el costo total estimado considerando peajes, gasolina y tiempo de conducción, y representa la solución más eficiente hallada por el algoritmo.

Detalle de costos por tramo

A continuación se muestra el costo individual de cada trayecto entre pares consecutivos de ciudades:

Origen Destino Costo (COP)
Cúcuta Bucaramanga $73,397.27
Bucaramanga Santa Marta $208,392.43
Santa Marta Barranquilla $46,121.28
Barranquilla Cartagena $56,307.19
Cartagena Medellín $298,235.20
Medellín Manizales $117,686.23
Manizales Ibagué $89,019.42
Ibagué Pereira $59,348.34
Pereira Cali $111,118.18
Cali Neiva $120,726.62
Neiva Bogotá $152,503.69
Bogotá Villavicencio $88,845.24
Villavicencio Cúcuta $232,569.62
Tabla 4: Detalle de costos por ruta - Hormiga Viajera

Estadísticas generales

  • Número total de ciudades (incluyendo el regreso): 14
  • Costo total del recorrido: $1,654,270.71 COP
  • Costo promedio por tramo: $127,251.59 COP
  • Iteración en la que se encontró la mejor solución: 41

Interpretación

Este resultado demuestra cómo el enfoque de colonia de hormigas es capaz de encontrar soluciones eficientes a problemas complejos como el del viajante (TSP), incorporando restricciones realistas como costos por distancia, tiempo y peajes.

La solución obtenida puede servir como base para:

  • Optimización logística de rutas de transporte.
  • Análisis de costos en distribución.
  • Planeación territorial y de infraestructura.

2.9 Visualización interactiva de la ruta óptima

Para complementar el análisis numérico y facilitar la interpretación geoespacial de los resultados, se construye un mapa interactivo que representa gráficamente la ruta óptima encontrada por el algoritmo de colonia de hormigas.

Componentes de la visualización

  • Se usa la librería leaflet para generar un mapa interactivo con zoom, etiquetas y trazados dinámicos.
  • Las rutas entre ciudades se calculan utilizando osrmRoute, que obtiene trayectos realistas en carretera.
  • Los puntos en el mapa representan las ciudades y están etiquetados con su orden de visita.
  • Las líneas rojas indican el recorrido secuencial que debe seguirse.
  • El mapa se ajusta automáticamente para mostrar toda la ruta.

Lógica del código

  1. Se recorre la secuencia best_path_names, obtenida del algoritmo ACO.
  2. Para cada par consecutivo de ciudades, se consulta la API de OSRM para obtener la ruta vial real (con manejo de errores y reintentos).
  3. Las rutas individuales se combinan en un solo objeto espacial (sf) para dibujar el trayecto completo.
  4. Se agregan:
    • Círculos azules para marcar las ciudades.
    • Números en negrita sobre cada ciudad que indican el orden de visita.
    • Un zoom centralizado sobre el mapa de Colombia.

Resultado

El resultado es una visualización intuitiva e interactiva de la ruta más eficiente para visitar todas las ciudades, teniendo en cuenta el costo total estimado (peajes + gasolina + tiempo).

Esta representación es especialmente útil en entornos logísticos, educativos o de presentación de resultados, ya que permite comunicar de forma clara y atractiva el producto del modelo de optimización.

Fig 18. Ruta Óptima

Visualización de la Ruta Óptima (Animación)

A continuación, se muestra una animación de la ruta óptima.

Fig. 19. Animación que ilustra la ruta óptima encontrada. El recorrido conecta las ciudades principales de manera eficiente, mostrando dinámicamente la secuencia de la visita.

Los supuestos del problema del viajero son los siguientes:

2.10 Resolución del TSP con Algoritmo Genético (GA)

Los algoritmos genéticos (GA) son técnicas de optimización bioinspiradas, basadas en el principio de selección natural propuesto por Darwin. Se utilizan ampliamente para resolver problemas complejos de búsqueda, como el del Viajante de Comercio (TSP).

¿Cómo funciona un GA?

  • Una población de posibles soluciones (rutas) es generada aleatoriamente.
  • Cada ruta es evaluada usando una función de aptitud (fitness), que mide qué tan buena es la solución.
  • A través de ciclos (llamados generaciones), se seleccionan las mejores rutas, se combinan (cruce) y se modifican (mutación), generando nuevas rutas potencialmente mejores.
  • El proceso se repite hasta cumplir un criterio: alcanzar un número máximo de generaciones o encontrar una mejora mínima.

Aplicación al TSP

En el contexto del TSP:

  • Cada individuo es una permutación del conjunto de ciudades (un recorrido completo).
  • La función fitness busca minimizar el costo total de recorrer todas las ciudades y volver al origen.
  • Se emplea la matriz matriz_costo_total, que ya incluye el costo por peajes, tiempo laboral y gasolina.
  • Al finalizar, obtenemos una ruta que aproxima la mejor solución posible usando este enfoque heurístico.

En esta sección, se define el entorno necesario para ejecutar el algoritmo genético con el paquete GA. A continuación se cargan las librerías, se define la función de evaluación y se prepara la estructura de coordenadas.

Preparación del entorno para el Algoritmo Genético

En este chunk se cargan las librerías necesarias y se definen las funciones de soporte:

Elemento Propósito Detalles clave
GA Implementación estándar de algoritmos genéticos. Permite representar rutas como permutaciones y ajustar parámetros como popSize, pmutation, maxiter.
ggplot2 / ggrepel Visualización y anotación de gráficas. Se usarán más adelante para animar la evolución y rotular ciudades.
animation Generación de GIFs desde R. Facilita guardar cuadros de la evolución del GA.

Funciones definidas
- tourLength()
- Recibe una permutación (tour) y devuelve el costo total acumulado según matriz_costo_total.
- tspFitness()
- Convierte el problema de minimizar costo en maximizar aptitud, usando la relación fitness = 1/costo.

Se extraen además las coordenadas (x, y) de coords_df que servirán para graficar rutas y animaciones posteriores.

Ejecución principal del GA

En este chunk se lanza el algoritmo genético con los parámetros escogidos para el TSP:

  • Población (popSize = 100): incrementa la diversidad de soluciones por generación.
  • Generaciones máximas (maxiter = 3000): otorga tiempo suficiente para converger.
  • Mutación (pmutation = 0.3): introduce variación y evita estancamiento en óptimos locales.
  • Parada temprana (run = 200): si en 200 generaciones no mejora el mejor fitness, se detiene para ahorrar tiempo.
  • type = "permutation": cada individuo es una permutación de índices de ciudades.

El objeto resultante GAiter guarda: 1. @solution — mejor ruta encontrada.
2. @fitnessValue — aptitud asociada (inverso del costo).
3. @iter — número de generación en que se logró el óptimo.

Impresión organizada de la ruta óptima y sus costos

Este chunk formatea la salida al estilo utilizado en la sección de ACO:

  1. Ruta óptima GA — lista ordenada de ciudades con flechas.
  2. Tabla de costos por tramo — muestra origen, destino y costo monetario.
  3. Estadísticas globales:
    • Número de ciudades (incluye el regreso al origen).
    • Costo total de la ruta.
    • Costo promedio por tramo.
    • Generación en la que se halló el mejor resultado.

Así, el lector puede comparar rápidamente la solución del GA con la obtenida por la colonia de hormigas.

Análisis de la ruta óptima obtenida con el Algoritmo Genético (GA)

1. Resumen de la solución

La mejor ruta hallada por el GA recorre las 13 ciudades y regresa al origen en el siguiente orden:

Ibagué → Pereira → Cali → Neiva → Bogotá → Villavicencio →

Cúcuta → Bucaramanga → Santa Marta → Barranquilla → Cartagena →

Medellín → Manizales → Ibagué

  • Ciudades visitadas (incluye retorno): 14
  • Costo total: $ 1 654 270,71 COP
  • Costo promedio por tramo: $ 127 251,59 COP
  • Generación en la que se encontró el óptimo: 436

2. Detalle de costos por tramo

# Origen Destino Costo (COP)
1 Ibagué Pereira 59 348,34
2 Pereira Cali 111 118,18
3 Cali Neiva 120 726,62
4 Neiva Bogotá 152 503,69
5 Bogotá Villavicencio 88 845,24
6 Villavicencio Cúcuta 232 569,62
7 Cúcuta Bucaramanga 73 397,27
8 Bucaramanga Santa Marta 208 392,43
9 Santa Marta Barranquilla 46 121,28
10 Barranquilla Cartagena 56 307,19
11 Cartagena Medellín 298 235,20
12 Medellín Manizales 117 686,23
13 Manizales Ibagué 89 019,42
Tabla 5: Detalle de costos por ruta - Algoritmos Geneticos

3. Segmentos más costosos

Tramo Costo (COP) % del costo total
Cartagena → Medellín 298 235,20 18 %
Villavicencio → Cúcuta 232 569,62 14 %
Bucaramanga → Santa Marta 208 392,43 13 %
Tabla 6: Segmentos más costosos

Observación:
Tres tramos (Cartagena → Medellín, Villavicencio → Cúcuta y Bucaramanga → Santa Marta) concentran ≈45 % del presupuesto total. Optimizar o replantear estos saltos tendría el mayor impacto económico.

4. Interpretación logística

  1. Fluidez geográfica – La secuencia avanza de forma continua por el eje cafetero, se desplaza al sur (Neiva), retorna al centro (Bogotá), cruza al oriente y luego asciende hasta la costa atlántica antes de volver por Antioquia y Caldas; evita saltos innecesarios.
  2. Equilibrio de costos – Los tramos cortos de la región Andina equilibran los tramos largos hacia y desde la costa, manteniendo un promedio estable.
  3. Puntos de optimización – Revisar rutas o transportes alternos para los tres tramos más caros podría reducir significativamente el gasto total.

5. Recomendaciones técnicas

  • Parametrización del GA
    • Si se requiere mayor precisión, aumentar popSize o maxiter, o ajustar pmutation entre 0.2 – 0.4.
  • Análisis de sensibilidad
    • Evaluar cómo variaciones en precio del combustible, peajes o salario/hora afectan la ruta óptima.
  • Exportación de resultados
    • Guardar la ruta y costos en CSV/GeoJSON para sistemas GIS o planificación logística.

📝 Conclusión:
El GA proporciona una ruta económicamente sólida y geográficamente coherente. Las áreas de mayor impacto en costos están claramente identificadas, ofreciendo puntos de partida concretos para futuras optimizaciones.

Mapa interactivo de la ruta óptima (GA)

Al igual que con ACO, se crea un mapa leaflet que:

  1. Traza la ruta definitiva con líneas verde-oscuro (darkgreen).
  2. Marca las ciudades con círculos azules y etiquetas de nombre.
  3. Numera el orden de visita encima de cada punto para facilitar la lectura de la secuencia.
  4. Centra el zoom en el promedio de longitudes y latitudes, mostrando todo el recorrido a escala nacional.

La función get_route() devuelve geometrías realistas vía OSRM; si la API falla, se dibuja una línea recta de respaldo, garantizando siempre la visualización.

Fig20Ruta óptima encontrada con GA

Animación de la evolución genética

Para ilustrar visualmente cómo el GA refina la ruta a lo largo del tiempo, se genera un GIF:

  • Iteraciones capturadas: se toman 10 puntos equiespaciados desde la generación 300 hasta la final (GAiter@iter).
  • Re-ejecución incremental: se crea un GA temporal (tempGA) con maxiter = i para cada cuadro, asegurando que el gráfico refleje el estado real en esa generación.
  • Visualización:
    • Puntos azules → ciudades.
    • Segmentos con flecha en color steelblue → recorrido actual.
    • Título dinámico con número de generación.

animation::saveGIF() compila las 10 imágenes en ga_tsp_route.gif. Se fijó interval = 1 s para evitar conflictos con fps.

## [1] TRUE

Visualización de la Ruta Óptima (Animación)

A continuación, se muestra una animación de la ruta óptima.

Fig. 22. Animación que ilustra la ruta óptima encontrada. El recorrido conecta las ciudades principales de manera eficiente, mostrando dinámicamente la secuencia de la visita.

2.11 Comparativo: Algoritmo Genético (GA) vs Colonia de Hormigas (ACO)

A continuación se presentan los hallazgos clave al contrastar ambos enfoques heurísticos aplicados al mismo problema del viajante (TSP) con idéntica matriz de costos y conjunto de ciudades.

1. Métricas principales de desempeño

Métrica GA ACO Observaciones
Costo total (COP) 1 654 270,71 1 654 270,71 Coinciden al peso: ambos alcanzan el mismo óptimo global.
Costo medio por tramo 127 251,59 127 251,59 Igual — confirma que la secuencia de tramos es la misma (rota).
N.º de tramos (incl. retorno) 14 14 Idéntico. La única diferencia es la ciudad donde inicia el ciclo.
Generación/iteración óptima 436 de 3 000 41 de 100 ACO converge ~10 × más rápido en términos relativos.
Evaluaciones de costo 436 × 100 ≈ 43 600 41 × 13 ≈ 533 GA requiere órdenes de magnitud más evaluaciones.
Parámetros críticos popSize, pmutation, maxiter evap_rate, n_hormigas GA sensible a 3–4 hiperparámetros, ACO a 2–3.
Tiempo de cómputo† ~90 s ~8 s †Medido en un portátil i5; variará con hardware.
Tabla 7: Comparativo: Algoritmo Genético (GA) vs Colonia de Hormigas (ACO)

2. Coincidencias y diferencias cualitativas

  1. Misma ruta cíclica
    • GA: inicia en Ibagué.
    • ACO: inicia en Cúcuta.
    • En TSP la rotación no cambia el costo; ambas soluciones son equivalentes.
  2. Patrones de convergencia
    • GA mejora gradualmente por cruce y mutación; necesita mayor población y más generaciones.
    • ACO refuerza rápidamente los mejores arcos mediante feromonas; converge antes pero puede estancarse si evap_rate es muy bajo.
  3. Diversidad y exploración
    • GA preserva diversidad con mutación (pmutation = 0.3), pero el progreso se ralentiza cuando la población se vuelve homogénea.
    • ACO depende de la evaporación para escapar de óptimos locales; demasiada evaporación genera ruido, muy poca genera sobre-explotación.

3. Ventajas y desventajas operativas

Criterio GA ACO
Velocidad de convergencia ❌ Lenta (436 gen) ✅ Rápida (41 iter)
Computo por iteración ❌ Alto (popSize × n_ciudades) ✅ Bajo (n_hormigas × n_ciudades)
Facilidad de ajuste ⚠️ Se deben balancear 3 hiperparámetros | ✅ Ajuste intuitivo de evap_rate y #hormigas | | | | | | | | | | | | | | | | |
Robustez a datos ruidosos ✅ Buena (mutación reinyecta diversidad) ⚠️ Puede atascarse sin variación | | | | | | | | |
Interpretabilidad de progreso ✅ Fácil de graficar fitness ✅ Fácil de graficar feromonas
Escalabilidad (50+ nodos) ✅ Admite poblaciones grandes, pero tiempo ↑ ⚠️ Requiere más hormigas; memoria ↑ | | | | | | | | |
Tabla 8: Ventajas y desventajas operativas - Algoritmo Genético (GA) vs Colonia de Hormigas (ACO)

4. Recomendaciones prácticas

  1. Uso rápido/prototipo → ACO
    • Menos ajustes, converge rápido, útil para estimar costo mínimo preliminar.
  2. Exploración exhaustiva → GA
    • Permite probar distintas poblaciones y mutaciones; útil cuando existen restricciones adicionales (ventanas de tiempo, sub-rutas obligatorias).
  3. Híbrido
    • Iniciar con ACO para acercarse al óptimo y luego refinar con GA (o viceversa) puede combinar rapidez y exploración profunda.
  4. Optimización de parámetros
    • Para GA: probar pmutation 0.2–0.4 y popSize 100–150.
    • Para ACO: mantener evap_rate entre 0.4–0.6 y 1–2 hormigas por ciudad.

5. Conclusión

Ambas heurísticas alcanzaron la misma solución óptima en términos de costo total, lo que valida la robustez del resultado.
- ACO destaca por su eficiencia computacional y rapidez.
- GA aporta mayor flexibilidad y capacidad de exploración, al costo de mayor tiempo y ajustes.

Elegir uno u otro depende del balance entre tiempo de cómputo y profundidad de búsqueda requerido en la aplicación logística real.

4. Reporte de Contribución Individual