Ứng Dụng Trí Tuệ Nhân Tạo Hỗ Trợ Sắp Xếp Lịch Học Tại Học Viện Công Nghệ Bưu Chính Viễn Thông

Tìm hiểu về ứng dụng trí tuệ nhân tạo (AI) trong việc tối ưu hóa sắp xếp lịch học tại Học viện Công nghệ Bưu chính Viễn thông. Giải pháp hiệu quả cho việc quản lý thời khóa biểu.

• Tác giả: Nguyễn Hồng Anh Tấn
• Người hướng dẫn: TS. Phan Lý Huỳnh
• Trường học: Học Viện Công Nghệ Bưu Chính Viễn Thông
• Chuyên ngành: Hệ Thống Thông Tin
• Đề tài: Ứng Dụng Trí Tuệ Nhân Tạo Hỗ Trợ Sắp Xếp Lịch Học Tại Học Viện Công Nghệ Bưu Chính Viễn Thông
• Loại tài liệu: Đề Án Tốt Nghiệp Thạc Sĩ Kỹ Thuật
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. MỞ ĐẦU: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HỌC VÀ CÁC PHƯƠNG PHÁP TIẾP CẬN
• 1.1. Đặt vấn đề
• 1.2. Mô tả bài toán
• 1.3. Các phương pháp tiếp cận
• 1.3.1. Giải thuật tham lam (Greedy Algorithm)
• 1.3.2. Giải thuật leo đồi (Hill Climbing Algorithm)
• 1.3.3. Giải thuật luyện kim (Simulated Annealing - SA)
• 1.3.4. Giải thuật tối ưu đàn kiến (Ant Colony Optimization - ACO)
• 1.3.5. Giải thuật di truyền (Genetic Algorithm - GA)
• 1.4. Kết luận
• 2. NGHIÊN CỨU ĐÁNH GIÁ GIẢI THUẬT DI TRUYỀN
• 2.1. Khởi tạo quần thể
• 2.2. Xây dựng mô hình
• 2.2.1. Ràng buộc cứng
• 2.2.2. Ràng buộc mềm
• 2.2.3. Hàm thích nghi
• 2.2.4. Biểu diễn nhiễm sắc thể
• 2.2.5. Khởi tạo quần thể
• 2.2.6. Toán tử chọn lọc
• 2.2.7. Toán tử đột biến
• 2.2.7.1. Cải tiến lai ghép
• 2.2.7.2. Cải tiến đột biến
• 3. XÂY DỰNG ỨNG DỤNG XẾP THỜI KHÓA BIỂU BÁN TỰ ĐỘNG
• 3.1. Phân tích thiết kế
• 3.1.1. Danh mục Use-case
• 3.1.2. Kiến trúc tổng quan
• 3.2. Chức năng chính
• 3.2.1. Rà soát nhu cầu học phần
• 3.2.1.1. Chương trình đào tạo
• 3.2.1.2. Kết quả học tập học phần
• 3.2.1.3. Rà soát nhu cầu
• 3.2.2. Phân công giảng dạy
• 3.2.3. Thiết lập danh mục phòng học
• 3.2.4. Thiết lập danh mục môn học
• 3.2.5. Xếp thời khóa biểu bán tự động
• 3.2.5.1. Cấu hình tham số giải thuật
• 3.2.5.2. Xếp thời khóa biểu tự động
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Ứng Dụng AI Sắp Xếp Lịch Học Tại PTIT 55 Ký Tự

Bài toán sắp xếp lịch học là một thách thức lớn đối với các tổ chức giáo dục, đặc biệt là các trường đại học như Học viện Công nghệ Bưu chính Viễn thông (PTIT). Thời khóa biểu không chỉ là lịch giảng dạy, mà còn liên quan đến lịch thực hành, lịch thi của sinh viên và các sự kiện khác. Mục tiêu là tạo ra một kế hoạch học tập hợp lý, tránh xung đột và đảm bảo cân bằng thời gian cho cả giảng viên và sinh viên. Việc giải quyết bài toán này phức tạp vì có nhiều yếu tố ràng buộc từ nhà quản trị, giảng viên và sinh viên, thường xuyên xung đột lẫn nhau. Các giải pháp sắp xếp thời khóa biểu tự động hoặc bán tự động trở nên thiết yếu, giúp giảm thiểu công sức của cán bộ trong việc xây dựng thời khóa biểu cho mỗi học kỳ. Nghiên cứu và phát triển giải pháp ứng dụng trí tuệ nhân tạo (AI) là hướng đi tiềm năng, đặc biệt khi Học viện Công nghệ Bưu chính Viễn thông đang phát triển hệ thống quản lý đào tạo số.

1.1. Hệ Đào Tạo Tín Chỉ và Bài Toán Lập Lịch Phức Tạp

Ngày nay, các trường Đại học thường tổ chức đào tạo theo hệ đào tạo tín chỉ, thay thế cho hệ đào tạo niên chế. Trong khi hệ đào tạo niên chế quản lý sinh viên tập trung theo lớp hành chính và dựa trên các lớp hành chính để xây dựng lịch học, hệ đào tạo tín chỉ lại coi sinh viên là đơn vị quản lý cơ sở và lập lịch học kết hợp giữa nhu cầu và chương trình đào tạo của sinh viên. Do đó việc sắp xếp lịch học đối với hệ thống đào tạo tín chỉ có nhiều ràng buộc hơn. Bên cạnh đó, lịch học có thể thay đổi liên tục nhưng vẫn phải đảm bảo các điều kiện ràng buộc về cơ sở vật chất, quỹ thời gian của người dạy và người học. Những điều trên khiến cho việc xếp lịch học là một bài toán phức tạp và tốn nhiều thời gian. Vì vậy, việc phát triển một công cụ xây dựng lịch học theo hệ đào tạo tín là điều cần thiết đối với công việc quản lý đào tạo của các trường Đại học.

