Skip to content

Clase 5 — Algoritmos de Colonia de Hormigas (ACO) aplicados al TSP

Resumen Ejecutivo

Primer algoritmo bioinspirado poblacional de la asignatura. La clase arranca con el salto conceptual "algoritmos exactos → heurísticas → metaheurísticas poblacionales" y se centra en Ant Colony Optimization (ACO) de Dorigo (1992). Se estudia el mecanismo natural (feromonas, exploradoras vs recolectoras, autorregulación), la traducción matemática a tres ecuaciones clave (probabilidad de movimiento, depósito de feromona, evaporación) y una traza manual sobre el problema del viajante (TSP) en un grafo de 7 nodos, implementada después en MATLAB. Se cierra con un vistazo a variantes (elitista, colonias, max-min) y un anticipo de la próxima clase: Particle Swarm Optimization (PSO). ⚠️ EXAMEN: el objetivo es interiorizar qué significa cada término de la fórmula de probabilidad y entender que el algoritmo es probabilístico, no determinista.

Conceptos Clave

  • Metaheurística: técnica de optimización que no garantiza el óptimo pero encuentra una buena solución en tiempo razonable. Se usa cuando el problema es NP y los algoritmos exactos son impracticables (combinatoria que crece exponencialmente). ⚠️ EXAMEN
  • Heurística vs metaheurística poblacional: una heurística clásica (búsqueda local) trabaja con una sola solución. Una metaheurística poblacional trabaja con un conjunto de agentes (hormigas, abejas, partículas) que exploran el espacio en paralelo.
  • Algoritmo bioinspirado: metaheurística cuya inspiración viene del comportamiento observado en la naturaleza (insectos sociales, bandadas, evolución genética).
  • Feromona: sustancia química que las hormigas reales depositan en el camino. En el algoritmo representa una memoria compartida sobre la calidad de un camino: cuantas más hormigas pasen por él, más feromona tendrá.
  • Visibilidad (η): inverso de la distancia, η_ij = 1/d_ij. Codifica la preferencia por caminos cortos. ⚠️ EXAMEN
  • Intensidad de feromona (τ): memoria acumulada de cuánto se ha usado el arco (i, j). Inicializada a un valor pequeño (p. ej. 0.01) y actualizada en cada iteración.
  • Tasa de evaporación (ρ): fracción de feromona que se pierde en cada iteración. ρ ∈ [0,1]; ρ=0 imposible en la práctica (feromona que no se disipa nunca), ρ=1 tampoco (feromona que se evapora por completo, se pierde la memoria).
  • Parámetros de control (α, β): exponentes que ponderan el peso de la feromona y de la visibilidad respectivamente. Ajustables por el usuario.
  • TSP (Travelling Salesman Problem): visitar N ciudades una sola vez cada una y volver al origen minimizando coste. NP-hard. Formulación natural en grafos; se resuelve bien con ACO.
  • Circuito hamiltoniano: recorrido que pasa por cada vértice exactamente una vez y regresa al origen.
  • Circuito euleriano: recorrido que pasa por cada arista exactamente una vez.

Desarrollo del Temario

1. El salto conceptual: de algoritmos exactos a heurísticas

Paradigma Ejemplos Garantía Coste Aplicabilidad
Exactos Derivación, programación lineal, ramificación y acotación Óptimo global Alto, crece rápido Problemas pequeños o convexos
Heurística local Búsqueda local, hill climbing Óptimo local Bajo Cuando exactos no escalan
Metaheurísticas poblacionales ACO, PSO, genéticos Buena solución Ajustable Problemas NP combinatorios grandes

El salto de exactos a metaheurísticas introduce un ingrediente nuevo: aleatoriedad controlada. Lo que parecía un vicio (no ser determinista) es precisamente la virtud que permite explorar soluciones que un algoritmo determinista no vería.

Frase clave del profesor: "esto es lo que hace que se parezcan a la realidad: el toque de aleatoriedad".

2. Inspiración natural de ACO

