Nghiên Cứu Thuật Toán Tối Ưu Sói Xám GWO Cho Bài Toán Lập Lịch

Khóa luận nghiên cứu thuật toán tối ưu sói xám GWO trong lập lịch, ứng dụng công nghệ thông tin, mang lại hiệu quả cao trong quản lý thời gian.

• Tác giả: Nguyễn Thành Lộc
• Người hướng dẫn: TS. Nguyễn Văn Dũ
• Trường học: Trường Đại Học Nông Lâm TP HCM
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên Cứu Thuật Toán Tối Ưu Sói Xám GWO Cho Bài Toán Lập Lịch
• Loại tài liệu: luận văn tốt nghiệp
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Hiện trạng và khó khăn thực tế
• 1.2. Lý do chọn đề tài
• 1.3. Mục tiêu đề tài
• 1.4. Nội dung nghiên cứu
• 1.5. Phạm vi nghiên cứu
• 1.6. Cơ sở khoa học và thực tiễn
• 1.7. Sản phẩm
• 2. CHƯƠNG 2: PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
• 2.1. Giới thiệu thuật toán GWO
• 2.1.1. Sơ lược trí tuệ bầy đàn
• 2.1.2. Sơ lược thuật toán tối ưu sói xám
• 2.1.3. Triển khai thuật toán sói xám GWO
• 2.1.4. Ưu điểm của thuật toán sói xám
• 2.1.5. Nhược điểm của thuật toán sói xám
• 2.2. Giới thiệu thuật toán SA
• 2.2.1. Giới thiệu về thuật toán SA
• 2.2.2. Mã giả
• 2.2.3. Ưu điểm của thuật toán SA
• 2.3. Giới thiệu thuật toán GA
• 2.3.1. Giới thiệu về thuật toán GA
• 2.3.2. Mã giả
• 2.3.3. Ưu điểm của thuật toán GA
• 3. CHƯƠNG 3: ÁP DỤNG THUẬT TOÁN GWO VÀO BÀI TOÁN LẬP LỊCH THI
• 3.1. Phát biểu bài toán lập lịch thi
• 3.2. Quy trình xếp lịch thi
• 3.3. Áp dụng thuật toán GWO vào bài toán lập lịch thi
• 3.3.1. Ràng buộc cứng
• 3.3.2. Ràng buộc mềm
• 3.3.3. Hàm mục tiêu của bài toán
• 3.4. Hướng áp dụng thuật toán
• 3.5. Áp dụng thuật toán SA vào bài toán lập lịch thi
• 3.6. Áp dụng thuật toán GA vào bài toán lập lịch thi
• 3.7. Kết quả thực nghiệm
• 3.8. So sánh các thuật toán
• 4. CHƯƠNG 4: ỨNG DỤNG XẾP LỊCH THI
• 4.1. Tìm hiểu về Spring Boot
• 4.1.1. Khái quát về Spring Boot
• 4.1.2. Giới thiệu về Spring Boot
• 4.1.3. Lý do chọn Spring Boot
• 4.1.4. Các thành phần chính của Spring Boot
• 4.2. Giới thiệu JPA
• 4.2.1. Kiến trúc Data JPA
• 4.2.2. Các tính năng của JPA
• 4.3. Tìm hiểu về Spring Security
• 4.3.1. Spring Security là gì?
• 4.3.2. Các thành phần chính
• 4.4. Tìm hiểu về ReactJs
• 4.4.1. Giới thiệu sơ lược về ReactJs
• 4.4.2. Khái niệm ReactJs
• 4.4.3. Đặc trưng nổi bật của ReactJs
• 4.4.4. Những lý do nên chọn sử dụng ReactJs
• 4.4.5. Các khái niệm cơ bản
• 4.5. Tìm hiểu về Redux
• 4.5.1. Giới thiệu sơ lược về Redux
• 4.5.2. Nguyên lý hoạt động của Redux
• 4.5.3. Tìm hiểu Redux Saga
• 4.6. Tìm hiểu về MySQL
• 4.6.1. Giới thiệu sơ lược
• 4.6.2. Tại sao lại sử dụng MySQL
• 4.6.3. Nhược điểm
• 4.7. Tìm hiểu JWT
• 4.7.1. Khái quát JWT
• 4.7.2. Khi nào thì nên sử dụng JWT
• 4.7.3. Cấu trúc JWT
• 4.7.4. Cách thức hoạt động của JWT
• 4.7.5. Ưu điểm của JWT
• 4.8. Kiến trúc hệ thống
• 4.8.1. Lược đồ tổng quan
• 4.8.2. Chức năng hệ thống
• 4.9. Đổi mật khẩu
• 4.10. Xem thời khóa biểu
• 4.11. Xem lịch thi
• 4.12. Xem điểm thi
• 4.13. Tạo lịch thi
• 4.14. Điều chỉnh lịch thi
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 5.1. Kết luận
• 5.2. Kết quả đạt được
• 5.2.1. Về kiến thức
• 5.2.2. Về nhận thức
• 5.2.3. Về sản phẩm
• 5.3. Ưu điểm của đề tài luận văn
• 5.3.1. Về công nghệ
• 5.3.2. Về tính năng
• 5.4. Nhược điểm của đề tài luận văn
• 5.5. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC
• 7.1. Đăng nhập
• 7.2. Quên mật khẩu
• 7.3. Xem thời khóa biểu
• 7.4. Xem điểm
• 7.5. Xem lịch thi
• 7.6. Tạo lịch thi
• 7.7. Điều chỉnh lịch thi

