[Meta-huristics] Simulated Annealing : 담금질 기법

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

저번 글에 작성했던 알고리즘인 Grid는 최적의 답을 구할 수는 없다. 그저 근사치를 구할 수 있을 뿐이다. 그렇기 때문에 최적해를 구할 수 있는 방법을 소개하고자 한다. Grid알고리즘의 경우 내 블로그에 적어뒀지만 여기에 한번 더 링크를 남겨둘테니 헷갈린다면 한번 더 보는걸 추천한다. 

https://naemamdaelo.tistory.com/47

알고리즘 - 그리디(Greedy)

https://naemamdaelo.tistory.com/48

Routing Problems : 최단경로 찾기

 

그렇다면 최적 해를 구할 수 있는 알고리즘이 무엇인지 알아보기 전에, "해" 라는 것이 어떤것인지, 최적해는 무엇인지 알아보겠다.

"해" 라는 것은 결과값을 의미한다. 쉬운 말로는 "정답"이라고 할 수도 있다. 경로를 찾는 것을 예시로 들자면, 최적의 해인 가장 짧은 경로가 존재한다. 이를 Global optimum이라고 한다. 그리고 최적은 아니지만 적당히 좋은 답, 현실적인 해를 Local optimum이라고 한다. 우리의 목표는 Global optimum을 찾아내는 것이다. 그렇기 때문에 아래와 같은 알고리즘을 사용한다.

Meta-huristics

범용적인 알고리즘이다. 그렇기 때문에 어지간한 최적경로 찾는 문제에 적용이 가능하다. 하지만 알고리즘 내부에 랜덤성이 존재한다. 그렇기 때문에 시간이 지날수록 정확도가 높아진다. 

 

Meta-huristics은 여러 종류가 존재한다. 

1. Simulated Annealing

2. Tabu Search

3. Genetic Algorithms

4. Ant Colony Optimization

5. Particle Swarm Optimization

 

이중에서 우리는 Simulated Annealing을 알아볼 것이다.

 

Simulated Annealing(SA)

Annealing의 뜻은 제련이다.

제련의 과정인 Heat it -> form it -> cool it -> REPEAT

이 것을 적용시킨 알고리즘을 Simulated Annealing이라고 한다. 

 

우리는 어떠한 값을 구할때 Global Optimum을 구하고자 한다. 하지만, 최적해로 가는 과정에는 Local Optimum이 존재한다. 물론 Local Optimum에서 자연스럽게 Global Optimum으로 향상되어간다면 아주 이상적일 것이다. 하지만 그렇지 않은 경우가 존재한다. 

위의 그림처럼, start부분에서 공을 굴린다고 가정해보자. 단, 이때 가속도나 관성 뭐 이런것들은 존재하지 않는다고 한다.

그렇다면 공이 굴러내려가다가 Local Optimum에서 멈출 것이다. 우리의 알고리즘이 공이 위에서 아래로 내려가는 것 처럼 점점 개선되는 방향으로만 움직이게 작성되어있다면, Local Optimum이라는 구덩이에 빠져 Global Optimum에 도달하지 못할 것이다. 그렇기 때문에 사용되는 기법이 Simulate Annealing이다.

 

Simulate Annealing을 한마디로 요약하자면 "일정 확률로 좋지않은 선택지를 선택하는 알고리즘"이다. 이게 뭔 개소린가? 싶을수도 있다. 나도 그랬거든. 위의 그림을 보면서 추가적으로 설명하겠다.

공이 "아래로만 내려가도록" 진행한다면 앞서 말했듯 Local Optimum에 빠지게 된다. 이때 알고리즘을 약간 수정한다.

1. 공의 다음 진행방향이 아래일 경우 아래로 내려간다. 

2. 공의 다음 진행방향이 위로 올라갈 경우 특정 확률로 위로 올라간다(이전 값보다 좋지않은 선택지로 이동한다.)

여기서 특정 확률을 정하는 방법이 중요하다. 초반에는 확률을 높여주고, 후반으로 갈 수록 확률을 낮춰주는 것을 권장한다. 이 확률을 정하기 위해 사용되는 것이 Boltzmann's constant, 즉 볼트만 상수이다. 

그렇다면 왜 볼트만 상수를 활용해서 확률을 구할까? 이것을 해당 알고리즘의 이름과 관련이 있다.

"담금질 기법"이라는 이름에 걸맞게 프로그램이 작동되면 점점 온도가 내려간다고 표현한다. 이때, 볼트만 상수에 이 온도값을 적용시킨다면 아래와 같은 그래프가 나오게 된다. 

현재의 온도가 낮다면 그 값도 작게, 현재의 온도가 크다면 그 값도 큰값이 나온다. 즉, 현재의 온도가 높다는 것은 시행한지 얼마되지 않았다는 것 이고, 온도가 낮다는 것은 시행한지 오래되었다는 것이다. 그렇기 때문에 온도가 높은 초반은 그 값이 크기 때문에 확률이 높고, 온도가 낮은 후반은 그 값이 작기때문에 확률이 작다. 이러한 성질로 인해 볼트만 상수를 활용한다. 

 

이렇게 확률을 정하는 방법을 배웠으니 간단하게 요약하여 SA를 활용하는 방법을 보여주겠다.

1. 예제를 선정한다.

2. 현재온도, 1cycle당 내려갈 온도, 최종 온도를 정한다.

3. 근처의 값(다음 경로)를 선택한다.

4. 해당 위치로 이동한 후 이전값과 현재 결과값을 비교한다.

5. 지금까지의 가장 적합한 값을 저장한 후, SA알고리즘을 적용한다.

5-1. 현재값보다 다음 값이 더 좋은 값이다 => 해당 값 적용 후 3번으로 돌아감

5-2. 현재값보다 다음 값이 더 좋지않은 값이다

     => 볼트만 상수를 활용하여 확률을 구한다.

          => 특정 확률에 들어왔을 경우 : 해당 값을 적용 후 3번으로 돌아간다.

          => 특정 확률에 들어오지 못했을 경우 : 현재 값을 무시하고, 이전값을 활용하여 3번으로 돌아간다.

6. 현재 온도가 최종 온도에 도달했을 경우 프로그램을 종료시킨다. 

 

이때 2번이 아주 중요하다. 온도를 천천히 낮추게 될 경우 많은 cycle이 돌게 되고, 보다 정확한 값을 도출할 수 있지만 시간이 오래 걸린다. 온도를 빠르게 낮추게 될 경우 정확한 값이 도출될 확률이 낮아진다. 그렇기 때문에 2번의 적절한 값을 선택하는 것이 중요하다. 2번에 따라서 결과물이 천차만별로 달라지게 될 것이다.

 

위와 같은 과정을 통해 프로그램을 작성할 경우 여러가지 장단점이 존재한다.

장점

1. 일반적인 Local Optimum보다 좋은 값을 구할 수 있다. 즉 Global Optimum에 가까운 값을 구할 수 있다.

2. 폭넓은 활용이 가능하다. 모든 분야에서 활용이 가능하다. 

 

단점

1.  시간이 정말 오래 걸린다.

 

이러한 장점과 단점이 존재하니 적절한 상황에 맞춰서 사용한다면 좋을 것 이다.