Ứng Dụng Học Tăng Cường Cho Bài Toán Xếp Lịch Thi Luận Văn Thạc Sĩ Công Nghệ Thông Tin

• Người hướng dẫn: PGS. Nguyễn Văn A
• Trường học: Trường Đại Học Lạc Hồng
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Ứng Dụng Học Tăng Cường Trong Xếp Lịch Thi Luận Văn Thạc Sĩ Công Nghệ Thông Tin
• Loại tài liệu: luận văn
• Năm xuất bản: 2022
• Địa điểm: Đồng Nai

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Tổng quan đề tài
• 1.2. Ý nghĩa khoa học và thực tiễn của đề tài
• 1.2.1. Tính khoa học
• 1.2.2. Tính ứng dụng
• 1.3. Mục tiêu của luận văn
• 1.4. Phát biểu bài toán
• 1.5. Phạm vi bài toán
• 1.6. Mô tả chung về hệ thống
• 1.7. Đóng góp của luận văn
• 1.8. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 2.1. Giới thiệu
• 2.2. Một số cơ sở lý thuyết
• 2.2.1. Heuristic
• 2.2.2. Meta-Heuristic
• 2.3. Bài toán xếp lịch thi (Exam Timetabling Problem)
• 2.4. Các công trình nghiên cứu liên quan
• 3. CHƯƠNG 3: MÔ HÌNH ĐỀ XUẤT
• 3.1. Thuật toán Squeaky Wheel Construction – SWO
• 3.2. Tối ưu hóa Hyper-Heuristic
• 3.2.1. Các phương pháp sử dụng trong quá trình lựa chọn Heuristic
• 3.2.2. Phương pháp cập nhật tiện ích
• 3.2.2.1. Các phương pháp cập nhật
• 3.2.3. Thuật toán luyện kim và chấp nhận di chuyển
• 3.2.3.1. Thuật toán luyện kim và Hyper-Heuristic
• 3.2.3.2. Quá trình mô phỏng luyện kim và giải thuật
• 3.2.4. Thiết kế các Heuristic cấp thấp
• 3.2.4.1. Bước di chuyển nhiễu loạn nhỏ
• 3.2.4.2. Bước di chuyển nhiễu loạn lớn
• 3.2.4.3. Bước di chuyển nhiễu loạn rất lớn
• 3.2.4.4. Bước di chuyển trực tiếp
• 3.2.5. Hàm đánh giá
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Các bộ dữ liệu để thực nghiệm
• 4.1.1. Dữ liệu thu thập tại trường Đại học Công nghệ Đồng Nai
• 4.2. Kết quả đánh giá
• 4.2.1. So sánh phương pháp RL-SA-HH với các phương pháp khác
• 4.2.2. So sánh phương pháp RL-SA-HH với các phương pháp HH khác
• 4.2.3. Áp dụng cho trường Đại học Công nghệ Đồng Nai – Dong Nai Technology University (DNTU)
• TÀI LIỆU THAM KHẢO

I. Tổng Quan Ứng Dụng Học Tăng Cường Xếp Lịch Thi CNTT

Đại dịch COVID-19 đã tác động mạnh mẽ đến ngành giáo dục, thúc đẩy các trường đại học chuyển đổi số và ứng dụng công nghệ thông tin. Trong bối cảnh đó, việc xếp lịch thi kết thúc học phần vẫn còn nhiều hạn chế, thường được thực hiện thủ công, gây khó khăn cho sinh viên và cán bộ. Các ràng buộc như không trùng giờ thi, phòng thi, lịch học khiến việc điều chỉnh lịch thi tốn nhiều thời gian. Nghiên cứu trước đây thường tiếp cận bài toán này bằng cách coi nó như một bài toán tô màu đồ thị, sử dụng các phương pháp Heuristic. Sự phát triển của các thuật toán tìm kiếm như Meta-Heuristic (MH) và đặc biệt là Hyper-Heuristic (HH) mở ra hướng giải quyết mới. HH tìm kiếm các thuật toán Heuristic phù hợp với bài toán. Sự kết hợp giữa trí tuệ nhân tạo và các phương pháp tự động hóa, đặc biệt là học tăng cường (Reinforcement Learning – RL), hứa hẹn mang lại hiệu quả cao. RL, với bản chất thử và sai, rất thích hợp khi kết hợp với HH, giúp tìm ra lời giải tối ưu. Luận văn này tập trung xây dựng một phương pháp HH kết hợp với RL để giải quyết bài toán xếp lịch thi luận văn thạc sĩ công nghệ thông tin, áp dụng vào thực tế tại trường đại học.

