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

Genetic Algorithm (GA) Tổng quan 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 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 Khởi tạo quần thể Đánh giá độ thích nghi Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Các thành phần của GA Phương pháp mã hóa lời giải Phương pháp lai tạo Phương pháp đột biến Phương pháp chọn lọc cha mẹ Phương pháp đấu tranh sinh tồn Các phương pháp mã hóa lời giải 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 Genotype space = {0,1} L Phenotype space Encoding (representation) Decoding (inverse representation) 011101001 010001001 10010010 10010001 Các phương pháp mã hóa lời giải - Mã hóa đa giá trị 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ụ 1.7 2.3 5.6 5.2 A C B A Black White Yellow Yellow 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 Các phương pháp mã hóa lời giải - Mã hóa hoán vị 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 Mã hóa cạnh: (1,2),(2,3), (1,4),(4,5) Mã hóa đỉnh cha Parent(1) = 1, Parent(2) = 1. Các phương pháp mã hóa lời giải - Mã hóa Cây – tiếp Prufer: Biểu diễn một cây bằng một vector số nguyên Kích th ư ớc mã hóa bằng n-2, n là số đỉnh của đồ thị Mã hóa: B ư ớc 1: Đánh nhãn các đỉnh trên cây từ 1 đến n Bước 2: Tìm đỉnh là đỉnh có id nhỏ nhất và có bậc = 1 trong cây B ư ớc 3: Đỉnh là đỉnh kết nối với ( duy nhất 1 đỉnh tồn tại, do bậc của là 1) và thêm j vào trong mã hóa B ư ớc 4: Loại bỏ đỉnh và cạnh ( , ) trên cây B ư ớc 5: Lặp lại b ư ớc 2 cho tới khi cây còn 2 đỉnh Các phương pháp mã hóa lời giải - Mã hóa Cây – tiếp Prufer: Giải mã Bước 1: Tìm tập đỉnh S mà không xuất hiện trên mã hóa P B ư ớc 2: Tìm là đỉnh có id nhỏ nhất trong S, là phần tử trái nhất trong mã hóa B ư ớc 3: Loại bỏ đỉnh khỏi S và thêm cạnh ( , ) vào cây B ư ớc 4: Lặp lại b ư ớc 1 cho tới khi S chỉ còn 2 đỉnh (giả sử a,b) Bước 5: Thêm hai cạnh (a,b) vào cây Các phương pháp mã hóa lời giải - Mã hóa Cây – tiếp Prufer: Ví dụ Các phương pháp mã hóa lời giải - Mã hóa Cây – tiếp NetKeys: Gán độ ư u tiên cho mỗi cạnh thêm lần l ư ợt các cạnh theo thứ tự độ ư u tiên sao cho không tạo thành chu trình Kích th ư ớc vector mã hóa = số cạnh trong đồ thị Đồ thị đẩy đủ => nxn Mềm dẻo Độ d ư thừa mã hóa cao Các ph ư ơng pháp lai ghép Trên mã hóa nhị phân, đa giá trị Lai ghép theo điểm cắt Lai ghép đồng bộ Trên mã hóa hoán vị Lai ghép thứ tự -OX Lai ghép t ư ơng hợp bộ phận –PMX Lai chu trình – CX Trên mã hóa số thực Lai ghép chéo hóa nhị phân – SBX Trên mã hóa cây Lai ghép trộn cạnh Các ph ư ơng pháp lai ghép Lai ghép theo điểm cắt a. Một điểm cắt b. Hai điểm cắt c. N điểm cắt Thích hợp với mã hóa nhị phân Các ph ư ơng pháp lai ghép Lai ghép đồng bộ Thích hợp với mã hóa nhị phân Tại mỗi vị trí của cá thể con, lấy ngẫu nhiên 1 số thực u trong [0,1] u<0.5: lấy gene của cha u>= 0.5: lấy của mẹ Các ph ư ơng pháp lai ghép Lai ghép thứ tự Chọn 2 điểm lai bất kì, khác nhau Con 1: Sao chép phần giữa 2 điểm lai của cha 1 vào con 1 Các gen chưa được sao chép, tiến hành thêm vào con 1 bắt đầu từ điểm lai thứ 2, theo thứ tự xuất hiện ở cha 2 Các ph ư ơng pháp lai ghép Lai ghép t ư ơng hợp bộ phận Chọn 2 điểm lai bất kì Con thứ nhất: Sao chép phần giữa 2 điểm lai của cha 1 sang con Các vị trí còn trống, sao chép các gene tương ứng ở cha 2 mà chưa có mặt trong con Các vị trí còn lại thực hiện tìm kiếm “đối sánh” Các ph ư ơng pháp lai ghép Lai ghép t ư ơng hợp bộ phận B ư ớc 1: B ư ớc 2: B ư ớc 3: 9->4->2 8->3 Các ph ư ơng pháp lai ghép Lai ghép chu trình Tìm các chu trình Copy lần lượt các chu trình vào con theo thứ tự nghịch đảo xen kẽ . Các ph ư ơng pháp lai ghép Lai ghép Chéo hóa nhị phân - SBX Với hai cá thể cha mẹ , SBX sinh ra hai cá thể con như sau: B ư ớc 1: Lấy ngẫu nhiên một số thực Bước 2: Tính hệ số theo công thức: trong đó, là hệ số phân bố thường trong khoảng từ 2 đến 10. càng cao thì cá thể con sinh ra càng gần cha mẹ. Các ph ư ơng pháp lai ghép Lai ghép Chéo hóa nhị phân - SBX B ư ớc 3: Các cá thể con và được sinh ra theo công thức Đặc điểm: Hai con có phân phối gần với phân phối của cha mẹ giúp duy trì và kế thừa được những đặc tính tốt của hai cha mẹ. Các ph ư ơng pháp lai ghép Lai ghép trộn cạnh Trộn tập cạnh của hai cây t ư ơng ứng thu đ ư ợc tập cạnh E Thực hiện thuật toán PrimRST để sinh cây khung ngẫu nhiên trên E Các phương pháp đột biến Đảo bít : Biểu diễn nhị phân Đổi chỗ: Biểu diễn nhị phân, hoán vị Đổi giá trị: số nguyên, số thực Đảo đoạn: nhị phân, hoán vị, số nguyên Đột biến cây: biểu diễn cây Đột biến đa thức: số thực Các ph ư ơng pháp đột biến Đảo bít Áp dụng với mã hóa nhị phân Các ph ư ơng pháp đột biến Đảo đổi chỗ Áp dụng với mã hóa nhị phân/ hoán vị Các ph ư ơng pháp đột biến Đổi giá trị Tiến hành thêm bớt một lượng nhỏ vào giá trị của gene Các ph ư ơng pháp đột biến Đảo đoạn Chọn 2 ví trí ngẫu nhiên Đảo đoạn nằm giữa 2 ví trí đó Các ph ư ơng pháp đột biến Đột biến cây Cắt một cây con (subtree) trên cây ban đầu và gắn vào một nút khác trong cây Các ph ư ơng pháp đột biến Đột biến đa thức Đối t ư ợng: Biểu diễn số thực Cá thể đột biến từ theo các bước sau: Bước 1: Lấy ngẫu nhiên một giá trị u thuộc [0,1] Bước 2: Tại mỗi vị trí trên p tính các giá trị và Cập nhật vị trí t ư ơng ứng trên cá thể con : Các ph ư ơng pháp đột biến Đột biến đa thức Đặc điểm: Phân phối của các cá thể con gần với cha mẹ Toán tử parent-centric Các phương pháp chọn lọc cha mẹ Chọc lọc ngẫu nhiên Chọn lọc theo vòng quay roulette Chọn lọc theo xếp hạng Chọn lọc theo thể thức giao đấu Các ph ư ơng pháp lựa chọn cha mẹ Lựa chọn ngẫu nhiên Các cá thể cha mẹ mang đi giao phối đ ư ợc chọn ngẫu nhiên hoàn toàn Các ph ư ơng pháp lựa chọn cha mẹ Lựa chọn theo bánh xe roulete Tính tổng độ thích nghi của cả quần thể Tính xác suất lựa chọn cá thể thứ là Xác suất quỹ tích của cá thế thứ là Lấy ngẫu nhiên một số thực r trong [0,1] Cá thể thứ đ ư ợc lựa chọn nếu Các ph ư ơng pháp lựa chọn cha mẹ Lựa chọn theo thứ hạng Tiến hành xếp hạng các cá thể trong quần thể dựa trên độ thích nghi Các xếp hạng có thể chỉ đơn giản là sắp xếp, cũng có thể sử dụng các hàm đặc biệt Dựa trên hạng đã xếp chọn tỉ lệ tương ứng các cá thể theo ý muốn. Ví dụ: Chọn 50% tốt nhất Chọn 40% tốt nhất và 10% tồi nhất Chia ra làm 3 khoảng: Tốt, trung bình, xấu. Mỗi khoảng lấy 50% tốt nhất (Elitsm) Các ph ư ơng pháp lựa chọn cha mẹ Lựa chọn theo thể thức giao đấu Chọn ngẫu nhiên k cá thể cha mẹ Ghép cặp cá thể đ ư ợc so sánh ngẫu nhiên với nhau và chọn ra hai cá thể tốt nhất làm cha mẹ A B C D A D Fitness(D) > Fitness(C) Fitness(A) > Fitness(B) Phương pháp đấu tranh sinh tồn Nạp lại hoàn toàn Nạp lại ngẫu nhiên Giữ lại cá thể ưu tú Áp dụng các phương pháp của chọn lọc cha mẹ Các ph ư ơng pháp đấu tranh sinh tồn Nạp lại hoàn toàn Sinh ra số con bằng số lượng cha mẹ và tiến hành thay thế tất cả cha mẹ bằng con Có thể gây ra việc mất đi cá thể cha mẹ tốt Tính tăng trưởng ổn định của quần thể bị giảm Nguy cơ bị cục bộ thấp hơn Các ph ư ơng pháp đấu tranh sinh tồn Nạp lại ngẫu nhiên Sau khi lai tạo có k con Chọn ngẫu nhiên k cha mẹ của quần thể để thay thế bằng k con mới Có thể gây ra việc mất đi cá thể cha mẹ tốt Các ph ư ơng pháp đấu tranh sinh tồn Nạp lại ngẫu nhiên Luôn luôn giữ lại cá thể ưu tú nhất của quần thể Đảm bảo quần thể không bao giờ bị suy giảm chất lượng Các ph ư ơng pháp đấu tranh sinh tồn Áp dụng ph ư ơng pháp của lựa chọn cha mẹ Kết hợp các phương pháp chọn lọc để chọn ra cá thể của quần thể cũ bị đào thải Hoặc trộn các cá thể con vào quần thể và sử dụng các phương pháp chọn lọc để chọn các cá thể bị đào thải (con có thể cũng bị loại) Cũng có thể căn cứ vào tuổi của cá thể để đào thải Giải thuật di truyền cơ bản Giải thuật di truyền cho không gian thực Giải thuật di truyền cho các biểu diễn có thứ tự và hoán vị Giải thuật di truyền trên cây và đồ thị Giải thuật di truyền cho các bài toán tối ưu có ràng buộc Cấu trúc quần thể Giải thuật di truyền song song Thanks for your attention