Un Algoritmo Genético para generar el Sorteo de Grupos de la Copa Mundial de la FIFA

Contenido

• El sorteo de grupos de la Copa Mundial de la FIFA 2026
  • Solución factible
  • Combinaciones posibles
  • Restricciones del sorteo
• ¿Qué es un Algoritmo Genético?
  • Algoritmo Genético básico
• Población inicial
  • Estructura del individuo
• Función de costo
• Ciclo de vida del Algoritmo Genético
• Operadores Genéticos
  • Selección
  • Cruce
  • Mutación
  • Reemplazo
• Criterio de terminación
• Resultados

El sorteo de grupos de la Copa Mundial de la FIFA 2026

Fig: 1. Itinerario de las rondas eliminatorias del mundial según la FIFA. Esta configuración da lugar a la restricción de no enfrentamientos entre España y Argentina, o entre Francia e Inglaterra antes de la final, lo que afecta su asignación de grupo en el sorteo.

Solución factible

Combinaciones posibles

Fig: 2. Orden de los equipos en los bombos. Los equipos anfitriones no participan del sorteo, al tener ya asignados de antemano sus respectivos grupos.

• Bombo 1: $9!$,
• Bombos 2, 3, y 4: $12!$
• Esto es en total: $9! \times 12! \times 12! \times12! = 3.9881 \times 10^{31}$ combinaciones posibles.

¿Qué tan grande es este número? 39, 881, 724, 135, 495, 319, 399, 956, 480, 000, 000 combinaciones posibles de organizar los equipos en los grupos. Ignorando las restricciones.

Para tener una idea de la magnitud de este número, si pudiéramos evaluar cada sorteo generado por nuestro algoritmo de fuerza bruta en 0.05 segundos, evaluar todas las soluciones posibles tardaría $6.3 \times 10^{22}$ años. Si el algoritmo hubiera iniciado en el Big Bang, aún no habría terminado, de hecho llevaría el 0.00000000002% del tiempo total.

Restricciones del sorteo

• Anfitriones: México se le asignará la posición A1 (primero del grupo A), a Canadá, la posición B1, y a Estados Unidos, la posición D1.
• Bombo 1: Las otras nueve selecciones del bombo 1 se identificarán mediante nueve bolas del mismo color y se asignarán automáticamente a la posición 1 del grupo en el que resulten encuadradas.
• Distribución uniforme: En cada grupo debe haber un equipo de cada bombo.
• Confederaciones por grupo: Ningún grupo puede tener más de una selección de la misma confederación, excepto las de la UEFA, que pueden tener hasta dos selecciones en un mismo grupo.
• Top 4 del ranking: Por último, las selecciones de España y Argentina por un lado, y Francia e Inglaterra por otro, no podrán enfrentarse hasta la final, por ser los cuatro primeros del ranking masculino de la FIFA a la fecha^[2]. Esto restringe que se agreguen a cualquier grupo.

Fig: 3. Distribución de los brackets o itinerarios de los equipos. Los equipos de un bracket que clasifiquen a la siguiente ronda competirán contra los equipos del otro bracket. España vs Argentina, ni Inglaterra vs Francia podrán enfrentarse hasta la final del mundial. Esto bajo el supuesto que cada una de esas selecciones clasifique de primera en su grupo.

¿Qué es un Algoritmo Genético?

Algoritmo Genético básico

• Tamaño de la población: Cuántos individuos (soluciones candidatas) van a conformar la población en cada generación.
• Número de generaciones: Cuántas veces se va a repetir el ciclo de vida del algoritmo.
• Probabilidad de cruce. Se establece en un 80%, ya que este valor suele ser efectivo para explorar el espacio de búsqueda.
• Probabilidad de mutación. Establecida en un 20%, ya que este valor suele ser efectivo para mantener la diversidad genética sin alterar demasiado las soluciones existentes.

python
1POBLACION_TAM = 10 # Tamaño de la población
2GENERACIONES = 1000 # Número de generaciones
3PROB_CROSSOVER = 0.8  # 80% probabilidad de cruce
4PROB_MUTACION = 0.2  # 20% probabilidad de mutación

Población inicial

Debemos encontrar una forma de representarlo en algoritmo y crearlo (codificación).

python
1def crear_individuo(lista_equipos):
2    # Crear un individuo (sorteo) válido inicial
3    bombos = {1: [], 2: [], 3: [], 4: []}
4    # Distribuir equipos por bombo
5    for eq in lista_equipos:
6        bombos[eq.bombo].append(eq)
7    # Asignar equipos a grupos
8    grupos = [[] for _ in range(12)]
9    for b in range(1, 5):
10        equipos = bombos[b]
11        # Mezclar para aleatoriedad
12        random.shuffle(equipos)
13        pendientes = []
14        for eq in equipos:
15            if eq.grupo_fijo:
16                # Asignar al grupo fijo y saltar (convierte letra del grupo a índice)
17                idx = ord(eq.grupo_fijo) - 65
18                grupos[idx].append(eq)
19            else:
20                pendientes.append(eq)
21        idx_p = 0
22        # Asignar restantes de este bombo
23        for g_idx in range(12):
24            if len(grupos[g_idx]) < b:
25                grupos[g_idx].append(pendientes[idx_p])
26                idx_p += 1
27    return grupos

Estructura del individuo

Fig: 4. Representación de un individuo como un sorteo completo de 12 grupos y 48 equipos. Se observa que este individuo no cumple con algunas restricciones, por ejemplo el grupo que comparten Catar y Jordania. Estas dos selecciones pertenecen a la misma confederación y no está permitido que tengan el mismo grupo.

python
1class Equipo:
2    def __init__():
3        self.nombre = nombre
4        self.confederacion = confederacion  # String simple
5        self.bombo = bombo
6        self.grupo_fijo = grupo_fijo
7        self.ranking_top = ranking_top  # 1, 2, 3, 4 o None
8
9    def __repr__(self):
10        # Muestra info útil al imprimir
11        r =  if self.ranking_top else ""
12        f =  if self.grupo_fijo else ""
13        return

python
1Equipo("España", ["UEFA"], bombo=1, ranking_top=1)
2Equipo("Argentina", ["CONMEBOL"], bombo=1, ranking_top=2)

python
1Equipo("México", ["CONCACAF"], bombo=1, grupo_fijo="A")
2Equipo("Canadá", ["CONCACAF"], bombo=1, grupo_fijo="B")

python
1Equipo("Alemania", ["UEFA"], bombo=1)
2Equipo("Ecuador", ["CONMEBOL"], bombo=2)
3Equipo("Panamá", ["CONCACAF"], bombo=3)
4# Y asi hasta completar el resto...

Función de costo

Fig: 5. Evaluación de dos individuos. El individuo A tiene un fitness de 900, ya que viola la repetición de confederaciones en los grupos C,D,E. Además de no separar los itinerarios de España y Argentina.

• Confederaciones: Ningún grupo puede tener más de un equipo de la misma confederación (salvo Europa, que permite dos).

python
1for j in range(len(grupo)):
2            for k in range(j + 1, len(grupo)):
3                equipo_a = grupo[j]
4                equipo_b = grupo[k]
5
6                # Intersección de conjuntos:
7                set_a = set(equipo_a.confederacion)
8                set_b = set(equipo_b.confederacion)
9                interseccion = set_a.intersection(set_b)
10
11                # Si hay intersección y NO es UEFA (porque UEFA permite 2), penalizamos
12                conflicto_real = [c for c in interseccion if c != "UEFA"]
13
14                if conflicto_real:
15                    penalizacion += PENALTY_CONF_LIMIT

• Itinerarios: Los cabezas de serie del Top 4 deben estar distribuidos en llaves opuestas para no enfrentarse antes de la semifinal. Si el Top 1 y Top 2 caen en el mismo grupo, aplicamos una penalización masiva (+500).

python
1# Creamos un diccionario para saber dónde están los Top 4
2  ubicacion_tops = {}
3    # Para cada grupo obtenemos esa ubicación:
4    for equipo in grupo:
5            if equipo.ranking_top:
6                ubicacion_tops[equipo.ranking_top] = i
7
8    # Regla: Top 1 y Top 2 deben ir por lados opuestos del itinerario
9    if 1 in ubicacion_tops and 2 in ubicacion_tops:
10        it_1 = obtener_itinerario(ubicacion_tops[1])
11        it_2 = obtener_itinerario(ubicacion_tops[2])
12    # Se penaliza si se encuentran en el mismo lado de la llave
13    if it_1 == it_2:
14        penalizacion += PENALTY_ITINERARY

python
1def calcular_fitness(sorteo):
2    """
3    Calcula la penalización total de un sorteo (cromosoma).
4    0 = Sorteo válido.
5    return: penalizacion
6    """
7    penalizacion = 0
8
9    # Constantes de Penalización (Pesos)
10    PENALTY_CONF_LIMIT = 1000  # Conflicto de confederación (Grave)
11    PENALTY_UEFA_LIMIT = 500  # Más de 2 europeos
12    PENALTY_ITINERARY = 500  # Top seeds chocando antes de la final
13
14    # Rastrear dónde cayeron los Top seeds {ranking: indice_grupo}
15    ubicacion_tops = {}
16
17    # --- 1. Ciclo por Grupos ---
18    for i, grupo in enumerate(sorteo):
19
20        # A. Revisar límite de UEFA (Máximo 2)
21        # Contamos cuántos equipos tienen 'UEFA' en su lista de confederaciones
22        uefa_count = sum(1 for equipo in grupo if ["UEFA"] in equipo.confederacion)
23
24        if uefa_count > 2:
25            # Penalizamos para corregirlo
26            penalizacion += PENALTY_UEFA_LIMIT * (uefa_count - 2)
27
28        # B. Revisar choques de Confederaciones (NO UEFA)
29        # Usamos doble for para comparar todos contra todos en el grupo
30        for j in range(len(grupo)):
31            for k in range(j + 1, len(grupo)):
32                equipo_a = grupo[j]
33                equipo_b = grupo[k]
34
35                # Intersección de conjuntos:
36                # Si Equipo A es ['CONMEBOL'] y Equipo B (Repesca) es ['CONMEBOL', 'AFC']
37                # La intersección es {'CONMEBOL'} -> ¡Conflicto!
38                set_a = set(equipo_a.confederacion)
39                set_b = set(equipo_b.confederacion)
40                interseccion = set_a.intersection(set_b)
41
42                # Si hay intersección y NO es UEFA (porque UEFA permite 2), penalizamos
43                # Nota: Si ambos son UEFA, 'UEFA' estará en la intersección,
44                # pero eso ya lo controlamos arriba con uefa_count.
45                conflicto_real = [c for c in interseccion if c != "UEFA"]
46
47                if conflicto_real:
48                    penalizacion += PENALTY_CONF_LIMIT
49
50        # C. Guardar ubicación de Tops para la fase 2
51        for equipo in grupo:
52            if equipo.ranking_top:
53                ubicacion_tops[equipo.ranking_top] = i
54
55    # --- 2. Penalizaciones de Itinerario (Bracket) ---
56
57    # Regla: Top 1 y Top 2 deben ir por lados opuestos del itinerario
58    if 1 in ubicacion_tops and 2 in ubicacion_tops:
59        it_1 = obtener_itinerario(ubicacion_tops[1])
60        it_2 = obtener_itinerario(ubicacion_tops[2])
61
62        if it_1 == it_2:
63            penalizacion += PENALTY_ITINERARY
64
65    # Regla: Top 3 y Top 4 deben ir por lados opuestos del itinerario
66    if 3 in ubicacion_tops and 4 in ubicacion_tops:
67        it_3 = obtener_itinerario(ubicacion_tops[3])
68        it_4 = obtener_itinerario(ubicacion_tops[4])
69
70        if it_3 == it_4:
71            penalizacion += PENALTY_ITINERARY
72
73    return penalizacion

Ciclo de vida del Algoritmo Genético

python
1def ejecutar_ga_completo():
2    # --- CONFIGURACIÓN ---
3    POBLACION_TAM = 10
4    GENERACIONES = 1000
5    PROB_CROSSOVER = 0.8  # 80% probabilidad de cruce
6    PROB_MUTACION = 0.2  # 20% probabilidad de mutación
7    K_TORNEO = 2  # Tamaño del torneo para selección
8
9    datos = generar_datos_usuario()
10    poblacion = [crear_individuo(datos) for _ in range(POBLACION_TAM)]
11
12    print()
13
14    for gen in range(GENERACIONES):
15        # Evaluar Fitness
16        # Guardamos (score, individuo)
17        evaluados = [(calcular_fitness(ind), ind) for ind in poblacion]
18        evaluados.sort(key=lambda x: x[0])
19
20        best_score = evaluados[0][0]
21        # Monitorización
22        if gen % 100 == 0 or best_score == 0:
23            print()
24
25        if best_score == 0:
26            print()
27            return evaluados[0][1]
28
29        # Selección (Torneo simple)
30        nueva_poblacion = []
31
32        while len(nueva_poblacion) < POBLACION_TAM:
33            
34            # OPCIÓN A: TORNEO
35            # padre1 = seleccion_torneo(evaluados, k=K_TORNEO)
36            # padre2 = seleccion_torneo(evaluados, k=K_TORNEO)
37
38            # OPCIÓN B: RULETA
39            padre1 = seleccion_ruleta(evaluados)
40            padre2 = seleccion_ruleta(evaluados)
41
42            # Crossover sujeto a probabilidad (0.8)
43            if random.random() < PROB_CROSSOVER:
44                hijo1, hijo2 = cruzar(padre1, padre2)
45            else:
46                hijo1, hijo2 = copy.deepcopy(padre1), copy.deepcopy(padre2)
47            # Mutación sujeta a probabilidad (0.2)
48            hijo1 = mutar(hijo1, PROB_MUTACION)
49            hijo2 = mutar(hijo2, PROB_MUTACION)
50
51            nueva_poblacion.append(hijo1)
52            if len(nueva_poblacion) < POBLACION_TAM:
53                nueva_poblacion.append(hijo2)
54        poblacion = nueva_poblacion
55
56    print("⚠️ Límite alcanzado. Devolviendo mejor aproximación.")
57    return evaluados[0][1]

Operadores Genéticos

Selección

python
1def seleccion_ruleta(evaluados):
2    """
3    Input: Lista de tuplas (fitness, individuo)
4    Selección proporcional al fitness (Ruleta).
5    Como buscamos MINIMIZAR el costo, invertimos el valor.
6    Fitness 0 -> Peso muy alto. Fitness 500 -> Peso bajo.
7    """
8    individuos = [item[1] for item in evaluados]
9    costos = [item[0] for item in evaluados]
10
11    # Invertimos los costos para obtener pesos (Mayor peso = Mayor probabilidad)
12    pesos = [1.0 / (1.0 + c) for c in costos]
13
14    # La función choices de 3 argumentos (población, pesos, cantidad)
15    seleccionado = random.choices(population=individuos, weights=pesos, k=1)[0]
16
17    return seleccionado

Cruce

Fig: 6. Ejemplo del operador de cruce. En la imagen vemos que el Padre A dona todos los equipos que pertenecen a los bombos 1 y 4 al hijo A, y los equipos del bombo 2 y 3 al hijo B.

El cruce que se utiliza aquí toma dos padres y crea dos hijos.

• Lanza moneda: ¿de qué padre heredar este bombo?
• Hijo1 hereda bombo completo del padre elegido
• Hijo2 hereda bombo completo del otro padre

python
1def cruzar(padre1, padre2):
2    """
3    Operador de Cruce Estratificado (Uniform Crossover por Bombos).
4    El hijo hereda la configuración entera de un bombo de uno de los padres.
5    """
6    # Hijos vacíos
7    hijo1 = [[] for _ in range(12)]
8    hijo2 = [[] for _ in range(12)]
9    # Recorremos cada nivel de Bombo (0 a 3)
10    for bombo_idx in range(4):
11        # Decisión aleatoria: ¿Quién dona este bombo?
12        if random.random() < 0.5:
13            # Caso A: Hijo 1 hereda de Padre 1, Hijo 2 hereda de Padre 2
14            donante_1 = padre1
15            donante_2 = padre2
16        else:
17            # Caso B: Cruzado
18            donante_1 = padre2
19            donante_2 = padre1
20
21        # Copiamos la fila entera de ese bombo a los hijos
22        for g_idx in range(12):
23            equipo_p1 = donante_1[g_idx][bombo_idx]
24            equipo_p2 = donante_2[g_idx][bombo_idx]
25
26            hijo1[g_idx].append(equipo_p1)
27            hijo2[g_idx].append(equipo_p2)
28    return hijo1, hijo2

Mutación

Fig: 7. Ejemplo del operador de mutación.

• Elige 2 grupos al azar
• Elige un bombo al azar (1, 2, 3, o 4)
• Intercambia los equipos de ese bombo entre los 2 grupos
• Solo si ninguno tiene grupo fijo

python
1def mutar(individuo, prob_mutacion):
2    """
3    Intenta mutar con probabilidad 'prob_mutacion'.
4    """
5    if random.random() > prob_mutacion:
6        return individuo  # No muta
7
8    # Si muta, hacemos el intercambio
9    nuevo = copy.deepcopy(individuo)
10    idx_g1, idx_g2 = random.sample(range(12), 2)
11    bombo_idx = random.randint(0, 3)
12
13    e1 = nuevo[idx_g1][bombo_idx]
14    e2 = nuevo[idx_g2][bombo_idx]
15
16    if not e1.grupo_fijo and not e2.grupo_fijo:
17        nuevo[idx_g1][bombo_idx], nuevo[idx_g2][bombo_idx] = (
18            nuevo[idx_g2][bombo_idx],
19            nuevo[idx_g1][bombo_idx],
20        )
21
22    return nuevo

Reemplazo

Criterio de terminación

• Si encuentra un sorteo con $\text{penalización} = 0 \Rightarrow \text{Éxito}$
• Si llega a generación $1000 \Rightarrow$ devuelve el mejor encontrado.

Resultados