Документація / Історія

Історичне: дисертація (2026)

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

Проблема

MLB планує 2 430 ігор для 30 команд приблизно за 180 днів. Кожна команда подорожує між містами, і відстань значно відрізняється від команди до команди. У 2016 році Сіетл подолав 76 683 км, а Чикаго Кабс — 39 015 км.

Пошук розкладу з найменшою загальною відстанню називається Турнірною транспортною задачею (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.