Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Bài toán hôn nhân ổn định (Stable Marriage Problem - SMP) do Gale và Shapley giới thiệu năm 1962 là mô hình nền tảng trong lý thuyết trò chơi, tối ưu hóa tổ hợp và trí tuệ nhân tạo. Ý nghĩa lý thuyết và ứng dụng thực tiễn của mô hình này đã được khẳng định khi Alvin Roth và Lloyd Shapley được trao giải thưởng Nobel Kinh tế năm 2012. Trong thực tế, SMP và các mô hình phát triển từ nó được ứng dụng rộng rãi trong các hệ thống phân bổ nguồn lực như:

  1. Phân bổ sinh viên y khoa thực tập tại các bệnh viện (National Resident Matching Program - NRMP tại Mỹ, Resident Matching Service - CARMS tại Canada, Scottish Pre-registration House Officer Allocations tại Scotland);
  2. Phân công giảng viên hướng dẫn sinh viên thực hiện đề tài tốt nghiệp (Student-Project Allocation - SPA);
  3. Phân bổ nhà ở cho cư dân và sinh viên ký túc xá (Stable Roommates Problem);
  4. Tối ưu hóa yêu cầu dịch vụ của người dùng Internet tới các nhà mạng viễn thông.

Tuy nhiên, bài toán SMP truyền thống đặt ra các giả định nghiêm ngặt: danh sách xếp hạng ưu tiên phải đầy đủ và hoàn toàn không có sự ngang hàng (không có ties). Trong các ứng dụng thực tế, người tham gia thường chỉ có thể xếp hạng một tập con các đối tượng (danh sách không đầy đủ) và có thể đánh giá nhiều đối tượng có mức độ ưu tiên ngang nhau (danh sách có quan hệ ngang bằng). Sự kết hợp này dẫn đến 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 đủ (SMTI), cùng các mô hình mở rộng một-nhiều gồm: bài toán phân bổ bác sĩ/sinh viên thực tập tại các bệnh viện/doanh nghiệp có quan hệ ngang hàng (HRT) và bài toán phân công đề tài cho sinh viên (SPA).

Khi xuất hiện quan hệ ngang hàng, các tiêu chuẩn ổn định được phân hóa thành: ổn định yếu (weakly stable), ổn định mạnh (strongly stable) và siêu ổn định (super-stable). Nghiên cứu của Irving và Manlove đã chứng minh rằng phép ghép siêu ổn định hoặc ổn định mạnh có thể không tồn tại trên mọi thể hiện, trong khi phép ghép ổn định yếu luôn luôn tồn tại nhưng kích thước của các phép ghép ổn định yếu lại khác nhau. Bài toán tìm kiếm một phép ghép ổn định yếu có kích thước lớn nhất (MAX-SMTI, MAX-HRT, MAX-SPA) đã được chứng minh là bài toán thuộc lớp NP-khó.

Khoảng trống nghiên cứu được luận án chỉ ra:

  • Các thuật toán xấp xỉ hiện hành (với tỷ lệ xấp xỉ tốt nhất là $3/2$) cho chất lượng nghiệm chưa tối ưu và thiếu các thử nghiệm quy mô lớn.
  • Các thuật toán tìm kiếm cục bộ và lập trình thỏa mãn ràng buộc trước đây (như thuật toán LTIU của Gelain và cộng sự, hoặc thuật toán tìm kiếm thích nghi AS của Munera và cộng sự) đòi hỏi không gian tìm kiếm lân cận lớn với chi phí tính toán cao ($O(n^3)$ cho mỗi bước lặp để đánh giá lân cận), dẫn đến thời gian thực thi chậm và dễ bị mắc kẹt tại các cực tiểu cục bộ khi giải quyết các thể hiện có kích thước lớn.

Mục tiêu nghiên cứu

