Simulated Annealing: đôi khi phải đi lùi để đi xa hơn

Hill Climbing có một quy tắc rất cứng: chỉ đi sang trạng thái tốt hơn.

Quy tắc này nghe hợp lý, nhưng lại gây ra một vấn đề: nếu muốn thoát khỏi local optimum, đôi khi ta phải chấp nhận một bước xấu hơn trước khi tới được vùng tốt hơn.

Hãy nghĩ về cảnh này: bạn đang tìm lối thoát trong một mê cung. Nếu chỉ đi về phía “gần đích hơn”, bạn có thể bị kẹt ở hành lang cụt. Đôi khi cần lùi lại một bước để tìm nhánh khác dẫn ra ngoài. Simulated Annealing làm đúng điều đó — nhưng không lùi bừa bãi, mà lùi có tính toán.

1. Ý tưởng từ quá trình ủ nhiệt

Trong luyện kim, để tạo thép chất lượng cao, người ta nung nóng kim loại rồi làm nguội từ từ. Khi nhiệt độ cao, các nguyên tử có nhiều năng lượng và có thể tự sắp xếp lại mạnh mẽ. Khi nguội dần, chúng dần ổn định ở cấu hình năng lượng thấp hơn.

Nếu làm nguội quá nhanh (tôi thép): vật liệu cứng nhưng giòn — bị kẹt ở cấu hình không tối ưu.
Nếu làm nguội đúng cách (ủ nhiệt): vật liệu đạt cấu trúc tinh thể tốt hơn — global optimum trong vật lý.

Kirkpatrick, Gelatt và Vecchi (1983) nhận ra rằng bài toán tối ưu tổ hợp có cấu trúc tương tự, và dùng phép tương tự này để xây dựng thuật toán:

Nhiệt độ cao = cho phép thử nghiệm mạnh, kể cả chấp nhận bước xấu hơn.
Nhiệt độ thấp = trở nên cẩn thận, chủ yếu giữ các bước cải thiện.

2. Quy tắc chấp nhận

Giả sử ta đang cực tiểu hóa chi phí. Đặt:

\Delta = \text{cost}(new) - \text{cost}(current)

Nếu $\Delta < 0$ : trạng thái mới tốt hơn → luôn chấp nhận.
Nếu $\Delta > 0$ : trạng thái mới xấu hơn → chấp nhận với xác suất:

P(\mathrm{accept}) = e^{-\Delta / T}

Trong đó $T$ là nhiệt độ hiện tại.

Cơ chế này có nguồn gốc từ phân phối Boltzmann trong vật lý thống kê: ở nhiệt độ $T$ , xác suất hệ thống ở trạng thái có năng lượng $E$ tỉ lệ với $e^{-E/k_BT}$ . SA mô phỏng quá trình này để “lấy mẫu” từ không gian nghiệm.

3. Công thức nói lên điều gì?

Biểu đồ dưới so sánh xác suất chấp nhận cùng một bước xấu ( $\Delta = 5$ ) tại chín mức nhiệt độ khác nhau, từ rất thấp đến rất cao:

Nhiệt độ T	Xác suất P	Hành vi
0.5	≈ 0.000	Từ chối tuyệt đối → như Hill Climbing
2	≈ 0.082	Hiếm khi chấp nhận bước xấu
10	≈ 0.607	Thường chấp nhận
50	≈ 0.905	Gần như luôn chấp nhận
200	≈ 0.975	Khám phá ngẫu nhiên gần như hoàn toàn

Cùng một bước xấu ( $\Delta = 5$ ), nhưng khi $T$ cao → thuật toán chấp nhận tự do; khi $T$ thấp → thuật toán từ chối.

Điều thú vị: nếu $\Delta$ lớn hơn (bước tệ hơn), xác suất chấp nhận giảm mạnh hơn ở cùng $T$ . SA không chấp nhận bước xấu bừa bãi — nó ưu tiên các bước “hơi xấu một chút” hơn là “xấu rất nhiều”.

Ví dụ tại $T = 10$ :

$\Delta = 2$ : $P = e^{-0.2} \approx 0.82$ (hay chấp nhận)
$\Delta = 5$ : $P = e^{-0.5} \approx 0.61$
$\Delta = 15$ : $P = e^{-1.5} \approx 0.22$ (hiếm khi chấp nhận)

Nếu đổi sang ví dụ giao hàng: tuyến hiện tại dài 6.2 km, tuyến mới dài 6.7 km, vậy $\Delta = 0.5$ km.

