SA(Simulated Annealing) 알고리즘

본 포스팅에서는 SA(Simaulated Annelaing)알고리즘에 대해설명드리도록 하겠습니다. SA알고리즘은 전역 최적화 문제에 대한 확률론적 메타휴리스틱 알고리즘 입니다. Simaulated Annelaing알고리즘은 금속공학에서의 담금질 기법인 annelaing에서 아이디어를 얻었습니다, 즉 뜨거운 욕조에서의 재료의 냉각 과정에서 아이디어를 얻었다고 볼수있습니다. 먼저 Annelaing은 다음과 같은 의미를 지닙니다.

• 내부강도를 제거하기 위해 금속이나 유리를 가열하고 천천히 냉각시키는 방법.
• 금속재료를 가열한 다음 조금씩 냉각해 결정을 성장시켜 그 결함을 줄이는 작업.
• 열에 의해서 원자는 초기의 위치(내부 에너지가 극소점에 머무르는 상태)로부터 멀어져 에너지가 더욱 높은 상태로 추이됩니다.
• 천천히 냉각함으로써 원자는 초기 상태보다 내부 에너지가 한층 더 극소인 상태를 얻을 가능성이 많아집니다.

흔히 철을 담금질 할때, 온도가 높아진 철은 붉은 색으로 변하게되며, 약한 충격에도 변형이 잘됩니다. 또한 온도가 내려갈수록 철의 본 색을 띄우게되며 만들고자하는 형태에 가까워집니다. Simaulated Annelaing알고리즘은 이와 같은 방법으로 높은 온도로 부터 시작해서 점차 그온도를 떨어뜨리며 최적의 해를 찾는 방법으로 볼 수 있습니다.

 

SA 알고리즘의 경우 다음과 같이 작동합니다.

1. 초기해를 만듭니다.
2.  현재의 해를 랜덤하게 변화 시킵니다.
3. 새로운 해가 원래의 해보다 더 좋으면 바꿉니다.
4. 새로운 해가 원래의 해보다 조금 나쁘고(delta) 랜덤하게 생성한 0-1 사이의 수가 acceptance probabilty 보다 적으면 나쁜해로 바꿉니다. 처음에는 나쁜 해로의 이동을 높은 확률로 허가하고 점차 그 확률을 낮춥니다(difference/temperature).
5. 2~4의 과정을 반복합니다.

즉, 온도가 낮아지면서 global minimum에 근접한 곳에 자리잡게 되고 global minimum에 정착게 됩니다. 이제 SA알고리즘의 Pesudo code에 대해 살펴보도록 하겠습니다.