Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto

Estigmergia, el experimento del doble puente, el sistema de hormigas de Dorigo, el papel de los parámetros α, β y ρ y las variantes mejoradas, sobre un circuito por las capitales regionales checas y sobre 60 ciudades, en comparación con el recocido.

13 minutos Matěj Žalmánek 2026-10-15

Serie Fundamentos de IA Parte 29 de 52

1. Mapa de la inteligencia artificial: qué es cada cosa y cómo encaja todo
2. Breve historia de la inteligencia artificial: de Turing a los modelos de lenguaje
3. Datos, modelo, entrenamiento, inferencia: los conceptos básicos en un solo ejemplo
4. Cómo leer la notación matemática: símbolos, subíndices, sumatorios y cuantificadores
5. Conjuntos y relaciones: las piezas con las que se construyen las definiciones en IA
6. Funciones y aplicaciones: por qué todo modelo de IA es una función
7. Lógica y demostraciones: las reglas con las que se razona en IA
8. Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales
9. Álgebra lineal para aprendizaje automático: vectores, matrices y por qué la IA sobre todo multiplica
10. Derivadas, gradiente y regla de la cadena: cómo sabe un modelo en qué dirección aprender
11. Descenso de gradiente: cómo aprende un modelo
12. Qué es la probabilidad: del lanzamiento de un dado a los axiomas de Kolmogórov
13. Probabilidad condicionada y teorema de Bayes: cómo cambiar una estimación cuando te enteras de algo nuevo
14. Variable aleatoria y función de distribución: una sola función que lo dice todo sobre la distribución
15. Función de densidad y función de probabilidad: por qué una variable continua tiene probabilidad cero en cada punto
16. Esperanza, varianza y covarianza: dónde está una distribución, qué anchura tiene y qué se relaciona con qué
17. Resumen de las distribuciones de probabilidad: Bernoulli, binomial, Poisson, uniforme, normal y exponencial
18. Ley de los grandes números y teorema central del límite: por qué las medias se comportan de forma tan predecible
19. Estadística y estimación de parámetros: máxima verosimilitud, MAP e intervalos de confianza
20. Teoría de la información: entropía, entropía cruzada y divergencia KL, el origen de las funciones de pérdida
21. Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones
22. Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search
23. Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas
24. Lógica y sistemas basados en conocimiento: encadenamiento hacia delante y hacia atrás, resolución y sistemas expertos
25. Planificación: STRIPS, el mundo de bloques, heurísticas a partir de la relajación y la planificación en los agentes de IA
26. Búsqueda local y recocido simulado: un viajante por las capitales regionales checas
27. Algoritmos genéticos: población, cruce, mutación y selección en una mochila para la excursión
28. Estrategias evolutivas y programación genética: de la regla de un quinto a la ley de Kepler
29. Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto
30. Optimización por enjambre de partículas: inercia, experiencia propia y experiencia del enjambre
31. Neuroevolución: evolución de los pesos y la forma de las redes neuronales, y el algoritmo NEAT
32. Conjuntos difusos y funciones de pertenencia: cómo escribir «algo cálido»
33. Lógica difusa y probabilidad: por qué «algo cálido» no significa «probablemente cálido»
34. Lógica difusa: t-normas, implicaciones y reglas SI–ENTONCES
35. Control difuso: Mamdani y Sugeno, del ventilador al péndulo invertido sobre un carro
36. Agrupamiento difuso: el algoritmo fuzzy c-means y los puntos entre clusters
37. Sistemas neuro-difusos (ANFIS): reglas difusas que aprenden de los datos
38. Cadenas de Markov: matriz de transición, distribución estacionaria y PageRank
39. Modelos ocultos de Márkov: el algoritmo de Viterbi y el casino deshonesto
40. Redes bayesianas: por qué está mojada la hierba y qué significa eso para el aspersor
41. El filtro de Kalman: cómo estimar a partir de mediciones imprecisas dónde está un coche y a qué velocidad va
42. Tipos de aprendizaje automático: supervisado, no supervisado, semisupervisado y más
43. Prompts, contexto y RAG: cómo darle a un modelo la información correcta
44. Autocodificadores variacionales (VAE): imágenes nuevas a partir de un espacio latente continuo
45. Redes generativas adversarias (GAN): el falsificador contra el detective
46. Modelos de difusión: cómo el ruido puro se convierte en una imagen
47. Procesos de decisión de Markov: estados, acciones, recompensas y ecuaciones de Bellman
48. Q-learning y DQN: aprender el valor de las acciones, de la tabla a la red neuronal
49. Gradiente de la política y PPO: aprender directamente la política
50. Cómo funciona un agente de IA: un modelo de lenguaje en un bucle con herramientas
51. Programación con agentes de IA: encargo, pruebas y revisión
52. Evaluación y seguridad de los sistemas de IA: cómo medir y cómo vigilar

