Bài giảng Tính toán tiến hóa - Chương 10: Multi. Objective optimization

MULTI-OBJECTIVE OPTIMIZATION  Nội dung 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 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 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 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 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 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 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 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 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 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 Phân hoạch Hàng xóm A multi-objective evolutionary algorithm based on decomposition Một số khái niệm 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 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 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 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 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: Bài toán con 1: Bài toán con 2: Bài toán con 3: Hàng xóm? Một số khái niệm 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 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 Cấu trúc thuật toán Đầu vào: Các tham số: vector trọng số : Số hàng xóm của 1 bài toán con Các đối tượng được duy trì và cập nhật qua từng thế hệ: Quần thể: lời giải của bài toán con Điểm tham chiếu : Dùng cho phương pháp đánh giá Tchebycheff Không cần thiết nếu không dùng Tchebycheff Quần thể ngoài EP: Biên Pareto của tất cả lời giải tìm được tính đến thế hệ hiện tại Không cần thiết nếu trực tiếp dùng quần thể làm đầu ra Cấu trúc thuật toán Bước 1: Khởi tạo B ư ớc 1.1: Đặt quần thể ngoài Bước 1.2: Xây dựng tập hàng xóm: : Tập hàng xóm của bài toán thứ - vector trọng số gần với vector nhất B ư ớc 1.3: Khởi tạo ngẫu nhiên quần thể: Bước 1.4: Khởi tạo điểm tham chiếu : Cấu trúc thuật toán Bài toán 1 Bài toán 2 Bài toán N EP Bước 1.1 Cấu trúc thuật toán Bước 2: Tiến hóa theo thế hệ (1) Với mỗi bài toán con : B ư ớc 2.1: Tạo lời giải mới Chọn ngẫu nhiên 2 lời giải hàng xóm của ( ) Lai ghép:  lời giải mới Đột biến  lời giải mới B ư ớc 2.2: Sửa chữa/Cải thiện lời giải Nếu không là lời giải hợp lệ, cần sửa chữa hoặc loại bỏ Cải thiện nếu có thể (tùy bài toán) Cấu trúc thuật toán Bài toán 1 Bài toán 2 Bài toán N EP Bước 2.1: Tạo lời giải mới Xét bài toán 2 Chọn Chọn Lai ghép + Đột biến Bước 2.2: Sửa chữa / Cải thiện Cấu trúc thuật toán Bước 2: Tiến hóa theo thế hệ (2) Với mỗi bài toán con : B ư ớc 2.3: Cập nhật Bước 2.4: Cập nhật các hàng xóm: Với mọi nếu (theo Tchebycheff) t hay bằng Bước 2.5: Cập nhật EP: Loại mọi lời giải bị trội bởi Thêm vào EP nếu nó không bị trội bởi lời giải nào Cấu trúc thuật toán Bài toán 1 Bài toán 2 Bài toán N EP Bước 2.4: So sánh + Thay thế Bước 2.5: Cập nhật EP Cấu trúc thuật toán Bước 3: Điều kiện dừng Điều kiện dừng: Tương tự các thuật toán GA thông thường Số thế hệ tối đa Số thế hệ tối đa mà EP không đ ư ợc cập nhật Đầu ra: EP (Biên Pareto) Đánh giá Ưu điểm: Nhanh, độ phức tạp tương đương GA thông thường Biên Pareto đều Khả năng duy trì cân bằng các hàm mục tiêu (ví dụ: tránh hội tụ sớm khi áp dụng tìm kiếm cục bộ quá mạnh lên 1 mục tiêu) Nhược điểm: Hiệu quả phụ thuộc lớn vào tham số người dùng tự đặt (đặc biệt là cách chia vector trọng số) Không hiệu quả bằng các thuật toán như NSGA-II trong nhiều bài toán thông thường (khả năng tối ưu các mục tiêu tương đối đồng đều) Thanks for your attention