Simulated Annealing cho TSP mini – đường đi thăm tất cả điểm

Simulated Annealing (SA) là một kỹ thuật meta-heuristic mô phỏng quá trình “tôi luyện kim loại”: ban đầu hệ thống có “nhiệt độ” cao nên chấp nhận cả những bước đi tệ hơn (để thoát local minimum), sau đó dần “lạnh” xuống và trở nên tham lam hơn. Với TSP, ta có thể:

• Bắt đầu từ một tour ngẫu nhiên đi qua tất cả điểm.
• Mỗi bước: tạo một tour “hàng xóm” (neighbor), ví dụ bằng cách đảo ngược một đoạn (2-opt).
• Nếu tour mới ngắn hơn → nhận luôn.
• Nếu tour mới xấu hơn → đôi khi vẫn nhận với xác suất phụ thuộc vào độ xấu và nhiệt độ T.
• Giảm dần nhiệt độ T theo thời gian (cooling schedule).

Kết quả: ta thường thu được một đường đi khá tốt, nhất là với số điểm không quá lớn. Trong demo dưới đây, bạn có thể tự sinh điểm, cho thuật toán chạy và quan sát đường đi cùng độ dài tour thay đổi theo thời gian.

Demo Simulated Annealing cho TSP mini

Giải thích nhanh cấu trúc code

• cities: mảng các điểm 2D, mỗi điểm { x, y } là một “thành phố”.
• currentTour: thứ tự hiện tại đi qua các city, là một hoán vị các index 0..n-1.
• bestTour: tour tốt nhất tìm được từ đầu tới giờ (độ dài nhỏ nhất).
• currentDistance() và tourDistance(tour): hàm tính tổng độ dài đường đi (vòng kín).
• stepAnnealing():
  • Chọn ngẫu nhiên 2 vị trí trong tour và tạo hàng xóm bằng cách đảo đoạn (2-opt đơn giản).
  • Tính Δ = newDist - currentDist.
  • Nếu Δ < 0 → nhận tour mới. Nếu Δ > 0 → nhận với xác suất exp(-Δ / T).
  • Giảm nhiệt độ T = T * α.
• drawAll(): vẽ các city, đường đi hiện tại (current) và đường tốt nhất (best) lên canvas, kèm thông tin T, iteration, độ dài tour.
• Nút “Chạy 1 bước SA” gọi một lần stepAnnealing(); nút “Chạy liên tục” dùng requestAnimationFrame để lặp nhiều bước cho đến khi T < T_min hoặc người dùng dừng.