Bài giảng Tính toán tiến hóa - Bài 9: Multi-objective Optimization

MULTI-OBJECTIVE OPTIMIZATION

PGS.TS Huỳnh Thị Thanh Bình

Email: [email protected]

Nội dung

2

 TỐI ƯU ĐA MỤC TIÊU

 Bài toán đa mục tiêu

 Hướng tiếp cận 1: Quy về đơn mục tiêu

 Hướng tiếp cận 2: Pareto optimal

 A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON

DECOMPOSITION

 Một số khái niệm

 Cấu trúc thuật toán

 Đánh giá

TỐI ƯU ĐA MỤC TIÊU

Bài toá n đa mục tiêu

4

Bài toán tối ưu đa mục tiêu (Multi-objective optimization

problem):

 Bài toán yêu cầu tối ưu 2 hay nhiều hàm mục tiêu cùng lúc.

 Mô hình hóa:

minimize 푓 푥 = 푓 푥 , 푓 푥 , … , 푓 푥

1

2

푘

s. t. 푥 ∈ 푋

 (Giả sử các mục tiêu đều là cực tiểu hóa)

 푋 là tập nghiệm chấp nhận được của bài toán

 푘 hàm mục tiêu khác nhau: 푓 푥 : 푋 ⟼ ℝ

푖

Bài toá n đa mục tiêu

5

 Ví dụ:

 Xây dựng hệ thống mạng:

◼ Tối đa phạm vi phủ sóng

◼ Tối thiểu chi phí triển khai

 Lập kế hoạch đầu tư:

◼ Tối đa lợi nhuận

◼ Tối thiểu rủi ro…

 Trong bài toán tối ưu đa mục tiêu, các hàm mục tiêu

thường xung đột lẫn nhau, do đó hiếm có một lời giải tối

ưu với tất cả mục tiêu cùng lúc.

Bài toá n đa mục tiêu

6

Hướng tiếp cận giải bài toán đa mục tiêu:

 Quy về đơn mục tiêu: Đưa ra công thức ánh xạ nhiều

mục tiêu về 1 mục tiêu, rồi giải như bài toán đơn mục

tiêu.

 Pareto optimal: Dựa trên khái niệm tính trội và biên

Pareto, tìm ra một số lời giải tốt với các hàm mục tiêu

khác nhau, để một decision maker (ở đây có thể là con

người) tự lựa chọn lời giải thích hợp nhất.

Hướng tiếp cận 1: Quy về đơn mục tiêu

7

Một số phương pháp quy về đơn mục tiêu:

 Vector trọng số

 Tchebycheff

 Penalty-based boundary intersection (PBI) (không giới

thiệu)

Hướng tiếp cận 1: Quy về đơn mục tiêu

8

Vector trọng số

 Quy 푑 mục tiêu về 1 mục tiêu

 Định nghĩa vector trọng số 휆 = (휆₁, 휆₂, … , 휆_푑), sao cho

σ^푑_푖=1

휆_푖= 1

 Trọng số 1 mục tiêu càng lớn thì mục tiêu đó càng được ưu tiên

 Mục tiêu mới:

푑

푔^푤푠푋 휆 = ෍ 휆_푖푓_푗(푋)

푖=1

 Ví dụ: Hai mục tiêu: 푓 = 푓 , 푓 ⇒ 푓^′= 0.3 × 푓 + 0.7 × 푓

1 2

1

2

Hướng tiếp cận 1: Quy về đơn mục tiêu

9

 Vector trọng số 휆 = (휆₁, 휆₂, … , 휆_푑)

 Điểm tham chiếu 푍^∗= (푍₁^∗, 푍₂^∗, … , 푍_푑^∗)

 Biên tốt nhất tìm được theo từng mục

tiêu

 Giả sử các mục tiêu đều là minimize,

với mọi lời giải 푋 tìm được:

푍^∗= min{푓 (푋)}

푖

 Mục tiêu mới: Cực tiểu hóa:

푔^푡푒푋 휆, 푍^∗= max {휆_푖(푓_푖푋 − 푍_푖^∗)}

1≤푖≤푑

Hướng tiếp cận 2: Pareto optimal

10

Tính trội (Pareto dominance):

 Phương pháp so sánh 2 lời giải trong bài toán đa mục tiêu.

 Lời giải 푥₁được gọi là trội hơn 푥₂nếu:

 푥₁không tệ hơn 푥₂ở mọi mục tiêu tương ứng

 푥₁tốt hơn 푥₂ở ít nhất 1 mục tiêu

 Ví dụ trong bài toán cực tiểu hóa:

∀푖, 푓 (푥 ) ≤ 푓 (푥 )

푖 1

푖 2

푥₁푑표푚푖푛푎푡푒 푥₂⟺ ൝

∃푗, 푓 푥 < 푓 (푥 )

푗 1

푗 2

Hướng tiếp cận 2: Pareto optimal

11

Biên Pareto (Pareto front):

 Một tập lời giải của bài toán đa mục tiêu trong đó không lời

