Tối ưu hóa Đa mục tiêu (Multi-Objective Optimization)

Điểm khác biệt cốt lõi so với tối ưu hóa đơn mục tiêu là trong MOO, thường không tồn tại một giải pháp duy nhất được coi là “tốt nhất” cho tất cả các mục tiêu. Một giải pháp cải thiện một mục tiêu này có thể làm suy giảm một hoặc nhiều mục tiêu khác. Thay vào đó, mục tiêu của MOO là tìm ra một tập hợp các giải pháp được gọi là tập Pareto tối ưu (Pareto optimal set), trong đó mỗi giải pháp đại diện cho một sự đánh đổi (trade-off) khác nhau giữa các mục tiêu. Lựa chọn giải pháp cuối cùng từ tập hợp này sẽ phụ thuộc vào quyết định của người ra quyết định dựa trên các ưu tiên cụ thể.

2. Phát biểu bài toán tổng quát

Một bài toán tối ưu hóa đa mục tiêu có thể được phát biểu dưới dạng toán học như sau:

Tối thiểu hóa (hoặc Tối đa hóa) vector hàm mục tiêu:
$ \vec{f}(\vec{x}) = (f_1(\vec{x}), f_2(\vec{x}), …, f_m(\vec{x})) $

Thỏa mãn các ràng buộc:
$ \vec{x} \in \Omega $

Trong đó:

• $ \vec{x} = (x_1, x_2, …, x_n) $ là vector biến quyết định, thuộc về không gian quyết định (decision space).
• $ \Omega $ là tập hợp các giải pháp khả thi (feasible set), được xác định bởi các ràng buộc của bài toán (ví dụ: $g_j(\vec{x}) \le 0$, $h_k(\vec{x}) = 0$).
• $ f_i(\vec{x}) $ là hàm mục tiêu thứ $i$. Vector $ \vec{f}(\vec{x}) $ ánh xạ từ không gian quyết định sang không gian mục tiêu (objective space). Số lượng mục tiêu là $m$, với $ m \ge 2 $.

3. Các khái niệm cốt lõi trong Tối ưu hóa Đa mục tiêu

Sự khác biệt cơ bản nhất giữa tối ưu hóa đơn mục tiêu và đa mục tiêu nằm ở khái niệm “tối ưu”. Trong khi bài toán đơn mục tiêu thường tìm kiếm một giải pháp tối ưu toàn cục duy nhất, MOO lại dựa trên khái niệm về sự đánh đổi (trade-off) và sự thống trị (dominance). Điều này dẫn đến các định nghĩa cốt lõi sau đây, được đặt theo tên nhà kinh tế học Vilfredo Pareto.

• Ưu thế Pareto (Pareto Dominance): Giả sử chúng ta đang giải bài toán tối thiểu hóa. Một vector quyết định $ \vec{x}_a $ được gọi là thống trị Pareto (Pareto dominates) một vector quyết định $ \vec{x}_b $ (ký hiệu là $ \vec{x}_a \prec \vec{x}_b $) nếu và chỉ nếu:
  • $ f_i(\vec{x}_a) \le f_i(\vec{x}_b) $ với mọi mục tiêu $ i \in \{1, 2, …, m\} $. (Tức là $ \vec{x}_a $ không tệ hơn $ \vec{x}_b $ ở bất kỳ mục tiêu nào).
  • Tồn tại ít nhất một mục tiêu $ j \in \{1, 2, …, m\} $ sao cho $ f_j(\vec{x}_a) < f_j(\vec{x}_b) $. (Tức là $ \vec{x}_a $ tốt hơn một cách chặt chẽ so với $ \vec{x}_b $ ở ít nhất một mục tiêu).