Nhiệt độ	Xác suất nhận tuyến dài hơn 0.5 km	Diễn giải
$T=2$	$e^{-0.25} \approx 0.78$	Đầu quá trình: vẫn thử nhiều hướng
$T=0.5$	$e^{-1} \approx 0.37$	Đã chọn lọc hơn
$T=0.1$	$e^{-5} \approx 0.007$	Gần cuối: gần như không nhận bước xấu

Vì vậy SA không “đi lùi cho vui”: cùng một bước xấu có thể được nhận ở đầu quá trình, nhưng bị từ chối ở cuối quá trình.

4. Pseudocode

current = trạng thái ban đầu
best = current  # giữ nghiệm tốt nhất từng thấy

for t = 1 ... max_steps:
    T = temperature(t)          # nhiệt độ giảm dần
    neighbor = random_neighbor(current)

    delta = cost(neighbor) - cost(current)

    nếu delta < 0:              # tốt hơn → nhận ngay
        current = neighbor
    ngược lại:                  # xấu hơn → nhận với xác suất
        if random() < exp(-delta / T):
            current = neighbor

    if cost(current) < cost(best):
        best = current          # cập nhật nghiệm tốt nhất

return best  # trả về nghiệm TỐT NHẤT đã thấy, không phải cuối cùng

Lưu ý: trả về best (nghiệm tốt nhất từng gặp) thay vì current (trạng thái cuối). SA có thể di chuyển xấu đi ở các bước cuối — cần giữ lại best trên suốt quá trình.

5. SA so với Hill Climbing trên cùng bài toán

Biểu đồ dưới so sánh chi phí của SA và Hill Climbing theo thời gian trên cùng một bài toán có nhiều local optimum:

Hill Climbing: giảm nhanh rồi kẹt tại 18.
Simulated Annealing: đôi khi đi ngược lên (bước 15, 30, 40, 70) — đây là lúc SA chấp nhận bước xấu. Nhưng nhờ các bước đó, SA thoát được các thung lũng cục bộ và tìm được chi phí 9.

Những lúc đường SA đi lên chính là cơ chế thoát local optimum.

6. Cooling schedule — giảm nhiệt như thế nào?

Một lịch giảm nhiệt phổ biến:

T_t = T_0 \cdot \alpha^t, \qquad 0 < \alpha < 1

Với $T_0 = 100$ và $\alpha = 0.95$ , biểu đồ dưới cho thấy nhiệt độ qua 12 mốc thời gian:

Bước 0–20: nhiệt độ còn cao (36–100), SA khám phá tự do, sẵn sàng chấp nhận bước xấu.
Bước 30–50: nhiệt độ xuống 8–21, SA trở nên chọn lọc hơn.
Bước 80–100: nhiệt độ ≈ 1–2, hành vi gần như Hill Climbing.

Chọn $T_0$ và $\alpha$ như thế nào?

Vấn đề	Triệu chứng	Điều chỉnh
$T_0$ quá thấp	Thuật toán gần như Hill Climbing ngay từ đầu	Tăng $T_0$
$T_0$ quá cao	Lãng phí bước đầu trong vùng ngẫu nhiên hoàn toàn	Giảm $T_0$
$\alpha$ quá nhỏ (làm nguội nhanh)	Sớm kẹt local optimum	Tăng $\alpha$ lên gần 1
$\alpha$ quá lớn (làm nguội chậm)	Kết quả tốt hơn nhưng chạy rất lâu	Giảm $\alpha$ hoặc giảm max_steps

Không có giá trị tốt nhất cho mọi bài toán — cần thử nghiệm.

7. Ví dụ thực tế: tuyến giao hàng

Giả sử một shipper phải ghé 20 địa điểm. Một trạng thái là thứ tự ghé thăm. Một láng giềng được tạo bằng cách đổi vị trí hai địa điểm bất kỳ (2-opt swap).

Tại sao cho phép tuyến 12.7 km? Vì đôi khi tuyến ngắn nhất địa phương (12.4 km) là dead end — các hoán đổi tiếp từ đó chỉ làm tuyến dài hơn. Nhận một bước xấu nhỏ (+0.3 km) có thể mở ra chuỗi cải thiện dẫn đến tuyến 11.2 km.

Ứng dụng lịch sử: bài báo Kirkpatrick, Gelatt và Vecchi dùng phép tương tự ủ nhiệt để xử lý các bài toán tối ưu tổ hợp lớn, trong đó có placement/layout. Đây là một lý do SA thường được giới thiệu cùng các ví dụ routing, lập lịch và bố trí linh kiện.

8. Cài đặt với Python

import math
import random

