Luận án thuật toán xấp xỉ bài toán tối ưu submodular ràng buộc chi phí - Học viện KH&CN

Nghiên cứu thuật toán xấp xỉ cho bài toán tối ưu submodular ràng buộc chi phí, phân tích các mô hình giải thuật song song và tối ưu hiệu quả.

• Tác giả: Nguyễn Thị Huệ
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu thuật toán xấp xỉ cho một số bài toán tối ưu submodular với ràng buộc chi phí
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2026
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về thuật toán xấp xỉ bài toán tối ưu submodular

Tối ưu hóa submodular đóng vai trò nền tảng trong lĩnh vực khoa học máy tính và toán học ứng dụng. Hàm submodular mô hình hóa nguyên lý lợi nhuận biên giảm dần trong kinh tế học và tự nhiên. Khi thêm một phần tử vào tập hợp nhỏ, giá trị gia tăng nhận được luôn lớn hơn hoặc bằng khi thêm vào tập hợp lớn hơn. Nhiều bài toán quan trọng thuộc lớp tối ưu hóa này, bao gồm chọn cảm biến, tóm tắt tài liệu và lan truyền ảnh hưởng mạng xã hội.

Tuy nhiên, phần lớn các bài toán tối ưu hóa submodular thuộc lớp bài toán NP-khó. Các phương pháp vét cạn hoặc tìm kiếm chính xác không thể thực thi khi kích thước dữ liệu tăng cao. Do đó, việc thiết kế thuật toán xấp xỉ là giải pháp tất yếu. Thuật toán xấp xỉ cung cấp lời giải có chất lượng được đảm bảo về mặt toán học trong thời gian đa thức.

Tại Học viện Khoa học và Công nghệ, luận án của nghiên cứu sinh Nguyễn Thị Huệ nghiên cứu chuyên sâu về các thuật toán xấp xỉ cho bài toán tối ưu submodular với ràng buộc chi phí. Công trình phân tích từ mô hình cơ bản đến mô hình hàm k-submodular mở rộng, tạo nền tảng lý thuyết vững chắc cho bài toán tối ưu tổ hợp hiện đại.

1.1. Khái niệm và tính chất của hàm submodular

Hàm submodular là hàm tập hợp có tính chất trực giác sâu sắc. Cho một tập hữu hạn V, hàm f gán mỗi tập con của V thành một số thực. Tính chất submodular thể hiện qua điều kiện: f(A hợp {e}) trừ f(A) luôn lớn hơn hoặc bằng f(B hợp {e}) trừ f(B), với mọi tập A là con của B.

Điều này mô tả chính xác hiệu ứng giảm biên. Giá trị tăng thêm của một phần tử giảm dần khi quy mô tập hợp tích lũy tăng lên. Khi hàm f đơn điệu, việc thêm phần tử không bao giờ làm giảm giá trị tổng thể.

Trong nhiều ngữ cảnh, hàm k-submodular mở rộng khái niệm này cho k tập con rời nhau. Mô hình mới cho phép biểu diễn các bài toán phân bổ nguồn lực phức tạp hơn.

1.2. Vai trò của thuật toán xấp xỉ trong tối ưu tổ hợp

Tối ưu tổ hợp thường dẫn đến những bài toán NP-khó điển hình. Không thuật toán chính xác nào có thể giải quyết các bài toán này trong thời gian đa thức, trừ khi P bằng NP. Khi không gian tìm kiếm bùng nổ theo hàm mũ, các kỹ thuật duyệt toàn bộ đều thất bại trên dữ liệu thực tế.

Thuật toán xấp xỉ giải quyết thách thức này bằng cách cân bằng giữa độ chính xác và thời gian tính toán. Thuật toán trả về một nghiệm khả thi với cam kết toán học cụ thể. Tỷ lệ xấp xỉ chứng minh nghiệm tìm được không bao giờ sai lệch quá một giới hạn định trước so với nghiệm tối ưu.

Phương pháp xấp xỉ tiêu chuẩn kép cung cấp sự linh hoạt vượt trội. Kỹ thuật này vừa kiểm soát chi phí, vừa bảo đảm mục tiêu.

II. Phân tích độ khó thuật toán xấp xỉ bài toán tối ưu submodular

Nghiên cứu tối ưu hóa submodular đối mặt với nhiều rào cản kỹ thuật nghiêm trọng. Hai nhóm bài toán kinh điển bao gồm tối đa hóa hàm submodular có ràng buộc và bài toán phủ submodular với chi phí tối thiểu (MCSC). Trong bài toán MCSC, mục tiêu là tìm tập con có tổng chi phí nhỏ nhất để hàm tiện ích đạt một ngưỡng định trước. Khi mở rộng sang hàm k-submodular, độ phức tạp của bài toán tăng lên theo cấp số nhân do sự xuất hiện đồng thời của k trạng thái độc lập.

