PS: 뉴비를 위한 Simulated Annealing 입문 (1)

INTRO

PS에서 우리가 푸는 평범한 알고리즘 문제들은 결정론적 문제입니다. 이 말은, 이미 출제자에 의해서 밝혀진 고정된 시간 안에 동작하는 해법이 있고, 우리는 그 해법을 찾아서 구현하기만 하면 된다는 뜻입니다. 그렇지만 NYPC 예선에서 나오는 출력 파일 문제라던가, IOI의 "그 문제"인 nowruz로 대표되는 Output Only 문제,  Topcoder에서 진행되는 Marathon Match 등에서는 완벽한 최적해를 찾아내는 것이 불가능하기도 합니다. 이럴 때에는 많은 사람들이 휴리스틱 알고리즘을 사용합니다. 사실 휴리스틱 알고리즘이라고 하면 어떤 특정한 알고리즘을 지칭하는 것이 아닌데, 보통 저는 휴리스틱을 완전 탐색을 할 때 속도 향상을 위해 사용하는 일반적인 휴리스틱과 전역에서 최적점과 가까운 근사해만을 찾기 위해 사용하는 메타휴리스틱 알고리즘으로 나누어 생각하는 편입니다. 널리 알려진 메타휴리스틱 알고리즘에는 타부 서치(Taboo Search)와 유전 알고리즘(Genetic Algorithm)이 있는데, 오늘은 그 중 하나인 담금질 기법(Simulated Annealing)에 대해서 다뤄보려고 합니다.

그래서 시뮬레이티드 어닐링이 뭔데요?

시뮬레이티드 어닐링이 과연 뭘까요? 담금질 기법이라는 이름만 들어서는 그 작동 과정을 이해하기가 쉽지 않습니다. TMI를 좀 하자면, 제가 알기로는 이 명칭이 오역 등으로 인해서 조금 원 의미와 다르게 해석되었다고 알고 있습니다. 하여튼 시뮬레이티드 어닐링의 작동 과정을 한 마디로 하면, 엔탈피를 감소시켜 가면서 최적해에 다가가는 과정이라고 할 수 있습니다. 갑자기 PS 하다가 뜬금없이 엔탈피가 왜 튀어나오나 하시겠지만, 시뮬레이티드 어닐링은 실제로 엔탈피가 감소되는 과정을 정확히 따라면서 최적해를 찾습니다. 

우리가 어떤 문제에서 최적해를 찾으려면, 일반적으로 다음과 같은 과정을 거칠 겁니다. 가능한 해의 후보를 구하고, 그 후보를 평가하여, 그 중 가장 좋은 해를 찾습니다. 다익스트라, dp, 디닉 등을 통해 최적해를 구하는 거라면 후보를 평가할 필요도 없이 바로 구해지겠고, 백트래킹에서 일반적인 휴리스틱을 사용한다면 봐야 하는 후보의 집합을 최대한 줄이는 방법을 사용하겠죠. 시뮬레이티드 어닐링을 비롯한 메타휴리스틱 알고리즘은 최적해를 찾기 위해 보아야 하는 최소한의 해의 집합조차 보지 않습니다. 대신 그 중 "좋은 해가 있을 것 같은" 일부 지역만을 탐색하게 됩니다. 이를 구현하는 방식은 다양하겠지만, 시뮬레이티드 어닐링은 다음과 같이 행동합니다. 현재 상태와 인접한 상태를 하나 구하고, 그 상태로 변할 때 얼마만큼 이득인지/손해인지를 판단한 다음, 얻을 이득과 손해의 정도에 따라 확률적으로 그 상태로 이동합니다. 여기서 인접한 상태란, 현재의 상태를 국소적으로 바꾸어서 만들 수 있는 상태입니다. 예를 들어서 TSP에서는, 여행하는 도시의 순열 중에서 임의의 인접한 두 도시를 교환하는 것이 되겠고 3SAT에서는 변수 하나의 참거짓을 바꾸는 것이 되겠죠. 꼭 이렇게가 아니라 국소적인 변화라면 뭐든지 괜찮습니다. 시뮬레이티드 어닐링은 이 과정을 반복함을 통해서 최적해를 향해 나아가고, 와중에 더 나빠지는 해에 대해서도 가끔씩은 탐색을 해보면서 지역 최적점을 피해가려 노력합니다.

어떻게 돌아가나요?

이 단계들을 조금 더 자세히 설명하면 다음과 같이 되겠네요.

1) 인접 상태 정의
문제를 풀기 위해서 가장 먼저 해야 하는 것은 상태와 인접 상태를 정의하는 것입니다. 인접 상태를 하나 찾는 연산은 여러 번 반복적으로 수행해야 하기 때문에 찾는 것이 오래 걸려도 안 되고, 너무 많이 변하면 최적점으로 수렴하기 힘들기 때문에 말 그대로 최대한 조그맣게 잡아야 합니다. 또한 어떤 상태에 대한 인접 상태는 여러 개가 있는데, 이 여러 개중에서 가능한 무작위하게 하나를 잡는 것도 문제입니다. 그러나 실제로는 문제를 보면 대충 어떻게 상태를 정의해야 할지는 감이 잡히기 때문에, 어떻게 이동할까만 잘 생각해보면 됩니다. TSP에서 임의의 두 정점 방문 순서를 교환하는 것 보다는 인접한 두 가지를 교환하는게 더 효율이 좋겠죠.
여담으로, 어떠한 방식으로 랜덤하게 이동하느냐는 굉장히 큰 효율 변화를 일으킵니다. 넓게는 해를 변형시키는 방법 자체를 변형시킬 수도 있고, 좁게는 더 균일한 랜덤 함수를 사용할 수도 있습니다. 특히 실수를 사용하는 문제의 경우 (C++에서) rand 함수로 비비는 것 보다는 mt19937을 사용하는 것이 생각보다 많은 차이를 불러일으킵니다.