Temario completo de la serie 52 de 83 temas publicados

Una hormiga sola no tiene mapa, no sabe contar y apenas ve unos centímetros por delante. Aun así, la colonia encuentra de forma fiable el camino más corto del hormiguero a la comida. Ninguna hormiga lo conoce: surge de cómo todas juntas marcan el terreno. A principios de los años noventa, Marco Dorigo, del Politécnico de Milán, se dio cuenta de que el mismo truco se puede aplicar al problema del viajante. Así nació la optimización por colonia de hormigas y, con ella, todo el campo de la inteligencia de enjambre.

Continúa el artículo Búsqueda local y recocido simulado. Resolvemos la misma tarea —un circuito por las capitales regionales con un óptimo de 1 060,4 km—, así que veremos qué tal les va a las hormigas frente al recocido.

1. Comunicarse con rastros

Definición — estigmergia

La estigmergia es una comunicación indirecta a través del entorno: un individuo modifica el entorno y ese cambio influye en lo que harán después los demás (o él mismo). El término lo acuñó Pierre-Paul Grassé en 1959 al estudiar cómo construyen las termitas sus termiteros.

2. El experimento del doble puente

En 1989, Goss, Deneubourg y sus colegas construyeron para hormigas argentinas dos puentes entre el hormiguero y la comida, uno el doble de largo que el otro. Al cabo de un rato, la mayor parte de la colonia iba por el más corto. ¿Por qué? Una hormiga que eligió la rama corta llega antes a la comida y, cuando vuelve, la rama corta ya está marcada junto a la comida. El camino corto se marca más deprisa y empieza a ganar.

Definición — modelo de elección de rama (Deneubourg et al.)

Si al principio la rama corta y la larga tienen cantidades de feromona A y B, una hormiga elige la rama corta con probabilidad

P = (k + A)^h / ((k + A)^h + (k + B)^h),

donde k determina con qué fuerza reacciona la hormiga a un rastro débil y h > 1 amplifica las diferencias. La hormiga deposita feromona al principio de la rama elegida y al final cuando llega.

P = (k + A)^h / ((k + A)^h + (k + B)^h)

P

la probabilidad de que la siguiente hormiga vaya por la rama corta: la hormiga no decide con certeza, solo con un peso; la rama larga se queda con el resto 1 − P

A

feromona en la rama corta: lo único que la hormiga «sabe» del camino; cuanta más hay, más atrae la rama corta

B

feromona en la rama larga: en el denominador compite con la corta, así que decide la proporción de los rastros, no su cantidad absoluta

k

un «umbral de atención»: se suma por igual a ambas ramas, de modo que las primeras moléculas de feromona apenas cambian la proporción; sin él, la primera hormiga decidiría por toda la colonia

h

el amplificador: una potencia mayor que 1 exagera la diferencia; es justo lo que convierte una pequeña ventaja casual en retroalimentación positiva

Ejemplo — cómo deciden k = 30 y h = 2

