Ứng dụng giải thuật di truyền vào bài toán sắp xếp lịch thi
26 thg 9, 2023 | 14:03

Ứng dụng giải thuật di truyền vào bài toán sắp xếp lịch thi



Trên thế giới hiện nay, Thuật Giải Di Truyền kết hợp với Công nghệ thông tin được ứng dụng để giải quyết những vấn đề phức tạp trong hệ thống điện một cách rất hiệu quả. Nhưng trong đề tài này, chúng ta nghiên cứu ứng dụng Thuật giải Di truyền xếp lịch thi trong trường Đại học.



NỘI DUNG:



CHƯƠNG 1 - TÌM HIỂU VỀ BÀI TOÁN LẬP LỊCH  7

1.1 Tìm hiểu chung .................................................................................................. 7
1.2 Các đặc tính của bài toán lập lịch ................................................................... 7
1.3 Bài toán Lập Lịch Thi..................................................................................... 8
1.3.1 Giới thiệu bài toán .................................................................................... 8
1.3.2 Dữ liệu bài toán ........................................................................................ 8
1.4 Một số bước cơ bản để giải quyết bài toán lập lịch thi .................................... 8
CHƯƠNG 2 - GIẢI THUẬT DI TRUYỀN (GAS) .................................................. 9
2.1 Tìm hiểu chung về GAS ................................................................................. 9
2.1.1 Cấu trúc giải thuật di truyền tổng quát .................................................... 11
2.1.2 Những nguyên tắc cơ bản thực hiện giải thuật di truyền GAS ................ 12
2.2. Các toán tử của giải thuật di truyền.............................................................. 13
2.3 Các tham số của giải thuật di truyền ............................................................. 13
2.4 Cách biểu diễn bài toán trong giải thuật di truyền ......................................... 14
2.4.1 Biểu diễn Gen bằng chuỗi nhị phân ........................................................ 14
2.4.2 Biểu diễn số thực bằng chuỗi nhị phân ................................................... 15
2.4.2 Biểu diễn Gen bằng chuỗi số thực .......................................................... 17
2.4.3 Biểu diễn Gen bằng cấu trúc cây ............................................................ 18
2.5 Nguyên lý về xác định tính thích nghi .......................................................... 18
2.5.1 Độ thích nghi tiêu chuẩn ........................................................................ 19
2.5.2 Độ thích nghi xếp hạng (rank method) ................................................... 20
2.6 Mã hóa (Encoding) ....................................................................................... 23
2.6.1 Giới thiệu (Introduction) ........................................................................ 23
2.6.2 Mã hóa bằng số nhị phân (Binary Encoding)

3

......................... 23

2.6.3 Mã hóa vị trí (Permutation Encoding) .................................................... 24
2.6.4 Mã hóa theo giá trị (Value Encoding)

. ....................................... 24

2.6.5 Cây mã hóa (Tree Encoding) .................................................................. 25
2.7 Các phương pháp chọn (Selection) ............................................................... 26
2.7.1 Chọn lọc Roulette (Roulette Wheel Selection) ....................................... 26
2.7.2 Chọn lọc xếp hạng (Rank Selection)....................................................... 27
2.7.3 Chọn lọc cạnh tranh ( Tournament Selection) ......................................... 27
2.8 Các phương pháp lai tạo (crossover) và đột biến (mutation) ......................... 27
2.8.1 Binary Encoding (mã hóa nhị phân) ....................................................... 27
2.8.2 Permutation Encoding (Mã hóa vị trí) .................................................... 29
2.8.3 Value Encoding (mã hóa theo giá trị) ..................................................... 29
2.8.4 Tree Encoding (Cây mã hóa) .................................................................. 29
2.9 Các toán tử trong giải thuật di truyền ............................................................ 31
2.9.1 Toán tử Chọn lọc.................................................................................... 31
2.9.2 Toán tử lai ghép ..................................................................................... 32
2.9.3 Toán tử đột biến ..................................................................................... 33
2.9.4 Toán tử sinh sản ..................................................................................... 34
2.10 Các tham số cần sử dụng trong giải thuật di truyền ..................................... 34
2.11 Điều kiện kết thúc thuật giải di truyền ........................................................ 34
2.12 Ứng dụng của thuật giải di truyền ............................................................... 34
CHƯƠNG 3 - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN SẮP
XẾP LỊCH THI ..................................................................................................... 35
3.1 Giai đoạn 1: Xếp lịch thi các lớp .................................................................. 36
3.1.1 Chọn mô hình cá thể............................................................................... 36
3.1.2 Tạo quần thể ban đầu ............................................................................. 37
3.1.3 Độ thích nghi – chọn cá thể .................................................................... 37