Luận án tập trung nghiên cứu, thiết kế và đánh giá các thuật toán tìm kiếm heuristic nhằm tìm kiếm phép ghép ổn định yếu có kích thước tối đa cho bài toán SMTI và các biến thể mở rộng, cụ thể gồm 3 mục tiêu:

  1. Đề xuất các thuật toán tìm kiếm heuristic giải quyết bài toán MAX-SMTI;
  2. Đề xuất các thuật toán tìm kiếm heuristic giải quyết bài toán MAX-HRT;
  3. Đề xuất các thuật toán tìm kiếm heuristic giải quyết bài toán MAX-SPA (bao gồm hai biến thể MAX-SPA-P và MAX-SPA-ST).

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Cấu trúc toán học, độ phức tạp tính toán và các thuật toán tìm kiếm heuristic cho bài toán MAX-SMTI, MAX-HRT và MAX-SPA.
  • Phạm vi nghiên cứu:
    • Về mặt lý thuyết: Tập trung vào tiêu chuẩn phép ghép ổn định yếu (weakly stable matching) với mục tiêu tối đa hóa kích thước phép ghép.
    • Về mặt thực nghiệm: Đánh giá thuật toán thông qua việc sinh các bộ dữ liệu ngẫu nhiên với các không gian tham số có kiểm soát, đo lường thời gian tính toán, tỷ lệ tìm thấy phép ghép ổn định, tỷ lệ phép ghép hoàn chỉnh và số bước lặp trên môi trường tính toán quy chuẩn.

Tổng quan tài liệu và vị trí của luận án

Luận án đã hệ thống hóa các công trình nghiên cứu trong và ngoài nước liên quan đến bài toán hôn nhân ổn định và các biến thể theo các nhóm phương pháp chính:

Hướng tiếp cận Tác giả & Năm công bố Phương pháp / Thuật toán Mục tiêu xử lý
Thuật toán xấp xỉ Gale và Shapley (1962) [1] Thuật toán Gale-Shapley (GS) Tìm phép ghép ổn định tối ưu một phía cho SMP
Manlove và cộng sự (2002) [7, 8] Thuật toán 2-xấp xỉ Phân tích độ phức tạp NP-khó và tìm nghiệm cho SMT, SMTI, HRT
Halldórsson và cộng sự (2003, 2007) [47, 17] Thuật toán xấp xỉ trên đồ thị Tối ưu bình đẳng, tỷ lệ xấp xỉ $13/7$ cho MAX-SMTI
Iwama và cộng sự (2004–2012) [50, 55, 96] Tìm kiếm cục bộ / xấp xỉ Tỷ lệ xấp xỉ cho MAX-SMTI và bài toán MAX-SPA-P
McDermid (2009) [57] Thuật toán xấp xỉ tỷ lệ $3/2$ Thời gian tính toán $O(n^{3/2}L)$ cho MAX-SMTI
Király (2013) [60] Thuật toán GSA2 và HP Tỷ lệ xấp xỉ $3/2$ thời gian tuyến tính cho MAX-SMTI và MAX-HRT
Paluch (2012, 2014) [59, 61] Cải tiến thuật toán xấp xỉ $3/2$ Khám phá cấu trúc danh sách cho SMTI
Cooper và Manlove (2018) [89] Thuật toán APX Tỷ lệ xấp xỉ $3/2$ cho bài toán MAX-SPA-ST
Abraham và cộng sự (2003) [3] Thuật toán xấp xỉ thời gian $O(m)$ Phép ghép ổn định cho SPA-S (tối ưu sinh viên / giảng viên)
Heuristic & Trí tuệ nhân tạo Codognet và cộng sự (2001) [41] Tìm kiếm cục bộ dựa trên CSP Mô hình hóa SMP dưới dạng bài toán thỏa mãn ràng buộc
Gent và Prosser (2001, 2002) [42, 54] Thuật toán sinh ngẫu nhiên Thiết lập mô hình sinh dữ liệu kiểm thử chuẩn cho SMP, SMTI
Nakamura và cộng sự (2005) [33] Thuật toán di truyền (GA) Tìm phép ghép ổn định hai phía cho SMP
Vien và cộng sự (2007) [23] Tối ưu hóa đàn kiến (ACS) Tìm phép ghép ổn định cân bằng cho SMP
Gelain và cộng sự (2010, 2013) [10, 43] Tìm kiếm cục bộ (LTIU, SML) Xử lý MAX-SMTI và tìm phép ghép ổn định hai phía
Munera và cộng sự (2015) [13, 65, 99] Tìm kiếm thích nghi (Adaptive Search - AS) Giải MAX-SMTI và chuyển đổi HRT về SMTI
Việt và cộng sự (2016, 2019) [22, 35] Short list-BilS Tối ưu hóa cân bằng giới tính cho SMT và SMP
Harper và cộng sự (2005) [94] Thuật toán di truyền Giải quyết bài toán MAX-SPA-S
Chown và cộng sự (2018) [98] Mô phỏng luyện kim (Simulated Annealing) Giải quyết bài toán MAX-SPA-P
Quy hoạch & Tiếp cận khác Vohra và cộng sự (2012) [24] Quy hoạch tuyến tính Phân tích cấu trúc polytope cho SMTI
Drummond và cộng sự (2015, 2020) [68] Mô hình SAT Mã hóa bài toán SMTI và SMTI có cặp đôi
Kwanashie và cộng sự (2013, 2020) [19] Quy hoạch nguyên (IP / ILP) Giải quyết chính xác MAX-HRT và MAX-SMTI
Diebold và Bichler (2017) [93] Quy hoạch nguyên tuyến tính (ILP) Khảo sát thực nghiệm 8 thuật toán trên dữ liệu phân bổ khóa học
Erdem và cộng sự (2020) [70] Answer Set Programming (ASP) Giải quyết bài toán MAX-SMTI bằng logic vị từ

