مستندات / تاریخچه

تاریخی: پایان نامه (۲۰۲۶)

برنامه نویسی ژنتیکی در برنامه ریزی فصل بیسبال. مسئله امکان سنجی و بهینه سازی. پایان نامه مهندسی کامپیوتر، ITAM. مشاور: دکتر آندرس گومز د سیلوا گارزا. تأیید شده در ۲۳ ژوئیه ۲۰۲۶.

مشکل

MLB در حدود ۱۸۰ روز، ۲۴۳۰ بازی برای ۳۰ تیم برنامه ریزی می کند. هر تیم بین شهرها سفر می کند و فاصله بین تیم ها بسیار متفاوت است. در سال ۲۰۱۶، سیاتل ۷۶۶۸۳ کیلومتر و شیکاگو کابز ۳۹۰۱۵ کیلومتر سفر کردند.

یافتن برنامه ای با کمترین مسافت کل به عنوان مشکل حمل و نقل تورنمنت (PTT) شناخته می شود. این یک مشکل سخت NP است: تعداد برنامه های ممکن آنقدر سریع افزایش می یابد که نمی توانید همه را بررسی کنید.

روش

برنامه ریزی ژنتیکی (PG) که توسط جان کوزا در سال ۱۹۹۲ پیشنهاد شد، تکامل را تقلید می کند. این روش جمعیتی از راه حل ها ایجاد می کند، بهترین ها را می گیرد و آن ها را ترکیب و اصلاح می کند تا نسل جدیدی بسازد.

نمایش: هر تقویم یک درخت است. گره های آن عملیاتی مانند crear_juego (تاریخ، تیم میزبان، تیم مهمان) و obtener_calendario، هستند که دو فهرست بازی را به هم متصل می کنند.
قابلیت اجرا (C1): هر تیم باید دقیقا به تعداد بازی هایی که تورنمنت نیاز دارد انجام دهد. مقدار ۰ به معنای معتبر بودن برنامه است.
فاصله (C2): مجموع انتقال ها که با فرمول هاورسین روی مختصات هر ورزشگاه محاسبه می شود.
نرم افزار: سه ماژول (برنامه ریز، ماشین حساب و برنامه ژنتیکی) با کتابخانه DEAP، جدا از یک برنامه وب در جنگو.

نتایج

۳۰ تیم، ۱۶۳ بازی برای هر تیم، سری ۵ بازی و ۲۰ نسل را امتحان کن.

مقایسه جستجوی تصادفی و برنامه ریزی ژنتیکی
روش	مشکل. در عبور	احتمالا. از جهش	امکان سنجی (C1)	کل فاصله (C2)	زمان
جستجوی تصادفی	0.0	0.0	۰ (معتبر)	2,663,470.70 km فاصله کوتاه تر	200.25 s
برنامه ریزی ژنتیکی	0.8	0.2	۰ (معتبر)	3,182,738.33 km	3,337.81 s

یافته اصلی

برنامه ریزی ژنتیکی از جستجوی تصادفی بهتر عمل نکرد. این روش فاصله ۱۹.۵٪ بیشتر را نشان می داد و تقریبا ۱۷ برابر بیشتر طول می کشید. بهترین تقویم همیشه از نسل اولیه می آمد که تصادفی است.

این پایان نامه علل زیر را شناسایی کرد:

عملگرهای کراس اور و جهش عمومی بدون دانستن مشکل گره ها را تغییر می دهند. آن ها تقریبا همیشه تقویم های نامعتبر تولید می کنند.
تابع شایستگی وزن بسیار بیشتری به قابلیت زنده ماندن نسبت به فاصله می دهد. یک کودک نامعتبر همیشه به یک والد معتبر می بازد.
الگوریتم به زودی به یک بهینه محلی همگرا شد و تنها راه حل های اولیه را حفظ کرد.

نتیجه منفی نیز نتیجه است. این نشان می دهد که نمایش و عملگرها به اندازه الگوریتم اهمیت دارند.

فعالیت های آینده

پایان نامه عملگرهای زمینه ای را پیشنهاد کرد: به جای تغییر تصادفی گره ها، کل سری ها یا بلوک هایی را که تقویم را معتبر نگه می دارند، جابجا کنید. او همچنین به محاسبات کوانتومی برای بررسی چندین پیکربندی به طور همزمان اشاره کرد.

ببینید بعد از پایان نامه چه کاری انجام شد

جدول زمانی

مه ۲۰۲۶ · نسخه پیش رسمی سند پایان نامه.
۲۳ ژوئیه ۲۰۲۶ · دفاع در مکزیکوسیتی. پایان نامه تأیید شد.

مواد و ارجاعات

سند پایان نامه، نسخه پیش رسمی (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.