Bài giảng Tính toán tiến hóa - Chương 6: Evolution Strategy

Evolution Strategy Nội dung Tổng quan Evolution Strategy (ES) Các loại ES Ví dụ minh họa Tổng quan về Evolution Strategy Evolution Strategy (Chiến l ư ợc tiến hóa – ES) Thuộc lớp các thuật toán tiến hóa EAs, dựa trên quần thể Lấy cảm hứng từ chiến l ư ợc chọn lọc tự nhiên Rất hiệu quả cho việc tối ư u số thực Tổng quan về Evolution Strategy Cho hộp đen với hàm mục tiêu cần tối ư u f(x) Không thể tính đ ư ợc đạo hàm, không lồi. f(x) là tất định Gọi là phân phối của các lời giải tốt cho việc tối ưu f(x) Nếu dạng phân phối là xác định (giả sử gauss) thì là tham số mang thông tin về lời giải tốt nhất được cập nhật qua mỗi thế hệ trong EAs Tổng quan về Evolution Strategy Bắt đầu với giá trị khởi tạo , Các thuật toán ES cập nhật theo 3 bước như sau: B ư ớc 1: Sinh một quần thể ban đầu P(t) , với N mẫu. B ư ớc 2: Đánh giá các cá thể trong P(t) Bước 3: Chọn một tập con cá thể có độ thích nghi tốt nhất trong P(t) và cập nhật lại B ư ớc 4: t = t+1 và lặp lại b ư ớc 1 cho đến khi thỏa mã ĐK dừng Các loại ES Dựa theo chiến l ư ợc chọn lọc sinh tồn ( : Chọn cá thể tốt nhất từ cá thể con để sinh tồn ở thế hệ tiếp theo ( : Chọn cá thể tốt nhất từ tập hợp của cá thể con và cá thể cha trước đó Các thuật toán ES phổ biến: Simple Gaussian Evolution Strategies Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Simple Gaussian Evolution Strategies Là chiến l ư ợc tiến hóa đ ơ n giản và cổ điển nhất của ES Phân phối của các cá thể là phân phối Gauss n-chiều lưu trữ thông tin của giá trị trung bình và độ lệch chuẩn Các b ư ớc của thuật toán Bước 1: Khởi tạo Bước 2: Sinh ngẫu nhiên cá thể từ phân phối Bước 3: Chọn ngẫu nhiên cá thể tốt nhất trong P(t+1) để cập nhật lại và Bước 4: Lặp lại b ư ớc 2 và 3 Simple Gaussian Evolution Strategies – Ví dụ B ư ớc 1: Khởi tạo 1- Initial Solution Simple Gaussian Evolution Strategies – Ví dụ B ư ớc 2: Sinh ra cá thể con Simple Gaussian Evolution Strategies – Ví dụ B ư ớc 3: Chọn ra cá thể con tốt nhất Simple Gaussian Evolution Strategies – Ví dụ B ư ớc 4: Cập nhật giá trị trung bình của phân phối và lặp lại b ư ớc 2 và 3 Simple Gaussian Evolution Strategies càng cao: Mức độ khám phá của thuật toán càng lớn Tuy nhiên giá trị khá tương đồng với Khả năng hội tụ kém khi cao Hình dạng của phân phối trong SGES là giống nhau ở mọi thởi điểm Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Để khắc phụ những điểm yếu của SGES, CMA-ES xây dựng cơ chế thích nghi, điều chỉnh không gian khám phá sau mỗi thế hệ Hình dạng của phân phối thay đổi và cập nhật sau mỗi thế hệ Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Covariance Matrix Adaptation Evolution Strategies (CMA-ES) CMA-ES thay đổi hình dạng của phân phối thông qua việc thích nghi hiệp ph ư ơng sai C Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Hiệp ph ư ơng sai chỉ ra h ư ớng mà quần thể nên tiến hóa V ariance Covariance Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Phân phối của các cá thể đ ư ợc xác định theo biểu thức điều khiển mức độ scale của phân phối, gọi là step-size Step-size Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Các b ư ớc của CMA-ES: Bước 1: Khởi tạo: Ma trận hiệp ph ư ơng sai C = I (ma trận đ ơ n vị) m : vector nx1 chứa giá trị NST trung bình ban đầu của quần thể : Step size ( vector nx1 chứa độ lệch chuẩn của các biển trong NST) B ư ớc 2: Sinh ra cá thể con thông qua cơ chế đột biến vector trung bình Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Bước 3: Đánh giá độ thích nghi các cá thể con vừa sinh ra Bước 4: Sắp xếp các cá thể con theo thứ tự giảm dần độ thích nghi: B ư ớc 5: Update giá trị trung bình m của quần thể Với là cá thể tốt nhất đầu tiên trong quần thể con sau khi sắp xếp là vector hằng số ( ): Hệ số đóng góp của các cá thể vào vector trung bình Covariance Matrix Adaptation Evolution Strategies (CMA-ES) B ư ớc 6: Cập nhật đ ư ờng tiến hóa step –size Với : tốc độ phân hủy C: ma trận hiệp ph ư ơng sai = với : Vector ngẫu nhiên để đột biến trung bình sinh ra cá thể i B ư ớc 7: Cập nhật step-size Với ||X|| là chuẩn Euclid của vector X: Covariance Matrix Adaptation Evolution Strategies (CMA-ES) B ư ớc 8: Cập nhật đ ư ờng tiến hóa của ma trận hiệp ph ư ơng sai C Với : tốc độ phân hủy Bước 9: Cập nhật ma trận C * Với , Covariance Matrix Adaptation Evolution Strategies (CMA-ES) Điểm mạnh của CMA-ES Hội tụ nhanh sau một số l ư ợng thế hệ nhỏ Giải quyết đ ư ợc các bài toán số chiều cao, không gian tìm kiếm rộng lớn, hoặc có hàm mục tiêu không tính đ ư ợc đạo hàm Điểm yếu: Tốc độ tính toán, nhiều kiến thức toán học, lý thuyết Thanks for your attention