시뮬레이티드 어닐링의 전체적인 맥락을 요약해 보려한다.

---

시뮬레이티드 어닐링의 구조

• 초기화 단계 : 초기온도, 초기해, 초기반복수(온도가 평행에 도달할때까지 반복수) 등을 설정
• 외부루프 : 이웃 목적함수(새로운 챔피언) < 현재 목적함수(현 챔피언) 이면 이웃->현재 업데이트
• 내부루프 : 이를 초기반복수만큼 반복
• 핵심 : 수락확률(acceptance probability)과 냉각 스케줄(cooling schedule)의 선택.
  • 수락확률 : 개선되지 않은 이웃해로의 이동을 가능하게 함
  • 냉각 스케줄 : 알고리즘을 반복할때마다 온도를 적절하게 낮추는 방법을 말함

수락기준

요약 : 더 좋은 해가 나오면 채택하지만, 확률적으로 가끔은 더 나쁜해도 골라봐.

냉각 스케줄

요약 : 온도가 처음에는 높았으나 점점 작아지게. 온도가 0이면 수락 확률이 0이 되게끔 만듦

• 주의할점 : 해의 성능에 큰 영향을 미치는데 적절한 냉각 스케줄을 선택하지 않으면 좋은 해를 구하기 어려움.
• 냉각 스케줄 종류 : 선형(linear) 스케줄, 기하(geometric) 스케줄, 로그(logarithmic) 스케줄 등 있음

내부루프 반복수

요약 : 내부루프는 평형 상태까지의 반복

• 온도 하락폭이 크면 반복수가 많아지고, 하락폭이 작으면 쉽게 평형상태를 이룸
• 계산소요시간이 길어지면 해의 품질이 향상되는데, 해의 향상을 얻을 때 내부루프의 반복수를 증가시키는 것보다 온도의 하락 폭을 줄이는 것이 좋음
• 매 온도에서 평형상태에 도달하는데 요구되는 반복수는 문제의 크기에 따라 지수적으로 증가함
• 적절한 내부루프의 반복수를 결정 방법
  • 첫째, 일반적인 방법으로 해의 크기에 일정한 상수를 곱하여 내부루프의 반복수가 일정하게 유지되는 정적(static) 방법
  • 둘째, 내부루프의 반복수가 상황에 따라 변하는 정응적 방법(adaptive method)로 해의 평균값이 빨리 떨어지는 온도에서는 더 머물게 하는 개념을 사용하는 것

종료 조건

요약 : 종료조건은 (1)온도 T를 0.01로 설정하거나 (2)일정 카운터까지 더 좋은 해가 발견되지않으면 종료

• 시뮬레이티드 어닐링의 종료 조건(terminal condition)은 온도가 0에 도달할 때 멈추는 것
  • 첫째, 종료 조건의 온도 T를 0.01로 설정
  • 둘째, 지금까지 발견한 가장 좋은 해가 개선되지 않으면 종료하는 것 그리고 수락확률이 일정 수준 이하로 떨어진 후에 해의 향상 여부에 따라 종료시점을 결정 (온도가 떨어지면 수락확률이 0에 수렴되기 때문에 종료 조건의 온도까지 매우 오랜 시간이 걸리기 때문에 한계치 아래로 내려가면 카운터를 시작하여 일정한 카운터까지 더 좋은 해가 발견되지 않으면 종료하는 방식)

참고 블로그