Thách thức lớn nhất nằm ở tính khả thi khi xử lý dữ liệu quy mô đồ sộ. Các mạng xã hội hiện đại chứa hàng triệu nút và hàng tỷ cạnh kết nối. Thuật toán tham lam tuần tự truyền thống đòi hỏi số lượng vòng lặp rất lớn. Tại mỗi bước, thuật toán phải duyệt qua toàn bộ tập phần tử còn lại để tính độ lợi biên. Quá trình này dẫn đến độ trễ tính toán không thể chấp nhận được trên thực tế.

Bên cạnh đó, các mô hình cũ thường giả định chi phí đồng nhất hoặc bỏ qua tính công bằng giữa các nhóm đối tượng. Việc kết hợp ràng buộc chi phí công bằng làm cho không gian nghiệm bị thu hẹp. Các giải thuật cũ dễ vượt ngân sách.

2.1. Hạn chế của thuật toán tham lam tuần tự truyền thống

Thuật toán tham lam tuần tự là cách tiếp cận phổ biến nhất cho bài toán tối ưu submodular. Tại mỗi bước, thuật toán lựa chọn phần tử có tỷ số giữa độ lợi biên và chi phí cao nhất. Chiến lược này hoạt động tốt trên các tập dữ liệu nhỏ.

Tuy nhiên, thuật toán bộc lộ điểm yếu chí mạng khi kích thước đồ thị mở rộng. Bản chất tuần tự buộc thuật toán thực hiện hàng nghìn vòng lặp liên tiếp. Mỗi vòng lặp yêu cầu số lần truy vấn hàm mục tiêu tỷ lệ thuận với số nút trong mạng. Độ phức tạp truy vấn tăng vọt làm tê liệt các hệ thống tính toán đơn luồng. Hơn nữa, thuật toán tuần tự không thể khai thác kiến trúc đa luồng hiện đại.

2.2. Khó khăn từ ràng buộc chi phí và tính công bằng

Trong các ứng dụng thực tế, chi phí kích hoạt hoặc lựa chọn phần tử không bao giờ đồng nhất. Mỗi nút mạng có mức phí riêng biệt dựa trên tầm ảnh hưởng và vị trí địa lý. Ràng buộc ngân sách cố định đòi hỏi giải thuật phải tối ưu hóa nghiêm ngặt trên từng đồng chi phí.

Vấn đề trở nên phức tạp hơn khi bổ sung tiêu chí công bằng. Tiếp thị lan truyền hoặc phân bổ tài nguyên phải đảm bảo quyền lợi cân đối giữa các cộng đồng người dùng khác nhau. Thuật toán không được phép ưu tiên một nhóm dân cư và bỏ rơi các nhóm còn lại. Thêm ràng buộc chi phí công bằng làm phức tạp hóa không gian nghiệm của bài toán.

III. Giải pháp mới cho thuật toán xấp xỉ bài toán tối ưu submodular

Để vượt qua các rào cản tính toán, luận án tiến sĩ tại Học viện Khoa học và Công nghệ đề xuất hàng loạt thuật toán xấp xỉ đột phá. Đối với bài toán MCSC tổng quát với hàm tiện ích nhận giá trị thực, tác giả phát triển thuật toán song song AdaptMCSC. Đây là thuật toán xấp xỉ tiêu chuẩn kép đầu tiên giải quyết trọn vẹn bài toán này trong môi trường song song. AdaptMCSC đạt độ phức tạp song song ở mức thấp và giảm thiểu tối đa độ phức tạp truy vấn.

Đối với bài toán phủ k-submodular chi phí tối thiểu, luận án giới thiệu bộ ba thuật toán FBiUOpt, FBiU và FBi. Thuật toán FBi khai thác tính chất đơn điệu để tăng tốc độ hội tụ. Cơ chế lọc ngưỡng nhị phân giúp giải thuật loại bỏ các phần tử kém hiệu quả nhanh chóng.

Ngoài ra, công trình nghiên cứu xây dựng giải pháp tối ưu cho bài toán tối đa hàm submodular dưới ràng buộc chi phí công bằng. Thuật toán đề xuất xử lý thành công cả trường hợp chi phí đồng nhất lẫn tổng quát. Các chứng minh toán học khẳng định tỷ lệ xấp xỉ lý thuyết luôn được bảo đảm.

3.1. Thuật toán song song AdaptMCSC giải quyết bài toán phủ

