Ngành: Khoa học máy tính
Mã số: 62 48.01 01
Họ tên nghiên cứu sinh: Nguyễn Tấn Trần Minh Khang
Người hướng dẫn khoa học: PGS. TS. Trần Thị Huệ Nương
Cơ sở đào tạo: Trường Đại học Khoa học Tự nhiên – ĐHQG.HCM
1. Tóm tắt nội dung luận án
Luận án này tập trung giải quyết bài toán xếp thời khóa biểu dựa trên nhóm học phần có mang đặc trưng riêng của các trường đại học Việt Nam, một bài toán có nhiều ứng dụng trong thực tế. Điểm khác biệt giữa bài toán xếp thời khóa biểu môn học tại các trường đại học của Việt Nam với các bài toán xếp thời khóa biểu đại học trên thế giới là sự đa dạng hơn về mặt ràng buộc, ví dụ: một phân công khi được sắp thời khóa biểu có thể được chia ra nhiều cụm (block element), một một cụm phải được gán vào một buổi và các cụm của một phân công (activity) cần phải gán vào các ngày khác nhau; một buổi dạy/học của giáo viên và lớp học cần phải được hạn chế số lượng tiết lủng; lịch giảng dạy của giáo viên cần được cực tiểu hóa số lượng buổi dạy khi có yêu cầu. Thách thức của bài toán xếp thời khóa biểu môn học là bài toán bùng nổ tổ hợp, không gian tìm kiếm lớn, trong khi đó thời gian yêu cầu để thuật giải chạy cho ra lời giải phải trong khoảng thời gian chấp nhận được.
Luận án này tập trung vào các phương pháp theo hướng tiếp cận metaheuristic bởi vì hướng tiếp cận này được sử dụng rất thông dụng để giải quyết các bài toán xếp thời khóa biểu, một trong những lớp bài toán dạng NP-khó. Tuy nhiên việc áp dụng các thuật giải theo hướng tiếp cận này là không đơn giản bởi vì việc áp dụng một thuật giải metaheuristic vào một bài toán đặc thù cần sự tinh tế trong việc biểu diễn lời giải, khởi tạo lời giải ban đầu, thực hiện việc tìm kiếm lời giải trong không gian lời giải. Hơn nữa, với sự đa dạng của các thuật giải đã công bố, việc đánh giá để lựa chọn thuật giải tối ưu cho bài toán xếp thời khóa biểu với đặc thù Việt Nam là rất cần thiết. Do đó luận án này tập trung làm rõ các vấn đề sau:
- Đánh giá, so sánh, và đề xuất một số cải tiến các thuật giải hiện có cho bài toán xếp thời khóa biểu môn học của Việt Nam, cụ thể như sau:
o Đề xuất một mô hình Toán học để có thể đánh giá các thuật giải một cách hiệu quả.
o Phân tích, đánh giá các thuật giải như TabuSearch, thuật giải tôi luyện thép (SA), thuật giải Variable Neighborhood Search, thuật giải Memetic, thuật giải Particle Swarm Optimization và thuật giải bầy ong (Bees Algorithm) dựa trên mô hình đã đề xuất cho tập dữ liệu thực tế thu thập tại trường ĐH Khoa Học Tự Nhiên Tp. HCM. Đây là tập dữ liệu có độ phức tạp cao với 10 ràng buộc cứng, 10 ràng buộc mềm sát với thực tế triển khai.
o Đề xuất một số cải tiến dựa trên các phân tích trên. Cụ thể, với thuật giải Tabu Search, SA, VNS để tối ưu bộ nhớ, khi khám phá không gian lân cận, luận án đề xuất chỉ lưu trữ các phép chuyển thay cho lưu trữ các lời giải lân cận. Kỹ thuật này được tiếp tục áp dụng cho các thuật giải SA, VNS, Memetic. Với thuật giải PSO, luận án đề xuất khái niệm vị trí, vận tốc trong việc ứng dụng thuật giải.
- Nghiên cứu cách kết hợp các thuật giải hiện có sao cho đạt hiệu quả tối ưu hơn. Cụ thể luận án đã đề xuất các phương pháp kết hợp giữa các thuật giải GA-Bees, Harmony-Bees, GA-SA, Bees-VNS, Bee-PSO. Ý tưởng chính của việc kết hợp các thuật giải là nhằm tăng tính đa dạng và mở rộng không gian tìm kiếm hết khả năng có thể. Kết quả thực nghiệm cho thấy sự vượt trội của các phương pháp kết hợp này so với các phương pháp áp dụng đơn thuần một thuật giải.
2. Những kết quả mới của luận án
Luận án đề xuất một mô hình toán học để có thể đánh giá các thuật giải một cách hiệu quả và thống nhất trong cùng một bộ dữ liệu và tiêu chí đánh giá. Trong mô hình này đã mô hình hóa biểu diễn các ràng buộc cứng, ràng buộc mềm của bài toán xếp lịch và hàm mục tiêu nhằm đánh giá chất lượng lời giải.
Luận án đã phân tích, đánh giá, cải tiến và so sánh 23 thuật giải thuộc nhóm thuật giải metaheuristics bao gồm:
- 3 thuật giải đơn lời giải gồm thuật giải Tabu Search, thuật giải Simulated Annealing và thuật giải Variable Neighbourhood Search.
- 5 thuật giải quần thể gồm: thuật giải di truyền, thuật giải Memetic, thuật giải Harmony Search, thuật giải Particle Swarm Optimization và thuật giải Bees.
- Đề xuất 15 mô hình thuật giải kết hợp gồm hai nhóm con:
o Nhóm con thứ nhất - kết hợp các thuật giải đơn lời giải và các thuật giải bầy đàn, gồm sự kết hợp lần lượt giữa các thuật giải di truyền, Harmony Search, Particle Swarm Optimization, Bees với các thuật giải Tabu Search, Variable Neighborhood Search, Simulated Annealing.
o Nhóm con thứ hai - kết hợp các thuật giải bầy đàn với nhau, gồm sự kết hợp giữa các cặp thuật giải Bees và di truyền, Bees và Harmony Search, Particle Swarm Optimization và Bees.
Nghiên cứu của luận án đã chỉ ra các thuật giải quần thể có lợi thế hơn so với các thuật giải đơn lời giải.
Kết quả thực nghiệm chỉ ra mô hình kết hợp Bees-VNS là tốt nhất đối với bộ dữ liệu của bài toán.
3. Các ứng dụng/Khả năng ứng dụng trong thực tiễn hay những vấn đề còn bỏ ngỏ cần tiếp tục nghiên cứu
Hãy là người bình luận đầu tiên