anneal vt.

  1. (금속이나 유리를 불에 달궜다가 천천히 식혀) 강화시키다, 담금질하다.
  2. (정신 등을) 단련하다, 강화하다.


Simulated annealing (SA) is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For certain problems, simulated annealing may be more efficient than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.




Simulated Annealing은 아주 어려운 문제를 풀기 위해 점진적으로 그 해(solution)에 가까운 방향으로 이동하되 적은 확률(0.05~0.5%)로 예상되는 해에 아주 먼 방향으로 이동하는 겁니다. 


좀 더 이해하기 쉬운 예로 산오르기를 들겠습니다. 


수백개의 산들로 이루어진 산맥에서 가장 높은 산을 찾고 싶습니다. 그런데 그 산이 어떤 산인지, 가장 높은 산의 높이가 얼마인지 전혀 모릅니다. 그리고 지금 가지고 있는 장비는 고도계 하나 뿐입니다. 그리고 산에는 나무가 아주 울창해서 가장 높은 산은 커녕 어느 방향이 산봉우리인지도 모릅니다. 이러한 상황에서 우리가 할 수 있는 것은 주위를 보고서 현재 위치보다 좀 더 높은 곳으로 향하는 것이 제일 무난한 방법입니다. 그런데 이런 식으로 가면 결국은 한 산봉우리에 올라갈 수는 있습니다. 그런데 그 산봉우리가 가장 높은 산일 확률은 1/(산봉우리의 수) 입니다. 매우 낮은 확률이죠.


시뮬레이티드 어닐링은 가장 높은 산으로 갈 확률을 높이기 위해서 어느 정도 올라가다가 주사위를 굴립니다. 그래서 특정한 수가 나오게 되면 (특정 확률로) 절벽이나 비탈 아래로 미끌어집니다. 어느 정도 미끌어진 뒤에 거기서부터 다시 올라가기 시작합니다. 이와 같이 가끔씩 미끌어지면 어떤 산봉우리에 올라가는데 걸리는 시간은 굉장히 오래 걸리지만 아주 높은 산봉우리에 올라갈 가능성이 훨씬 높아집니다. 이게 무슨 말일까? 계속 살펴보자.


Simulated annealing은 커다란 탐색공간에서 주어진 함수의 전역 최적점 (global optimum) 에 대한 훌륭한 근사치를 찾으려고 하는 전역최적화 (global optimization) 문제에 대한 일반적인 확률적 휴리스틱 (probabilistic heuristic) 접근방식이다. 이 방법은 1983년에 S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, 1985년에 V. Cerny이 각각 동시에 발명한 것이다.

그 명칭과 정신은 야금학(metallurgy)에서 담금질(annealing)에서 따온 것이다. 즉 결정체(crystals)의 크기를 크게하고 결함(defects)을 작게 하려고 금속에 열을 가하고 냉각시키는 속도를 조절하는(controlled cooling) 기술에서 따온 것이다. 열을 가하면 원자(atoms)는 최초의 위치 (내부 에너지의 국소 최적점; local minimum) 에서 떨어져 나가고 더 높은 에너지 상태로 정처없이 방황하게 된다. 서서히 냉각시키면 최초의 상태보다 더 낮은 내부 에너지를 가지는 환경을 찾을 수 있는 기회를 더 많이 가지게 된다.



이러한 개념들은 고체의 물리적인 담금질과 아주 많은 경우의 수를 가진 조합 최적화 (Combinatorial Optimization) 문제 사이의 밀접한 관계에 의거한다. Simulated annealing은 신경망(Neural Network)의 구조를 갖는 것은 아니다. 단지 이러한 개념으로 여러 다른 신경망의 학습과정을 변화시켜줄 수 있다. 실제 많은 신경망 시스템에서 학습한다는 개념은 minimization 과정으로 볼 수 있으며, 그것은 energy function이나 error function에서 downward 방향으로 간다는 것을 의미한다. 하지만 그러한 경우 initial weight 값을 잘못 선택하면 local minimum 값에 빠지고 마는 경우가 생기게 된다. 이러한 문제를 해결하기 위한 방안으로 simulated annealing 개념이 도입되었다.