Thuật toán AdaptMCSC là bước tiến đột phá trong nghiên cứu bài toán MCSC với hàm tiện ích nhận giá trị thực. Thuật toán áp dụng cơ chế ngưỡng tuần tự thích ứng kết hợp xử lý song song phân tán. Thay vì duyệt từng nút, AdaptMCSC bổ sung đồng thời các tập phần tử thỏa mãn ngưỡng hiệu quả biên vào lời giải.

Cấu trúc song song giúp thuật toán giảm thời gian thực thi đáng kể trên các cụm máy chủ hiệu năng cao. Độ phức tạp vòng lặp chỉ còn phụ thuộc logarit vào kích thước tập dữ liệu và sai số. Kết quả thực nghiệm chứng minh AdaptMCSC chạy nhanh hơn nhiều lần so với giải thuật tuần tự nhưng vẫn bảo đảm chi phí tối ưu.

3.2. Bộ thuật toán FBiUOpt và FBi cho hàm k submodular

Bài toán phủ k-submodular mở rộng phạm vi áp dụng khi phân chia các phần tử vào nhiều trạng thái hoạt động. Để giải quyết trường hợp chi phí tổng quát, luận án phát triển thuật toán FBiUOpt khi biết trước ước lượng tối ưu, và thuật toán FBiU cho trường hợp không biết trước nghiệm.

Đối với trường hợp hàm mục tiêu đơn điệu, thuật toán FBi mang lại bước nhảy vọt về tốc độ. Giải thuật sử dụng kỹ thuật tìm kiếm nhị phân thông minh để co hẹp khoảng giá trị ngưỡng. Thuật toán chỉ chọn các phần tử có đóng góp biên vượt trội. Cách tiếp cận này giảm thiểu số lần truy vấn hàm, duy trì tính ổn định trên các tập dữ liệu lớn.

IV. Ứng dụng thực tế thuật toán xấp xỉ bài toán tối ưu submodular

Các đóng góp lý thuyết trong luận án mở ra tiềm năng ứng dụng to lớn trong thời đại kinh tế số. Điển hình nhất là bài toán tối đa hóa ảnh hưởng (IM) và tối đa hóa doanh thu (RM) trên mạng xã hội trực tuyến. Doanh nghiệp cần xác định tập khách hàng hạt giống ban đầu với ngân sách hạn chế để kích hoạt làn sóng lan truyền rộng nhất. Nhờ mô hình hóa hành vi bão hòa bằng hàm submodular, các thuật toán mới giúp tối ưu hóa chi phí chiến dịch chuẩn xác.

Bên cạnh tiếp thị lan truyền, các thuật toán xấp xỉ đề xuất còn giải quyết hiệu quả bài toán đặt cảm biến quan trắc. Hệ thống giúp thu thập dữ liệu ô nhiễm toàn diện với số trạm tối thiểu. Trong lĩnh vực xử lý ngôn ngữ tự nhiên, thuật toán hỗ trợ tóm tắt văn bản từ kho tài liệu khổng lồ.

Công trình nghiên cứu tại Học viện Khoa học và Công nghệ khẳng định năng lực giải quyết các bài toán công nghệ mũi nhọn. Các giải thuật này có giá trị học thuật cao và sẵn sàng chuyển giao vào thực tế.

4.1. Tối đa hóa doanh thu và ảnh hưởng trên mạng xã hội

Mạng xã hội trực tuyến tạo ra môi trường tương tác vô cùng phức tạp. Bài toán tối đa doanh thu (RM) không chỉ đo lường số người tiếp nhận tin tức, mà còn phân tích đóng góp kinh tế cụ thể của từng cá nhân. Khách hàng thường xuất hiện hiện tượng bão hòa tiêu dùng khi đã tiếp xúc đủ thông điệp quảng cáo.

Hàm doanh thu phi tuyến submodular mô hình hóa trọn vẹn hiện tượng tâm lý này. Thuật toán đề xuất chọn lọc chính xác nhóm người dùng hạt giống nhằm sinh ra tổng doanh thu cao nhất. Hơn nữa, việc tích hợp ràng buộc chi phí công bằng giúp doanh nghiệp phân bổ ngân sách hài hòa, bảo đảm hiệu quả truyền thông.

4.2. Ý nghĩa khoa học và triển vọng phát triển tương lai

Luận án tiến sĩ tại Học viện Khoa học và Công nghệ đánh dấu đóng góp lý thuyết xuất sắc cho ngành khoa học máy tính nước nhà. Các thuật toán như AdaptMCSC hay FBi đã thu hẹp khoảng cách giữa lý thuyết tối ưu hóa tổ hợp và tính toán hiệu năng cao. Nghiên cứu mở ra hướng tiếp cận mới trong việc xử lý đồ thị quy mô lớn với chi phí thấp.

