여행하는 세일즈맨 문제와 simulated Annealing 소개

 

 

이상하게 그룹 카테고리가 만들어지지 않네요. 당분간 PET 프로젝트 그룹에 쓰겠습니다.

 

 

여행하는 세일즈 문제를 시작해보죠.

 

이 문제는 유럽을 돌아다니는 영업사원이 n 도시를 돌아다니는데 가장 빠른 경로가 뭔지 찾는 문제입니다. 물론 제일 마지막 도시가 출발도시가 되죠.

 

말로는 굉장히 간단한 문제입니다.

 

 

1) 모든 가능한 경로를 찾는다.

 

2) 각 경로마다 거리를 잰다

 

3) 가장 짧은 거리를 가진 경로를 찾는다.

 

 

 

그러나 문제가 그리 간단하지 않다는 이야기입니다.

 

 

만역 n=50, 즉 도시가 50개 이면 모든 가능한 경로가 49! 만큼 되고, n=100 이면 99! 만큼 경로가 생긴다. n이 커지면 가능한 경로는 기하급수적으로 늘어납니다. 컴퓨터학과에서 흔히 이야기하는 NP 문제에 해당합니다. NP문제에 대해서는 묻지 마시고요. 저는 잘 모릅니다. 검색하거나 컴퓨터 전공하신 분에게 물어 보시고요.

 

이렇게 가능한 경로 수가 많아지면 거리 재는 것도 만만치 않고, 여기서 가장 짧은 경로 찾는 것도 시간이 많이 걸립니다.

 

그래서 정확한 답은 아니지만 근사적인 답을 찾자는 것이죠.

 

여기서 Simulated Annealing 알고리즘이 나옵니다.

 

이건 MCMC의 출발 논문인 흔히 Metropolis 알고리즘이라고 부르는 논문에서 처음 나옵니다. 이 논문은 읽은 것 같지 않는데요. 어디 방구석에 있는지는 모르겠지만. Hasting 논문도 찾지 못하겠고요,

 

 

 

하여간 Boltzman(Simulated Annealing and Boltzmann machines 책을 Boltzmann 책이라 이야기 하겠습니다) 책에 보면 간략하게 설명되어 있으니까 이쪽 전공하실 분 아니면 구태여 읽을 필요는 없는 것 같고요.

 

Simulated Annealing을 SA라고 부르겠습니다. 흔히 대장간에서 담금질한다고 하나요. 검색해보니 풀림이라고 되어 있던데, 하여간 물체를 확 온도를 올렸다가 천천히 내리면 에너지 상태가 최소화되면서 표면이 매우 부드럽게 된다고 합니다. 이 아이디어를 빌려온 것입니다.

 

이 알고리즘의 또 하나의 장점은 local minimum, maximum을 막아 줍니다. relaxation 이라고 하는 모양입니다.

 

다음 시간에 더 쓰죠.