2) 평가 함수 정의
모든 휴리스틱에서 필요한 바로 그 함수입니다. 최적해를 향해 가려고 한다면, 뭐가 어찌 됐던 간에 이 해가 얼마만큼 최적해에 가까운지를 알려줄 수 있는 방법이 필요합니다. 이를 평가 함수라고 부릅니다. 일반적인 문제에서는 최소화/최대화 하고 싶은 바로 그 값이 평가 함수가 되기 때문에 큰 문제가 없지만 문제가 여러 개의 특정 제약 조건을 반드시 만족시키는 하에서 무언가를 최적화 시켜야 한다면 그 때는 그 제약 조건들에 대해 얼마만큼 가중치를 둬서 진행을 시킬 건지에 대한 고민 또한 해야 할 겁니다.

3) 이동
사실 이 과정은 고민할 필요가 없습니다. 시뮬레이티드 어닐링에서 상태와 평가 함수가 정의되었다면, 이 확률에 따라 이동할 확률이 결정됩니다. e^((e1-e2)/kt), 매우 간단합니다. e1은 현재 에너지, e2는 나중 에너지, k는 볼츠만 상수, t는 현재 온도입니다. "에너지"는 상태의 평가 함수 값입니다. 시뮬레이티드 어닐링이 에너지를 줄이는 방향으로 상태를 이동시키는 알고리즘이라서 이런 이름을 씁니다. 볼츠만 상수인 k는 말 그대로 조절할 수 있는 상수이고, t는 후술할 온도입니다. 만약 상태가 더 나아진다면 (에너지가 줄어든다면), e1-e2>0이므로 확률이 1을 넘어 반드시 그 방향으로 이동합니다. 만약 상태가 악화된다면 (에너지가 증가한다면), 위에서 계산한 확률에 의거하여 이동하게 됩니다. 결과적으로는 에너지가 줄어드는, 즉 더 좋은 해가 있는 방향을 찾아서 이동하게 되겠죠.

4) 온도 감소
위에 써놓은 내용들 중 시뮬레이티드 어닐링의 핵심적인 부분은 확률을 결정하는 식이지만, 온도 개념을 제외하면 사실 어느 메타휴리스틱에나 다 비슷하게 있는 부분이기도 합니다. 시뮬레이티드 어닐링에서 온도는 매우 중요한 역할을 합니다. 좀 직관적으로 설명하자면 마치 담금질을 할때 점점 식히는 것처럼, 해를 탐색하는 초기에는 많은 곳을 뛰어다니면서 어느 곳이 전역 최적에 가까울지를 봐야 하지만, 어느정도 전역 최적점에 대한 "각"이 날카롭게 선 후에는 그 안에서 조금이라도 더 나은 해를 찾기 위해 세밀한 탐색을 진행해야 합니다. 시뮬레이티드 어닐링은 이를 온도의 감소라는 우아한 방식을 통해 구현합니다. (좋은 비유는 아니지만) 마치 경사하강법에서 나중으로 갈수록 이동하는 길이가 줄어들듯, 시뮬레이티드 어닐링에서는 위에서 설명한 인자인 온도 t가 감소하면서 현재 해에서 더 에너지가 높은 해로 이동할 확률이 점점 줄어들게 됩니다. 나중으로 갈 수록 위험을 감수하기는 더 힘들어지는 것이죠. 실제 구현에서는 한 사이클이 돌아갈 때마다, 약 0.9995~0.99999 내외로 지정되는 온도 감률이 현재 온도에 곱해지게 됩니다. 

시뮬레이티드 어닐링은 이 네 단계를 계속해서 반복하면서 수행됩니다. 이 과정을 특정 횟수만큼 반복하거나 만족스러운 해가 나올 때 까지 진행하고 종료하면 됩니다. ps에서 사용한다면 반복하는 횟수를 TLE가 나기 직전까지 잡으면 될 것이고 오프라인에서 진행되는 output only 문제에서는 시간에 상대적으로 구애받지 않고 돌려도 되겠죠. 
시뮬레이티드 어닐링은 유전 알고리즘에 비해서 메모리와 시간을 상대적으로 덜 사용하면서도 나름 괜찮은 해법에 굉장히 빠른 속도로 접근하기 때문에 비교적 사용하기 용이합니다. 또한 최적해가 어느 모양이 될 것이라는 확신이 있다면 처음에 그 모양으로 초기 상태를 지정해 준 다음 알고리즘을 작동시켜도 효과가 괜찮습니다. 

다음 글에서는 실제 문제를 해결해 보면서 시뮬레이티드 어닐링이 어떻게 작동하는지 살피도록 하겠습니다.