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

Download

Evolutionary Programming

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

Email: [email protected]

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

Ví dụ minh họa

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ụ 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

 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:

1. Thay đổi trạng thái ban đầu

2. Xóa trạng thái

3. Thêm một trạng thái

4. Thay đổi một dịch chuyển trạng thái

5. 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ư

 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]

푓 푥 = sin 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:

푂 푖 = 푃 푖 + 훿_푖푣ớ푖 훿_푖~푁(0, 휎_푖²)

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

17 trang Thùy Anh 20780 Free

Download

Bạn đang xem tài liệu "Bài giảng Tính toán tiến hóa - Bài 4: Evolutionary Programming - 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_4_evolutionary_programming.ppt
4. EvolutionaryProgramming.pdf