giải nào trội hơn (dominate) lời giải nào

 Minh họa biên Pareto trong bài toán cực tiểu hóa 2 mục tiêu:

Hướng tiếp cận 2: Pareto optimal

12

 Các thuật toán áp dụng khái niệm Pareto optimal sẽ tập trung

tìm kiếm biên Pareto tối ưu hoặc gần tối ưu cho bài toán

 Một số thuật toán tiến hóa điển hình:

 Non-dominated Sorting Genetic Algorithm II (NSGA-II)

 Strength Pareto Evolutionary Algorithm 2 (SPEA2)

 A Multi-objective Evolutionary Algorithm Based on

Decomposition (MOEA/D)

A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON

DECOMPOSITION (MOEA/D)

Một số khá i niệm

14

 Phân hoạch

 Hàng xóm

 A multi-objective evolutionary algorithm based on

decomposition

Một số khá i niệm

15

Phân hoạch (Decomposition):

 Nhắc lại: Phương pháp vector trọng số → Quy bài toán đa mục

tiêu về đơn mục tiêu

 Cho 푁 vector 휆 khác nhau: 1 bài toán đa mục tiêu → 푁 bài

toán đơn mục tiêu khác nhau → 푁 lời giải tối ưu khác nhau

 Phân hoạch: Phương pháp quy bài toán đa mục tiêu thành 푁

bài toán đơn mục tiêu khác nhau, kết hợp giải 푁 bài toán con

này để được tập lời giải tạo thành biên Pareto của bài toán gốc

Một số khá i niệm

16

Phân hoạch (Decomposition):

 Ví dụ phân hoạch bài toán 2 mục tiêu:

Bài toán gốc:

푓 = (푓 , 푓 )

1 2

Bài toán con 2:

Bài toán con 1:

Bài toán con 9:

…

푔^푤푠= 0.2 × 푓 + 0.8 × 푓

푔^푤푠= 0.1 × 푓 + 0.9 × 푓

푔^푤푠= 0.9 × 푓 + 0.1 × 푓

1

2

1

2

1

2

1

9

Một số khá i niệm

17

Hàng xóm:

 Trong phân hoạch ở trên, một số bài toán con có hàm mục tiêu

(hay vector 휆) gần nhau hơn các bài toán khác

 Ví dụ: Bài toán gốc có 2 mục tiêu, bài toán con đang xét có 휆₁=

(0.3, 0.7). Có 2 bài toán con khác: 휆₂= (0.4, 0.6) và 휆₃=

(0.7, 0.3). Dễ thấy bài toán 휆₁gần với 휆₂hơn.

 Định nghĩa: “Hàng xóm” của 1 bài toán con là 푇 bài toán con

gần với nó nhất trong 푁 bài toán con (bao gồm chính nó)

 푇 là hằng số cho trước (1 ≤ 푇 ≤ 푁)

 Khoảng cách 2 bài toán con là khoảng cách Euclid giữa 2 vector

trọng số tương ứng

 Ký hiệu: Hàng xóm của bài toán con 푖: 퐵^푖= {푏₁, 푏₂, … , 푏_푇}

Một số khá i niệm

18

Hàng xóm:

 Ví dụ xây dựng tập hàng xóm cho bài toán con 2:

 푇 = 3: Mỗi bài toán con có 3 hàng xóm

 3 bài toán con gần nhất là 1, 2, 3 (bao gồm chính nó)

 Hàng xóm của 2: 퐵²= {1, 2, 3}

Hàng xóm?

Bài toán con 1:

Bài toán con 2:

Bài toán con 3:

푔^푤푠= 0.1 × 푓 + 0.9 × 푓

푔^푤푠= 0.2 × 푓 + 0.8 × 푓

푔^푤푠= 0.3 × 푓 + 0.7 × 푓

1

2

1

2

1

2

1

2

3

Một số khá i niệm

19

A multi-objective evolutionary algorithm based on decomposition

(MOEA/D)

 Giải thuật tiến hóa đa mục tiêu dựa trên phân hoạch

 Ý tưởng:

 Phân hoạch bài toán đa mục tiêu thành 푁 bài toán đơn mục tiêu con

푃¹, … , 푃^푁

◼ Tạo 푁 vector trọng số khác nhau

 Duy trì 1 lời giải tốt nhất cho từng bài toán con

 Tối ưu lời giải bài toán con bằng cách kết hợp lời giải của các “hàng

xóm” (các bài toán gần nhau thì thường có lời giải tốt gần nhau)

 Đánh giá lời giải:

 1 trong các phương pháp quy về đơn mục tiêu đã nêu

 Trong slide này dùng phương pháp Tchebycheff

Cấu trúc thuật toá n

20

Thuật toán MOEA/D gồm 3 bước chính:

 Bước 1: Khởi tạo

 Bước 2: Tiến hóa theo thế hệ

 Lặp lại nhiều lần tới khi thỏa mãn điều kiện dừng

 Bước 3: Điều kiện dừng

Bài giảng Tính toán tiến hóa - Bài 9: Multi-objective Optimization - Huỳnh Thị Thanh Bình