Vị trí của luận án

Dựa trên phân tích các công trình trước đây, các phương pháp quy hoạch nguyên (ILP/SAT) cho lời giải tối ưu nhưng chi phí tính toán bùng nổ theo hàm mũ khi kích thước bài toán lớn; các thuật toán xấp xỉ lý thuyết bị chặn dưới bởi tỷ lệ $3/2$ và chất lượng thực nghiệm chưa cao; các thuật toán tìm kiếm heuristic hiện có (LTIU, AS) bị suy giảm hiệu năng do kích thước không gian lân cận quá lớn và chiến lược thoát cực tiểu cục bộ chưa tối ưu. Luận án định vị nghiên cứu vào việc phát triển các cấu trúc chọn lọc xung đột dựa trên tập các cặp chặn trội nhất (Undominated Blocking Pairs - UBPS) và cơ chế sửa lỗi heuristic (Heuristic Repair) nhằm giảm độ phức tạp mỗi bước lặp từ $O(n^3)$ xuống $O(n^2)$, cho phép xử lý hiệu quả các bài toán kích thước lớn (lên tới hàng nghìn tác nhân).

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và các khái niệm cơ bản

  • 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 đủ (SMTI):
    • Cho tập $n$ người nam $M = {m_1, m_2, \dots, m_n}$ và tập $n$ người nữ $W = {w_1, w_2, \dots, w_n}$.
    • Mỗi tác nhân có một danh sách xếp hạng sở thích gồm các đối tượng chấp nhận được từ tập đối tác, trong đó có thể chứa các liên kết ngang bằng (ties), ký hiệu bằng dấu ngoặc đơn $(\dots)$.
    • Phép ghép $M$ là tập các cặp $(m_i, w_j) \in M \times W$ sao cho mỗi cá nhân được ghép với tối đa một đối tác. Nếu $m_i$ không được ghép, ký hiệu $M(m_i) = \emptyset$.
    • Cặp $(m_i, w_j)$ là một cặp chặn yếu (weakly blocking pair) cho phép ghép $M$ nếu:
      1. $(m_i, w_j)$ chấp nhận lẫn nhau;
      2. $m_i$ độc thân hoặc thực sự thích $w_j$ hơn bạn ghép hiện tại $M(m_i)$;
      3. $w_j$ độc thân hoặc thực sự thích $m_i$ hơn bạn ghép hiện tại $M(w_j)$.
    • Phép ghép $M$ được gọi là ổn định yếu (gọi tắt là ổn định) nếu không tồn tại bất kỳ cặp chặn yếu nào. Kích thước $|M|$ là số cặp được ghép trong $M$. Phép ghép hoàn chỉnh khi $|M| = n$.
  • Cặp chặn trội (Dominated Blocking Pair) và Cặp chặn trội nhất (Undominated Blocking Pair - UBP):
    • Cặp chặn $(m_i, w_j)$ vượt trội (dominate) cặp chặn $(m_i, w_k)$ theo thứ tự xếp hạng của $m_i$ nếu $rank(m_i, w_j) < rank(m_i, w_k)$.
    • Cặp $(m_i, w_j)$ là cặp chặn trội nhất (UBP) nếu không tồn tại cặp $(m_i, w_k)$ nào khác mà $m_i$ thích hơn $w_j$. Ký hiệu $X$ là tập các UBP của phép ghép $M$.
  • Bài toán Hospitals/Residents with Ties (HRT):
    • Mở rộng một-nhiều giữa tập sinh viên/bác sĩ nội trú $R = {r_1, \dots, r_n}$ và tập bệnh viện/doanh nghiệp $H = {h_1, \dots, h_m}$, trong đó mỗi bệnh viện $h_j$ có chỉ tiêu tiếp nhận tối đa $c_j \in \mathbb{Z}^+$.
  • Bài toán Student-Project Allocation (SPA):
    • Gồm tập sinh viên $S = {s_1, \dots, s_n}$, tập đề tài $P = {p_1, \dots, p_q}$, và tập giảng viên $L = {l_1, \dots, l_m}$.
    • Mỗi đề tài $p_j$ có dung lượng $c_j$, mỗi giảng viên $l_k$ có dung lượng $d_k$.
    • Biến thể SPA-P: Giảng viên xếp hạng ưu tiên theo đề tài ($P$).
    • Biến thể SPA-ST: Giảng viên xếp hạng ưu tiên theo sinh viên ($S$) và danh sách có chứa quan hệ ngang hàng (ties).

