출처:

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

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

시뮬레이티드 어닐링은 스코트 커크패이트릭 (Scott Kirkpatrick), 젤라트 (Gelatt) 와 베키 (Vecchi) [KIR83] 등에 의해 처음 제안된 방법으로 조합 최적화 문제와 관련하여 소개되었다 [KIR82, KIR83, KIR94]. 또한 1985 년에 체르니 (Cerney)[CER85] 에 의해 독립적으로 연구 발표되었다. 이러한 개념들은 고체의 물리적인 담금질과 아주 많은 경우의 수를 가진 조합 최적화 문제 사이의 밀접한 관계에 의거한다.

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


시뮬레이티드 어닐링 알고리즘의 응용 예

EUR100 [AAR89] 은 유럽의 100대 도시들을 연결하는 순회판매원 (TSP) 문제인데 상호 대칭적이고 2차 평면적인 유클리트 거리를 다룬다. 거리 행렬 (distance matrix) 의 요소들은 테이블에 주어진 지리학상의 좌표로 계산되어 진다.
<그림 1> [AAR89] 은 EUR100 문제의 해결을 위하여 수행된 시뮬레이티드 어닐링 최적화 과정의 단계적 발전도를 보여준다. <그림 1> 의 (a) 에서 보는 바와 같이 처음의 해답은 100개 도시의 임의적인 나열로서 콘트롤 변수인 c 의 값이 17.85 인 경우인데 최적의 값과는 거리가 멀다. 이 해답은 매우 혼란스럽고 또한 매우 큰 엔트로피 (entrophy) 를 가지며 총 여행거리는 무려 129.965 나 된다. <그림 1> 의 (b) 와 (c) 는 콘트롤 변수인 c 가 각각 4.46 과 1.28 로 총 여행거리가 각각 68.153 과 33.048 로 점차 줄어들고 있다. 마지막으로, 거의 최적인 해답은 <그림 1> 의 (d) 와 같이 얻어지는데 이때의 c 값은 0.06 이다. 이 경우 패턴이 겹치지 않고 엔트로피가 매우 작으며 총 여행 거리가 앞의 경우들보다 훨씬 적은 21,456 에 불과하다.

사용자 삽입 이미지


이 문제의 경우 최소 여행 거리는 21,134 이고 이 경우의 여행 루트는 <그림 2> [AAR88b] 에 나타나 있는데 직선의 연결은 최적의 여행 경로를 나타낸다. CYBER-205 컴퓨터에서 최적의 여행 경로를 구하는데 59.5 CPU 초가 걸렸다.

사용자 삽입 이미지

http://www.aistudy.com/neural/simul_kim.htm
http://en.wikipedia.org/wiki/Simulated_annealing
신고

'research > distributed algorithm' 카테고리의 다른 글

Matlab-General simulated annealing algorithm open source  (0) 2008.02.10
fuzzy c-mean  (0) 2008.02.10
Global Optimization  (0) 2008.02.08
Important Referencess for Wireless Sensor Networks  (0) 2008.02.01
[펌] Simulated Annealing  (1) 2008.01.29
[펌] k-means clustering  (0) 2008.01.29
Posted by 나마스떼

댓글을 달아 주세요

  1. AGEN BOLA 2012.08.25 03:26 신고  댓글주소  수정/삭제  댓글쓰기

    AGEN BOLA BV : 늦었지만 네이버로 연락드렸습니다. ^^



티스토리 툴바