Tài liệu tham khảo / Lịch sử
Lịch sử: luận văn (2026)
Lập trình di truyền trong lập kế hoạch mùa giải bóng chày. Bài toán khả thi và tối ưu hóa. Luận văn Kỹ thuật Máy tính, ITAM. Cố vấn: Tiến sĩ Andrés Gómez de Silva Garza. Được phê duyệt vào ngày 23 tháng 7 năm 2026.
Vấn đề
MLB lên lịch thi đấu 2.430 trận cho 30 đội trong khoảng 180 ngày. Mỗi đội di chuyển giữa các thành phố, và khoảng cách rất khác nhau giữa các đội. Năm 2016, Seattle di chuyển 76.683 km, còn Chicago Cubs di chuyển 39.015 km.
Việc tìm lịch trình có tổng quãng đường thấp nhất được gọi là Vấn đề Vận chuyển Giải đấu (PTT). Đây là một vấn đề NP-khó: số lượng lịch trình có thể tăng nhanh đến mức bạn không thể kiểm tra hết.
Phương pháp
Lập trình di truyền (PG), do John Koza đề xuất năm 1992, mô phỏng tiến hóa. Nó tạo ra một quần thể các giải pháp, lấy những giải pháp tốt nhất, kết hợp và điều chỉnh chúng để tạo thành một thế hệ mới.
- Biểu diễn: Mỗi lịch là một cây. Các nút của nó là các phép toán như
crear_juego(ngày, đội nhà, đội khách) vàobtener_calendario, kết nối hai danh sách trò chơi. - Tính khả thi (C1): Mỗi đội phải chơi đúng số trận mà giải đấu yêu cầu. Giá trị 0 nghĩa là lịch thi đấu hợp lệ.
- Khoảng cách (C2): tổng các lần chuyển nhượng, được tính bằng công thức Haversine trên tọa độ của mỗi sân vận động.
- Phần mềm: ba mô-đun (lập kế hoạch, máy tính và chương trình di truyền) với thư viện DEAP, tách biệt với ứng dụng web trong Django.
Kết quả
Hãy thử 30 đội, 163 trận mỗi đội, loạt 5 trận và 20 thế hệ.
| Phương pháp | Vấn đề. của việc vượt qua | Có thể. của đột biến | Tính khả thi (C1) | Tổng quãng đường (C2) | Thời gian |
|---|---|---|---|---|---|
| Tìm kiếm ngẫu nhiên | 0.0 | 0.0 | 0 (hợp lệ) | 2,663,470.70 km Khoảng cách ngắn hơn | 200.25 s |
| Lập trình di truyền | 0.8 | 0.2 | 0 (hợp lệ) | 3,182,738.33 km | 3,337.81 s |
Phát hiện chính
Lập trình di truyền không vượt trội hơn tìm kiếm ngẫu nhiên. Nó cho khoảng cách lớn hơn 19,5% và mất gần 17 lần lâu hơn. Lịch tốt nhất luôn đến từ thế hệ đầu tiên, vốn là ngẫu nhiên.
Luận án đã xác định các nguyên nhân sau:
- Các toán tử giao thoa và đột biến tổng quát thay đổi nút mà không biết vấn đề. Chúng gần như luôn tạo ra lịch không hợp lệ.
- Hàm thích nghi đặt trọng tâm lớn hơn nhiều vào khả năng tồn tại so với khoảng cách. Một đứa trẻ tàn tật luôn thua trước một phụ huynh hợp pháp.
- Thuật toán nhanh chóng hội tụ về một tối ưu cục bộ và chỉ giữ lại các nghiệm ban đầu.
Kết quả âm cũng là kết quả. Nó cho thấy biểu diễn và toán tử quan trọng ngang với thuật toán.
Công việc trong tương lai
Luận án đề xuất các toán tử ngữ cảnh: thay vì thay đổi nút một cách ngẫu nhiên, hãy hoán đổi toàn bộ chuỗi hoặc khối giữ cho lịch hợp lệ. Ông cũng đề cập đến tính toán lượng tử để khám phá nhiều cấu hình cùng lúc.
Dòng thời gian
- · Phiên bản tiền chính thức của tài liệu luận văn.
- · Phòng thủ ở Thành phố Mexico. Luận án được chấp thuận.
Tài liệu và trích dẫn
- Tài liệu luận văn, phiên bản tiền chính thức (PDF, 4.8 MB, bằng tiếng Tây Ban Nha)
- Giới thiệu về bản bào chữa (PDF, 2.9 MB, bằng tiếng Tây Ban Nha)
Trích dẫn theo định dạng 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.