Phương pháp nghiên cứu thực tế

  1. Phương pháp nghiên cứu lý thuyết:
    • Mô hình hóa toán học các điều kiện biên và không gian trạng thái;
    • Thiết lập hàm đánh giá heuristic $f(M)$ dựa trên số lượng tác nhân độc thân và hàm heuristic lựa chọn cặp xung đột $h(m_i) = n \times ubp(w_j) - rank(w_j, m_i)$;
    • Chứng minh tính hội tụ của thuật toán qua việc giải phóng các chuỗi xung đột UBP.
  2. Phương pháp thực nghiệm định lượng:
    • Sử dụng thuật toán sinh dữ liệu ngẫu nhiên của Gent và cộng sự (2002) để tạo các bộ dữ liệu kiểm định theo các phân phối tham số:
      • Thể hiện SMTI: Bộ 3 tham số $(n, p_1, p_2)$ với kích thước $n$, xác suất không đầy đủ $p_1 \in [0.0, 0.8]$, xác suất quan hệ ngang hàng $p_2 \in [0.0, 1.0]$.
      • Thể hiện HRT: Bộ 5 tham số $(n, m, p_1, p_2, c_j)$.
      • Thể hiện SPA-P: Bộ 6 tham số $(n, m, q, p, c_j, d_k)$.
      • Thể hiện SPA-ST: Bộ 7 tham số $(n, m, q, p_1, p_2, c_j, d_k)$.
    • Tiêu chí định lượng đo lường:
      • Thời gian thực hiện trung bình (đơn vị: giây hoặc $\log_{10}(\text{giây})$);
      • Tỷ lệ phần trăm tìm thấy phép ghép ổn định (%);
      • Tỷ lệ phần trăm tìm thấy phép ghép hoàn chỉnh (%);
      • Số bước lặp trung bình và số lần gọi hàm tái khởi tạo (resets).
  3. Môi trường và công cụ cài đặt:
    • Ngôn ngữ lập trình: MATLAB 2019a.
    • Cấu hình phần cứng thực nghiệm: Máy tính cá nhân CPU Intel Core i7-8550U 1.8GHz, RAM 16 GB.

Nội dung chính theo từng chương

Chương 1. Tổng quan về bài toán hôn nhân ổn định

Chương 1 thiết lập nền tảng lý thuyết và tổng quan tài liệu về bài toán SMP, các biến thể (SMT, SMI, SMTI) và các bài toán mở rộng (HRT, SPA). Tác giả phân tích các điều kiện ổn định yếu, ổn định mạnh, siêu ổn định và trình bày chi tiết chứng minh của Manlove và Irving về độ phức tạp NP-khó của bài toán tối đa hóa kích thước phép ghép ổn định yếu.

Nội dung chương trình bày chi tiết quy trình sinh dữ liệu kiểm thử chuẩn:

  • Đối với bài toán SMTI, với mỗi bộ tham số $(n, p_1, p_2)$, hệ thống sinh 100 thể hiện ngẫu nhiên. Với $p_1$ nhận 8 giá trị từ $0.1$ đến $0.8$ và $p_2$ nhận 11 giá trị từ $0.0$ đến $1.0$, tổng cộng có $100 \times 8 \times 11 = 8.800$ bộ dữ liệu được tạo ra để phục vụ đánh giá thống kê.
  • Chương 1 cũng đặc tả rõ các tiêu chuẩn đánh giá thực nghiệm và môi trường cài đặt phần mềm trên MATLAB 2019a.

