[휴리스틱 알고리즘] 시뮬레이티드 어닐링(Simulated Annealing)에 관하여 1탄
in Data on Optimization
시뮬레이티드 어닐링에 대해서 조금씩 알아가 본다.
시뮬레이티드 어닐링(Simulated Annealing)
시뮬레이티드 어닐링은 국소 탐색 방법을 개선한 방법이다. 방법론을 짧게 말하면,
국소 탐색 방법
(1) 초기해를 만든다.
(2) 현재의 해를 랜덤하게 변화시킨다.
(3) 새로운 해가 원래의 해보다 더 좋다면 바꾸고, 그렇지 않으면 무시한다.
(4) 2~3의 과정을 적당히 반복한다.SA
(1) 초기해를 만든다.
(2) 현재의 해를 랜덤하게 변화시킨다.
(3) 새로운 해가 원래의 해보다 더 좋다면 바꾸고, 그렇지 않으면 일정한 확률로 바꾼다.
(4) 2~3의 과정을 적당히 반복한다.
국소 탐색 방법과 SA가 다른점은 3번이 다르다. 좋지 못한 해로의 수락도 어느정도의 확률로 허락한다.
Q. 그렇다면 그 확률을 어떻게 계산할까?
A. SA에는 “온도”라는 개념이 있다. 이 온도가 없다면 갈팡질팡 하면서 최적해를 찾지 못할 것이다.
Q. 그렇다면 SA의 뜻을 알아보자.
A. Simulated 가상의, Annealing 담금질(풀림)
담금질(풀림)에 대해 간단 설명을 하자면, 금속을 달군 뒤, 냉각을 하게됨.
그런데 어떤 조건하에서 금속을 냉각 시키는 가에 따라 금속 성질이 크게 변함.
온도가 높을때는 원소들이 활발하게 움직이지만, 온도가 안정을 찾으면 금속의 결정 상태도 고르게 됨. 이것을 SA가 흉내냄.
다른 좋은 예로 1.5리터 패트병에 자갈과 콩, 모래를 넣는다. 그리고 우리의 목표는 패트병 안에 부피를 최소화 하려고한다.
그러면 우리는 처음에는 힘을 크게줘서 모래들이 자갈과 콩 사이로 잘 들어가게 하고 점점 약하게 한다.
다시 말해 SA에서는 처음에는 나쁜 해로의 이동을 큰확률로 주고, 점점 그 확률을 줄인다.
결국 이 것이 온도의 개념이다.
맨 처음에 온도가 적절히 주어지면 이 온도를 조금씩 줄여나가서 0이 되도록한다.
이렇게 온도가 0이 되면 SA는 끝나게된다.
온도가 높을때에는 나쁜해로의 허락 확률이 크고, 온도가 낮을 때에는 허락 확률이 낮다.
