- BẢN TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: Kỹ thuật quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc và phân cụm cân bằng trong việc giải các bài toán tối ưu tổ hợp Tác giả luận văn: Huỳnh Thành Trung Khóa: 2016CLC Người hướng dẫn: TS. - Lý do chọn đề tài Bài toán tối ưu tổ hợp là lớp bài toán bài toán rất phổ biến trong phổ biến trên mọi khía cạnh của cuộc sống, từ sản xuất, năng lượng, vận chuyển hậu cần, giao thông, tổ chức hành chính, y tế. - Tuy nhiên việc giải các bài toán này gặp nhiều khó khăn bởi đa số các bài toán này thuộc lớp các bài toán NP-khó, độ phức tạp cao. - Do đó, trong khuôn khổ của luận văn, chúng tôi nghiên cứu một số các phương pháp giải quyết bài toán tối ưu hóa tổ hợp, đồng thời ứng dụng đề xuất thuật toán mới cho bài toán tối ưu tổ hợp thực tế: Bài toán xếp lịch bảo vệ cao học. - Mục đích nghiên cứu - Tìm hiểu nghiên cứu một số phương pháp giải quyết bài toán tối ưu hóa tổ hợp - Ứng dụng đề xuất thuật toán mới cho bài toán tối ưu tổ hợp thực tế: Bài toán xếp lịch bảo vệ cao học. - Đối tượng - Lớp bài toán tối ưu hóa tổ hợp, bài toán xếp lịch bảo vệ cao học - Các phương pháp: kỹ thuật quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc, phân cụm cân bằng c. - Phạm vi nghiên cứu - Nắm vững các phương pháp - Ứng dụng đề xuất thuật toán cho bài toán xếp lịch bảo vệ cao học 3. - Tóm tắt cô đọng các nội dung chính và đóng góp mới của tác giả Trong luận văn này, chúng tôi sẽ tìm hiểu chi tiết nền tảng kiến thức về quy hoạch ràng buộc (constraint programming), tìm kiếm cục bộ dựa trên ràng buộc (constraint-based local search) trong việc giải các bài toán tối ưu tổ hợp. - Sau đó, chúng tôi tiến hành triển khai các phương pháp nêu trên vào mô hình hóa và thiết kế giải thuật cho bài toán xếp lịch bảo vệ cao học (Master thesis defense timetabling), với đề xuất nổi bật là sử dụng phân cụm cân bằng (K-means balance clustering) để phân rã bài toán thành các bài toán con để song song tìm các lời giải tối ưu từng phần, giúp giảm thiểu đáng kể thời gian tính toán trong khi vẫn đảm bảo được những phương án lịch đưa ra đạt chất lượng cao cho người quyết định (giáo vụ). - Phương pháp nghiên cứu - Tìm hiểu nền tảng lý thuyết, đọc các bài báo liên quan - Tìm hiểu yêu cầu thực tế của bài toán xếp lịch bảo vệ cao học, mở rộng mô hình bài toán, số hóa các bộ dữ liệu thực tế để thử nghiệm - Đề xuất các ý tưởng trong pha mô hình hóa và pha tìm kiếm lời giải của bài toán, tiến hành thử nghiệm trên các bộ dữ liệu với từng ý tưởng để đánh giá 5. - Kết luận - Chúng tôi đã đạt được việc tìm hiểu một số các phương pháp giải lớp các bài toán tối ưu tổ hợp, mở rộng mô hình bài toán xếp lịch bảo vệ cao học, đề xuất thành công thuật toán xấp xỉ giải quyết bài toán với khả năng đưa ra một lời giải tốt trong thời gian chấp nhận được - Ý tưởng phân cụm cân bằng là một ý tưởng mới và hiệu quả, có tiềm năng nghiên cứu để áp dụng vào các bài toán khác xét đến mục tiêu cân bằng tải Ngày 29 tháng 03 năm 2017 Giáo viên hướng dẫn Tác giả luận văn
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt