Objetivos didácticos
Hay problemas que no sabemos resolver, y las furgonetas salen igual cada mañana. Este laboratorio empieza por el problema del viajante —cuántas rutas hay, por qué ni siquiera sabemos comprobar que una es la mejor y cómo se acota el error— y luego mira a cinco bichos que resuelven versiones de él sin que ningún individuo conozca el problema: hormigas, termitas, un moho mucilaginoso, abejas y las obreras de un hormiguero que se reparten el trabajo. Todo se mide con presupuesto fijo, contra una cota y contra métodos clásicos, y el resultado se cuenta aunque no deje bien a los bichos. Tercero de la trilogía de Optimización, después de Optimización lineal y Optimización heurística. Pensado para Universidad; los bloques A y B se pueden trabajar en Bachillerato.
Qué se aprende
- La explosión combinatoria del problema del viajante: (n − 1)!/2 rutas, de dónde sale cada factor y por qué un ordenador mil veces más rápido solo compra dos paradas más (salas 1-2).
- La diferencia entre comprobar una ruta y certificar que es óptima, P contra NP, y el trato que hace todo el lab: renunciar al óptimo a cambio de una respuesta con el error acotado (salas 3-5).
- El experimento del puente doble con hormigas reales, la regla de elección con su parámetro α, la evaporación ρ y la estigmergia de Grassé: comunicarse a través del entorno (salas 6-9).
- Del puente al mapa: trazar rutas a mano, el goloso y su último tramo, el intercambio 2-opt y la colonia de hormigas de Dorigo con rastro y vista (salas 10-14).
- Afinar una colonia con presupuesto fijo: cuántas hormigas, cuánto olvidar, cuánto pesan rastro y vista, cuánto pasear al principio y quién deposita. En cada perilla, más no es mejor, y el alumno lo mide (salas 15-19).
- Medir y mezclar: la cota del árbol generador mínimo, la colonia que pule con 2-opt y un torneo honesto donde la colonia sola pierde (salas 20-23).
- Otros tres mecanismos con la misma receta: el moho que diseña redes baratas y robustas, las abejas que reparten intentos entre opciones de calidad desconocida y deciden por quórum, y las hormigas Pheidole, que reparten el trabajo sin jefe con umbrales de respuesta (salas 24-33).
- Lo que aporta de verdad lo descentralizado: no calidad, sino adaptación cuando el problema cambia y tolerancia a fallos (salas 8, 22, 23, 32, 33 y 34).
Ideas matemáticas clave
- Con el almacén fijo y la ruta al revés midiendo lo mismo, n puntos dan (n − 1)!/2 rutas. El factorial crece tan deprisa que 29!/2 ≈ 4,42·10³⁰: a mil rutas por segundo, diez mil millones de veces la edad del universo.
- La versión de decisión del viajante es NP-completa, pero certificar la optimalidad es más difícil todavía. Lo que sí se puede es acotar: AGM ≤ óptimo ≤ mi ruta, porque quitarle un tramo a la mejor ruta deja un camino que une todos los puntos. El gap contra la cota es una garantía pesimista.
- La regla de elección P = (c + τ)^α / Σ convierte ventajas pequeñas en grandes cuando α > 1 (refuerzo no lineal). En el mapa, P ∝ τ^α · η^β combina memoria (rastro) y vista (1/distancia).
- La evaporación τ ← (1 − ρ)τ hace que el rastro se desvanezca geométricamente (0,9¹⁰ ≈ 0,35). Sin decaimiento lo aprendido se fosiliza; con demasiado no se aprende nada.
- Todas las comparaciones se hacen con presupuesto fijo, contado en cálculos de distancia. Sin esa moneda, más hormigas o más vueltas siempre ganan y no hay compromiso que descubrir.
- La entropía de la matriz de feromona mide cuánta duda le queda a la colonia: la curva de resultados no distingue «va lento» de «está muerto»; la entropía sí.
- El moho sigue dD/dt = |Q|^μ − D con el caudal repartido por las leyes de Kirchhoff: μ pequeño conserva bucles (red cara y robusta), μ grande se acerca al árbol (barato y frágil).
- El dilema explorar/aprovechar (el bandido de varios brazos) tiene siempre dos formas de fallar: decidir con poca información o gastar el presupuesto mirando.
- Los umbrales de respuesta P = s^n / (s^n + θ^n) reparten el trabajo sin jefe; su dispersión tiene un compromiso (todas a la vez o muchas sin trabajar), y si los umbrales aprenden, de generalistas idénticas salen especialistas.
- Las únicas garantías demostradas del lab son de métodos clásicos: Christofides (nunca más de 1,5 veces el óptimo en el caso métrico) y Graham (la regla golosa de reparto nunca más de 4/3 − 1/(3m)). Ningún bicho da garantías; dan adaptación.
Contenidos por salas
Sala 1 · Un problema de 1832
Una furgoneta recorre sobre un plano de ciudad los 30 puntos de reparto en el orden en que llegaron los pedidos (111 km). El alumno valora a ciegas la importancia del problema y después lee el contexto actual y el histórico (el manual alemán de 1832, Dantzig, Fulkerson y Johnson en 1954). Al final la misma furgoneta recorre la mejor ruta conocida: 43 km.
Tareas para el alumno
- Valorar la importancia del problema antes de leer nada.
- Reconocer entre cuatro situaciones nuevas cuáles son el mismo problema disfrazado.
Sala 2 · Treinta puntos
Estimación a ciegas de cuánto se tarda en probar todas las rutas de 30 puntos, y después la cuenta hecha por el alumno: cuenta las 24 ordenaciones de 4 paradas, descubre por qué se divide entre 2 buscando parejas de kilómetros en 24 miniaturas con flechas, y escribe 29!/2 (el lab entiende factoriales). Termina con la escalera de tiempos y la frase clave: un ordenador mil veces más rápido solo compra dos paradas.
Tareas para el alumno
- Contar las ordenaciones de 4 paradas.
- Explicar por qué cada ruta aparece dos veces.
- Escribir el número de rutas con 30 puntos.
Sala 3 · Ni siquiera sabemos comprobarlo
Se separan comprobar una ruta (barato) y certificar que es la mejor (nadie sabe hacerlo deprisa), y se presenta P contra NP. Un reto con una ruta de 460 y una cota de 430 introduce la idea que salva el problema en la práctica: acotar el error sin conocer la solución.
Tareas para el alumno
- Distinguir «no se conoce un algoritmo rápido» de «no existe».
- Decidir qué se puede afirmar con una ruta y una cota.
Sala 4 · Renunciar al óptimo
El récord exacto (85 900 ciudades en 2006) frente a la furgoneta que sale a las siete. Se fija el vocabulario del lab: cota, gap y método anytime, con una barra dibujada sobre la instancia real.
Tareas para el alumno
- Elegir en qué caso compensa pagar el óptimo exacto.
- Calcular cuánto cuesta un 4% de exceso a una flota.
Sala 5 · Por qué mirar a un bicho
Una vitrina con cuatro escenas animadas (hormigas con su rastro, un moho que teje su red, abejas y su danza, termitas levantando un arco). Qué aporta una colonia que no aporta un algoritmo escrito por una persona, y el contrapunto honesto: la naturaleza no optimiza, se conforma. La pregunta final se repite en la sala 33.
Tareas para el alumno
- Identificar la afirmación falsa sobre los métodos inspirados en la naturaleza.
- Elegir qué bicho copiar para diseñar una red de tranvía.
Sala 6 · El puente doble
El experimento de Goss y Deneubourg (1989) con hormigas argentinas: el alumno predice el reparto del tráfico, suelta 200 hormigas y ve el rastro engordar en la rama corta sobre un suelo de tierra, con una gráfica en vivo. Un reto numérico sobre viajes de ida y vuelta descubre el mecanismo: quien toma la corta vuelve antes a depositar.
Tareas para el alumno
- Predecir el reparto antes de soltar a las hormigas.
- Responder qué hormiga decidió usar la rama corta.
- Calcular cuántas gotas hay en la corta por cada gota de la larga.
Sala 7 · La única regla
La regla de elección P = (c+τ)^α / Σ, con dos cuentas a mano y una horquilla interactiva. Después, la segunda mitad del experimento de Goss (la rama corta se abre tarde) y la curva de compromiso de α que mide el alumno: con α pequeño la colonia no se compromete, con α grande se cierra sobre la rama larga y no rectifica.
Tareas para el alumno
- Calcular la probabilidad de una rama con α = 1 y α = 4.
- Medir el tráfico final para varios α y explicar los dos extremos.
Sala 8 · Olvidar a tiempo
La evaporación τ ← (1 − ρ)τ y un reto con 0,9¹⁰. A mitad del experimento se corta la rama buena y el alumno mide cuántas hormigas se pierden para cada ρ: sin evaporación la colonia se fosiliza, con demasiada es amnésica. Es la sala que justifica el lab: la colonia gana por adaptable, no por rápida.
Tareas para el alumno
- Calcular cuánto rastro queda tras 10 pasos.
- Medir la curva de ρ y diagnosticar los dos fallos.
Sala 9 · Escribir en el suelo
Las termitas de Grassé (1959) levantan pilares sin plano: cada una suelta su barro donde más huele a barro fresco. Con olor salen pilares; sin él, una capa plana. Se define la estigmergia y se destila la receta de todo el lab: refuerzo, decaimiento y ruido.
Tareas para el alumno
- Responder quién decide dónde va cada pilar.
- Distinguir un sistema que no es estigmergia.
- Predecir qué le pasa a una colonia sin ruido.
Sala 10 · Hazlo tú
El alumno traza a mano una ruta por 12 puntos (19 958 400 rutas posibles) pinchando las paradas. Debe bajar de 30 km: ni el orden de la lista ni el goloso lo consiguen. La furgoneta recorre su ruta y después la mejor, y el alumno calcula su propio gap. Pista a los dos intentos y salida abierta a los cuatro.
Tareas para el alumno
- Trazar una ruta de menos de 30 km.
- Calcular el gap de su ruta respecto de la óptima.
Sala 11 · Ir siempre a lo más cerca
El vecino más cercano, paso a paso, con las candidatas dibujadas en cada parada. Al final, la vuelta a casa mide casi 10 km cuando el tramo medio es de 2: el goloso se deja las sobras y acaba un 49% por encima de la mejor ruta.
Tareas para el alumno
- Predecir a ciegas cuánto se pasará el goloso.
- Calcular su exceso en porcentaje.
- Explicar por qué no puede arreglar el último tramo.
Sala 12 · Deshacer cruces
El 2-opt de Croes (1958) hecho a mano: el alumno pincha dos tramos que se cruzan y se intercambian; si el cambio alargara la ruta, se rechaza. Baja de 36 km desde los 50 del goloso. Se ve por qué un intercambio solo mira 4 distancias y por qué 2-opt se para en un óptimo local.
Tareas para el alumno
- Deshacer cruces hasta bajar de 36 km.
- Decir cuántas distancias hay que mirar en un intercambio.
Sala 13 · Una hormiga sobre el mapa
La regla de Dorigo (1992): P ∝ τ^α · η^β, rastro y vista. Tras un reto numérico, una hormiga elige parada a parada con su abanico de probabilidades a la vista, y el alumno mueve α y β para ver qué hace cada uno.
Tareas para el alumno
- Calcular la probabilidad de una candidata.
- Explicar qué hace una hormiga con β = 0 y con α = 0.
Sala 14 · El ciclo completo
Construir, depositar, evaporar: diez hormigas sobre 30 puntos durante 41 vueltas. Las tres primeras se ven hormiga a hormiga; el rastro pasa de maraña a esqueleto, con las curvas de gap y entropía debajo. Al final, tres fotos del rastro para ordenar en el tiempo.
Tareas para el alumno
- Calcular el depósito de tres hormigas sobre una arista.
- Ordenar tres fotos del rastro.
Sala 15 · ¿Un millón de hormigas?
Primera sala del bloque de afinar la colonia, con presupuesto fijo. El alumno predice, calcula cuántas vueltas caben y mide la curva del número de hormigas: una sola refuerza con ruido, 160 no tienen tiempo de aprender, y la zona buena está en torno a una docena.
Tareas para el alumno
- Calcular cuántas vueltas caben en el presupuesto.
- Medir la curva y explicar los dos extremos.
Sala 16 · Cuánto dura el recuerdo
La evaporación sobre el mapa con dos curvas a la vez: gap y entropía del rastro. Tres colonias desordenadas (ρ muy baja, sana y muy alta) para identificar por sus gráficas.
Tareas para el alumno
- Medir la curva de ρ.
- Reconocer la colonia estancada y la indecisa por su entropía.
Sala 17 · Memoria contra vista
Una rejilla de 30 colonias (α × β) que se miden al pincharlas, coloreadas por su gap. La columna β = 0 es una pared y la fila α = 4 sale peor que la de α = 2.
Tareas para el alumno
- Encontrar una casilla por debajo del 6%.
- Explicar el fallo de β = 0 y el de α alto.
Sala 18 · El paseo del principio
La feromona inicial τ₀ en una colonia que se fía del rastro (α = 3, β = 1). Cada medida dice cuántas vueltas han sido casi al azar: con τ₀ minúsculo ninguna, con τ₀ enorme todas.
Tareas para el alumno
- Medir la curva de τ₀.
- Explicar por qué fallan los dos extremos.
Sala 19 · ¿Todas pintan?
AS, elitista y MAX-MIN medidas con tres presupuestos en una tabla. La sorpresa: MMAS es la peor con poco presupuesto y la mejor con mucho, porque su suelo de rastro la mantiene explorando.
Tareas para el alumno
- Completar las columnas de 4 000 y 40 000.
- Explicar por qué el ganador cambia con el presupuesto.
Sala 20 · Un suelo para el óptimo
El árbol generador mínimo crece tramo a tramo bajo la ruta golosa y da una cota: sin conocer la mejor ruta, se garantiza que la golosa se pasa como mucho un 45%. Held-Karp y Christofides en el plegable.
Tareas para el alumno
- Calcular el gap garantizado contra la cota.
- Decidir qué se puede afirmar con un 3% contra la cota.
Sala 21 · Hormigas con navaja
La colonia pule cada ruta con 2-opt sobre 60 puntos, con presupuesto fijo. El alumno mide cuántas pasadas conviene dar: pulir rescata casi todo, y pasado un punto se come las vueltas de colonia.
Tareas para el alumno
- Medir la curva de pasadas de 2-opt.
- Explicar qué aporta pulir y por qué no conviene pulir de más.
Sala 22 · El torneo
Seis métodos en cuatro mapas con el mismo presupuesto. La colonia sola pierde contra 2-opt con reinicios en todos; gana la colonia que pule, y solo en el mapa grande. Se dice así, y se remite a la sala 8 para explicar su valor real.
Tareas para el alumno
- Leer el torneo mapa a mapa.
- Explicar para qué sirve la colonia si no gana en potencia bruta.
Sala 23 · El combate
Cinco métodos corren en directo sobre 60 puntos: al principio solo hay 48 paradas y a mitad del presupuesto llegan 12 pedidos nuevos. Antes del cambio lidera la colonia que pule (0,65%); justo después gana el 2-opt que repara su ruta (1,72%) y la colonia sola se hunde (45%) porque su rastro viejo apunta a rutas sin las paradas nuevas. La memoria ayuda o estorba según el cambio sea gradual o brusco, y anunciado o no.
Tareas para el alumno
- Predecir quién se recuperará antes.
- Explicar por qué la memoria de la colonia estorba tras un cambio brusco.
- Decir cuándo compensa la colonia.
Sala 24 · Un moho en el laberinto
Abre el bloque del moho Physarum: red barata frente a red con bucles, Nakagaki (Nature, 2000) y cuentas de árbol (35 conexiones) frente a 630 posibles. Después el moho llena un laberinto y se queda solo con los 23 tramos del camino mínimo; sin atrofia no poda nada.
Tareas para el alumno
- Contar las conexiones de un árbol y las posibles.
- Explicar qué pasa sin atrofia.
Sala 25 · La red de Tokio
Avena sobre 36 ciudades del área de Tokio y un moho que teje la red (Tero et al., Science 2010). Con un solo parámetro μ, el alumno busca una red que cueste como mucho el doble que el árbol mínimo y que casi ningún corte la parta.
Tareas para el alumno
- Encontrar una μ con coste y fragilidad aceptables.
- Explicar por qué no basta con el árbol mínimo.
Sala 26 · La misma receta, otra cocina
El puente doble hecho con tubos de moho (se queda la rama corta), una tabla hormigas frente a moho por ingredientes, y qué bicho copiar según el problema.
Tareas para el alumno
- Identificar el decaimiento del moho.
- Elegir mecanismo para una red de fibra y para una ruta de recogida.
Sala 27 · Explorar o aprovechar
El dilema del bandido (Robbins, 1952; Charnov, 1976) en tests A/B, ensayos clínicos y redes sociales. Una abeja con 300 visitas y cinco flores: el alumno mide cuántas pruebas por flor compensan antes de comprometerse.
Tareas para el alumno
- Calcular cuántas visitas quedan tras explorar.
- Medir la curva y explicar los dos extremos.
Sala 28 · La danza
Von Frisch y la danza del meneo; reclutas por circuito de baile. El experimento de Seeley (1991): dos comederos que se intercambian a mitad. Con demasiada ganancia de reclutamiento la colmena se queda en el comedero que ya no es bueno.
Tareas para el alumno
- Calcular las seguidoras de una danza.
- Medir la curva de ganancia y explicar el bloqueo.
Sala 29 · Elegir casa
Un enjambre elige hueco por quórum (Seeley, Honeybee Democracy). Quórum bajo decide rápido y se equivoca; quórum alto acierta y llega tarde. El alumno mide el valor de la decisión para varios quórums.
Tareas para el alumno
- Medir la curva del quórum.
- Explicar los dos fallos.
Sala 30 · Repartir el trabajo
El makespan con 7 operaciones y 3 quirófanos: el alumno las reparte en un diagrama de Gantt hasta acabar en 9 horas. La regla golosa de Graham (1969) da 11: exactamente el peor caso de su garantía 4/3 − 1/(3m).
Tareas para el alumno
- Encontrar un reparto que acabe en 9 horas.
- Calcular cuánto se pasa la regla golosa.
Sala 31 · Cada una con su umbral
Umbrales de respuesta P = s^n/(s^n+θ^n) con una colonia de 100 obreras. Con umbrales iguales la colonia trabaja a golpes; con mucha dispersión, una parte no trabaja nunca. El alumno busca el término medio.
Tareas para el alumno
- Calcular cuántas obreras se ponen con un estímulo dado.
- Encontrar una dispersión que cumpla las dos condiciones.
Sala 32 · Aprender haciendo
Umbrales que bajan con la práctica: de 100 generalistas idénticas salen especialistas (histograma con dos jorobas). Si se retiran las especialistas, las demás ocupan su sitio sin que nadie las reasigne.
Tareas para el alumno
- Calcular un umbral tras 10 pasos de práctica.
- Explicar quién decide la especialización.
Sala 33 · Cuando cambia el problema
Plan exacto, plan que se recalcula cada 100 pasos y colonia de umbrales frente a una demanda que se invierte sin avisar. Antes del cambio gana el plan; con el cambio, la colonia.
Tareas para el alumno
- Decir quién gana antes y después del cambio.
- Elegir cuándo conviene cada política.
Sala 34 · El banco de pruebas
Playground sin retos: se genera un mapa de 6 a 40 puntos (con óptimo exacto hasta 13) y se sueltan hormigas, moho o abejas con sus parámetros a la vista. Cada simulación se anima suavemente y se guarda en una gráfica de rastro sobre el mismo mapa, con un botón para lanzar 100 más y ver la mediana. Los umbrales no están: reparten trabajo, no construyen rutas ni redes.
Tareas para el alumno
- Probar los tres métodos sobre un mismo mapa y comparar sus resultados.
- Mover los parámetros y comprobar en la gráfica de rastro si cambia la mediana.
Sala 35 · Ninguno gana en todos
La tabla de la receta para los cinco mecanismos con una casilla por rellenar, qué problema resuelve cada uno, la pregunta de la sala 5 otra vez (recordando lo que eligió el alumno) y el cierre honesto de la trilogía.
Tareas para el alumno
- Completar la receta de las abejas.
- Responder de nuevo la pregunta de la sala 5.
Salas para proyectar
Las más vistosas para mostrar y discutir en clase.