...... 금속의 담금질(annealing)이란 고체를 녹을 때까지 가열하고 난 후 그것을 완전한 격자 상태의 결정체가 될 때까지 식히는 물리적인 과정이다. 이런 과정 중에 그 고체의 자유 에너지(free energy)는 최소화된다. 오래 전부터의 경험에 의하면 고체화되는 과정에서 지역 최소점에 빠지지 않도록 하기 위해서는 조심스럽게 서서히 식혀야 한다.

...... 금속재료 등을 가열한 후 서서히 냉각시켜 내부의 결함을 없애는 방법과 유사하여 시뮬레이티드 어닐링 (simulated annealing) 이라 부른다. 여기에서 중요한 것은 온도를 낮추어가는 방법이다. 온도를 너무 급속히 낮추면 평행상태를 이루어도 최소 에너지 상태에 도달할 확률이 적고, 너무 천천히 낮추면 최소 에너지에 도달할 확률은 커지지만 많은 반복을 필요로 하므로 시간이 많이 걸린다. ......

조합 최적화 (combinatorial optimization) 문제에서도 이와 유사한 과정을 정의할 수 있다. 이 과정은 잠재적으로 매우 많은 해결방안 중에서 최소의 비용이 드는 해답을 구하는 문제로 공식화될 수 있다. 우리는 여기서 비용 함수(cost function)와 자유 에너지 사이의 관계, 그리고 해답과 물리적인 상태의 관계를 정립함으로써 물리적인 담금질 과정의 시뮬레이션에 의거한 조합 최적화 문제의 해결 방안을 소개할 수 있는데 이러한 방법이 바로 Simulated Annealing이다.

이 방법의 두드러진 특징은 폭넓은 응용 가능성과 최상에 가까운 해답을 얻을 수 있다는 점이다. 그러나 이 방법에도 상당히 큰 단점이 있다. 상당히 좋은 해답을 얻는데 걸리는 계산 시간이 엄청나게 길다는 점이다. 그러나 시뮬레이티드 어닐링 알고리즘의 구현시 필요한 엄청난 시간은 대규모 병렬처리 (massively parallel execution) 를 기반으로 하는 계산 모델을 사용함으로써 상당히 줄일 수 있는데 그러한 모델 중의 하나가 바로 볼쯔만 머신(Boltzmann Machine)이다.


이 테크닉은 Informed Search의 한 종류이며, (따라서 평가 함수를 잘 만들어야한다)

일종의 Greed Method인 Hill Climbing Method에 Heuristics을 적용한 것이다.

그 Heuristics에 대해서 알아보자.


일반적으로 Hill Climbing Method는 그저 현재 상태보다 다음 상태가 좋으면 이동하게 된다. 이는 Local Maxima (혹은 Minima)에 빠지기 쉽다. 

어떤 공이 언덕(Hill)을 내려가는 예를 보자.



시작 위치에서 공을 굴리면, 공은 Local Minima에 빠질 것이다. (가속도는 생각하지 말도록 하자) 하지만 우리가 원하는 것은 Global Minima에 공이 도달하는 것이다. 하지만 Hill Climbing Method에 의해서는, 공은 현재 위치보다 높은 곳으로는 이동하지 않기 때문에, 위 그림과 같은 상황이 발생한다.


이 때, 이 언덕 전체를 살짝 흔들어주면 어떻게 될까? 공이 Local Minima를 겨우 빠져 나갈 정도로 흔들어 준다면, 공은 Global Minima에 도달할 수 있을 것이다. 이렇게 흔들어 주는 것이 Simulated Annealing에 적용된 Heuristics이다.


그럼 어느 정도로 흔들어야 하는가? Simulated Annealing에서는 처음에는 세게, 그리고 시간이 지날수록 점점 그 강도를 약하게 할 것을 권하고 있다. 그리고 그 세기가 0이 되고 공이 더이상 움직이지 않는다면, 그 순간을 종료 시점으로 삼고 있다.


이 흔들어주는 세기는 담금질 기법에서 냉각 속도에 해당된다.


