10 El viajante de principio a fin
Herramientas: EvoTraveller, crossover-ga y mutation-ga, accesibles desde el portal. EvoTraveller está en inglés.
Al terminar el recorrido básico de este capítulo podrás:
- describir el problema del viajante, su representación con permutaciones y su aptitud, y calcular la longitud de una ruta;
- aplicar a mano una generación completa a una población de rutas: evaluar, seleccionar, cruzar, mutar y reemplazar;
- interpretar lo que muestra EvoTraveller durante una ejecución: la curva de aptitud, la mejor ruta y la pérdida de diversidad de la población;
- explicar qué hace la élite en el reemplazo y por qué su tamaño importa menos que su existencia;
- elegir los parámetros de EvoTraveller con mapas parecidos al caso real y estimar la calidad de la elección con mapas que no hayan servido para elegir.
10.1 Primero, observa BásicoB
¿Qué hace un algoritmo genético con un problema de rutas, de la primera generación a la última?
En los capítulos anteriores hemos estudiado cada pieza por separado: la representación, la población inicial y la aptitud, la selección, el cruce, la mutación, el reemplazo y los parámetros. En este capítulo las juntamos en un solo problema, el del viajante, con EvoTraveller (Santos et al., 2025). Ya la usamos en la sección 2.9 y en el capítulo 9. Antes de explicar nada, vamos a mirar una ejecución entera y a anotar lo que vemos. Las explicaciones llegarán en las secciones siguientes.
EvoTraveller tiene tres gráficas. Fitness muestra la aptitud de la mejor ruta de cada generación; la aptitud es la inversa de la longitud, así que si sube, la mejor ruta es más corta. Best solution dibuja la mejor ruta al final. Y bajo Solutions, el control Generation elige una generación y la gráfica dibuja todas las rutas de la población en esa generación, cada una en su casilla.
Datos. En EvoTraveller, deja los valores iniciales de la barra lateral: Number of places 10, Seed 1111, Population size 100, Generations 50, Tournament size 4, Mutation rate 0,05, Elitism 0,05 y Crossover 0,6. Pulsa Run. Después, bajo Solutions, mueve Generation a 0, a 10 y a 49, el último valor.
Predice. ¿Sigue subiendo la curva Fitness hasta la generación 50? ¿Se parecen entre sí las rutas de la población al principio? ¿Y al final?
Abrir y configurar: EvoTraveller
Ver el resultado
- La curva sube al principio y después se queda plana. La aptitud pasa de 0,0230 en la generación 0 a 0,0293 en la 3, y no cambia en las 47 generaciones siguientes. La mejor ruta mide 1/0,0293 ≈ 34,11.
- En la generación 0, las 100 rutas son distintas y casi todas están muy enredadas.
- En la generación 10 hay muchas rutas repetidas. Solo quedan 30 rutas distintas, y 43 de los 100 dibujos son la misma ruta: la mejor, de longitud 34,11.
- En la generación 49 sigue igual. Hay 23 rutas distintas, y 46 dibujos son la mejor ruta. Las demás son variaciones de ella, algunas bastante peores.
Con lo que has visto en el ejemplo 10.1, apunta una respuesta provisional a cada pregunta. Las responderemos en las secciones siguientes.
- ¿Por qué la curva Fitness no baja nunca, ni siquiera un poco?
- ¿Por qué la población se llena de copias de la misma ruta?
- La mejor ruta posible de este mapa mide 31,50 (sección 9.1). ¿Por qué el algoritmo deja de mejorar en la generación 3, si le quedan 47 generaciones?
Ver la solución
Por la élite: las mejores rutas pasan sin cambios a la generación siguiente. Lo veremos en la sección 10.5.
Porque la élite y las copias de los ganadores del torneo, que casi siempre son la mejor ruta, ocupan buena parte de la población, y la mutación solo cambia el 5 % de los individuos. Lo calcularemos en el ejercicio 10.4.
Porque la población ha perdido diversidad: casi todo lo que se cruza son copias de la misma ruta o variaciones pequeñas de ella, y no aparece nada mejor. Es la convergencia prematura de la sección 9.7. Lo veremos en la sección 10.4.
10.2 El problema y su representación BásicoB
¿Cómo se convierte una ruta en un cromosoma, y cuántas rutas hay?
El problema del viajante es seguramente el problema de optimización combinatoria más popular. Dadas n ciudades y la distancia entre cada par, hay que encontrar el circuito más corto que visita cada ciudad una sola vez y vuelve al punto de partida (Talbi, 2009, p. 7). En EvoTraveller, el punto de partida es un origen O en la posición (0, 0), y los demás lugares están en puntos enteros de una cuadrícula de 10 × 10. La distancia entre dos lugares es la distancia en línea recta, y la longitud de una ruta es la suma de las distancias de sus tramos.
Representación. Un circuito es un orden de visita, así que la representación natural es una permutación de los lugares, como en la sección 3.5: cada lugar aparece exactamente una vez (Talbi, 2009, p. 36). El origen no forma parte del cromosoma, porque siempre es el primero y el último. El cromosoma es el genotipo; la ruta completa, con el origen al principio y al final, es el fenotipo (sección 3.1). En este capítulo escribimos el cromosoma con los números de los lugares: 3 4 1 2 5 es la ruta O → 3 → 4 → 1 → 2 → 5 → O.
Aptitud. Queremos minimizar la longitud L, y EvoTraveller usa como aptitud su inversa, f = 1/L, que es mayor cuanto más corta es la ruta (sección 4.6). Como la selección de EvoTraveller es un torneo, que solo mira qué ruta es mejor que otra, daría lo mismo elegir la ruta más corta directamente.
Tamaño del espacio de búsqueda. Con n lugares contando el origen, hay (n-1)! cromosomas distintos. Pero una ruta y la misma recorrida al revés tienen la misma longitud: 3 4 1 2 5 y 5 2 1 4 3 son el mismo circuito. Las rutas distintas son la mitad:
| Lugares (n) | Cromosomas, (n-1)! | Rutas distintas, (n-1)!/2 |
|---|---|---|
| 6 | 120 | 60 |
| 10 | 362 880 | 181 440 |
| 15 | 87 178 291 200 | 43 589 145 600 |
Cada lugar más multiplica las rutas. Con 15 lugares hay más de 40 000 millones, y por eso no se pueden revisar todas salvo en mapas pequeños.
Para trabajar a mano usaremos un mapa pequeño de EvoTraveller, con la semilla de siempre: Number of places 6 y Seed 1111. Son el origen y cinco lugares (figura 10.1).
figuras/10-viajante.py, en el repositorio del libro.
Distancias entre los lugares, redondeadas a dos decimales:
| O | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| O | — | 10,63 | 7,81 | 4,12 | 8,25 | 7,21 |
| 1 | 10,63 | — | 2,83 | 7,21 | 5,00 | 3,61 |
| 2 | 7,81 | 2,83 | — | 4,47 | 3,61 | 1,00 |
| 3 | 4,12 | 7,21 | 4,47 | — | 4,12 | 3,61 |
| 4 | 8,25 | 5,00 | 3,61 | 4,12 | — | 2,83 |
| 5 | 7,21 | 3,61 | 1,00 | 3,61 | 2,83 | — |
Las longitudes de las rutas de este capítulo están calculadas con las distancias sin redondear. Si sumas las de la tabla, a veces te saldrá una centésima de diferencia.
Datos. En EvoTraveller, pon Number of places 6 y deja los demás valores iniciales (Seed 1111, Population size 100, Generations 50). Pulsa Run. Después pon Population size 10 y Generations 10, y vuelve a pulsar Run.
Predice. Con 100 individuos, ¿cuántas generaciones necesitará el algoritmo para encontrar la ruta de la figura 10.1? ¿Y con 10?
Abrir y configurar: EvoTraveller
Ver el resultado
Con 100 individuos, ninguna: la curva Fitness es plana desde la generación 0, en 0,0412, que es 1/24,29. Hay solo 120 cromosomas posibles, y una población inicial de 100 cromosomas al azar ya contiene alguno de los dos que dan la mejor ruta. Best solution dibuja la ruta O 3 4 1 2 5 O.
Con 10 individuos, nueve generaciones. La mejor aptitud empieza en 0,0384 (longitud 26,01), sube a 0,0390 (25,66) en la generación 1, a 0,0403 (24,80) en la 8 y llega a 0,0412 (24,29) en la 9.
Con un problema tan pequeño, el algoritmo genético no hace falta: basta con revisar las 60 rutas. Lo usamos porque se puede seguir a mano.- Con la tabla de distancias, calcula la longitud de la ruta 3 1 2 4 5.
- Escribe el cromosoma de la misma ruta recorrida al revés. ¿Por qué tiene la misma longitud?
- ¿Por qué no sirve como cromosoma un vector de cinco enteros del 1 al 5 elegidos libremente?
Ver la solución
La ruta es O → 3 → 1 → 2 → 4 → 5 → O. Sus tramos miden 4,12 + 7,21 + 2,83 + 3,61 + 2,83 + 7,21 = 27,81.
Al revés, la ruta es O → 5 → 4 → 2 → 1 → 3 → O, con el cromosoma 5 4 2 1 3. Usa los mismos seis tramos, recorridos en sentido contrario, y la distancia de ida y vuelta entre dos lugares es la misma.
Porque un vector de enteros puede repetir lugares y dejar otros sin visitar, por ejemplo 3 1 3 4 5, que pasa dos veces por el 3 y nunca por el 2. No sería un circuito válido. Una permutación garantiza que cada lugar aparece una sola vez (sección 3.5).
10.3 Una generación a mano BásicoB
¿Qué le pasa a una población de rutas en una generación?
Vamos a hacer a mano una generación como las de EvoTraveller, con una población de solo cuatro rutas en el mapa de la figura 10.1. Cada generación de EvoTraveller tiene tres partes: la élite, que pasa sin cambios; las copias de individuos seleccionados, que pueden mutar; y los hijos de parejas de individuos seleccionados, que se cruzan y pueden mutar. Con cuatro individuos tomaremos uno de élite, una copia y una pareja, que da dos hijos. La selección es un torneo de dos; el cruce, el OX de EvoTraveller; y la mutación, el intercambio de dos lugares, con pm = 0,2 por individuo, el valor más alto que permite la herramienta.
Los sorteos están fijados de antemano. Los hemos elegido para que en una sola generación aparezcan todos los casos que queremos ver.
1. Evaluar. La población inicial tiene cuatro rutas sorteadas al azar:
| Individuo | Cromosoma | Longitud L | Aptitud 1/L |
|---|---|---|---|
| A | 5 2 1 3 4 | 30,62 | 0,0327 |
| B | 3 1 2 4 5 | 27,81 | 0,0360 |
| C | 2 1 3 5 4 | 32,53 | 0,0307 |
| D | 1 5 4 2 3 | 29,26 | 0,0342 |
La media de las longitudes es 30,06 y la mejor ruta es B.
2. Élite. La mejor ruta, B, pasa a la generación siguiente sin cambios (sección 8.3).
3. Seleccionar. Se juegan tres torneos de dos individuos distintos, y gana el de ruta más corta (sección 5.2):
| Torneo | Contendientes | Ganador | Destino |
|---|---|---|---|
| 1 | B y C | B | Padre 1 |
| 2 | A y C | A | Padre 2 |
| 3 | D y A | D | Copia |
C, la peor ruta, no gana ningún torneo. Con dos contendientes distintos, la peor no puede ganar nunca.
4. Cruzar. EvoTraveller cruza con OX en la variante que crossover-ga llama «Orden desde el inicio», que no es la clásica de la sección 6.6, sino la de la sección 6.9. Los cortes caen detrás del primer gen y detrás del tercero, así que el segmento son las posiciones 2–3. Para formar el Hijo 1:
- copia el segmento del Padre 1 (B): · 1 2 · ·;
- lee el Padre 2 (A) desde la primera posición, saltando los lugares que ya están: de 5 2 1 3 4 quedan 5, 3 y 4;
- rellena los huecos en ese orden a partir del segundo corte: las posiciones 4 y 5 y después, dando la vuelta, la 1.
El Hijo 1 es 4 1 2 5 3. El Hijo 2 se forma igual, con los papeles cambiados: el segmento de A, · 2 1 · ·, y de B, leído desde el principio, quedan 3, 4 y 5. El Hijo 2 es 5 2 1 3 4, igual que A.
5. Mutar. Cada individuo nuevo, salvo la élite, muta con probabilidad pm = 0,2. Se sortea un número para cada uno: 0,71 para la copia de D, 0,48 para el Hijo 1 y 0,13 para el Hijo 2. Solo el último es menor que 0,2, así que solo muta el Hijo 2. El intercambio sortea dos posiciones, la 4 y la 5, y las intercambia: 5 2 1 3 4 pasa a ser 5 2 1 4 3.
Datos. Cruce OX en la variante «Orden desde el inicio», con el Padre 1 = 3 1 2 4 5 (B), el Padre 2 = 5 2 1 3 4 (A) y el segmento en las posiciones 2–3. Después, mutación por intercambio del Hijo 2, 5 2 1 3 4, en las posiciones 4 y 5.
Predice. ¿Cuánto miden los dos hijos y el mutante? ¿Alguno mejora a B, la mejor ruta de la población?
Abrir: cruce OX como en EvoTraveller Abrir: intercambio del Hijo 2
Ver el resultado
| Individuo | Cromosoma | Longitud |
|---|---|---|
| Hijo 1 | 4 1 2 5 3 | 24,80 |
| Hijo 2 | 5 2 1 3 4 | 30,62 |
| Hijo 2 mutado | 5 2 1 4 3 | 24,29 |
Mostrar aquí la herramienta (cruce OX, «Orden desde el inicio»)
6. Reemplazar. La generación siguiente está formada por la élite, la copia y los dos hijos (figura 10.2):
| Individuo | Origen | Cromosoma | Longitud |
|---|---|---|---|
| B | Élite | 3 1 2 4 5 | 27,81 |
| D | Copia, sin mutar | 1 5 4 2 3 | 29,26 |
| H1 | Hijo 1, sin mutar | 4 1 2 5 3 | 24,80 |
| H2 | Hijo 2, mutado | 5 2 1 4 3 | 24,29 |
La media de las longitudes baja de 30,06 a 26,54, y la mejor ruta, de 27,81 a 24,29. C ha desaparecido, y de A queda lo que ha pasado a los hijos.
figuras/10-viajante.py, en el repositorio del libro.
Con cinco lugares hay solo 60 rutas y es fácil dar con la mejor. En un mapa de 15 lugares, con más de 40 000 millones de rutas, una generación no da tanto de sí: la mejora es lenta y depende de muchas generaciones.
Repite el paso 4 con el OX clásico de la sección 6.6, que lee el otro padre a partir del segundo corte. Con los mismos padres, el mismo segmento y la misma mutación del Hijo 2 en las posiciones 4 y 5, ¿qué hijos salen y cuál es la mejor ruta de la generación siguiente?
Ver la solución
Hijo 1: el segmento de B es · 1 2 · ·. A, leído a partir del segundo corte, es 3 4 5 2 1; sin el 1 y el 2 quedan 3, 4 y 5, que van a las posiciones 4, 5 y 1. El Hijo 1 es 5 1 2 3 4, de longitud 30,49.
Hijo 2: el segmento de A es · 2 1 · ·. B, leído a partir del segundo corte, es 4 5 3 1 2; quedan 4, 5 y 3. El Hijo 2 es 3 2 1 4 5, de longitud 26,46. Mutado en las posiciones 4 y 5 queda 3 2 1 5 4, de longitud 26,10.
La generación siguiente sería B (27,81), D (29,26), 5 1 2 3 4 (30,49) y 3 2 1 5 4 (26,10). La mejor ruta sería 3 2 1 5 4, que mejora a B pero no llega a 24,29. Con los mismos sorteos, la variante del cruce cambia los hijos. Las dos variantes conservan el segmento de un padre y el orden relativo del otro, y ninguna es mejor en general; en el viajante lo que importa son los tramos (sección 9.10).- La herramienta abre con los padres B y A y la Variante «Orden desde el inicio», la de EvoTraveller. Arrastra los cortes para probar otros segmentos y anota los hijos. Con esta variante, ningún segmento da la mejor ruta, 3 4 1 2 5 o 5 2 1 4 3.
- Cambia la Variante a «Clásica (Goldberg, 1989)» y vuelve a probar segmentos. ¿Con cuál da el Hijo 2 la mejor ruta?
10.4 Qué pasó en la ejecución BásicoB
Con lo que hemos hecho a mano, ¿cómo se explica lo que vimos en la ejecución del ejemplo 10.1?
La curva no baja nunca porque hay élite: la mejor ruta de una generación pasa a la siguiente sin cambios, como B en la sección 10.3. La mejor aptitud solo puede subir o quedarse igual.
La población se llena de copias porque varias piezas empujan en la misma dirección. La élite ya son 6 copias de la mejor ruta. El torneo favorece a las mejores rutas, y cuantas más copias hay de la mejor, más torneos gana. Una copia sin mutar es idéntica a su padre, y con Mutation rate 0,05 solo muta uno de cada veinte individuos. En la generación 10, 43 de los 100 individuos eran la mejor ruta.
El algoritmo deja de mejorar porque ha perdido diversidad. Casi la mitad de la población es la misma ruta, y muchos cruces son entre dos copias de ella. Con el OX de EvoTraveller, que no es puro (ejemplo 6.11), cruzar dos copias da la misma ruta solo si el segmento empieza en la primera posición; si no, da la misma ruta con un trozo desplazado. En este mapa, ninguno de esos hijos es más corto que la mejor ruta: de los 36 pares de cortes posibles, 8 la repiten y 28 la alargan. Y lo que trae la mutación no basta para dar con una ruta mejor. La búsqueda queda atascada alrededor de una ruta de 34,11, mientras que la mejor posible mide 31,50: es la convergencia prematura de la sección 9.7. La población sigue cambiando, pero no aparece nada mejor.
La presión selectiva (capítulo 5) decide lo deprisa que se pierde la diversidad. En EvoTraveller la controla el Tournament size.
Datos. Los valores iniciales de EvoTraveller, salvo Tournament size, que tomará dos valores: 2 y 10. Pulsa Run con cada uno y mira la población con Generation 10.
Predice. ¿Con qué torneo hay más copias de la mejor ruta en la generación 10?
Abrir y configurar: EvoTraveller
Ver el resultado
| Tournament size | Rutas distintas en la generación 10 | Copias de la mejor ruta | Longitud de la mejor ruta |
|---|---|---|---|
| 2 | 73 | 14 | 31,86 |
| 4 (valor inicial) | 30 | 43 | 34,11 |
| 10 | 22 | 57 | 31,50 |
Con el torneo de 10, más de la mitad de la población son copias de la mejor ruta; con el de 2, solo 14. Cuanto mayor es el torneo, mayor es la presión selectiva y más deprisa se pierde la diversidad.
Fíjate en la última columna: en este mapa, con el torneo de 10 se encuentra la mejor ruta posible y con el de 4 no. Pero es una sola ejecución en un solo mapa, y ya sabemos que eso no basta (sección 9.3).Para saber qué pasa en general, hemos repetido el experimento con 30 mapas de 10 lugares, los de las semillas 1111 a 1140, con una ejecución en cada mapa. Un programa aparte nos da la mejor ruta de cada mapa, y contamos en cuántos la encuentra EvoTraveller:
| Configuración | Rutas distintas en la generación 10 (media) | Mapas en que encuentra la mejor ruta |
|---|---|---|
| Torneo de 2 | 72,8 | 29 de 30 |
| Torneo de 4 (valores iniciales) | 43,3 | 17 de 30 |
| Torneo de 10 | 22,0 | 13 de 30 |
| Torneo de 4 con Mutation rate 0,2 | 58,9 | 28 de 30 |
Con más presión selectiva se conservan menos rutas distintas y el algoritmo se atasca más a menudo. Mutar más también conserva diversidad. Los valores iniciales de EvoTraveller no son los mejores para estos mapas.
En la generación 10 del ejemplo 10.1, 43 de los 100 individuos son la mejor ruta. Con los valores iniciales, cada generación de EvoTraveller tiene 6 rutas de élite, 34 copias de ganadores de torneos y 60 hijos de cruce (lo veremos en la sección 10.7). Cada torneo enfrenta a 4 individuos distintos, y cada copia o hijo muta con probabilidad 0,05.
- ¿Qué probabilidad hay de que una copia de la mejor ruta gane un torneo?
- ¿Cuántas de las 34 copias serán, en promedio, la mejor ruta sin mutar?
- Cruzar dos copias de la mejor ruta solo la repite si el segmento empieza en la primera posición, lo que ocurre en 2 de cada 9 sorteos de cortes con 9 lugares. ¿Cuántos de los 60 hijos serán, en promedio, la mejor ruta? ¿Cuántas copias esperas en total?
Ver la solución
- Hay 57 individuos que no son la mejor ruta. La probabilidad de que los 4 contendientes salgan de ellos es
\frac{57}{100} \cdot \frac{56}{99} \cdot \frac{55}{98} \cdot \frac{54}{97} \approx 0{,}10.
Si en el torneo hay al menos una copia de la mejor ruta, gana ella, así que la probabilidad es 1 - 0{,}10 = 0{,}90.
Cada copia es la mejor ruta con probabilidad 0,90 y no muta con probabilidad 0,95: en promedio, 34 \times 0{,}90 \times 0{,}95 \approx 29.
Los dos padres son la mejor ruta con probabilidad 0{,}90^2 \approx 0{,}81. En promedio, 60 \times 0{,}81 \times \frac{2}{9} \times 0{,}95 \approx 10 hijos. En total, 6 + 29 + 10 = 45 copias, muy cerca de las 43 observadas. La mayoría vienen de la élite y de las copias, no del cruce.
10.5 La élite en el reemplazo BásicoB
¿Cuántas de las mejores rutas conviene guardar de una generación a la siguiente?
EvoTraveller usa un reemplazo generacional con élite (sección 8.3): las e mejores rutas pasan sin cambios y el resto de la población se sustituye por copias e hijos. El tamaño de la élite lo fija Elitism, como fracción de la población. Con los valores iniciales, Elitism 0,05 y 100 individuos, la élite son 6 rutas (en la sección 10.7 veremos por qué 6 y no 5).
Pero la élite son las 6 primeras posiciones de la población ordenada, no 6 rutas distintas. En el ejemplo 10.1, a partir de la generación 5, las 6 posiciones están ocupadas por copias de la misma ruta, porque la mejor ya tiene muchas copias. Una élite de 6 guarda entonces lo mismo que una élite de 1.
Datos. Los valores iniciales de EvoTraveller, salvo Elitism, que tomará tres valores: 0,01, 0,05 y 0,1. Pulsa Run con cada uno.
Predice. ¿Con qué élite se encuentra la ruta más corta?
Abrir y configurar: EvoTraveller
Ver el resultado
| Elitism | Rutas de élite | Aptitud final | Longitud final |
|---|---|---|---|
| 0,01 | 2 | 0,0317 | 31,50 |
| 0,05 | 6 | 0,0293 | 34,11 |
| 0,1 | 10 | 0,0317 | 31,50 |
Con los 30 mapas de 10 lugares de la sección 10.4, una ejecución por mapa, el número de mapas en que se encuentra la mejor ruta es:
| Mutation rate | Elitism 0,01 | Elitism 0,05 | Elitism 0,1 |
|---|---|---|---|
| 0,05 | 26 | 17 | 20 |
| 0,2 | 23 | 28 | 27 |
No hay un orden claro: con poca mutación gana la élite pequeña, y con más mutación, la intermedia. Las diferencias cambian de sentido al cambiar otro parámetro. Es lo esperable si la élite guarda casi siempre la misma ruta, la mejor, sea cual sea su tamaño.
Lo que sí importa es que haya élite. EvoTraveller no permite quitarla, pero podemos hacerlo cambiando una línea de su código, y repetirlo con 30 mapas de 15 lugares (semillas 1111 a 1140) y pm = 0,2:
| Reemplazo | Diferencia media sobre la mejor ruta | La curva de la mejor ruta empeora alguna vez | La ruta final es peor que la mejor encontrada |
|---|---|---|---|
| Con élite (6 rutas) | 6,1 % | 0 de 30 | 0 de 30 |
| Sin élite | 10,2 % | 28 de 30 | 13 de 30 |
Sin élite, la mejor ruta de una generación puede perderse: si muta o se cruza, su hijo puede ser peor. En 13 de las 30 ejecuciones, la ruta que entrega el algoritmo al final es peor que otra que había encontrado antes. Con pm = 0,05 la diferencia es mucho menor (13,7 % con élite y 13,5 % sin ella), porque las copias de la mejor ruta casi nunca mutan. La élite hace barato mutar mucho, como vimos en la sección 9.9.
Repite el reemplazo de la sección 10.3 sin élite. En lugar de B pasa una segunda copia, la del ganador de un cuarto torneo entre B y D, y no muta. a) ¿Cuál es la generación siguiente y su mejor ruta? b) Imagina ahora que, además, el Hijo 2 no hubiera mutado y el Hijo 1 hubiera salido peor que B. ¿Qué podría pasar con la mejor ruta?
Ver la solución
B gana el torneo contra D, así que la generación siguiente sería la misma: B (como copia), D, H1 y H2. Su mejor ruta es H2, de 24,29. Aquí la élite no cambia nada, porque el torneo ya ha elegido a B.
Si ningún hijo mejorase a B, la mejor ruta seguiría siendo B solo si B ganase algún torneo. Si B no saliera elegida, la mejor ruta de la generación siguiente sería peor que B, y la curva de la mejor aptitud bajaría. La élite garantiza que eso no pase.
10.6 Del ensayo al caso real BásicoB
Una empresa reparte cada semana desde su almacén a 14 clientes, cuyas posiciones cambian de una semana a otra. ¿Cómo elegimos los parámetros de EvoTraveller para calcular sus rutas?
Es un problema táctico (sección 9.6): se resuelve cada semana, interesa la calidad de la ruta y hay un tiempo limitado para calcularla. Supongamos que el tiempo da para unas 5000 evaluaciones de rutas por semana, las de los valores iniciales de EvoTraveller: 100 rutas en cada una de las 51 generaciones, de la 0 a la 50. Vamos a juntar todo lo que hemos visto en los capítulos 9 y este.
1. Casos parecidos al real. No conocemos los mapas de las semanas que vienen, pero sí cómo son: 15 lugares contando el almacén. Usaremos mapas de EvoTraveller de ese tamaño (sección 9.5).
2. Una medida. En cada mapa, cuánto más larga es la ruta del algoritmo que la mejor posible, en porcentaje. Aquí la mejor ruta la calcula un programa exacto; en un caso real se compararía con la mejor conocida.
3. Tres grupos de mapas. Ajustamos con 10 mapas (semillas 1111 a 1120). Con otros 20, los de validación (semillas 1121 a 1140), comparamos las configuraciones y elegimos una. Y guardamos 20 más, los de prueba (semillas 1141 a 1160), que solo usaremos al final, una vez, con la configuración elegida. Si eligiéramos y evaluáramos con los mismos mapas, el resultado sería demasiado optimista (sección 9.11). Por eso la cifra que importa es la de prueba: los mapas de ajuste y los de validación sirven para elegir.
4. Configuraciones candidatas. Con lo visto en este capítulo y en el anterior, probamos cuatro:
- A, los valores iniciales;
- B, con Mutation rate 0,2, para conservar más diversidad;
- C, como B pero con Tournament size 7;
- D, como B pero con Population size 50 y Generations 100: 50 rutas en cada una de 101 generaciones, unas 5000 evaluaciones, como las demás.
Datos. En EvoTraveller, pon Number of places 15 y prueba las configuraciones B y D con tres semillas: 1111, 1112 y 1117. B: valores iniciales con Mutation rate 0,2. D: lo mismo, con Population size 50 y Generations 100. Son seis ejecuciones. Lee en la curva Fitness la aptitud final, aproximada, y calcula la longitud como su inversa.
Predice. ¿Qué configuración da rutas más cortas?
Abrir y configurar: EvoTraveller
Ver el resultado
| Seed | Mejor ruta posible | B | D |
|---|---|---|---|
| 1111 | 37,04 | 38,46 (+3,8 %) | 40,03 (+8,1 %) |
| 1112 | 39,81 | 45,72 (+14,8 %) | 39,91 (+0,2 %) |
| 1117 | 37,00 | 40,16 (+8,6 %) | 41,02 (+10,9 %) |
| Media | +9,1 % | +6,4 % |
B gana en dos de los tres mapas, pero D tiene la media más baja, porque en la semilla 1112 B se queda muy lejos. Con tres mapas, la respuesta depende de qué mapas se miren. Hacen falta más.
Las aptitudes finales son 0,0260, 0,0219 y 0,0249 con B, y 0,0250, 0,0251 y 0,0244 con D.Con los 10 mapas de ajuste, una ejecución por mapa, el resultado es:
| Configuración | Diferencia media sobre la mejor ruta | Peor mapa | Mapas con la mejor ruta |
|---|---|---|---|
| A, valores iniciales | 13,3 % | 17,6 % | 0 de 10 |
| B, pm = 0,2 | 5,2 % | 14,8 % | 1 de 10 |
| C, pm = 0,2 y torneo de 7 | 4,7 % | 16,9 % | 2 de 10 |
| D, pm = 0,2, población 50 y 100 generaciones | 5,4 % | 27,3 % | 3 de 10 |
Con la tabla de los 10 mapas de ajuste, ¿qué configuración elegirías para la empresa? ¿Cuánto te fías de la diferencia entre B y C? Mapa a mapa, C mejora a B en 5 mapas, empeora en 4 y empata en 1.
Ver la solución
El paso de A a B es claro: la media baja de 13,3 % a 5,2 %, y B mejora a A en 9 de los 10 mapas. Entre B, C y D, la diferencia de medias es de menos de un punto, mientras que de un mapa a otro los resultados varían mucho más (el peor mapa de cada una queda entre el 15 % y el 27 %). Que C gane en 5 mapas y pierda en 4 es lo que se esperaría si fueran igual de buenas. Con estos datos, no sabemos si C es mejor que B. Elegir C solo porque tiene la media más baja sería fiarse del azar de diez ejecuciones. Lo comprobaremos con los mapas de validación.Comparamos las cuatro configuraciones con los 20 mapas de validación:
| Configuración | Diferencia media | Peor mapa | Mapas con la mejor ruta |
|---|---|---|---|
| A, valores iniciales | 13,9 % | 32,5 % | 0 de 20 |
| B, pm = 0,2 | 6,5 % | 16,2 % | 3 de 20 |
| C, pm = 0,2 y torneo de 7 | 8,2 % | 30,4 % | 2 de 20 |
| D, pm = 0,2, población 50 y 100 generaciones | 4,4 % | 14,6 % | 4 de 20 |
La mejora de A a B se mantiene en los mapas nuevos: de 13,9 % a 6,5 %. La pequeña ventaja de C sobre B, en cambio, ha desaparecido: con los mapas nuevos, C es peor que B en 12 de 20. Era azar. Y D, que en el ajuste parecía la peor de las tres por su peor mapa, queda ahora por delante. Su ventaja sobre B, 2,1 puntos de media, tampoco es mucho mayor que la variación entre mapas; harían falta más mapas para estar seguros.
Hay que decidir antes de mirar los mapas de prueba. Elegimos D, que tiene la menor diferencia media en validación y también el mejor peor mapa. Ahora, y solo ahora, la ejecutamos en los 20 mapas de prueba:
| Configuración D | Diferencia media | Peor mapa | Mapas con la mejor ruta |
|---|---|---|---|
| En los 20 mapas de validación | 4,4 % | 14,6 % | 4 de 20 |
| En los 20 mapas de prueba | 9,1 % | 25,4 % | 1 de 20 |
En los mapas de prueba, la diferencia media de D es el doble de la que prometía la validación. D no ha empeorado: la cifra de validación era optimista. Elegimos D precisamente porque le fue mejor que a las demás en esos 20 mapas, y parte de esa ventaja era suerte, como le pasó a C en el ajuste. Con una ejecución por mapa y tanta variación de un mapa a otro, 20 mapas no bastan para separar B, C y D.
¿Y si ahora probamos B con los mapas de prueba? Le va mejor: 5,0 % de media. Pero si cambiamos de elección por eso, los mapas de prueba habrán servido para elegir y pasarán a ser de validación, y ese 5,0 % será tan optimista como lo era el 4,4 % de D. Lo que sí nos dice es que entre B y D no hay una ganadora clara: en validación ganó D y en prueba, B. Para separarlas harían falta más mapas o varias ejecuciones por mapa, y después, otros mapas de prueba nuevos.
Para la empresa, la decisión razonable sigue siendo B o D, y no los valores iniciales, que quedan muy por detrás en el ajuste y en la validación. Hemos elegido D, y la prueba nos dice qué esperar de ella: rutas, en promedio, un 9 % más largas que la mejor posible, y en algún mapa, un 25 %. Si el tiempo lo permite, hay otra palanca: con pm = 0,2 y Generations 100, el doble de evaluaciones, la diferencia media en los mapas de validación baja al 4,6 % y el peor mapa queda en el 10,4 %. Antes de adoptarla, también habría que estimar su calidad con mapas de prueba nuevos. Comprar calidad con tiempo es una decisión del problema, no del algoritmo (sección 9.6).
10.7 EvoTraveller por dentro AvanzadoA
¿Qué hace exactamente EvoTraveller en cada generación, y en qué se diferencia de lo que hemos hecho a mano?
El código de EvoTraveller es público. Leído con atención, cada generación hace lo siguiente (véase también Santos et al., 2025, pp. 8–9):
- Ordena la población por aptitud, de mejor a peor.
- Élite. Calcula e = \max(1, \lfloor \text{Elitism} \times N \rfloor) y, si sale impar, le suma 1. Con N = 100, Elitism 0,01 da e = 2; 0,05 da 5, que pasa a 6; y 0,1 da 10. Las e primeras rutas pasan sin cambios. Como e es al menos 2, no se puede ejecutar EvoTraveller sin élite.
- Selección. Juega N torneos, cada uno con Tournament size individuos distintos de toda la población, élite incluida, y baraja a los ganadores.
- Copias. Los N - n_c - e primeros ganadores pasan como copias, que pueden mutar. Aquí n_c = \lfloor \text{Crossover} \times N \rfloor, que también se sube al par siguiente si es impar.
- Cruce. Los demás ganadores forman n_c/2 parejas, y todas se cruzan con el OX «Orden desde el inicio». Los dos cortes se sortean entre las posiciones, y el último gen nunca queda dentro del segmento.
- Mutación. Cada copia y cada hijo muta con probabilidad Mutation rate, intercambiando dos posiciones sorteadas. La élite no muta.
Hay tres diferencias con lo que hemos estudiado en otros capítulos:
- Crossover no es una probabilidad de cruce. En el capítulo 6, cada pareja se cruza con probabilidad Pc, y el número de hijos de cruce varía de una generación a otra. En EvoTraveller, Crossover es una fracción fija: con 0,6 y 100 individuos hay exactamente 60 hijos de cruce en cada generación. En promedio es lo mismo, pero sin variación.
- La mutación es por individuo, no por gen. Con pm = 0,2, un individuo cambia en promedio 2 \times 0{,}2 = 0{,}4 posiciones (sección 9.2).
- El problema y el algoritmo comparten la semilla. Seed fija a la vez las posiciones de los lugares y los sorteos del algoritmo. Por eso, para repetir con otro azar hay que cambiar de mapa, y cada mapa es una sola ejecución (sección 9.1).
Dos detalles más ayudan a leer la herramienta. Los lugares se sortean en la cuadrícula y nada impide que dos caigan en el mismo punto: entonces Best solution muestra un lugar menos. Pasa con frecuencia; con 15 lugares, en 18 de los 30 mapas de las semillas 1111 a 1140. Y el control Generation llega hasta Generations − 1, así que la última población no se puede ver.
Con Population size 100, Elitism 0,07 y Crossover 0,5, ¿cuántas rutas forman la élite, cuántas son copias y cuántas hijos de cruce? ¿Cuántas pueden mutar?
Ver la solución
Élite: \lfloor 0{,}07 \times 100 \rfloor = 7, que es impar, así que e = 8. Hijos de cruce: \lfloor 0{,}5 \times 100 \rfloor = 50, que es par: 25 parejas. Copias: 100 − 50 − 8 = 42. Pueden mutar las 42 copias y los 50 hijos, 92 rutas; con pm = 0,05, mutarán unas 4,6 por generación en promedio.10.8 Mejorar el algoritmo AvanzadoA
Esta sección requiere las secciones 6.10, 7.9 y 9.10.
En EvoTraveller solo podemos cambiar los parámetros. Si pudiéramos cambiar también los operadores, ¿cuáles cambiaríamos?
En la sección 9.10 vimos que, en el viajante, la longitud de una ruta depende de sus tramos, y que los operadores que los conservan funcionan mejor: la mutación por inversión rompe dos tramos y el intercambio, hasta cuatro; el cruce ERX conserva casi todos los tramos de los padres, y OX, menos. Lo comprobamos entonces con un algoritmo propio. Ahora lo hemos repetido con el propio código de EvoTraveller, cambiando solo el operador, con la configuración B de la sección 10.6 (pm = 0,2) y los 30 mapas de 15 lugares:
| Cruce | Mutación | Diferencia media sobre la mejor ruta | Peor mapa | Mapas con la mejor ruta |
|---|---|---|---|---|
| OX «Orden desde el inicio» | Intercambio | 7,1 % | 24,1 % | 4 de 30 |
| OX clásico | Intercambio | 7,2 % | 25,4 % | 7 de 30 |
| OX «Orden desde el inicio» | Inversión | 2,1 % | 10,9 % | 9 de 30 |
| ERX | Intercambio | 2,8 % | 23,4 % | 15 de 30 |
| ERX | Inversión | 1,1 % | 5,9 % | 15 de 30 |
La primera fila son los operadores de EvoTraveller. No coincide exactamente con la configuración B de la sección 10.6 (6,1 % en esos mismos 30 mapas) porque, para poder usar ERX, este programa trata como lugares distintos los que caen en el mismo punto (sección 10.7).
Cambiar la variante de OX apenas cambia la media: las dos conservan el orden relativo, no los tramos. Cambiar el intercambio por la inversión divide la diferencia media por más de tres, y ERX con inversión la deja en el 1,1 %, con el peor mapa en el 5,9 %. Con los operadores de EvoTraveller, ninguna configuración de la sección 10.6 baja tanto, ni siquiera la que usa el doble de generaciones (3,6 % en estos 30 mapas). Los parámetros se ajustan después de elegir unos operadores que conserven lo que importa del problema (sección 9.10).
En el ejercicio 10.3, la variante clásica de OX daba otros hijos. ¿Por qué, entonces, cambiar de variante no mejora la media en la tabla? ¿Qué tienen en común las dos variantes y qué les falta?
Ver la solución
Las dos variantes copian el segmento de un padre y colocan los demás lugares en el orden en que aparecen en el otro padre; solo cambia por dónde se empieza a leer. Las dos conservan el orden relativo, y ninguna se preocupa de qué lugares quedan juntos. En el viajante, la longitud depende de los tramos, es decir, de qué lugares son vecinos. Un hijo de OX conserva el orden, pero al encajar los lugares del otro padre crea tramos nuevos, casi siempre largos. ERX construye el hijo con los tramos de los padres, y la inversión rompe solo dos.10.9 Ampliaciones Para saber más+
Algoritmos híbridos. Los algoritmos genéticos exploran bien el espacio de búsqueda, pero refinan mal las soluciones que encuentran. Por eso los más eficaces suelen combinarse con una búsqueda local, que mejora cada hijo antes de evaluarlo. Talbi llama a estos híbridos low-level teamwork hybrids e incluye entre ellos los algoritmos meméticos (Talbi, 2009, p. 388). En el viajante, una búsqueda local clásica es la de 2-opt, que invierte tramos de la ruta mientras alguna inversión la acorte (Croes, 1958; Talbi, 2009, p. 92). Su movimiento es el de la mutación por inversión (sección 7.10).
Sembrar la población. Se puede empezar con rutas construidas con una heurística, como la del vecino más cercano, en lugar de rutas al azar. No siempre ayuda: la población puede llenarse enseguida de copias de esas rutas y converger prematuramente (sección 4.4). Talbi recoge un caso del viajante en que una búsqueda local da peores resultados partiendo de las rutas de una heurística voraz que partiendo de rutas al azar (Talbi, 2009, p. 102).
El viajante real. El viajante de este capítulo es el más sencillo: distancias en línea recta, iguales a la ida y a la vuelta, y un solo vehículo. Los problemas reales añaden ventanas de tiempo, requisitos concretos de las rutas o varios vehículos, como en el problema de rutas de vehículos (Talbi, 2009, p. 102). Los algoritmos genéticos pueden adaptarse a restricciones como estas (Santos et al., 2025, p. 8), a costa de diseñar con cuidado la representación, la aptitud y el tratamiento de las rutas no factibles (sección 4.7).
EvoTraveller. Santos et al. (2025) describen la herramienta: sus parámetros, las tres gráficas y el propósito de cada una. Destacan la gráfica de la población como su rasgo más característico, porque permite ver cómo los parámetros afectan a la convergencia y a la diversidad de las rutas, como hemos hecho en las secciones 10.1 y 10.4.
Resumen
- En el problema del viajante, una ruta se representa con una permutación de los lugares y el origen se añade al principio y al final; la aptitud de EvoTraveller es la inversa de la longitud. Con n lugares hay (n-1)!/2 rutas distintas, demasiadas para revisarlas salvo en mapas pequeños.
- Una generación de EvoTraveller tiene tres partes: la élite, que pasa sin cambios; las copias de los individuos seleccionados por torneo; y los hijos de parejas cruzadas con OX. Las copias y los hijos pueden mutar por intercambio.
- Durante una ejecución, la mejor aptitud no baja gracias a la élite, y la población se llena de copias de la mejor ruta. Cuanto mayor es el torneo, antes se pierde la diversidad y más a menudo se atasca el algoritmo.
- Importa que haya élite, pero no tanto su tamaño, porque las posiciones de la élite suelen estar ocupadas por copias de la misma ruta.
- Los parámetros se eligen con mapas parecidos al caso real: unos para ajustar, otros de validación para elegir y otros de prueba, que solo se usan al final con la configuración elegida. Una ventaja pequeña en unos mapas puede desaparecer en otros, y la cifra de la ganadora en los mapas con que se eligió es optimista.