Chương 2. Đề xuất thuật toán giải bài toán MAX-SMTI

Chương 2 trình bày hai thuật toán heuristic mới nhằm giải quyết bài toán MAX-SMTI:

  1. Thuật toán tìm kiếm heuristic dựa trên xung đột tối đa (Max-Conflicts based heuristic search - MCS):

    • Nguyên lý hoạt động: Bắt đầu từ một phép ghép ngẫu nhiên $M$. Tại mỗi bước lặp, thuật toán xác định tập hợp các cặp chặn trội nhất $X = \text{Find_UBPs}(M)$.
    • Hàm heuristic: Được định nghĩa cho mỗi cặp $(m_i, w_j) \in X$: $$h(m_i) = n \times ubp(w_j) - rank(w_j, m_i)$$ Trong đó $ubp(w_j)$ là số lượng cặp UBP mà người nữ $w_j$ tham gia tạo ra trong $X$. Trọng số $n$ đảm bảo ưu tiên chọn người nữ $w_j$ tạo ra nhiều xung đột nhất; sau đó chọn người nam $m_i$ mà $w_j$ thích nhất (rank nhỏ nhất).
    • Cơ chế loại bỏ: Xóa cặp $(m_i, w_j)$ tốt nhất khỏi phép ghép hiện tại, gán $m_i$ ghép với $w_j$, đưa các bạn ghép cũ về trạng thái độc thân. Thao tác này xóa bỏ toàn bộ các cặp chặn do $m_i$ và phần lớn các cặp chặn do $w_j$ tạo ra.
    • Cơ chế thoát cực tiểu cục bộ (Escape_Local_Minima): Nếu thuật toán bị kẹt tại một phép ghép không hoàn chỉnh, hàm sẽ chọn ngẫu nhiên một tác nhân độc thân ($m_j$ hoặc $w_j$ với xác suất $p \le 0.5$) và phá vỡ các cặp ghép của các đối tác nằm trong danh sách xếp hạng của tác nhân đó.
    • Kết quả thực nghiệm của MCS:
      • So sánh với thuật toán LTIU ($n=100$, tối đa 3.000 bước lặp): MCS chạy nhanh hơn LTIU khoảng 90 lần. Về chất lượng, MCS đạt tỷ lệ tìm thấy phép ghép ổn định 100% trên mọi miền tham số, trong khi LTIU giảm mạnh khi $p_2$ tăng; tỷ lệ phép ghép hoàn chỉnh của MCS vượt trội hoàn toàn so với LTIU.
      • So sánh với thuật toán tìm kiếm thích nghi AS ($n=500$, tối đa 3.000 bước lặp): MCS chạy nhanh gấp khoảng 2 lần so với AS. Khi $p_2$ tăng từ $0.0$ đến $0.9$, MCS không cần gọi hàm khởi tạo lại (resets = 0), trong khi AS phải gọi trung bình khoảng 400 lần. Tại $p_1 = 0.0$, AS không tìm được phép ghép hoàn chỉnh nào (0%), trong khi MCS đạt tỷ lệ khoảng 55%; khi $p_1 \in [0.1, 0.7]$, MCS đạt trên 90% phép ghép hoàn chỉnh.
      • Khả năng mở rộng: MCS duy trì hiệu năng ổn định trên các bài toán kích thước lớn $n \in {500, 700, 900, 1200}$.

  2. Thuật toán Heuristic Repair (HR):

    • Cơ chế sửa đổi cấu trúc phép ghép cục bộ kết hợp với việc tái khởi tạo danh sách đề xuất.
    • Thực nghiệm cho thấy HR đạt tỷ lệ phép ghép hoàn chỉnh và thời gian thực thi vượt trội khi so sánh trực tiếp với thuật toán xấp xỉ GSA2 của Király và thuật toán kinh điển GS của Gale-Shapley.

Chương 3. Đề xuất thuật toán giải bài toán MAX-HRT

