Simulated Annealing
로컬 최적점을 피하기위해 사용하는 최적점 휴레스틱 알고리즘
주어진 시간에(자원에) 최선을 다한 글로발 최적점을 찾기위해 사용
(정획히 글로발 최적점을 찾기위해 모든 가능성을 계산하는게 아니라 주어진 자원만큼만 계산함)
컨셉 :철을 강화하기 위해 열을 높이고 식이는 담금질 기법에서 아이디어를 차용함
temp라는 온도 변수 높은 값에서 --> 낮은값으로
s (현재파라미터), s'(비교파라미터), E() 결과 함수
기본적으로 현재값 E(s)보다 비교값 E(s')이 작을때 비교파라미터 s' 을 현재 파라미터로 s 로 변경하나
로컬 최적점을 피하기 위해서 확률을 사용해 반대의 경우에도 변경하는경우가 있다(T가 높을때 반대의 경유로 변경하는일이 자주 발생)
동작방법
while temp > 0
if(E(s') < E(s)) prob = 1
else prob = exp(-(E(s')-E(s))/T)
if(random.float() < prob) s = s'
temp--;
return s
위 함수를 보면 temp 가 0이될때까지 계산한다(주어진 자산만큼)
E(s') < E(s) 이면 prob = 1
만약 비교 파라미터가 이전 파라미터보다 크면 무조건 비교 파라미터로 변경
그렇지 않다면 exp(-(E(s')-E(s))/T)
비교 값이 현재 값보다 작기 때문에 크기 때문에 -(E(s')-E(s)) 은 무조건 양수
최초 T 가 크면 exp(0)에가까워지고 확률은 1이 나올 가능 성이 높아진다.
(현재값보다 비교값이 크지만 로컬 옵티마를 피하기 위해 변경 하는 경우)
하지만 T 가 작아질수록 1에 비해 상대적으로 작은 값이 나올 확률이 점점 높아 진다