4

3.1.4 Thuật toán lai ghép và đột biến............................................................... 38
3.2 Giai đoạn 2: Xếp lịch thi cho toàn bộ cơ sở .................................................. 38
3.2.1 Chọn mô hình cá thể............................................................................... 38
3.2.2 Tạo quần thể ban đầu ............................................................................. 39
3.2.3 Độ thích nghi - chọn cá thể..................................................................... 39
3.2.4 Thuật toán lai ghép và đột biến............................................................... 40
3.2.5 Chọn điểm dừng thuật toán .................................................................... 40
CHƯƠNG 4 - THIẾT KẾ HỆ THỐNG BÀI TOÁN LẬP LỊCH THI .................... 41
4.1 Sơ đồ chức năng liên kết .............................................................................. 41
4.2 Phân tích thiết kế hệ thống cơ sở dữ liệu....................................................... 42
4.3 Các đối tượng của lịch thi ............................................................................. 42
4.4 Mô tả bảng sơ đồ liên kết trong cơ sở dữ liệu ............................................... 43
4.5 Chương trình thực nghiệm ............................................................................ 47
4.5.1 Form đăng nhập ..................................................................................... 48
4.5.2 Giao diện chính của chương trình ........................................................... 48
4.5.3 Form đổi mật khẩu ................................................................................. 49
4.5.4 Form nhân viên, quản trị ........................................................................ 50
4.5.5 Form quản lý lớp học ............................................................................. 51
4.5.7 Form quản lý ca thi ................................................................................ 51
4.5.9 Form quản lý khóa học ........................................................................... 52
4.5.6 Form quản lý môn thi ............................................................................. 52
4.5.8 Form quản lý sinh viên ........................................................................... 53
4.5.11 Form quản lý phòng học ....................................................................... 54
4.5.10 Form sắp xếp lịch thi ............................................................................ 54
4.5.12 Form đăng xuất .................................................................................... 55

5

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.............................................................. 56
1. Kết quả đạt được ............................................................................................ 56
2. Hạn chế - Hướng phát triển trong tương lai .................................................... 56
2.1 Hạn chế ..................................................................................................... 56
2.2 Hướng phát triển trong tương lai ............................................................... 56
TÀI LIỆU THAM KHẢO






Trên thế giới hiện nay, Thuật Giải Di Truyền kết hợp với Công nghệ thông tin được ứng dụng để giải quyết những vấn đề phức tạp trong hệ thống điện một cách rất hiệu quả. Nhưng trong đề tài này, chúng ta nghiên cứu ứng dụng Thuật giải Di truyền xếp lịch thi trong trường Đại học.



NỘI DUNG:



CHƯƠNG 1 - TÌM HIỂU VỀ BÀI TOÁN LẬP LỊCH  7

1.1 Tìm hiểu chung .................................................................................................. 7
1.2 Các đặc tính của bài toán lập lịch ................................................................... 7
1.3 Bài toán Lập Lịch Thi..................................................................................... 8
1.3.1 Giới thiệu bài toán .................................................................................... 8
1.3.2 Dữ liệu bài toán ........................................................................................ 8
1.4 Một số bước cơ bản để giải quyết bài toán lập lịch thi .................................... 8
CHƯƠNG 2 - GIẢI THUẬT DI TRUYỀN (GAS) .................................................. 9
2.1 Tìm hiểu chung về GAS ................................................................................. 9
2.1.1 Cấu trúc giải thuật di truyền tổng quát .................................................... 11
2.1.2 Những nguyên tắc cơ bản thực hiện giải thuật di truyền GAS ................ 12
2.2. Các toán tử của giải thuật di truyền.............................................................. 13
2.3 Các tham số của giải thuật di truyền ............................................................. 13
2.4 Cách biểu diễn bài toán trong giải thuật di truyền ......................................... 14
2.4.1 Biểu diễn Gen bằng chuỗi nhị phân ........................................................ 14
2.4.2 Biểu diễn số thực bằng chuỗi nhị phân ................................................... 15
2.4.2 Biểu diễn Gen bằng chuỗi số thực .......................................................... 17
2.4.3 Biểu diễn Gen bằng cấu trúc cây ............................................................ 18
2.5 Nguyên lý về xác định tính thích nghi .......................................................... 18
2.5.1 Độ thích nghi tiêu chuẩn ........................................................................ 19
2.5.2 Độ thích nghi xếp hạng (rank method) ................................................... 20
2.6 Mã hóa (Encoding) ....................................................................................... 23
2.6.1 Giới thiệu (Introduction) ........................................................................ 23
2.6.2 Mã hóa bằng số nhị phân (Binary Encoding)