Chương 3 mở rộng hướng tiếp cận heuristic cho bài toán ghép cặp một-nhiều Hospitals/Residents with Ties (MAX-HRT), giải quyết bài toán phân bổ sinh viên y khoa/bác sĩ nội trú vào các bệnh viện có giới hạn chỉ tiêu tiếp nhận ($c_j$):

  • Thuật toán Min-Conflicts (MCA): Áp dụng nguyên lý tối thiểu hóa xung đột, lựa chọn sửa đổi các liên kết vi phạm ràng buộc dung lượng và giảm thiểu sự hình thành các cặp chặn mới.
  • Thuật toán Heuristic Search (HS): Tích hợp hàm heuristic định tuyến đa tiêu chí giữa mức độ hài lòng của sinh viên và hạn ngạch của doanh nghiệp/bệnh viện.
  • Kết quả thực nghiệm:
    • So sánh thực nghiệm với thuật toán LTIU, thuật toán tìm kiếm thích nghi AS trên các cấu hình kích thước $n \in {100, 200, \dots, 700}$, các phân bố chỉ tiêu $c_j = n/m$ và $c_j$ biến thiên.
    • So sánh trực tiếp với thuật toán xấp xỉ HP của Király trên các kích thước lớn: $n=1.000$ với $m \in {25, 50, 75, 100}$ và bài toán quy mô lớn $n=5.000$. Thuật toán đề xuất đạt kích thước phép ghép ổn định lớn hơn và thời gian thực hiện tối ưu hơn so với thuật toán xấp xỉ HP.

Chương 4. Đề xuất thuật toán giải bài toán MAX-SPA

Chương 4 tập trung giải quyết bài toán phân công đề tài cho sinh viên (Student-Project Allocation) với hai biến thể cụ thể:

  1. Thuật toán SPA-P-heuristic giải bài toán MAX-SPA-P:
    • Xử lý bài toán khi giảng viên xếp hạng sở thích dựa trên danh sách các đề tài ($P$).
    • Thuật toán định vị và giải tỏa các xung đột ràng buộc kép (dung lượng đề tài $c_j$ và dung lượng tối đa của giảng viên $d_k$).
  2. Thuật toán HAG giải quyết bài toán MAX-SPA-ST:
    • Xử lý bài toán khi giảng viên xếp hạng sở thích dựa trên sinh viên ($S$) và danh sách có chứa quan hệ ngang hàng (Ties).
    • So sánh thực nghiệm với thuật toán xấp xỉ chuẩn APX của Cooper và Manlove (2018):
      • Thử nghiệm trên các cấu hình tham số: $n=500, m=25, q=50$ và cấu hình quy mô lớn $n=10.000, m=200, q=1.000$.
      • Kết quả đo lường: Thuật toán HAG vượt trội hơn APX về tỷ lệ tìm thấy phép ghép hoàn chỉnh, giảm thiểu đáng kể số lượng sinh viên chưa được ghép (sinh viên độc thân), đồng thời duy trì số bước lặp và thời gian thực thi trung bình thấp trên toàn bộ các dải tham số xác suất $p_1, p_2$.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và thuật toán

  1. Phát triển khung phân tích xung đột dựa trên UBP: Luận án đã xây dựng mô hình toán học sử dụng tập các cặp chặn trội nhất (Undominated Blocking Pairs) để thu hẹp không gian tìm kiếm lân cận từ bậc $O(n^3)$ xuống $O(n^2)$ cho mỗi bước lặp, chứng minh rằng việc loại bỏ UBP theo hàm mục tiêu $h(m_i)$ sẽ đồng thời triệt tiêu toàn bộ các cặp chặn liên đới do tác nhân đó tạo ra.
  2. Hệ thống 6 thuật toán heuristic mới:
    • Giải quyết MAX-SMTI: Thuật toán MCS (Max-Conflicts based heuristic search) và thuật toán HR (Heuristic Repair);
    • Giải quyết MAX-HRT: Thuật toán MCA (Min-Conflicts Algorithm) và thuật toán HS (Heuristic Search);
    • Giải quyết MAX-SPA: Thuật toán SPA-P-heuristic (cho MAX-SPA-P) và thuật toán HAG (cho MAX-SPA-ST).
  3. Chiến lược thoát cực tiểu cục bộ hiệu quả: Đề xuất cơ chế phá vỡ liên kết có định hướng dựa trên danh sách sở thích của tác nhân độc thân (Escape_Local_Minima), giúp thuật toán vượt qua bẫy tối ưu cục bộ mà không cần tái khởi động lại toàn bộ phép ghép từ đầu như các phương pháp truyền thống.

