Luận án: Nghiên cứu biến thể bài toán hôn nhân ổn định theo tiếp cận heuristic - Nguyễn Thị Uyên

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN THỊ UYÊN NGHIÊN CỨU MỘT SỐ BIẾN THỂ CỦA BÀI TOÁN HÔN NHÂN ỔN ĐỊNH THEO TIẾP CẬN HEURISTIC LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH Hà Nội - 2023 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN THỊ UYÊN NGHIÊN CỨU MỘT SỐ BIẾN THỂ CỦA BÀI TOÁN HÔN NHÂN ỔN ĐỊNH THEO TIẾP CẬN HEURISTIC LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH Mã số: 9 48 01 01 Xác nhận của Học viện Người hướng dẫn 1 Người hướng dẫn 2 Khoa học và Công nghệ (Ký, ghi rõ họ tên) (Ký, ghi rõ họ tên) PGS. Hoàng Hữu Việt PGS.TS Nguyễn Long Giang Hà Nội - 2023 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả công bố trong luận án là công trình nghiên cứu của bản thân tôi trong thời gian học tập, nghiên cứu và được hoàn thành với sự hướng dẫn của hai Thầy giáo gồm PGS. Hoàng Hữu Việt và PGS. Nguyễn Long Giang.

Các tài liệu tham khảo được trích dẫn đầy đủ và được ghi rõ ở phần tài liệu tham khảo. Các kết quả nghiên cứu được thực nghiệm trên cùng một môi trường thực nghiệm và được ghi nhận một cách khách quan, trung thực và đã được công bố trên các tạp chí khoa học chuyên ngành. Hà Nội, ngày 31 tháng 03 năm 2023 Nguyễn Thị Uyên i LỜI CẢM ƠN Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự giúp đỡ nhiệt tình từ các thầy giáo hướng dẫn, bạn bè và người thân trong suốt 4 năm học tập và nghiên cứu tại Viện Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Đầu tiên, tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc tới hai Thầy giáo hướng dẫn PGS.TS Hoàng Hữu Việt và PGS.TS Nguyễn Long Giang.

Sự tận tình chỉ bảo, hướng dẫn và động viên của các Thầy dành cho tác giả trong suốt thời gian thực hiện luận án. Tác giả xin gửi lời cảm ơn tới các Thầy, Cô giáo và Cán bộ bộ phận quản lý nghiên cứu sinh của Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam và bộ phận quản lý sau đại học của Viện Công nghệ thông tin đã nhiệt tình giúp đỡ và tạo ra môi trường nghiên cứu tốt để tác giả hoàn thành công trình của mình. Tác giả xin chân thành cảm ơn tới Ban Giám hiệu Trường Đại học Vinh, các đồng nghiệp ở Viện Kỹ thuật và Công nghệ, nơi tác giả đang công tác đã luôn động viên, giúp đỡ tác giả trong công tác để tác giả có thời gian tập trung nghiên cứu và hoàn thành luận án đúng thời hạn. Cuối cùng tác giả muốn bày tỏ lòng biết ơn sâu sắc nhất tới gia đình và bạn bè đã luôn động viên, chia sẻ, ủng hộ và giúp đỡ tác giả vượt qua những khó khăn để đạt được những kết quả nghiên cứu trong luận án.

Tác giả xin trân trọng cảm ơn! Hà Nội, ngày 31 tháng 03 năm 2023 Nguyễn Thị Uyên ii MỤC LỤC LỜI CAM ĐOAN. ii Mục lục. iii Danh mục các ký hiệu, các chữ viết tắt. vi Danh mục các hình vẽ.

vii Danh mục các bảng biểu. viii CHƯƠNG 1. TỔNG QUAN VỀ BÀI TOÁN HÔN NHÂN ỔN ĐỊNH 6 1.1 Bài toán hôn nhân ổn định .2 Các nghiên cứu liên quan .2 Các biến thể của bài toán hôn nhân ổn định .1 Bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng .2 Bài toán hôn nhân ổn định với danh sách không đầy đủ .3 Bài toán hôn nhân ổn định với danh sách xếp hạng ngang bằng và không đầy đủ .4 Các nghiên cứu liên quan .3 Một số bài toán mở rộng của bài toán SMTI .1 Bài toán Hospitals/Residents with Ties .2 Bài toán Student-Project Allocation .3 Các nghiên cứu liên quan .4 Vấn đề tồn tại .5 Định hướng nghiên cứu .6 Phương pháp thực nghiệm và đánh giá .1 Bộ dữ liệu .2 Ngôn ngữ và cấu hình cài đặt .7 Kết luận chương 1. ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-SMTI 28 2.2 Đề xuất thuật toán MCS.3 Mô tả thuật toán.5 Các kết quả thực nghiệm.3 Đề xuất thuật toán HR.2 Mô tả thuật toán.4 Các kết quả thực nghiệm.4 Kết luận Chương 2.

ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-HRT 53 3.2 Đề xuất thuật toán MCA.2 Mô tả thuật toán.4 Các kết quả thực nghiệm.3 Đề xuất thuật toán HS.2 Mô tả thuật toán.4 Các kết quả thực nghiệm.4 Kết luận Chương 3. ĐỀ XUẤT THUẬT TOÁN GIẢI BÀI TOÁN MAX-SPA 74 4.2 Đề xuất thuật toán SPA-P-heuristic giải bài toán MAX-SPA-P.3 Mô tả thuật toán.5 Các kết quả thực nghiệm.3 Đề xuất thuật toán HAG giải quyết bài toán MAX-SPA-ST.3 Mô tả thuật toán.5 Các kết quả thực nghiệm.4 Kết luận Chương 4. 102 KẾT LUẬN 104 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA NGHIÊN CỨU SINH VÀ CỘNG SỰ 106 Tài liệu tham khảo 108 PHỤ LỤC A.1 Thuật toán Gale-Shapley .2 Thuật toán tạo danh sách xếp hạng. P2 v DANH MỤC CÁC CHỮ VIẾT TẮT STT Từ viết tắt Tiếng Anh Ý nghĩa 1 AS Adaptive Search Tìm kiếm thích nghi 2 CSP Constraint Satisfaction Problem Bài toán thỏa mãn ràng buộc 3 GS Gale-Shapley Thuật toán Gale-Shapley 4 HR Heuristic Repair Thuật toán sửa đổi heuristic 5 HRT Hospitals/Residents problem with Bài toán phân bổ sinh viên thực tập Ties tại các doanh nghiệp 6 HS Heuristic Search Tìm kiếm Heuristic 7 MAX-HRT Maximum Stable Matching for HRT Phép ghép ổn định với kích thước tối đa cho HRT 8 MAX-SMTI Maximum Stable Matching for Phép ghép ổn định với kích thước tối SMTI đa cho SMTI 9 MAX-SPA Maximum Stable Matching for SPA Phép ghép ổn định với kích thước tối đa cho SPA 10 MCA Min-Conflicts Algorithm Thuật toán xung đột tối thiểu 11 MCS Max-Conflicts based heuristic Thuật toán tìm kiếm heuristic dựa Search trên các xung đột tối đa 12 SMI Stable Marriage problem with Bài toán hôn nhân ổn định với danh Incomplete lists sách xếp hạng không đầy đủ 13 SMP Stable Marriage Problem Bài toán hôn nhân ổn định 14 SMT Stable Marriage with Ties Problem Bài toán hôn nhân ổn định với danh sách xếp hạng ngang hàng 15 SMTI Stable Marriage with Ties and Bài toán hôn nhân ổn định với danh Incomplete lists sách xếp hạng ngang hàng và không đầy đủ 16 SPA Student-Project Allocation Problem Bài toán phân bổ đề tài cho sinh viên 17 SPA-P Student-Project Allocation problem Bài toán phân bổ đề tài cho sinh viên with lecturer preferences over với danh sách xếp hạng của giảng Projects viên dựa vào đề tài 18 SPA-S Student-Project Allocation problem Bài toán phân bổ đề tài cho sinh viên with lecturer preferences over với danh sách xếp hạng của giảng Students viên dựa vào sinh viên 19 SPA-ST Student-Project Allocation problem Bài toán phân bổ đề tài cho sinh viên with lecturer preferences over với danh sách xếp hạng của giảng Students containing Ties viên dựa vào đề tài có chứa quan hệ ngang hàng 20 UBP Undominated Blocking Pair Cặp chặn trội nhất 21 UBPS Undominated Blocking Pairs Tập hợp các cặp chặn trội nhất vi DANH MỤC CÁC HÌNH VẼ Hình 1 Cấu trúc của luận án .1 Thời gian thực hiện trung bình MCS và LTIU.2 Phần trăm phép ghép ổn định của MCS và LTIU.3 Phần trăm phép ghép hoàn chỉnh của MCS và LTIU.4 Thời gian thực hiện trung bình của MCS và AS.5 Trung bình số bước lặp và khởi tạo lại của MCS và AS.6 Chất lượng nghiệm của MCS và AS khi p2 = 1.7 Trung bình thời gian thực hiện và số bước lặp của MCS.8 Trung bình số lần gọi hàm khởi tạo và số cặp chặn vượt trội.9 Phần trăm phép ghép hoàn chỉnh của HR và MCS.10 Thời gian thực hiện của của HR và MCS với n ∈ {100, 200}.11 Phần trăm phép ghép hoàn chỉnh của HR và GSA2.12 Phần trăm phép ghép hoàn chỉnh của HR và GSA2.13 Thời gian thực hiện trung bình của HR, GSA2 và GS.14 Thời gian thực hiện trung bình của HR, GSA2 và GS.1 Thời gian thực nghiệm và chất lượng nghiệm của MCA và LTIU.2 MCA với các tham số n = {100, 200, · · · , 700}.3 Phần trăm phép ghép hoàn chỉnh trong trường hợp cj = n/m .4 HS và AS với n = 200, m = 20 và cj = n/m .5 HS và AS với n = 200, m = 20 và cj = [0.6 HS và AS với n = 300, n = {15, 20, 25} và cj = n/m .7 HS và HP với n = 200, m = 20.8 HS và HP với n = 1000, m = 25.9 HS và HP với n = 1000, m = 50, 75 và 100.10 HS và HP với n = 5000.1 So sánh về chất lượng nghiệm.2 Phần trăm phép ghép và thời gian thực hiện trung bình.3 Phần trăm phép ghép và thời gian thực hiện trung bình.4 So sánh về chất lượng nghiệm.5 Phần trăm phép ghép hoàn chỉnh và thời gian thực hiện trung bình.6 Thời gian thực hiện và số bước lặp của HAG và APX.7 Phần trăm phép ghép hoàn chỉnh và số sinh viên chưa được ghép của HAG và APX.8 Thời gian thực hiện trung bình của HAG và APX.9 Trung bình số lần lặp HAG và APX với p1 ∈ [0.10 Phần trăm phép ghép hoàn chỉnh và trung bình số sinh viên chưa được ghép của HAG và APX.11 Trung bình thời gian thực hiện của HAG và APX với n = 500, m = 25, q = 50.12 Phần trăm phép ghép hoàn chỉnh và trung bình số sinh viên chưa được ghép HAG và APX.13 Trung bình thời gian thực hiện và số bước lặp của HAG và APX.14 Chất lượng nghiệm của HAG và APX với n = 10000, m = 200, q = 1000102 Hình 4.15 HAG và APX với n = 10000, m = 200, q = 1000.102 viii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Một thể hiện của bài toán SMP .2 Các nghiên cứu liên quan giải quyết bài toán SMP .3 Một thể hiện của bài toán SMT .4 Một thể hiện của bài toán SMI.5 Ví dụ của một thể hiện SMTI.6 Các nghiên cứu liên quan giải quyết bài toán MAX-SMTI.7 Ví dụ một thể hiện HRT.8 Ví dụ một thể hiện SPA-P.9 Ví dụ một thể hiện SPA-ST.10 Các nghiên cứu liên quan của bài toán HRT và SPA.1 Ví dụ của một thể hiện SMTI.2 Xóa cặp chặn UBP cho phép ghép M.3 Ví dụ thực hiện của thuật toán MCS cho MAX-SMTI.4 Ví dụ một thể hiện SMTI.1 Ví dụ một thể hiện HRT.2 Ví dụ thực hiện của thuật toán MCA.3 Ví dụ một thể hiện HRT.4 Ví dụ thực hiện của thuật toán HS.1 Một thể hiện của SPA-P.2 Ví dụ thực hiện của thuật toán SPA-P-heuristic.3 Các giá trị của tham số.4 Các giá trị tham số.5 Một thể hiện của SPA-ST.