.png&blockId=04a8d577-ace8-4bac-bec8-3da8a3f63bbd)
@Hyun Ahn @7/4/2024
물리학에서 영감을 받은 최적화 기법으로 합금을 가열한 후 천천히 냉각시키면서 제련하는 과정(annealing)을 모사한 방법이다. 이는 지역 최적해에 빠지지 않고, 전역 최적해를 최대한 찾을 수 있게 한다. 제한된 시간과 자원으로 효율적으로 최적화하기 위한 방법이므로 메타휴리스틱(Metaheuristic) 기법에 속한다.
Simulated annealing을 비유할 때 가장 자주 언급되는 것이 합금을 제련하는 과정(annealing)이다. 처음에는 높은 온도를 가열해서 합금의 모양을 대폭적으로 변형시키고, 차츰 온도가 낮아지면서 합금을 세밀하게 변형시켜 최종적인 모양을 만들어낸다.
동작 과정
수용 확률(Acceptance Probability)Simulated annealing 이 해를 결정할 때는 다음의 두 가지 경우를 고려한다.
1.
기존 해보다 새로운 해가 더 좋은 경우 → 새로운 해를 선택
2.
기존 해보다 새로운 해가 더 나쁜 경우 → 수용 확률을 계산하여 새로운 해를 선택할 지를 결정
여기서 수용 확률은 새로운 해가 더 나쁜 경우에도 특정 확률에 따라 새로운 해로 이동하기 위한 개념으로 지역 최적해(local optima)에 빠지지 않기 위한 장치이다.
수식: 최적화 문제가 함수 최소화인 경우
•
: 현재 해의 목적 함수 값
•
: 새로운 해의 목적 함수 값
•
: 현재 온도
•
: 자연지수함수 = , : Euler number
수용 확률은 새로운 해가 기존 해보다 나쁜 경우에서 새로운 해를 선택할 지를 결정하기 때문에 함수 값이 음수인 구간에 적용된다. 온도 T가 높을수록 함수 값이 0에 가까우므로 높은 수용 확률을 기대할 수 있으며, T가 낮을수록 함수 값이 큰 음수를 가지므로 수용 확률 또한 낮아진다.
새로운 해에 대한 선택은 계산된 수용 확률 과 무작위 확률 값과 비교하여 가 더 큰 경우에 해당된다.
•
최적화 문제가 함수 최대화인 경우에는 수식에서가 아닌 로 적용하면 된다.
동작 방식•
높은 온도에서는 탐색을 더 넓게 하기 위해 더 나쁜 해도 수용할 확률이 크기 때문에 지역 최적해에 갇히지 않게 한다.
•
온도가 낮아질수록 더 나쁜 해를 수용할 확률이 감소하므로, 탐색 범위가 줄어들게 됨. 이는 최적해 근처에서 세밀한 탐색을 가능하게 한다.
Simulated annealing 기법을 외판원(TSP: Traveling Salesman Problem) 문제에 적용한 예 (Computational Scientist)
참고 자료
•
◦
Simulated Annealing 동작 과정에 대한 시각화