Đóng góp về mặt thực tiễn

  1. Cung cấp bộ công cụ thuật toán hiệu quả cao cho các hệ thống phân bổ tài nguyên thực tế có quy mô lớn: tuyển sinh đại học, phân bổ bác sĩ nội trú thực tập tại các bệnh viện, phân công đề tài tốt nghiệp cho sinh viên, và tối ưu định tuyến yêu cầu dịch vụ mạng viễn thông.
  2. Bộ chương trình nguồn và quy trình kiểm thử xây dựng trên MATLAB cung cấp một khung thực nghiệm chuẩn hóa cho việc sinh dữ liệu ngẫu nhiên có kiểm soát tham số ($n, m, q, p_1, p_2, c_j, d_k$) để phục vụ các nghiên cứu tiếp theo về tối ưu hóa tổ hợp.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của đề tài

  • Nghiên cứu tập trung vào bài toán ghép cặp ổn định tĩnh với thông tin sở thích đầy đủ tại thời điểm xét, chưa tích hợp các yếu tố sở thích động (dynamic preferences) hoặc thông tin bất định/mờ (fuzzy/uncertain preferences).
  • Thuật toán heuristic không cung cấp bảo đảm lý thuyết về cận dưới của kích thước phép ghép (approximation ratio) như các thuật toán xấp xỉ thuần túy, mà đánh giá tính hiệu quả thông qua thực nghiệm thống kê.
  • Việc thực nghiệm mới thực hiện trên môi trường đơn luồng (single-thread) của máy tính cá nhân, chưa khai thác kiến trúc tính toán song song (parallel computing/GPU).