1.2. Mục tiêu và phạm vi nghiên cứu của đề tài tại PTIT

Đề tài "Ứng dụng trí tuệ nhân tạo hỗ trợ sắp xếp lịch học tại Học viện Công nghệ Bưu chính Viễn thông" được xây dựng với mục đích nghiên cứu và phát triển giải pháp xây dựng thời khoá biểu tự động/bán tự động có hiệu quả cao cho hệ thống quản lý đào tạo số của Học viện. Đề án nghiên cứu có mục tiêu tìm ra giải pháp sắp xếp thời khoá biểu ứng dụng trí tuệ nhân tạo, từ đó phát triển ứng dụng sắp xếp thời khoá biểu tự động/bán tự động. Đề án nghiên cứu giải pháp sắp xếp thời khoá biểu dựa trên giải thuật di chuyền. Bên cạnh đó, đề án nghiên cứu biến thể của giải thuật di chuyền có khả năng tối ưu cho bài toán sắp xếp thời khoá biểu. Mô hình thời khoá biểu được xây dựng dựa trên thời khoá biểu giảng dạy theo học chế tín chỉ tại Học viện Công nghệ Bưu chính Viễn thông.

II. Thách Thức Sắp Xếp Lịch Học Thủ Công Tại PTIT 58 Ký Tự

Theo quy chế đào tạo tín chỉ tại các trường đại học, sinh viên có quyền tự do lựa chọn môn học và thời gian học phù hợp với nhu cầu cá nhân. Trước mỗi học kỳ, phòng đào tạo lập kế hoạch giảng dạy dựa trên chương trình đào tạo, số lượng sinh viên đủ điều kiện học, dự tính số lượng sinh viên học lại và ý kiến phản hồi từ các khoa và sinh viên. Kế hoạch này bao gồm thông tin chi tiết về từng môn học, số lớp dự kiến mở và tiến độ học tập. Các khoa sẽ đóng góp ý kiến và thu thập ý kiến từ sinh viên để điều chỉnh kế hoạch. Sau đó, các khoa phân công giảng viên phụ trách giảng dạy, có thể kèm theo các yêu cầu riêng. Dựa trên danh sách phân công và phản hồi, phòng Đào tạo sẽ phân lớp, lập và công bố thời khóa biểu. Với số lượng lớp tín chỉ lớn, việc lập thời khóa biểu thủ công dễ dẫn đến trùng lịch học, gây khó khăn cho sinh viên.

2.1. Bài Toán Phân Bổ Lịch Học và Các Ràng Buộc

Mỗi trường có một danh sách lớp học, danh sách phòng học, danh sách các tiết học trong một ngày, danh sách các thứ học trong một tuần. Mỗi lớp học ứng với một môn học, được phân công cho giảng viên giảng dạy thuộc khoa, bộ môn quản lý môn học đó. Mỗi lớp học có danh sách các buổi học căn cứ theo số tín chỉ của môn học và số tiết cần giảng dạy. Cần tìm một phương án sắp xếp các buổi học của các lớp vào các phòng học tại các tiết học của một ngày trong tuần. Việc sắp xếp lịch học cần thỏa mãn các điều kiện bắt buộc (ràng buộc cứng) và tối ưu hóa tối đa các điều kiện không bắt buộc (ràng buộc mềm).

2.2. Giải Pháp Xếp Lịch Học Bán Tự Động Cho PTIT

Việc tạo thời khóa biểu cho một lượng lớn các lớp tín chỉ có thể dẫn đến việc sinh viên gặp khó khăn khi đăng ký các môn học do trùng lịch học. Vì vậy, việc phát triển một công cụ xây dựng lịch học theo hệ đào tạo tín là điều cần thiết đối với công việc quản lý đào tạo của các trường Đại học. Nghiên cứu và phát triển giải pháp ứng dụng trí tuệ nhân tạo (AI) là hướng đi tiềm năng, đặc biệt khi Học viện Công nghệ Bưu chính Viễn thông đang phát triển hệ thống quản lý đào tạo số. Việc áp dụng giải pháp bán tự động sẽ giúp giảm thiểu thời gian và sai sót trong quá trình xếp lịch học.

III. Giải Thuật Di Truyền Giải Pháp AI Tối Ưu 52 Ký Tự

Có nhiều phương pháp được sử dụng để giải quyết bài toán sắp xếp thời khóa biểu, dựa trên khảo sát của Tan, J. và các cộng sự [2]. Trong số đó, giải thuật di truyền là một kỹ thuật tìm kiếm metaheuristic được mô phỏng theo quá trình chọn lọc tự nhiên. Ưu điểm của giải thuật di truyền bao gồm khả năng tìm kiếm trên không gian tìm kiếm lớn, khả năng xử lý song song, khả năng tối ưu hoá toàn cục [2]. Bên cạnh đó, giải thuật này cũng có một số nhược điểm như độ phức tạp lớn trong việc tính toán, khả năng xảy ra hội tụ sớm, khó tìm kiếm chính xác tối ưu toàn cục [2]. Các biến thể của giải thuật di truyền đã được nghiên cứu để khắc phục các nhược điểm trên [3]. Một biến thể của giải thuật với các tiêu chí phù hợp sẽ được lựa chọn để áp dụng giải quyết bài toán sắp xếp thời khoá biểu.