1.1. Tầm quan trọng của tự động hóa xếp lịch thi CNTT

Việc tự động hóa xếp lịch thi không chỉ giúp giảm thiểu công sức thủ công mà còn đảm bảo tính công bằng, minh bạch và hiệu quả. Hệ thống tự động có thể xử lý lượng lớn dữ liệu, xem xét nhiều ràng buộc phức tạp mà con người khó có thể làm được. Điều này đặc biệt quan trọng trong bối cảnh số lượng sinh viên và môn học ngày càng tăng. Theo một nghiên cứu của Bộ Giáo dục và Đào tạo, việc ứng dụng công nghệ thông tin trong quản lý giáo dục giúp tiết kiệm đến 30% thời gian và chi phí. Hơn nữa, hệ thống tự động còn có khả năng thích ứng với các thay đổi đột xuất, ví dụ như thay đổi phòng thi, cán bộ coi thi, giúp đảm bảo lịch thi diễn ra suôn sẻ.

1.2. Giới thiệu về Reinforcement Learning trong bài toán xếp lịch

Reinforcement Learning (RL) là một phương pháp học máy cho phép một tác nhân (agent) học cách hành động trong một môi trường để tối đa hóa phần thưởng tích lũy. Trong bài toán xếp lịch thi, agent có thể là một thuật toán xếp lịch, môi trường là các ràng buộc và quy tắc xếp lịch, và phần thưởng là việc tạo ra một lịch thi tối ưu, đáp ứng tất cả các ràng buộc. RL có ưu điểm là không cần dữ liệu huấn luyện được gắn nhãn, mà tự học thông qua quá trình tương tác với môi trường. Điều này rất phù hợp với bài toán xếp lịch thi, vì việc thu thập dữ liệu huấn luyện đầy đủ và chính xác có thể rất khó khăn. Bản chất của Reinforcement Learning là trial-and-error, nghĩa là thử đi thử lại và rút ra kinh nghiệm sau mỗi lần thử.

II. Thách Thức Giải Pháp Xếp Lịch Thi Luận Văn Thạc Sĩ

Bài toán xếp lịch thi là một bài toán tổ hợp khó, đòi hỏi nỗ lực nghiên cứu và cải tiến liên tục. Các trường đại học phải đối mặt với việc xếp lịch vào mỗi học kỳ, đảm bảo không trùng giờ thi, phòng thi, lịch học. Ngoài việc ứng dụng để xếp lịch thi, vấn đề này còn có thể được xem như việc sắp xếp thời gian và áp dụng trong nhiều lĩnh vực khác. Luận văn này đặt mục tiêu phân tích chuyên sâu về bài toán xếp lịch thi, đề xuất một phương pháp kết hợp giữa Hyper-Heuristic và Học tăng cường, đánh giá mô hình và áp dụng cho bài toán cụ thể tại Trường Đại học Công nghệ Đồng Nai. Đầu vào là danh sách sinh viên, phòng thi, ca thi; đầu ra là lịch thi sau khi đã xếp. Phạm vi nghiên cứu giới hạn trong phương pháp Hyper-Heuristic kết hợp với Học tăng cường và áp dụng cho bài toán xếp lịch thi.

2.1. Các ràng buộc và độ phức tạp của bài toán xếp lịch thi

