ÁP DỤNG GIẢI THUẬT DI TRUYỀN
VÀO SẮP XẾP THỜI KHÓA BIỂU
Báo cáo viên: Đỗ Thị Chi
1
TRƢỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG
BỘ MÔN TRUYỀN THÔNG ĐA PHƢƠNG TIỆN
Thái Nguyên - 2012
Nội dung chính
Tính cấp thiết của đề tài
Bài toán Xếp Thời khóa biểu
Áp dụng GA vào bài toán xếp TKB
Kết quả thử nghiệm
Tính cấp thiết của đề tài
• TKB là bộ xương sống cơ bản để kết nối
hầu như toàn bộ các hoạt động của nhà
trường.
• Chương trình TKB thay thế các công việc
thao tác bằng tay trên giấy tờ đạt hiệu
quả không cao và mất nhiều thời gian.
• Ở Việt Nam hay trên Thế giới, tồn tại
không nhiều phần mềm hỗ trợ xếp TKB.
• 1000 trong số hơn 20000 trường THPT
dùng phần mềm TKB.
 Đòi hỏi nghiên cứu và đƣa ra các
chƣơng trình hỗ trợ lập TKB hợp lý,
hiệu quả và chính xác.
3
Mô hình xếp TKB
Phân loại theo khuôn dạng thời gian
• Thời khóa biểu TUẦN:dạng TKB cho
1 tuần và làm chuẩn cho cả học

Địa lý(2 - Phùng)
Toán(2 - A)
Ngoại ngữ(2 - Kim Vân)
Sinh vật(2 - Hưởng)
Địa lý(2 - Phùng)
Toán(2 - A)
Ngữ văn(2 - Sáu)
Ngoại ngữ(2 - Kim Vân)
Vật lý(2 - Diễn)
Ngữ văn(2 - Sáu)
Toán(2 - A)
Hóa học(2 - Dũng) Sinh hoạt.L6(1 - A)
Giảng viên: Tỵ
Thứ 2 Thứ 3 Thứ 4 Thứ 5 Thứ 6 Thứ 7
12A2-Toán(3-2)
12A2-Toán(1-2) 12A2-Toán(3-2)
Giảng viên: A
Thứ 2 Thứ 3 Thứ 4 Thứ 5 Thứ 6 Thứ 7
12A1-Chào cờ.F2(1-1)
12A1-Toán(2-2)
12A1-Toán(1-2)
12A1-Sinh hoạt.L6(5-1)
12A1-Toán(4-2)
TKB học sinh
TKB giáo viên
Bài toán Thời khóa biểu
• Ràng buộc cứng
- Tại 1 thời điểm 1 GV không thể dạy 2 lớp.
- Tại 1 thời điểm 1 lớp không thể học 2 môn học.
- Bảo đảm các quy định về thời gian (Số giờ học/ngày, số

được đơn giản hóa trong giai đoạn trước. Kết quả của
giai đoạn này chính là mục tiêu cuối cùng của bài toán.
Đó là lịch học của các lớp trong một cơ sở.
11
Cách biểu diễn lời giải cho bài toán
12
TKB Lớp 1
TKB Lớp 2
TKB Lớp 3
………
TKB Lớp n
Thứ 2
Thứ 3
Thứ 4
…
Thứ n
Tiết 1
Tiết 2
Tiết 3
…
Tiết n
Tên môn
Số tiêt
Tên GV
Thứ 2
Thứ 3
Thứ 4
…
Thứ n
Thứ 2

Tên môn
Số tiêt
Tên GV
Hàm thích nghi
- Trùng giờ
- Số môn học bị lặp lại trong buổi
- Lịch bận của giáo viên
Chọn cách tính tốt nhất là xếp theo giá trị giảm dần
của giá trị bị phạt theo độ thích nghi. Cá thể được
chọn là cá thể tốt nhất, giá trị thích nghi đạt ở mức
đỉnh là 0.
Các tham số
• Xác suất lai ghép Pc:cho biết tần suất thực
hiện toán tử lai ghép. 0.85 – 0.9
• Xác suất đột biến Pm:cho biết tần suất đột
biến của nhiễm sắc thể. 0.05 – 0.1
• Xác suất tái sinh Pr: cho biết tần suất thực
hiện toán tử tái sinh.
• Kích thước quần thể: cho biết có bao nhiêu
cá thể (NST) trong 1 thế hệ của quần thể.
Toán tử lai ghép
- Chọn ngẫu nhiên 1 cặp NST trong quần thể.
- Chọn một đoạn lai ghép ngẫu nhiên rồi tiến hành lai
ghép. Ví dụ:
cha
mẹ
Sau khi lai :
con 1
con 2
Lớp A1

Lớp Z2
Toán tử đột biến
- Chọn ngẫu nhiên 1 NST trong quần thể.
- Chọn một điểm đột biến ngẫu nhiên rồi tiến hành
đột biến ( phép đột biến được thực hiện bằng cách
khởi tạo lại giá trị tại điểm đó ).
Ví dụ: Trước khi đột biến:
Sau khi đột biến:
Lớp A1
Lớp B1
Lớp C1
Lớp D1
Lớp E1
Lớp G1
……
Lớp Z1
Lớp A1
Lớp B1
Lớp C’
Lớp D1
Lớp E1
Lớp G1
………
Lớp Z1
Toán tử chọn lọc
- Toán tử chọn lọc là một quá
trình loại bỏ các NST kém thích
nghi trong quần thể.
- NST có độ thích nghi càng cao
thì xác suất tồn tại càng lớn.