Simulated Annealing

높은 온도에서 액체 상태인 물질이 온도가 점차 낮아지면서 결정체로 변하는 과정을 모방한 해 탐색 알고리즘

용융 상태에서는 물질의 분자가 자유로이 움직이는데 이를 모방하여 해를 탐색하는 과정도 특정한 패턴 없이 이루어짐

온도가 점점 낮아지면 분자의 움직임이 점점 줄어들어 결정체가 되는데, 해 탐색 과정도 이와 유사하게 점점 더 규칙적인 방식으로 이루어짐

이러한 방식으로 해를 탐색하려면, 후보해에 대해 이웃하는 해를 정의해야 한다.

<Pseudo-code>

임의의 후보해 s를 선택한다.
초기 T를 정한다.
repeat
	for i = 1 to kT {
		s의 이웃해 중에서 랜덤하게 하나의 해 S'를 선택한다.
		d = (s'의 값) - (s의 값)
		if (d < 0)
			s ← s'
		else
			q ← (0,1) 사이에서 랜덤하게 선택한 수
			if (q < p) s ← s'
	}
	T ← aT
until(종료 조건이 만족될 때까지)
return s

높은 T에서의 초기 탐색은 최솟값을 찾는데도 불구하고 확률 개념을 도입하여 현재 해의 이웃해 중에서 현재 해보다 ‘나쁜' 해로 이동하는 자유로움을 보인다.

그러나 점차 T가 낮아지면서 탐색 방향은 점점 아래로

즉, T가 낮아지면서 위 방향으로 이동하는 확률은 점차 작아짐

또 , 유전자 알고리즘은 여러 개의 후보해를 한 세대로 하여 탐색을 진행하지만 모의 담금질은 하나의 초기 해로부터 탐색이 진행된다는 것이 특징