Tối ưu đa mục tiêu Pareto (Not Pareto 80-20)

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.

10 thoughts on “Tối ưu đa mục tiêu Pareto (Not Pareto 80-20)

  1. Xin chào,

    Hiện giờ mình đang tìm hiểu việc tối ưu đa tiêu chí Pareto, bạn có thể vui lòng cho mình các bài viết chi tiết hơn hoặc địa chỉ website để tìm hiểu.

    Trân trọng cảm ơn!

  2. ồh, rất lấy làm vui khi có người hỏi Gió về vấn đề này. Nhưng quả thực khi viết bài này(cách đây nửa năm) chỉ với mục đích giúp các bạn trong lớp thi qua môn học: Lý thuyết nhận nghiện. Trong môn học này có chương nói về tối ưu hóa đa mục tiêu, mà sách tiếng Việt không có nên Gió đã đọc một số sách bằng tiếng anh trên mạng nhưng không nhớ nó nằm ở đâu nữa. Bạn cũng có thể google trên mạng như mình từng làm. Còn nữa là mình sẽ rất săn sằng để thảo luận với bạn về các vấn đề này.

  3. pareto Optimization! thử xem nha bạn.
    Thầy giáo Gió nói: cứ tìm kiếm, không thấy được cái bạn muốn, nhưng có thể thấy được cái bạn cần!

  4. Bài toán tối ưu đa mục tiêu: Tìm điểm Pareto của hàm đa mục tiêu:
    F(x)={3x+y+2,2y,x+y-2} với các ràng buộc: x+y=0; y>=0

    Ai chỉ dùm mình cách giải bài toán với.

  5. chao ban Gio,

    Minh vua moi hoc 1 chuong moi trong mo^n Linear Programming Modelling (lap trinh bang Xpress MP) ve de tai nay: Multi-objective optimisation with linear programming tools. Thuc ra chua bao gio minh lam quen voi toi uu da muc tieu ca. Neu ban ra`nh co the cho minh hoi chi tiet dc khong?

    Cam on ban.

    Than chao,

    VBT

    P.S: Email cua minh: bichthuan_vu@yahoo.com

  6. Chào bạn Gió. mình đang làm luận văn có liên quan đến bài toán tối ưu đa mục tiêu. bạn có tai liêu j liên quan đến nó ko cho mình vơi. cảm ơn gió nhiều

  7. Tài liệu liên quan thì giờ mình không có, vì vấn đề này đã quá lâu rồi, bạn thông cảm nhé. Có điều nếu có vấn đề gì bạn cứ đưa lên chúng ta cùng suy nghĩ tìm cách giải quyết. Đây là một vấn đề thú vị🙂

  8. mình đang tìm hiểu các phương pháp tối ưu Pareto, với các định nghĩa như “Desirable gambles”, “maximality rule”, ” interval dominance”, “interval bound dominance” mình chưa biết dịch như thế nào? Bạn Gió có thể gợi ý?

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s