시뮬레이티드 어닐링(Simulated Annealing)

시뮬레이티드 어닐링은 자연에서 영감을 받은 전역 최적화 기법으로, 메타휴리스틱을 통해 (주로 이산적인) 넓은 탐색 공간에서 전역 최댓값을 근사적으로 찾는 방법이다. 이 이름은 금속 공학에서의 어닐링(annealing) 과정에서 유래했는데, 이는 재료를 가열한 후 제어된 조건 하에 서서히 냉각시켜 강도와 내구성을 향상시키는 과정을 말한다. 이 알고리즘의 목표는 열역학 시스템의 특성을 활용해 탐색 공간에서 최소 비용 해를 찾는 것이다.

일반적으로 지역 최댓값에 갇히는 언덕 오르기(hill climbing) 기법과 달리, 시뮬레이티드 어닐링은 지역 최댓값을 탈출할 수 있다. 이 알고리즘의 흥미로운 특성은 높은 온도에서는 하향 이동을 허용할 확률이 높고, 서서히 냉각되면서 이 확률이 점차 감소한다는 점이다. 즉, 높은 온도에서는 탐색 공간에 대한 수용 기준이 느슨해져 알고리즘의 수용 함수가 초기/고온 단계에서 혼돈스러운 행동을 보이며, 이로 인해 지역 최댓값에서 벗어날 가능성이 높아진다. 반면, 낮은 온도에서는 수용 기준이 좁혀지며 개선에 집중한다.

의사코드

Input: initial, temperature, coolingRate, acceptance
Output: Sbest
Scurrent <- CreateInitialSolution(initial)
Sbest <- Scurrent
while temperature is not minimum:
	Snew <- FindNewSolution(Scurrent)
	if acceptance(Energy(Scurrent), Energy(Snew), temperature) > Rand():
		Scurrent = Snew
	if Energy(Scurrent) < Energy(Sbest):
		Sbest = Scurrent
	temperature = temperature * (1-coolingRate)

일반적인 수용 기준

P(accept) <- exp((e-ne)/T) where 
	e는 현재 에너지(현재 해), 
	ne는 새로운 에너지(새로운 해),
	T는 현재 온도.

이 알고리즘을 사용해 20개 도시로 구성된 외판원 문제(Travelling Salesman Problem) 인스턴스를 해결한다. 코드는 simann_example.swift에 있다.

시뮬레이티드 어닐링(Simulated Annealing)

의사코드

일반적인 수용 기준

관련 자료