부분적인 해, 근인 Local optima를 탈출하여 Global optima를 찾기 위해 쓰이는 MonteCarloMethod 의 일종. 어떤 문제의 답을 찾기 위해서 사용한 알고리즘이 반드시 Global optima를 찾아 내는 것이 아니라 Local optima로 수렴할 가능성이 있을 때, 그 state에서 최선의 것이 아닌 것도 선택할 수 있게 함으로써 Local optima를 탈출할 여지를 준다.
Artificial temperature를 사용하여, 먼저 high temperature를 줘서 시스템을 Hill Climbing과 유사하게 움직이게 한 후, 천천히 온도를 낮춰주어 다른 방향으로도 움직일 확률을 낮춰준다. 그러면 처음에는 매우 랜덤하게 이리저리 움직이다가, 결국 방향을 하나 잡아서, Hill Climbing하게 된다.
더 나쁜 답을 선택할 확률을 허용한다는 점에서, 흔히 Greedy method와 비교된다.
쉬운 설명 ¶
어떤 외계의 혹성에 스타게이트를 통해 갑자기 순간이동된 탐사대가 있었다. 그들은 그 혹성의 면적이 얼마나 되는지도 -- 심지어 무한대인지도 -- 모른다. 그들의 임무는 그 혹성에서 가장 낮은 곳의 깊이를 측정하는 것이었다. 하지만 문제는 혹성 전체가 짙은 안개에 깔려있어서 현재 위치의 깊이 밖에 알 수가 없다는 것이고, 또, 그곳에 머무를 수 있는 시간이 유한하기에 느긋하게 모든 곳을 다녀볼 길이 없다는 것이었다.
한 대원이, "한 발자국 움직여서 만약 밑으로 더 내려가면 그 쪽으로 가고, 그게 아니고 더 올라가게 되면 다른 쪽을 택하도록 하죠"라고 말했다. 대장 왈 "그렇게 되면 별로 깊지도 않은 계곡에 들어갔을 경우 거기가 제일 깊은지 알 것 아닌가?"라고 반문했다.
한 똘똘한 대원이 SimulatedAnnealing이라는 방법을 제안했다. 간혹 "올라가는 멍청한 짓"도 하긴 하되, 시간이 갈 수록 그 확률을 줄이자는 것이었다. 무슨 이야기인고 하니, 임의로 한 발자국 움직여서 "더 낮은 곳"이라면 그리로 가고, 만약 "더 높은 곳"이라면 우리가 들고 다니는 컴퓨터로 확률 계산을 하되 시간이 갈수록, 우리의 위치가 더 낮을수록 "낮은 확률"이 나오도록 해서, 실제로 주사위를 던지든가 하는 것으로 그 확률 안에 들어가면 그곳이 비록 더 고지대일지라도 그리로 이동하고, 아니면 다른 곳으로 발걸음을 옮기자는 말이었다.
일상생활에의 적용 ¶
어떤 문제에 대한 안정된 해결책을 가지고 있을 때, 그 방법만 계속 고수해서는 발전은 없다. 변화를 시도하라. 몇 번의 한번꼴로 다른 방법으로 문제를 해결하려고 노력해 보라. 때로 기존의 방법보다 더 나은 방법을 찾을 수 있을 것이다.
역시 휴리스틱스에 GeneticAlgorithm이라는 게 있는데, 생물이 교배하고, 돌연변이하고 세대를 거치며 진화하는 모델을 프로그램에 적용한 것이다. 이름하여, "진화하는 프로그램". 김창준은 이걸로 VLSI 디자인 관련 프로그램을 만들었다 -- 98년도쯤 됐었다. 재미는 있다. 하지만 젊은 사람이 할 짓은 아니라고 생각하게 되었다. 젊은 사람은 좀더 치열하고 정밀하며 견고한 방법을 먼저 익혀야, 저런 '유혹'이 와도 알맞게 이용할 수 있다.
SimulatedAnnealing을 물리학적인 최적화방법이라고 말한다면 GeneticAlgorithm은 생물학적인 최적화방법에 해당한다. 즉, 가장 낮은 곳을 찾는 문제에서 SimulatedAnnealing은 물체를 톡톡쳐서 높은 곳으로도 가게 만드는 방법이다. 이것은 비교적 단순한 계에서는 강력한 방법이 된다. 예를 들어 Si 원자가 약 100 개 미만 뭉쳐있는 나노클러스터의 구조를 최적화한다면, 이 방법이 아마도 가장 강력하고 효율이 좋은 방법이 될 것이다. 그러나 계의 크기가 증가하면 SimulatedAnnealing 의 신뢰도는 급격하게 감소한다. 수백개의 Si 원자가 뭉쳐있기만 해도, 그 최적 구조를 찾아내기 위해서는 GeneticAlgorithm 외에는 대안이 없다. 아마도 생물체가 유전자를 사용하여 차 세대를 만들어내는 그 기저에는 이러한 이유가 있을 거라고 생각한다.
SA 에서는 'Solution Space 가 과연 계곡 처럼 되어 있나?', '확률에 따른 accept 함수를 쉽게 만들 수 있나?', '초기 온도는 과연 어떻게 잡아야 하는가?' 같은 실제 구현상의 문제들이 있습니다. hill climbing 으로 과연 local minima 를 탈출할 수 있는지가 상당히 의심스럽고 -_-; 확률에 따른 accept 함수도 만들기가 상당히 어렵고, 초기 온도 또한 설정하기가 애매합니다. 또한 각종 변수를 대부분 실험적으로 정하고 랜덤하게 수해하기 때문에 과학 실험의 기본인 '실험 결과의 재현'이 상당히 어렵습니다. -_-; 물론 확률에 따른 accept 를 사용하지 않아도 매번 실행할 때마다 seed 를 다르게 주고 3박 4일간 수만번씩 돌려보면 괜찮은 결과가 나올 수는 있을 것입니다. 그래서 보통 '이 실험 결과는 10번의 독립적인 실행 결과를 평균낸 것이다..' 라고 하기는 하지만 '이 작업을 3박 4일간 수행하였다...' 같은 말이 빠져있죠. 
SA 로 풀 수 있는 문제라면, 즉 solution 을 인코딩 할 수 있고 그 solution 을 평가할 수 있는 cost function 이 있다면 GA 로 바꿀 수 있습니다. 위에서 언급한 SA 의 문제로 solution encoding 이 커지면 solution pertubation(흔들어주기 -_-;)에 문제가 있는데 이것도 여러가지 기법을 사용해서 처리를 하기는 합니다. SA 의 경우에도 우성 형질을 넘겨주기 위에서 여러가지 작업을 수행합니다. SA 로 하지 않고 GA 로 해서 더 좋은 결과가 나타날 수는 있겠지만 그건 정말 '그 때 그 때 달라요...'라고 생각합니다. -_-;
SA 나 GA 같은 메타 휴리스틱은 정말로 '그 때 그 때 달라요...'기 때문에 최적해를 찾을 수도 없고 일반적인 휴리스틱을 만들어내기 어려운 경우가 아니면 정말 조심스럽게 사용하는 것이 좋다고 생각합니다. -.- --asiawide