3.1. Các Phương Pháp Tiếp Cận Bài Toán Lập Lịch

Một số phương pháp được sử dụng để giải quyết bài toán xếp thời khóa biểu gồm Giải thuật tham lam (Greedy Algorithm), Giải thuật leo đồi (Hill Climbing Algorithm), Giải thuật luyện kim (Simulated Annealing - SA), Giải thuật tối ưu đàn kiến (Ant Colony Optimization - ACO) và Giải thuật di truyền (Genetic Algorithm - GA). Mỗi phương pháp có ưu và nhược điểm riêng, tùy thuộc vào đặc điểm của bài toán.

3.2. Ưu Điểm Của Giải Thuật Di Truyền So Với Các Phương Pháp Khác

Giải thuật Di truyền dễ dàng hơn trong việc mô hình hóa và cài đặt so với giải thuật Tối ưu đàn kiến và dễ kết hợp với các giải thuật khác trong việc tìm kiếm tối ưu hơn. Do đó giải thuật Di truyền được chọn để nghiên cứu áp dụng giải quyết bài toán xếp thời khóa biểu.

IV. Nghiên Cứu và Đánh Giá Giải Thuật Di Truyền 50 Ký Tự

Chương này sẽ trình bày các khái niệm của giải thuật di truyền và cách xây dựng mô hình giải thuật để giải quyết bài toán xếp thời khóa biểu. Giải thuật di truyền được lấy cảm hứng từ lý thuyết tiến hóa của Darwin [3] [4], trong đó sự sống sót của sinh vật có khả năng thích nghi cao hơn và gen của chúng được mô phỏng lại. Giải thuật di truyền là một thuật toán dựa trên quần thể (population-based). Mỗi giải pháp tương ứng với một nhiễm sắc thể (chromosome) và mỗi tham số đại diện cho một gen. Giải thuật di truyền đánh giá mức độ thích hợp của từng cá thể trong quần thể bằng cách sử dụng hàm thích nghi (mục tiêu).

4.1. Các Khái Niệm Cơ Bản Của Giải Thuật Di Truyền

Các khái niệm quan trọng trong giải thuật di truyền bao gồm quần thể, nhiễm sắc thể, gen, hàm thích nghi, chọn lọc, lai ghép và đột biến. Mỗi khái niệm đóng vai trò quan trọng trong quá trình tìm kiếm giải pháp tối ưu.Toán tử chọn lọc (ví dụ: bánh xe roulette). Toán tử này có nhiều khả năng chọn giải pháp tốt nhất hơn vì xác suất tỷ lệ thuận với mức độ phù hợp. Điều làm tăng khả năng tránh tối ưu cục bộ là xác suất chọn được các giải pháp kém. Điều này có nghĩa là nếu các giải pháp tốt bị mắc kẹt trong một giải pháp cục bộ, chúng có thể được rút ra bằng các giải pháp khác [5].

4.2. Lai Chéo và Đột Biến Trong Giải Thuật Di Truyền

Sự lai chéo (crossover) giữa các nhiễm sắc thể giúp trao đổi thông tin giữa các giải pháp với nhau mà giải pháp còn lại không có [5]. Giải thuật di truyền cũng được hưởng lợi từ toán tử đột biến (mutation). Toán tử này thay đổi ngẫu nhiên các gen trong nhiễm sắc thể, giúp duy trì sự đa dạng của các cá thể trong quần thể và làm mở rộng không gian tìm kiếm của giải thuật di truyền.

V. Xây Dựng Ứng Dụng Xếp Thời Khóa Biểu AI 53 Ký Tự

Chương này sẽ tập trung vào quá trình xây dựng ứng dụng xếp thời khóa biểu bán tự động dựa trên giải thuật di truyền. Quá trình này bao gồm phân tích thiết kế, xác định các use-case, xây dựng kiến trúc tổng quan và triển khai các chức năng chính của ứng dụng. Ứng dụng sẽ giúp Học viện Công nghệ Bưu chính Viễn thông tự động hóa quá trình sắp xếp lịch học, giảm thiểu công sức và thời gian cho cán bộ quản lý.

5.1. Phân Tích Thiết Kế và Kiến Trúc Tổng Quan

Quá trình phân tích thiết kế bao gồm xác định danh mục use-case, xây dựng kiến trúc tổng quan của hệ thống. Các use-case sẽ mô tả các tương tác giữa người dùng và hệ thống, trong khi kiến trúc tổng quan sẽ định nghĩa các thành phần chính của hệ thống và cách chúng tương tác với nhau. Các chức năng chính sẽ bao gồm rà soát nhu cầu học phần, phân công giảng dạy, thiết lập danh mục phòng học, thiết lập danh mục môn học và xếp thời khóa biểu bán tự động.

5.2. Triển Khai Chức Năng Xếp Thời Khóa Biểu Bán Tự Động

