[6기 신촌 김상훈] Simulated Annealing

안녕하세요. 신촌멤버십 22-2기 김상훈입니다.

이번 포스팅에서는 광역적 최적화 문제에 대한 확률적 알고리즘인 Simulated Annealing에 대해 알아보겠습니다.

 광역적 최적화 문제란 광대한 탐색 공간 안에서, 주어진 함수의 광역 최적해를 구하는 것입니다. 이러한 문제를 해결하기 위해서는 광대한 양의 조합을 모두 탐색해야하고, 그 만큼 많은 시간이 걸리기 때문에 일반적인 Brute Force 방법으로는 해를 구할 수 없습니다. 그러므로 완벽한 해를 구하기 보다는 Simulated Annealing과 같은 방법을 사용하여 근사해를 구합니다.

 Simulated Annealing은 금속학의 냉각과정에서 유래되었는데, 고온 물질의 분자가 식어가면서 점차 안정화되어 가는 과정을 묘사하여 광역적 최적화 문제에 적용한 알고리즘입니다. 그 방법에 대한 핵심 아이디어는 온도가 높을수록 분자의 자유로운 이동이 가능하며, 온도가 낮을수록 점차 안정화 되어 비교적 자유롭지 않은 이동을 한다는 것입니다.

 아래와 같이 어떤 공간에서 가장 낮은 점을 찾는 문제를 가정해 봅시다.

만약 Greedy 방식으로 해를 탐색한다면 지역적 최적점에서 수렴하고, 다른 공간상에 존재하는 광역적 최적점에 도달하지 못하게 됩니다. 지역적 최적점에서 벗어나기 위해서는 어떠한 변수가 필요하게 됩니다. 만약 어떠한 변수에 의해 지역적 최적점을 벗어난다면 광역적 최적점에 다가갈 수 있는 확률은 높아질 수 있습니다.

 Simulated Annealing 에서는 이러한 변수를 온도에 따른 분자이동으로 설명하고 있습니다. 높은 온도에서부터 차츰 온도를 낮추어 가며 최적을 향해가는 탐색을 진행하되, 온도에 따른 확률값에 따라 최적이 아님에도 최적이 아닌 방향으로도 이동을 할 수 있습니다.

(위키디피아 - http://en.wikipedia.org/wiki/Simulated_annealing)

위는 위키디피아에 있는 Simulated Annealing의 Pseudocode 입니다.

요약하면 다음과 같습니다.

* 전체적인 반복문은 일정 온도에 도달하였거나 충분히 좋은 해를 구하였을 때 종료합니다.

* 반복문 내에서는 현재 상태에서 약간 변형된 새로운 상태에 대해 탐색을하고 그 상태에 대한 평가를 합니다.

* 만약 그 새로운 상태가 현재 상태보다 더 최적이라면 현재 상태를 새로운 상태로 변경합니다.

* 최적이 아니라 할지라도 온도에 따른 확률을 적용하여 새로운 상태로 변경할 수 있습니다.

 정리하면 Simulated Annealing은 고온 물질의 분자가 식어가는 모습을 모티브로 하여, 광역적 최적해를 찾는 문제에서 근사 해를 확률적으로 찾아가는 알고리즘입니다. 이를 외판원 문제(Traveling Salesman Problem)에 적용해 보았습니다. NP문제로 알려진 외판원 문제는 Dynamic Programming으로 풀이할 때, 시간복잡도가 O(n² * 2ⁿ)로 정점이 30개가 넘어도 해결할 수 가 없습니다. Simulated Annealing을 사용하면 빠른 시간 내에 외판원 문제의 근사해를 찾을 수 있습니다. 

정점 131개에 대한 근사해를 찾아가는 모습입니다.

정점 2924개에 대한 근사해를 찾아가는 모습입니다.

이상으로 simulated Annealing에 대해 알아보았습니다.

Reference

  - '위키피디아' http://en.wikipedia.org/wiki/Simulated_annealing