[알고리즘] simulated annealing

0.

보통 알고리즘 문제들은 해법이 있다.

 

하지만, real life 문제들은 완벽한 최적해를 구할 수 없는 경우가 많다.

 

그래서 생각한 것이 근사해다.

 

이때, 휴리스틱 알고리즘을 사용하는데, 2가지가 있다.

 

1)완전탐색할때 속도향상을 위해 사용하는 휴리스틱

2)최적점과 가까운 근사해를 찾는 메타 휴리스틱

 

이 메타 휴리스틱에는 simulated annealing알고리즘이 있다.

 

1.

쉽게 말하면, 최적해에 다가가는 과정이다.

 

일반적으로 휴리스틱을 사용한다면 가능한 해의 후보를 보고, 평가하고, 그 중 가장 좋은 해를 찾는다.

 

하지만 여기서는 해의 후보를 보지 않는다.

 

그냥 "좋은 해가 있을 것 같은" 일부 지역을 탐색한다.

-> 현재상태에서 인접한 상태를 구하고 이득과 손해의 정도를 확률적으로 이동한다.

 

(인접한 상태란 tsp를 예로 들자면 임의의 인접한 두 도시를 교환하는 것이다. 즉, 국소적인 변화를 말한다.)

 

즉, 위와 같이 인접한 상태를 보면서 최적해를 향해 가는데 와중에 더 나빠지는 해에 대해서도 가끔은 탐색을 해서 local optima를 피하려 노력한다.

 

(참고: 원래는 정해준 옳은 규칙 즉, 탐욕법계통의 알고리즘이 많았다면, random의 요소를 통해서 stochastic 계통의 알고리즘이 주목받고 있다. 최악을 피하면서 최선을 찾을 가능성이 있기 때문이다.)

 

 

2.

1)인접상태정의

-인접상태를 찾는 연산은 너무 오래 걸려도 안되고 너무 많이 변해도 안된다 최대한 조금 걸리고 변하도록 잡아야한다.

 

2)평가함수정의

-이 해가 얼마나 최적해에 가까운지를 알려줄 방법/ 일반적으로는 최소화,최대ㅎ화하고 싶은 그 값이 평가함수가 된다.

 

3)이동

- 상태가 더 나아진다면(에너지가 줄어든다면, 평가함수값이 좋아진다면) 확률이 1을 넘어 그 방향으로 무조건 간다.

- 상태가 악화된다면(에너지가 증가한다면, 평가함수값이 나빠진다면) 위에서 계산한 확률에 따라서 이동한다.

그래서, 보통 좋은 해로 가지만 나쁜 곳도 가끔은 탐색을 한다.

 

4)온도감소

해를 탐색하는 초기에는 많은 곳을 뛰어다니면서 어느 곳이 전역 최적에 가까울지를 봐야하지만, 어느 정도 전역 최적점에 대한 "감"이 오면 그 안에서 조금이라도 더 나은 해를 찾기 위한 세밀한 탐색을 해야한다.

 

온도가 높을 수록 즉, T가 클수록 확률이 0.5에 근사하여 random search가 된다.

온도가 낮아지면 확률이 1에 근사하여 ordinary hill climbing이 된다.

 

다시 말해서, 초반에는 gradient descent알고리즘처럼 많이 많이 변하지만 해에 가까워질수록 T가 감소하여 세밀하게 진행된다.

 

 

참고

m.blog.naver.com/PostView.nhn?blogId=jaehyubious&logNo=220356334132&proxyReferer=https:%2F%2Fwww.google.com%2F

LECTURE 3. Simulated Annealing