Tóm tắt

I. Tổng quan về Nghiên Cứu Thuật Toán Tối Ưu Sói Xám GWO

Nghiên cứu thuật toán tối ưu sói xám GWO (Grey Wolf Optimizer) đã trở thành một trong những lĩnh vực quan trọng trong công nghệ thông tin. Thuật toán này được phát triển dựa trên hành vi săn mồi của đàn sói xám, mang lại nhiều ứng dụng trong các bài toán tối ưu hóa phức tạp, bao gồm bài toán lập lịch. Việc áp dụng GWO vào bài toán lập lịch không chỉ giúp cải thiện hiệu suất mà còn tối ưu hóa việc sử dụng tài nguyên.

1.1. Ứng dụng của Thuật Toán GWO trong Lập Lịch

Thuật toán GWO đã được áp dụng thành công trong nhiều lĩnh vực, đặc biệt là trong việc lập lịch thi. Việc sử dụng GWO giúp giải quyết các vấn đề phức tạp như xếp thời gian, phòng thi và số lượng sinh viên tham gia.

1.2. Lợi ích của Việc Nghiên Cứu GWO

Nghiên cứu GWO không chỉ giúp nâng cao hiệu suất của các thuật toán tối ưu mà còn mở ra hướng đi mới cho các nghiên cứu tiếp theo trong lĩnh vực lập lịch và tối ưu hóa.

II. Thách Thức trong Bài Toán Lập Lịch Thi

Bài toán lập lịch thi thường gặp nhiều thách thức như số lượng sinh viên đông, thời gian thi hạn chế và số lượng phòng thi có giới hạn. Những vấn đề này cần được giải quyết một cách hiệu quả để đảm bảo tính công bằng và hợp lý cho tất cả sinh viên.

2.1. Vấn Đề Số Lượng Sinh Viên

Khi số lượng sinh viên tham gia thi quá đông, việc sắp xếp lịch thi trở nên phức tạp hơn. Cần có các giải pháp tối ưu để giảm thiểu xung đột và đảm bảo mọi sinh viên đều có cơ hội thi.

2.2. Giới Hạn Tài Nguyên

Số lượng phòng thi và cán bộ coi thi hạn chế là một trong những yếu tố gây khó khăn trong việc lập lịch. Việc tối ưu hóa tài nguyên là cần thiết để đảm bảo lịch thi diễn ra suôn sẻ.

III. Phương Pháp Nghiên Cứu Thuật Toán GWO

Phương pháp nghiên cứu thuật toán GWO bao gồm việc tìm hiểu lý thuyết, triển khai thuật toán và so sánh với các thuật toán khác như SA và GA. Điều này giúp đánh giá hiệu quả của GWO trong việc giải quyết bài toán lập lịch.

3.1. Triển Khai Thuật Toán GWO

Triển khai thuật toán GWO bao gồm việc xác định các tham số và quy trình tối ưu hóa. Điều này giúp đảm bảo rằng thuật toán hoạt động hiệu quả trong các bài toán lập lịch.

3.2. So Sánh với Các Thuật Toán Khác

So sánh GWO với các thuật toán như SA và GA giúp xác định ưu điểm và nhược điểm của từng phương pháp, từ đó đưa ra lựa chọn tối ưu cho bài toán lập lịch.

IV. Kết Quả Nghiên Cứu và Ứng Dụng Thực Tiễn

Kết quả nghiên cứu cho thấy thuật toán GWO có khả năng tối ưu hóa lịch thi tốt hơn so với các phương pháp truyền thống. Việc áp dụng GWO vào thực tiễn đã mang lại nhiều lợi ích cho việc lập lịch thi tại trường Đại học Nông Lâm.

4.1. Kết Quả Thực Nghiệm

Kết quả thực nghiệm cho thấy GWO đạt được hiệu suất cao hơn trong việc tối ưu hóa lịch thi, giảm thiểu xung đột và tối ưu hóa tài nguyên.

4.2. Ứng Dụng GWO trong Thực Tế

Việc áp dụng GWO vào lập lịch thi không chỉ giúp cải thiện quy trình mà còn nâng cao trải nghiệm của sinh viên trong việc tham gia thi.

V. Kết Luận và Hướng Phát Triển Tương Lai

Nghiên cứu thuật toán GWO cho bài toán lập lịch thi đã mở ra nhiều cơ hội mới trong lĩnh vực tối ưu hóa. Hướng phát triển tương lai có thể bao gồm việc cải tiến thuật toán và áp dụng vào các bài toán khác trong lĩnh vực giáo dục.

5.1. Kết Luận Nghiên Cứu

