Lai, đột biến và GA cho TSP, vertex cover
Toán tử lai đột biến, GA cho TSP và phủ đỉnh tối thiểu, chỉnh tham số và ứng dụng xa hơn.
Chuyên giaThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học thuật toán di truyền với lai và đột biến. Dùng nó để tìm đường đi ngắn và tập đỉnh phủ rẻ.
Kiến thức cần nhớ
Lai và đột biến là gì
- Lai là trộn gen 2 bố mẹ thành con.
- Đột biến là sửa nhỏ ngẫu nhiên để giữ đa dạng.
- Ví dụ đời thường: con lấy mắt bố, mũi mẹ, thêm nốt ruồi riêng.
- Lai giúp hội tụ nhanh, đột biến giúp khỏi kẹt sớm.
Lai cho TSP dạng hoán vị
- TSP là tour thăm mỗi thành phố đúng 1 lần.
- Lai cắt đơn hay tạo tour trùng và thiếu thành phố.
- Lai OX giữ 1 đoạn của bố, điền phần còn lại theo thứ tự mẹ.
- Ví dụ: bố 1-2-3-4, mẹ 4-3-2-1, con vẫn đủ 4 thành phố.
GA cho phủ đỉnh dạng bit
- Phủ đỉnh là chọn ít đỉnh sao cho mọi cạnh đều chạm đỉnh chọn.
- Mã hóa bit: 1 là chọn đỉnh, 0 là bỏ.
- Fitness = số đỉnh chọn + phạt nặng mỗi cạnh hở.
- Ví dụ đời thường: đặt camera sao cho mọi hành lang đều có camera soi.
| Bài toán | Mã hóa | Lai hợp lệ | Đột biến |
|---|---|---|---|
| TSP | Hoán vị | OX, PMX | Đổi 2 thành phố |
| Phủ đỉnh | Chuỗi bit | Lai 1 điểm, lai đều | Lật 1 bit |
Ví dụ
- Input: 2 tour cha 1 2 3 4 5 và 5 4 3 2 1. Output: con OX 1 2 3 5 4 hợp lệ đủ 5 thành phố.
- Giải thích: con giữ khung tốt của bố mà không trùng thiếu.
- Input: phủ đỉnh 4 nút hình vuông, nghiệm 1010. Output: fitness = 2 đỉnh + 0 phạt = 2.
- Giải thích: 2 đỉnh đối nhau đã phủ hết 4 cạnh.
💻 Bài tập
Ngôn ngữ: Python 3 với NumPy (hoặc C++). Dùng khung GA ngày 115. Nộp vào day-122/.
Bài 1: Toán tử lai và đột biến cho hoán vị
| Toán tử | Yêu cầu |
|---|---|
order_crossover(p1, p2, rng) | OX |
pmx(p1, p2, rng) | Partially Mapped Crossover |
edge_recombination(p1, p2, rng) | Giữ cạnh chung của 2 cha |
swap_mutation, inversion_mutation, scramble_mutation |
OX: cha [1 2 3 4 5], mẹ [5 4 3 2 1], đoạn cắt vị trí 0..2 -> con [1 2 3 5 4]
Mọi toán tử luôn trả hoán vị hợp lệ (test 10.000 lần mỗi toán tử)
Bài 2: So toán tử trên TSP
Chạy GA trên berlin52, cùng số lần tính fitness (ví dụ 200.000).
lai đột_biến best trung_bình_10_lần độ_lệch
OX inversion ...
PMX inversion ...
ERX inversion ...
OX swap ...
Thêm memetic: sau khi tạo con, chạy 2-opt cục bộ vài bước. So với GA thường.
Bài 3: GA cho phủ đỉnh (nâng cao)
- Mã hóa bit. Fitness (tối thiểu hóa) = số đỉnh chọn +
penalty× số cạnh chưa phủ. - Thêm toán tử sửa: với mỗi cạnh chưa phủ, chọn thêm đỉnh có bậc lớn hơn.
- Chạy trên đồ thị ngẫu nhiên 100 đỉnh, 300 cạnh. So với:
- Tham lam: lặp chọn đỉnh bậc lớn nhất.
- Xấp xỉ 2: lấy cả 2 đầu của một cặp ghép cực đại.
- Với đồ thị nhỏ (
n = 20), so với nghiệm tối ưu vét cạn.
Hình vuông 4 đỉnh, nghiệm 1010 -> 2 đỉnh, 0 cạnh hở, fitness = 2
✅ Tiêu chí hoàn thành
- Mọi toán tử ra hoán vị hợp lệ.
- Bảng toán tử trên berlin52 và kết quả memetic.
- Phủ đỉnh: bảng GA vs tham lam vs xấp xỉ 2, và so tối ưu ở
n = 20. - Giải thích vì sao lai cắt 1 điểm không dùng được cho hoán vị.
❓ Câu hỏi ôn tập
- Lai OX khác lai cắt đơn ở điểm gì?
- Đột biến giữ vai trò gì trong GA?
- Fitness cho TSP và phủ đỉnh tính thế nào?
- Khi nào GA hợp hơn SA và gradient?
🌕 Bạn đã hoàn thành ngày 122. Làm hết bài tập phía trên rồi sang ngày tiếp theo.