Simulated Annealing

SA

• SA는 복잡한 최적화 문제 or 탐색공간의 global optimum을 찾기 위한 확률론적 최적화 기법이다.
  • 이 방법은 금속공학에서 금속을 서서히 냉각시키면서 결정구조를 안정화 시키는 'annealing' 공정에서 영감을 받은것.
• 'annealing 공정'의 영감이란?
  • 금속을 고온에서 천천히 냉각시키면, 원자들의 결정구조가 안정된 상태를 형성함. 하지만 이를 급격히 냉각 시키면 결정구조는 불안정한 상태를 형성하게 된다.
  • 그러면 왜 'annealing 공정'이 최적화 문제와 유사한가?
    • ==> 최적화 문제도 초기에는 '높은 온도'에서 많은 해를 탐색하며, 이후 '낮은 온도'로 천천히 가면서 해가 개선되는 방향으로 향하게 유도한다.
      즉, 높은 온도에서는 나쁜 해도 확률적으로 허용되어서 지역 최적해에 빠지지않고 전역 최적해로 나아갈 수 있게 해준다.
• 장점
  • 1. 높은 초기 온도에서 나쁜해도 허용하면서 지역최적해에 머물지 않고, 전역 최적해에 다가갈수 있는 가능성을 높임.
  • 2. 매운 큰 탐색 공간이나 비선형,다봉우리 문제에서 효과적이다.
• 단점
  • 1. 매개변수에 민감하다
  • 2. 충분한 탐색을 위해서 많은 반복을 한다면 많은 시간이 소요될수있다.
  • 3. 항상 최적해를 찾는다고는 보장하지 못한다.

 

 

SA의 원리 및 절차

• 1. 초기해 설정 : 최적화 하려는 문제에 대해서, 시작점을 무작위 or 휴리스틱에 따라 선택한다.
• 2. 알고리즘 초기 단계이니 높은온도를 설정함. ( 높은 온도는 탐색 공간 전체를 폭넓게 탐색할 수 있게 해준다.)
• 3. 현재의 해에서 약각의 변화를 주어서 새로운 이웃 해 s'을 생성한다. ( 이웃해 생성 방법은 문제의 특성에 따라서 다양하게 설계됨. )
• 4.  해의 평가 및 수용 여부 결정
  • 4-1. 목적 함수 E( s ) 계산 : 목적함수는 각 해의 '에너지' or '비용'을 나타내는 함수를 계산한다.
  • 4-2. 새로운 해를 수용할지는 수용 기준을 가지고 결정을 한다.
    • 새로운 해( s' )가 기존 해( s )보다 더 좋은 경우는 무조건 채택한다. ( 즉, E(s') < E(s) 인 경우 ) 
    • 만약 s'이 나쁘다면? ==> 확률 P를 통해서 채택할수 있다. ( 아래는 확률에 대한 식 )
      • ( 온도 T가 높을수록, 에너지 차이가 클지라도 나쁜 해를 선택할 가능성이 존재 . 이를 통해서 초기에는 다양한 해를 탐색하며, 점차 좋은 해로 수렴하게 한다.)

확률에 대한 식

• 5. 온도를 일정한 비율로 서서히 낮춘다. 혹은 다른 복잡한 스케줗 알고리즘을 사용할 수 있음.
  • 온도가 낮아질수록, 나쁜해를 수용할 확률도 낮아지며, 탐색이 점차 '보수적'으로 변한다.
• 6. 종료 조건 만족시에 알고리즘을 종료한다.
  • 종료조건들....
    • 온도가 특정 임계값이하로 떨어진 경우
    • 일정 횟수