Chức năng xếp thời khóa biểu bán tự động sẽ cho phép người dùng cấu hình các tham số của giải thuật di truyền, sau đó chạy thuật toán để tạo ra một thời khóa biểu ban đầu. Người dùng cũng có thể chỉnh sửa thủ công thời khóa biểu để đáp ứng các yêu cầu đặc biệt. Quá trình này sẽ được hỗ trợ bởi giao diện trực quan và dễ sử dụng.

VI. Kết Luận và Hướng Phát Triển Ứng Dụng AI 50 Ký Tự

Đề tài đã nghiên cứu và phát triển thành công ứng dụng trí tuệ nhân tạo (AI) hỗ trợ sắp xếp lịch học tại Học viện Công nghệ Bưu chính Viễn thông (PTIT). Ứng dụng dựa trên giải thuật di truyền và có khả năng tự động hóa quá trình lập lịch biểu, giúp giảm thiểu thời gian và công sức cho cán bộ quản lý. Kết quả nghiên cứu có thể được áp dụng trong việc xây dựng mô hình sắp xếp thời khóa biểu tự động/bán tự động trong hệ thống quản lý đào tạo số đang được phát triển tại Học viện.

6.1. Đánh Giá Hiệu Quả và Các Hạn Chế Của Ứng Dụng

Cần thực hiện đánh giá hiệu quả của ứng dụng bằng cách so sánh thời khóa biểu được tạo ra bởi ứng dụng với thời khóa biểu được tạo ra thủ công. Đánh giá này sẽ tập trung vào các tiêu chí như thời gian tạo thời khóa biểu, số lượng xung đột và mức độ hài lòng của sinh viên và giảng viên. Các hạn chế của ứng dụng cũng cần được xác định để có kế hoạch cải tiến trong tương lai.

6.2. Hướng Phát Triển Ứng Dụng và Ứng Dụng AI trong Giáo Dục

Trong tương lai, ứng dụng có thể được phát triển thêm các tính năng mới, chẳng hạn như tích hợp với các hệ thống khác tại PTIT, hỗ trợ lập lịch biểu cho các hoạt động ngoại khóa và cung cấp các gợi ý cá nhân hóa cho sinh viên. Ngoài ra, cần tiếp tục nghiên cứu và ứng dụng AI trong các lĩnh vực khác của giáo dục, chẳng hạn như personalized learning và đánh giá học sinh.

Nội dung chính

Tổng quan nghiên cứu

Bài toán xếp thời khóa biểu là một thách thức phổ biến trong các tổ chức giáo dục, đặc biệt là các trường đại học áp dụng hệ đào tạo tín chỉ. Theo ước tính, tại Học viện Công nghệ Bưu chính Viễn thông, mỗi học kỳ có khoảng 326 môn học, 1555 lớp học với trung bình 3 tiết/tuần, 272 giảng viên và 175 phòng học, tạo nên một không gian tìm kiếm phức tạp với tổng số tiết học cần xếp khoảng 5000 trên tổng số 14700 tiết khả dụng trong tuần. Việc xây dựng thời khóa biểu phải đảm bảo không gây xung đột về phòng học, giảng viên, sinh viên và tối ưu hóa các điều kiện như nhu cầu giảng dạy, sử dụng phòng học hiệu quả.

Mục tiêu nghiên cứu là phát triển một giải pháp ứng dụng trí tuệ nhân tạo, cụ thể là giải thuật di truyền, để hỗ trợ sắp xếp lịch học tự động hoặc bán tự động tại Học viện. Phạm vi nghiên cứu tập trung vào dữ liệu thực tế của học kỳ 1 năm học 2023-2024 tại Học viện Công nghệ Bưu chính Viễn thông, với các ràng buộc cứng và mềm được mô hình hóa chi tiết. Ý nghĩa của nghiên cứu thể hiện qua việc giảm thiểu thời gian và công sức cho cán bộ quản lý đào tạo, đồng thời nâng cao chất lượng và tính khả thi của thời khóa biểu, góp phần cải thiện hiệu quả quản lý đào tạo số.

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 dựa trên các lý thuyết và mô hình sau:

• Giải thuật di truyền (Genetic Algorithm - GA): Mô phỏng quá trình chọn lọc tự nhiên, sử dụng các toán tử chọn lọc, lai ghép và đột biến để phát triển các giải pháp tối ưu qua các thế hệ. GA có khả năng tìm kiếm trên không gian lớn, xử lý song song và tối ưu hóa toàn cục.
• Mô hình ràng buộc cứng và mềm: Ràng buộc cứng bao gồm các điều kiện bắt buộc như không trùng lịch giảng viên, phòng học và lớp học; ràng buộc mềm là các ưu tiên như nhu cầu tiết học của giảng viên, tối ưu sử dụng phòng, tránh trùng lịch trong cùng nhóm ngành.
• Biểu diễn nhiễm sắc thể: Thời khóa biểu được biểu diễn dưới dạng mảng ba chiều (ngày, tiết học, phòng học), đảm bảo không vi phạm ràng buộc cứng về phòng học.
• Toán tử chọn lọc bánh xe roulette: Chọn các cá thể tốt dựa trên xác suất tỷ lệ thuận với độ thích nghi, giúp duy trì đa dạng quần thể và tránh tối ưu cục bộ.