흔드는 것은 어떻게 구현하는가? Temperature에 비례하는 확률로 공을 좋지 않은 방향으로 보내는 것이다. 위 그림에서, 공이 Local Minima에 빠졌을 때, 확률적으로 언덕을 올라가게 한다. 물론 올라가는 방향이 제일 시작위치 쪽일 수도 있다. 하지만 그쪽은 훨씬 높기 때문에, 올라가다가 도로 내려올 확률이 높다. (기본 방향은 아래쪽이며, 가끔씩 확률적으로 올라가므로)

물론 오른쪽으로 올라가다가도 그냥 내려올 수도 있으나, 적어도 왼쪽 언덕을 넘는 것보다는 오른쪽 언덕을 넘는 확률이 더 높을 것이다.


Temperature의 값은 시작할때 최대로, 그리고 이동할 때마다 일정 수치를 감소시키면 될 것이다. 이것은 나의 생각이다. 문제에 따라 달라질 수 있으며, 중요한건 갈수록 줄어들면 된다는 것.


반대의 경우인, 산을 등반하는 경우에도 그대로 적용된다. 이 때는 기본값은 올라가는 것이고, 가끔씩 확률적으로 내려간다.


다음은, Artificial Intelligence - A Modern Approach,

출판: Prentice Hall,

저자: Stuart Russell & Peter Norvig

라는 책에 있는 Simulated Annealing의 알고리즘을 약간 C 스타일로 내가 보기 편하게 만든 것이다.



Schedule[t]라는 것은 Temperature를 정해주는 함수이다.

VALUE[] 라는 것은 평가 함수의 값이다. 위의 공이 내려가는 문제에서는 공의 높이가 목표 지점과 가까운 정도가 될 것이다. 

MAKE-NODE() 함수는 트리 구조 같은데서 노드를 만드는 것이다. 트린지 그래픈진 모르겠지만 중요한건 처음 시작 지점을 현재 위치로 잡는다는 의미 뿐일 것이다.

 

e는 아마 오일러수 같다. 이는 대략 2.718281828459045235360287471352662497 의 값이다.


첨부 파일은 내가 직접 만든 Hill Climbing Method와 Simulated Annealing 방식으로 가장 높은 곳을 찾아가는 등산 프로그램이다. 제대로 된건지 모르겠다.


예제.txt 파일은 위의 예제보다 좀 더 나중에 작성 된 것으로, 완벽하진 않지만 흐름은 더 잘 보여주는 것 같아 첨부한다. 이 예제는 대충 수도코드 비스므리한 알고리즘 수준이며, 이것을 바로 컴파일하면 안 된다.


Annealing - 담금질. 쇠를 연마하는 작업이라고 한다. 사극이나 전쟁 영화에서 나오는, 검 같은 걸 만들 때, 뜨겁게 달군 쇳덩어리를 망치로 때리면서, 한번씩 찬물에 담근다. 그러면 더 단단해진다나? 이 찬물에 담그는 과정이 담금질이다. Simulated Annealing은 바로 이것에서 휴리스틱을 배워온 것!


뜨겁게 달궈서 두드리는 것.. 이것을 greedy(혹은 exploit)한 측면(위의 공 예제에선 낮은쪽으로 가는 것)으로 본다면, 찬물에 담그는 것은 뭔가 모험적인, explore한 측면(위의 공 예제에선 높은 곳으로 이동하는 것)이다. 항상 뜨거운 상태만 유지하는 것이 아니라, 가끔 당장은 안좋아보이는 방향으로도 가보는 것이 결과적으로는 좋아 진다는 것이다.


인공지능 기법은 이 exploit과 explore를 적절하게 조절해야 성공한다고 한다.


Temperature는 실제 담금질에서 쇳덩어리의 온도이다. 처음엔 쇳덩어리가 무지 뜨겁다. 이 때는 자주 찬물에 담가주다가 쇳덩어리가 거의 식어가면 더 이상 안담궈도 되는 것이다. 이 휴리스틱이 그대로 Simulated Annealing에 적용되어, 처음에는 Temperature가 높아 자주 explore를 하다가, 시간이 지날수록 차츰 exploit 하게 되는 것이다.


그리고 저 공식! 오일러 상수 들어가는거

저게 열역학에서 나오는 공식이란다 -0-; 그 쪽 휴리스틱을 적용시키는것!


[출처] Simulated Annealing|작성자 임경업



References


티스토리툴바