토픽 78 / 82

시뮬레이티드 어닐링 (SA, Simulated Annealing)

금속 담금질(Annealing) 과정에서 착안한 메타휴리스틱으로, 높은 온도에서 나쁜 해도 확률적으로 수용하다가 온도를 서서히 낮추어 최적해에 수렴

목적: 지역 최적해 탈출, 전역 최적해 근사, 단일 해 기반 탐색

특징: 단일 해 기반, 확률적 수용, 온도 감소, 지역 최적 탈출

동작 원리: ① 초기 해와 높은 온도 설정 → ② 이웃 해 생성 → ③ 개선이면 수용, 악화면 확률적 수용 → ④ 온도 감소 → ⑤ 종료 조건까지 반복

수용 확률: P = exp(-deltaE/T), 온도 T가 높을수록 나쁜 해 수용 확률 높음

냉각 스케줄: 선형(T-=alpha), 지수(T*=alpha), 로그(T=T0/log(1+t))

장점: 지역 최적해 탈출, 구현 간단, 범용적 적용

단점: 냉각 스케줄 민감, 수렴 느림, 초기 온도 설정 중요

적용사례: VLSI 배치, TSP, 조합 최적화, 이미지 처리

비교: SA(단일해/담금질/간단) vs GA(집단/진화/병렬) vs 타부서치(단일해/메모리/금지목록)

연관: 메타휴리스틱, 담금질, 볼츠만 분포, NP-hard