Tìm kiếm trong không gian trạng thái và thuật toán Simulated Annealing

Có thể giải thích như sau:

1. Việc chọn ra trạng thái y là một các ngẫu nhiên (Đối với bài toán Người bán hàng, trạng thái y chính là chi phí cho 1 tổ hợp bất kì được chọn ra từ A, ví dụ: A0 = {3,6,9,2,…n, n-3, n-9}, chi phí Obj = 100)

// Creates a random individual
public void generateIndividual() {
	// Loop through all our destination cities and add them to our tour
	for (int cityIndex = 0; cityIndex < TourManager.numberOfCities(); cityIndex++) {
		setCity(cityIndex, TourManager.getCity(cityIndex));
	}
	// Randomly reorder the tour
	Collections.shuffle(tour);
}

1. Việc tính  Δ(x,y) = Obj(y) – Obj(x) . Tại bước này ta so sánh trạng thái trước và trạng thái vừa sinh ra (Giả sử Obj(n+1) = 90, Obj(n) = 92. Vậy Δ(x,y) = 90 – 92 = 2 )
2. if Δ(x,y) < 0 then p = 1. Tại bước này, ta kiếm tra, nếu Δ(x,y) < 0 điều đó có nghĩa là trạng thái sau tốt hơn trạng thái trước. ta sẽ xét xác suất p = 1
3. Giả sử nếu Δ(x,y) > 0, thì điều đó có nghĩa là trạng thái sau tồi hơn trạng thái trước. Thì ta sẽ xét trạng thái p = exp(−Δ(x,y)/T). Tại bước này là bước quan trọng nhất, vì thay vì lựa chọn phương án tối ưu hơn, với thuật toán này sẵn sàng chọn một phương án tồi hơn, hoàn toàn phụ thuộc vào xác suất p được sinh ra. Tại sao lại vậy ? Vì nếu ta chỉ lựa chọn các phương án tối ưu hơn, đôi khi ta sẽ chỉ tìm được các trạng thái tối ưu cục bộ, mà bỏ qua trạng thái tối ưu toàn cục ( giống như việc tìm min, max trong bài toán giải đồ thị, điều kiện cần để một điểm m(x,y) là min hoặc max, thì điểm m phải là điểm cực trị, nhưng chưa chắc đó là điểm min, max). T là số lần lặp, exp(−Δ(x,y)/T) công thức này phụ thuộc vào T, tức là khi T càng nhỏ, thì p sẽ càng nhỏ và tiến tới 0, điều đó có nghĩa là khi bắt đầu chạy thuật toán, ta sẵn sàng lựa chọn các phương án ít tối ưu hơn, nhưng càng về cuối vòng lặp, ta sẽ hạn chế dần việc chọn các phương án tồi, vì khi đó các trạng thái tốt đã dần được tìm ra.

// Calculate the acceptance probability
public static double acceptanceProbability(int energy, int newEnergy, double temperature) {
	// If the new solution is better, accept it
	if (newEnergy < energy) {
		return 1.0;
	}
	// If the new solution is worse, calculate an acceptance probability
	return Math.exp((energy - newEnergy) / temperature);
}

1. if rand[0,1] < p then x ← y.  Ta sẽ random một số bất kỳ từ 0 -> 1, nếu số đó nhỏ hơn p thì ta sẽ lưu trạng thái mới đó
2. if Obj(x) < Obj(x*) then x* ← x.  Nếu trạng thái hiện tại tối ưu nhất thì ta sẽ lưu lại trạng thái đó.

// Keep track of the best solution found
if (currentSolution.getDistance() < best.getDistance()) {
	best = new Tour(currentSolution.getTour());
}

1. Giảm T

// Cool system
temp *= 1 - coolingRate;

Đặc điểm của thuật toán này luôn cho ta trạng thái tốt, mặc dù chưa phải trạng thái tốt nhất nhưng luôn là trạng thái có thể chấp nhận nếu T đủ lớn.