7.124 시뮬레이티드 어닐링

7.124 시뮬레이티드 어닐링

1. 기본 원리

시뮬레이티드 어닐링(Simulated Annealing, SA)은 금속의 어닐링(풀림) 공정에서 착안한 확률론적 전역 최적화 방법이다. 금속을 고온으로 가열한 후 서서히 냉각하면, 원자들이 열적 요동을 통해 결정 격자의 최소 에너지 상태에 도달하는 현상을 모사한다. 커크패트릭(Kirkpatrick), 젤라트(Gelatt), 벡키(Vecchi)가 1983년에 조합 최적화에의 응용을 제안하였다.

SA의 핵심 특성은 탐색 과정에서 목적 함수를 악화시키는 이동(상향 이동)을 확률적으로 허용한다는 점이다. 이를 통해 국소 최소점에서의 탈출이 가능하며, 충분히 느린 냉각 스케줄에서 전역 최적해에의 수렴이 이론적으로 보장된다.

2. 알고리즘

  1. 초기 해 \mathbf{x}_0, 초기 온도 T_0 > 0을 설정한다.
  2. k = 0, 1, 2, \ldots에 대해:
  3. \quad 현재 해 \mathbf{x}_k의 근방에서 후보 해 \mathbf{x}'를 무작위로 생성한다.
  4. \quad 에너지 차이 \Delta E = f(\mathbf{x}') - f(\mathbf{x}_k)를 계산한다.
  5. \quad 수용 확률:

P(\text{수용}) = \begin{cases} 1 & \text{if } \Delta E \leq 0 \\ \exp(-\Delta E / T_k) & \text{if } \Delta E > 0 \end{cases}

  1. \quad 균일 난수 u \sim U(0, 1)을 생성하여, u < P이면 \mathbf{x}_{k+1} = \mathbf{x}', 아니면 \mathbf{x}_{k+1} = \mathbf{x}_k.
  2. \quad 온도 갱신: T_{k+1} = \alpha(T_k)
  3. \quad 종료 조건 확인

3. 수용 확률과 메트로폴리스 기준

수용 확률 \exp(-\Delta E / T)는 메트로폴리스(Metropolis) 기준에 해당한다. 온도 T가 높으면 상향 이동의 수용 확률이 높아 광범위한 탐색이 이루어지고, T가 낮으면 하향 이동만이 거의 수용되어 국소 탐색에 집중한다.

정상 상태에서 해의 분포는 볼츠만(Boltzmann) 분포에 수렴한다.

\pi(\mathbf{x}) \propto \exp(-f(\mathbf{x}) / T)

T \to 0에서 이 분포는 전역 최소점에 집중된다.

4. 냉각 스케줄

4.1 로그 냉각(Logarithmic Cooling)

T_k = \frac{T_0}{\ln(k + 2)}

Geman과 Geman(1984)에 의해 전역 최적에의 확률적 수렴이 보장되는 스케줄이다. 그러나 냉각이 극히 느려 실용적이지 않다.

4.2 기하 냉각(Geometric Cooling)

T_{k+1} = \alpha T_k, \quad 0.9 \leq \alpha < 1

실용적으로 가장 널리 사용되는 스케줄이며, \alpha = 0.95 \sim 0.99가 통상적이다. 전역 수렴이 보장되지는 않지만, 실용적 성능이 우수하다.

4.3 적응적 냉각

수용률(acceptance rate)을 모니터링하여 온도를 적응적으로 조절한다. 수용률이 높으면 냉각을 가속하고, 수용률이 낮으면 냉각을 둔화시킨다.

5. 근방 구조의 설계

후보 해의 생성 방식은 문제의 성격에 맞추어 설계해야 한다.

연속 변수: 정규 분포 \mathbf{x}' = \mathbf{x}_k + \sigma \boldsymbol{\epsilon}, \boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{I}). 표준 편차 \sigma는 온도에 비례하여 감소시킬 수 있다.

이산 변수: 현재 해에서 하나의 성분을 무작위로 변경하는 연산이 사용된다.

조합 문제: 교환(swap), 삽입(insertion), 역전(inversion) 등의 문제 특화 연산이 설계된다.

6. 수렴 이론

SA의 수렴 이론은 비동차 마르코프 연쇄(inhomogeneous Markov chain)에 기반한다. 로그 냉각 스케줄 T_k = C/\ln(k) (C가 충분히 큰 상수)에서, SA가 생성하는 상태의 분포가 전역 최소점 집합에 수렴함이 증명되어 있다. 그러나 이 수렴은 무한 시간을 요구하며, 유한 시간 내의 성능 보장은 제한적이다.

7. 장점과 한계

장점: 구현이 단순하고, 목적 함수의 미분 가능성을 요구하지 않으며, 비볼록 문제에서 국소 최소점 탈출 능력을 갖는다. 이산 및 연속 변수를 모두 처리할 수 있다.

한계: 수렴이 느리고, 냉각 스케줄과 근방 구조의 선택에 민감하며, 고차원 연속 문제에서는 경사 기반 방법에 비해 현저히 비효율적이다.

8. 로봇 공학에서의 응용

조립 순서 최적화: 다수의 부품으로 구성된 제품의 조립 순서를 최적화하는 조합 최적화 문제에 SA가 적용된다.

센서 배치: 센서의 최적 배치 문제에서 SA가 비볼록 감지 영역 모델과 함께 사용된다.

로봇 설계 최적화: 링크 길이, 관절 배치 등의 이산적 설계 변수가 포함된 로봇 구조 최적화에 SA가 활용된다.

9. 참고 문헌

  • Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). “Optimization by Simulated Annealing.” Science, 220(4598), 671–680.
  • Černý, V. (1985). “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm.” Journal of Optimization Theory and Applications, 45(1), 41–51.
  • Geman, S., & Geman, D. (1984). “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.” IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6), 721–741.

version: 1.0