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

- Huỳnh Thành Trung HỆ THỐNG THÔNG TIN 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 LUẬN VĂN THẠC SĨ KHOA HỌC HỆ THỐNG THÔNG TIN 2016CLC Hà Nội – 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- Huỳnh Thành Trung 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 Chuyên ngành : Hệ thống thông tin LUẬN VĂN THẠC SĨ KHOA HỌC HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC : 1.
- Katsumi Inoue Hà Nội – 2017 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn: Huỳnh Thành Trung Đề tài luận văn: 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 Chuyên ngành: Hệ thống thông tin Mã số SV: CBC16001 Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày với các nội dung sau.
- Nêu lên các cơ sở lý thuyết về 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 hướng tiếp cận giải bài toán tối ưu tổ hợp như tìm kiếm cục bộ, quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc và các kỹ thuật bổ trợ như Loại bỏ đối xứng, Phân rã bài toán, Phân cụm.
- Chương 3: Đề xuất thuật toán giải bài toán xếp lịch bảo vệ cao học.
- Trình bày thuật toán đề xuất với các phương pháp sử dụng để cải thiện mô hình hóa bài toán và các phương pháp sử dụng để tìm kiếm lời giải cho bài toán, sau đó là thực nghiệm đánh giá so sánh kết quả của thuật toán đề xuất.
- Tôi xin chân thành cảm ơn! Hà Nội, ngày 12 tháng 03 năm 2017 Học viên Huỳnh Thành Trung Danh mục các bảng biểu sử dụng trong đồ án Bảng 1: Một số API tiêu biểu của thư viện OpenCBLS.
- 40 Bảng 2: Bảng so sánh hiệu năng mô hình nQueen sử dụng Symmetry Breaking.
- 65 Bảng 5: Bảng thực nghiệm đánh giá hiệu quả của thuật toán KPBC.
- 75 Bảng 7: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiếm lời giải tối ưu từng phần với một phân hoạch.
- 83 Bảng 8: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiếm cục bộ sử dụng lời giải từng phần.
- 90 Danh mục các hình vẽ sử dụng trong đồ án Hình 1: Minh họa cho bài toán TSP với 4 thành phố.
- 11 Hình 2: Ví dụ về chu trình con của bài toán TSP.
- 12 Hình 3: Minh họa Local search với bài toán 4-queen.
- 20 Hình 4: Minh họa lời giải cực trị địa phương trong LS.
- 21 Hình 5: Minh họa Backtracking Search với bài toán 4-queen.
- 35 Hình 8: Minh họa Symmetry Breaking với bài toán N-queens.
- 47 Hình 10: Ví dụ minh họa bài toán ghép cặp cực đại.
- 63 Hình 16: Mô hình pha 1-1 của bài toán MTDT.
- 69 Hình 18: Ví dụ minh họa trường hợp kết quả phân cụm không sử dụng được70 Hình 19: Ví dụ minh họa thuật toán hậu xử lý kết quả phân cụm.
- 72 Hình 20: Mô hình pha 1-2 của bài toán.
- 78 Hình 21: Minh họa phân hoạch láng giềng trong tìm kiếm cục bộ.
- 85 Danh mục các từ ngữ viết tắt và thuật ngữ Chữ viết tắt Tên đầy đủ Ý nghĩa NP Non-determistic polynomial Lớp bài toán quyết định chưa có thuật toán độ phức tạp đa thức để giải LS Local search Tìm kiếm cục bộ CP Constraint Programming Quy hoạch ràng buộc CBLS Constraint-based Local search Tìm kiếm cục bộ dựa trên ràng buộc MỤC LỤC MỤC LỤC.
- Bài toán tối ưu tổ hợp: tính cần thiết và các khó khăn.
- Các phương pháp giải quyết.
- Bài toán xếp lịch bảo vệ cao học.
- Nội dung luận văn.
- Bài toán tối ưu hóa tổ hợp.
- Phương pháp tổng trọng số trong bài toán tối ưu hóa tổ hợp đa mục tiêu.
- Ví dụ - Bài toán người du lịch (TSP.
- Bài toán xếp lịch bảo vệ cao học (MTDT.
- Mô tả bài toán.
- Mô hình toán học của bài toán.
- Ví dụ minh họa.
- Các hướng tiếp cận giải bài toán tối ưu tổ hợp.
- Tìm kiếm cục bộ.
- Quy hoạch ràng buộc.
- Tìm kiếm cục bộ dựa trên ràng buộc.
- 40 Chương 3: Đề xuất thuật toán giải bài toán xếp lịch bảo vệ cao học.
- Các phương pháp sử dụng cải thiện mô hình bài toán.
- Kỹ thuật phân rã thu gọn bài toán.
- Các phương pháp sử dụng để tìm kiếm lời giải cho bài toán.
- Tìm kiếm cục bộ sử dụng lời giải từng phần.
- Giới thiệu chung Tên đề tài luận văn: 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.
- Sơ lược: 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 sẽ 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ụ).
- Bài toán tối ưu tổ hợp: tính cần thiết và các khó khăn Bài toán tối ưu tổ hợp là lớp bài toán trong đó chúng ta phải đưa ra lời giải quyết định thỏa mãn một số những ràng buộc và đồng thời tối ưu hóa một hoặc nhiều những mục tiêu có tính mâu thuẫn với nhau (ví dụ: trong bài toán lên kế hoạch sản xuất, chất lượng sản phẩm, tốc độ sản xuất, hiệu quả sản xuất và chi phí sản xuất là những mục tiêu có tính mâu thuẫn với nhau).
- Trên thực tế hiện nay, các bài toán tối ưu hóa tổ hợp xuất hiện rất 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ế, etc … Việc giải quyết tốt các bài toán như vậy là rất quan trọng, bởi chất lượng của các phương án đưa ra liên quan trực tiếp đến chất 2 lượng của cuộc sống chúng ta: công việc sản xuất được tối ưu hơn giúp đưa ra các sản phẩm có chất lượng tốt mà giá thành hợp lý.
- năng lượng được sử dụng tối ưu nên tiết kiệm hơn mà vẫn đảm bảo được hiệu năng.
- việc xếp lịch được tối ưu giúp cho mọi người làm việc hiệu quả hơn và tránh được những rắc rối không mong muốn (trùng thời gian, không cân đối, v.v.
- Có rất, rất nhiều những ví dụ tương tự như vậy, qua đó thể hiện mức độ phổ biến và nhu cầu giải quyết của các bài toán tối ưu hóa tổ hợp trong cuộc sống là rất lớn.
- Tuy rất phổ biến và cần thiết như vậy, việc giải các bài toán tối ưu hóa tổ hợp nhìn chung gặp nhiều khó khăn.
- Các bài toán này thuộc lớp NP-đầy đủ, trong đó chúng ta có thể kiểm chứng nhanh chóng bất kỳ một lời giải nào có phải là lời giải thỏa mãn cho bài toán hay không (trong thời gian đa thức), nhưng hiện chưa có cách nào tìm ra lời giải thỏa mãn một cách hiệu quả (độ phức tạp thuật toán vẫn là độ phức tạp lũy thừa) [2, 6].
- Nói cách khác, thời gian thực thi của tất cả các thuật toán hiện tại cho những bài toán này đều tăng rất nhanh theo kích thước bài toán.
- Các phương pháp giải quyết Mặc dù các bài toán tối ưu hóa tổ hợp rất khó để giải quyết, các nhà nghiên cứu về tối ưu hóa trong những năm qua vẫn cố gắng nghiên cứu tìm ra các phương pháp để giải các bài toán này một cách tốt nhất có thể được.
- Có thể chia các phương pháp thành hai dạng chính.
- Các phương pháp giải đúng: tiêu biểu có thể kể đến o Constraint programming (Quy hoạch ràng buộc): là khuôn mẫu lập trình trong đó mối quan hệ của các biến quyết định được biểu diễn bằng các ràng buộc.
- Người dùng có thể sử dụng các ràng buộc và các biến quyết định để mô hình hóa bài toán cần giải, sau đó sử dụng các phương pháp cắt tỉa không gian tìm kiếm dựa vào sự lan truyền của các ràng buộc để tìm ra lời giải cho bài toán.
- Phương pháp này đảm bảo đưa ra 3 được lời giải tốt nhất nhờ vào việc tìm kiếm quay lui, không gian lời giải được vét cạn.
- Ưu điểm của quy hoạch ràng buộc là người dùng có thể sử dụng các ràng buộc được định nghĩa trước hoặc tự mình định nghĩa để mô hình hóa bài toán, các ràng buộc này khá tự nhiên với cách hiểu của con người và linh hoạt cho việc mô hình hóa.
- o Integer Linear Programming (Quy hoạch nguyên): là khuôn mẫu lập trình trong đó sử dụng các biến nguyên và sử dụng các quan hệ tuyến tính để biểu diễn mô hình bài toán cần giải, sau đó sử dụng các phương pháp như cắt tỉa, đơn hình, v.v… để tìm ra lời giải của bài toán.
- o Logic Programming (Quy hoạch logic): là khuôn mẫu lập trình trong đó sử dụng các vị từ (có thể hiểu là các biến boolean, nhận giá trị true hoặc false) để mô hình hóa bài toán thông qua các mệnh đề, sau đó sử dụng các giải thuật để tìm kiếm lời giải của bài toán, phổ biến nhất là tìm kiếm quay lui (backtracking search.
- Các phương pháp xấp xỉ: sử dụng các metaheuristic, có thể chia thành 2 loại o Local search (Tìm kiếm cục bộ): là thuật toán xấp xỉ trong đó đòi hỏi chúng ta phải mô hình hóa được không gian lời giải của bài toán và mối quan hệ láng giềng giữa các lời giải.
- Trong quá trình tìm kiếm, giải thuật sẽ di chuyển lần lượt qua các lời giải lân cận với lời giải hiện tại tại mỗi bước với mong muốn tìm được lời giải tối ưu.
- Ưu điểm của tìm kiếm cục bộ là có thể làm việc trong thời gian tùy ý, do đó có ích khi giải quyết các bài toán tối ưu tổ hợp cần đưa ra một lời giải tốt trong thời gian bị hạn chế.
- Tuy nhiên nhược điểm của tìm kiếm cục bộ là lời giải tìm được có thể là không tối ưu nhất mà bị kẹt ở một tối ưu cục bộ.
- Các metaheuristic là local search tiêu biểu có thể kể đến là hill-climbing, tabu search, simulated annealing, v.v… 4 o Global search (Tìm kiếm toàn cục): trái với local search – thực hiện việc tìm kiếm lời giải tối ưu thông qua thông tin cục bộ của một lời giải với các lời giải láng giềng của nó, tìm kiếm toàn cục thường dựa vào thông tin của một quần thể các lời giải để tìm kiếm lời giải tối ưu.
- Bài toán xếp lịch bảo vệ cao học Bài toán xếp lịch cao học là một bài toán tối ưu hóa tổ hợp xuất hiện ở các trường đại học của Việt Nam hiện nay.
- Phương pháp này có nhiều nhược điểm, bởi nghiệp vụ xếp lịch bảo vệ cao học là một nghiệp vụ phức tạp bởi nhiều các ràng buộc (các giáo viên của một hội đồng không trùng nhau, các giáo viên không trùng kíp, các hội đồng không trùng kíp phòng, yêu cầu giảng viên trong/ngoài trường cho các vị trí thành viên trong hội đồng, v.v…) mà người xếp lịch thủ công rất khó khăn trong việc theo dõi và kiểm soát.
- Hơn nữa, kể cả khi những ràng buộc chặt này được thỏa mãn, thì lịch bảo vệ được xếp bởi con người khó lòng đạt được sự tối ưu với tổ hợp các mục tiêu phức tạp như: mức độ phù hợp của các phản biện với đề tài, một giáo viên không ngồi quá nhiều hội đồng, v.v… Do đó việc giải quyết bài toán xếp lịch cao học tự động bằng thuật toán là nhu cầu cần thiết.
- Lý do thực hiện Xuất phát từ nhu cầu thực tiễn của các bài toán tối ưu hóa tổ hợp nói chung (phần 1.2.1) và bài toán xếp lịch bảo vệ cao học nói riêng (phần 1.2.3), chúng tôi: 5 - Tìm hiểu việc sử dụng quy hoạch ràng buộc và tìm kiếm cục bộ trong việc giải quyết các bài toán tối ưu hóa tổ hợp với mong muốn có nền tảng kiến thức vững chắc trong việc giải quyết các bài toán này.
- Đề xuất một thuật toán hiệu quả giải quyết bài toán xếp lịch bảo vệ cao học, sử dụng quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc.
- Ngoài ra, thuật toán đề xuất còn sử dụng phân cụm cân bằng để phân rã bài toán thành các bài toán con và xử lý song song.
- Với thuật toán đề xuất, chúng tôi mong muốn đây sẽ là một giải pháp được áp dụng vào thực tế để giảm thiểu công sức của các giáo vụ và tăng chất lượng tối ưu của các lịch được xếp.
- Bài toán tối ưu hóa tổ hợp 2.1.1.
- Một số khái niệm Như phần 1.2.1 đã giới thiệu, bài toán tối ưu hóa tổ hợp là lớp bài toán trong đó chúng ta phải đưa ra lời giải/ quyết định thỏa mãn một số những ràng buộc/ giới hạn và đồng thời tối ưu hóa một hoặc nhiều những mục tiêu có tính mâu thuẫn với nhau.
- Đây là những bài toán xuất hiện và có vai trò quan trọng trên mọi lĩnh vực của cuộc sống, từ năng lượng, giao thông vận tải, tổ chức hành chính, sản xuất, v.v… Sau đây là định nghĩa cụ thể hơn cho các khái niệm liên quan và cho bài toán tối ưu hóa tổ hợp.
- Định nghĩa 2.1: Biến quyết định của bài toán (Decision variable) Biến quyết định của bài toán tối ưu hóa tổ hợp là một biến nằm trong mô hình của bài toán mà người ra quyết định có thể kiểm soát được giá trị của biến đó và cần xác định giá trị cho biến đó.
- Biến quyết định có thể coi như những tế bào xây dựng nên bài toán tối ưu hóa tổ hợp.
- Biến quyết định của bài toán thường được ký hiệu là x, và tập hợp các biến quyết định của bài toán là X.
- Trong khuôn khổ của luận văn, chúng tôi chỉ xét các bài toán tối ưu hóa tổ hợp rời rạc, trong đó miền của tất cả các biến quyết định cấu

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt