Bài giảng Tính toán tiến hóa - Bài 3: Genetic Algorithm (Phần 2) - Huỳnh Thị Thanh Bình
Nội dung
2
Tổng quan Genetic Programming (GP)
Các toán tử của GP
Ví dụ minh họa
Tổng quan về Genetic Programming
3
Genetic Programming (Lập trình di truyền – GP) có thể coi
là một thuật toán di truyền đặc biệt
Sơ đồ của GP giống sơ đồ của thuật toán GA
Điểm khác biệt giữa GA và GP
GA: Biểu diễn mỗi cá thể (nhiễm sắc thể) dưới dạng chuỗi các
alen
GP: Mỗi cá thể là một hàm số hay chương trình máy tính,
được biểu diễn dưới dạng cây
Mục tiêu của GP là tìm một chương trình tối ưu trong tập
không gian các chương trình có thể, để thu được hiệu suất
cao nhất
Ưng dụng: Tối ưu kiến trúc mạng Neural…
Tổng quan về Genetic Programming
4
Tại mỗi thế hệ, mỗi cá thể (hàm, chương trình) được tiến
hóa để tìm ra hàm số ẩn tối ưu, có độ lỗi thấp nhất cho
bài toán
Ví dụ: Tìm 1 hàm số f(x) sao cho đi qua tất cả các đỉnh
A1, A2, A3, A4…
Cá c toá n tử của GP
5
Biểu diễn cá thể
Lai ghép
Đột biến
Đánh giá độ thích nghi
Biểu diễn cá thể
6
Mỗi cá thể trong GP biểu diễn một chương trình máy
tính hay một hàm ẩn cần tìm
Để đảm bảo ngữ pháp của chương trình, ta cần xác định
hai tập:
Tập kết thúc (terminal set) chứa các biến, hằng số, modun
cơ bản có thể của chương trình
Tập hàm ( function set) chứa tất cả các hàm toán học cơ
bản có thể dùng: +,-,*,/, exp, log, and , or, xor hoặc các cấu
trúc quyết định if-then-else,…
Biểu diễn cá thể
7
Mỗi cá thể được biểu diễn dưới dạng một cấu trúc cây
Các nút lá của cây: Chọn từ tập kết thúc
Các nút trong của cây: Chọn từ tập hàm
Mỗi cá thể được khởi tạo như sau:
Nút gốc: được chọn ngẫu nhiên trong tập hàm
Nút không phải gốc: Chọn ngẫu nhiên trong tập hàm hoặc
tập kết thúc
◼ Chọn trong tập kết thúc: Nút trở thành nút lá
◼ Chọn trong tập hàm: Nút là nút trong
Số lượng nhánh tại mỗi nút phụ thuộc vào hàm cơ bản tại
nút đó
Biểu diễn cá thể - Ví dụ
8
y := x * ln(a) + sin(z) / exp(-x) - 3.4
• Tập kết thúc: x, a, z, 3.4
• Tập hàm: *, +, - , /, ln, sin, exp
Lai ghé p
9
Các phương pháp chọn lọc cha mẹ sử dụng giống GA
Toán tử lai ghép trong GP:
Chọn ngẫu nhiên một cây con trong mỗi cây cha mẹ và tráo
đổi chúng cho nhau
Lai ghé p – Ví dụ
10
Đột biến
11
Các phương pháp đột biến trong GP
Đột biến nút trong
Đột biến nút kết thúc
Đột biến đảo
Đột biến phát triển cây
Đột biến Gauss
Đột biến cắt tỉa cây
Đột biến - Đột biến nút trong
12
Thay thế hàm tại nút đó bằng một hàm khác trong tập hàm
Đột biến - Đột biến nút kết thúc
13
Thay thế biến, hằng tại nút đó bằng một biến, hằng khác
trong tập kết thúc
Đột biến - Đột biến đảo
14
Chọn ngẫu nhiên một nút trong và đảo hai nút con của nó
Đột biến - Đột biến phá t triển câ y
15
Chọn ngẫu nhiên một nút và thay thế toàn bộ cây con của
nút đó bằng một cây con ngẫu nhiên khác
Đột biến - Đột biến Gauss
16
Chọn ngẫu nhiên một nút lá chứa hằng số và thêm giá trị
nhiễu Gauss vào nút đó
Đột biến - Đột biến cắt tỉa câ y
17
Chọn ngẫu nhiên một nút và thay thế nút đó bởi một biến
hay hằng số ngẫu nhiên trong tập kết thúc
Đánh giá độ thí ch nghi
18
Các cá thể được đánh giá trên cùng tập mẫu dữ liệu và giá
trình hiệu suất trung bình thu được trên mẫu đó được sử
dụng là giá trị độ thích nghi
Giả sử có một tập mẫu X và mỗi mẫu chứa ba giá trị đầu
vào (a,x,z) và giá trị đích y. Độ thích nghi được tính như
sau:
Tính giá trị đầu y^ ra thu được của chương trình mà cá
thể biểu diễn với mỗi đầu vào (a,x,z)
Tính giá trị lỗi y^ so với y
Độ sai số trung bình MSE trên toàn bộ tập dữ liệu được
xem như tiêu chí để đánh giá độ thích nghi
Ví dụ minh họa
19
GP tìm Activation Function tối ưu cho Deeplearning [1]
Bước 1: Xác định tập kết thúc và tập hàm
2
2 3
푥 −푥
ሺ
Tập kết thúc: : 0, 1, 푥, −푥, 푥 , 푥 , 푥 , 푥, 푒 , 푒 , log 1 +
푥ሻ
푒 , log 푥 + 휖 , sin 푥 , sinh 푥 , arcsinh(x), cos(x),
cosh(x), tanh(x), arctanh(x), max{x, 0}, min{x, 0}, σ(x),
erf(x), sinc(x)
Tập hàm: x1 + x2, x1 − x2, x1 · x2, x1/(x2 + ϵ), max{x1, x2},
min{x1, x2}
[1] Bingham, Garrett, William Macke, and Risto Miikkulainen. "Evolutionary
optimization of deep learning activation functions." arXiv preprint
arXiv:2002.07224 (2020) (GECCO 2020)
Ví dụ minh họa
20
Đột biến chương trình
(min{1, cosh(x)})^3 ∗ σ(e x + arctan(x))
(min{1, cosh(x)})^3 ∗ |e x + arctan(x)|
Tải về để xem bản đầy đủ
23 trang
17640
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tính toán tiến hóa - Bài 3: Genetic Algorithm (Phần 2) - 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_3_genetic_algorithm_phan_2.ppt
3. GeneticProgramming.pdf