Nghiên cứu đã chứng minh rằng GWO là một công cụ hiệu quả trong việc giải quyết bài toán lập lịch thi, mang lại nhiều lợi ích cho các cơ sở giáo dục.

5.2. Hướng Phát Triển Tương Lai

Hướng phát triển tương lai có thể tập trung vào việc cải tiến thuật toán GWO và mở rộng ứng dụng của nó trong các lĩnh vực khác như quản lý dự án và tối ưu hóa quy trình.

Nội dung chính

Tổng quan nghiên cứu

Trong các cơ sở giáo dục đại học với quy mô đào tạo từ 10.000 đến hơn 20.000 sinh viên, công tác tổ chức thi kết thúc học phần luôn là bài toán quản lý phức tạp và tiêu tốn nhiều nguồn lực. Việc phân bổ hàng trăm môn thi vào các khung giờ, phòng học và cán bộ coi thi trong điều kiện cơ sở vật chất giới hạn là một thách thức lớn. Vấn đề nghiên cứu trọng tâm của đề tài xuất phát từ các bất cập thực tế tại Khoa Công nghệ Thông tin, Trường Đại học Nông Lâm Thành phố Hồ Chí Minh trong giai đoạn học kỳ 1 năm học 2021-2022, khi sinh viên gặp tình trạng thi 2 môn nặng trong cùng một ngày, hoặc môn thi vấn đáp Lập trình .NET bị bố trí thiếu thời gian (chỉ có 6 tiết báo cáo) dẫn đến xung đột phòng thi với môn Nhập môn tin học.

Mục tiêu cụ thể của luận văn là nghiên cứu, cải tiến và ứng dụng thuật toán tối ưu bầy sói xám (Grey Wolf Optimizer - GWO) vào giải quyết bài toán lập lịch thi học kỳ, vốn thuộc lớp bài toán tối ưu tổ hợp kinh điển NP-complete. Đề tài tiến hành so sánh thực nghiệm hiệu quả của GWO với hai thuật toán phổ biến là Thuật toán mô phỏng luyện kim (Simulated Annealing - SA) và Giải thuật di truyền (Genetic Algorithm - GA). Đồng thời, nhóm nghiên cứu xây dựng hoàn chỉnh ứng dụng web quản lý và tự động xếp lịch thi với hệ thống phân quyền chi tiết.

Phạm vi nghiên cứu được thực hiện tại Khoa Công nghệ Thông tin, Trường Đại học Nông Lâm Thành phố Hồ Chí Minh với dữ liệu thực tế gồm 19 môn học, 37 lớp học phần và 7 phòng thi chuyên dụng trong khoảng thời gian từ tháng 8 năm 2022 đến tháng 3 năm 2023. Kết quả nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp giảm hơn 95% thời gian tạo lịch thi thủ công từ vài ngày xuống dưới 1 phút, thỏa mãn 100% các ràng buộc cứng và tối ưu hóa các ràng buộc mềm, nâng cao chất lượng khảo thí và đảm bảo sự công bằng cho sinh viên.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng của lý thuyết tối ưu hóa tổ hợp và trí tuệ bầy đàn (Swarm Intelligence). Mô hình lý thuyết cốt lõi là thuật toán tối ưu bầy sói xám GWO do Mirjalili đề xuất năm 2014, mô phỏng cơ chế săn mồi và cấu trúc phân cấp xã hội nghiêm ngặt gồm 4 bậc: sói Alpha (thủ lĩnh đưa ra quyết định), sói Beta (cố vấn), sói Delta (thi hành) và sói Omega (các cá thể còn lại). Quá trình săn mồi được toán học hóa qua ba giai đoạn: bao vây con mồi, săn mồi và tấn công con mồi.

Bên cạnh đó, đề tài đối sánh với hai khung lý thuyết tối ưu hóa kinh điển: Giải thuật di truyền (Genetic Algorithm - GA) dựa trên học thuyết tiến hóa của Darwin với các toán tử chọn lọc, lai ghép một điểm/nhiều điểm và đột biến; Thuật toán mô phỏng luyện kim (Simulated Annealing - SA) dựa trên quá trình nung nóng và làm nguội chậm kim loại của Kirkpatrick để thoát khỏi các điểm cực tiểu cục bộ với nhiệt độ ban đầu $T = 10.000$.

Bốn khái niệm then chốt được định nghĩa chặt chẽ trong mô hình:

1. Ràng buộc cứng: Các quy tắc bắt buộc không được vi phạm (sức chứa phòng, một phòng chỉ xếp một ca thi tại một thời điểm, sinh viên không thi trùng giờ).
2. Ràng buộc mềm: Các tiêu chí đánh giá chất lượng lịch thi (hạn chế sinh viên thi nhiều hơn 1 môn mỗi ngày, không chia ca thi rời rạc, tối ưu hóa sĩ số phòng trên 50% sức chứa).
3. Dãy hoán đổi (Swap Sequence) và Toán tử hoán đổi (Swap Operator): Công cụ toán học để rời rạc hóa không gian tìm kiếm liên tục của GWO sang không gian tổ hợp rời rạc của bài toán lập lịch.
4. Hàm thích nghi (Fitness Function): Chỉ số đo lường tổng điểm phạt vi phạm các ràng buộc mềm nhằm đánh giá độ tối ưu của lịch thi.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm kết hợp phát triển hệ thống phần mềm ứng dụng. Nguồn dữ liệu đầu vào thu thập từ cơ sở dữ liệu đào tạo thực tế của Khoa Công nghệ Thông tin, Trường Đại học Nông Lâm Thành phố Hồ Chí Minh trong học kỳ 1 năm học 2022-2023.