Hướng nghiên cứu tiếp theo

  • Mở rộng các thuật toán heuristic đề xuất để giải quyết bài toán hôn nhân ổn định với các ràng buộc phức tạp hơn, chẳng hạn như bài toán có ràng buộc nhóm (matching with couples) hoặc ràng buộc chỉ tiêu dưới (quota lower bounds).
  • Nghiên cứu cơ chế song song hóa thuật toán tìm kiếm heuristic trên cấu trúc đa lõi hoặc GPU để giải quyết các bài toán có quy mô siêu lớn ($n > 100.000$).
  • Tích hợp các kỹ thuật học máy (machine learning) nhằm tự động tinh chỉnh các trọng số tham số trong hàm heuristic và xác suất lựa chọn ngẫu nhiên dựa trên đặc trưng cấu trúc của từng thể hiện dữ liệu đầu vào.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Công nghệ thông tin và Toán tin ứng dụng: Tham khảo phương pháp mô hình hóa bài toán tối ưu thỏa mãn ràng buộc (CSP), kỹ thuật thiết kế hàm heuristic và phương pháp chứng minh tính chất của các cặp chặn trội nhất.
  • Giảng viên và các nhà nghiên cứu về Tối ưu hóa tổ hợp / Trí tuệ nhân tạo: Sử dụng cấu trúc chương 2, 3, 4 để tham khảo phương pháp luận thực nghiệm so sánh thuật toán, quy trình sinh dữ liệu kiểm thử chuẩn (Gent's generator) và các kỹ thuật xử lý suy thoái cực tiểu cục bộ.
  • Kỹ sư phát triển phần mềm và nhà quản lý hệ thống giáo dục - y tế: Tham khảo các thuật toán cụ thể (HAG, SPA-P-heuristic, MCA) để cài đặt vào các phần mềm phân bổ thực tế như hệ thống xếp khóa luận tốt nghiệp, hệ thống ghép cặp tuyển dụng hoặc phân bổ tài nguyên hạ tầng.

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

1. Tại sao luận án lại chọn giải quyết bài toán tìm phép ghép ổn định yếu (weakly stable) thay vì ổn định mạnh hay siêu ổn định?

Theo chứng minh của Irving và Manlove, đối với các thể hiện có danh sách xếp hạng chứa quan hệ ngang hàng (ties), phép ghép siêu ổn định (super-stable) và ổn định mạnh (strongly stable) có thể không tồn tại. Ngược lại, phép ghép ổn định yếu luôn luôn tồn tại trên mọi thể hiện nhưng kích thước của các phép ghép ổn định yếu lại không bằng nhau. Do đó, bài toán tìm kiếm một phép ghép ổn định yếu có kích thước tối đa (MAX-SMTI, MAX-HRT, MAX-SPA) là bài toán có ý nghĩa thực tiễn cao nhất nhằm ghép nối được nhiều đối tượng nhất mà vẫn đảm bảo tính ổn định.

2. Thuật toán MCS vượt trội hơn thuật toán LTIU về thời gian thực hiện nhờ vào cơ chế nào?

Tại mỗi bước lặp, thuật toán LTIU cần tạo ra toàn bộ tập hợp các phép ghép lân cận bằng cách xóa từng cặp chặn trong tập cặp chặn trội nhất, sau đó tính toán chi phí của từng phép ghép lân cận để chọn ra trạng thái tốt nhất. Thao tác này đòi hỏi chi phí tính toán $O(n^3)$. Ngược lại, thuật toán MCS chỉ mất $O(n^2)$ để xác định tập cặp chặn trội nhất $X$ và sử dụng ngay hàm heuristic $h(m_i) = n \times ubp(w_j) - rank(w_j, m_i)$ để chọn duy nhất một cặp chặn có mức độ xung đột cao nhất nhằm loại bỏ. Nhờ vậy, MCS giảm đáng kể khối lượng tính toán và chạy nhanh hơn LTIU khoảng 90 lần trong các thử nghiệm thực tế.

3. Hàm Escape_Local_Minima trong thuật toán MCS hoạt động như thế nào để đưa thuật toán thoát khỏi điểm cực tiểu cục bộ?

Khi thuật toán đạt đến một phép ghép ổn định nhưng không hoàn chỉnh (bị kẹt tại cực tiểu cục bộ), hàm Escape_Local_Minima sẽ:

  • Lựa chọn ngẫu nhiên một tác nhân đang độc thân ($m_j$ hoặc $w_j$ với xác suất $p \le 0.5$).
  • Nếu chọn người nam độc thân $m_j$, hàm duyệt qua tất cả các người nữ $w_k$ nằm trong danh sách xếp hạng của $m_j$ và phá vỡ cặp ghép hiện tại của họ $(M(w_k), w_k)$ để tạo thành các cá nhân độc thân mới.
  • Cơ chế này tạo ra một trạng thái xuất phát mới có số lượng cặp chặn ít hơn nhiều so với việc khởi tạo lại ngẫu nhiên hoàn toàn, giúp thuật toán tiếp tục tìm kiếm phép ghép có kích thước lớn hơn một cách nhanh chóng.

4. Thuật toán HAG giải quyết bài toán MAX-SPA-ST đạt kết quả thực nghiệm như thế nào khi so sánh với thuật toán chuẩn APX?

Trong các thử nghiệm trên các tập dữ liệu ngẫu nhiên quy mô lớn (lên đến $n=10.000$ sinh viên, $m=200$ giảng viên, $q=1.000$ đề tài), thuật toán HAG luôn đạt tỷ lệ tìm thấy phép ghép hoàn chỉnh cao hơn thuật toán xấp xỉ APX của Cooper và Manlove, giảm thiểu đáng kể số lượng sinh viên không được phân bổ đề tài (sinh viên độc thân), đồng thời duy trì thời gian thực thi và số bước lặp trung bình ở mức thấp và ổn định.

Kết luận

Luận án đã giải quyết toàn diện bài toán tìm phép ghép ổn định có kích thước tối đa cho bài toán SMTI và hai bài toán mở rộng quan trọng là HRT và SPA thuộc lớp bài toán NP-khó. Bằng việc xây dựng không gian tìm kiếm dựa trên các cặp chặn trội nhất (UBP) và tích hợp các hàm heuristic định hướng xung đột, luận án đã đề xuất thành công 6 thuật toán mới (MCS, HR, MCA, HS, SPA-P-heuristic, HAG). Các kết quả thực nghiệm định lượng trên MATLAB với quy mô lên đến hàng nghìn tác nhân đã chứng minh tính hiệu quả vượt trội của các thuật toán đề xuất về cả thời gian thực hiện lẫn tỷ lệ tìm thấy phép ghép tối đa so với các thuật toán xấp xỉ và heuristic công bố trước đây. Công trình đóng góp nền tảng lý thuyết vững chắc và công cụ giải thuật thực tiễn cho các bài toán tối ưu hóa phân bổ nguồn lực trong xã hội, y tế và giáo dục.