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

Evolutionary Programming Nội dung Tổng quan Evolutionary Programming (EP) Các toán tử của EP Ví dụ minh họa Tổng quan về Evolutionary Programming Evolutionary Programming (Lập trình tiến hóa – EP) về c ơ bản khác GA và GP: Lấy cảm hứng từ việc mô phỏng các hành vi trong quá trình tiến hóa GP tìm một tập hành vi tối ư u trong tập không gian hành vi quan sát đ ư ợc GP không sử dụng toán tử lai ghép , chỉ sử dụng toán tử đột biến để sinh ra quần thể con mới S ơ đồ thuật toán EP B ư ớc 1: Khởi tạo một quần thể P(0) có N cá thể, t =0 Bước 2: Đánh giá độ thích của các cá thể trong P(t) Bước 3: Đột biến mỗi các thể trong P(t) để sinh ra một quần thể con O(t) Bước 4: Đánh giá các cá thể trong O(t) B ư ớc 5 : Chọn lọc P(t+1) từ P(t) và O(t) Bước 6: t = t+1 và lặp lại b ư ớc 2,3,4,5 cho đến khi thỏa mã DK dừng Các toán tử của GP Biểu diễn cá thể Đột biến và chọn lọc sinh tồn <- Khác biệt Đánh giá độ thích nghi Đột biến và chọn lọc sinh tồn Phép đột biến đ ư ợc thực hiện trên mỗi cá thể trong quần thể Cá thể con sinh ra sẽ cạnh tranh với cá thể cha để sinh tồn trong thế hệ tiếp theo Quá trình chọn lọc đ ư ợc diễn ra theo các cách sau: Trên tất cả các cá thể : Cá thể cha và con có c ơ hội đ ư ợc lựa chọn nh ư nhau. Có thể dung các toán tử chọn lọc sinh tồn trong GA nh ư tournament( giao đấu).. Elitist : gọi S = N1 cá thể tốt nhất trong P(t) P(t+1) = S U {N-N1 cá thể tốt nhất trong (P(t)\S) và O(t) } Cull strategy : Loại bỏ các cá thể cha và con tồi nhất Vi dụ 1: EP tiến hóa máy trạng thái Ví dụ 2: EP tối ư u hàm số f(x) Ví dụ minh họa Ví dụ 1- EP tiến hóa máy trạng thái Ví dụ 1- EP tiến hóa máy trạng thái hữu hạn Máy trạng thái hữu hạn (Finite-state machine FSM) là gì ? Là một chuuwong trình máy tính biểu diễn các hành ddoogj cần thực thi Các hành động phụ thuộc vào trạng thái hiện tại của máy và tham số đầu vào FSM đ ư ợc định nghĩa nh ư sau: Với S: tập hữu hạn các trạng thái I : Tập hữu hạn các kí hiệu đầu vào O: Tập hữu hạn các kí hiệu đầu ra : hàm trạng thái tiếp thoe : hàm kí hiệu tiếp theo Ví dụ 1- EP tiến hóa máy trạng thái hữu hạn Ví dụ 1- EP tiến hóa máy trạng thái hữu hạn Biểu diễn cá thể: Chuỗi nhị phân 6 bit Bit 1: 1: trạng thái đang hoạt động, 0: không hoạt động Bit 2: Biểu diễn kí hiệu đầu vào ( do chỉ có 0,1 nên dung 1 bít) Bit 3,4: Biểu diễn trạng thái tiếp theo của máy ( do có 3 trạng thái) Bit 5,6: Biểu diễn trạng kí hiệu đầu ra tiếp theo ( Do có 3 kí hiệu đầu ra có thể) Ví dụ 1- EP tiến hóa máy trạng thái hữu hạn Độ thích nghi: Độ thích nghi của các cá thể đ ư ợc đo bằng khả năng dự đoán đúng kí hiệu đầu ra Đột biến: Có thể áp dụng các ph ư ơng pháp sau: Thay đổi trạng thái ban đầu Xóa trạng thái Thêm một trạng thái Thay đổi một dịch chuyển trạng thái Thay đổi kí hiệu đầu ra với trạng thái hiện tại và đầu vào không đổi Các toán tử có thể áp dụng nh ư sau Ví dụ 1- EP tiến hóa máy trạng thái hữu hạn Các toán tử đột biến có thể áp dụng theo các cách nh ư sau Chọn ngâu nhiên đều 1 trong 5 ph ư ơng pháp đầu tiên và áp dụng với xác xuất đột biến pm Sinh một số theo phân phối Possion với trung bình . Lựa chọn ngẫu nhiên đều toán tử đột biến và áp dụng theo thứ tự Ví dụ 2- EP tối ư u hàm số f(x) Ví dụ 2- EP tối ư u hàm f(x) Giả sử cần tối thiểu hàm số f(x) trong đoạn [0,2] Mỗi cá thể đ ư ợc biểu diễn bằng một vector số thực chỉ chứa 1 phần tử Mỗi cá thể đ ư ợc khởi tạo ngẫu nhiên đều trong đoạn [0,2] Độ thích nghi: Cá teher nào cho giá trị f(x) càng nhỏ thì có độ thích nghi càng cao Đột biến: Sử dụng đột biến Gauss: Cộng thêm một l ư ợng giá trị nhỏ vào cá thể P(i) nh ư sau: Ví dụ 2- EP tối ư u hàm f(x) có thể được lựa chọn theo các cách như sau: Không đổi, và giá trị nhỏ Ban đầu lớn và giảm dần qua các thế hệ : Tăng khả năng khám phá của thuật toán ở giai đoạn ban đầu và khả năng khai thác ở các giai đoạn sau để thuật toán tội tụ bằng độ lệch chuẩn của quần thể bố mẹ Tự thích nghi. Thanks for your attention