Optimización Heurística — Trabajo 01
Autores: Manuel Alejandro Sánchez Daza · Mario Alberto Cañas Baquero
Curso: Redes Neuronales y Algoritmos Bio-inspirados
Repositorio: github.com/LeMannuelo/RNAB-Trabajo-01
Este trabajo tiene dos partes. En la primera comparamos métodos de optimización numérica sobre funciones matemáticas clásicas. En la segunda resolvemos el Problema del Vendedor Viajero sobre las 32 capitales de México. En ambos casos usamos métodos heurísticos y los contrastamos con enfoques más tradicionales.
Parte 1 — Optimización Numérica
1.1 Introducción
La optimización numérica aparece en casi todo lo que hacemos en machine learning e ingeniería: entrenar una red neuronal, ajustar parámetros de un modelo, minimizar el error de un sistema. El problema siempre es el mismo en esencia: encontrar el punto donde una función alcanza su valor mínimo.
En esta parte comparamos dos enfoques muy distintos. Por un lado el descenso por gradiente, que usa la información matemática de la función para moverse siempre en la dirección que más reduce el valor. Por otro lado los métodos heurísticos — PSO, Evolución Diferencial y Algoritmos Evolutivos — que no necesitan conocer el gradiente y en cambio exploran el espacio de búsqueda con una población de soluciones que evoluciona iterativamente.
Las dos funciones de prueba que escogimos son:
Función de Rosenbrock — famosa por su "valle de banana": el mínimo global es fácil de encontrar en papel, pero en la práctica los algoritmos tienen que atravesar un valle largo, estrecho y curvado para llegar ahí.
f(x) = Σ [ 100·(xᵢ - xᵢ₋₁²)² + (1 - xᵢ₋₁)² ]
Mínimo global en x* = (1, 1, ..., 1), f(x*) = 0.
Función de Griewank — multimodal, con muchos mínimos locales distribuidos por toda la superficie. Cualquier algoritmo sin mecanismos de exploración queda atrapado antes de llegar al mínimo global.
f(x) = (1/4000)·Σᵢxᵢ² - Πᵢ cos(xᵢ/√i) + 1
Mínimo global en x* = (0, 0, ..., 0), f(x*) = 0
Ambas se optimizaron en 2D y 3D.
1.2 Metodología
Descenso por gradiente
Parte de una posición inicial aleatoria en $[-5, 5]^d$ y en cada iteración da un paso en dirección opuesta al gradiente:
x_(k+1) = x_k - α · ∇f(x_k)
donde α es la tasa de aprendizaje (learning rate)
Implementamos los gradientes analíticos de ambas funciones. Los parámetros usados:
| Función | Dimensión | Learning rate | Máx. iteraciones |
|---|---|---|---|
| Rosenbrock | 2D | 0.001 | 50 000 |
| Rosenbrock | 3D | 0.001 | 30 000 |
| Griewank | 2D | 0.01 | 1 400 |
| Griewank | 3D | 0.01 | 1 400 |
El learning rate de Rosenbrock es más bajo porque su valle estrecho hace que pasos grandes generen oscilaciones. Para Griewank se puede usar un paso mayor porque la superficie es más suave localmente.
PSO — Optimización por Enjambre de Partículas
Inspirado en el comportamiento de bandadas de aves. Cada partícula tiene posición y velocidad; la velocidad combina inercia, atracción hacia el mejor punto personal y atracción hacia el mejor punto global de la población (Eberhart & Kennedy, 1995).
v_(k+1) = w·v_k + c1·r1·(p_i - x_k) + c2·r2·(g - x_k)
donde:
w = inercia
c1 = coeficiente cognitivo (atracción al mejor personal)
c2 = coeficiente social (atracción al mejor global)
r1, r2 = números aleatorios en [0, 1]
| Parámetro | Rosenbrock | Griewank |
|---|---|---|
| Partículas | 40–50 | 40–50 |
| Iteraciones | 300–500 | 200 |
| Inercia $w$ | 0.7 | 0.5 |
| $c_1$, $c_2$ | 1.5, 1.5 | 1.5, 1.5 |
DE — Evolución Diferencial
Cada candidato genera un vector mutante combinando tres individuos aleatorios distintos, y decide si adopta ese vector según quién tenga menor costo (Storn & Price, 1997).
v = x_r1 + F · (x_r2 - x_r3)
donde F es el factor de escala y r1, r2, r3 son índices distintos aleatorios
| Parámetro | Valor |
|---|---|
| Población | 40 |
| Iteraciones | 200–300 |
| Factor de escala $F$ | 0.8 |
| Tasa de cruce $cr$ | 0.9 |
EA — Algoritmo Evolutivo
Selección por torneo, cruce intermedio y mutación gaussiana. Los mejores individuos producen descendencia con pequeñas perturbaciones.
| Parámetro | Valor |
|---|---|
| Población | 60 |
| Iteraciones | 200–350 |
| $\sigma$ mutación | 0.001–0.05 según función |
| Tamaño torneo | 3 |
Para la comparación estadística se realizaron 10 corridas independientes por algoritmo con semillas distintas.
1.3 Resultados
Descenso por gradiente
| Función | Dim. | $f(\mathbf{x})$ final | Evaluaciones |
|---|---|---|---|
| Rosenbrock | 2D | $1.38 \times 10^{-18}$ | 50 002 |
| Rosenbrock | 3D | $4.99 \times 10^{-14}$ | 30 002 |
| Griewank | 2D | $7.40 \times 10^{-3}$ | 1 402 |
| Griewank | 3D | $1.15 \times 10^{-2}$ | 1 402 |
En Rosenbrock el gradiente funcionó espectacularmente: precisión de $10^{-18}$ en 2D. En Griewank converge rápido pero a un mínimo local — el valor final es mayor que cero.
Las animaciones lo muestran claramente:
Figura 1. Descenso por gradiente sobre Rosenbrock 2D. El punto recorre lentamente el valle hasta llegar al mínimo global en (1, 1).
Figura 2. Trayectoria del gradiente sobre Rosenbrock 3D.
Figura 3. Descenso por gradiente sobre Griewank 2D. El algoritmo cae al primer mínimo local que encuentra.
Figura 4. Trayectoria del gradiente sobre Griewank 3D.
Métodos heurísticos
| Función | Gradiente | PSO | DE | EA |
|---|---|---|---|---|
| Rosenbrock 2D | $1.4 \times 10^{-18}$ ✅ | ~$10^{-4}$ | ~$10^{-6}$ | ~$10^{-3}$ |
| Rosenbrock 3D | $5.0 \times 10^{-14}$ ✅ | ~$10^{-2}$ | ~$10^{-4}$ | ~$10^{-2}$ |
| Griewank 2D | $7.4 \times 10^{-3}$ ❌ | ~$0$ ✅ | ~$0$ ✅ | ~$10^{-3}$ |
| Griewank 3D | $1.2 \times 10^{-2}$ ❌ | ~$0$ ✅ | ~$0$ ✅ | ~$10^{-3}$ |
Figura 5. PSO sobre Rosenbrock 2D. Las partículas convergen al valle desde distintas posiciones iniciales.
Figura 6. Evolución Diferencial sobre Rosenbrock 2D.
Figura 7. Algoritmo Evolutivo sobre Rosenbrock 2D.
Figura 8. PSO sobre Griewank 2D. La población logra escapar de los mínimos locales y converge al origen.
Figura 9. Evolución Diferencial sobre Griewank 2D.
Figura 10. Algoritmo Evolutivo sobre Griewank 2D.
1.4 Discusión
El resultado más interesante no es que un método sea "mejor" sino que cada uno tiene fortalezas claras dependiendo del tipo de función.
El gradiente en Rosenbrock logró una precisión de $10^{-18}$, algo que ningún heurístico alcanzó. Cuando la función tiene un solo mínimo y se puede calcular el gradiente exacto, no hay forma más eficiente de llegar al óptimo que seguir directamente esa información matemática. En Griewank ese mismo gradiente se convirtió en su peor enemigo: la primera pendiente descendente lo llevó a un mínimo local y no salió.
Los heurísticos mostraron exactamente lo contrario: en Griewank, PSO y DE encontraron el mínimo global de manera consistente en casi todas las corridas. La razón es que al trabajar con una población distribuida en todo el espacio tienen una visión más amplia del paisaje y pueden escapar de mínimos locales. En Rosenbrock sin embargo ninguno alcanzó la precisión del gradiente, porque el valle estrecho dificulta la exploración poblacional — los saltos no aprovechan la curvatura del valle.
En evaluaciones, el gradiente fue el más costoso en Rosenbrock (hasta 50 000) pero el más barato en Griewank (1 400). Los heurísticos se mantuvieron estables entre 8 000 y 12 000 evaluaciones sin importar la función, lo que los hace más predecibles en costo computacional.
Conclusión práctica: si la función es unimodal y diferenciable, el gradiente es imbatible en precisión. Si es multimodal o no se puede calcular el gradiente, los heurísticos son la opción correcta.
Parte 2 — TSP: 32 Capitales de México
2.1 Introducción
El Problema del Vendedor Viajero (Traveling Salesman Problem, TSP) es uno de los problemas de optimización combinatoria más estudiados en la literatura. Su formulación es simple: dado un conjunto de $n$ ciudades y los costos de desplazamiento entre cada par, se busca la ruta que permita visitar todas exactamente una vez y regresar al punto de partida minimizando el costo total (Applegate et al., 2006).
Este trabajo aplica dos metaheurísticas al TSP sobre las 32 capitales de los estados de México, modelando el costo de desplazamiento con datos reales de carretera obtenidos mediante OSRM. El objetivo es encontrar la ruta de menor costo económico considerando combustible, peajes y el costo del tiempo del vendedor.
2.2 Formulación del problema
Sea $G = (V, E)$ un grafo completo donde $V = {v_0, \ldots, v_{31}}$ representa las 32 capitales. Se busca la permutación $\pi$ que minimice:
min Σₖ c(π(k), π(k+1 mod n))
sujeto a que cada ciudad se visite exactamente una vez
El costo entre cada par de ciudades integra tres componentes:
c_ij = C_combustible(d_ij) + C_peaje(d_ij) + C_vendedor(t_ij)
- Combustible: vehículo Renault Twingo Access 2012, rendimiento 55 km/galón, precio gasolina Magna $92.5 MXN/galón → ~$1.68 MXN/km
- Peajes: modelo proporcional de $1.5 MXN/km basado en tarifa media de autopistas de cuota (~$1.0–$2.0 MXN/km según SCT, 2023)
- Tiempo del vendedor: $150 MXN/hora
2.3 Obtención de datos
Las distancias y tiempos reales entre las 32 capitales se obtuvieron mediante OSRM (Open Source Routing Machine), que calcula rutas siguiendo la red vial real de OpenStreetMap incluyendo autopistas y restricciones de tráfico (Luxen & Vetter, 2011). Se realizaron 496 consultas para los $\binom{32}{2}$ pares únicos de ciudades.
| Métrica | Distancia (km) | Tiempo (h) | Costo (MXN) |
|---|---|---|---|
| Mínimo | 38.1 | 0.60 | $204 |
| Máximo | 5 212.6 | 65.92 | $25 483 |
| Media | 1 216.2 | 15.11 | $5 906 |
El par de menor distancia es Tlaxcala–Puebla (38.1 km) y el de mayor distancia es Mexicali–Chetumal (5 212.6 km), los dos extremos geográficos del país — lo que valida la coherencia de los datos.
Las 32 entidades y sus capitales:
| # | Estado | Capital | # | Estado | Capital |
|---|---|---|---|---|---|
| 0 | Aguascalientes | Aguascalientes | 16 | Morelos | Cuernavaca |
| 1 | Baja California | Mexicali | 17 | Nayarit | Tepic |
| 2 | Baja California Sur | La Paz | 18 | Nuevo León | Monterrey |
| 3 | Campeche | Campeche | 19 | Oaxaca | Oaxaca de Juárez |
| 4 | Chiapas | Tuxtla Gutiérrez | 20 | Puebla | Puebla |
| 5 | Chihuahua | Chihuahua | 21 | Querétaro | Santiago de Querétaro |
| 6 | CDMX | Ciudad de México | 22 | Quintana Roo | Chetumal |
| 7 | Coahuila | Saltillo | 23 | San Luis Potosí | San Luis Potosí |
| 8 | Colima | Colima | 24 | Sinaloa | Culiacán |
| 9 | Durango | Durango | 25 | Sonora | Hermosillo |
| 10 | Guanajuato | Guanajuato | 26 | Tabasco | Villahermosa |
| 11 | Guerrero | Chilpancingo | 27 | Tamaulipas | Ciudad Victoria |
| 12 | Hidalgo | Pachuca | 28 | Tlaxcala | Tlaxcala |
| 13 | Jalisco | Guadalajara | 29 | Veracruz | Xalapa |
| 14 | Estado de México | Toluca | 30 | Yucatán | Mérida |
| 15 | Michoacán | Morelia | 31 | Zacatecas | Zacatecas |
2.4 Metodología
Colonia de Hormigas (ACO)
Propuesto por Dorigo et al. (1996), se inspira en el comportamiento de las hormigas reales al buscar rutas entre el nido y fuentes de alimento. Las hormigas depositan feromonas en los caminos recorridos; los más cortos acumulan más feromona y atraen a más hormigas, reforzando esa ruta (Dorigo & Stützle, 2004).
La probabilidad de que una hormiga en la ciudad $i$ elija la ciudad $j$ es:
p_ij = (τᵢⱼᵅ · ηᵢⱼᵝ) / Σₖ (τᵢₖᵅ · ηᵢₖᵝ)
donde:
τᵢⱼ = feromona en el arco (i, j)
ηᵢⱼ = 1/c_ij (visibilidad — preferencia por rutas baratas)
α = peso de la feromona
β = peso de la heurística
donde $\eta_{ij} = 1/c_{ij}$ es la visibilidad (preferencia por rutas baratas) y tras cada iteración la feromona se actualiza:
τᵢⱼ ← ρ · τᵢⱼ + Δτᵢⱼ
donde ρ = tasa de evaporación (0.95) y Δτᵢⱼ = 1/costo_ruta
| Parámetro | Valor | Justificación |
|---|---|---|
n_ants |
150 | Cobertura amplia del espacio |
n_best |
150 | Todas las hormigas depositan feromona |
n_iterations |
500 | Convergencia estable antes de iter. 400 |
decay ($\rho$) |
0.95 | Evaporación lenta, favorece explotación |
alpha |
1 | Peso igual feromona–heurística |
beta |
2 | Leve énfasis en costo |
Algoritmo Genético (GA)
Metaheurística evolutiva inspirada en los principios de selección natural (Holland, 1975). Cada cromosoma es una permutación de las 32 ciudades. Los operadores:
- Cruce Order Crossover (OX): preserva el orden relativo de los genes del segundo padre, evitando ciudades duplicadas (Davis, 1985).
- Mutación Swap: intercambia dos ciudades aleatorias con probabilidad $p_m$.
- Selección: elitismo (20 mejores pasan directo) + torneo binario.
| Parámetro | Valor | Justificación |
|---|---|---|
n_population |
200 | Balance diversidad–costo computacional |
n_generations |
500 | Convergencia verificada antes de gen. 400 |
mutation_rate |
0.02 | Mutación baja para preservar buenas soluciones |
elite_size |
20 | 10% de la población pasa sin modificación |
2.5 Resultados
Comparación ACO vs. GA
| Algoritmo | Costo óptimo (MXN) | Tiempo de cómputo |
|---|---|---|
| ACO | $69 747.57 | 100.6 s |
| GA | $76 651.69 | 6.4 s |
El ACO encontró una solución 9% mejor que el GA ($6 904 MXN de diferencia), a costa de un tiempo de cómputo ~15 veces mayor.
Desglose del costo — Ruta óptima ACO
| Concepto | Valor | % del total |
|---|---|---|
| Distancia total | 13 987.1 km | — |
| Tiempo de viaje | 186.0 h (7.7 días) | — |
| Combustible | $20 867.88 MXN | 29.9% |
| Peajes (est.) | $20 980.68 MXN | 30.1% |
| Costo vendedor | $27 899.00 MXN | 40.0% |
| Total | $69 747.57 MXN | 100% |
Ruta óptima (ACO)
Aguascalientes → Zacatecas → San Luis Potosí → Guanajuato → Santiago de Querétaro → Pachuca → Tlaxcala → Puebla → Xalapa → Oaxaca de Juárez → Tuxtla Gutiérrez → Villahermosa → Campeche → Mérida → Chetumal → Chilpancingo → Cuernavaca → Ciudad de México → Toluca → Morelia → Guadalajara → Colima → Tepic → Durango → Culiacán → Hermosillo → Mexicali → La Paz → Chihuahua → Saltillo → Monterrey → Ciudad Victoria → Aguascalientes
La ruta recorre el Bajío y el centro, desciende hacia el sureste por el Golfo, cruza la Península de Yucatán, asciende por el Pacífico y cierra por el norte — geográficamente consistente con un recorrido de mínima distancia.
Figura 11. Comparación visual de las rutas óptimas encontradas por ACO (azul) y GA (rojo) sobre el mapa de México.
Animación del recorrido
Figura 12. Construcción progresiva de la ruta óptima (ACO) sobre las 32 capitales de México.
Convergencia
Ambos algoritmos convergieron antes de completar las 500 iteraciones. El ACO mostró una caída pronunciada del costo en las primeras 150 iteraciones seguida de refinamientos graduales. El GA convergió más rápido en tiempo real pero se estabilizó en un costo subóptimo.
Análisis de sensibilidad — tarifa del vendedor
El costo del vendedor representa el 40% del total, más que combustible y peajes. Para entender su impacto se recalculó el costo de ambas rutas con distintas tarifas horarias:
| Tarifa (MXN/h) | Costo ACO (MXN) | Costo GA (MXN) |
|---|---|---|
| 50 | ~$55 000 | ~$60 000 |
| 100 | ~$62 000 | ~$68 000 |
| 150 | ~$69 748 | ~$76 652 |
| 200 | ~$77 000 | ~$85 000 |
| 300 | ~$91 000 | ~$101 000 |
| 500 | ~$119 000 | ~$132 000 |
A medida que sube la tarifa, el costo del tiempo domina sobre el combustible y los peajes, lo que en escenarios extremos podría cambiar la ruta óptima hacia trayectos más rápidos aunque sean más largos en distancia.
2.6 Conclusiones
En calidad de solución el ACO fue claramente superior: encontró una ruta 9% más barata que el GA. Esto es consistente con la literatura para problemas de permutación — el mecanismo de memoria colectiva mediante feromona permite explotar eficientemente rutas prometedoras a lo largo de las iteraciones (Dorigo & Stützle, 2004). El GA sin embargo convergió en menos de 7 segundos frente a los 100 del ACO, lo que lo hace preferible cuando el tiempo de cómputo es una restricción o se necesitan múltiples ejecuciones.
El hallazgo más relevante del modelo de costos es que el tiempo del vendedor representa el 40% del costo total, superando tanto al combustible como a los peajes. Esto implica que la tarifa horaria es el parámetro más sensible del modelo: un incremento en el salario puede alterar la ruta óptima de forma no trivial, favoreciendo trayectos más rápidos sobre los más cortos en distancia.
El uso de distancias reales por carretera (OSRM) fue una mejora metodológica importante respecto a distancias euclidianas, ya que México presenta rodeos significativos especialmente hacia Baja California y la Península de Yucatán.
Uso de inteligencia artificial
Durante el desarrollo de este trabajo se utilizó Claude (Anthropic) como herramienta de apoyo. Los principales usos fueron:
- Revisión y depuración del código de los algoritmos heurísticos (PSO, DE, EA, ACO, GA).
- Consultas sobre la configuración y justificación de parámetros.
- Ajustes de presentación y visualización en los notebooks.
- Apoyo en la redacción y estructura de este reporte.
El impacto fue positivo en velocidad de desarrollo: debugging que podría tomar horas se resolvió en minutos con consultas puntuales. Todos los resultados numéricos, las decisiones de diseño del experimento y las conclusiones fueron verificados y validados manualmente. La IA funcionó como asistente de código y escritura, no como autor del trabajo.
Referencias
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
Davis, L. (1985). Applying adaptive algorithms to epistatic domains. Proceedings of the International Joint Conference on Artificial Intelligence, 162–164.
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, 26(1), 29–41. https://doi.org/10.1109/3477.484436
Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press. https://doi.org/10.7551/mitpress/1290.001.0001
Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 39–43. https://doi.org/10.1109/MHS.1995.494215
Griewank, A. O. (1981). Generalized descent for global optimization. Journal of Optimization Theory and Applications, 34(1), 11–39. https://doi.org/10.1007/BF00933356
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
Luxen, D., & Vetter, C. (2011). Real-time routing with OpenStreetMap data. Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 513–516. https://doi.org/10.1145/2093973.2094062
OpenStreetMap contributors. (2024). OpenStreetMap. https://www.openstreetmap.org
OSRM Project. (2024). Open Source Routing Machine. http://project-osrm.org
Rosenbrock, H. H. (1960). An automatic method for finding the greatest or least value of a function. The Computer Journal, 3(3), 175–184. https://doi.org/10.1093/comjnl/3.3.175
Secretaría de Comunicaciones y Transportes (SCT). (2023). Tarifas de autopistas de cuota en México. Gobierno de México.
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
Top comments (0)