Trong tương lai, các mô hình này có thể mở rộng cho môi trường dữ liệu luồng động, nơi cấu trúc mạng thay đổi liên tục theo thời gian thực. Sự kết hợp giữa thuật toán xấp xỉ và trí tuệ nhân tạo sẽ tạo ra những đột phá mới trong tối ưu tự động.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 TỔNG QUAN VỀ CÁC BÀI TOÁN TỐI ƯU SUBMODULAR Chương này trình bày tổng quan về các bài toán Tối ưu tổ hợp (CO) và tối ưu submodular (SO), cùng với một số ứng dụng tiêu biểu như tóm tắt thông tin, tối đa hóa ảnh hưởng trên OSN và lựa chọn đặc trưng. Thông qua các ứng dụng này, chương làm rõ cách thức mô hình hóa các vấn đề thực tiễn dưới dạng các bài toán CO. Tiếp theo, chương giới thiệu các khái niệm nền tảng, các mô hình thuật toán cơ bản và tổng quan các nghiên cứu tiêu biểu đối với lớp bài toán SO. Đồng thời, các đặc điểm quan trọng của hàm submodular và những dạng ràng buộc thường gặp cũng được trình bày.

Cuối cùng, chương tổng hợp các khái niệm về độ phức tạp tính toán và các kỹ thuật thiết kế thuật toán hiện đại cho SO. Những cơ sở lý thuyết này tạo nền tảng cho việc mô hình hóa, phát triển và phân tích các thuật toán được nghiên cứu trong các chương tiếp theo. BÀI TOÁN TỐI ƯU TỔ HỢP Các bài toán CO bắt nguồn từ những nhu cầu thực tiễn của con người trong sản xuất và đời sống. Trong nhiều tình huống khác nhau của xã hội, con người thường phải lựa chọn trong số nhiều khả năng các phương án tối ưu nhất, dưới các ràng buộc và điều kiện cụ thể.

Nhu cầu này hiện diện rộng rãi trong nhiều lĩnh vực kinh tế – xã hội, bao gồm sản xuất, kinh doanh, quản lý, cũng như trong các quyết định thường nhật. Nhằm mô hình hóa và xử lý các vấn đề nêu trên, nhiều bài toán kinh điển trong CO đã được phát triển. Tiêu biểu có thể kể đến các bài toán như xác định tuyến vận chuyển tối ưu về chi phí, xây dựng kế hoạch và lịch làm việc trong tổ chức, cũng như phân công nhiệm vụ và phân bổ nguồn lực. Thậm chí, những tình huống quen thuộc trong đời sống, chẳng hạn việc tìm đường đi ngắn nhất từ nhà đến nơi làm việc, cũng có thể được biểu diễn dưới dạng các mô hình CO.

Nhờ khả năng mô tả linh hoạt các bài toán thực tiễn cùng tính khái quát cao, CO đã trở thành một lĩnh vực nền tảng trong khoa học máy tính. Một cách tổng quát, có thể định nghĩa bài toán CO cụ thể như sau Định nghĩa 1. Một bài toán CO được xác định bởi các thành phần sau. Input: - Một không gian nghiệm rời rạc hữu hạn Ω, bao gồm các lời giải hợp lệ của bài toán.

- Một hàm mục tiêu nhận giá trị thực không âm f : Ω → R+ , trong đó f (S) đo 10 lường chất lượng hoặc lợi ích của nghiệm S ∈ Ω. Output: - Một nghiệm O ∈ Ω sao cho f (O) đạt giá trị tối ưu (tối đa hóa hoặc tối thiểu). Bài toán cũng có thể được phát biểu dưới dạng max f (S) (hoặc min f (S)).1) S∈Ω S∈Ω Dưới đây là một số khái niệm quan trọng về bài toán CO: - Lời giải hợp lệ (feasible solution): Một tập con S ∈ Ω được gọi là một lời giải chấp nhận được. - Lời giải tối ưu (optimal solution): Một lời giải chấp nhận được O ∈ Ω được gọi là lời giải tối ưu nếu O ∈ arg maxS∈Ω f (S) (hoặc O ∈ arg minS∈Ω f (S)).

- Tập nền V : Trong nhiều bài toán CO, không gian nghiệm Ω thường được xác định là tập các lời giải hợp lệ được xây dựng từ một tập nền V. Cụ thể, mỗi nghiệm là một tập con của V , do đó ta có: Ω ⊆ 2V , trong đó 2V là tập lũy thừa của V , bao gồm tất cả các tập con của V .