1. A*의 한계
앞에서 언급한 A* 알고리즘은 68년에 나왔지만 optimality와 completeness를 모두 만족하는 특성과 더불어 휴리스틱 함수를 잘 정하는 경우 무척 빠른 속도로 답을 구할 수 있다는 특성으로 인해 아직까지도 널리 쓰이는 알고리즘이다. 그러나 이 알고리즘 역시 시간 복잡도가 지수적으로 증가하는 모양새를 하고 있기 때문에 문제의 크기가 커질수록 문제를 푸는데 드는 시간은 기하급수적으로 늘어난다.
이를테면 스타크래프트에서 A*를 이용해 길을 찾는다고 해보자. 제일 작은 크기의 맵인 64x64만 하더라도 기본 단위의 타일 숫자만 4096개이며, 실제 길 찾기에 사용되는 더 정교한 path map으로 치자면 훨씬 더 커진다. 맵 끝에서 맵 끝으로 마린 한 부대가 이동한다 해보자. 그냥 아무 생각 없이 마린 전부에게 A* 알고리즘을 그대로 적용해서 길을 찾으려 한다면, 스타크래프트는 아마 실시간 RTS 딱지를 붙이고 나오기는 어려웠을 것이다. (여담이지만, 스타크래프트 등의 RTS에서는 길찾기를 위해 A* 알고리즘을 사용하되, 효율성을 위해 타일의 크기를 몇 단계로 나누거나 최대 탐색 깊이를 제한하는 등의 방법을 이용하여 길을 찾는 것으로 알고 있다)
물론 이는 휴리스틱 함수를 잘 정하면 상당 부분 해결될 수 있는 문제이다. 하지만 좋은 휴리스틱 함수를 정하는 것은 무척이나 어려운 일이다. 길 찾기는 직관적으로 유클리드 거리를 휴리스틱 함수로 사용할 수 있기 때문에 쉬운 편이나 STRIPS로 정의된 행동과 조건, 목표, 그에 따른 행동 순서를 정하는 계획(Planning) 문제와 같이 직관적으로 휴리스틱 함수를 정하기 어려운 문제가 훨씬 더 많다. 즉, 쉽게 개선할 수 있는 문제가 아니라는 것이다.
이러한 한계는 가능한 모든 경우의 수를 전부 탐색하는 A* 알고리즘의 특성에서 온다. 모든 경우의 수를 탐색하는 방법에 기반해서는 문제가 커질 때 탐색해야 하는 상태의 수가 기하급수적으로 늘어나는 것을 피할 수 없다는 의미이다. 하지만 이를 다르게 본다면 최적 해답을 포기하고 가능한 모든 경우를 전부 확인하지 않는다면 훨씬 빠른 탐색이 가능하다는 의미이기도 하다. 이 아이디어에 따라 모든 경우를 전부 탐색하지 않고 주변 노드만을 탐색하면서 해답을 찾아 나가는 방법을 Local search라 하며 (이 역시 Informed search의 일부이다), 이러한 접근법을 사용한 방법으로는 Hill climbing, Simulated annealing, Genetic algorithm 등이 있다.
2. Local search
우선 Local search를 이해하기 위해서 현 상태 x를 평가하는데 사용할 함수를 하나 정의하고 이를 목적 함수(Objective function) f(x)라 두자. 이를테면 길 찾기 알고리즘이라면 목표 지점까지 가는 경로 x의 길이가 될 수 있고, n-queen 문제라면 서로를 바로 공격할 수 있는 여왕의 갯수가 될 수 있다. TSP 문제에서는 경로의 길이 합이 될 것이다. f(x)의 정의역은 가능한 상태 공간(State space) 전체가 될 것이며, 이에 대응하는 f(x)의 공역은 여러 모양을 취할 수 있으나, 대개 대소 관계가 명확한 정수 혹은 실수 꼴일 것이다.
문제에 따라 천차 만별일 것이나, 만일 f(x)의 모양을 시각화하면 대부분의 문제에 있어서 특정 상태(state) x와 y가 서로 이웃하고 있는 경우 f(x)와 f(y)의 차이 역시 비교적 작을 것이므로 그 모양에 있어서 어느 정도 미분 가능한 함수와 비슷한 꼴을 가지는, 부드러운 형태의 그래프가 나올 것이다. f(x)의 이러한 특성을 생각해보면 임의의 한 상태를 택한 뒤 f(x')가 커지는 방향으로 이웃 상태 x'를 택해 나간다면 f(x)의 최대값은 몰라도 적어도 극대값은 구할 수 있지 않을까 하는 것이 Local search의 기본 아이디어이다. 이렇게 현재의 답을 개선해나간다는 특성 상 이는 최적화 문제를 푸는 알고리즘으로 분류된다.
윗 문단에서 두 상태가 이웃한다는 이야기를 꺼냈는데, 이 역시 Local search에서 중요한 개념 중 하나이다. 서로 이웃한다는 것은 문제에 따라 달라질 수 있는 개념이기 때문에 이를 일반화하여 정의하기는 어려우나, 두 상태가 가진 특성 대부분이 유사한 경우를 보통 서로 이웃한다고 본다. 이웃의 개념을 잘 정의하느냐에 따라 문제의 구조가 완전히 달라질 수 있기 때문에 이 역시 문제를 효율적으로 푸는데 있어 중요한 개념이다.
이러한 추상적인 설명만 가지고는 개념을 이해하기 어려울 수도 있으니 예를 한가지 들어보자. 서울, 대전, 광주, 대구, 부산, 인천의 TSP 문제에서 임의의 상태는 모든 도시를 연결하는 경로, 즉 가능한 해답 중 하나이다. 이는 (서울 - 대전 - 광주 - 대구 - 부산 - 인천 - 서울)이 될 수도 있고, (대전 - 대구 - 인천 - 부산 - 서울 - 광주 - 대전)이 될 수도 있다. 이웃을 정의하는 데에는 다양한 방법이 있을 수 있으나 도시 순서에서 두 도시를 서로 바꿔치는게 가장 직관적이다. 이를테면 (서울 - 대전 - 광주 - 대구 - 부산 - 인천 - 서울)의 이웃 중 하나로는 대전과 부산의 위치를 바꾼 (서울 - 부산 - 광주 - 대구 - 대전 - 인천 - 서울)이 있는 것이다.
3. Hill-climbing search
Local search에서 가장 간단한 알고리즘은 Hill-climbing search인데, 이 알고리즘의 동작은 무척 간단하다. 우선 목적 함수와 이웃 구조가 모두 정의된 문제가 있다고 하자. 이 때 임의의 상태 하나를 선택한다. 그 뒤 그 상태의 이웃들을 탐색한 뒤 그 중 목적 함수의 값이 가장 큰, 다시 말해 평가가 좋은 상태를 택한다. 만약 이 상태가 현 상태보다 좋다고 판단되는 상태라면 해당 상태로 이동하고, 아니라면 현 상태를 해답으로 반환하고 알고리즘을 종료시킨다.
오로지 현재 상태와 이웃 상태만을 고려하여 그 때 그 때 최선의 선택을 취하는 특성으로 인해 greedy local search로 분류되며, Hill-climbing이라는 이름 역시 한치 앞도 안 보이는, 안개가 낀 산을 타고 올라가는 듯한 특성으로 인해 붙여진 이름이다. 임의의 상태 중 하나를 골라 이를 개선시켜 나가는 특성으로 인해 해답 자체를 구하는 것이 목적인 경우보다는 보통 해답 자체를 구하기는 아주 쉬우나 어느 정도 괜찮은 해답을 구해야 할 필요가 있는 경우에 자주 사용된다.
위에서 안개가 낀 산을 탄다는 표현을 했는데, 한 치 앞도 안 보이는 이런 상황에서는 산 봉우리에 올라섰다고 해도 주변 지리를 모르면 여기가 제일 높은 봉우리인지 아닌지 알 방도가 없다. 재수가 없으면 산 입구에 위치한 바위 꼭대기에 올라선 것일 수도 있는 것이다. 제일 높은 봉우리가 최대값(global maximum), 바위 꼭대기가 극대값(local maximum)이라고 해보자. 이 예시는 탐색이 끝나더라도 찾은 해답의 목적 함수 값이 최대값인지 극대값인지를 구분하지 않고 그냥 반환해버리는 이 알고리즘의 특성과 정확하게 일치한다. 다시 말해 이 알고리즘은 답의 optimality를 보장하지 못한다.
그렇다면 이렇게 찾아낸 해답의 품질은 어떨까? 문제에 따라 상당히 다르지만, 알고리즘이 간단하니만큼 전반적으로 그다지 좋은 편은 되지 못한다. 물론 임의로 찾아낸 해답에 비한다면야 나은 것은 사실이지만, 최적 해답에 비한다면 그다지 좋지 못한 편이라는 것이다. 가장 큰 문제는 임의로 선택된 초기 상태에 따라 나오는 해답의 품질이 무척 들쑥날쑥하다는 것으로, Hill climbing 자체만으로는 신뢰성이 그다지 높지 않다.
그러나 알고리즘 자체가 간단하고 계산의 부하가 매우 적기 때문에 문제점을 해결하기 위한 변형이 몇 가지 나왔는데, 그 중 하나가 Stochastic hill climbing이다. 이는 매 번 최적의 이웃을 택하지 않고, 현 상태보다 나은 이웃 중 하나를 임의로 택하여 이동하는 방식을 통해 이동할 수 있는 상태의 범위를 넓힌다. 이 경우 단순한 Hill climbing보다는 비효율적이지만 결과 자체는 더 나은 경우가 있다. 그 외에 이웃 노드를 반복적으로 생성하다 그 중 현 상태보다 조금이라도 나은 상태가 나오면 바로 그 상태를 택하여 연산의 부하를 줄이는 First-choice hill climbing도 있다(보통 이웃 노드의 수가 수천 수만개가 나오는 경우 사용한다). 이러한 Hill climbing 알고리즘들을 여러 번 반복하여 그 중 가장 좋은 해답을 택하는 Random-restart hill climbing 알고리즘도 존재하는데, 대부분의 경우 높은 확률로 상당히 괜찮은 해답을 내놓는다고 한다.
4. Simulated annealing
위에서 알아본 Hill climbing 알고리즘의 단점은 극대값을 가진 상태에 빠질 가능성이 높다는 것이다. 이러한 문제는 근본적으로 올라가는 길만 있을 뿐, 내려가는 길이 전혀 없다는 점에 기인한다. 즉, 주어진 시작 상태에 따라 수렴하게 되는 해답이 오르막길을 통해서 갈 수 있는 극히 일부로 제한되고, 그로 인해 최대값을 찾을 수 있는 초기 상태 역시 극히 일부로 한정되기 때문이다. 이는 산에서 제일 높은 봉우리로 가는 길 위가 아닌 곳에서는 오르막길만 타선 대개 제일 높은 봉우리로 가지 못하는 것에 비유될 수 있다.
이를 해결하는 방법으로는 Random-restart hill climbing 알고리즘과 같이 여러 번 반복한 결과 중 최선을 택하는 방법도 있지만, 다른 한 편으로는 알고리즘을 수행하는 과정에서 내리막길의 선택을 제한적으로 허용하는 방법이 있다. Simulated annealing은 이러한 방식을 택한 알고리즘이다. 흥미로운 것은 이렇게 제약을 살짝 푸는 것 만으로도 수렴할 수 있는 영역의 범위에 최대값이 포함될 수 있다는 것인데, 이는 아래에서 이야기한다.
Simulated annealing의 뜻은 금속 공학에서의 풀림(annealing)을 따라한다는 의미이다. 안정적인(에너지 상태가 낮은) 금속 하나를 가열한다 치자. 이 떄 온도가 높아질수록 원자들간의 결합은 약해지고 운동 에너지는 커져 여러 곳을 떠돌게 되는데, 이 상태에서 온도를 천천히 낮추면 도리어 초기보다 더 낮은 에너지를 가지는 결정(Crystal)의 형태로 원자들이 결합할 확률이 커진다. 금속은 대개 일반적으로 안정적인 상태이기 때문에 더 안정적인 상태로 변환하기가 어려우나, 이를 가열하여 불안정한 상태로 만들면 전혀 다른 구조의 더 안정적인 상태로 이동할 확률이 생기게 되는 것이다. 이 과정은 초기의 극대값 상태(초기 결합 구조)를 빠져나와 오히려 더 안 좋은 상태(운동 에너지의 상승)로 빠지지만, 온도가 낮아질수록 최대값 상태(가장 낮은 에너지를 가지는 결합 구조)가 될 확률이 높아지는 것으로 해석할 수 있다.
풀림의 이러한 모습은 최적화 문제로 분류되는 local search에도 적용될 여지가 상당히 큰데, 이러한 아이디어를 local search에 적용하기 위해서는 몇 가지 대응되는 개념부터 정의해야 한다. Simulated annealing에서 내리막길, 즉 더 안 좋은 상태를 선택하는 것은 운동 에너지가 높은 것, 즉 온도가 높은 것에 대응시킬 수 있다. 그렇다면 온도라는 개념을 도입하고, 온도가 높을 때에는 안 좋은 상태를 선택하더라도 높은 확률로 이를 허용하고, 온도가 천천히 낮아짐에 따라 이 확률을 낮추면 되지 않을까?
설명에 비해 실제 알고리즘의 동작은 생각보다 간단하다. 우선 이웃한 상태 중 임의로 상태 하나를 택한다. 그 뒤 해당 상태가 현 상태보다 낫다면 바로 전이하고, 더 안 좋다면 '온도'와 안 좋아지는 정도에 의해 결정되는 확률에 따라 전이할지 말지의 여부를 결정한다. 이 것이 가장 기본적인 아이디어인데, 구체적인 식으로 표현한다면 온도가 T, 안 좋아지는 정도가 df(x)라 한다면 이 확률은 보통 e^(-df(x)/T)로 결정된다. 여기에서 온도는 시간에 따라 낮아지는 방향으로 변하게 되는데, 온도가 변하는 스케쥴(annealing schedule)은 알고리즘을 사용하는 사람이 결정할 파라메터이다.
그렇다면 이 알고리즘은 optimal할까? 흥미롭게도 온도가 충분히 느리게 낮아진다면 optimal하다는 것이 증명되어 있다. 그러나 이는 실제로 사용하기엔 너무 느린 속도라고 하며, 문제마다 '충분히 느리게 낮아지는 스케쥴을' 따로 구하는 일도 쉽지 않기 때문에 대개 문제에 직접 적용해보며 온도-시간 함수를 조절하여 사용한다. 이 때 온도가 빠르게 낮아지면 찾아낸 해답의 평균적인 퀄리티가 낮으며, 천천히 낮아지면 그 퀄리티가 올라가는 경향이 있다. 그래서 이 알고리즘은 대부분 반드시 최적해를 구해야 할 때보다는 어느 정도 수준이 보장되는 해답을 구해야 할 필요가 있을 때 많이 사용된다.
5. Genetic algorithm
Simulated annealing과 유사하게 유전자 알고리즘 역시 자연계의 현상을 관찰하여 이를 계산에 적용한 것이다. 자연계에서 각 종들이 진화하고 도태하는 과정을 살펴보면 각 세대마다 유전자가 섞여 자식이 나오는데, 그 중 생존에 유리한 유전자가 주로 남고 불리한 유전자가 도태되는 것을 알 수 있다. 또한 이 과정에서 돌연변이가 생기는 등의 변인이 개입되면서 진화가 이루어지는데, 인류의 경우 불과 수천 세대만에 현재의 위치까지 온 것을 보면 이는 대단히 효율적인 알고리즘이라고 볼 수 있을 것이다.
이 역시 실제 현상에 대응되는 개념들을 정의하고 이를 통해 알고리즘을 만든다. 우선 유전자, 혹은 각 개체는 상태(state)라고 볼 수 있으며, 실제 존재하는 개체들의 집합, 즉 개체군은 문제에서 임의로 생성한 상태들의 집합에 대응된다. 유전자가 섞이는 것은 두 상태의 파라미터들이 임의로 섞이는 것으로 볼 수 있다. 일반적으로 이 과정은 각 상태를 이진수로 표현되는 문자열로 인코딩한 뒤 문자열의 일부를 서로 치환하는 방법을 사용하지만, 다른 인코딩도 별 상관은 없다. 생존에 유리한 정도는 문제에 따라 다르게 정의되는 적합도 함수로 표현하며, 이는 목적 함수와도 관련이 깊다.
실제 알고리즘이 돌아가는 과정은 아래와 같다.
- 주어진 개체군에 대하여 적합도를 계산, 각 개체들이 선택될 확률을 계산한다.
- 해당 확률에 맞게 개체들을 다수 선택한다.
- 선택된 개체들의 유전자를 섞어 다음 세대의 개체군을 만든다.
- 다음 세대의 개체군에서 일부 개체의 유전자를 임의로 바꾼다. (돌연변이)
- 원하는 수준의 해답이 나올 때까지 이를 계속 반복한다.
위의 알고리즘에 따르면 적합도가 높을수록 다음 세대를 만드는 개체에 선택될 확률이 높아지므로 자신의 상태를 다음 세대로 넘길 확률이 높아질 것이다. 이런 식으로 적합도가 높은 개체들을 교배하여 만든 다음 세대의 개체 역시 적합도가 높을 것이라는 기대가 유전자 알고리즘의 근간을 이루고 있다. 이 때 돌연변이의 개념이 도입된 것은 극대값에 빠질 가능성을 낮추기 위함이다. 물론 유전자 알고리즘 자체가 어느 정도는 무작위성에 기대고 있기 때문에 Hill-climbing에 비해서는 극대값에 빠질 확률이 적긴 하지만, 이 역시 어느 정도 예측 가능한 무작위성이기에 이를 보정하기 위해 돌연변이의 개념이 도입된다. (실제로 돌연변이가 있는 경우와 없는 경우 최적의 해답을 찾는데 걸리는 시간은 크게 차이 난다고 알려져 있다.)
유전자 알고리즘을 적용할 때 중요한 것은 각 상태를 표현할 유전자적 표현법(Genetic representation)을 찾는 것이다. 위에서는 이진수로 표현되는 문자열이라 했는데, 굳이 이진수일 필요는 없으나 진화적인 관점에서 볼 때 어느 정도 납득이 가능한 변환이어야 한다. 이를테면 적합도가 높은 두 개체를 인코딩한 뒤 이 둘을 서로 치환했을 때 대개 적합도가 높은 개체가 나타난다면 이는 괜찮은 변환이다. 하지만 이러한 경향성이 없는 경우라면 사실상 무작위로 새로운 개체들을 만드는 것과 다를 바가 없어지는 것이다. 실제로 이러한 표현법을 찾는 것은 쉬운 일이 아니며, 유전자 알고리즘 뿐 아니라 진화적 알고리즘 대부분에서 중요하게 여겨진다고 한다.
알려진 바에 따르면 유전자 알고리즘은 Simulated annealing과 유사하게 최대값을 찾는데에는 그다지 효율적이지 못하나 해답을 알고 있는 경우 이를 최적화하여 어느 정도 괜찮은 수준의 해답을 찾는데에는 대단히 효율적이다. 그러나 모든 문제에 대해 무조건적으로 적용할 수 있는 만능의 알고리즘은 아니므로 가급적 local search에 맞도록 문제를 변형하여 풀도록 해야 한다.
