ডকুমেন্টেশন / ইতিহাস
ঐতিহাসিক: থিসিস (2026)
বেসবল মরসুম পরিকল্পনায় জেনেটিক প্রোগ্রামিং। সম্ভাব্যতা এবং অপ্টিমাইজেশান সমস্যা। কম্পিউটার ইঞ্জিনিয়ারিং থিসিস, আইটিএএম। উপদেষ্টা: ডঃ আন্দ্রেস গোমেজ ডি সিলভা গার্জা। 23 জুলাই, 2026 এ অনুমোদিত।
সমস্যা
এমএলবি প্রায় 180 দিনের মধ্যে 30 টি দলের জন্য 2,430 টি গেম নির্ধারণ করে। প্রতিটি দল শহরগুলির মধ্যে ভ্রমণ করে এবং দূরত্ব দল থেকে দলে ব্যাপকভাবে পরিবর্তিত হয়। 2016 সালে, সিয়াটল 76,683 কিলোমিটার ভ্রমণ করেছিল এবং শিকাগো কাবস 39,015 কিলোমিটার ভ্রমণ করেছিল।
সর্বনিম্ন মোট দূরত্বের সাথে সময়সূচী সন্ধান করা টুর্নামেন্ট ট্রান্সপোর্টেশন সমস্যা (পিটিটি) হিসাবে পরিচিত। এটি একটি এনপি-হার্ড সমস্যা: সম্ভাব্য সময়সূচীর সংখ্যা এত দ্রুত বৃদ্ধি পায় যে আপনি সেগুলি পরীক্ষা করতে পারবেন না।
পদ্ধতি
1992 সালে জন কোজা দ্বারা প্রস্তাবিত জেনেটিক প্রোগ্রামিং (পিজি) বিবর্তনকে অনুকরণ করে। এটি সমাধানের একটি জনসংখ্যা তৈরি করে, সেরাগুলি গ্রহণ করে এবং একটি নতুন প্রজন্ম গঠনের জন্য তাদের একত্রিত করে এবং সংশোধন করে।
- উপস্থাপনা: প্রতিটি ক্যালেন্ডার একটি গাছ। এর নোডগুলি অপারেশন যেমন (
crear_juegoতারিখ, হোম টিম, অ্যাওয়ে টিম) এবং ,obtener_calendarioযা গেমগুলির দুটি তালিকায় যোগ দেয়। - ভায়াবিলিটি (সি 1): প্রতিটি দলকে অবশ্যই টুর্নামেন্টের জন্য ঠিক সংখ্যক গেম খেলতে হবে। 0 এর মান মানে হল যে সময়সূচীটি বৈধ।
- দূরত্ব (সি 2): স্থানান্তরের যোগফল, প্রতিটি স্টেডিয়ামের স্থানাঙ্কে হ্যাভারসিনের সূত্র দিয়ে গণনা করা হয়।
- সফ্টওয়্যার: ডিইএপি লাইব্রেরির সাথে তিনটি মডিউল (পরিকল্পনাকারী, ক্যালকুলেটর এবং জেনেটিক প্রোগ্রাম), জাঙ্গোতে একটি ওয়েব অ্যাপ্লিকেশন থেকে পৃথক।
ফলাফল
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 গুণ বেশি সময় নিয়েছিল। সেরা ক্যালেন্ডারটি সর্বদা প্রাথমিক প্রজন্ম থেকে এসেছিল, যা এলোমেলো।
থিসিসটি এই কারণগুলি চিহ্নিত করেছে:
- জেনেরিক ক্রসওভার এবং মিউটেশন অপারেটররা সমস্যাটি না জেনেই নোড পরিবর্তন করে। তারা প্রায় সর্বদা অবৈধ ক্যালেন্ডার তৈরি করে।
- ফিটনেস ফাংশন দূরত্বের চেয়ে কার্যকারিতাকে অনেক বেশি গুরুত্ব দেয়। একটি অবৈধ শিশু সর্বদা বৈধ পিতামাতার কাছে হেরে যায়।
- অ্যালগরিদমটি শীঘ্রই একটি স্থানীয় সর্বোত্তম দিকে একত্রিত হয়েছিল এবং কেবল প্রাথমিক সমাধানগুলি ধরে রেখেছিল।
একটি নেতিবাচক ফলাফলও একটি ফলাফল। এটি দেখায় যে প্রতিনিধিত্ব এবং অপারেটরগুলি অ্যালগরিদমের মতোই গুরুত্বপূর্ণ।
ভবিষ্যৎ কাজ
থিসিসটি প্রাসঙ্গিক অপারেটরদের প্রস্তাব করেছিল: এলোমেলোভাবে নোড পরিবর্তন করার পরিবর্তে, পুরো সিরিজ বা ব্লকগুলি অদলবদল করুন যা ক্যালেন্ডারকে বৈধ রাখে। তিনি একবারে অনেকগুলি কনফিগারেশন অন্বেষণ করার জন্য কোয়ান্টাম কম্পিউটিংয়ের কথাও উল্লেখ করেছিলেন।
সময়রেখা
- · থিসিস ডকুমেন্টের প্রাক-অফিসিয়াল সংস্করণ।
- · মেক্সিকো সিটিতে প্রতিরক্ষা। থিসিস অনুমোদিত।
উপকরণ এবং উদ্ধৃতি
- থিসিস ডকুমেন্ট, প্রাক-অফিসিয়াল সংস্করণ (PDF, 4.8 MB, স্পেনীয় ভাষায়)
- প্রতিরক্ষা উপস্থাপনা (PDF, 2.9 MB, স্পেনীয় ভাষায়)
এপিএ ফর্ম্যাটে উদ্ধৃতি:
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.