Bài giảng Tính toán tiến hóa - Bài 2: Genetic algorithm (GA). Bài này cung cấp cho học viên những nội dung về: sơ đồ thuật toán GA; các thành phần của GA; các phương pháp mã hóa lời giải; các phương pháp lai ghép; các phương pháp đột biến; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | 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 Khởi tạo Đánh giá độ Sinh quần Chọn lọc điều kiện Kết thúc quần thể thích nghi thể 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ã .
