›
›

Bài giảng Tính toán tiến hóa - Bài 3: Genetic Algorithm (Phần 1) - Huỳnh Thị Thanh Bình

Download
Genetic Algorithm (GA)  
PGS.TS Huỳnh Thị Thanh Bình  
Email: [email protected]n  
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  
điều kiện  
dừng  
Khởi tạo  
quần thể  
Đánh giá độ  
thích nghi  
Sinh quần  
thể mới  
Chọn lọc  
Kết thúc  
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 =  
{0,1}L  
Encoding  
(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.  
1.7  
2.3  
5.6  
5.2  
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,2),(2,3), (1,4),(4,5)  
Mã hóa đỉnh cha  
1
2
4
3
5
Parent(1) = 1, Parent(2) = 1….  
1
1
2
1
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ã 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  
13  
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  
14  
Prufer: Ví dụ  
Cá c phương phá p mã hó a lời giải  
- Mã hóa Cây – tiếp  
15  
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  
16  
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  
17  
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ộ  
18  
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ẹ  
Thích hợp với mã hóa nhị phân  
Cá c phương phá p lai ghé p  
Lai ghé p thứ tự  
19  
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  
20  
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”  
Tải về để xem bản đầy đủ
ppt 45 trang Thùy Anh 22020 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tính toán tiến hóa - Bài 3: Genetic Algorithm (Phần 1) - 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:

  • pptbai_giang_tinh_toan_tien_hoa_bai_3_genetic_algorithm_phan_1.ppt
  • pdf3. Genetic Algorithm.pdf