• Giải pháp Pareto tối ưu (Pareto Optimal Solution): Một giải pháp $ \vec{x}^* \in \Omega $ được gọi là Pareto tối ưu nếu không tồn tại bất kỳ giải pháp nào khác $ \vec{x} \in \Omega $ mà $ \vec{x} \prec \vec{x}^* $. Nói cách khác, một giải pháp là Pareto tối ưu nếu không thể cải thiện bất kỳ mục tiêu nào mà không làm suy giảm ít nhất một mục tiêu khác. Các giải pháp này còn được gọi là giải pháp không bị thống trị (non-dominated solutions).
• Tập hợp Pareto tối ưu (Pareto Optimal Set): Là tập hợp tất cả các giải pháp Pareto tối ưu trong không gian quyết định. $ P_S = \{ \vec{x}^* \in \Omega \mid \nexists \vec{x} \in \Omega, \vec{x} \prec \vec{x}^* \} $.
• Mặt trận Pareto (Pareto Front): Là hình ảnh của Tập hợp Pareto tối ưu trong không gian mục tiêu. Nó biểu diễn tất cả các kết quả (các vector mục tiêu) tương ứng với các giải pháp Pareto tối ưu. $ P_F = \{ \vec{f}(\vec{x}^*) \mid \vec{x}^* \in P_S \} $.

4. Các phương pháp giải quyết bài toán MOO

Các phương pháp giải quyết bài toán MOO có thể được chia thành nhiều loại, tùy thuộc vào cách chúng xử lý các mục tiêu và thời điểm người ra quyết định đưa vào sở thích của mình. Dưới đây là một số phương pháp phổ biến:

• • Phương pháp Tổng có trọng số (Weighted Sum Method): Đây là một trong những phương pháp đơn giản nhất, chuyển đổi bài toán đa mục tiêu thành bài toán đơn mục tiêu bằng cách tính tổng các hàm mục tiêu với các trọng số do người dùng xác định:
    $ \min F(\vec{x}) = \sum_{i=1}^{m} w_i f_i(\vec{x}) $
    Trong đó $ w_i \ge 0 $ là trọng số thể hiện tầm quan trọng của mục tiêu thứ $i$, và $ \sum_{i=1}^{m} w_i = 1 $. Bằng cách thay đổi bộ trọng số $ (w_1, …, w_m) $, ta có thể tìm ra các điểm khác nhau trên Mặt trận Pareto.
    Ưu điểm: Dễ triển khai. Nhược điểm: Yêu cầu các hàm mục tiêu phải được chuẩn hóa về cùng một thang đo và không thể tìm thấy các giải pháp trong các vùng lõm (non-convex) của Mặt trận Pareto.
• Phương pháp Ràng buộc Epsilon ($\epsilon$-Constraint Method): Phương pháp này chọn một mục tiêu để tối ưu hóa và chuyển các mục tiêu còn lại thành các ràng buộc.
  $ \min f_j(\vec{x}) $
  Thỏa mãn: $ f_i(\vec{x}) \le \epsilon_i $ với mọi $ i \ne j $.
  Bằng cách thay đổi các giá trị ngưỡng $ \epsilon_i $, ta có thể khám phá các vùng khác nhau của Mặt trận Pareto.
  Ưu điểm: Có khả năng tìm ra các giải pháp ở vùng lõm của Mặt trận Pareto, điều mà phương pháp tổng trọng số không làm được. Nhược điểm: Việc lựa chọn các giá trị $\epsilon_i$ phù hợp có thể không tầm thường.
• Các thuật toán tiến hóa đa mục tiêu (Multi-Objective Evolutionary Algorithms – MOEAs): Đây là một lớp các thuật toán dựa trên quần thể, lấy cảm hứng từ quá trình tiến hóa tự nhiên. Các thuật toán tiêu biểu như NSGA-II (Non-dominated Sorting Genetic Algorithm II) và SPEA2 (Strength Pareto Evolutionary Algorithm 2) duy trì một quần thể các giải pháp và sử dụng các toán tử chọn lọc, lai ghép, đột biến để tiến hóa quần thể này hướng tới Mặt trận Pareto.
  Ưu điểm: Có khả năng tìm ra một tập hợp đa dạng các giải pháp trải rộng trên toàn bộ Mặt trận Pareto chỉ trong một lần chạy duy nhất. Chúng rất hiệu quả cho các bài toán phức tạp, “hộp đen” (black-box), nơi đạo hàm không tồn tại hoặc khó tính toán.
  Nhược điểm: Cần nhiều lần đánh giá hàm mục tiêu, có thể tốn kém về mặt tính toán và không đảm bảo tìm thấy Mặt trận Pareto tối ưu thực sự.
