ES 
EnglishDefault
Українська
Polski🚚 Optimizador de Rutas de Suministro — Un Algoritmo Genético en Acción
Observa cómo un algoritmo genético hace evolucionar las rutas de entrega entre almacenes y clientes — selección, cruce y mutación reduciendo la distancia total generación tras generación.
Acerca del Optimizador de Rutas de Suministro
Enrutar eficientemente una flota de vehículos de reparto es una variante de uno de los problemas más famosos de la informática: el Problema del Viajante (TSP). Dado un depósito y un conjunto de clientes, ¿en qué orden deberían visitarse para minimizar la distancia total recorrida? Para cualquier número de paradas más allá de un puñado, comprobar todos los órdenes posibles resulta computacionalmente inviable — solo 16 clientes ya dan lugar a más de 650 mil millones de rutas distintas. El software de logística real utiliza en su lugar metaheurísticas que buscan de forma inteligente sin garantizar nunca la respuesta perfecta, y el algoritmo genético (AG) es una de las más antiguas e intuitivas de ellas.
Esta simulación hace evolucionar una población de rutas de entrega candidatas generación tras generación. En cada generación, las rutas se puntúan según su distancia total, las rutas más aptas (más cortas) tienen más probabilidades de ser elegidas como progenitoras, el cruce por orden combina dos rutas progenitoras en una ruta hija válida, la mutación de intercambio aleja a las rutas de su forma actual, y el elitismo garantiza que la única mejor ruta sobreviva intacta. Observa cómo la mejor ruta se dibuja en directo sobre el mapa y cómo el gráfico de distancia frente a generaciones tiende a la baja a medida que la población en su conjunto se vuelve más apta — estancándose ocasionalmente en un óptimo local antes de que una mutación afortunada logre un avance.
Preguntas frecuentes
¿Qué es un algoritmo genético?
Un algoritmo genético (AG) es una heurística de búsqueda inspirada en la selección natural. En lugar de deducir una solución analíticamente, un AG mantiene una población de soluciones candidatas — aquí, rutas de entrega completas — y aplica repetidamente selección, cruce y mutación para generar nuevos candidatos. Los individuos más aptos (rutas más cortas) tienen más probabilidades de transmitir su estructura a la siguiente generación. A lo largo de muchas generaciones, la calidad media de la población aumenta aunque ninguna ruta individual se haya resuelto nunca de forma directa, porque la búsqueda explora muchas regiones del espacio de soluciones en paralelo y recombina continuamente lo que funciona.
¿Qué hacen realmente el cruce y la mutación aquí?
Cada ruta es una permutación de paradas de clientes, así que un cruce ordinario produciría rutas inválidas con clientes repetidos o ausentes. Esta simulación usa cruce por orden (OX): un tramo contiguo de paradas se copia del progenitor A en las mismas posiciones, y las paradas restantes se rellenan a partir del progenitor B en el orden en que aparecen, saltando cualquier parada ya colocada. Esto garantiza una permutación válida. La mutación es una mutación de intercambio: con una probabilidad igual a la tasa de mutación, dos paradas elegidas al azar en una ruta intercambian sus posiciones, alejando la ruta de su forma actual sin llegar a crear nunca un recorrido inválido.
¿Por qué importa el elitismo?
La selección, el cruce y la mutación son todos procesos estocásticos, así que una generación puede producir por azar una población que, en promedio, sea peor que la anterior — el cruce puede romper una buena ruta y la mutación puede dañar una casi óptima. El elitismo copia la única mejor ruta de la generación actual directamente en la siguiente generación, completamente sin cambios. Esto garantiza que la mejor distancia encontrada hasta el momento nunca pueda empeorar de una generación a otra, por lo que la curva de "mejor distancia" del gráfico siempre es plana o descendente, nunca ascendente.
¿Cómo se relaciona esto con el auténtico Problema del Viajante?
Esta es una pequeña variante de enrutamiento de vehículos del Problema del Viajante (TSP): encontrar el recorrido cerrado más corto que empieza y termina en un depósito y visita a cada cliente exactamente una vez. El TSP es NP-difícil — el número de rutas posibles para N clientes es (N−1)!/2, que para apenas 16 clientes supera los 650 mil millones. Los algoritmos exactos (ramificación y poda, programación dinámica) pueden resolver instancias modestas pero escalan mal. Los algoritmos genéticos, junto con otras metaheurísticas como el recocido simulado y la optimización por colonia de hormigas, cambian la garantía de optimalidad por una ruta que suele ser muy buena y se encuentra en una fracción del tiempo — exactamente el compromiso que asume el software de logística real para flotas con decenas o cientos de paradas.
¿Por qué a veces la ruta se queda atascada en un óptimo local?
Si toda la población converge hacia rutas que comparten la misma estructura básica, el cruce entre dos progenitores similares reproduce en su mayoría esa misma estructura, y las pequeñas mutaciones de intercambio rara vez bastan para escapar de un bucle localmente bueno pero globalmente subóptimo — por ejemplo, una ruta con un cruce de aristas evitable. Esto se llama convergencia prematura: la diversidad de la población colapsa antes de encontrar el mejor recorrido posible. Aumentar la tasa de mutación, incrementar el tamaño de la población o usar un mapa nuevo para comparar ejecuciones son formas de observar este equilibrio entre exploración (diversidad) y explotación (perfeccionar lo que ya funciona).
¿Qué es la selección por torneo y por qué se usa?
La selección por torneo elige un pequeño subconjunto aleatorio de la población (un torneo, aquí de tamaño 3) y escoge al miembro más apto de ese subconjunto como progenitor. Es simple, rápida, y su presión de selección es fácil de ajustar mediante el tamaño del torneo: un torneo más grande hace más probable que el único mejor individuo domine la reproducción (convergencia más rápida, mayor riesgo de convergencia prematura), mientras que un torneo más pequeño mantiene más diversidad. Esto evita algunos escollos de la selección proporcional a la aptitud (ruleta), donde una ruta con una distancia inusualmente corta puede dominar de inmediato toda la población.
¿Cómo afectan el tamaño de la población y la tasa de mutación a la velocidad de convergencia?
Una población más grande explora más espacio de permutaciones de rutas por generación y es menos propensa a perder diversidad útil por deriva aleatoria, pero cada generación cuesta más evaluaciones de distancia. Una tasa de mutación más alta inyecta más aleatoriedad, ayudando a escapar de óptimos locales pero también alterando buenas rutas con más frecuencia, lo que puede ralentizar la convergencia o incluso empeorar temporalmente el promedio de la población (el elitismo protege a la mejor ruta única en cualquier caso). En la práctica hay un punto óptimo — tamaños de población de decenas a pocos cientos y tasas de mutación de unos pocos puntos porcentuales por gen tienden a converger más rápido para problemas de este tamaño.
Observa cómo un algoritmo genético hace evolucionar las rutas de entrega entre almacenes y clientes — selección, cruce y mutación reduciendo la distancia.
3D · motor de renderizado Three.js / WebGL · objetivo de 60 FPS · funciona enteramente en el cliente, sin instalación