En la rama corta hay A = 20 unidades de feromona; en la larga, B = 10:

P = (30 + 20)² / ((30 + 20)² + (30 + 10)²) = 2 500 / (2 500 + 1 600) = 2 500 / 4 100 ≈ 0,610.

• Rastros iguales (A = B, por ejemplo ambos nulos): P = 0,500, puro azar.
• Cinco unidades contra cero: P = 35² / (35² + 30²) ≈ 0,576; un rastro pequeño apenas decide nada, ese es el trabajo de k.
• A = 60, B = 10: P = 8 100 / (8 100 + 1 600) ≈ 0,835, ya un claro predominio.
• Sin amplificación (h = 1), con A = 20 y B = 10 saldría solo 50 / 90 ≈ 0,556 en lugar de 0,610.

Una simulación del modelo (k = 30, h = 2, diez hormigas por paso, rama corta de 5 pasos, larga de 10) muestra la proporción de feromona en la rama corta en ocho colonias:

Siete colonias se estabilizaron en la rama corta y una en la larga: las primeras hormigas eligieron por casualidad la rama larga y la retroalimentación positiva la «bloqueó». De cien colonias, 85 terminaron en la rama corta y 9 en la larga. Cuando ambas ramas son igual de largas, las colonias se reparten más o menos a medias (46 y 42): la simetría la rompe el azar. La longitud del camino desplaza, pues, el resultado, pero no lo garantiza. Veremos la misma debilidad en el algoritmo.

3. El sistema de hormigas

El sistema de hormigas de Dorigo (Ant System, 1992) envía hormigas virtuales por un grafo de ciudades. Cada una construye un circuito completo y, según lo corto que sea, deposita feromona en sus aristas.

Definición — circuito y su longitud

Se dan n ciudades y distancias d_ij = d_ji > 0. Un circuito es un orden de las ciudades π = (π₁, …, π_n) en el que cada ciudad aparece exactamente una vez; su longitud es

L(π) = d_π1π2 + d_π2π3 + … + d_πnπ1

(el último término devuelve al viajero a casa). Una arista (i, j) pertenece al circuito si i y j van seguidas en él. El problema del viajante busca el circuito de longitud mínima.

Definición — regla de transición

Una hormiga en la ciudad i va a una ciudad j aún no visitada con probabilidad

p_ij = τ_ij^α · η_ij^β / ∑_l τ_il^α · η_il^β,

donde τ_ij es la feromona de la arista, η_ij = 1 / d_ij es la visibilidad (las ciudades cercanas son más atractivas) y la suma recorre todas las ciudades no visitadas l. Los parámetros α y β ponderan el rastro frente a la distancia.

p_ij = τ_ij^α · η_ij^β / ∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

la probabilidad de un paso de i a j: sorteamos en lugar de elegir lo mejor, para que la colonia siga probando también otros circuitos

τ_ij^α

la memoria de la colonia: la feromona lleva la experiencia de las hormigas anteriores; el exponente α dice cuánto fiarse de ella (α = 0 la apaga por completo)

η_ij^β

codicia: η = 1 / d favorece las ciudades cercanas; es un consejo que tenemos gratis desde la primera iteración, cuando la feromona aún no sabe nada

∑ … sobre N_i

la suma de los pesos de todas las ciudades aún no visitadas: al dividir, los pesos se convierten en probabilidades que suman 1; las ciudades visitadas no están en ella, así que la hormiga no vuelve a ellas

Ejemplo — una decisión de una hormiga

Una hormiga está en la ciudad i y le quedan tres ciudades: a 50, 100 y 150 km, con feromona τ = 1, 3 y 2. La constante de la visibilidad se simplifica en la fracción, así que calculemos con η = 100 / d, es decir, 2, 1 y 2/3. Con α = 1 y β = 3:

• pesos: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• su suma, 11,593;
• probabilidades 0,690, 0,259 y 0,051.

