MỤC LỤC

LỜI CẢM ƠN . 1

MỤC LỤC . 3

DANH MỤC HÌNH VẼ . . 5

DANH MỤC BẢNG BIỂU . 6

DANH MỤC CHỮ VIẾT TẮT . . 7

MỞ ĐẦU . . 8

CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN XẾP THỜI KHÓA BIỂU

VÀ CÁC PHƯƠNG PHÁP TIẾP CẬN . 9

1.1 Tổng quan . . 9

1.2 ng Cao đẳng - Đại học . . 10

1.3 Các phương pháp tiếp cận hiện nay . . 12

CHƯƠNG 2: GIẢI THUẬT DI TRUYỀN VÀ TÍNH TOÁN TIẾN

HÓA . 15

2.1 Giải thuật di truyền . 15

2.1.1 Ý tưởng . . 15

2.1.2 Đặc trưng . . 15

2.1.3 Cấu trúc . . 16

2.1.4 Biểu diễn bằng vector số thực . 23

2.1.5 Một số cải tiến đơn giản của giải thuật di truyền . . 24

2.2 Tính toán tiến hóa (Evolutionary Computation) . . 25

2.2.1 Các chiến lược tiến hóa (Evolution Strategies - ES) . . 25

2.2.2 Lập trình tiến hóa (Evoluationary Programming - EP) . 28

2.2.3 Lập trình di truyền (Genetic Programming - GP) . . 29

2.2.4 Chương trình tiến hóa (Evoluation Programmes - Eps) . . 31

CHƯƠNG 3: BÀI TOÁN THỜI KHÓA BIỂU - PHÂN TÍCH THIẾT

KẾ HỆ THỐNG VÀ ÁP DỤNG GIẢI THUẬT TIẾN HÓA . 35

3.1 Phân tích thiết kế hệ thống . . 35

3.1.1 Mô hình đào tạo theo tín chỉ . . 35

3.1.2 Quy trình xếp thời khóa biểu theo đào tạo tín chỉ . 36

3.1.3 Sơ đồ tiến trình nghiệp vụ xếp thời khóa biểu . . 39

3.1.4 Mô hình nghiệp vụ . . 40

3.1.5 Biểu đồ ngữ cảnh . . 41

3.1.6 Biểu đồ phân rã chức năng . 42

3.1.7 Danh sách hồ sơ dữ liệu sử dụng . 43

3.1.8 Ma trận thực thể chức năng . 43

3.1.9 Biểu đồ luồng dữ liệu . 44

3.1.10 Mô hình liên kết thực thể (ER) . 47

3.1.11 Mô hình quan hệ . 50

3.2 Áp dụng giải thuật tiến hóa . 54

3.2.1 Các yêu cầu cơ bản của thời khóa biểu theo đào tạo tín chỉ . 54

3.2.2 Biểu diễn nhiễm sắc thể . 55

3.2.3 Khởi tạo quần thể ban đầu . 57

3.2.4 Xác định hàm thích nghi . 60

3.2.5 Các toán tử di truyền . 61

3.2.6 Quá trình chọn lọc . 63

3.2.7 Thủ tục tiến hóa . 64

CHƯƠNG 4: XÂY DỰNG ỨNG DỤNG MINH HỌA . 65

4.1 Tổng quan về ứng dụng . 65

4.2 Một số chức năng vào giao diện của ứng dụng . 66

4.2.1 Chức năng nhập dữ liệu . 66

4.2.2 Chức năng hiển thị thời khóa biểu . 69

4.3 Thử nghiệm ứng dụng . 70

4.3.1 Kết quả đạt được của ứng dụng . 71

4.3.2 Bảng kết quả thực nghiệm . 71

TÀI LIỆU THAM KHẢO . 74

4

MỞ ĐẦU

Thời khóa biểu của trường học là kế hoạch giảng dạy của giáo viên và học

tập của sinh viên. Một bảng thời khóa biểu hợp lý giúp giáo viên thuận lợi, thoải

mái khi lên lớp và giúp sinh viên thoải mái khi đăng ký học tập.

Đã từ lâu, việc lập thời khóa biểu cho các lớp tín chỉ là vấn đề quan trọng của

phòng đào tạo và phải luôn luôn hoàn thành trước khi triển khai cho sinh viên đăng

ký học. Lập thời khóa biểu bằng phương pháp thủ công là công việc rất nặng nề, tốn

nhiều thời gian và dễ vi phạm các ràng buộc về nghiệp vụ. Do vậy, khi áp dụng phải

trải qua điều chỉnh vài lần mới có thể đạt được yêu cầu cơ bản.

Các bài toán thời khóa biểu rất phong phú và đa dạng bởi những ràng buộc

và yêu cầu đặc trưng của từng hệ đào tạo, thậm chí từng trường học.

Bài toán thời khóa biểu thuộc lớp các bài toán tối ưu nên các giải thuật

truyền thống khó giải quyết được trọn vẹn các yêu cầu nghiệp vụ và yêu cầu về thời

gian thực hiện.

Trong ba thập niên qua, có nhiều giải thuật được xây dựng và cải tiến để giải

các bài toán tối ưu. Giải thuật di truyền và tính tiến hóa mô phỏng sự tiến hóa của tự

nhiên của sinh học và gần đây nhất là phương pháp tối ưu hóa đàn kiến do Dorigo

đề xuất là hướng tiếp cận hiện đại nhất. Cả hai loại giải thuật trên đã tỏ ra rất hiệu

quả trong việc áp dụng giải quyết các bài toán tối ưu trong thực tế, tiêu biểu là bài

toán lập thời khóa biểu trường học, là một bài toán thú vị và có tính thực tiễn cao.

Xuất phát từ những vấn đề trên, đề tài “Xây dựng chương trình hỗ trợ xếp

lịch thời khóa biểu cho đào tạo và học tập tín chỉ” được hình thành, đồ án tập trung

nghiên cứu bài toán lập thời khóa biểu cho đào tạo tín chỉ, sử dụng giải thuật di

truyền và phương pháp tính toán tiến hóa để giải bài toán cả về mặt lý thuyết lẫn

xây dựng ứng dụng.

Cấu trúc của đồ án như sau:

Chương 1: Tổng quan về bài toán xếp thời khóa biểu và các phương pháp

tiếp cận,

Chương 2: Giải thuật di truyền và tính toán tiến hóa,

Chương 3: Bài toán thời khóa biểu - Phân tích thiết kế hệ thống và áp dụng

giải thuật tiến hóa,

Chương 4: Xây dựng ứng dụng minh họa,

Và cuối cùng là phần kết luận