Документация / История

Историческая: диссертация (2026)

Генетическое программирование в планировании бейсбольного сезона. Задача осуществимости и оптимизации. Диссертация по компьютерной инженерии, ITAM. Научный руководитель: доктор Андрес Гомес де Сильва Гарса. Утверждено 23 июля 2026 года.

Проблема

MLB запланировала 2 430 игр для 30 команд примерно за 180 дней. Каждая команда путешествует между городами, и расстояние сильно варьируется от команды к команде. В 2016 году Сиэтл проехал 76 683 км, а Чикаго Кабс — 39 015 км.

Поиск расписания с наименьшей общей дистанцией называется задачей Tournament Transportation Problem (PTT). Это сложная задача, связанная с NP: количество возможных расписаний растёт так быстро, что невозможно проверить их все.

Метод

Генетическое программирование (PG), предложенное Джоном Козой в 1992 году, имитирует эволюцию. Оно создаёт популяцию решений, берёт лучшие из них и объединяет их, чтобы создать новое поколение.

Представление: Каждый календарь представляет собой дерево. Его узлы — это операции, такие crear_juego как (дата, домашняя команда, гостевая команда) и obtener_calendario, которые объединяют два списка игр.
Жизнеспособность (C1): Каждая команда должна сыграть ровно столько матчей, сколько требует турнир. Значение 0 означает, что расписание действительно.
Расстояние (C2): сумма трансферов, вычисляемая по формуле Хаверсина на координатах каждого стадиона.
Программное обеспечение: три модуля (планер, калькулятор и генетическая программа) с библиотекой DEAP, отдельно от веб-приложения в Django.

Результаты

Попробуйте 30 команд, по 163 игры на команду, 5-игровые серии и 20 поколений.

Сравнение случайного поиска и генетического программирования
Метод	Наверное. пересечения	Вероятно. мутации	Осуществимость (C1)	Общее расстояние (C2)	Время
Случайный поиск	0.0	0.0	0 (действительно)	2,663,470.70 km Короткое расстояние	200.25 s
Генетическое программирование	0.8	0.2	0 (действительно)	3,182,738.33 km	3,337.81 s

Основное открытие

Генетическое программирование не превосходило случайный поиск. Оно давало на 19,5% большее расстояние и занимало почти в 17 раз больше времени. Лучший календарь всегда исходил из начального поколения, которое происходит случайно.

В диссертации были выявлены следующие причины:

Общие операторы кроссовера и мутаций меняют узлы, не зная проблемы. Они почти всегда создают недопустимые календари.
Функция приспособленности придаёт гораздо больше значения жизнеспособности, чем расстоянию. Невалидный ребёнок всегда проигрывает действительному родителю.
Алгоритм вскоре сблизился к локальному оптимуму и сохранил только исходные решения.

Отрицательный результат также является результатом. Он показывает, что представление и операторы имеют такое же значение, как и алгоритм.

Будущая работа

В диссертации предлагались контекстные операторы: вместо случайной смены узлов можно поменять местами целые серии или блоки, которые сохраняют календарь действительным. Он также упомянул квантовые вычисления для изучения множества конфигураций одновременно.

Посмотрите, что было сделано после диссертации

Хронология

Май 2026 · Предофициальная версия дипломного документа.
23 июля 2026 года · Оборона в Мехико. Диссертация одобрена.

Материалы и цитирование

Диссертация, предофициальная версия (PDF, 4.8 MB, на испанском языке)
Представление защиты (PDF, 2.9 MB, на испанском языке)

Цитата в формате 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.