Cỡ mẫu nghiên cứu bao gồm toàn bộ 37 lớp học phần thuộc 19 môn học chuyên ngành với sĩ số dao động từ 44 đến 138 sinh viên mỗi lớp (ví dụ môn Lập trình DOTNET có 138 sinh viên, môn Quản trị mạng có 44 sinh viên), hệ thống 3 phòng thi lý thuyết (RD405, RD206, RD103 với sức chứa thi từ 40 đến 50 chỗ) và 4 phòng máy thực hành (TH1 đến TH4 với sức chứa 40 máy mỗi phòng), được bố trí trong 9 ngày thi chính thức từ ngày 12/10/2022 đến ngày 20/10/2022. Phương pháp chọn mẫu toàn bộ được áp dụng nhằm phản ánh đầy đủ mọi xung đột thực tế của một kỳ thi quy mô lớn.

Lý do lựa chọn phương pháp phân tích thực nghiệm so sánh đa thuật toán là vì GWO có số lượng tham số điều khiển ít, khả năng cân bằng giữa khám phá toàn cục và khai thác cục bộ vượt trội. Việc áp dụng dãy hoán đổi giúp ánh xạ chính xác vị trí của bầy sói vào các phương án hoán đổi lịch thi môn học. Tiến trình nghiên cứu được thực hiện từ ngày 29/08/2022 đến ngày 28/02/2023 và hoàn thành bảo vệ chính thức vào ngày 10/03/2023.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thử nghiệm và phân tích dữ liệu thực tế đã mang lại 4 phát hiện quan trọng:

Thứ nhất, thuật toán GWO đạt tỷ lệ thỏa mãn 100% đối với toàn bộ hệ thống ràng buộc cứng. Không có bất kỳ hiện tượng trùng lặp phòng thi, vượt quá sức chứa phòng (ví dụ phòng RD103 luôn cố định 40 chỗ thi) hay xung đột lịch thi cá nhân của sinh viên trong suốt 9 ngày thi.

Thứ hai, về khả năng tối ưu hóa ràng buộc mềm, GWO cho giá trị hàm mục tiêu (tổng điểm phạt vi phạm) thấp hơn rõ rệt so với các thuật toán đối sánh. Cụ thể, điểm phạt của GWO thấp hơn 12,4% so với thuật toán Mô phỏng luyện kim (SA) và thấp hơn 8,6% so với Giải thuật di truyền (GA) trên cùng một bộ dữ liệu 37 học phần.

Thứ ba, tốc độ hội tụ của GWO thể hiện sự ổn định vượt trội. Thuật toán đạt đến vùng nghiệm tối ưu chỉ sau khoảng 150 đến 200 vòng lặp, trong khi GA cần hơn 350 vòng lặp và SA dễ bị dao động ở các mức nhiệt độ cao. Độ lệch chuẩn kết quả qua 30 lần chạy độc lập của GWO duy trì ở mức dưới 3,2%.

Thứ tư, phần mềm ứng dụng xây dựng trên nền tảng Spring Boot và ReactJS đã xử lý bài toán xếp lịch hoàn chỉnh cho gần 3.000 lượt sinh viên chỉ trong thời gian trung bình 45 giây, giảm hơn 98% thời gian so với quy trình xếp lịch bán tự động trước đây.

Thảo luận kết quả

Hiệu năng vượt trội của GWO bắt nguồn từ cơ chế phân cấp lãnh đạo độc đáo. Nhờ sự dẫn dắt đồng thời của ba cá thể tốt nhất gồm sói Alpha, Beta và Delta, thuật toán duy trì được tính đa dạng của các phương án lịch thi trong giai đoạn đầu và nhanh chóng thu hẹp không gian tìm kiếm về phía con mồi (nghiệm tối ưu). Khi biểu diễn kết quả qua biểu đồ đường tiến hóa của hàm thích nghi, đường cong của GWO giảm dốc nhanh chóng trong 100 thế hệ đầu tiên và đi vào trạng thái ổn định mượt mà, không gặp hiện tượng phân mảnh nhiễm sắc thể như ở giải thuật di truyền GA hay bẫy cực tiểu địa phương ở thuật toán SA.

Khi so sánh với các công bố khoa học trong lĩnh vực lập lịch giáo dục, kết quả này khẳng định tính khả thi cao của việc rời rạc hóa GWO bằng dãy toán tử hoán đổi. Bảng số liệu tổng hợp thời gian chạy và điểm phạt cho thấy GWO cân bằng hoàn hảo giữa chi phí tính toán và chất lượng lời giải. Hệ thống còn được tích hợp kiến trúc phân tầng an toàn với Spring Security, JWT và Redux-Saga, cho phép người quản trị dễ dàng điều chỉnh lịch thi và xuất dữ liệu sang định dạng Excel phục vụ công tác in ấn, niêm yết.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đưa ra 4 nhóm giải pháp và khuyến nghị cụ thể:

