담금질 기법 (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

알고리즘 흐름도

flowchart TD
    A["초기 해 s, T = T0"] --> B["이웃 해 s_new 생성"]
    B --> C["delta = cost(s_new) - cost(s)"]
    C --> D{"delta 음수?"}
    D -->|"Yes"| E["s = s_new 수용"]
    D -->|"No"| F{"확률 수용?"}
    F -->|"Yes"| E
    F -->|"No"| G["거절, s 유지"]
    E --> H{"T 최솟값 초과?"}
    G --> H
    H -->|"Yes"| I["T *= alpha 냉각"]
    I --> B
    H -->|"No"| J["최적 해 반환"]

구현

// 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)

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80
0 1 3 2

복잡도

변형 / 활용

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

냉각 스케줄 비교

냉각 속도가 너무 빠르면 local optimum 에 갇히고, 너무 느리면 수렴 시간이 지수적으로 증가. alpha = 0.997 ~ 0.999 가 실전 균형점.

함정

1. 냉각 속도

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

2. 초기 온도

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

3. 이웃 생성

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

4. 초기 해의 질

무작위 초기 해로 시작해도 SA 는 동작하지만, greedy 해를 초기 해로 주면 수렴이 빠름. TSP 에서 nearest neighbor heuristic 으로 구한 해를 SA 시작점으로 활용하면 품질이 높아짐.

5. 시간 기반 냉각

PS 에서 실행 시간 제한이 있을 때는 iteration 대신 경과 시간으로 냉각:

auto start = chrono::steady_clock::now();
// ... 루프 내부 ...
auto now = chrono::steady_clock::now();
double elapsed = chrono::duration<double>(now - start).count();
double T = T0 * (1.0 - elapsed / TIME_LIMIT);

제한 시간 2초라면 TIME_LIMIT = 1.95 로 안전 마진 확보.

6. 비결정성

SA 는 확률적 알고리즘. 같은 입력에도 결과가 다를 수 있음. 제출 시 mt19937 에 고정 seed 를 쓰거나, 시간 seed 로 여러 번 실행 후 최소값 선택.

BOJ 연습 문제

참고

• 휴리스틱
• 경사 하강법