Simulated Annealing
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)) 에서 떨어져 나가고 더 높은 에너지 상태로 정처없이 방황하게 된다 ; 서서히 냉각시키면 최초의 상태보다 더 낮은 내부 에너지를 가지는 환경을 찾을 수 있는 기회를 더 많이 가지게 된다..... ....... (Wikipedia : Simulated annealing)
이러한 개념들은 고체의 물리적인 담금질과 아주 많은 경우의 수를 가진 조합 최적화 (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) 이다. .... (김대수 1992)
term :
신경망 (Neural Network) 지도학습 (Supervised Learning) 시뮬레이티드 어닐링 (Simulated Annealing) 볼쯔만 머신 (Boltzmann Machine) 조합최적화 (Combinatorial Optimization) 병렬분산처리 (Parallel Distributed Processing)
paper :
유전자 알고리즘과 시뮬레이티드 어닐링을 이용한 활성외곽선 모델의 에너지 최소화 기법 비교 (Comparison of Genetic Algorithm and Simulated Annealing Optimization Technique to Minimize the Energy of Active Contour Model) : 박선영, 김명희, 박주영, 컴퓨터그래픽학회, 1998
site :
Parallel Simulated Annealing ( F. H. Allisen Lee & Dyke Stiles , Utah State)
Simulated Annealing Information, Taygeta Scientific Inc. [Monterey]
Ensemble Based Simulated Annealing (Richard Frost , San Diego)
Adaptive Simulated Annealing by Lester Ingber
COSA: Cooperative Simulated Annealing (Oliver Wendt , Frankfurt)
Parallel Simulated Annealing ( Ralf Diekmann , Paderborn)
Parallel Simulated Annealing for T3E
CalTech Adaptive Simulated Annealing (ASA) site.
Collection of Computer Science Bibliographies has many references on simulated annealing
parSA, Parallel Simulated Annealing Library