시뮬레이티드 어닐링 : Simulated Annealing

(1) 경사하강법(Gradient Descent)의 탐욕적 한계와 지역 극소점(Local Minima) 탈출

오차역전파(Backpropagation)나 결정론적 홉필드 망과 같은 전통적인 신경망 학습은 목적 함수(오차 함수 또는 에너지 함수)의 기울기(Gradient)만을 따라 아래로만 내려가는 하향 탐욕 알고리즘(Greedy Descent)을 기반으로 합니다. 그러나 수많은 매개변수를 가진 고차원 신경망의 오차 곡면(Loss Surface)에는 수없이 많은 지역 극소점(Local Minima)과 안장점(Saddle Points)이 존재하며, 초기 가중치 설정에 따라 학습이 미성숙한 채 멈추어버리는 조기 수렴(Premature Convergence) 현상이 발생합니다. 시뮬레이티드 어닐링은 에너지가 증가하는(즉, 오차가 일시적으로 커지는) 상향 방향으로의 전이도 일정한 확률로 허용함으로써 깊은 계곡을 박차고 나와 전체 탐색 공간에서 전역 최적점(Global Optimum)을 찾을 수 있는 근본적인 해결책을 제시했습니다.

(2) 물리적 담금질(Metallurgical Annealing)과 메트로폴리스 알고리즘의 융합

1953년 N. Metropolis 등이 제안한 몬테카를로 통계역학 모델과 야금학(Metallurgy)의 담금질 원리를 결합하였습니다. 고온에서는 원자들이 높은 운동 에너지로 에너지 장벽을 자유롭게 뛰어넘어 광범위한 구조를 탐색하다가, 온도를 제어하며 서서히 냉각(Controlled Cooling)함에 따라 가장 안정적인 최저 에너지 결정 격자(Ground State)로 응고되는 물리 법칙을 수학적 최적화로 구현하였습니다.

(3) 확률적 신경망(Stochastic Neural Networks)의 이론적 초석

시뮬레이티드 어닐링 자체는 정적인 신경망 아키텍처가 아니라 최적화 메커니즘이지만, 이를 신경망의 뉴런 상태 전이와 학습 규칙에 직접 결합함으로써 볼쯔만 머신(Boltzmann Machine)과 코시 머신(Cauchy Machine)이 탄생할 수 있었습니다. 이는 훗날 현대 딥러닝의 기틀이 된 제한된 볼쯔만 머신(RBM)과 심층 신뢰망(DBN)의 확률적 생성 모델로 이어지는 이론적 모태가 되었습니다.

(1) 메트로폴리스 수용 판별 기준 (Metropolis Acceptance Criterion)

현재 상태 $S$에서 무작위 섭동을 통해 이웃 상태 $S'$를 생성했을 때, 목적 함수의 에너지 변화량 $\Delta E = E(S') - E(S)$에 따라 상태 전이 채택 확률 $P$를 다음과 같이 계산합니다:

난수 $R \in [0, 1)$을 발생시켜 $R < P(\text{수용})$이면 에너지가 증가하는 상태라도 새로운 해로 기꺼이 수용합니다. 이 확률적 관용도가 바로 지역 극소점의 함정을 탈출하게 만드는 핵심 원동력입니다.

(2) 냉각 스케줄링 (Cooling Schedule / Temperature Annealing)

온도 $T$를 시간에 따라 어떻게 낮출 것인가는 알고리즘의 성패를 가르는 가장 핵심적인 요소입니다:

• 초기 온도 $T_0$ 설정: 거의 모든 상향 전이가 높은 확률로 수용될 만큼 충분히 높은 온도로 시작하여, 전체 상태 공간에 대한 편향 없는 대역 탐색(Exploration)을 수행합니다.
• 기하급수적 냉각 (Geometric Cooling): 가장 널리 쓰이는 실용적 방법으로, 각 단계마다 일정 감쇄율 $\alpha$ ($0.80 \le \alpha \le 0.99$)를 곱해 온도를 점진적으로 낮춥니다 ($T_{k+1} = \alpha T_k$).
• 로그형 냉각 (Logarithmic Cooling & Geman-Geman 정리): $T_k = T_0 / \ln(1 + k)$ 방식을 사용할 경우 수학적으로 전역 최적점에 100% 수렴함이 증명되어 있으나, 냉각 속도가 매우 느립니다.
• 종료 온도 $T_{\min}$: 온도가 0에 가깝게 냉각되면 상향 전이 확률이 0이 되어, 알고리즘은 순수한 탐욕 하강법(Greedy Descent)으로 전환되어 가장 깊은 전역 극소점 바닥에 정밀하게 안착(Exploitation)합니다.

(3) 신경망 가중치 최적화에서의 직접적 적용

신경망의 가중치 공간에서 가중치를 미세하게 무작위 변형($W' = W + \Delta W$)시키면서 전체 오차의 변화량을 메트로폴리스 기준으로 판별하여 가중치를 갱신할 수 있습니다. 이 방식은 목적 함수나 활성화 함수가 미분 불가능하거나 불연속적인 극단적 비선형 신경망 구조에서도 역전파 오차 미분값 계산 없이 가중치를 최적화할 수 있는 강력한 장점을 지닙니다.

(1) 초대형 조합 최적화(Combinatorial Optimization) 문제 해결

• 순회 외판원 문제(Traveling Salesman Problem, TSP): 수백~수만 개 이상의 도시를 단 한 번씩만 방문하고 출발지로 돌아오는 최단 경로를 탐색하는 대표적 NP-난해 문제에서, 지수적 탐색 시간 대신 효율적인 다항 시간 내에 최적해에 근접한 뛰어난 해를 도출합니다.
• 작업 일정 계획(Job Shop Scheduling) & 배낭 문제(Knapsack Problem): 한정된 자원과 시간 제약 조건 하에서 공정 효율을 극대화하는 생산 및 물류 최적화에 광범위하게 쓰입니다.

(2) VLSI 반도체 칩 소자 배치 및 배선(Placement & Routing)

현대 전자 설계 자동화(EDA) 툴의 핵심 알고리즘으로, 수억 개 이상의 트랜지스터와 논리 소자들을 실리콘 웨이퍼 상에 배치할 때 총 도선 연결 길이를 최소화하고 신호 지연 및 발열을 억제하는 데 표준적으로 적용됩니다.

(3) 신경망 구조 탐색(NAS) 및 하이퍼파라미터 튜닝

딥러닝 모델의 층수(Layer Depth), 은닉 노드 수, 드롭아웃 비율, 학습률 등 미분이 불가능한 이산적·연속적 하이퍼파라미터 공간에서 최적의 모델 아키텍처 구성을 자동으로 탐색해 냅니다.

(4) 컴퓨터 비전의 활성 외곽선 모델(Snakes) 및 영상 분할 에너지 최소화

영상 처리에서 객체의 경계선을 찾아내는 활성 외곽선(Active Contour) 모델의 비선형 변형 에너지를 최소화하거나, 마르코프 랜덤 필드(MRF) 기반의 노이즈 제거 및 의료 영상 3차원 분할에서 대역 최소 에너지 상태를 찾아내는 데 성공적으로 활용됩니다.