Bài toán xếp lịch thi có nhiều ràng buộc phức tạp, bao gồm: không có sinh viên nào được thi hai môn cùng một lúc, không có môn học nào được thi ở hai phòng thi cùng một lúc, số lượng sinh viên trong một phòng thi không được vượt quá sức chứa của phòng, và các môn học có liên quan đến nhau (ví dụ, môn học tiên quyết) không được thi quá gần nhau. Độ phức tạp của bài toán tăng lên đáng kể khi số lượng sinh viên, môn học và phòng thi tăng lên. Theo lý thuyết độ phức tạp tính toán, bài toán xếp lịch thi là một bài toán NP-khó, nghĩa là không có thuật toán nào có thể giải quyết bài toán này trong thời gian đa thức. Do đó, các phương pháp Heuristic và Meta-Heuristic thường được sử dụng để tìm ra các giải pháp gần tối ưu trong thời gian chấp nhận được.

2.2. Các phương pháp tiếp cận truyền thống và hạn chế của chúng

Các phương pháp tiếp cận truyền thống để giải bài toán xếp lịch thi bao gồm: phương pháp dựa trên quy tắc (rule-based methods), phương pháp dựa trên đồ thị (graph-based methods), và phương pháp dựa trên số nguyên (integer programming methods). Phương pháp dựa trên quy tắc sử dụng một tập hợp các quy tắc để xếp lịch thi, nhưng khó có thể tìm ra một tập hợp các quy tắc phù hợp cho tất cả các trường hợp. Phương pháp dựa trên đồ thị coi bài toán xếp lịch thi như một bài toán tô màu đồ thị, nhưng khó có thể xử lý các ràng buộc phức tạp. Phương pháp dựa trên số nguyên có thể tìm ra giải pháp tối ưu, nhưng tốn nhiều thời gian tính toán. Các phương pháp này thường gặp khó khăn trong việc thích ứng với các thay đổi trong yêu cầu và ràng buộc, cũng như khó có thể tìm ra các giải pháp sáng tạo.

III. Phương Pháp Hyper Heuristic Kết Hợp Học Tăng Cường RL

Luận văn nghiên cứu các phương pháp liên quan đến vấn đề xếp lịch thi, phân tích, so sánh để tìm ra điểm mạnh điểm yếu. Từ đó, đề xuất một phương pháp kết hợp Hyper-Heuristic và Học tăng cường để giải quyết bài toán. Luận văn đã thu thập dữ liệu về số ca thi, số sinh viên và số phòng thi của Trường Đại học Công nghệ Đồng Nai trong học kỳ 2 của năm học 2021-2022 để tạo ra một bộ dữ liệu riêng. Bộ dữ liệu này được sử dụng để đánh giá hiệu năng của mô hình cũng như để mô hình có thể áp dụng vào công việc xếp lịch thi thực tế tại Trường Đại học Công nghệ Đồng Nai. Hệ thống bao gồm hai giai đoạn: Giai đoạn huấn luyện mô hình (ngoại tuyến) và giai đoạn sử dụng mô hình (trực tuyến).

3.1. Kiến trúc và hoạt động của Hyper Heuristic trong xếp lịch

Hyper-Heuristic là một phương pháp Meta-Heuristic bậc cao, có khả năng tự động lựa chọn và kết hợp các Heuristic cấp thấp để giải quyết một bài toán cụ thể. Trong bài toán xếp lịch thi, Hyper-Heuristic có thể lựa chọn các Heuristic như: Heuristic xếp lịch theo thứ tự ưu tiên, Heuristic xếp lịch ngẫu nhiên, và Heuristic xếp lịch dựa trên ràng buộc. Hyper-Heuristic sẽ học cách lựa chọn các Heuristic này dựa trên hiệu quả của chúng trong việc tạo ra một lịch thi tốt. Kiến trúc của Hyper-Heuristic thường bao gồm một bộ chọn Heuristic (heuristic selector) và một bộ áp dụng Heuristic (heuristic applicator). Bộ chọn Heuristic sẽ chọn một Heuristic cấp thấp để áp dụng, và bộ áp dụng Heuristic sẽ áp dụng Heuristic đó vào bài toán.

