Giải thuật di truyền: chromosome, fitness, selection
Cảm hứng tự nhiên, quần thể nhiễm sắc thể, fitness chọn lọc và khuôn mẫu thuật toán di truyền.
KhóThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học nuôi đàn lời giải tiến hóa qua từng đời. Dùng để tìm tour và lịch khi hàm gãy khúc.
Kiến thức cần nhớ
Mã hóa và fitness
- Định nghĩa: chromosome là chuỗi gen tả 1 lời giải.
- Tour TSP là hoán vị thành phố trên chuỗi gen.
- Fitness là điểm khỏe, tour ngắn thì điểm cao.
- Ví dụ đời thường: như điểm thi quyết ai được chọn.
- Phạt nặng gen vi phạm ràng buộc bài toán.
Chọn lọc
- Giữ khỏe bỏ yếu qua nhiều thế hệ liên tiếp.
- Bánh xe: theo tỉ lệ fitness nhưng dễ lấn át sớm.
- Giải đấu: lấy tốt nhất nhóm ngẫu nhiên ổn định hơn.
- Ví dụ đời thường: như chọn đội tuyển qua vòng loại nhỏ.
- Giữ tinh hoa vài cá thể tốt sang thẳng đời sau.
| Cách chọn | Ưu điểm | Nhược điểm |
|---|---|---|
| Bánh xe | Đơn giản, nhanh | Siêu cá thể lấn át |
| Giải đấu | Ổn định, dễ chỉnh | Chậm hơn một chút |
| Xếp hạng | Chặn lấn át tốt | Phải sắp hạng cả đàn |
Vòng đời thuật toán
- Khởi tạo đàn ngẫu nhiên cộng vài mẹo tốt sẵn.
- Đánh giá fitness cả đàn mỗi thế hệ mới.
- Chọn, lai, đột biến, thay thế rồi lặp lại.
- Ví dụ đời thường: như lai giống cây qua nhiều vụ.
- Theo dõi tốt nhất để phát hiện hội tụ sớm.
Ví dụ
- Input: đàn 10 con cho TSP 200 -> Output: tăng đàn và giảm ép.
- Giải thích: đàn bé thiếu đa dạng nên kẹt tour xấu sớm.
# Giải đấu chọn bố mẹ từ nhóm ngẫu nhiên
nhom = random.sample(dan, k=3) # bốc 3 con
bo_me = max(nhom, key=fitness) # giữ con khỏe nhất
print(bo_me)
💻 Bài tập
Ngôn ngữ: Python 3 với NumPy. Nộp vào day-115/.
Bài 1: GA cho bài toán OneMax và ba lô
def ga(pop_size, n_genes, fitness, init, select, crossover, mutate,
generations, elite=2, seed=0) -> tuple[object, float, list[tuple[float, float]]]:
"""Trả (tốt nhất, fitness tốt nhất, lịch sử (best, trung bình) mỗi thế hệ)."""
| Toán tử | Yêu cầu |
|---|---|
tournament(pop, fit, k=3) | Chọn tốt nhất trong k cá thể ngẫu nhiên |
roulette(pop, fit) | Xác suất tỉ lệ fitness |
one_point_crossover(a, b) | Cho chuỗi bit |
bit_flip(x, p) | Lật mỗi bit với xác suất p |
OneMax 100 bit (fitness = số bit 1) -> đạt 100 trong dưới 200 thế hệ
Ba lô 0-1 (dữ liệu ngày 77) -> khớp nghiệm DP; nghiệm quá tải bị phạt fitness
Bài 2: Tham số và áp lực chọn
Trên OneMax 200 bit:
- So
tournament(k=2),tournament(k=7),roulette. Vẽ fitness tốt nhất và trung bình theo thế hệ. - Thử
elite = 0, 2, 10. Chỉ ra khi nào hội tụ sớm. - Đo độ đa dạng: khoảng cách Hamming trung bình giữa các cá thể theo thế hệ.
Bài 3: GA cho TSP (nâng cao)
- Nhiễm sắc thể là hoán vị. Lai bằng Order Crossover (OX). Đột biến bằng đảo đoạn (như 2-opt).
- Chạy trên berlin52. So với SA ngày 114 cùng số lần tính fitness.
- Khởi tạo 10% đàn bằng tham lam từ các điểm xuất phát khác nhau. So tốc độ hội tụ.
OX của cha [1,2,3,4,5,6,7,8] và mẹ [8,6,4,2,7,5,3,1] với đoạn cắt [3..5]
-> con giữ 4,5,6 ở vị trí 3..5, các vị trí còn lại điền theo thứ tự của mẹ, không trùng
✅ Tiêu chí hoàn thành
- OneMax đạt tối ưu, ba lô khớp DP.
- Hình fitness và độ đa dạng theo thế hệ cho các cấu hình.
- OX luôn ra hoán vị hợp lệ (test 10.000 lần).
- Bảng GA vs SA trên berlin52.
❓ Câu hỏi ôn tập
- Chromosome là gì?
- Fitness để làm gì?
- Giải đấu khác bánh xe sao?
- Lai và đột biến làm gì?
🌕 Bạn đã hoàn thành ngày 115. Làm hết bài tập phía trên rồi sang ngày tiếp theo.