Observación de las hormigas reales:

  1. Salen del nido exploradoras caminando aleatoriamente.
  2. Cuando una encuentra comida, la lleva al nido dejando feromona en el camino.
  3. Otras hormigas detectan el olor de la feromona y tienden a seguirlo.
  4. Cuanto más cortito es el camino bueno, más hormigas lo recorren en menos tiempo, más feromona se acumula, más atractivo se vuelve.
  5. Las feromonas de los caminos malos se evaporan. El sistema se autorregula hacia caminos cortos.

Principios de la conducta de enjambre: ⚠️ EXAMEN

  • Autorregulación: encuentran el objetivo sin control externo.
  • Evolución sin ayuda externa: no hay un "supervisor" que diga qué hacer.
  • División de tareas: exploradoras, recolectoras, etc.
  • Control descentralizado: ningún agente ve el todo. Toman decisiones locales.

3. Traducción a matemáticas: las tres ecuaciones de ACO

Ecuación 1 — Probabilidad de movimiento (la más importante): ⚠️ EXAMEN

\[ p_{ij}^k(t) = \begin{cases} \dfrac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\displaystyle\sum_{l \in N_i^k} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta} & \text{si } j \in N_i^k \\[1em] 0 & \text{en otro caso} \end{cases} \]

Desglose:

  • \(p_{ij}^k(t)\) = probabilidad de que la hormiga \(k\), estando en el nodo \(i\), vaya al nodo \(j\) en la iteración \(t\).
  • \(\tau_{ij}(t)\) = intensidad de feromona sobre el arco \((i, j)\).
  • \(\eta_{ij} = 1/d_{ij}\) = visibilidad (inverso de la distancia).
  • \(\alpha\) = peso de la feromona (memoria social).
  • \(\beta\) = peso de la visibilidad (preferencia por caminos cortos).
  • \(N_i^k\) = nodos que la hormiga \(k\) aún no ha visitado desde \(i\).
  • Valor 0 si el nodo ya fue visitado — evita repetir y respeta la restricción del TSP.

Interpretación: la fracción es probabilidad total (numerador de arco j entre la suma de todos los arcos candidatos). Sumar todos los \(p_{ij}^k\) posibles da 1.

Ecuación 2 — Depósito de feromona por una hormiga:

\[ \Delta \tau_{ij}^k = \begin{cases} \dfrac{Q}{L_k} & \text{si la hormiga } k \text{ ha pasado por } (i,j) \\ 0 & \text{en otro caso} \end{cases} \]
  • \(Q\) = constante de escala.
  • \(L_k\) = longitud total del recorrido de la hormiga \(k\).
  • Cuanto más corto es el recorrido, más feromona deposita.

Ecuación 3 — Actualización (evaporación + depósito):

\[ \tau_{ij}(t+1) = (1-\rho) \cdot \tau_{ij}(t) + \sum_k \Delta \tau_{ij}^k \]
  • El término \((1-\rho) \cdot \tau_{ij}(t)\) evapora una fracción \(\rho\) de la feromona previa.
  • El sumatorio añade lo depositado por todas las hormigas que pasaron por el arco en esta iteración.
  • Casos extremos (solo para intuición, no ocurren en la práctica): ⚠️ EXAMEN
  • \(\rho = 0\): la feromona no se evapora nunca, se acumula indefinidamente.
  • \(\rho = 1\): la feromona se evapora por completo cada iteración ("hay viento", se pierde la memoria del camino).
  • En la práctica siempre \(\rho \in (0, 1)\).

4. Algoritmo completo

1. Inicializar τ_ij a un valor pequeño constante (p. ej. 0.01) para todos los arcos.
2. Mientras no se cumpla el criterio de parada:
   a. Colocar m hormigas en nodos de inicio (aleatorios o fijos).
   b. Para cada hormiga k:
      - Construir recorrido nodo a nodo usando la ecuación 1.
      - No visitar nodos repetidos.
      - Al llegar a destino: calcular L_k (longitud total).
   c. Actualizar las feromonas con la ecuación 3.
3. Devolver el mejor recorrido encontrado.

Criterio de parada: iteraciones máximas, convergencia (varios ciclos sin mejora), coste computacional.

5. Contexto en grafos

