담금질 모사 (Simulated Annealing)

최적설계 수치해석 통계 시뮬레이션 마지막 수정: 2026-07-17 04:46:09

1. 개요[편집]

담금질 모사 Simulated Annealing
약칭	SA
발표	1983년, Kirkpatrick, Gelatt & Vecchi
기반	메트로폴리스 알고리즘, 금속 열처리
핵심 파라미터	온도 T, 냉각 스케줄
분류	확률적 전역 최적화, 메타휴리스틱

담금질 모사(Simulated Annealing, SA)는 금속을 고온에서 천천히 식혀 결함 없는 결정을 얻는 열처리(annealing) 과정을 흉내 낸 확률적 전역 최적화 알고리즘이다. 목적함수를 “에너지”, 알고리즘 진행도를 “온도”로 놓고, 온도가 높을 때는 나빠지는 방향으로도 과감히 움직이다가 온도를 서서히 낮춰 최적해에 정착시킨다. 1983년 Kirkpatrick 등이 Science에 발표하면서 이름을 얻었다.¹

경사하강법 계열이 가장 가까운 골짜기로 직행해 지역 최적해에 처박히는 것과 대조적으로, SA는 “가끔 언덕을 올라간다”. 대장장이가 담금질할 때 급랭시키면 내부 응력이 잔뜩 남은 유리질이 되고 서랭시키면 반듯한 결정이 되는 것과 같은 원리 — 급하게 식히면 아무 데나 굳어버린다는 물리적 직관이 그대로 알고리즘이 됐다.

목적함수가 미분 불가능하거나, 불연속이거나, 조합적이거나, 그냥 블랙박스여도 상관없다는 것이 최대 강점이다. 필요한 건 딱 두 가지 — 해를 조금 바꾸는 방법(이웃 생성)과 그 해의 점수를 매기는 함수뿐이다.

2. 알고리즘[편집]

핵심은 몬테카를로 방법의 메트로폴리스 판정 기준이다. 현재 해 $x$ 에서 이웃 해 $x'$ 를 뽑아 에너지 차이 $\Delta E = E(x') - E(x)$ 를 계산하고, 다음 확률로 수락한다.

P(\text{accept}) = \begin{cases} 1 & \Delta E \le 0 \\[4pt] \exp\left(-\dfrac{\Delta E}{T}\right) & \Delta E > 0 \end{cases}

좋아지면 무조건 받고, 나빠지면 확률적으로 받는다. 그 확률이 볼츠만 인자 $e^{-\Delta E/T}$ 다. 온도 $T$ 가 크면 웬만한 개악도 통과되어 탐색 공간을 마구 헤집고, $T \to 0$ 이면 개선만 받으므로 사실상 탐욕적 언덕오르기가 된다. 즉 온도 하나가 탐험(exploration)과 활용(exploitation)의 다이얼이다.²

의사코드로 정리하면 놀랄 만큼 짧다.

x ← 초기해;  T ← T0
while T > T_min:
    for k = 1..L:                       # 각 온도에서 L번 시도
        x' ← 이웃(x)
        ΔE ← E(x') - E(x)
        if ΔE ≤ 0 or rand() < exp(-ΔE/T):
            x ← x'
        best ← min(best, x)             # 최고 기록은 따로 보관
    T ← 냉각(T)

30줄이면 구현되고 파라미터도 몇 개 없다. 진입 장벽이 이렇게 낮은데 성능은 제법 나오는 것이 SA가 40년 넘게 살아남은 이유다.

3. 냉각 스케줄[편집]

SA의 성패는 사실상 냉각 스케줄이 다 한다. 대표적인 것들:

기하 냉각: $T_{k+1} = \alpha T_k$ , $\alpha \in [0.8, 0.99]$ . 압도적으로 가장 많이 쓰인다. 단순하고 잘 먹힌다.
선형 냉각: $T_k = T_0 - \beta k$ . 직관적이지만 초반에 너무 빨리 식는다.
로그 냉각: $T_k = c / \ln(1+k)$ .

여기서 흥미로운 지점이 나온다. Geman & Geman(1984)은 로그 냉각을 쓰면 SA가 확률 1로 전역 최적해에 수렴한다는 것을 증명했다.³ 문제는 그 로그가 너무 느리다는 것. 온도를 절반으로 내리는 데 필요한 반복 수가 지수적으로 늘어난다. 실무에서 이 보장을 받으려면 완전 탐색보다 오래 걸리는 경우가 많다. 그래서 모두가 기하 냉각을 쓰고 전역 수렴 보장은 포기한다. 이론과 실무의 거리를 보여주는 교과서적 사례다.

실무 튜닝 포인트:

항목	처방
초기 온도 T0	초반 수락률이 0.8 정도가 되도록 역산
냉각률 α	0.95 근처에서 시작, 시간 예산에 맞춰 조정
온도당 반복 L	문제 차원에 비례하게
이웃 생성	여기가 진짜 핵심 — 아래 참고
종료	T_min 도달 또는 일정 구간 개선 없음

4. 이웃 생성이 절반이다[편집]

논문은 냉각 스케줄을 이야기하지만, 현업에서 SA 성능을 가르는 건 대개 이웃 생성 연산자다. 이웃이 너무 크면 랜덤 서치와 다를 바 없고, 너무 작으면 온도를 아무리 높여도 골짜기를 못 넘는다.

연속 변수: 가우시안 섭동 $x' = x + \sigma \mathcal{N}(0,1)$ . 온도에 따라 $\sigma$ 를 함께 줄이는 것이 국룰.
순회 판매원 문제(TSP): 경로 일부를 뒤집는 2-opt 연산이 고전. SA + 2-opt 조합은 아직도 준수한 베이스라인이다.
배치·스케줄링: 두 작업 교환, 작업 하나 이동 등 도메인 지식이 그대로 들어간다.

즉 SA는 “아무 문제나 던지면 풀어주는 마법”이 아니라, 문제 구조를 이웃 연산자에 얼마나 잘 녹였는가를 증폭시켜 주는 틀에 가깝다. 아무 생각 없이 랜덤 섭동만 넣으면 아무 생각 없는 결과가 나온다.

5. 어디에 쓰이나, 그리고 사촌들[편집]

원 논문의 무대부터가 VLSI 배치·배선 문제였고, 지금도 조합 최적화 쪽에서 꾸준히 쓰인다. 시뮬레이션 분야에서는 이런 자리들:

위상 최적화나 형상 최적화에서 설계 변수가 이산적이거나 민감도를 못 구할 때. 다만 유한요소 해석 한 번이 비싸면 SA의 수만 번 평가가 그대로 재앙이 되므로, 대리 모델을 씌워 쓰는 것이 정석이다.
힘장 파라미터 피팅, 결정 구조 예측, 분자 형태 탐색 등. 여기서는 온도가 은유가 아니라 진짜 온도인 경우도 있어서, 분자동역학에 서모스탯을 걸어 실제로 가열-서랭하는 방식으로 구현되기도 한다.
격자 생성의 노드 재배치, 실험 배치 설계, 역해석 문제(역문제)의 파라미터 추정 등.

메타휴리스틱 친척들과 비교하면 SA의 자리는 이렇다. 유전 알고리즘과 입자 군집 최적화는 해집단(population)을 굴리므로 병렬화가 자연스럽고 다중 최적해를 동시에 훑지만, 파라미터가 많고 메모리를 먹는다. SA는 해 하나만 들고 다녀서 메모리가 거의 안 들고 구현이 짧지만, 순차적이라 병렬화가 어색하다. 이 약점을 메우려고 여러 온도의 사슬을 동시에 굴리며 교환하는 병렬 템퍼링(parallel tempering / replica exchange)이 나왔고, 오늘날 계산화학·통계물리에서는 오히려 이쪽이 주류다.

한 가지 오해를 정리하자면, “양자 어닐링”은 SA의 양자 버전 이름표만 붙인 것이 아니다. 언덕을 넘는 대신 터널링으로 뚫는 다른 물리를 쓴다. 이름이 비슷하다고 같은 알고리즘이라고 말하면 그쪽 사람들이 정색한다.⁴

6. 관련 문서[편집]

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). “Optimization by Simulated Annealing”. Science 220, 671. IBM에서 VLSI 배치 문제를 붙들고 있다가 통계역학 배경을 그대로 최적화에 이식했다. 물리학자가 다른 분야로 넘어가 판을 뒤집은 고전적 사례. ↩
온도가 높을 때 나쁜 해를 받아들이는 것은 버그가 아니라 기능이다. “지금 손해 보더라도 나중을 위해 넓게 본다”를 수식 한 줄로 구현한 셈인데, 이게 사람 인생에 적용되지 않는다는 점이 아쉬울 따름이다. ↩
Geman, S. & Geman, D. (1984). 로그 냉각의 전역 수렴 보장은 수학적으로 아름답지만 실용성은 거의 없다. 보장을 받는 데 걸리는 시간이 무한대에 수렴하기 때문. “무한한 시간을 주면 최적해를 찾아준다”는 문장은 무작위 탐색도 만족한다. ↩
양자 어닐링은 에너지 장벽을 열적으로 넘는 대신 양자 터널링으로 통과한다. 얇고 높은 장벽에서는 유리할 수 있다는 것이 논리인데, 실제 하드웨어에서 고전 SA를 확실히 이겼는지에 대해서는 여전히 논쟁이 진행 중이다. 학회에서 이 주제를 꺼내면 커피 브레이크가 길어진다. ↩