- 1. TSP — Bài toán “đơn giản” nhưng không dễ
- 2. Genetic Algorithm — Khi máy tính “học” từ thiên nhiên
- Các thành phần cốt lõi của GA
- 3. Cách GA giải TSP — Từng bước một
- Bước 1: Khởi tạo quần thể
- Bước 2: Đánh giá Fitness
- Bước 3: Chọn lọc (Selection)
- Bước 4: Lai ghép (Crossover)
- Bước 5: Đột biến (Mutation)
- Bước 6: Thay thế và lặp lại
- 4. Demo trực quan: GA giải TSP ngay trên trình duyệt
- 5. Tại sao GA hiệu quả với TSP?
- Không gian tìm kiếm khổng lồ
- Khai thác thông tin từ nhiều nghiệm
- Tránh nghiệm cục bộ
- Song song hóa tự nhiên
- 6. Các biến thể và cải tiến của GA cho TSP
- 7. Giới hạn của GA và khi nào không nên dùng
- 8. Ứng dụng thực tế ngoài TSP
- 9. Kết luận
1. TSP — Bài toán “đơn giản” nhưng không dễ
Bài toán Traveling Salesman Problem (TSP) được phát biểu đơn giản: Tìm đường đi ngắn nhất để đi qua tất cả các thành phố, mỗi thành phố đúng một lần, rồi quay về điểm xuất phát.
Với 5 thành phố, bạn có 12 đường đi khả thi. Với 10 thành phố, con số là 181.440. Với 20 thành phố? 60 nghìn tỷ. Với 50 thành phố? Nhiều hơn số nguyên tử trong vũ trụ quan sát được.
Đây là lý do TSP thuộc lớp NP-hard. Không có thuật toán đa thức nào giải chính xác trong thời gian hợp lý. Và đây cũng là lý do Genetic Algorithm (GA) trở thành một lựa chọn hấp dẫn — nó không đảm bảo tối ưu toàn cục, nhưng nó tìm được lời giải đủ tốt trong thời gian đủ nhanh.
2. Genetic Algorithm — Khi máy tính “học” từ thiên nhiên
Charles Darwin đã chỉ ra: trong tự nhiên, những cá thể thích nghi tốt hơn có xu hướng sống sót và sinh sản, truyền lại đặc điểm tốt cho thế hệ sau. Qua hàng triệu năm, quá trình này tạo ra sự đa dạng và phức tạp đáng kinh ngạc của sự sống.
Genetic Algorithm mô phỏng quá trình này:
Các thành phần cốt lõi của GA
| Thuật ngữ tự nhiên | Thuật ngữ GA | Ý nghĩa trong TSP |
|---|---|---|
| Cá thể (Individual) | Nhiễm sắc thể (Chromosome) | Một chuỗi thứ tự các thành phố, ví dụ: [A, C, B, D, E] |
| Gen (Gene) | Gen | Một thành phố đơn lẻ trong chuỗi |
| Quần thể (Population) | Population | Tập hợp nhiều nhiễm sắc thể — nhiều đường đi khác nhau |
| Sức khỏe / Khả năng sinh tồn | Fitness | Tổng quãng đường — càng ngắn càng tốt |
| Sinh sản | Crossover (Lai ghép) | Kết hợp 2 đường đi để tạo đường đi mới |
| Đột biến | Mutation | Đổi chỗ ngẫu nhiên 2 thành phố trong đường đi |
| Chọn lọc tự nhiên | Selection | Ưu tiên giữ lại các đường đi ngắn hơn |
3. Cách GA giải TSP — Từng bước một
Bước 1: Khởi tạo quần thể
Tạo ngẫu nhiên một tập hợp các đường đi. Mỗi đường đi là một hoán vị của các thành phố. Ví dụ với 5 thành phố:
Chromosome 1: [A, B, C, D, E] → Distance: 45
Chromosome 2: [A, C, E, B, D] → Distance: 38
Chromosome 3: [A, D, B, E, C] → Distance: 52
Chromosome 4: [A, E, D, C, B] → Distance: 41
...Bước 2: Đánh giá Fitness
Tính tổng quãng đường của mỗi đường đi. Đường đi càng ngắn, fitness càng cao. Trong TSP, fitness thường được định nghĩa là nghịch đảo của tổng khoảng cách:
Fitness = 1 / TotalDistanceBước 3: Chọn lọc (Selection)
Chọn các cá thể “tốt” để làm cha mẹ cho thế hệ tiếp theo. Phương pháp phổ biến nhất là Tournament Selection: chọn ngẫu nhiên vài cá thể, lấy cá thể có fitness cao nhất.
Một phương pháp khác là Roulette Wheel Selection: xác suất được chọn tỉ lệ thuận với fitness. Đường đi ngắn hơn có “slice” lớn hơn trên “bánh xe roulette”.
Bước 4: Lai ghép (Crossover)
Lấy 2 đường đi (cha và mẹ), kết hợp để tạo đường đi mới (con). Trong TSP, crossover phải đảm bảo mỗi thành phố xuất hiện đúng một lần.
Ordered Crossover (OX) là phương pháp phổ biến:
- Chọn ngẫu nhiên một đoạn từ cha
- Sao chép đoạn này vào vị trí tương ứng của con
- Điền các thành phố còn lại theo thứ tự xuất hiện trong mẹ, bỏ qua các thành phố đã có
Cha: [A, B, C, D, E, F, G, H]
Mẹ: [C, A, E, B, F, D, H, G]
↑-----↑ (đoạn chọn: vị trí 2-4)
Con: [_, B, C, D, _, _, _, _] ← lấy từ cha
[C, A, E, B, F, D, H, G] ← mẹ (bỏ B, C, D đã có)
↓
Con: [A, B, C, D, E, F, G, H] ← điền E, F, G, H từ mẹ
Wait — để chính xác hơn:
Con: [E, B, C, D, F, A, G, H] ← E, F, A, G, H từ mẹ theo thứ tự, bỏ B, C, DBước 5: Đột biến (Mutation)
Để duy trì sự đa dạng và tránh bị “mắc kẹt” ở nghiệm cục bộ, GA đôi khi đổi chỗ ngẫu nhiên 2 thành phố trong một đường đi:
Trước: [A, B, C, D, E] → đổi chỗ C và E
Sau: [A, B, E, D, C]Tỷ lệ đột biến thường rất thấp (0.01 – 0.05) để tránh phá hủy những đường đi tốt đã được tìm thấy.
Bước 6: Thay thế và lặp lại
Thế hệ mới thay thế thế hệ cũ (hoặc một phần). Lặp lại từ Bước 2. Sau hàng trăm, hàng nghìn thế hệ, quần thể sẽ “tiến hóa” về phía các đường đi ngắn hơn.
4. Demo trực quan: GA giải TSP ngay trên trình duyệt
Hãy thử điều chỉnh các tham số và quan sát cách quần thể tiến hóa. Mỗi điểm là một thành phố, mỗi đường nối là một đường đi trong quần thể. Đường màu đỏ là đường đi tốt nhất hiện tại.
Thế hệ: 0
Khoảng cách tốt nhất: –
Đường đi tốt nhất: –
5. Tại sao GA hiệu quả với TSP?
Không gian tìm kiếm khổng lồ
Brute-force duyệt toàn bộ (n-1)!/2 đường đi là không khả thi. GA không duyệt tất cả — nó “lướt” qua không gian tìm kiếm theo hướng có lợi nhất, dựa trên nguyên tắc chọn lọc.
Khai thác thông tin từ nhiều nghiệm
Crossover cho phép kết hợp “đoạn đường tốt” từ nhiều lời giải khác nhau. Nếu đoạn [B, C, D] xuất hiện ở nhiều đường đi ngắn, GA sẽ ưu tiên giữ lại đoạn này.
Tránh nghiệm cục bộ
Mutation duy trì sự đa dạng gen, giúp quần thể không bị “mắc kẹt” ở một đường đi tốt cục bộ nhưng không phải tối ưu toàn cục.
Song song hóa tự nhiên
Mỗi nhiễm sắc thể trong quần thể có thể được đánh giá độc lập — GA rất dễ song song hóa trên GPU hoặc multi-core.
6. Các biến thể và cải tiến của GA cho TSP
| Kỹ thuật | Mô tả | Hiệu quả |
|---|---|---|
| 2-Opt Local Search | Sau mỗi thế hệ, áp dụng 2-opt (đảo ngược một đoạn đường) để cải thiện nghiệm ngay lập tức | Giảm 20-40% khoảng cách, tăng thời gian tính toán |
| Elitism | Luôn giữ lại cá thể tốt nhất của thế hệ trước, không để nó bị mất do crossover ngẫu nhiên | Đảm bảo fitness không giảm theo thời gian |
| Adaptive Mutation | Tăng tỷ lệ đột biến khi quần thể “hội tụ” quá nhanh (đa dạng gen thấp) | Tránh premature convergence |
| Island Model | Chia quần thể thành nhiều “đảo” nhỏ, mỗi đảo tiến hóa độc lập, thỉnh thoảng trao đổi cá thể | Duy trì đa dạng, khám phá nhiều vùng không gian |
| Hybrid GA + Simulated Annealing | Kết hợp GA (tìm kiếm toàn cục) với SA (tìm kiếm cục bộ tinh vi) | Chất lượng nghiệm cao nhất, nhưng phức tạp |
7. Giới hạn của GA và khi nào không nên dùng
GA không phải “thần dược”:
- Không đảm bảo tối ưu toàn cục — chỉ đảm bảo “đủ tốt” trong thời gian hợp lý.
- Cần tuning tham số — tỷ lệ crossover, mutation, kích thước quần thể ảnh hưởng lớn đến kết quả.
- Chậm hơn thuật toán chuyên biệt — với TSP, Lin-Kernighan hoặc Concorde TSP Solver thường cho kết quả tốt hơn GA cho instance nhỏ và trung bình.
- Khó debug — quá trình tiến hóa là ngẫu nhiên, khó tái tạo lỗi.
Tuy nhiên, GA vẫn là lựa chọn tuyệt vời khi:
- Bài toán có không gian tìm kiếm khổng lồ và không có cấu trúc đặc biệt để khai thác.
- Bạn cần lời giải “tốt” nhanh hơn là lời giải “tối ưu” chậm.
- Bài toán có nhiều ràng buộc phức tạp (multi-objective optimization).
- Bạn muốn một framework tổng quát áp dụng cho nhiều loại bài toán khác nhau.
8. Ứng dụng thực tế ngoài TSP
GA không chỉ giải TSP. Nó được dùng rộng rãi trong:
- Lập lịch (Scheduling): Lịch bay, lịch sản xuất, lịch thi đấu
- Tối ưu hóa mạng: Routing trong mạng viễn thông, placement của data center
- Thiết kế kỹ thuật: Tối ưu hình dạng cánh máy bay, cấu trúc khung xe
- Machine Learning: Tối ưu kiến trúc neural network (Neuroevolution), tối ưu hyperparameters
- Game AI: Tiến hóa hành vi NPC, tối ưu chiến lược trong game chiến thuật
- Sinh học tính toán: Protein folding, drug discovery
9. Kết luận
Genetic Algorithm là một minh chứng đẹp đẽ cho sức mạnh của “bio-inspired computing”. Bằng cách mô phỏng quá trình chọn lọc tự nhiên — chọn lọc, lai ghép, đột biến — GA có thể “tiến hóa” ra những lời giải ấn tượng cho những bài toán mà con người không thể giải bằng cách duyệt toàn bộ.
Với TSP, GA không phải thuật toán tốt nhất, nhưng nó là một trong những cách tiếp cận dễ hiểu nhất, trực quan nhất, và dễ mở rộng nhất. Bạn có thể thêm ràng buộc, thay đổi hàm fitness, hoặc kết hợp với các kỹ thuật khác — tất cả đều nằm trong cùng một framework duy nhất.
Hãy thử điều chỉnh demo ở trên: tăng số thành phố, giảm tỷ lệ đột biến, hoặc chạy chậm hơn để quan sát từng thế hệ. Bạn sẽ thấy quần thể ban đầu hỗn loạn dần dần “tự tổ chức” thành những đường đi gọn gàng — đó chính là tiến hóa đang diễn ra trước mắt bạn.
Tham khảo: Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning.
Bình luận