담금질 기법 (Simulated Annealing)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 2분 · 692자/단어 #algorithm #optimization #simulated-annealing

정의

담금질 기법 (Simulated Annealing, SA) 은 금속의 담금질 (annealing) 과정에서 영감을 받은 확률적 메타휴리스틱. 온도 T 가 높을 때는 나쁜 해도 확률적으로 수용하여 local optimum 탈출을 시도하고, T 가 낮아질수록 greedy 수용으로 전환.

문제 상황과 동기

휴리스틱 중 Local Search 는 지역 최적 (local optimum) 에 갇히는 fatal 한 단점. SA 는 확률적 탈출로 이 문제를 완화.

Local Search: 항상 개선 방향으로만 이동 -> 지역 최적.
SA: 나쁜 이동도 P = exp(-delta / T) 확률로 수용 -> 전역 탐색 가능.

핵심 통찰: 초기에는 “exploration”, 후기에는 “exploitation”.

시각화

핵심 아이디어

에너지와 온도

E(s): 현재 해 s 의 비용 (목적 함수)
T: 온도 (제어 파라미터), 시간에 따라 감소
delta = E(s') - E(s): 새 해와 현 해의 비용 차

수용 확률 (Metropolis Criterion)

P(accept) = 1                if delta < 0 (개선됨)
P(accept) = exp(-delta / T)  if delta >= 0 (악화됨)

T 가 클수록 나쁜 해도 자주 수용. T -> 0 이면 greedy 와 동일.

알고리즘

1. 초기 해 s, 초기 온도 T0 설정
2. while T > T_min:
3.   s' = neighbor(s)   # 이웃 생성
4.   delta = E(s') - E(s)
5.   if delta < 0 or random() < exp(-delta / T):
6.     s = s'
7.   T = T * alpha      # 냉각 (cooling)
8. return best_s

구현

// TSP simulated annealing, 2-opt swap neighbor
#include <bits/stdc++.h>
using namespace std;

double cost(const vector<int>& ord, const vector<vector<double>>& d) {
  double sum = 0; int n = ord.size();
  for (int i = 0; i < n; i++)
      sum += d[ord[i]][ord[(i+1)%n]];
  return sum;
}

int main() {
  int n; cin >> n;
  vector<vector<double>> dist(n, vector<double>(n));
  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
          cin >> dist[i][j];
  vector<int> cur(n);
  iota(cur.begin(), cur.end(), 0);
  random_device rd;
  mt19937 gen(rd());
  uniform_real_distribution<> dis(0, 1);
  double T = 1000, alpha = 0.997, T_min = 1e-8;
  double curE = cost(cur, dist), bestE = curE;
  vector<int> best = cur;
  while (T > T_min) {
      int i = uniform_int_distribution<>(0, n-1)(gen);
      int j = uniform_int_distribution<>(0, n-1)(gen);
      if (i == j) continue;
      swap(cur[i], cur[j]);
      double newE = cost(cur, dist);
      double delta = newE - curE;
      if (delta < 0 || dis(gen) < exp(-delta / T)) {
          curE = newE;
          if (curE < bestE) { bestE = curE; best = cur; }
      } else {
          swap(cur[i], cur[j]);
      }
      T *= alpha;
  }
  cout << (int)bestE << "\n";
  for (int v : best) cout << v << " ";
  cout << "\n";
}

# TSP simulated annealing
import random, math

def total_dist(ord, d):
  n = len(ord)
  return sum(d[ord[i]][ord[(i+1)%n]] for i in range(n))

n = int(input())
dist = [list(map(float, input().split())) for _ in range(n)]
cur = list(range(n))
random.shuffle(cur)
T, alpha, T_min = 1000, 0.997, 1e-8
curE = total_dist(cur, dist)
bestE, best = curE, cur[:]

while T > T_min:
  i, j = random.sample(range(n), 2)
  cur[i], cur[j] = cur[j], cur[i]
  newE = total_dist(cur, dist)
  delta = newE - curE
  if delta < 0 or random.random() < math.exp(-delta / T):
      curE = newE
      if curE < bestE:
          bestE, best = curE, cur[:]
  else:
      cur[i], cur[j] = cur[j], cur[i]
  T *= alpha

print(int(bestE))
print(*best)

stdin

결과

80
0 1 3 2

복잡도

항목	값
시간 (iteration 당)	O(N) (이웃 생성 + 평가)
전체 iteration	O(log(T0 / T_min) / log(1/alpha))
공간	O(N)
냉각 방식	기하급수적 alpha=0.99~0.999

변형 / 활용

변형	설명
Adaptive SA	온도 자동 조절 (reannealing)
Parallel SA	여러 체인 동시 실행
Quantum Annealing	양자 요동을 활용한 SA (D-Wave)

응용: TSP, VLSI 배치, 일정 최적화, 단백질 폴딩, hyperparameter tuning.

함정

1. 냉각 속도

alpha 가 너무 작으면 (급속 냉각) 지역 최적. 너무 크면 수렴 느림. alpha=0.997 ~ 0.999 권장.

2. 초기 온도

T0 가 너무 낮으면 초기부터 greedy. 초기 수용률 ~80% 가 되도록 T0 설정.

3. 이웃 생성

neighbor 구조가 SA 성능을 결정. TSP 에서 2-opt 가 swap 보다 훨씬 효과적.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1699	제곱수의 합 (SA)	-	kokoa-lab
BOJ 19192	TSP (SA 로 풀이 가능)	-	kokoa-lab