เอกสารประกอบ / ประวัติศาสตร์

ประวัติศาสตร์: วิทยานิพนธ์ (2026)

โปรแกรมพันธุกรรมในการวางแผนฤดูกาลเบสบอลปัญหาความเป็นไปได้และการเพิ่มประสิทธิภาพ วิทยานิพนธ์วิศวกรรมคอมพิวเตอร์ ITAM ที่ปรึกษา: ดร. อันเดรส โกเมซ เด ซิลวา การ์ซาอนุมัติเมื่อวันที่ 23 กรกฎาคม 2026

ปัญหา

MLB กําหนดการแข่งขัน 2,430 เกมสําหรับ 30 ทีมในเวลาประมาณ 180 วันแต่ละทีมเดินทางระหว่างเมืองต่าง ๆ และระยะทางแตกต่างกันมากในแต่ละทีมในปี 2016 ซีแอตเทิลเดินทาง 76,683 กิโลเมตร และชิคาโก คับส์ เดินทาง 39,015 กิโลเมตร

การหาตารางที่มีระยะทางรวมต่ําสุดเรียกว่า ปัญหาการขนส่งในทัวร์นาเมนต์ (PTT)เป็นปัญหา NP-hard: จํานวนตารางการแข่งขันที่เป็นไปได้เพิ่มขึ้นอย่างรวดเร็วจนไม่สามารถตรวจสอบทั้งหมดได้

วิธีการ

โปรแกรมพันธุกรรม (PG) ที่ John Koza เสนอในปี 1992 เลียนแบบวิวัฒนาการมันสร้างประชากรของทางออก เลือกวิธีที่ดีที่สุด และผสมผสานและปรับเปลี่ยนเพื่อสร้างคนรุ่นใหม่

การแทนค่า: แต่ละปฏิทินเป็นต้นไม้โหนดของมันเป็นการดําเนินการ เช่น crear_juego (วันที่, ทีมเหย้า, ทีมเยือน) และ obtener_calendario, ซึ่งรวมสองรายการเกมเข้าด้วยกัน
ความเป็นไปได้ (C1): แต่ละทีมต้องเล่นจํานวนเกมตามที่ทัวร์นาเมนต์กําหนดไว้อย่างแม่นยําค่า 0 หมายความว่าตารางการแข่งขันนั้นถูกต้อง
ระยะทาง (C2): ผลรวมของการโอนย้าย คํานวณด้วยสูตร haversine บนพิกัดของแต่ละสนาม
ซอฟต์แวร์: สามโมดูล (แพลนเนอร์, เครื่องคิดเลข และโปรแกรมพันธุกรรม) ที่มีไลบรารี 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.