Các khái niệm chính bao gồm: nhiễm sắc thể, gen, hàm thích nghi, toán tử lai ghép đa điểm, toán tử đột biến, ràng buộc cứng và mềm.

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

Nguồn dữ liệu chính là bộ dữ liệu thời khóa biểu học kỳ 1 năm học 2023-2024 của Học viện Công nghệ Bưu chính Viễn thông, bao gồm 326 môn học, 1555 lớp học, 272 giảng viên, 175 phòng học, với tổng số tiết cần xếp khoảng 5000 tiết trong tuần.

Phương pháp phân tích sử dụng giải thuật di truyền với các bước:

• Khởi tạo quần thể ngẫu nhiên với kích thước quần thể P1 trong khoảng {20, 40}.
• Áp dụng toán tử chọn lọc bánh xe roulette để chọn cá thể tốt.
• Thực hiện lai ghép đa điểm với mặt nạ lai ghép ngẫu nhiên, kiểm tra không vi phạm ràng buộc cứng.
• Thực hiện toán tử đột biến với xác suất pm, cải tiến đột biến để tăng tốc tối ưu ràng buộc mềm.
• Đánh giá độ thích nghi dựa trên hàm mục tiêu giảm thiểu vi phạm ràng buộc mềm, với trọng số ưu tiên cho từng ràng buộc.
• Thực hiện lặp lại quá trình trong số vòng lặp tối đa P2 trong khoảng {500, 1000}.

Timeline nghiên cứu bao gồm thu thập dữ liệu, xây dựng mô hình, phát triển giải thuật, thử nghiệm và đánh giá trên bộ dữ liệu thực tế trong năm học 2023-2024.

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

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

1. Hiệu quả của giải thuật di truyền: Kết quả thử nghiệm trên bộ dữ liệu thực tế cho thấy giải thuật di truyền đạt độ thích nghi tốt nhất lên đến 0.90 trong thời gian khoảng 2 phút với các tham số P1=20, P2=500, P3=5, P4=2. Khi tăng số vòng lặp lên 1000 và phần trăm tiết trống lên 15, thời gian thực thi tăng lên 4.87 phút nhưng độ thích nghi không cải thiện đáng kể.

2. Ảnh hưởng của kích thước quần thể: Kích thước quần thể ban đầu (20 hoặc 40) không ảnh hưởng rõ rệt đến độ tối ưu của giải thuật do tính ngẫu nhiên trong khởi tạo quần thể.

3. Tác động của số lớp tối thiểu học cùng thời gian (P4): Việc tăng số lớp tối thiểu học cùng một thời điểm từ 2 lên 3 làm giảm hiệu quả giải thuật do tăng khả năng trùng lịch trong cùng nhóm khóa ngành, dẫn đến vi phạm ràng buộc mềm SC4.

4. Tối ưu hóa ràng buộc mềm: Các ràng buộc mềm được đánh trọng số ưu tiên, trong đó ràng buộc về việc tất cả các lớp phải được xếp lịch và tránh trùng lịch trong cùng nhóm khóa ngành có trọng số cao nhất (2), giúp giải thuật tập trung tối ưu các yếu tố quan trọng nhất.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả cao là do mô hình hóa chi tiết các ràng buộc cứng và mềm, cùng với việc cải tiến toán tử lai ghép và đột biến giúp giảm vi phạm ràng buộc cứng ngay từ đầu, đồng thời tăng tốc tối ưu ràng buộc mềm. So với các nghiên cứu khác sử dụng giải thuật tham lam hay leo đồi, giải thuật di truyền cho phép thoát khỏi tối ưu cục bộ và tìm kiếm giải pháp toàn cục hiệu quả hơn.

Dữ liệu có thể được trình bày qua biểu đồ so sánh độ thích nghi theo các bộ tham số đầu vào, hoặc bảng thống kê thời gian thực thi và mức độ vi phạm ràng buộc. Kết quả này có ý nghĩa thực tiễn lớn trong việc tự động hóa quá trình xếp thời khóa biểu, giảm thiểu sai sót và tăng tính linh hoạt trong quản lý đào tạo.

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

1. Triển khai ứng dụng xếp thời khóa biểu bán tự động: Áp dụng giải thuật di truyền đã cải tiến vào hệ thống quản lý đào tạo số của Học viện, nhằm giảm thời gian lập lịch từ vài ngày xuống còn vài phút, tăng độ chính xác và khả năng tùy chỉnh theo nhu cầu thực tế.

2. Tăng cường thu thập và cập nhật dữ liệu: Đề xuất phòng đào tạo và các khoa thường xuyên cập nhật thông tin về nhu cầu giảng dạy, số lượng sinh viên, và yêu cầu phòng học để đảm bảo dữ liệu đầu vào chính xác, giúp giải thuật hoạt động hiệu quả hơn.

3. Đào tạo cán bộ quản lý sử dụng công cụ: Tổ chức các khóa đào tạo cho cán bộ phòng đào tạo và chuyên viên công nghệ thông tin về cách vận hành và điều chỉnh tham số giải thuật, nhằm tối ưu hóa kết quả xếp lịch theo từng học kỳ.

4. Nghiên cứu mở rộng giải thuật: Khuyến nghị tiếp tục nghiên cứu các biến thể giải thuật di truyền kết hợp với các kỹ thuật học máy để nâng cao khả năng dự đoán và tối ưu hóa lịch học, đặc biệt trong các tình huống phức tạp như thay đổi đột xuất về giảng viên hoặc phòng học.

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