Gana la ciudad más cercana, aunque tiene menos feromona. Con β = 1 saldría 0,316, 0,474 y 0,211: manda la feromona. Y con β = 0 decide solo el rastro: 0,167, 0,500 y 0,333 (proporciones 1 : 3 : 2).

Definición — actualización de la feromona

Tras cada iteración la feromona se evapora en todas partes y cada hormiga m añade a las aristas de su circuito de longitud L_m una cantidad proporcional a 1 / L_m:

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ circuito m} Q / L_m,

donde ρ ∈ (0, 1) es la tasa de evaporación.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ circuito m} Q / L_m

τ_ij a la izquierda

la nueva feromona de la arista: aquello por lo que se guiarán las hormigas de la próxima iteración

(1 − ρ)

evaporación: cada iteración quita a cada rastro la misma fracción ρ; la experiencia antigua se debilita así geométricamente y la colonia puede reaprender

τ_ij a la derecha

la feromona hasta ahora: la memoria solo se corrige, no se empieza de cero

∑_m

suma sobre las hormigas que pasaron por la arista: cada hormiga añade solo a las aristas de su circuito; una arista que usan más hormigas recibe más; aquí se cuentan los «votos» de la colonia

Q / L_m

una recompensa inversamente proporcional a la longitud del circuito: circuito más corto = rastro más fuerte; la constante Q solo fija la escala

Ejemplo — una actualización

Una arista tiene τ = 1, ρ = 0,3, Q = 1 000 y han pasado por ella dos hormigas con circuitos de 1 100 y 1 300 km:

τ ← 0,7 · 1 + 1 000 / 1 100 + 1 000 / 1 300 ≈ 0,700 + 0,909 + 0,769 = 2,378.

Una arista por la que no pasó nadie tiene tras la misma iteración solo 0,7. La hormiga con el circuito más corto añadió más (0,909 frente a 0,769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # evaporación
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # circuito más corto, rastro más fuerte
            tau[b][a] += Q / L

El sistema de hormigas completo se limita a alternar la construcción de circuitos y la actualización, y recuerda el mejor circuito que alguien haya construido nunca:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # al principio igual en todas partes
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # evaporación + nuevo rastro
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Hormigas sobre las capitales regionales

Soltemos 13 hormigas (una desde cada ciudad) durante 100 iteraciones con α = 1, β = 3 y ρ = 0,3. El mapa muestra la feromona en las aristas tras las iteraciones 1, 5, 20 y 100; cuanto más gruesa la línea, más feromona:

En la primera iteración el rastro está repartido casi por todas partes y el mejor circuito mide 1 292,6 km. Ya en la quinta iteración una de las hormigas encuentra el óptimo de 1 060,4 km. La feromona se concentra después en las aristas de los buenos circuitos —las líneas débiles desaparecen, las fuertes se quedan— y la hormiga media construye un circuito de unos 1 250 km. La colonia no converge del todo: sigue probando un poco.

Traza de la ejecución por iteraciones: el mejor circuito encontrado hasta el momento y el circuito medio de las trece hormigas en esa iteración:

El mejor circuito mejora a saltos (la tercera iteración no aportó nada nuevo, la cuarta recortó 111 km), mientras que la media baja más despacio y de forma irregular: las hormigas sortean, así que incluso en una buena iteración algunas construyen circuitos flojos. La diferencia entre la media y el mejor es justo la exploración que impide que la colonia se congele del todo.

No siempre sale tan bien. De veinte ejecuciones con semillas distintas, solo 7 encontraron el óptimo; la media fue de 1 073,9 km y el peor resultado, 1 083,0 km. El recocido, con 98 de 100 en la misma tarea, fue más fiable. Para hacerse una idea: el «vecino más cercano» voraz, que siempre va a la ciudad no visitada más próxima, da entre 1 120 y 1 336 km según el punto de partida. Las hormigas son claramente mejores, pero el sistema de hormigas básico por sí solo no es un campeón; por eso surgieron sus variantes mejoradas.

5. Para qué sirven α, β y ρ

Con trece ciudades se puede resolver mucho incluso sin feromona. La diferencia solo la muestra una tarea mayor: las mismas 60 ciudades aleatorias que en el artículo sobre el recocido, 30 hormigas, 150 iteraciones, media de tres ejecuciones:

• Sin feromona (α = 0), las hormigas son solo viajeros voraces aleatorios y no aprenden nada: circuitos un tercio más largos.
• Sin distancias (β = 0), la colonia no tiene dónde apoyarse: los primeros circuitos son completamente aleatorios y la feromona que dejan lleva a otros igual de aleatorios.
• Una evaporación lenta mantiene demasiado tiempo los rastros de los primeros circuitos, malos, y la colonia aprende despacio. Una evaporación rápida, en cambio, olvida también lo bueno.

Cuánto tiempo recuerda la colonia se puede calcular con exactitud. Basta con seguir una sola arista.

Teorema — feromona estacionaria y vida media de la evaporación

Si una arista recibe en cada iteración el mismo incremento Δ ≥ 0, es decir, τ_t+1 = (1 − ρ) τ_t + Δ, entonces

τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ) → Δ/ρ cuando t → ∞.

Sin incremento (Δ = 0), el rastro baja a la mitad en t_½ = ln 2 / (−ln(1 − ρ)) iteraciones.

Demostración. Restando Δ/ρ a ambos lados de la recurrencia se obtiene τ_t+1 − Δ/ρ = (1 − ρ)(τ_t − Δ/ρ), porque (1 − ρ)Δ/ρ + Δ = Δ/ρ. La desviación respecto de Δ/ρ se multiplica, pues, en cada iteración por el número 1 − ρ ∈ (0, 1) y tiende geométricamente a cero. La vida media es la solución de (1 − ρ)^t = ½. ∎

τ^* = Δ / ρ

τ^*

el nivel en el que se estabiliza la feromona de la arista: el aporte y la evaporación están en equilibrio

Δ

cuánto recibe la arista por iteración: las aristas de circuitos frecuentes y cortos tienen un Δ grande y, por tanto, también un nivel alto

ρ

en el denominador: una evaporación lenta deja crecer mucho los rastros y las diferencias entre aristas tardan en igualarse; una rápida los mantiene bajos y dependientes solo de las últimas iteraciones

Una arista con τ₀ = 1 y ρ = 0,3: una recibe en cada iteración Δ = 1; la otra no la usa nadie.

La arista usada se acerca a 1/0,3 ≈ 3,33; la no usada cae en diez iteraciones por debajo de tres centésimas. La vida media de la evaporación para las filas de la tabla anterior: con ρ = 0,3 es de 1,94 iteraciones; con ρ = 0,02, nada menos que 34,31 iteraciones —así que los rastros de los primeros circuitos aleatorios mandan todavía durante decenas de iteraciones—, y con ρ = 0,9, solo 0,30 iteraciones, de modo que la colonia recuerda prácticamente solo la última ronda.

La mejor configuración dio entre 2 194 y 2 314 km, comparable con el recocido del artículo anterior, que en las mismas ciudades terminó entre 2 210 y 2 270 km.

6. Hormigas mejores

• La estrategia elitista añade feromona extra al mejor circuito hasta el momento para que no se pierda.
• MAX–MIN Ant System (Stützle y Hoos, 2000) solo permite depositar feromona a la mejor hormiga y mantiene τ entre un límite inferior y uno superior. El límite inferior garantiza que ninguna arista desaparezca del todo, de modo que la colonia no se congela antes de tiempo, como la que en el experimento del puente acabó en la rama larga.
• Ant Colony System (Dorigo y Gambardella, 1997) elige con cierta probabilidad directamente la mejor arista y quita feromona ya durante la construcción del circuito, para que las demás hormigas prueben en otro sitio.
• Búsqueda local. En la práctica, cada circuito construido por una hormiga se pule además con movimientos 2-opt del artículo sobre el recocido. Las hormigas encuentran una buena región y el escalador la afina; en los años noventa esta combinación estaba entre los mejores métodos para el problema del viajante.

Definición — estrategia elitista y MAX–MIN Ant System

La estrategia elitista añade a la actualización habitual otros e · Q / L^best en cada arista del mejor circuito hasta el momento, de longitud L^best; e es el número de «hormigas elitistas».

MAX–MIN Ant System deposita feromona solo según el mejor circuito y recorta el resultado al intervalo [τ_min, τ_max]:

τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), donde Δ_ij = 1 / L^best para las aristas del mejor circuito y 0 en otro caso.

Stützle y Hoos eligen como límite superior τ_max = 1 / (ρ L^best), justo el valor estacionario Δ/ρ del teorema anterior para una arista que está en el mejor circuito todas las veces. El límite inferior es una pequeña fracción del superior; además, al principio la feromona se fija en τ_max para que las primeras iteraciones exploren lo más ampliamente posible.

Definición — reglas de Ant Colony System

Regla proporcional pseudoaleatoria: una hormiga en la ciudad i sortea q en [0, 1). Si q ≤ q₀, va directamente a la ciudad de mayor peso, j = arg max_{l ∈ Ni} τ_il · η_il^β; si no, elige por sorteo según la regla de transición del sistema de hormigas.

Actualización local: justo después de pasar por la arista (i, j), τ_ij ← (1 − ξ) τ_ij + ξ τ₀, de modo que una arista usada se debilita un poco hacia el valor inicial τ₀.

Actualización global tras una iteración, solo en las aristas del mejor circuito: τ_ij ← (1 − ρ) τ_ij + ρ / L^best.

Dorigo y Gambardella (1997) usan en el artículo original q₀ = 0,9, β = 2 y ρ = ξ = 0,1: en nueve de cada diez pasos la hormiga toma la mejor arista y solo en el décimo explora.

7. Dónde trabajan las hormigas

• Encaminamiento en redes. El algoritmo AntNet (Di Caro y Dorigo, 1998) envía por la red pequeños paquetes-hormiga que miden los retardos y actualizan las tablas de encaminamiento. Así la red se adapta continuamente a la congestión.
• Rutas de vehículos y planificación. Reparto de mercancías, recogida de residuos u orden de los pedidos en producción: tareas emparentadas con el problema del viajante, en las que los algoritmos de hormigas se usan junto con la búsqueda local.
• Inteligencia de enjambre. Una colonia de hormigas es uno de los ejemplos de cómo de individuos simples y reglas locales surge un comportamiento inteligente del conjunto. Otro, el enjambre de partículas, es el tema del próximo artículo.

8. Resumen

• Las hormigas se comunican con rastros en el entorno (estigmergia): un camino más corto se marca más deprisa y la retroalimentación positiva lo refuerza.
• En el modelo del doble puente, 85 de 100 colonias se estabilizan en la rama corta, pero el azar también puede bloquear la larga.
• El sistema de hormigas elige la siguiente ciudad según la feromona τ^α y la distancia η^β; la feromona se evapora a la tasa ρ y los circuitos cortos añaden más.
• En las capitales regionales encontró el óptimo, pero solo en 7 de 20 ejecuciones; en 60 ciudades quedó a la par del recocido. Sin feromona o sin distancias, bastante peor.
• Las variantes usadas en la práctica (MAX–MIN, ACS) evitan la congelación prematura y combinan las hormigas con búsqueda local.

¿Quieres probarlo tú? Pide a un agente de IA que escriba una simulación del doble puente y mira qué pasa si «cierras» la rama corta a mitad del experimento: ¿consigue la colonia volver a la larga?

¿Lo ves de otra manera? Escribe a support@coden-app.com.