Tối ưu hóa đa mục tiêu là gì? Nghiên cứu khoa học liên quan

Định nghĩa và phạm vi

Tối ưu hóa đa mục tiêu (Multi-Objective Optimization, MOO) là quá trình tìm kiếm tập hợp các giải pháp tốt nhất đồng thời theo nhiều hàm mục tiêu có thể mâu thuẫn, không thể gộp thành một tiêu chí duy nhất. Mỗi giải pháp trong tập Pareto đại diện cho một thỏa hiệp giữa các mục tiêu và không thể cải thiện mục tiêu này mà không làm suy giảm mục tiêu khác.

Không gian quyết định $X$ bao gồm tất cả các biến số đầu vào hợp lệ, thường bị ràng buộc bởi hệ bất đẳng thức và đẳng thức. Không gian mục tiêu là tập hợp các vector $F(x) = (f_1(x), f_2(x), \dots, f_k(x))$ mà ta cần tối ưu hóa đồng thời.

• Ứng dụng kỹ thuật: thiết kế cơ khí, tối ưu kết cấu cầu, cân bằng độ bền và chi phí.
• Ứng dụng kinh tế: tối ưu lợi nhuận và rủi ro trong đầu tư tài chính.
• Ứng dụng logistics: tối ưu chi phí vận chuyển và thời gian giao hàng.

Giải thích chi tiết về MOO có thể tham khảo tài liệu giảng dạy của MIT OpenCourseWare ở đây, cung cấp cơ sở lý thuyết và ví dụ minh hoạ.

Lịch sử và phát triển

Nguồn gốc MOO bắt đầu từ công trình của Charnes và Cooper (1961) với bài toán lập trình tuyến tính nhiều mục tiêu. Họ đề xuất cách xây dựng hàm mục tiêu tổng hợp bằng trọng số, mở đường cho các phương pháp scalarization.

Những năm 1960–1970, Kuhn–Tucker và các nhà toán học tiếp tục phát triển lý thuyết tối ưu lồi đa mục tiêu, định nghĩa điều kiện bão hòa và biện luận tối ưu cục bộ. Góc nhìn lý thuyết giúp xác định tính khả thi và tính lồi của miền Pareto.

• 1961: Charnes & Cooper – Linear Programming đa mục tiêu.
• 1963: Kuhn–Tucker – Điều kiện tối ưu lồi.
• 1970s: Phương pháp ε-constraint, phương pháp điểm tham chiếu.

Cách mạng thực sự xảy ra với thuật toán tiến hóa NSGA-II của Deb và cộng sự (2002), cung cấp khả năng tìm và duy trì đa dạng giải pháp Pareto trong một quần thể với độ phức tạp tính toán hợp lý Deb et al., 2002.

Hình thức bài toán

Bài toán MOO điển hình được biểu diễn dưới dạng:

$\min_{x\in X} F(x) = \bigl(f_1(x), f_2(x), \dots, f_k(x)\bigr)$

Trong đó, $X = \{x\in\mathbb{R}^n: g_j(x)\le0\ (j=1,\dots,m),\ h_\ell(x)=0\ (\ell=1,\dots,p)\}$ xác định miền khả thi. Các hàm mục tiêu $f_i(x)$ có thể tuyến tính hoặc phi tuyến, lồi hoặc không lồi.

Để giải quyết bài toán phi tuyến đa mục tiêu, thường phải chuyển bài toán sang dạng xấp xỉ hoặc phân mảnh thành nhiều bài toán con scalarization:

1. Trọng số tuyến tính: $\min \sum_{i=1}^k w_i f_i(x),\quad w_i\ge0,\;\sum w_i=1$
2. Phương pháp ε-constraint: $\min f_p(x)\ \text{với}\ f_i(x)\le\varepsilon_i,\ i\ne p \end{script> </li> </ol> <table> <thead> <tr> <th>Phương pháp</th> <th>Nguyên lý</th> <th>Ưu/Nhược</th> </tr> </thead> <tbody> <tr> <td>Trọng số tuyến tính</td> <td>Tổng có trọng số các hàm mục tiêu</td> <td>Đơn giản; khó áp dụng khi không lồi</td> </tr> <tr> <td>ε-constraint</td> <td>Ràng buộc mục tiêu phụ</td> <td>Bao phủ Pareto tốt; khó chọn ε phù hợp</td> </tr> </tbody> </table> <h2>Khái niệm Pareto</h2> <p>Giải pháp <script type="math/tex">x^*$ được gọi là Pareto tối ưu nếu không tồn tại $x\in X$ sao cho $f_i(x)\le f_i(x^*)$ với ít nhất một bất đẳng thức nghiêm ngặt. Khi đó, ta nói $x^*$ không bị chặn (non-dominated).

   Tập Pareto ($\mathcal{P}$) là tập hợp tất cả các giải pháp không bị chặn, biểu diễn ranh giới biện hộ giữa các mục tiêu. Đồ thị phân tán các điểm $F(x)$ trên mặt cắt 2D hoặc 3D thường minh hoạ biên Pareto.

   • Non-dominated: không ai tốt hơn về tất cả mục tiêu.
   • Dominated: tồn tại giải pháp khác tốt hơn hoặc ngang bằng mọi mục tiêu và tốt hơn ít nhất một.

   Thuộc tính	Mô tả
   Non-dominated	Giải pháp Pareto tối ưu, không bị chặn
   Dominated	Giải pháp kém hơn ít nhất một mục tiêu

   Thuật toán tiến hóa đa mục tiêu

   Thuật toán tiến hóa đa mục tiêu (MOEA) sử dụng cơ chế chọn lọc, lai ghép và đột biến lấy cảm hứng từ sinh học để tìm khoảng giá trị Pareto. Quần thể các cá thể đại diện cho các giải pháp được cập nhật qua nhiều thế hệ, đồng thời duy trì đa dạng và tiến gần biên Pareto.

   NSGA-II (Non-dominated Sorting Genetic Algorithm II) là thuật toán phổ biến, sử dụng phân loại non-dominated để xác định front ưu việt, kết hợp khoảng cách đám đông (crowding distance) để ưu tiên cá thể giúp giữ độ đa dạng. Việc sắp xếp non-dominated có độ phức tạp tính toán $O(MN^2)$, với $M$ số mục tiêu và $N$ kích thước quần thể.

   • SPEA2 (Strength Pareto Evolutionary Algorithm 2) xây dựng archive lưu trữ các cá thể tốt nhất qua các thế hệ, tính fitness dựa trên số cá thể mà chúng thống trị.
   • MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) chia bài toán MOO thành nhiều bài toán con bằng scalarization, giải song song và chia sẻ thông tin giữa các bài toán con.
   • Bi-objective algorithms như PESA-II hay IBEA cải thiện khả năng phân phối dọc biên Pareto và cân bằng giữa khai thác (exploitation) và thăm dò (exploration).

   Các thuật toán này có thể mở rộng cho số mục tiêu lớn (many-objective optimization) bằng cách sử dụng hình chiếu hoặc ánh xạ hạ chiều để tránh sự mất phương hướng trong quần thể.

   Chỉ số đánh giá hiệu năng

   Đánh giá chất lượng của MOEA đòi hỏi nhiều chỉ số khác nhau phản ánh gần đúng biên Pareto thực và độ đa dạng giải pháp.

   • Generational Distance (GD): đo khoảng cách trung bình từ các điểm thu được đến biên Pareto thật.
   • Inverted Generational Distance (IGD): kết hợp hàm khoảng cách đến và từ biên thật để đánh giá toàn diện hơn.
   • Spread (Δ): đo độ phân tán của các điểm trên tập Pareto so với các cực trị, phản ánh độ đa dạng.

   Chỉ số	Công thức/Đặc điểm	Ý nghĩa
   GD	$\sqrt{\frac{1}{|P|}\sum_{x\in P} d(x,P^*)^2}$	Nhỏ hơn tốt hơn, phản ánh độ chính xác
   IGD	$\frac{1}{|P^*|}\sum_{y\in P^*} d(y,P)$	Giá trị thấp cho thấy bao phủ tốt
   Spread (Δ)	$\frac{\sum |d_i-\bar d|}{\sum d_i + \bar d}$	Giá trị gần 0 cho độ đa dạng cao

   Các chỉ số phi-đối xứng và hypervolume (HV) cũng được sử dụng, trong đó HV đo thể tích không gian mục tiêu bị chiếm bởi tập Pareto và ưu tiên tập bao phủ lớn hơn.

   Ứng dụng thực tiễn

   Trong thiết kế cơ khí, MOO giúp tối ưu hóa hình học chi tiết để cân bằng giữa độ bền kết cấu và khối lượng, giảm tiêu hao vật liệu trong khi đảm bảo an toàn. Ví dụ: tối ưu cánh máy bay cần đồng thời giảm lực cản và tăng lực nâng.

   Chuỗi cung ứng và logistics áp dụng MOO để cân bằng chi phí vận chuyển, thời gian giao hàng và mức độ dịch vụ. Thuật toán MOEA phân tích mạng lưới vận tải, chọn lộ trình tối ưu theo nhiều tiêu chí như chi phí, độ tin cậy và tác động môi trường.

   • Quản lý năng lượng: tối ưu công suất phát, tổn thất điện áp và phát thải khí nhà kính trong hệ lưới phân tán (Sci. Direct (2015)).
   • Tài chính: tối ưu danh mục đầu tư cân bằng giữa lợi suất kỳ vọng và rủi ro biến động giá.
   • Sinh học tính toán: khám phá thuốc mới bằng tối ưu hóa đa mục tiêu hoạt tính và độ hòa tan của phân tử.

   Ứng dụng mới nổi bao gồm thiết kế vật liệu mới với đa mục tiêu về độ bền, dẫn điện và chi phí sản xuất, sử dụng mô hình phân tử kết hợp MOEA.

   Thách thức và xu hướng tương lai

   Với số mục tiêu tăng lên, các thuật toán tiến hóa đa mục tiêu truyền thống gặp khó khăn trong việc duy trì hiệu quả, dẫn đến sự kém đa dạng và chồng lấn quần thể. Nhiều nghiên cứu tập trung vào chiến lược phân mảnh và loại bỏ định hướng kém nổi bật (reference-based methods).

   Học máy và mô hình surrogate (ví dụ Gaussian Process, Random Forest) được tích hợp vào quá trình tối ưu hóa để giảm chi phí đánh giá hàm mục tiêu, đặc biệt hữu ích trong các bài toán cần tính toán mô phỏng phức tạp.

   1. Bayesian Optimization đa mục tiêu: sử dụng acquisition functions để chọn điểm đánh giá hiệu quả.
   2. Deep Reinforcement Learning tích hợp với MOEA: học chiến lược thăm dò tự động.
   3. Tối ưu thời gian thực: ứng dụng trong điều khiển tự động và hệ thống IoT cần phản hồi nhanh.

   Hệ thống phân tán và tính toán đám mây giúp mở rộng quy mô tính toán MOEA, cho phép xử lý quần thể lớn và số mục tiêu cao thông qua kiến trúc micro-services.

   Tài liệu tham khảo

   1. Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Trans. Evol. Comput. 2002, 6(2), 182–197. https://doi.org/10.1109/4235.7085742
   2. Zitzler, E.; Thiele, L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans. Evol. Comput. 1999, 3(4), 257–271. https://doi.org/10.1109/4235.797969
   3. Miettinen, K. Nonlinear Multiobjective Optimization. Springer, 1999. https://doi.org/10.1007/978-1-4612-0564-4
   4. Coello Coello, C. A.; Lamont, G. B.; Van Veldhuizen, D. A. Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, 2007. https://doi.org/10.1007/978-0-387-36797-2
   5. Marler, R. T.; Arora, J. S. Survey of Multi-Objective Optimization Methods for Engineering. Struct. Multidisc. Optim. 2004, 26, 369–395. https://doi.org/10.1007/s00158-003-0368-6
   6. Knowles, J. D.; Corne, D. W. Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evol. Comput. 2000, 8(2), 149–172. https://doi.org/10.1162/106365600568202
   7. Fonseca, C. M.; Fleming, P. J. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. Proc. 5th European Conference on Artificial Life, 1999.