1. Cán bộ quản lý đào tạo tại các trường đại học: Giúp hiểu rõ về các phương pháp tự động hóa xếp thời khóa biểu, từ đó áp dụng vào thực tiễn quản lý đào tạo tín chỉ.

2. Nhà phát triển phần mềm giáo dục: Cung cấp kiến thức về mô hình hóa bài toán xếp lịch và ứng dụng giải thuật di truyền trong phát triển các hệ thống quản lý đào tạo số.

3. Nghiên cứu sinh và sinh viên ngành công nghệ thông tin, hệ thống thông tin: Là tài liệu tham khảo về ứng dụng trí tuệ nhân tạo trong lĩnh vực giáo dục, đặc biệt về giải thuật tiến hóa và tối ưu hóa.

4. Các chuyên gia tư vấn quản lý giáo dục: Hỗ trợ đánh giá và đề xuất các giải pháp công nghệ nhằm nâng cao hiệu quả quản lý đào tạo tại các cơ sở giáo dục đại học.

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

1. Giải thuật di truyền có ưu điểm gì so với các giải thuật khác trong xếp thời khóa biểu?
   Giải thuật di truyền có khả năng tìm kiếm trên không gian lớn, tránh tối ưu cục bộ nhờ các toán tử lai ghép và đột biến, đồng thời dễ dàng mô hình hóa và kết hợp với các giải thuật khác để nâng cao hiệu quả.

2. Làm thế nào để đảm bảo không vi phạm các ràng buộc cứng trong quá trình xếp lịch?
   Bằng cách cải tiến toán tử lai ghép và đột biến để loại bỏ các cá thể vi phạm ràng buộc cứng ngay từ đầu, giúp các thế hệ nhiễm sắc thể luôn thỏa mãn các điều kiện bắt buộc.

3. Thời gian thực thi của giải thuật trên bộ dữ liệu thực tế là bao lâu?
   Thời gian thực thi dao động từ khoảng 2 phút đến gần 5 phút tùy thuộc vào các tham số đầu vào như kích thước quần thể, số vòng lặp và phần trăm tiết trống.

4. Giải pháp này có thể áp dụng cho các trường đại học khác không?
   Có, mô hình và giải thuật có thể được điều chỉnh phù hợp với quy mô và đặc thù của từng trường, đặc biệt là các trường áp dụng hệ đào tạo tín chỉ với nhiều ràng buộc phức tạp.

5. Có thể tích hợp giải thuật này vào hệ thống quản lý đào tạo hiện có không?
   Hoàn toàn có thể, nghiên cứu đã xây dựng ứng dụng xếp thời khóa biểu bán tự động với kiến trúc hiện đại sử dụng ReactJS, NestJS và Keycloak, dễ dàng tích hợp vào các hệ thống quản lý đào tạo số.

Kết luận

• Đề tài đã phát triển thành công giải pháp ứng dụng giải thuật di truyền cải tiến để hỗ trợ xếp thời khóa biểu tại Học viện Công nghệ Bưu chính Viễn thông.
• Mô hình hóa chi tiết các ràng buộc cứng và mềm giúp nâng cao chất lượng lịch học, giảm thiểu xung đột và tối ưu hóa sử dụng nguồn lực.
• Kết quả thử nghiệm trên bộ dữ liệu thực tế cho thấy giải thuật đạt độ thích nghi cao trong thời gian thực thi hợp lý.
• Ứng dụng xếp thời khóa biểu bán tự động được thiết kế với kiến trúc hiện đại, dễ dàng triển khai và tích hợp.
• Khuyến nghị tiếp tục nghiên cứu mở rộng và đào tạo cán bộ để phát huy tối đa hiệu quả của giải pháp trong quản lý đào tạo số.

Hành động tiếp theo là triển khai ứng dụng vào thực tế tại Học viện và thu thập phản hồi để hoàn thiện, đồng thời mở rộng nghiên cứu cho các trường đại học khác.

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

Đặt vấn đề Ngày này các trường Đại học thường tổ chức đào tạo theo hệ đào tạo tín chỉ, thay thế cho hệ đào tạo niên chế. Trong khi hệ đào tạo niên chế quản lý sinh viên tập trung theo lớp hành chính và dựa trên các lớp hành chính để xây dựng lịch học, hệ đào tạo tín chỉ lại coi sinh viên là đơn vị quản lý cơ sở và lập lịch học kết hợp giữa nhu cầu và chương trình đào tạo của sinh viên. Do đó việc sắp xếp lịch học đối với hệ thống đào tạo tín chỉ có nhiều ràng buộc hơn. Bên cạnh đó, lịch học có thể thay đổi liên tục nhưng vẫn phải đảm bảo các điều kiện ràng buộc về cơ sở vật chất, quỹ thời gian của người dạy và người học.