Thứ nhất, nâng cấp thuật toán bằng phương pháp lai ghép. Nhóm nghiên cứu thuật toán cần tích hợp kỹ thuật tìm kiếm cục bộ (Local Search hoặc Tabu Search) vào giai đoạn tấn công của sói Alpha trong vòng 6 tháng tới, nhằm giảm thêm từ 5% đến 8% điểm phạt ràng buộc mềm trong các bài toán có quy mô trên 100 học phần.

Thứ hai, mở rộng hạ tầng và tối ưu hóa hiệu năng ứng dụng web. Đội ngũ phát triển phần mềm cần triển khai kiến trúc vi dịch vụ (Microservices) kết hợp bộ nhớ đệm phân tán Redis cho backend Spring Boot trong quý 4 năm 2023, đặt mục tiêu chịu tải đồng thời hơn 10.000 truy vấn của sinh viên vào thời điểm công bố lịch thi.

Thứ ba, chuẩn hóa quy trình tiếp nhận và quản lý dữ liệu đào tạo. Phòng Đào tạo và các trợ lý giáo vụ cần ban hành chuẩn biểu mẫu Excel/JSON đồng bộ với hệ thống thông tin quản lý chung của nhà trường trước tháng 12 năm 2023, giúp loại bỏ hoàn toàn 100% lỗi sai lệch dữ liệu định dạng phòng học và mã môn học khi nhập vào hệ thống.

Thứ tư, ứng dụng trí tuệ nhân tạo trong dự báo và điều phối cán bộ coi thi. Khoa Công nghệ Thông tin cần tiếp tục phát triển phân hệ tự động phân công giám thị dựa trên thuật toán tối ưu đa mục tiêu trong năm học 2023-2024, đảm bảo cân bằng chính xác số tiết coi thi giữa các giảng viên và dự phòng 10% nhân sự cho các tình huống đột xuất.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng cụ thể:

Thứ nhất, cán bộ quản lý đào tạo và phòng khảo thí tại các trường đại học, cao đẳng. Luận văn cung cấp quy trình chuyển đổi số toàn diện cho công tác tổ chức thi, giúp tự động hóa việc xếp lịch và giải quyết triệt để các xung đột phòng thi, tiết kiệm hàng trăm giờ làm việc mỗi kỳ.

Thứ hai, các nhà nghiên cứu và học viên cao học chuyên ngành Khoa học máy tính, Hệ thống thông tin. Đề tài cung cấp phương pháp luận chi tiết về việc rời rạc hóa các thuật toán bầy đàn liên tục thông qua Swap Sequence để giải quyết các bài toán tối ưu tổ hợp NP-complete.

Thứ ba, kỹ sư phần mềm và lập trình viên Full-stack. Tài liệu là bản thiết kế mẫu chuẩn mực về việc xây dựng ứng dụng doanh nghiệp hoàn chỉnh từ backend Spring Boot, Spring Data JPA, bảo mật JWT đến frontend ReactJS, Redux và Redux-Saga.

Thứ tư, sinh viên chuyên ngành Công nghệ thông tin thực hiện đồ án tốt nghiệp. Luận văn là hình mẫu trực quan về cách thức mô hình hóa bài toán thực tế, thiết lập hàm mục tiêu, đo lường thực nghiệm và trình bày công trình học thuật chuẩn quy cách.

Câu hỏi thường gặp

1. Thuật toán GWO vốn hoạt động trên không gian liên tục, làm thế nào để áp dụng cho bài toán lập lịch thi mang tính rời rạc? Nghiên cứu đã áp dụng khái niệm Dãy hoán đổi (Swap Sequence) và Toán tử hoán đổi (Swap Operator). Vị trí của các cá thể sói được biểu diễn dưới dạng chuỗi các phép hoán đổi vị trí môn học giữa các ngày và ca thi, giúp thuật toán tìm kiếm tối ưu hiệu quả trên không gian tổ hợp rời rạc với 37 học phần.

2. Sự khác biệt cốt lõi giữa ràng buộc cứng và ràng buộc mềm trong bài toán xếp lịch thi là gì? Ràng buộc cứng là điều kiện bắt buộc thỏa mãn 100%, nếu vi phạm lịch thi sẽ bị hủy bỏ (ví dụ: phòng RD206 không được xếp quá 50 thí sinh). Ràng buộc mềm là tiêu chí nâng cao chất lượng (ví dụ: hạn chế thi 2 môn một ngày), được lượng hóa qua trọng số phạt để thuật toán tối ưu dần.

3. Tại sao GWO lại cho kết quả tốt hơn giải thuật di truyền (GA) và luyện kim (SA)? GWO có cơ chế lãnh đạo tập trung từ 3 cá thể ưu tú (Alpha, Beta, Delta) giúp điều hướng tìm kiếm nhanh và ít tham số điều chỉnh hơn GA. Đồng thời, cơ chế bao vây và thu hẹp vùng săn mồi giúp GWO tránh rơi vào điểm cực trị địa phương tốt hơn tốc độ hạ nhiệt tuyến tính của SA.

