World’s Best Student
Project 2
Giải thuật di truyền và bài toán sắp xếp thời khóa biểu cho một trường tiểu học
6/3/2012
Nội dung
I.Giải thuật di truyền
II.Mô tả bài toán sắp xếp TKB
III.Thiết kế giải thuật cho bài toán sắp xếp TKB
IV.Công cụ lập trình
I. Giải thuật di truyền
I.1. Khái quát về giải thuật di truyền
I.2. Các toán tử của giải thuật di truyền:
I.2.1. Toán tử lai ghép
I.2.2. Toán tử đột biến
I.2.3. Toán tử chọn lọc
Toán tử lai ghép
Quá trình lai ghép diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai
nhiễm sắc thể (NST) cha-mẹ để hình thành hai chuỗi NST con mang đặc tính của
cả cha lẫn mẹ. Giả sử chuỗi NST của cha và mẹ đều có chiều dài là m và được
chọn ngẫu nhiên trong quần thể. Điểm lai sẽ chia hai chuỗi NST cha-mẹ thành
hai chuỗi NST con. Đưa hai chuỗi NST con vào quần thể để tiếp tục tham gia quá
trình tiến hóa tiếp theo.
Toán tử đột biến
Quá trình đột biến xảy ra khi một hoặc một số tính trạng của con không
được thừa hưởng từ hai chuỗi NST cha-mẹ. Phép đột biến xảy ra với xác
suất thấp hơn rất nhiều lần so với xác suất xảy ra phép lai. Phép đột biến có
thể mô tả như sau: Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m. Thay đổi
giá trị của gen thứ k. Đưa NST con vào quần thể để tham gia quá trình tiến
hóa tiếp theo.
Toán tử chọn lọc
Là quá trình dựa trên độ thích nghi của từng cá thể. Độ thích nghi là một

- B2: xác định lịch học của tất cả các lớp trong từng ngày
Mô hình giải bài toán sắp xếp TKB
+ Bước 1:
- Thực hiện “Giải thuật di truyền (I)” cho tất cả giáo viên
- Thực hiện “Giải thuật di truyền (II)”
+ Bước 2:
- Thực hiện “Giải thuật di truyền (III)”
- Xuất kết quả
III. Thiết kế giải thuật cho bài toán sắp xếp TKB
III.1. Giải thuật di truyền (I):
Mục tiêu: tạo ra lịch giảng cho từng giáo viên
III.2. Giải thuật di truyền (II):
Mục tiêu: đưa bài toán sắp xếp thời khóa biểu N ngày về bài toán sắp lịch thời khóa
biểu trên 1 ngày
III.3. Giải thuật di truyền (III):
Mục tiêu: sắp lịch phân công trong 1 ngày sao cho thỏa mãn RB2 (1 lớp không thể
học 2 môn/1 tiết)
III. Thiết kế giải thuật cho bài toán sắp xếp TKB
•
Với mỗi giải thuật di truyền ở trên, ta lần lượt sử dụng các toán tử
lai ghép, đột biến và chọn lọc để cuối cùng chọn ra được những cá
thể có độ thích nghi cao và đạt được mục tiêu đã đề ra cho từng
giải thuật di truyền.
Một số chức năng của chương trình
+ Tạo mới TKB
+ Chỉnh sửa DL ( thêm, sửa, xóa thông tin giáo viên, môn học)
+ Định nghĩa thời gian xếp TKB (số ngày làm việc trong tuần, số tiết học
trong ngày)
+ Điều chỉnh các ràng buộc (thời gian bận, số ngày, tiết dạy trong tuần của
giáo viên)