편집토론문서 역사

담금질 기법

(Simulated annealing에서 넘어옴)


개요

담금질 기법은 전역 최적화 문제에 대한 일반적인 확률적 메타 알고리즘이다. 이 기법은 광대한 탐색 공간 안에서, 주어진 함수의 전역 최적해에 대한 좋은 근사를 준다. 커크패트릭, 젤라트, 베키가 1983년에 고안했다. 보통 영어를 그냥 읽어서 시뮬레이티드 어닐링이라고 부른다.

담금질 기법이라는 말은 금속 공학의 담금질(quenching)에서 왔는데, annealing의 오역이다. 풀림은 금속재료를 가열한 다음 조금씩 냉각해 결정을 성장시켜 그 결함을 줄이는 작업이다. 열에 의해서 원자는 초기의 위치(내부 에너지가 극소점에 머무르는 상태)로부터 멀어져 에너지가 더욱 높은 상태로 추이된다. 천천히 냉각함으로써 원자는 초기 상태보다 내부 에너지가 한층 더 극소인 상태를 얻을 가능성이 많아진다.

SA 알고리즘은 해를 반복해 개선함으로써, 현재의 해 근방에 있는 해를 임의로 찾는데, 그때에 주어진 함수의 값과 전역 인자 T 가 영향을 준다. 그리고 앞에서 기술한 물리 과정과 비슷한 원리로. T(온도)의 값은 서서히 작아진다. 따라서, 처음에는 T가 크기 때문에 해가 크게 변화하지만, T가 0에 가까워짐에 따라 변화가 줄어든다. 처음은 간단하게 비탈을 올라갈 수 있으므로, 등산법으로 문제가 되는 지역 최적점에 빠졌을 때의 대책을 생각할 필요가 없다.

Hill Climbing과 비교하였을때, Simulated Annealing기법은 항상 최적의 해만 찾아가기 위해서 노력하는 힐 클라이빙과는 다르게 잘못 된 선택을 종종함으로 현재의 상태를 더 그복할 수 있는 좋은 방법을 찾아간다는 점에서 차별점이 있다.

의사 코드

모든 경우의 수를 탐색하지 않고 최적의 해를 찾는 방법이 바로 담금질 기법이다. 하지만 이 담금질 기법의 문제점이 바로 적당한 Step 사이즈를 결정하는 것이다. Step의 사이즈가 작으면 최적화의 방법을 당연히 찾을 것이나, 사이즈가 작으면 작을 수록 무작위로 모든 경우 수를 해보는 것과 점점 차이가 없어진다.

담금질 기법의 원문을 자주 보거나 번역판을 보면 온도라는 말과 Frozen 즉 냉각이라는 말이 자주 나온다. 이것은 이 기법이 담금질 기법과 비슷하기 때문에 같은 개념으로 설명하기 위한 것이지 절대 이것이 정말 온도나 냉각을 의미하는 것이 아니라 경우의 수를 높여서 더 안좋은 결과가 나오는 것을 온도의 상승으로 보고, 경우의 수의 조합을 좋게 해서 온도의 하락으로 보고 설명을 하는 것이다. 온도가 완전히 떨어진 경우 Downhill의 최저점이 우리가 찾는 최적의 조합이 되는 것이다.

이러한 최적의 해를 향하게 하는 온도, 얼마나 온도를 내릴지, 어느 상태에 도달하면 멈출지와 같은 문제들은 경험적으로 찾아야 하는 Hyper Parameter이다.

기본적으로 알고리즘은 다음과 같다.

  1. new state으로 변하는 선택을 한다.
  2. 만약 new state로 가는 선택이 더 좋은 선택이라면 그 선택으로 이동한다.
  3. 만약 new state로 가는 선택이 더 안 좋은 선택이면 일정한 확률로 그 선택으로 이동한다.
begin
Get an initial solution S; //  s ← s0; e ← E(s) 초기값을 설정한다.
Get an initial temperature T>0; // 초기 온도값을 설정함, 예) T=1000
while not yet "frozen" do  // 최적의 경우를 찾을 때까지 즉 온도가 완전히 내려 갈때까지 프로그램을 Loop한다.
   for 1<= i <= P do       // P=nk 즉 Step의 사이즈가 되고 k는 주어진 종류를 n은 우리가 결정하게 된다. 즉 STEP사이즈를 결정하게 된다.
   Pick a random neighbor S' of S; // 임의로 선택한 솔루션 S' 과 기존의 솔루션 S를 선택한다.
   ∆ ← cost(S')-cost(S); // 기존의 솔루션과 새로운 솔루션을 가격의 차 즉 최적화의 값의 차를 만든다.
                          // ∆ ← area(S')-area(S), 돌을 예를 들면 면적이 크기가 효율성의 차이이다.
   /* downhill move */
   if ∆ <= 0 then S ← S' // S'의 값이 작으면 즉 차지하는 면적이 작고, 더 효율적으로 배치 되었으면,
                          // 이것이 현재까지의 최적화가 되고 이것을 온도가 내려간다. Downhill로 표현한다.
   /* uphill move */
   if ∆ > 0 then S ← S' // S'의 값이 크면 즉 차지하는 면적이 크고, 더 비 효율적으로 배치 되었으면, 이것을 온도가 올라간다.
                         //  uphill로 표현한다.
T ← rT; // 한가지 경우의 수를 처리 했었므로 한 단계 줄어 들게 되면 다음 반복을 진행한다.
return S    // 프로그램이 마무리 되면 우리가 찾는 최적화의 답을 리턴하고, 정확히 최적화의 답을 찾았으면 이것을 Global Optimization 즉 모든 경우의 수중에서 가장 최적화된 것이다.
end

여기서 원래의 SA(Generic Simulated Annealing Algorithm)은 여러가지 찾는 속도나 사용하는 메모리의 경우에 대하여 문제점이 있다. 하지만 이 아이디어 자체는 모든 분야에 대하여 적용이 가능하다. 임의의 경우의 수가 많은 경우 정해진 조건에서 대용량의 최적화를 찾을 때 유용하게 사용이 된다.