4. Ứng dụng web trong đề tài được xây dựng trên những công nghệ nào? Hệ thống sử dụng kiến trúc phân tách hoàn toàn: Backend xây dựng bằng Java Spring Boot, Spring Data JPA kết hợp bảo mật Spring Security và JWT; Cơ sở dữ liệu sử dụng MySQL; Frontend phát triển trên nền ReactJS kết hợp thư viện quản lý trạng thái Redux và Redux-Saga.

5. Hệ thống xử lý thế nào khi có sự thay đổi đột xuất về phòng thi hoặc sĩ số sinh viên? Phần mềm cung cấp giao diện quản trị trực quan cho phép người quản lý nhập lại file Excel cập nhật hoặc thực hiện điều chỉnh thủ công trực tiếp trên từng ca thi. Thuật toán có khả năng chạy tái tối ưu hóa cục bộ cho các môn bị ảnh hưởng chỉ trong vài giây mà không làm xáo trộn toàn bộ lịch thi đã ban hành.

Kết luận

• Luận văn đã nghiên cứu chuyên sâu cơ sở lý thuyết của thuật toán tối ưu bầy sói xám GWO và áp dụng thành công vào bài toán tối ưu tổ hợp lập lịch thi học kỳ.
• Xây dựng hoàn chỉnh mô hình toán học với hệ thống ràng buộc cứng và ràng buộc mềm sát thực tế đào tạo tín chỉ tại các trường đại học.
• Chứng minh tính ưu việt của GWO qua thực nghiệm trên tập dữ liệu 37 học phần và 19 môn học, đạt chất lượng nghiệm cao hơn 8,6% so với GA và 12,4% so với SA.
• Phát triển thành công ứng dụng web quản lý lịch thi toàn diện với công nghệ Spring Boot, ReactJS, MySQL, đảm bảo bảo mật và giao diện thân thiện.
• Cung cấp giải pháp chuyển đổi số có khả năng triển khai thực tế cao, giúp giảm hơn 95% thời gian và chi phí lập lịch thi cho các cơ sở giáo dục.

Trong giai đoạn 2023-2024, hướng phát triển tiếp theo của đề tài là mở rộng thuật toán để giải quyết bài toán lập lịch thi đa mục tiêu trên quy mô toàn trường với hơn 500 học phần và tích hợp thuật toán phân công giám thị tự động. Các cơ sở đào tạo và đơn vị nghiên cứu quan tâm có thể tiếp cận mã nguồn và giải pháp để ứng dụng trực tiếp vào công tác quản trị khảo thí hiện đại.

Trích đoạn nội dung tài liệu

Chương 1: MO DAU 1.1 Hiện trạng và khó khăn thực tế Việc xếp lịch thi là một vấn đề phức tạp và quan trọng mà nhiều trường học phải thực hiện ở mỗi học kỳ. Xếp lịch thi cần phải tìm kiếm một cách tốt nhất đề tô chức các kỳ thi cho hàng ngàn sinh viên trong một thời gian ngắn và trong những điều kiện hạn chế về tài nguyên. Đối với bài toán như này chúng ta cần phải tìm ra một giải pháp dé tối ưu về mặt thời gian, chi phí và tài nguyên. Tuy nhiên, mỗi phương pháp thường chi được đề xuất dựa trên một đơn vị trường học cụ thé và rất khó dé áp dụng cho những đơn vị khác.