• Phương pháp Lập trình Mục tiêu (Goal Programming): Thay vì tối ưu hóa, phương pháp này cố gắng tìm một giải pháp thỏa mãn một tập hợp các mục tiêu (goals) do người ra quyết định đặt trước. Bài toán trở thành việc tối thiểu hóa độ lệch (deviation) so với các mục tiêu này.

5. Ứng dụng thực tiễn

Tối ưu hóa đa mục tiêu là một công cụ cực kỳ mạnh mẽ với phạm vi ứng dụng rộng lớn trong hầu hết các lĩnh vực khoa học và kỹ thuật, nơi các quyết định phức tạp đòi hỏi sự cân bằng giữa nhiều yếu tố.

• Kỹ thuật và Sản xuất: Đây là lĩnh vực ứng dụng phổ biến nhất của MOO. Ví dụ bao gồm: thiết kế cánh máy bay để đồng thời tối đa hóa lực nâng và tối thiểu hóa lực cản; tối ưu hóa cấu trúc của một cây cầu để tối thiểu hóa trọng lượng vật liệu (chi phí) và tối đa hóa khả năng chịu tải; hoặc tìm ra các thông số vận hành cho một quy trình hóa học để tối đa hóa sản lượng và tối thiểu hóa năng lượng tiêu thụ.
• Tài chính và Kinh tế: Trong quản lý danh mục đầu tư, các nhà đầu tư muốn tối đa hóa lợi nhuận kỳ vọng trong khi tối thiểu hóa rủi ro. MOO giúp tạo ra một “mặt trận hiệu quả” (efficient frontier), nơi mỗi điểm đại diện cho một danh mục đầu tư với sự đánh đổi tối ưu giữa rủi ro và lợi nhuận.
• Khoa học Môi trường: Quản lý tài nguyên nước trong một lưu vực sông có thể được mô hình hóa như một bài toán MOO, với các mục tiêu như tối đa hóa nguồn nước cho nông nghiệp, tối đa hóa sản lượng thủy điện và tối thiểu hóa tác động tiêu cực đến hệ sinh thái.
• Y học: Trong lập kế hoạch xạ trị, các bác sĩ muốn tối đa hóa liều lượng bức xạ đến khối u trong khi tối thiểu hóa liều lượng đến các mô lành xung quanh. MOO giúp tìm ra các kế hoạch điều trị cân bằng được hai mục tiêu mâu thuẫn này.
• Học máy và Trí tuệ nhân tạo: MOO được sử dụng để tối ưu hóa các siêu tham số của mô hình, nhằm cân bằng giữa độ chính xác của mô hình và độ phức tạp của nó (để tránh overfitting). Trong tìm kiếm kiến trúc mạng nơ-ron (Neural Architecture Search – NAS), người ta dùng MOO để tìm các kiến trúc vừa có độ chính xác cao, vừa có độ trễ thấp và kích thước mô hình nhỏ.

6. Đánh giá hiệu suất các thuật toán MOO

Vì một thuật toán MOO trả về một tập hợp các giải pháp (Mặt trận Pareto xấp xỉ) thay vì một giá trị duy nhất, việc đánh giá hiệu suất của nó phức tạp hơn. Các độ đo hiệu suất (performance metrics) thường được thiết kế để đánh giá hai khía cạnh chính: (1) Sự hội tụ (Convergence): Tập hợp giải pháp tìm được gần với Mặt trận Pareto thực sự đến mức nào? và (2) Sự đa dạng (Diversity): Các giải pháp tìm được có phân bố đều và bao phủ toàn bộ Mặt trận Pareto hay không?

Một số độ đo phổ biến bao gồm:

• Hypervolume (HV): Đây là một trong những độ đo được sử dụng rộng rãi nhất vì nó có thể đánh giá cả sự hội tụ và đa dạng mà không cần biết Mặt trận Pareto thực sự. Nó tính toán “thể tích” (hoặc diện tích trong không gian 2D) của không gian mục tiêu bị thống trị bởi tập giải pháp tìm được, so với một điểm tham chiếu. Giá trị HV càng lớn, tập hợp giải pháp càng tốt.
• Generational Distance (GD): Đo khoảng cách trung bình từ mỗi giải pháp trong tập tìm được đến giải pháp gần nhất trong Mặt trận Pareto thực sự ($P^*$). Một giá trị GD bằng 0 cho thấy tất cả các giải pháp tìm được đều nằm trên $P^*$. Nó chủ yếu đo lường sự hội tụ.
  $ GD(A, P^*) = \frac{\sqrt{\sum_{v \in A} \min_{p \in P^*} d(v, p)^2}}{|A|} $
  Trong đó $d(v,p)$ là khoảng cách Euclide giữa giải pháp $v$ trong tập tìm được $A$ và giải pháp $p$ trong tập thực sự $P^*$.
• Inverted Generational Distance (IGD): Tương tự như GD, nhưng đo khoảng cách trung bình từ mỗi điểm trong Mặt trận Pareto thực sự ($P^*$) đến giải pháp gần nhất trong tập tìm được ($A$). Một giá trị IGD thấp cho thấy tập hợp giải pháp tìm được vừa hội tụ tốt vừa có độ phủ tốt trên toàn bộ $P^*$. Nó đo lường cả sự hội tụ và đa dạng.
• Spacing (SP): Đo độ đồng đều trong phân bố của các giải pháp dọc theo Mặt trận Pareto tìm được. Giá trị Spacing thấp cho thấy các giải pháp được phân bố đều hơn.

Lưu ý quan trọng: Các độ đo như GD và IGD đòi hỏi phải biết trước Mặt trận Pareto thực sự ($P^*$), điều này chỉ khả thi đối với các bài toán thử nghiệm (benchmark problems). Đối với các bài toán thực tế, HV là một lựa chọn mạnh mẽ hơn.

7. Lựa chọn giải pháp cuối cùng (Decision Making)

Sau khi thuật toán MOO trả về một tập hợp các giải pháp Pareto tối ưu, bước cuối cùng là lựa chọn một giải pháp duy nhất để triển khai. Quá trình này được gọi là ra quyết định đa tiêu chí (Multi-Criteria Decision Making – MCDM) và phụ thuộc vào sở thích của người ra quyết định.

• Phương pháp Trực quan hóa: Hiển thị Mặt trận Pareto (dưới dạng biểu đồ phân tán cho 2 hoặc 3 mục tiêu) để người ra quyết định có thể thấy rõ sự đánh đổi và chọn một điểm mà họ cho là phù hợp nhất.
• Sử dụng Điểm tham chiếu: Người ra quyết định có thể xác định một “điểm lý tưởng” (utopia point – điểm có giá trị tốt nhất cho tất cả các mục tiêu, thường không khả thi) hoặc một điểm tham chiếu mong muốn. Sau đó, giải pháp được chọn là giải pháp trên Mặt trận Pareto có khoảng cách Euclide nhỏ nhất đến điểm này.
• Phương pháp Tương tác: Người ra quyết định tương tác với thuật toán trong quá trình tìm kiếm. Họ có thể cung cấp các sở thích (ví dụ: “Tôi quan tâm nhiều hơn đến việc giảm chi phí”) để hướng thuật toán tập trung vào các vùng cụ thể của Mặt trận Pareto.