시뮬레이티드 어닐링

목차

1. 어닐링

2. 세일즈맨 문제

 

---

 

 

---

 

 

1. 어닐링 

 

원래는 기술용어였다가 수학용어가 된 말이 하나 있습니다. 바로 '어닐링'이라는 말인데 원래 유리 제조에서 사용되는 말로 가열된 유리를 서서히 식히는 통제된 냉각방식을 뜻합니다.

수학의 세계에서 '시뮬레이티드 어닐링', 즉 담금질 기법은 복잡한 최적화 문제를 해결하는 데 필요한 보편적 보조 도구로 자리 잡았습니다. 수학적 담금질의 내용은 목표값이 최대한 크게 나오도록 특정한 수의 매개변수를 찾는 것입니다.

 

 

 

만일 매개변수가 위도와 적도이고 목표값이 해발고도라면, 과제는 그 지역에서 가장 높은(혹은 낮은) 지점을 찾아내는 것입니다. 또는 화학 작용에서 다양한 성분의 함량을 찾아내거나 모터를 설정할 때도 쓰입니다. 특히 질 좋은 플라스틱을 만들거나 효율적인 모터 설정을 할 때 유용합니다.

 

원래는 이런 문제를 풀 때 미분을 사용했었는데, 미분을 사용하면 시작할 때의 값과 목표함수 사이의 관계가 분명히 드러나지 않을 수도 있고 구체적인 계산을 하기에 너무 복잡하다는 문제가 있었습니다.

이럴 때는 시뮬레이티드 어닐링이 도움이 됩니다. 구릉지대에서 가장 높은 지점을 찾는 첫 번째 예를 상기해 봅시다. 안개가 짙게 낀 날 산책을 한다고 가정해 보죠. 어떻게 하면 안개 속에서 가장 높은 지점을 찾아낼 수 있을까요? 그냥 위로 계속 올라가면 될까요? 그러면 작은 언덕에 오를 수는 있겠지만 미쳐 보지 못한 더 높은 언덕을 간과할 가능성도 큽니다. 그래서 시뮬레이티드 어닐링에서는 올라가기만 하는 것이 아니라 일부러 내려 가기도 합니다. 그러면서 안개 속을 헤매다 보면 가장 높은 지점에 오르게 된다는 것이 이 아이디어의 핵심입니다.

 

 

중요한 것은 가장 높은 지점에 오른 뒤 다시 내려가지 말아야 한다는 것인데, 이것은 시간이 지남에 따라 내려가는 횟수를 점점 줄여 0이 되게 하는 것으로 극복할 수 있습니다. 이상이 통제된 냉각방식을 비유적으로 설명한 것입니다.

다른 과제에서도 핵심적인 내용은 같습니다. 구릉지대에서의 산책이 매개 변수 공간에서의 산책으로 바뀔 뿐입니다. 매개변수 공간이 너무 크지 않고 넉넉한 연산 시간만 주어진다면 최적화 문제를 푸는 일은 시간문제라고 할 수 있습니다.

 

---

 

 

2. 세일즈맨 문제 

 

실생활과 밀접한 관계가 있는 최적화 문제를 '산책'에 비유하는 것은 조금 이상할 수 있기에, 더 실감나는 예로 세일즈맨 문제를 살펴보겠습니다.

 

전국에 거래처를 가진 회사가 있다고 하자. 회사의 홍보 담당자는 새로운 상품을 소개하기 위해 회사차를 끌고 전국을 돌아야 한다. 어떻게 돌아야 모든 거래처에 한 번씩만 들르면서 전체 주행거리가 최대한 적게 나와야 할까? 이렇게 최적의 제곱근을 찾는 문제가 바로 수학자들 사이에서 유명한 ‘세일즈맨 문제’다.

 

도시들에 1, 2, …, 20의 숫자를 붙이고 도시들을 순서 없이 늘어놓는다.

6,1,19,2,15,12,3,5,20,11,16,10.7.13.8,4,9,17,14,18

이 경로는 도시 6에서 출발해 도시 1로 간 다음 도시 19로 가서... 이렇게 계속 가다가 20번째 도시, 즉 도시 18에서 다시 출발점으로 돌아오는 순회 경로다.

 

 

 

이런 식으로 여행 경로의 조합 가능성을 구하면 천문학적인 수치가 나옵니다. 기본조합을 사용했을 때 나오는 가능한 여행코스의 가짓수는 2,432,902,008,176,640,000개나 됩니다. 이렇게 많은 코스의 주행거리를 일일이 컴퓨터로 알아본다는 것은 현실적으로 불가능합니다. 그러나 방법이 없는 것은 아닙니다. 각각의 코스를 구릉지대의 지점들로, 그리고 각 코스의 주행거리를 해발고도로 파악하고 가장 낮은 지점을 찾으면 됩니다.

 

이 문제를 ‘시뮬레이티드 어닐링’으로 풀려면 다음과 같은 방법을 사용할 수 있습니다. 일단 아무 코스나 하나 - 예를 들어 위의 코스(6, 1, 19, ) - 선택합니다. 그리고 그 코스 중 무작위로 두 개의 지점을 골라내 순서를 뒤섞고, 지점 3과 지점 8이 우연히 뽑혔다면 위의 여행코스는 아래와 같이 변합니다.

 

 

 

6,1,5,2,15,12,3,19,20, 11, 16,10.7,13,8, 1.9, 17, 14,18 도시 5와 19가 서로 자리를 바꾸었죠. 이것이 주행거리를 단축시키는 경우 그 상태에서 계속하고, 그렇지 않은 경우 뽑기를 다시 합니다. 이 방법의 특이한 검은 일정 정도의 확률로, 그리고 과정의 끝보다는 출발점에서 주행거리가 길어지는 것을 감수한다는 것입니다. 이렇게 해서 우물 안 개구리 식의 오류를 피할 수 있습니다(즉 가장 깊은 골짜기를 찾아야지 고지대의 분지를 찾으면 안 된다는 말이다).

 

---