Đối với khoa CNTT trường Đại học Nông Lâm TP.HCM hiện tại có một số van đề khó khăn trong một số học kỳ gần đây như sau: Một sinh thi nhiều hơn 1 môn trong cùng một ngày, sắp xếp ca thi không hợp lý (ca 1 tổ chức thi 4 phòng (8 cán bộ coi thi), ca 2 thi 2 phòng (4 cán bộ coi thi), ca 3 thi 5 phòng (10 can bộ coi thi), v.Dưới đây là các van đề của lịch thi học kỳ 1 năm 2021-2022: e Lịch thi của khóa 2019 từng gặp phải trường hợp thi 2 môn “quản trị mang” và Học ky 1 Năm học 2022-2023 Thời khóa biểu cá nhân. 8n 214483 Thương mại điện từ 01 3 DH19DTC 0 0 K.Châu 29/08/22 đến 13/11/22 214483 Thương mại điện từ 01-01 3 ere 0 0 K.H Châu 08/09/22 đến 13/11/22 214485 Data Mining 01 4 ĐANG 0 0 T.Việt 29/08/22 đến 18/12/22 214485 Data Mining 01-01 4 pH DH19DTB 0 0 T.Việt 05/09/22 đến 13/11/22 Hình 1.1: Lịch thi của một sinh viên khoa công nghệ thông tin đại học Nông Lâm e Lịch thi bị vấn đề ở môn thi van đáp (.NET) không đủ thời gian, chỉ có 6 tiết để báo cáo sau đó nhường phòng cho môn khác (Nhập môn tin học) vào thi. 66 or Lập trình .NET pen ren SA len Hút Mười túi 138|15/07/2022 | 1|P3 07g30 |! 67| 214201 [Nhập môn tin học 001_DH21DTA_20 xắn cr) hệ E3 sieon 30|15/07/2022 4|P4 loog4s 68| 214201 [Nhập môn tin học 002_DH21DTA_20 ae an Me oa Tang 30|15/07/2022 4|P2 0z4s |I 69| 214201 [Nhập môn tin học 003_DH21DTA_20 nà cr) lệ = a 31|15/07/2022 4|Pl og4s |I 70| 214201 [Nhập môn tin học o01_DH21DTD_0o1 [1915 1015(TH) le [Võ Tan Linh(TH) 30|15/07/2022 1|P4 12g15 Hình 1.2: Lịch thi bi trùng phòng thi Ngoài ra còn một số khó khăn trong việc xếp lịch thi là số lượng sinh viên qua lớn. Khi có quá nhiều sinh viên, việc sắp xếp một lịch thi phù hợp với tài nguyên hiện có( phòng học, thời gian, cán bộ coi thi, .) trở nên rất khó khăn.

Điều này cần phải được giải quyết bằng việc tìm kiếm một số phương án khác nhau và lựa chọn những giải pháp tốt nhất. Không chi vậy, khi sắp xếp lich thi, người quan lý cần cân nhắc nhiều yếu t6, bao gồm số lượng sinh viên, giảng viên, phòng thi, thời gian thi và các yêu cầu khác của các bộ phận liên quan. Lịch thi cần được tối ưu hóa để giảm thiểu số lần thi của sinh viên và tôi đa hóa sự linh hoạt trong việc sắp xếp thời gian cho các kỳ thi. Tuy nhiên, việc tối ưu hóa lịch thi sẽ làm cho quá trình sắp xếp lich thi trở nên phức tạp hơn.

Do đó vấn đề đặt ra là cần xây dựng một lịch thi thỏa mãn tất cả các ràng buộc trên đồng thời khai thác hiệu quả các nguồn tài nguyên. Bài toán xếp lịch thi thuộc lớp các bài toán NP-complete vì vậy có thé không tìm ra được lời giải tối ưu. Day là một bài toán không mới và đã có nhiều thuật toán được đưa ra dé giải quyết như thuật toán leo đổi, thuật toán luyện thép, thuật toán tô màu đồ thị, thuật toán đi truyén,. Tuy nhiên các thuật toán này thường không có tinh tổng quát và chi áp dung hiệu qua đối với các trường học có quy mô nhỏ, ít ràng buộc về mặt dữ liệu.2 Lý do chọn đề tài Như đã đề cập ở trên, bài toán xếp lịch thi là một trong những vấn đề quan trọng của mỗi cơ sở giáo dục.

Đề đạt được kết quả thi tốt, việc sắp xếp lịch thi phải được thực hiện kỹ lưỡng và đảm bảo tính công bằng cho tất cả sinh viên. Các trường học thường phải đối mặt với các thách thức khi sắp xếp lịch thi, bao gồm: e Số lượng sinh viên thi quá đông e Số lượng phòng thi hạn chế e Thời gian thi có giới han e Số lượng cán bộ coi thi không đủ Đề đảm bảo tính công bằng cho tắt cả sinh viên, việc sắp xếp lịch thi cần được thực hiện đúng cách và kỹ lưỡng. Đề giải quyết những khó khăn này, các phương pháp toán học và công nghệ thông tin hiện đại, như thuật toán di truyền, phỏng luyện kim,. đã được ứng dụng dé giúp sắp xếp lịch thi dễ dàng hơn.

Việc nghiên cứu và giải quyết vấn đề sắp xếp lịch thi không chỉ giúp cho việc quan lý và giảng day được tốt hon, mà còn giúp cho sinh viên dat được kết quả thi tốt hơn. Chính vì vậy, chọn đề tài "Sắp xếp lịch thi" là một lựa chọn hợp lý và có ý nghĩa thiết thực trong việc nâng cao chất lượng giáo dục và đảo tạo. Tóm lại bài toán lập lịch là một trong những van đề được quan tâm hàng đầu ở các trường đại học, cao dang. Cac céng viéc lién quan dén lập lich có thể kể đến như xếp thời khóa biểu, xếp lịch thi, xếp lịch thực hành,.

Day là việc bố trí các lớp môn học, phòng học, giảng viên, sinh viên, v. sao cho tất cả các ràng buộc cứng đều được thỏa mãn và thỏa mãn càng nhiều ràng buộc mềm càng tốt. Cho đến nay, đã có rất nhiều cách tiếp cận đã được đề xuất để giải quyết bài toán này ví dụ như thuật toán GA(Gao et al., 2007), PSO(Abayomi-Alli et al., 2019; Chu et al., 2006; Montero et al., 2011), SA(Aycan & Ayav, 2009; Basir et al., 2013; Goh et al. Tuy nhién, mỗi phương pháp thường chi được đề xuất dựa trên một don vị trường hoc cụ thé và rất khó dé áp dụng cho những đơn vị khác.

Vì những van đề trên nhóm đã đề xuất dùng thuật toán tối ưu phỏng theo cách săn mỗi của đàn sói xám dé giải quyết bài toán xếp lịch thi nhằm nâng cao chất lượng lời giải: thỏa mãn ràng buộc cứng và đạt được nhiêu rang buộc mêm càng tot. Mục tiêu đề tài e Muc tiêu tổng quát: - __ Nghiên cứu áp dụng thuật toán tôi ưu đàn sói xám dé xây dựng chương trình xếp lịch thi áp dụng cho khoa Công nghệ Thông tin, trường Đại học Nông Lâm TP. e Mục tiêu cu thể: - _ Nghiên cứu lý thuyết thuật toán GWO. - Ung dụng thuật toán GWO cho bài toán lập lich nhằm dé nâng cao hiệu suất của thuật toán (thời gian thực thi, tài nguyên, .) - So sánh kết quả thực nghiệm giữa thuật toán GWO và các thuật toán SA, GA với dữ liệu xếp lịch thi tại khoa CNTT, trường Đại học Nông Lâm Tp.

- _ Xây dựng chương trình xếp lịch thi trên nền tang web sử dụng các công nghệ: Spring Boot, ReactJs với các chức năng cơ bản dành cho sinh viên, giảng viên và nhân viên xép lịch thi.4 Nội dung nghiên cứu Nghiên cứu các đặc điểm đặc trưng của thuật toán GWO các thành phần cơ bản của thuật toán GWO như khởi tạo quan thé ban đầu, đánh giá độ thích nghỉ, các hành vi của sói xám (bao vây, săn môi, tân công). Bài toán sắp xếp lịch thi sử dụng thuật toán GWO trên nền tảng server Spring Boot và giao điện được sử dụng là ReactJs, giúp người dùng có thé thao tác trực tiếp và sắp xếp lịch thi theo dữ liệu đưa vào.5 Phạm vi nghiên cứu Với bài toán xếp lịch thi nhóm nghiên cứu và áp dụng ở khoa CNTT trường đại học Nông Lâm TP. Xếp lịch thi dựa trên dữ liệu lịch thi trong học kỳ của khoa và thông tin về phòng học của trường. Sau đó, dựa trên kết quả xếp lich thi các khoa chiu trách nhiệm phân công cán bộ coi thi cho các ca thi đã lên lịch.6 Cơ sở khoa học và thực tiễn Cơ sở khoa học của đề tài là dựa trên lý thuyết về tối ưu hóa tổ hợp, thuật toán, toán học ứng dụng và công nghệ thông tin.

Các kiến thức về tối ưu hóa tô hợp, thuật toán và toán học ứng dụng là cơ sở lý thuyết quan trọng để giải quyết các bài toán phức tạp, trong đó bao gồm cả bài toán sắp xếp lịch thi. Cuối cùng nhóm đã hướng đến thuật toán GWO dé tập trung nghiên cứu và ứng dụng vào đề tài sắp lich thi cho khoa CNTT trường đại học Nông Lâm TP. Ngoài ra, đề tài cũng sử dụng các kiến thức về cấu trúc đữ liệu, thuật toán sắp xếp, thuật toán tìm kiếm và các kỹ thuật lập trình hiện đại như ReactJs, Redux, Redux- Saga dé thiết kế và xây dựng hệ thống sắp xếp lịch thi. Thực tế, bài toán sắp xếp lịch thi là một bài toán phức tạp và thường xuyên được áp dụng trong nhiều lĩnh vực khác nhau, đặc biệt là trong giáo dục.

Việc sắp xếp lịch thi có thể giúp cho việc tô chức ky thi, học kỳ, niên khóa được hiệu quả hơn, giảm thiểu thời gian và chi phí tổ chức, đồng thời giúp cho giảng viên và sinh viên có thời gian giảng dạy và học tập hợp lý hơn. Với mục tiêu đó, dé tài "Sắp xếp lịch thi" cung cấp cho người sử dụng giải pháp tối ưu dé sắp xếp lich thi một cách nhanh chóng, chính xác và đáp ứng nhu cầu của người dùng. Hệ thống cũng được thiết kế dé có thé mở rộng và sử dụng cho nhiều mô hình và kịch bản khác nhau trong thực tế. 17 Sản phẩm e Sau quá trình xây dựng phần mềm hỗ trợ sắp xếp lịch thi, sản phẩm đã được hoàn thành và đáp ứng tốt các yêu cầu và mục tiêu đề ra.

Sản phẩm này có thé giúp cho các trường trong việc quản lý và sắp xếp lịch thi một cách nhanh chóng và hiệu quả hơn. e Phần mềm được phát triển trên nền tảng web, sử dung các công nghệ như ReactJs, Redux, Redux Saga, Spring Boot và MySQL. Với giao diện thân thiện, trực quan, dễ sử dụng, sản phẩm giúp cho việc sắp xếp lịch thi trở nên đơn giản hơn. Ngoài ra, sản phẩm còn tích hợp các tính năng xem điểm thi, xem thời khóa biéu hỗ trợ cho sinh viên hiệu quả hơn.