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

Bài giảng "Tính toán tiến hóa: Bài 9 - Multi-objective optimization" được biên soạn với các nội dung chính sau: Tối ưu đa mục tiêu; A multi-objective evolutionary algorithm based on decomposition. Mời các bạn cùng tham khảo bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Tính toán tiến hóa: Bài 9 - TS. Huỳnh Thị Thanh Bình MULTI-OBJECTIVE OPTIMIZATION PGS.TS Huỳnh Thị Thanh Bình Email: binhht@soict.hust.edu.vn 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:  (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  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:  Ví dụ: Hai mục tiêu: 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:  Mục tiêu mới: Cực tiểu hóa: 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: 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: Bài toán con 1: Bài toán con 2: … Bài toán con 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ó . Có 2 bài toán con khác: và . 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 ()  Khoảng cách 2 bài toán con là khoảng cách Euclid 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:  : 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: Hàng xóm? Bài toán con 1: Bài toán con 2: Bài toán con 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ậ ...