언덕내려가기(hill climbing)는 더 나은 해만 받아들이기 때문에 가장 가까운 국소최적에 갇힌다. 시뮬레이티드 어닐링은 온도라는 단 하나의 파라미터로 "나쁜 해를 받아들일 확률"을 제어한다. 뜨거울 때는 거의 무작위로 헤매고, 식어갈수록 점점 까다로워진다 — 금속이 천천히 식으며 결정 구조를 정돈하듯이. 이 페이지는 그 수용 규칙이 어디서 왔는지, 왜 (이론적으로) 전역최적에 수렴하는지, 그리고 Expert의 거대한 탐색공간 문제들이 이 원리를 어떻게 쓰는지 추적한다.
상태 공간 S와 비용(에너지) 함수 E : S → ℝ가 주어졌을 때, E를 최소화하는 상태 s* = argmin_{s∈S} E(s)를 찾는다. S는 너무 커서 전수 탐색이 불가능하고, E는 미분 불가능하거나 봉우리와 골짜기로 가득한 비볼록(non-convex) 함수다.
이런 지형에서 언덕내려가기는 무력하다. 현재 해의 이웃 중 더 싼 해로만 이동하면, 사방이 자기보다 비싼 해로 둘러싸인 첫 번째 국소최적(local optimum)에서 영원히 멈춘다. 그 국소최적이 전역최적(global optimum)이라는 보장은 어디에도 없다.
시뮬레이티드 어닐링(Simulated Annealing, SA)의 발상은 야금학에서 빌려왔다. 금속을 고온으로 가열하면 원자들이 자유롭게 진동하다가, 천천히 식히면 에너지가 가장 낮은 규칙적 결정 격자로 자리잡는다. 너무 빨리 식히면(담금질, quench) 무질서한 고에너지 상태에 갇힌다. SA는 이 물리 과정을 최적화 알고리즘으로 모사한다.
핵심 메커니즘은 한 줄로 요약된다. 이웃 해 s'가 현재 해 s보다 나쁘더라도, 온도 T에 의존하는 확률 exp(−ΔE/T)로 그것을 받아들인다. 여기서 ΔE = E(s') − E(s) > 0이다. 뜨거울 때(T 큼)는 이 확률이 1에 가까워 거의 모든 이동을 허용 — 지형 전체를 헤맨다. 식어갈 때(T → 0)는 확률이 0으로 떨어져 사실상 언덕내려가기가 된다 — 발견한 좋은 영역을 정밀하게 다듬는다.
모든 메타휴리스틱은 탐험(exploration)과 활용(exploitation)의 줄다리기다. 탐험만 하면 영원히 무작위 산책이고, 활용만 하면 언덕내려가기처럼 갇힌다. SA의 우아함은 이 두 힘을 온도 하나로 연속적으로 조절한다는 데 있다. 알고리즘 초반은 탐험 위주, 후반은 활용 위주 — 별도의 전환 로직 없이 냉각 스케줄이 자동으로 무게중심을 옮긴다.
SA의 상태열 s_0, s_1, s_2, …은 마르코프 연쇄(Markov chain)다. 다음 상태는 현재 상태에만 의존하고, 전이 확률은 "이웃 제안 분포 × 수용 확률"로 정해진다. 정당성 증명은 이 연쇄가 어떤 분포로 수렴하는지를 먼저 밝히고(정리 1), 온도를 0으로 보낼 때 그 분포가 전역최적에 집중됨(정리 2)을 보이고, 마지막으로 충분히 느린 냉각이면 전역최적 도달이 보장됨(정리 3)을 잇는다.
고정 온도 T에서, 이웃 제안 분포가 대칭(q(s→s') = q(s'→s))이라고 하자. 그러면 볼츠만 분포 π_T(s) = exp(−E(s)/T) / Z_T (단, Z_T는 정규화 상수)는 상세 균형 조건 π_T(s)·P(s→s') = π_T(s')·P(s'→s)를 만족한다.
검증. E(s') ≥ E(s)인 경우만 보면 충분하다(반대는 대칭). 이때 P(s→s') = q(s→s')·exp(−ΔE/T)이고 P(s'→s) = q(s'→s)·1이다. 좌변 = exp(−E(s)/T)·q·exp(−(E(s')−E(s))/T) = q·exp(−E(s')/T). 우변 = exp(−E(s')/T)·q·1 = q·exp(−E(s')/T). 정규화 상수 Z_T는 양변에 공통이므로 두 변이 같다.
고정 온도 T의 SA 마르코프 연쇄가 비주기적(aperiodic)이고 기약(irreducible — 임의의 두 상태가 서로 도달 가능)이면, 그 연쇄는 유일한 정상 분포로 수렴하며 그 분포는 볼츠만 분포 π_T다.
증명. 상세 균형(Lemma)을 만족하는 분포는 자동으로 정상 분포다 — π_T(s)·P(s→s')를 모든 s에 대해 합하면 Σ_s π_T(s)P(s→s') = Σ_s π_T(s')P(s'→s) = π_T(s')·Σ_s P(s'→s) = π_T(s'), 즉 π_T는 한 스텝 후에도 보존된다. 유한 상태공간에서 기약·비주기 마르코프 연쇄는 정상 분포가 유일하고 임의의 초기 분포가 그것으로 수렴한다(에르고딕 정리).
전역최적 집합을 S* = { s : E(s) = E_min }이라 하자. 온도를 0으로 보내면 볼츠만 분포는 S* 위의 균등분포로 수렴한다: lim_{T→0} π_T(s) = 1/|S*| (단 s ∈ S*), 그 외 상태에서는 0.
증명. π_T(s) = exp(−E(s)/T) / Σ_u exp(−E(u)/T). 분자·분모를 exp(−E_min/T)로 나누면 π_T(s) = exp(−(E(s)−E_min)/T) / Σ_u exp(−(E(u)−E_min)/T). s ∈ S*이면 분자는 항상 1. s ∉ S*이면 E(s)−E_min > 0이므로 T→0일 때 분자가 0으로 지수적으로 붕괴. 분모는 |S*|개의 1과 0으로 수렴하는 항들의 합이므로 |S*|로 수렴. 따라서 비최적 상태의 확률은 0, 최적 상태는 각각 1/|S*|.
냉각 스케줄이 T(k) ≥ c / log(1 + k)를 만족할 만큼 충분히 큰 상수 c로 천천히 식으면(c는 지형의 최대 에너지 장벽 깊이 이상), SA는 확률 1로 전역최적에 도달한다.
증명의 골자. 핵심 어려움은 온도가 변하면 연쇄가 더 이상 시간-동질(homogeneous)이 아니라는 점이다. 증명은 두 시간 척도를 분리한다. (1) 각 온도 구간이 충분히 길면 연쇄는 그 온도의 볼츠만 분포 π_{T(k)}에 "거의" 도달한다(Theorem 1). (2) 온도가 로그 속도보다 빠르지 않게 내려가면, 연쇄가 평형을 따라잡는 속도가 온도 하강 속도를 앞질러 분포 추적 오차가 0으로 수렴한다. (1)+(2)로 k→∞일 때 상태 분포가 π_{T(k)} → S* 집중분포(Theorem 2)를 따라간다. 로그 속도가 등장하는 이유는 깊이 d인 에너지 장벽을 넘을 기대 시간이 ∼ exp(d/T)이고, 이를 유한 시간에 무한히 자주 넘으려면 Σ_k exp(−d/T(k)) = ∞ (보렐-칸텔리)이어야 하므로 T(k) ≳ d/log k가 필요하기 때문이다.
SA 성능의 90%는 냉각 스케줄에서 결정된다. 핵심 파라미터는 셋이다.
종료 조건은 보통 (1) T가 임계값 이하, (2) 일정 횟수 동안 개선 없음, (3) 시간/반복 예산 소진 중 하나다. 그리고 반드시 탐색 중 만난 최선 해(best)를 별도로 기억한다 — 마지막 상태가 best가 아닐 수 있기 때문이다.
SA는 문제 독립적인 골격과 문제 의존적인 세 함수(energy, neighbor, 그리고 선택적으로 delta)로 깔끔하게 분리된다. 골격은 한 번 작성하면 단백질 배치든 칩 배치든 그대로 재사용한다. 아래는 기하 냉각 + Metropolis 수용 + best 추적을 갖춘 표준 구현이다.
#include <cmath>#include <random>#include <functional>using namespace std;// 문제 독립 골격. State 는 해의 표현(임의 타입).template <class State>State anneal( State cur, // 초기 해 function<double(const State&)> energy, // 비용 E(s) function<State(const State&, mt19937&)> neighbor) // 이웃 제안{ mt19937 rng(12345); uniform_real_distribution<double> unit(0.0, 1.0); double curE = energy(cur); State best = cur; // 만난 최선 해를 따로 보존 double bestE = curE; // 냉각 스케줄 파라미터 double T = 1.0e4; // 초기 온도 T0 const double Tmin = 1.0e-4; // 종료 온도 const double alpha = 0.995; // 기하 냉각률 const int L = 200; // 온도당 반복 횟수 while (T > Tmin) { for (int i = 0; i < L; ++i) { State cand = neighbor(cur, rng); double candE = energy(cand); double dE = candE - curE; // Metropolis: 개선이거나, exp(-dE/T) 확률로 후퇴 수용 if (dE <= 0.0 || unit(rng) < exp(-dE / T)) { cur = cand; curE = candE; if (curE < bestE) { best = cur; bestE = curE; } } } T *= alpha; // 냉각: T <- alpha * T } return best; // 마지막 cur 가 아니라 best 를 반환}
dE <= 0의 단락 평가(short-circuit) 덕분에 개선 이동에서는 비싼 exp 호출조차 건너뛴다. 라인 38이 best 반환의 이유 — 알고리즘은 식어가는 도중에도 후퇴를 수용하므로 종료 시점의 cur는 일반적으로 best보다 나쁘다. 실전 최적화 두 가지: (1) energy를 매번 처음부터 계산하지 말고, 이동이 바꾸는 부분만 다시 계산하는 증분 평가(delta evaluation)로 candE = curE + Δ를 직접 얻으면 큰 인스턴스에서 수십 배 빨라진다. (2) neighbor는 작고 국소적인 변화(2-swap, 한 원소 이동 등)를 제안해야 한다 — 변화가 너무 크면 ΔE가 항상 거대해져 저온에서 모든 이동이 거부된다.
온도 단계 수는 T₀ → T_min이 기하 냉각이므로 O(log(T₀/T_min) / log(1/α)). 각 단계가 L회 반복하고, 한 반복의 비용은 neighbor + energy다. 증분 평가를 쓰면 한 반복이 O(1)~O(log n)까지 줄어, 전체는 O(반복수 × 증분비용). 공간은 현재 해 + best 해 + 이웃 후보로 O(n). 시간 복잡도가 입력 크기로 깔끔하게 표현되지 않는 것이 SA의 본질이다 — 반복 횟수는 정확도-시간 트레이드오프를 쥔 사용자가 정하는 예산이지, 입력이 강제하는 값이 아니다.
SA가 Expert에서 등장하는 신호는 항상 같다 — 해의 공간이 지수적으로 크고, 비용 함수가 비볼록이며, 정확해를 다항시간에 구하는 알고리즘이 알려져 있지 않다. 이때 문제별 차이는 오직 세 함수(energy, neighbor, 냉각 스케줄)의 설계로 흡수된다.
단백질폴딩에서 상태는 아미노산 사슬의 3D 접힘 형태이고, energy는 "고가 원소(고밀도 잔기)들이 서로 얼마나 가까이 뭉쳐 있는가"를 측정한다. 이웃 이동은 회전 대수(rotation algebra)로 한 결합각을 작게 비트는 것 — 연속 공간이므로 이웃은 무한히 많고, 작은 각도 섭동(perturbation)으로 국소적 후보를 만든다. 비용 지형이 깊은 골짜기로 가득해 언덕내려가기는 즉시 갇히지만, SA는 초반의 높은 온도로 여러 골짜기를 건너뛰며 전역적으로 더 조밀한 코어를 찾는다.
RTX5090 칩배치에서 상태는 회로 블록들의 2D 배치이고, energy는 총 배선 길이 + 면적 + 겹침 페널티의 가중합이다. 이웃 이동은 두 블록 교환, 한 블록 회전, 한 블록 이동 같은 이산 연산. 배치 문제는 NP-난해의 전형이라 정확해가 불가능하고, SA는 산업용 EDA 도구가 실제로 채택한 표준 해법이다. 핵심 변형은 겹침을 금지(infeasible) 대신 비싼 페널티로 처리해 제약을 비용에 녹이는 것 — 그래야 SA가 일시적으로 겹친 배치를 거쳐 더 나은 배치로 건너갈 수 있다.
원형화물은 크기가 다른 원들을 컨테이너에 빈틈없이 채우는 기하 패킹 문제다. 상태는 각 원의 중심 좌표, energy는 컨테이너 밖으로 나가거나 서로 겹치는 양의 총합이다. 이웃 이동은 한 원을 작은 벡터만큼 밀기. 패킹 지형은 "거의 맞지만 한 원만 약간 겹친" 국소최적이 빽빽해 SA의 후퇴 수용이 결정적으로 작동한다 — 한 원을 일부러 나쁜 위치로 밀어야 옆 원들이 재배열될 공간이 생긴다.
neighbor 설계가 좋은 냉각 스케줄보다 중요하다.
| 알고리즘 | 국소최적 탈출 | 해 집합 | 쓰임 |
|---|---|---|---|
| Hill Climbing | 불가 | 단일 | 볼록 문제, 또는 빠른 국소 다듬기 |
| Simulated Annealing | 확률적 후퇴 수용 | 단일 | 비볼록 단일 목적 — 가장 범용적 |
| Tabu Search | 최근 이동 금지 | 단일 | 이산 조합 최적화 — 기억 기반 |
| Genetic Algorithm | 교차 + 변이 | 개체군 | 구조화된 해 표현 — 병렬 탐색 |
| Particle Swarm | 군집 정보 공유 | 개체군 | 연속 공간 — 좌표 벡터 최적화 |
SA와 언덕내려가기의 관계는 다익스트라와 BFS의 관계와 같다 — SA에서 온도를 0으로 고정하면 곧장 언덕내려가기다. SA는 "온도가 있는 언덕내려가기"인 셈이다. Tabu Search는 후퇴를 확률이 아니라 결정론적 금지 목록(tabu list)으로 다룬다 — 최근 방문한 해로 되돌아가는 것을 명시적으로 막아 사이클을 피한다. SA의 무작위성을 싫어하는 이산 문제에 강하다.
유전 알고리즘(GA)과 입자군집(PSO)은 해를 하나가 아니라 개체군으로 들고 다니며 그들 사이의 정보를 섞는다. SA는 한 점만 움직이므로 메모리가 가볍고 구현이 짧다 — Expert의 시간·메모리 제약 안에서는 이 단순함이 종종 결정적 이점이다. 실무 권장 순서: 먼저 SA로 견고한 베이스라인을 잡고, 성능이 부족하면 개체군 기반으로 옮긴다. 그리고 어떤 메타휴리스틱을 쓰든 — SA의 best 추적처럼 — 만난 최선 해를 항상 따로 보존하라.