ACO trabaja con grafos (nodos + aristas con peso = distancia). Dos representaciones matriciales son estándar: ⚠️ EXAMEN

  • Matriz de adyacencia (\(n \times n\), de nodos a nodos): entrada (i,j) es 1 si existe arista entre \(i\) y \(j\), 0 en caso contrario. Para grafos ponderados, la entrada puede ser el peso.
  • Matriz de incidencia (\(n \times m\), de vértices a aristas): entrada (v, a) es 1 si la arista \(a\) incide en el vértice \(v\).

Tipos de grafos relevantes: - No dirigidos — aristas sin sentido; usados en teoría de juegos. - Dirigidos — aristas con sentido; usados en transportes y TSP.

Tipos de circuitos: - Euleriano: pasa por cada arista una sola vez; puede repetir vértices. - Hamiltoniano: pasa por cada vértice una sola vez, sin repetir. Regresa al origen. Es el que define el TSP.

6. Ejemplo paso a paso: TSP simplificado con ACO

Grafo: 7 nodos, aristas con peso. Salida en nodo 1, destino nodo 4.

Parámetros elegidos: - Feromona inicial: \(\tau = 0.1\) en todos los arcos. - \(\rho = 0.5\) - \(\alpha = 1\), \(\beta = 2\)

Hormiga 1 en el nodo 1. Arcos candidatos: \(1 \to 2\) (distancia 5), \(1 \to 3\) (distancia 1.3), \(1 \to 6\) (distancia 5.2).

Cálculo del numerador para cada candidato:

Arco \(\tau^\alpha\) \(\eta = 1/d\) \(\eta^\beta = 1/d^2\) Numerador
\(1 \to 2\) \(0.1^1 = 0.1\) \(1/5\) \(1/25 = 0.04\) \(0.1 \cdot 0.04 = 0.004\)
\(1 \to 3\) \(0.1\) \(1/1.3\) \(1/1.69 \approx 0.59\) \(0.1 \cdot 0.59 \approx 0.059\)
\(1 \to 6\) \(0.1\) \(1/5.2\) \(1/27 \approx 0.037\) \(0.1 \cdot 0.037 \approx 0.0037\)

Suma total (denominador) ≈ 0.067.

Arco Probabilidad
\(1 \to 2\) 0.004 / 0.067 ≈ 6%
\(1 \to 3\) 0.059 / 0.067 ≈ 88% (el más cercano)
\(1 \to 6\) 0.0037 / 0.067 ≈ 5.5%

El nodo 3 tiene la mayor probabilidad, no la certeza. Al tirar los "dados", lo habitual es que se elija 3, pero no siempre. En el ejemplo del profesor salió 3.

Siguiente paso: hormiga en nodo 3. Candidatos: nodos 5 y 7 (el 2 ya se descartó por la regla de no repetir, aunque podría haberse incluido en variantes más laxas). Se repite el cálculo.

Al final la hormiga 1 construye el recorrido 1 → 3 → 7 → 4 con coste 19.

Hormiga 2 (mismo arranque, otros dados): podría seguir 1 → 3 → 5 → 4 con coste más alto. Se actualiza feromonas solo cuando todas las hormigas han terminado.

7. Traza en MATLAB (versión básica)

Estructura del código (mostrado en clase):

% Definir grafo
G = graph(s, t, pesos, nombres_nodos);
plot(G)

% Parámetros
n_aristas = numedges(G);
tau = 0.01 * ones(n_aristas, 1);  % feromona inicial
rho = 0.5;                         % evaporación
num_iter = 100;
num_hormigas = 10;

% Almacenes de solución
mejor_camino = [];
mejor_coste = Inf;

for t = 1:num_iter
    for k = 1:num_hormigas
        [camino_k, coste_k] = recorrido_hormiga(G, tau, alpha, beta);
        if coste_k < mejor_coste
            mejor_coste = coste_k;
            mejor_camino = camino_k;
        end
    end
    tau = actualizar_feromonas(tau, rho, caminos_iter, costes_iter);
end

Nota operativa del profesor: nombrar archivos sin espacios ni guiones bajos problemáticos, ya que en algunos entornos de MATLAB los identificadores con ciertos caracteres especiales dan problemas al ejecutar.

