[인공지능 : AI, Artificial Intelligence] Lecture 7 : Local Search

Lecture 7

Local Search

1. Local Search는 path가 중요하지 않을 때 사용한다. goal이 주어지지 않으며, path또한 찾지 않는다. 특히, global에서 가장 큰 제일 좋은 state를 찾는 것이 목표이다.
   • Traditional Search는 goal state로 가는 path를 찾는 것이어서, 전체 state space를 활용하고, 현 상태에서 다음 상태로 가는 traversal 전략이 정해져 있었다.
   • 경로를 찾는 것이 아니므로, random state 에서 시작한다. 각 state 는 object function 에 의한 value 를 가지고 있다. 이를 Fitness 값이라고도 한다.
2. current state를 유지하면서, imporve 한다. 바로 옆의 state로만 움직인다. 즉, 계속 옆으로 이동하면서 global maxima로 가겠다는 의미이다.
3. search tree 만들 필요 없다.
4. 메모리 사용량이 적다. 하나의 현재 state와 그에 이웃한 state만이 메모리에 있다.
5. good enough solution을 얻는다. continous or large state space에서.
6. Optimizer function에서 best state를 찾는 optimization problem에 적합하다.

Local Search는 다음 두가지 행동패턴을 지닌다.

1. exploitation
2. exploration은 보통 두 가지로 나뉜다.
   • random 사용
   • stochastic 사용

아래 사진에서 local maximum이 아닌, global maximum으로 가도록 유도해야한다.
이에 대한 방법은 아래에서 다룰 것이다.

크게 다음과 같은 전략이 있다.

1. Hill climbing : steepest ascent/descent
2. Simulated Annealing : Stastical physics
3. Local beam Search
4. Genentic Search

Local Search에는 3가지 이슈가 있다.

• local search 전략 : iterative imporvement
• 각 state의 정의
• 각 state의 value 정의(목적함수)
• 오프라인 검색(offline search) 알고리즘 : action에 앞서 완전한 해답을 계산 action한다.
• 온라인 검색(online search) 알고리즘 : search와 action을 교대로 실행한다.(interleave). Local Search가 이에 해당한다.

Hill Climbing

• greedy local search라고도 한다.
• 나를 중심으로 local에서 가장 좋은 쪽으로 이동하는 것을 반복하면(iterative) 점점 더 좋은 답으로 이동하여 결국 아주 좋은 goal을 찾게 될 것이라고 희망하는 알고리즘.
• 각 state 때마다 바로 이웃의 good state로만 이동한다.
• uphill로만 이동한다.
• local/global maximum에서 멈춘다.
• 하나의 node는 state와 objective funtion의 value를 지닌다.

다음은 슈도코드이다.

function HILL-CLIMBING(initialState)
  return State that is local maximum

  initialize current with initialState

  loop do
    neighbor = a highest valued successor of current
    if neighbor.value <= current.value
      return current.state
    current = neighbor

다음과 같은 코드로 표현할 수도 있다.

Hill Climbing을 이용할 때, local maximum에서 벗어나는 방법

1. Sideways moves : soulder, flat 지역 벗어나는 방법
2. random restart : local maxima를 극복하는 방법. 여러 군데에서 다시 시작하는 것
3. stochastic uphill move : uphill move에 대한 steepness를 이용해서 selection probability을 정하고, 이에 따라서 각 방향에 대해서 random하게 선택해서 이동

아래 사진을 예시로 들면, 각 방향 중 하나를 선택하는 것을 확률적으로 선택한다는 의미이다.

관용적으로, random이라고 하면 임의의 state에서 재시작하는 것을 의미하고, stochastic이라고 하면 임의의 방향으로 action을 하는 것을 의미한다.

참고할 것

• First-Choice hill climbing
  • 더 좋은 첫번째 것이 나올 때까지 stochastic하게 이웃 state를 추출한다.
• Greesy Hill climbing 은 random 에서 시작해서, 가능한 이웃을 보고 평가해서 그중 제일 좋은 것으로 나간다. (평가는 그 조합(상태)의 최적화 점수)
  • greedy Hill climbing local search는 지나온 과거를 되돌아 보지 않는다. 그래서 local maxima에 빠질 가능성이 높다.
• Greedy best-first search 는 시작 상태가 존재하고, 휴리스틱에 의해 다음으로 간다.

• random restart hill-climbing의 성공 확률이 p라면, 기대값 1/p의 횟수만큼 재시작해야 성공할 수 있다.

simulated annealing

쇠를 단단하게 하는 방법(온도를 높인 후 천천히 식혀서 결정 구조를 확립하는 방법)을 어닐링이라고 한다.
여기에서 모티브를 얻었다.

• hill climbing은 down되지 않는다. 무조건 up한다.
• simulated anneanling은 down으로도 갈 수 있다 확률적으로.
• hill climbing에서 exploration은 다음과 같이 한다.
  • 현재 상태보다 좋으면, 그 곳으로 exploit
  • 현재 상태보다 나쁘다면, 확률적으로 그 곳으로 explore
    • escape local maxima by allowing some “bad” moves
  • randomness를 초기에 주고, 갈 수록 exploitation을 늘린다.
• Optimal : 온도 T를 천천히 줄이면, Optimal하다

function  Simulated-Annealing( problem, schedule)
  return  a  solution  state 
  inputs: problem,  schedule(a  mapping  from  time  to  “temperature”)
  local   variables:   current, next, T(a  “temperature”  controlling  prob.  of  downward  steps)

  current ← Make-Node(Initial-State[problem]) 

  wfor  t ←   1  to  ∞  do
T ← schedule[t]
if  T  =  0  then  return  current
next ← a  randomly  selected  successor  of  current ∆E ← Value[next]  –  Value[current]
if  ∆E  >  0  then  current ← next
else  current ← next  only  with  probability  e^(-∆E/T)

시간이 진행되면서 temperature가 낮아진다. scheduler에 의해서 결정된다.

델타E가 0보다 크면 current가 되도록 이동한다. 아닌 경우에는, 특정한 확률(steepness 이것이 목적함수)을 기반으로만 이동한다.

여기서 steepness(exploration을 결정하는 확률)는 다음과 같은 개형을 지닌다.

$e^(-1/x)$

개형을 보면 다음과 같이,
T가 크면 100의 확률로 shift하고,
작으면 다른 곳으로 random shift할 확률이 줄어든다는 것을 알 수 있다.

다른 곳으로 이동할 확률을 줄임과 동시에,
shifting하는 절대적인 범위도 줄일 수 있다.
즉, 얼마나 많이 움직일지도 조정할 수 있다.

다음은 flow chart이다.

Local Beam Search

• random hill climb는 각각의 시작점이 독립적으로 시작한다.
  • k개를 동시에 병렬적으로 진행, 독립적으로 진행하면 큰 차이 없다.
• Local Beam Search는 이걸 동시에 진행한다.
  • k개를 동시에 병렬적으로 진행, 하지만 독립적이지 않게 한다.
  • 서로 관계성이 있게 start point를 잡는다.
  • 이걸 약간 변형하면 Genetic Algorithm