Bài giảng Tính toán tiến hóa - Chương 3: Genetic Programming

Genetic Programming Nội dung 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 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 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 Biểu diễn cá thể Lai ghép Đột biến Đánh giá độ thích nghi Biểu diễn cá thể 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ể 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ụ 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 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ụ Đột biến 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 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 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 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 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 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 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 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 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 Tập kết thúc: : 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 Đột biến chương trình Ví dụ minh họa Lai ghép Ví dụ minh họa- Kết quả thu đ ư ợc Thanks for your attention