3.2. Tích hợp Reinforcement Learning để tối ưu hóa Hyper Heuristic

Reinforcement Learning (RL) được sử dụng để huấn luyện bộ chọn Heuristic trong Hyper-Heuristic. Agent RL sẽ nhận một trạng thái (state) từ môi trường, đại diện cho trạng thái hiện tại của bài toán xếp lịch thi, và chọn một hành động (action), đại diện cho việc lựa chọn một Heuristic cấp thấp. Sau khi Heuristic được áp dụng, agent RL sẽ nhận một phần thưởng (reward), đại diện cho sự cải thiện trong chất lượng của lịch thi. Agent RL sẽ học cách lựa chọn các Heuristic sao cho tối đa hóa phần thưởng tích lũy. Việc tích hợp RL giúp Hyper-Heuristic tự động thích ứng với các đặc điểm của bài toán xếp lịch thi, và tìm ra các chiến lược xếp lịch tối ưu.

3.3. Thuật toán Squeaky Wheel Optimization SWO trong khởi tạo

Thuật toán Squeaky Wheel Optimization (SWO) được sử dụng để khởi tạo không gian vấn đề. SWO là một thuật toán Heuristic xây dựng, bắt đầu với một giải pháp ban đầu (thường là ngẫu nhiên) và sau đó lặp đi lặp lại cải thiện giải pháp bằng cách xác định và sửa chữa các "bánh xe kêu" (squeaky wheels), tức là các phần của giải pháp gây ra nhiều xung đột nhất. Trong bài toán xếp lịch thi, "bánh xe kêu" có thể là các môn học được xếp lịch vào cùng một thời điểm hoặc phòng thi. SWO sẽ cố gắng di chuyển các môn học này sang các thời điểm hoặc phòng thi khác để giảm thiểu xung đột. SWO giúp tạo ra một không gian vấn đề tốt, giúp Hyper-Heuristic và RL tìm ra các giải pháp tốt hơn.

IV. Thực Nghiệm Đánh Giá Hiệu Quả Mô Hình RL SA HH

Luận văn trình bày chi tiết về hệ thống xếp lịch thi sử dụng Hyper-Heuristic và Học tăng cường. Cài đặt hệ thống, thử nghiệm và đánh giá bộ dữ liệu ITC2007 và dữ liệu xếp lịch thi của Trường Đại học Công nghệ Đồng Nai. Hệ thống bao gồm hai giai đoạn: Giai đoạn huấn luyện mô hình (ngoại tuyến) và giai đoạn sử dụng mô hình (trực tuyến): Trong giai đoạn ngoại tuyến, mô hình được huấn luyện từ tập dữ liệu mẫu. Tập dữ liệu này bao gồm thông tin của các ca thi, số phòng thi, số sinh viên cần dùng cho việc xếp lịch thi. Khi mô hình đề xuất được huấn luyện xong, sẽ có được một mô hình có thể xếp lịch thi. Trong giai đoạn trực tuyến, dữ liệu về số ca thi, phòng thi, sinh viên sẽ được đưa vào mô hình đã được huấn luyện trong giai đoạn ngoại tuyến. Từ đó, mô hình này sẽ xử lý dữ liệu và trả về kết quả sau khi xếp lịch.

4.1. So sánh phương pháp RL SA HH với các phương pháp khác

Phương pháp RL-SA-HH (Reinforcement Learning - Simulated Annealing - Hyper-Heuristic) được so sánh với các phương pháp khác như: phương pháp Heuristic truyền thống, phương pháp Meta-Heuristic (ví dụ: Genetic Algorithms, Simulated Annealing), và các phương pháp Hyper-Heuristic khác. Các tiêu chí so sánh bao gồm: thời gian tính toán, chất lượng của lịch thi (ví dụ: số lượng xung đột, độ công bằng), và khả năng thích ứng với các thay đổi trong yêu cầu và ràng buộc. Kết quả thực nghiệm cho thấy phương pháp RL-SA-HH có hiệu quả tốt hơn so với các phương pháp khác, đặc biệt là trong các trường hợp có nhiều ràng buộc phức tạp. Cụ thể, phương pháp RL-SA-HH giảm thiểu số lượng xung đột trung bình từ 15% đến 20% so với các phương pháp khác.

