tailieunhanh - Bài giảng Tính toán tiến hóa: Bài 2 - TS. Huỳnh Thị Thanh Bình

Bài giảng "Tính toán tiến hóa: Bài 2 - TS. Genetic Algorithm (GA)" được biên soạn với các nội dung chính sau đây: Tổng quan về thuật toán Genetic Algorithm; Sơ đồ thuật toán GAs; Các thành phần của GA; . Mời các bạn cùng tham khảo bài giảng tại đây! | Genetic Algorithm GA Huỳnh Thị Thanh Bình Email binhht@ Tổng quan 2 Bắt đầu được nghiên cứu từ những năm 70 bởi J. Holland K. DeJong D. Goldberg Thường được áp dụng với Tối ưu hóa rời rạc Tính chất Không quá nhanh Sử dụng các heuristic để mang lại kết quả lại tạo tốt Đặc biệt Lại tạo từ các cá thể cha mẹ tốt có chọn lọc Áp dụng các mô hình chọn lọc và lai tạo khác nhau Tổng quan 3 Các thuật toán GAs khác nhau ở việc sử dụng các toán tử Biểu diễn mã hóa Đột biến Lai ghép Cơ chế chọn lọc sinh tồn sinh sản Sơ đồ thuật toán GA 4 Kiểm tra Đánh giá Sinh Khởi tạo điều độ thích quần thể Chọn lọc Kết thúc quần thể kiện nghi mới dừng Các thành phần của GA 5 I. Phương pháp mã hóa lời giải II. Phương pháp lai tạo III. Phương pháp đột biến IV. Phương pháp chọn lọc cha mẹ V. Phương pháp đấu tranh sinh tồn Các phương pháp mã hóa lời giải 6 Mã hóa nhị phân Mã hóa đa giá trị Mã hóa hoán vị Mã hóa cây cạnh Prufer mã hóa đỉnh cha Rời rạc hóa Các phương pháp mã hóa lời giải - Mã hóa nhị phân 7 Phenotype space Genotype space Encoding 0 1 L representation 10010001 10010010 010001001 011101001 Decoding inverse representation Các phương pháp mã hóa lời giải - Mã hóa đa giá trị 8 Thường sử dụng mã hóa giá trị phức tạp Giá trị được mã hóa có thể là Nguyên hay thực Rời rạc hay liên tục Hữu hạn hay vô hạn Các phương pháp mã hóa lời giải - Mã hóa đa giá trị - Ví dụ 9 a. Các gene trong nhiễm sắc thể nhận giá trị thực. b. Các gene trong nhiễm sắc thể nhận giá trị rời rạc từ một tập vô hạn hoặc hữu hạn A C B A Black White Yellow Yellow Các phương pháp mã hóa lời giải - Mã hóa hoán vị 10 NST là một hoán vị của một tập các gene Phù hợp với các bài toán liên quan đến tính hoán vị VD TSP 1 3 6 7 8 2 5 4 9 Các phương pháp mã hóa lời giải - Mã hóa Cây 11 Mã hóa cạnh 1 1 2 2 3 1 4 4 5 2 4 Mã hóa đỉnh cha 3 5 Parent 1 1 Parent 2 1 . 51 61 32 11 4 Các phương pháp mã hóa lời giải - Mã hóa Cây tiếp 12 Prufer Biểu diễn một cây bằng một vector số nguyên Kích thước mã .