Tối ưu đa mục tiêu Pareto

Khái niệm then chốt trong tối ưu hoá đa mục tiêu là phương án tối ưu Pareto.
Định nghĩa: X* là nghiệm cần tìm thì X* phải có các tính chất sau:

1. X* phải thuộc điểm các phương án khả thi của bài toán tức là thoả mãn các ràng buộc X* thuộc tập hợp D.
2. Mọi phương án khả thi khác X thuộc D mà có một mục tiêu nào đó tốt hơn ( fi(X)> = fi(X*) thì cũng phải có ít nhất một mục tiêu khác xấu hơn ( fj(X)<fj(X*)) với i khác j.

Nghiệm X* này còn được gọi là nghiệm hiệu quả. Trên tổng thể không có một X nào có thể trội hơn X*.
Từ tối ưu Pareto cho ra các nghiệm hiệu quả, bán hiệu quả và lý tưởng của bài toán. Vậy sự khác biệt của nghững nghiệm này là gì? Có thể nói khi tối ưu hoá đa mục tiêu thì tập tối ưu Pareto thu được là các giá trị thuộc miền xác định D của bài toán mà chúng toả mãn các điều kiện Pareto!
Ta thấy rằng nghiệm bán hiệu quả là các nghiệm mà thoả mãn: không tồn tại một nghiệm X nào khác thuộc tập xác đinh D mà với mọi i : fi(X)> fi(X*).
Nghiệm hiệu quả sẽ là các nghiệm thoả mãn: không tồn tại một nghiệm X nàothuộc tập xác đinh D mà có thể: với mọi i mà fi(X)>= fi(X*) và phải tồn tại một j mà fj(X)>fj(X*).
Để hiểu hơn Gió lấy ví dụ các điểm trên toạ độ De-cac hai chiều như sau(bạn nên vẽ ra để hiểu rõ hơn): nếu có 4 là a,b,c,d. Có toạ độ lần lượt x(a) = x(b) = x(c) = x(d) = 3 nhưng y(a) = 2, y(b) = 3, y(c) = 4, y(d) = 5. Vậy lúc này nghĩ xem đâu là nghiệm bán hiệu quả và hiệu quả ?? Xin trả lời như sau: Nghiệm hiệu quả ở đây sẽ là d. Bởi vì với d thì: f1(a)=f1(b)=f1(c)=f1(d)=2, nhưng không có một f2(a),f2(b) hoặc f2(c) nào có thể lớn hơn f2(d)! Nghiệm bán hiệu quả ở đây là: a,b,c,d. Nếu lúc này ta cho thêm một điểm e(4,4) thì lúc này nghiệm bán hiệu quả sẽ là: c,d,e và nghiệm hiệu quả là: d,e. Nếu  có thêm một điểm là e(2,4) thì nghiệm bán hiệu quả sẽ là: a,b,c,d và nghiệm hiệu quả là d. Nói đến đây Gió nghĩ chúng ta đã phân biệt được hai loại nghiệm này.

Vậy có thể kết luận:

1. Nghiệm hiệu quả cũng chính là nghiệm bán hiệu quả, và không có điều ngược lại! (cho nên nếu gọi tập nghiệm hiệu quả là A, tập nghiệm bán hiệu quả là B thì A<=B).
   
2. Nghiệm hiệu quả và bán hiệu quả luôn luôn tồn tại.

Nghiệm lý tưởng là một nghiệm hiệu quả nhưng nó thoả mãn yêu cầu: mọi X thuộc tập xác định D thì fi(X*)>=fi(X). Vậy trong ví dụ trên 4 điểm a,b,c,d thì nghiệm lý tưởng là d rồi. Nhưng không đánh đồng nghiệm lý tưởng với nghiệm hiệu quả. Nghiệm lý tưởng không phải bao giờ cũng tồn tại. Nếu lấy một ví duk như thế này: cũng trên không gian hai chiều  có 4 điểm a(1.3), b(2,2), c(3,1) thì 3 nghiệm này đều là nghiệm bán hiệu quả và nghiệm hiệu quả nhưng không có nghiệm lý tưởng nào!
Tiếp tục, các bài toán tối ưu trên hàm lồi mạnh (ví dụ parabol) thì nghiệm tối ưu tìm được luôn là nghiệm lý tưởng của bài toán, trên hàm lồi (một đường thẳng) thì nghiệm tìm được có thể là nghiệm hiệu quả thôi.
<<Trích http://hahong.wordpress.com/>>