Những điều trên khiến cho việc xếp lịch học là một bài toán phức tạp và tốn nhiều thời gian. Vì vậy, việc phát triển một công cụ xây dựng lịch học theo hệ đào tạo tín là điều cần thiết đối với công việc quản lý đào tạo của các trường Đại học.2 Mô tả bài toán Theo quy chế đào tạo của hệ đào tạo tín chỉ áp dụng cho trường Đại học, sinh viên được phép tự do lựa chọn môn học và thời gian học theo nhu cầu cá nhân của mình. Trước khi bắt đầu mỗi học kỳ, phòng đào tạo tiến hành xây dựng kế hoạch giảng dạy. Căn cứ để lập kế hoạch giảng dạy gồm:  Chương trình đào tạo toàn khóa của từng chuyên ngành đã được Hiệu trưởng ký duyệt.

 Số lượng sinh viên thuộc các khóa - ngành tương ứng có đủ điều kiện theo học các môn học dự kiến giảng dạy trong năm học. 4  Dự tính số lượng sinh viên sẽ học lại mỗi môn học và số lớp có thể mở tương ứng.  Ý kiến phản hồi và yêu cầu từ các khoa và sinh viên. Kế hoạch giảng dạy bao gồm :  Chương trình đào tạo của từng khóa-ngành.

 Thông tin chi tiết về từng môn học.  Số lớp dự kiến mở cho mỗi môn học trong học kỳ.  Tiến độ học tập của năm học. Kế hoạch này được gửi đến từng khoa và các đơn vị liên quan.

Các khoa góp ý cho bản kế hoạch giảng dạy và thông qua hệ thống cố vấn học tập thu thập ý kiến từ sinh viên để bổ sung, điều chỉnh kế hoạch. Dựa trên kế hoạch giảng dạy, các khoa phân công giảng viên phụ trách giảng dạy từng lớp tín chỉ, kể cả việc mời giảng khi cần thiết. Các giảng viên được phân công giảng dạy có thể nêu kèm theo các yêu cầu riêng, nếu có. Sau khi nhận được danh sách phân công giảng viên và các ý kiến phản hồi từ các đơn vị, căn cứ vào kế hoạch giảng dạy, phòng Đào tạo sẽ tiến hành phân lớp, lập và công bố Thời khóa biểu.

Thời khóa biểu này được công bố làm cơ sở để sinh viên đăng ký môn học. Dựa vào quy mô của chương trình đào tạo, số lượng lớp tín chỉ trong một kỳ học có thể biến đổi từ vài trăm đến vài ngàn lớp. Việc tạo thời khóa biểu cho một lượng lớn các lớp tín chỉ có thể dẫn đến việc sinh viên gặp khó khăn khi đăng ký các môn học do trùng lịch học. Phát biểu bài toán như sau: 5 Mỗi trường có một danh sách lớp học, danh sách phòng học, danh sách các tiết học trong một ngày, danh sách các thứ học trong một tuần.

Mỗi lớp học ứng với một môn học, được phân công cho giảng viên giảng dạy thuộc khoa, bộ môn quản lý môn học đó. Mỗi lớp học có danh sách các buổi học căn cứ theo số tín chỉ của môn học và số tiết cần giảng dạy. Cần tìm một phương án sắp xếp các buổi học của các lớp vào các phòng học tại các tiết học của một ngày trong tuần. Việc sắp xếp lịch học cần thỏa mãn các điều kiện bắt buộc (ràng buộc cứng) và tối ưu hóa tối đa các điều kiện không bắt buộc (ràng buộc mềm) [1].3 Các phương pháp tiếp cận Dưới đây là một số phương pháp được sử dụng để giải quyết bài toán xếp thời khóa biểu, dựa trên khảo sát của Tan, J.

và các cộng sự [2]: 1.1 Giải thuật tham lam (Greedy Algorithm) Giải thuật tham lam là một phương pháp giải quyết bài toán dựa trên việc lựa chọn bước đi tốt nhất tại mỗi bước mà không cần xem xét toàn bộ bài toán. Tư tưởng chính của giải thuật này là luôn chọn giải pháp tốt nhất hiện tại với hy vọng rằng nó sẽ dẫn đến kết quả tốt nhất toàn cục. Một giải thuật tham lam điển hình có ba thành phần chính: 1. Lựa chọn tham lam: Ở mỗi bước, chọn phương án tốt nhất tại thời điểm đó.

Tính chất không đổi: Sau mỗi bước chọn, bài toán con mới vẫn giữ nguyên tính chất như bài toán ban đầu. Giải quyết bài toán con: Tiếp tục áp dụng chiến lược tham lam để giải quyết bài toán con còn lại. 6 Giải thuật tham lam có thể áp dụng vào bài toán xếp thời khóa biểu bằng cách chọn các lớp học vào các khoảng thời gian sao cho tối ưu nhất tại mỗi bước. Chẳng hạn, nó có thể bắt đầu bằng việc sắp xếp các lớp học có số lượng sinh viên đông nhất vào các khung giờ có sẵn trước, sau đó tiếp tục với các lớp nhỏ hơn.

Tuy nhiên, giải pháp này không phải lúc nào cũng tối ưu toàn cục vì nó không xem xét toàn bộ bài toán từ đầu đến cuối.2 Giải thuật leo đồi (Hill Climbing Algorithm) Giải thuật leo đồi là một phương pháp tìm kiếm dựa trên việc bắt đầu từ một điểm khởi đầu và liên tục di chuyển đến trạng thái láng giềng tốt hơn, cho đến khi không còn trạng thái láng giềng nào tốt hơn điểm hiện tại. Điều này tương tự như việc leo lên đỉnh đồi, luôn di chuyển theo hướng lên cao cho đến khi đạt đỉnh. Quá trình này bao gồm: 1. Khởi tạo: Bắt đầu từ một trạng thái ban đầu ngẫu nhiên.

