한양과기고 에듀테크 수업도구 대시보드

🔥 담금질 기법 (Simulated Annealing)

대장장이가 뜨거운 쇠를 천천히 식히면 원자들이 안정된 배열을 찾아 단단해진다. 이 풀림(annealing) 과정을 흉내 낸 최적화 알고리즘이 담금질 기법이다. 처음엔 온도 T가 높아 손해 보는 이동도 자주 받아들여 넓게 탐색하고, T가 낮아질수록 점점 더 좋은 이동만 골라 정답 근처에 정착한다. 덕분에 지역 최솟값(local minimum)에 갇히지 않고 빠져나올 수 있다.

외판원 문제(TSP)로 보는 담금질

여러 도시를 한 번씩만 방문하고 출발지로 돌아오는 가장 짧은 순회 경로를 찾는 문제다. 도시가 N개면 경로 후보는 (N-1)!/2 개 — 20개만 되어도 전부 확인하기 불가능하다. 담금질은 지금 경로에서 구간 2개를 뒤집어(2-opt) 보고, 짧아지면 무조건 채택, 길어져도 확률 exp(−Δ/T) 로 채택한다.

탐욕 모드 (나쁜 이동 거부 = 언덕 오르기)

도시 수 22

시작 온도 T₀ 40

냉각률 α (T ← αT) 0.9970

속도 (스텝/프레임) 80

온도 T

–

현재 경로

–

최단 경로

–

반복 수

● 현재 경로 ● 지금까지 찾은 최단 경로 ✦ 방금 손해인데도 채택된 이동 (온도가 높을수록 자주 깜빡인다)

온도와 경로 길이의 변화

초반엔 온도가 높아 경로 길이가 출렁이며(위로도 튀며) 넓게 탐색한다. 온도가 지수적으로 떨어지면 점차 더 나은 방향으로만 움직여 길이가 계단처럼 수렴한다. 너무 빨리 식히면(α 작게) 지역 최솟값에 갇히고, 너무 천천히 식히면 오래 걸린다 — 냉각 스케줄이 핵심.

손해인 이동을 받아들일 확률

P(채택) = e^{−Δ / T} (단, Δ = 새 비용 − 현재 비용 > 0 일 때) Δ ≤ 0 이면 (더 좋아지면) 확률 1 로 무조건 채택

손해 정도 Δ 8

온도 T 40

채택 확률

T 가 크면 → 웬만한 손해도 잘 받아들임 (뜨거운 탐색)
T 가 0 에 가까우면 → 손해 이동 거의 거부 (탐욕적 마무리)
Δ 가 크면(많이 손해) → 같은 T 라도 채택 확률 급감

알고리즘 한눈에

초기 해 s를 아무렇게나 만들고, 온도 T = T₀ 로 설정
이웃 해 s'를 하나 만든다 (TSP면 경로 일부 구간을 뒤집기)
비용 차이 Δ = cost(s') − cost(s) 계산
Δ ≤ 0 이면 채택. Δ > 0 이면 확률 e^−Δ/T 로 채택 (난수 뽑아 비교)
채택되면 s ← s'. 지금까지 최선이면 따로 기록
온도를 식힌다: T ← α·T (예: α = 0.997)
T 가 충분히 낮아질 때까지 2~6 반복 → 기록해 둔 최선의 해가 정답

# 파이썬 의사코드 import math, random def simulated_annealing(cost, neighbor, s0, T=40.0, alpha=0.997, T_min=1e-3): s, best = s0, s0 while T > T_min: s2 = neighbor(s) d = cost(s2) - cost(s) if d <= 0 or random.random() < math.exp(-d / T): s = s2 if cost(s) < cost(best): best = s T *= alpha # 냉각 스케줄 return best

언덕 오르기(hill climbing)는 4번에서 "Δ ≤ 0 일 때만 채택"한다. 빠르지만 첫 번째로 만난 골짜기에서 못 빠져나온다. 담금질은 초반의 무작위성으로 그 함정을 건너뛴다. α = 1 로 두면(냉각 안 함) 영원히 무작위로 헤매고, T₀ = 0 이면 그냥 언덕 오르기가 된다. 비슷한 아이디어를 쓰는 친척으로 유전 알고리즘, 타부 서치가 있다.