Bài giảng Tính toán tiến hóa - Bài 6: Differential Evolution - Huỳnh Thị Thanh Bình
Tổng quan
2
Giải thuật tiến hóa sai phân (Differential Evolution - DE):
Thuật toán tối ưu ngẫu nhiên dựa trên quần thể
Được giới thiệu bởi Storn và Price vào năm 1996
Thuộc lớp giải thuật tiến hóa
Xử lý các bài toán tối ưu tham số thực, tìm cực trị hàm
đa biến, phi tuyến, không khả vi
Các dạng bài toán mà DE giải quyết
Hàm mục tiêu 푓: 푋 ⊂ 푅퐷 → 푅, 푋 ≠ ∅. Mục tiêu bài toán
tìm giá trị x* sao cho
푥∗ ∈ 푋: 푓 푥 ≥ 푓 푥∗ ∀ 푥 ∈ 푋
Sơ đồ của DE
3
Đột biến
Khởi tạo
Chọn lọc
Lai ghép
Mô hì nh thuật toá n
4
Khởi tạo
5
Giả sử cần tối ưu 퐷 tham số
Tham số thứ 푘 trong khoảng giá trị [퐿퐵푘, 푈퐵푘]
Kích thước quần thể 푁 ≥ 4
Mỗi cá thể được biểu diễn bằng một vector D
chiều
Cá thể thứ i
퐼푖 = 퐼푖1, 퐼푖2, … , 퐼푖퐷
I푖푗 = 푟푎푛푑 0,1 ∗ 푈퐵 − 퐿퐵 + 퐿퐵
푗
푗
푗
Đột biến
6
Mỗi cá thể trong DE đều tham gia vào quá trình
đột biến +lai ghép+ chọn lọc
Quá trình đột biến được thực hiện trước khi lai
ghép
Với mỗi cá thể 퐼푘 ta chọn ngẫu nhiên 3 cá thể khác
nhau 퐼푘1, 퐼푘2, 퐼푘3 푘 ≠ 푘1 ≠ 푘2 ≠ 푘3 .
Toán tử đột biến được thực hiện bằng cách thêm
sự chênh lệch giữa 2 cá thể vào cá thể thứ 3
푉 = 퐼푘3 + 퐹 ∗ (퐼푘2 − 퐼푘1)
푘
F là hằng số để scale chênh lệnh, 퐹 ∈ [0,2]
푉 là vector đột biến
푘
Lai ghé p
7
Cá thể con 푂푘 được sinh ra bằng cách lai ghép cá
thể 퐼푘 và vector đột biến 푉
푘
Toán tử lai ghép sử dụng lai ghép nhị thức
Chọn ngẫu nhiên một số nguyên j ∈ [1, 퐷]
푉 푛ế푢 푗 = 푖 ℎ표ặ푐 푟푎푛푑 0,1 < 퐶푅
푘푖
푂푘푖 = ቊ
퐼푘푖 푛푔ướ푐 푙ạ푖
Sinh ra 1 con
Chọn lọc
8
Cá thể con 푂푘 sinh ra được so sánh với cá thể cha
퐼푘 của chúng
Nếu độ thích nghi của 푂푘 lớn hơn 퐼푘 thì cá thể con
sẽ thay thế cá thể cha trong thế hệ tiếp theo
Cá c biến thể của DE
9
Khác nhau ở cách tính vector đột biến
Adaptive ?
DE/rand/1 : 푉 = 퐼푘1 + 퐹 ∗ (퐼푘3 − 퐼푘2)
푘
DE/rand/2: 푉 = 퐼푘1 + 퐹 ∗ 퐼푘3 − 퐼푘2 + 퐹2 ∗ (퐼푘5 − 퐼푘4)
푘
1
DE/best/1: 푉 = 퐼푏푒푠푡 + 퐹 ∗ (퐼푘2 − 퐼푘1)
푘
DE/best/2: 푉 = 퐼푏푒푠푡 + 퐹 ∗ 퐼푘2 − 퐼푘1 + 퐹2 ∗ (퐼푘4 − 퐼푘3)
푘
1
DE/target-to-best/1:
푉 = 퐼푘 + 퐹 ∗ 퐼푏푒푠푡 − 퐼푘 + 퐹2 ∗ 퐼푘2 − 퐼푘1
푘
1
Hiệu chỉnh tham số trong DE
10
Kích thước quần thể (N)
F
CR
Hiệu chỉnh tham số trong DE
Kí ch thước quần thể
11
Các giải thuật tiến hóa mong muốn khám phá được
nhiều không gian tìm kiếm trong các thế hệ đầu
Ở các thế hệ cuối, quá trình tập trung khai thác những
vùng có chứa lời giải hứa hẹn.
Các giải thuật tiến hóa khác nhau ở mức độ khám phá
và khai thác của chúng
Khám phá => Kích thước quần thể lớn
Khai thác => Kích thước quần thể nhỏ
Storn và Price chỉ ra nên chọn kích thước quần thể 푁 ∈
5퐷 , 10퐷 với D là số chiều không gian tìm kiếm
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
12
jDE
Điều kiển F và CR bởi 2 tham số 푟 , 푟
1 2
Cập nhật F và CR
퐹퐿 + 푟푎푛푑1 ∗ 퐹 푛ế푢 푟푎푛푑2 < 푟
푢
1
퐹 = ቊ
푖,퐺+1
퐹 푛푔ượ푐 푙ạ푖
푖,퐺
푟푎푛푑3 푛ế푢 푟푎푛푑4 < 푟2
퐶푅푖,퐺+1 = ቊ
퐶푅푖,퐺 푛푔ượ푐 푙ạ푖
푟 = 푟2 = 0.1, 퐹 ∈ 0.1, 0.9 , 퐶푅 ∈ [0,1]
1
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
13
SaDE
F = lấy ngẫu nhiên theo phân phối chuẩn N(0.5,0.3)
퐶푅 ~푁 CRm, std , std = 0.1. Giá trị trung bình ban
đầu CRm =0.5
Trong một số thế hệ (cụ thể 5), CR không đổi. Sau đó
CR được sinh lại theo phân phối 푁 CRm, std
Sau một số thế hệ (25 thế hệ) , CRm được tính lại từ
giá trị trung bình của các giá trị CR của các cá thể con
thành công ở các thế hệ trước
Mỗi khi tính lại CRm , các giá trị CR cũ bị xóa bỏ
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
14
JADE
퐶푅 ~푁 CRm, 0.1 , 퐶푅 ∈ 0,1
◼ Cập nhật
퐶푅푚 = 1 − 푐 퐶푅푚 + 푐 ∗ 푚푒푎푛퐴(푆퐶푟)
◼ 푆퐶푟 là tập các giá trị CR của các cá thể con thành công
F ~푁 Fm, 0.1 , F∈ 0,1
◼ Cập nhật
퐹푚 = 1 − 푐 퐹푚 + 푐 ∗ 푚푒푎푛퐿(푆퐹)
퐹 퐹2
σ퐹∈푆
푚푒푎푛퐿 =
σ퐹∈푆
퐹
퐹
푐 ∈ [0.05, 0.2]
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
15
SHADE
Sử dụng Lehmer mean (Cec 14) để tính 푆퐹, 푆퐶푟
Lưu trữ 푆퐹, 푆퐶푟 cảu mỗi thế hệ vào trong lịch sử
푀퐹, 푀퐶푟
푀퐹, 푀퐶푟 là mảng số thực có H phần tử
Cặp giá trị (퐹 , 퐶푟 ) được chọn bằng cách lấy ngẫu
푖
푖
nhiên một số k trong khoảng [1,H]
◼ 퐹 = Cauchy( MF k , 0.1)
푖
◼ 퐶푟 = N( MCr k , 0.1)
푖
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
16
SHADE
k = 2
◼ 퐹 = Cauchy(0.52, 0.1)
푖
◼ 퐶푟 = N(0.87, 0.1)
푖
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
17
SHADE
Các phần tử trong 푀퐹, 푀퐶푟 ban đầu được khởi tạo đều
là 0.5
퐹 , 퐶푟 được sử dụng bởi các cá thể con thành công
푖
푖
được lưu trong 푆퐹, 푆퐶푟
Sau mỗi thế hệ thứ i, tính lại 푆퐹, 푆퐶푟 và lưu trữ lại vị trí
k = i mod H +1 trong mảng 푀퐹, 푀퐶푟 tương ứng
Hiệu chỉnh tham số trong DE
Tỷ lệ lai ghé p (CR) và hệ số scale F
18
SHADE
Thanks for your attention
19 trang
14500
Bạn đang xem tài liệu "Bài giảng Tính toán tiến hóa - Bài 6: Differential Evolution - Huỳnh Thị Thanh Bình", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tinh_toan_tien_hoa_bai_6_differential_evolution_hu.ppt
6. DE.pdf
