دستاویزات / تاریخ

تاریخی: تھیسس (2026)

بیس بال سیزن کی منصوبہ بندی میں جینیاتی پروگرامنگ۔ فزیبلٹی اور آپٹیمائزیشن کا مسئلہ۔ کمپیوٹر انجینئرنگ تھیسس، ITAM۔ مشیر: ڈاکٹر آندریس گومیز ڈی سلوا گارزا۔ 23 جولائی 2026 کو منظور شدہ۔

مسئلہ

ایم ایل بی تقریبا 180 دنوں میں 30 ٹیموں کے لیے 2,430 میچز شیڈول کرتا ہے۔ ہر ٹیم شہروں کے درمیان سفر کرتی ہے، اور فاصلہ ٹیم سے ٹیم میں بہت مختلف ہوتا ہے۔ 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.