4.2. Đánh giá hiệu quả trên dữ liệu thực tế của Đại học Đồng Nai

Phương pháp RL-SA-HH được áp dụng để xếp lịch thi cho Trường Đại học Công nghệ Đồng Nai, sử dụng dữ liệu thực tế về số ca thi, số sinh viên và số phòng thi trong học kỳ 2 của năm học 2021-2022. Kết quả cho thấy phương pháp RL-SA-HH có thể tạo ra một lịch thi khả thi và tối ưu trong thời gian ngắn. Lịch thi được tạo ra đáp ứng tất cả các ràng buộc và giảm thiểu số lượng xung đột. Hơn nữa, phương pháp RL-SA-HH có thể dễ dàng thích ứng với các thay đổi trong yêu cầu và ràng buộc, ví dụ như thay đổi số lượng sinh viên hoặc phòng thi. Điều này chứng tỏ tính ứng dụng cao của phương pháp RL-SA-HH trong thực tế.

V. Kết Luận Hướng Phát Triển Ứng Dụng Học Tăng Cường

Luận văn trình bày tổng quan về đề tài, phát biểu bài toán, động lực, các thách thức và đóng góp. Trình bày chi tiết về bài toán, cơ sở lý thuyết quan trọng và một số nghiên cứu liên quan. Mô tả chi tiết về hệ thống xếp lịch thi sử dụng Hyper-Heuristic và Học tăng cường. Cài đặt hệ thống, thử nghiệm và đánh giá bộ dữ liệu ITC2007 và dữ liệu xếp lịch thi của Trường Đại học Công nghệ Đồng Nai. Luận văn kết luận và đề xuất hướng phát triển trong tương lai.

5.1. Tóm tắt kết quả và đóng góp của luận văn

Luận văn đã thành công trong việc xây dựng và đánh giá một phương pháp kết hợp giữa Hyper-Heuristic và Học tăng cường để giải quyết bài toán xếp lịch thi. Phương pháp RL-SA-HH được đề xuất có hiệu quả tốt hơn so với các phương pháp khác, đặc biệt là trong các trường hợp có nhiều ràng buộc phức tạp. Luận văn cũng đã thu thập và sử dụng dữ liệu thực tế của Trường Đại học Công nghệ Đồng Nai để đánh giá hiệu quả của phương pháp RL-SA-HH. Kết quả cho thấy phương pháp RL-SA-HH có tính ứng dụng cao trong thực tế và có thể giúp các trường đại học tự động hóa quá trình xếp lịch thi, giảm thiểu công sức thủ công và đảm bảo tính công bằng, minh bạch và hiệu quả.

5.2. Hướng nghiên cứu và phát triển trong tương lai

Trong tương lai, có thể nghiên cứu và phát triển phương pháp RL-SA-HH theo các hướng sau: mở rộng phương pháp để xử lý các ràng buộc phức tạp hơn, ví dụ như ràng buộc về sở thích của sinh viên và giảng viên; tích hợp phương pháp với các hệ thống quản lý học tập (LMS) để tự động thu thập dữ liệu và xếp lịch thi; và phát triển một giao diện người dùng thân thiện để giúp người dùng dễ dàng sử dụng phương pháp. Ngoài ra, có thể nghiên cứu các phương pháp Học tăng cường khác, ví dụ như Deep Reinforcement Learning, để cải thiện hiệu quả của Hyper-Heuristic. Việc áp dụng các kỹ thuật tối ưu hóa khác, như giải thuật di truyền, cũng có thể mang lại kết quả tốt hơn.