[Meta-huristics] Simulated Annealing : 담금질 기법

• 최적해를 구하는 알고리즘 중 하나인 Simulated Annealing(SA)는 제련 과정을 모방한 알고리즘이며, 일정 확률로 좋지 않은 선택지를 선택함으로써 Local Optimum에서 벗어나 Global Optimum을 찾아가는 방식을 사용한다.

• SA는 Meta-heuristics 알고리즘의 일종으로, 이는 범용적인 알고리즘으로 다양한 최적경로 찾는 문제에 적용 가능하며, 시간이 지날수록 정확도가 높아진다.

• 담금질 기법(Simulated Annealing, SA)은 최적화 문제를 해결하는 알고리즘으로, 공이 아래로만 내려가는 것이 아니라 특정 확률로 위로 올라가는 방식을 사용한다. 이때 확률을 정하는 방법은 볼트만 상수를 활용하며, 초반에는 확률을 높여주고 후반으로 갈수록 확률을 낮춰주는 것이 효과적이다.

• SA 알고리즘의 장점은 일반적인 Local Optimum보다 좋은 값을 구할 수 있고, 다양한 분야에서 활용이 가능하다는 점이다. 단점은 시간이 매우 오래 걸린다는 점이다. 따라서 적절한 상황에 맞춰서 사용하는 것이 중요하다.