[인공지능] Annealing, Local beam search

Simulated Annealing

function SIMULATED-ANNEALING(problem, schedule) returns  a solution state
  current ← MAKE-NODE(problem.INITIAL_STATE)
  for t = 1 to INFINITE do:
    T ← schedule(t) // t 가 증가할수록 T는 0에 수렴하는 스케쥴링 함수
    if T = 0 then return current

    next ← a randomly selected successor of current // successor 중 하나를 Random 으로 선택
    E ← next.VALUE - current.VALUE // 평가
    if E > 0 then current ← next // current 보다 좋으면 current 로 이동
    else current ← next only with probability eE/T // current 보다 나쁘면 확률적으로 이동

 

eE/T 확률 수식은 알고리즘 초반부에는 1에 가까워서 next 가 잘 움직이다가도 후반부로 갈수록 잘 움직이지 않으며 hill climbing 처럼 동작

Local beam search

탐색 방향으로 여러개로 하여 동시에 탐색

local search 는 현재 상태만을 저장하기에 메모리에 부담이 적기에 여러 노드를 동시에 관리할 수 있음

랜덤으로 선정된 k 개의 initial state 로 시작하고, 이들이 만들어낸 successor 들 중 최고의 k 개만을 추려서 다시 검색을 이어감

random restart hill-climbing 과는 다른 결과를 내는데, k 개의 state 가 항상 successor 를 만들어내는 것은 아니기 때문

Stochastic Beam Search

k 개의 최고 successor 가 아닌 확률적 랜덤으로 선택된 k 개의 successor 를 골라 탐색하는 방법