8. Variantes de ACO (panorama, no detalle)

El algoritmo básico (Dorigo 1992) ha generado una familia:

  • Elitist Ant System: las mejores hormigas de cada iteración depositan feromona extra, acelerando la convergencia.
  • Colonias de hormigas (ACS): múltiples puntos de inicio para cubrir más espacio de búsqueda; coste computacional mayor.
  • MAX-MIN Ant System: incorpora mutaciones (estilo algoritmos genéticos) y acota la feromona entre valores mínimo y máximo para evitar estancamiento.

Advertencia del profesor: revistas especializadas siguen publicando variantes nuevas constantemente (hormigas, águilas, lobos, murciélagos...). La esencia es la misma: observar un comportamiento natural y modelarlo en una fórmula probabilística.

9. Próxima clase: Particle Swarm Optimization (PSO)

Pregunta gancho: ¿qué diferencia hay entre hormigas y aves/patos? ⚠️ EXAMEN

  • Hormigas: se mueven en 2 dimensiones (el suelo). Adecuado para TSP y problemas discretos en grafos.
  • Aves/patos (PSO): se mueven en \(\mathbb{R}^n\). Permiten resolver problemas de optimización continua (funciones multidimensionales). Vuelan, no caminan; la metáfora cambia.

Preguntas de Autoevaluación

  1. ¿Qué diferencia una heurística de una metaheurística poblacional? La heurística trabaja con una única solución candidata; la metaheurística poblacional trabaja con un conjunto de agentes que exploran el espacio en paralelo.
  2. ¿Por qué las metaheurísticas son probabilísticas y no deterministas? Porque la aleatoriedad permite escapar de óptimos locales y explorar soluciones que un algoritmo determinista no consideraría.
  3. ¿Qué representa \(\tau_{ij}\) en ACO? La intensidad de feromona acumulada en el arco entre los nodos \(i\) y \(j\), que actúa como memoria compartida entre las hormigas.
  4. ¿Por qué \(\eta_{ij} = 1/d_{ij}\)? Para que caminos cortos tengan mayor visibilidad y por tanto más probabilidad de ser elegidos.
  5. Explica el rol de \(\alpha\) y \(\beta\). \(\alpha\) pondera el peso de la feromona (memoria social), \(\beta\) pondera el peso de la distancia (preferencia por lo cercano). Ajustándolos cambia el balance explotación/exploración.
  6. ¿Qué significa \(\rho\) y qué efecto tienen sus extremos? Tasa de evaporación de feromona. \(\rho=0\) acumularía feromona indefinidamente; \(\rho=1\) la evaporaría totalmente cada iteración. Ambos extremos rompen el algoritmo.
  7. ¿Por qué ACO cumple el principio de control descentralizado? Porque ninguna hormiga conoce el grafo completo ni toma decisiones con visión global; solo decide el siguiente movimiento según la información local (feromona + visibilidad).
  8. ¿Por qué se aplica ACO al TSP y no se resuelve con algoritmos exactos? Porque el TSP es NP-hard: la combinatoria crece factorialmente con el número de ciudades y los algoritmos exactos solo funcionan en grafos pequeños.
  9. Diferencia entre circuito euleriano y hamiltoniano. Euleriano: cada arista una sola vez. Hamiltoniano: cada vértice una sola vez. El TSP usa hamiltoniano.
  10. Diferencia entre matriz de adyacencia y matriz de incidencia. Adyacencia: nodos × nodos, indica si dos nodos están conectados. Incidencia: vértices × aristas, indica si un vértice toca una arista.
  11. ¿Cuándo se acaba el algoritmo? Cuando se cumple el criterio de parada: número máximo de iteraciones, convergencia (sin mejora durante varios ciclos) o presupuesto de tiempo.
  12. ¿Qué cambio cualitativo introduce PSO respecto a ACO? Permite optimización continua en \(\mathbb{R}^n\) (no solo grafos discretos), inspirándose en el vuelo de bandadas.

Referencias

  • Dorigo, M. (1992) — formulación original de Ant System.
  • Implementación en MATLAB (archivo a compartir por la profesora).
  • Próxima clase: PSO (Particle Swarm Optimization).