Đánh giá: Đánh giá các trạng thái láng giềng. Lựa chọn: Chọn trạng thái láng giềng tốt nhất để di chuyển đến. Lặp lại: Lặp lại quá trình cho đến khi không có cải thiện nào nữa. Trong bài toán xếp thời khóa biểu, giải thuật leo đồi có thể bắt đầu với một phân bố thời khóa biểu ngẫu nhiên và sau đó cải thiện bằng cách hoán đổi các lớp học, sao cho giảm thiểu xung đột (ví dụ như tránh trùng lặp phòng học, thời gian, giảng viên).

Tuy nhiên, phương pháp này dễ mắc kẹt tại các cực tiểu cục bộ và không đảm bảo tìm ra giải pháp tối ưu toàn cục.3 Giải thuật luyện kim (Simulated Annealing - SA) Giải thuật luyện kim dựa trên quá trình tôi luyện kim loại, trong đó kim loại được đun nóng đến nhiệt độ cao rồi làm nguội từ từ để đạt được cấu trúc tinh thể tối 7 ưu. Tương tự, SA bắt đầu từ một giải pháp ngẫu nhiên và thực hiện các thay đổi ngẫu nhiên với xác suất chấp nhận phụ thuộc vào nhiệt độ, từ đó giảm dần nhiệt độ theo thời gian. Các bước chính của SA bao gồm: 1. Khởi tạo: Bắt đầu từ một giải pháp ngẫu nhiên.

Đột biến và chấp nhận: Thực hiện thay đổi ngẫu nhiên giải pháp hiện tại và quyết định chấp nhận giải pháp mới dựa trên xác suất tính theo hàm nhiệt độ. Giảm nhiệt độ: Giảm nhiệt độ từ từ theo một lịch trình làm nguội. Lặp lại: Lặp lại quá trình cho đến khi nhiệt độ giảm về 0 hoặc đạt đến số lần lặp nhất định. SA có thể được sử dụng để xếp thời khóa biểu bằng cách bắt đầu từ một giải pháp ban đầu và thực hiện các thay đổi nhỏ, chẳng hạn như hoán đổi thời gian của các lớp học.

Với xác suất chấp nhận các giải pháp tạm thời kém hơn, SA có thể vượt qua các cực tiểu cục bộ và tìm kiếm giải pháp tối ưu hơn, làm cho nó phù hợp với các bài toán có không gian tìm kiếm phức tạp như xếp thời khóa biểu.4 Giải thuật tối ưu đàn kiến (Ant Colony Optimization - ACO) Giải thuật tối ưu đàn kiến là một phương pháp dựa trên hành vi tìm đường của các con kiến trong tự nhiên. Các con kiến khi di chuyển để tìm thức ăn sẽ để lại dấu vết pheromone, và các kiến khác có xu hướng đi theo những dấu vết này, dẫn đến việc tìm ra con đường ngắn nhất một cách tự nhiên. Các bước chính trong ACO bao gồm: 1. Khởi tạo: Đặt các kiến tại các điểm khởi đầu khác nhau.

Di chuyển và đặt pheromone: Các kiến di chuyển đến các điểm khác nhau dựa trên một xác suất tỉ lệ thuận với lượng pheromone trên đường đi. Cập nhật pheromone: Lượng pheromone trên các đường đi được cập nhật dựa trên chất lượng của giải pháp mà các kiến tìm được. Lặp lại: Lặp lại quá trình cho đến khi đạt được kết quả tối ưu. ACO có thể được áp dụng để tìm kiếm các phân bố thời khóa biểu tối ưu bằng cách mô phỏng các con kiến di chuyển giữa các lựa chọn lớp học và thời gian.

Mỗi kiến sẽ thử một giải pháp xếp thời khóa biểu và để lại dấu vết pheromone, từ đó các kiến khác sẽ dần dần tìm ra các giải pháp tối ưu hơn dựa trên dấu vết này. Điều này giúp tìm ra các giải pháp tốt một cách hiệu quả.5 Giải thuật di truyền (Genetic Algorithm - GA) Giải thuật di truyền mô phỏng quá trình chọn lọc tự nhiên, sử dụng các khái niệm như gen, lai ghép, và đột biến để phát triển các giải pháp tốt hơn qua các thế hệ. Các bước chính của GA bao gồm: 1. Khởi tạo quần thể: Tạo ra một quần thể các cá thể ngẫu nhiên.

Đánh giá: Đánh giá độ thích nghi của mỗi cá thể trong quần thể. Chọn lọc: Chọn các cá thể tốt nhất để làm cha mẹ dựa trên độ thích nghi. Lai ghép và đột biến: Lai ghép các cá thể cha mẹ để tạo ra thế hệ con mới, và thực hiện đột biến ngẫu nhiên. Lặp lại: Lặp lại quá trình cho đến khi đạt được giải pháp tối ưu hoặc sau một số thế hệ nhất định.

GA có thể áp dụng bằng cách mã hóa mỗi thời khóa biểu dưới dạng một cá thể trong quần thể. Các cá thể này sẽ trải qua các quá trình chọn lọc, lai ghép và đột biến để tạo ra các thời khóa biểu mới, tốt hơn. GA có thể tìm ra các giải pháp tối ưu bằng cách kết hợp các đặc điểm tốt từ các cá thể khác nhau qua nhiều thế hệ.