intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Tính toán tiến hóa - Bài 5: Evolution strategy

Chia sẻ: Hàn Lâm Cố Mạn | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST
Báo xấu
20
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Tính toán tiến hóa - Bài 5: Evolution strategy. Bài này cung cấp cho học viên những nội dung về: tổng quan Evolution Strategy (ES); các loại ES; chiến lược chọn lọc sinh tồn; chiến lược tiến hóa Gaussian đơn giản;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tính toán tiến hóa - Bài 5: Evolution strategy

  1. Evolution Strategy PGS.TS Huỳnh Thị Thanh Bình Email: binhht@soict.hust.edu.vn
  2. Nội dung 2  Tổng quan Evolution Strategy (ES)  Các loại ES  Ví dụ minh họa
  3. Tổng quan về Evolution Strategy 3  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
  4. Tổng quan về Evolution Strategy 4  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
  5. Tổng quan về Evolution Strategy 5  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
  6. Các loại ES 6  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)
  7. Simple Gaussian Evolution Strategies 7  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 𝜎 𝜃 = 𝜇, 𝜎 , 𝑝𝜃 𝑥 ~ 𝑁 𝜇, 𝜎 2 𝐼 = 𝜇 + 𝜎 ∗ 𝑁(0, 𝐼)  Các bước của thuật toán  Bước 1: Khởi tạo 𝜃 = 𝜃 0 , 𝑡 = 0  Bước 2: Sinh ngẫu nhiên 𝜆 cá thể từ phân phối 𝑝𝜃 (𝑡+1) (𝑡+1) 𝑃 𝑡 + 1 = 𝑥𝑖 𝑥𝑖 = 𝜇 (𝑡) + 𝜎 (𝑡) ∗ 𝑁 0, 𝐼 , i = 1, … , 𝜆}  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 𝜇 (𝑡+1) và 𝜎 (𝑡+1)  Bước 4: Lặp lại bước 2 và 3
  8. Simple Gaussian Evolution Strategies – Ví dụ 8 Bước 1: Khởi tạo 1- Initial Solution
  9. Simple Gaussian Evolution Strategies – Ví dụ 9 Bước 2: Sinh ra 𝜆 cá thể con
  10. Simple Gaussian Evolution Strategies – Ví dụ 10 Bước 3: Chọn ra 𝜇 cá thể con tốt nhất
  11. Simple Gaussian Evolution Strategies – Ví dụ 11 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
  12. Simple Gaussian Evolution Strategies 12  𝜎 càng cao: Mức độ khám phá của thuật toán càng lớn  Tuy nhiên giá trị 𝜎 (𝑡+1) 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
  13. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 13  Để 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ệ
  14. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 14
  15. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 15  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
  16. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 16  Hiệp phương sai chỉ ra hướng mà quần thể nên tiến hóa Covarianc Varianc e e
  17. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 17
  18. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 18
  19. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 19
  20. Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2