def simulated_annealing(
    initial_state,
    get_random_neighbor,
    cost_fn,
    T0=100.0,
    alpha=0.95,
    max_steps=10_000,
):
    """
    Simulated Annealing: local search có thể chấp nhận bước xấu.
    
    Args:
        T0: nhiệt độ ban đầu
        alpha: tốc độ làm nguội (gần 1 = làm nguội chậm)
        max_steps: tổng số bước
    """
    current = initial_state
    current_cost = cost_fn(current)
    best = current
    best_cost = current_cost

    T = T0

    for step in range(max_steps):
        T = T0 * (alpha ** step)        # giảm nhiệt theo hàm mũ
        if T < 1e-10:
            break                        # nhiệt độ gần 0, dừng sớm

        neighbor = get_random_neighbor(current)
        neighbor_cost = cost_fn(neighbor)
        delta = neighbor_cost - current_cost

        if delta < 0:                    # tốt hơn → nhận
            current = neighbor
            current_cost = neighbor_cost
        elif random.random() < math.exp(-delta / T):   # xấu hơn → nhận theo xác suất
            current = neighbor
            current_cost = neighbor_cost

        if current_cost < best_cost:     # cập nhật best
            best = current
            best_cost = current_cost

    return best, best_cost

9. So sánh với Hill Climbing

Tiêu chí	Hill Climbing	Simulated Annealing
Chấp nhận bước tốt hơn	✅	✅
Chấp nhận bước xấu hơn	❌	✅ xác suất theo T
Thoát local optimum	❌ (không)	✅ (có thể)
Số tham số cần tuning	Ít (chỉ max_steps)	Nhiều (T₀, α, max_steps)
Kết quả ổn định	Phụ thuộc điểm đầu	Có tính ngẫu nhiên rõ
Thời gian chạy	Nhanh	Chậm hơn nếu max_steps lớn
Bảo đảm global optimum	❌	❌ (nhưng lý thuyết: có với cooling log)

Với cooling schedule logarithmic ( $T_t = c / \ln(1+t)$ ), SA được chứng minh hội tụ về global optimum theo xác suất — nhưng thực tế quá chậm để dùng. Cooling hàm mũ (như trên) là thực dụng và thường cho kết quả tốt trong thực tế.

10. Khi nào nên dùng SA?

SA phù hợp khi:

Không gian rời rạc rất lớn, có nhiều local optimum.
Có thể tính chi phí nhanh.
Có thể định nghĩa neighborhood hợp lý.
Không yêu cầu chứng minh nghiệm tối ưu tuyệt đối.

Nó thường xuất hiện trong:

Lập lịch, routing, placement.
Thiết kế mạch (VLSI).
Tối ưu tổ hợp trong logistics.

SA không phải luôn tốt hơn Hill Climbing với Random Restart. Nếu không gian không có quá nhiều local optimum, Random Restart có thể đủ và đơn giản hơn.

11. Một lưu ý quan trọng về đánh giá

Vì SA có ngẫu nhiên, một lần chạy không đủ để kết luận. Cần chạy nhiều lần với seed khác nhau và báo cáo:

Best cost (chạy tốt nhất).
Mean ± Std (ổn định hay biến động).
Runtime (wall clock).

Khi so sánh với thuật toán khác, dùng cùng dữ liệu và cùng ngân sách tính toán (số bước hoặc thời gian giới hạn).

12. Câu hỏi tự kiểm tra

Tại sao SA không trả về current mà trả về best đã theo dõi trong suốt quá trình?
Khi $T$ giảm, thuật toán thay đổi hành vi như thế nào?
Biểu đồ SA vs HC cho thấy SA đi lên ở một số bước. Có phải đây là lỗi không?
Nếu đặt $\alpha = 0.99$ thay vì $\alpha = 0.95$ , SA sẽ hành xử khác thế nào?
Vì sao SA hữu ích cho VLSI placement hơn là dùng LP hay CSP?

Tài liệu tham khảo

S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi. “Optimization by Simulated Annealing.” Science, 220(4598), 1983, 671-680. https://doi.org/10.1126/science.220.4598.671
Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach, 4th ed., Chapter 4: https://aima.cs.berkeley.edu/
CS50 AI, Lecture 3 - Optimization: https://cs50.harvard.edu/ai/notes/3/
Emile Aarts, Jan Korst. Simulated Annealing and Boltzmann Machines. Wiley, 1989.
Artin Kavoosi. “Simulated Annealing” visual note: https://akavosi.github.io/blog/posts/simulated-annealing.html

Bản tiếng Anh đang soạn.