Thuật toán Simulated Annealing để tránh local minima

Trong các bài toán, ví dụ ta sử dụng k-means algorithm trong clusering, ta sẽ rất dễ bị local minima, dẫn đến thuật toán có thể converge nhưng không thể tìm ra giá trị tốt nhất.

Annealing xuất phát từ thuật ngữ là quá trình hình thành của pha lê (crystal formation process). Cụ thể, nhiệt độ sẽ giảm một cách rời rạc (không liên tục) trong một thời gian dài, quá trình này gọi là quá trình làm lạnh, quá trình được tiếp tục cho đến khi pha lê được hình thành tại một nhiệt độ T cố định.

Bình thường, ta biểu diễn local minima(minimum) như sau:

Giả sử ta đang từ từ phải sang trái và đang tiến đên local minima, rõ ràng, khi ta chạm đến điểm này, ta có thể dừng lại, nhưng global minima mới là điểm cho ta kết quả tốt nhất. Khi đó, làm sao ta biết ta nên đi tiếp lên từ điểm local minima  để đến global minima hay không.

Việc quyết định này được quyết định bởi một xác suất p:

Thuật toán SA với k-means được trình bày như sau:
1. Khởi tạo một giá trị T ngẫu nhiên và k clusters ngẫu nhiên.
2. Lặp lạo cho đến khi T chạm điểm cực tiểu
- Lặp n lần:
     + Ta xáo đổi các phần tử của các cluster một cách ngẫu nhiên
     + So sánh error của tập cluster mới và tập cluster cũ. Nếu tập cluster mới là tốt hơn, ta sẽ dùng tập       cluster mới với xác suất là p.
- Giảm giá trị của T [T = 0.9T]
3. Dừng thuật toán và trả về bộ clusters

Ở công thức tính p trên ta thấy, khi T lớn, xác suất p sẽ lớn, do đó xác suất chuyển sẽ lớn và ngược lại khi T nhỏ.