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

Download

Evolution Strategy

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

Email: binhht@soict.hust.edu.vn

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 휎

휃 = 휇, 휎 , 푝_휃푥 ~ 푁 휇, 휎²퐼 = 휇 + 휎 ∗ 푁(0, 퐼)

 Các bước của thuật toán

 Bước 1: Khởi tạo 휃 = 휃⁰, 푡 = 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

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ị 휎^(푡+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