Simulated annealing: leo lên để xuống đáy

Giới thiệu

Bài này học thỉnh thoảng chịu xấu để thoát đáy nông. Dùng để tìm tour và tranh vẽ khi nhiều đáy lừa.

Kiến thức cần nhớ

Ý tưởng ủ nhiệt

• Định nghĩa: tốt hơn nhận ngay, xấu hơn nhận theo nhiệt.
• Đầu nóng thì leo thoải mái để khám phá xa.
• Cuối nguội thì chỉ đi xuống để chốt đáy sâu.
• Ví dụ đời thường: như nung sắt nóng rồi nguội dần.
• Đôi khi phải leo lên mới xuống được đáy thật.

Chuyển ngắn và dài

• Ngắn: đổi 2 thành phố kề, tinh chỉnh kỹ vùng gần.
• Dài: đảo cả đoạn lớn, thoát xa nhưng dễ phá.
• Ví dụ đời thường: như nhích ghế và bê cả bàn đi.
• Lúc nóng dùng dài để khám, lúc nguội dùng ngắn.
• Luôn ghi nghiệm tốt nhất riêng vì đường đi leo lên.

So với gradient

• Gradient cần trơn có đạo hàm, đi tham nên nhanh.
• Ủ nhiệt không cần đạo hàm, đi được rời rạc.
• Ví dụ đời thường: như xe đua và xe địa hình leo đồi.
• Gradient kẹt đáy gần, ủ nhiệt thoát tốt hơn.
• Thực tế ủ tìm vùng rồi giao leo đồi chốt.

Ví dụ

• Input: nguội ngay từ đầu và kẹt đáy đầu -> Output: tăng nhiệt đầu.
• Giải thích: thiếu thăm dò nên giống leo tham thuần túy.

# Nhận nghiệm xấu theo nhiệt độ
if tot_hon or random() < exp(-(xau - tot) / T):
    hien_tai = moi  # thỉnh thoảng leo lên
T *= 0.95  # nguội dần

💻 Bài tập

Ngôn ngữ: Python 3 (hoặc C++). Nộp vào day-113/.

Bài 1: Khung simulated annealing tổng quát

def anneal(init, cost, neighbor, T0: float, alpha: float, steps_per_T: int, T_min: float,
           seed=0) -> tuple[object, float, list[tuple[float, float, float]]]:
    """Nhận nghiệm mới nếu tốt hơn, hoặc với xác suất exp(-(delta) / T).
       Giữ riêng nghiệm tốt nhất. Làm nguội T *= alpha.
       Trả (best, best_cost, lịch sử (T, current_cost, best_cost))."""

Thử trên hàm 1 biến nhiều đáy f(x) = x^2 + 10 sin(3x) trong [-10, 10], láng giềng là x + N(0, 1).

Hill climbing (T0 = 0) từ x = 8 -> kẹt đáy địa phương
SA với T0 = 50 từ x = 8          -> tìm đáy toàn cục (so với quét lưới 10^6 điểm)

Bài 2: Lịch nhiệt độ

1. So 3 lịch nguội: hình học T *= alpha, tuyến tính T -= c, logarit T0 / log(1 + k).
2. Chạy mỗi lịch 50 lần. In cost tốt nhất trung bình và độ lệch chuẩn.
3. Vẽ current_cost và best_cost theo bước cho 1 lần chạy. Chỉ ra đoạn leo lên.
4. Chọn T0 bằng cách lấy mẫu 100 bước ngẫu nhiên và đặt T0 sao cho xác suất nhận bước xấu trung bình là 0.8.

Bài 3: Bài toán rời rạc (nâng cao)

Bài toán xếp N quân hậu (N = 50): nghiệm là hoán vị, cost là số cặp hậu ăn nhau theo đường chéo.

1. Láng giềng: đổi chỗ 2 cột.
2. Tính delta trong $O(1)$ nhờ đếm số hậu trên mỗi đường chéo, không tính lại toàn bộ.
3. In số bước tới cost 0 cho N = 50, 100, 500.

✅ Tiêu chí hoàn thành

• SA thoát đáy địa phương mà hill climbing kẹt.
• Bảng 3 lịch nguội có số thật và hình quỹ đạo cost.
• N-queens N = 500 giải được, delta $O(1)$.
• Giải thích được vì sao phải leo lên mới xuống được đáy sâu.

❓ Câu hỏi ôn tập

• Nhiệt cao thì nhận xấu thế nào?
• Chuyển ngắn khác dài sao?
• Vì sao ghi tốt nhất riêng?
• Ủ hơn gradient ở đâu?

🌕 Bạn đã hoàn thành ngày 113. Làm hết bài tập phía trên rồi sang ngày tiếp theo.