3

......................... 23

2.6.3 Mã hóa vị trí (Permutation Encoding) .................................................... 24
2.6.4 Mã hóa theo giá trị (Value Encoding)

. ....................................... 24

2.6.5 Cây mã hóa (Tree Encoding) .................................................................. 25
2.7 Các phương pháp chọn (Selection) ............................................................... 26
2.7.1 Chọn lọc Roulette (Roulette Wheel Selection) ....................................... 26
2.7.2 Chọn lọc xếp hạng (Rank Selection)....................................................... 27
2.7.3 Chọn lọc cạnh tranh ( Tournament Selection) ......................................... 27
2.8 Các phương pháp lai tạo (crossover) và đột biến (mutation) ......................... 27
2.8.1 Binary Encoding (mã hóa nhị phân) ....................................................... 27
2.8.2 Permutation Encoding (Mã hóa vị trí) .................................................... 29
2.8.3 Value Encoding (mã hóa theo giá trị) ..................................................... 29
2.8.4 Tree Encoding (Cây mã hóa) .................................................................. 29
2.9 Các toán tử trong giải thuật di truyền ............................................................ 31
2.9.1 Toán tử Chọn lọc.................................................................................... 31
2.9.2 Toán tử lai ghép ..................................................................................... 32
2.9.3 Toán tử đột biến ..................................................................................... 33
2.9.4 Toán tử sinh sản ..................................................................................... 34
2.10 Các tham số cần sử dụng trong giải thuật di truyền ..................................... 34
2.11 Điều kiện kết thúc thuật giải di truyền ........................................................ 34
2.12 Ứng dụng của thuật giải di truyền ............................................................... 34
CHƯƠNG 3 - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN SẮP
XẾP LỊCH THI ..................................................................................................... 35
3.1 Giai đoạn 1: Xếp lịch thi các lớp .................................................................. 36
3.1.1 Chọn mô hình cá thể............................................................................... 36
3.1.2 Tạo quần thể ban đầu ............................................................................. 37
3.1.3 Độ thích nghi – chọn cá thể .................................................................... 37

4

3.1.4 Thuật toán lai ghép và đột biến............................................................... 38
3.2 Giai đoạn 2: Xếp lịch thi cho toàn bộ cơ sở .................................................. 38
3.2.1 Chọn mô hình cá thể............................................................................... 38
3.2.2 Tạo quần thể ban đầu ............................................................................. 39
3.2.3 Độ thích nghi - chọn cá thể..................................................................... 39
3.2.4 Thuật toán lai ghép và đột biến............................................................... 40
3.2.5 Chọn điểm dừng thuật toán .................................................................... 40
CHƯƠNG 4 - THIẾT KẾ HỆ THỐNG BÀI TOÁN LẬP LỊCH THI .................... 41
4.1 Sơ đồ chức năng liên kết .............................................................................. 41
4.2 Phân tích thiết kế hệ thống cơ sở dữ liệu....................................................... 42
4.3 Các đối tượng của lịch thi ............................................................................. 42
4.4 Mô tả bảng sơ đồ liên kết trong cơ sở dữ liệu ............................................... 43
4.5 Chương trình thực nghiệm ............................................................................ 47
4.5.1 Form đăng nhập ..................................................................................... 48
4.5.2 Giao diện chính của chương trình ........................................................... 48
4.5.3 Form đổi mật khẩu ................................................................................. 49
4.5.4 Form nhân viên, quản trị ........................................................................ 50
4.5.5 Form quản lý lớp học ............................................................................. 51
4.5.7 Form quản lý ca thi ................................................................................ 51
4.5.9 Form quản lý khóa học ........................................................................... 52
4.5.6 Form quản lý môn thi ............................................................................. 52
4.5.8 Form quản lý sinh viên ........................................................................... 53
4.5.11 Form quản lý phòng học ....................................................................... 54
4.5.10 Form sắp xếp lịch thi ............................................................................ 54
4.5.12 Form đăng xuất .................................................................................... 55

5

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.............................................................. 56
1. Kết quả đạt được ............................................................................................ 56
2. Hạn chế - Hướng phát triển trong tương lai .................................................... 56
2.1 Hạn chế ..................................................................................................... 56
2.2 Hướng phát triển trong tương lai ............................................................... 56
TÀI LIỆU THAM KHẢO




M_tả
M_tả

Chuyên mục:

Không có nhận xét nào: