Documentation / Histoire
Historique : la thèse (2026)
Programmation génétique dans la planification de saisons de baseball. Problème de faisabilité et d’optimisation. Thèse en génie informatique, ITAM. Directeur : Dr Andrés Gómez de Silva Garza. Approuvé le 23 juillet 2026.
Le problème
La MLB programme 2 430 matchs pour 30 équipes en environ 180 jours. Chaque équipe voyage entre les villes, et la distance varie considérablement d’une équipe à l’autre. En 2016, Seattle a parcouru 76 683 km, et les Chicago Cubs 39 015 km.
Trouver le planning avec la distance totale la plus basse est connu sous le nom de Problème de Transport du Tournoi (PTT). C’est un problème NP-difficile : le nombre d’emplois possibles augmente si vite qu’on ne peut pas tous les consulter.
La méthode
La programmation génétique (PG), proposée par John Koza en 1992, imite l’évolution. Elle crée une population de solutions, prend les meilleures, les combine et les modifie pour former une nouvelle génération.
- Représentation : Chaque calendrier est un arbre. Ses nœuds sont des opérations telles que
crear_juego(date, équipe à domicile, équipe visite) etobtener_calendario, qui relie deux listes de matchs. - Viabilité (C1) : Chaque équipe doit jouer exactement le nombre de matchs exigé par le tournoi. Une valeur de 0 signifie que le calendrier est valide.
- Distance (C2) : la somme des transferts, calculée selon la formule de Haversine sur les coordonnées de chaque stade.
- Logiciel : trois modules (planificateur, calculatrice et programme génétique) avec la bibliothèque DEAP, séparés d’une application web dans Django.
Les résultats
Essayez 30 équipes, 163 matchs par équipe, séries de 5 matchs et 20 générations.
| Méthode | Probablement. de traverser | Probablement. de mutation | Faisabilité (C1) | Distance totale (C2) | Temps |
|---|---|---|---|---|---|
| Recherche aléatoire | 0.0 | 0.0 | 0 (valide) | 2,663,470.70 km Distance plus courte | 200.25 s |
| Programmation génétique | 0.8 | 0.2 | 0 (valide) | 3,182,738.33 km | 3,337.81 s |
La principale découverte
La programmation génétique n’a pas surpassé la recherche aléatoire. Elle donnait une distance 19,5 % plus longue et prenait presque 17 fois plus de temps. Le meilleur calendrier venait toujours de la génération initiale, qui est aléatoire.
La thèse identifiait les causes suivantes :
- Les opérateurs génériques de crossover et de mutation changent de nœud sans connaître le problème. Ils produisent presque toujours des calendriers invalides.
- La fonction d’aptitude accorde beaucoup plus d’importance à la viabilité qu’à la distance. Un enfant invalide perd toujours face à un parent valide.
- L’algorithme convergea rapidement vers un optimum local et ne conserva que les solutions initiales.
Un résultat négatif est aussi un résultat. Cela montre que la représentation et les opérateurs comptent autant que l’algorithme.
Travaux futurs
La thèse proposait des opérateurs contextuels : au lieu de changer de nœud de façon aléatoire, échanger des séries entières ou des blocs qui maintiennent le calendrier valide. Il a également mentionné l’informatique quantique pour explorer de nombreuses configurations à la fois.
Chronologie
- · Version pré-officielle du document de thèse.
- · Défense à Mexico. Thèse approuvée.
Documents et citation
- Document de thèse, version pré-officielle (PDF, 4.8 MB, en espagnol)
- Présentation de la défense (PDF, 2.9 MB, en espagnol)
Citation au format APA :
Brenes Valencia, L. P. (2026). Programación genética en la planificación de temporadas de béisbol (Tesis de Ingeniería en Computación). Instituto Tecnológico Autónomo de México (ITAM), Ciudad de México, México.