• 반복 향상 알고리즘 Iterative improvement algorithms
  • 많은 최적화 문제에서 path에 관심을 두지 않는다. Goal State 그 자체가 목적이다.
• Tree Search Algorithm과 다르게 State space = complete configurations이다.
  • Tree Search에서는 초기상태에서 확장되어 가는 방식
  • Loacl Search에서는 초기상태가 Optimal하지 않지만 완전한 배열이고, 변화를 주면서 optimal solution을 찾아가는 방식
• State space의 구성
  • Location = state
  • Elevation = Heuristic cost function or objective function
    

Hill-climbing Search (Gradient Ascent/Descent Search)

• Ascent : Maximum
• Descent : minimum
• Ascent 기준 기술. Descent는 maximum을 minimum으로 바꿔 생각.

Psuedo Code

출처 :

Concept 개념

1. state value가 증가하는 방향으로 state를 계속해서 이동한다.
2. 현재 state가 주변 지점보다 높으면 / 낮으면 현재 state를 Local maximum / minimum으로 return 한다.

DrawBack 문제점

• 근접한 neighbor만 탐색(greedy)하기 때문에 Local maxima에 갇힐 수 있다.

Solution 해결책

Stochastic hill climbing

• 주변을 다 탐색한 후, 경사도에 따라 확률을 정해두고, 통계적으로 방향을 선택한다.
  Chooses at random from among the uphill moves with probability
  proportional to steepness

First-choice hill climbing

• 좋은 successor가 나타나면 그것으로 대체하여 진행
  Generates successors randomly until one is found that is better
  than the current state

Random-restart hill climbing

• initail state를 랜덤하게 여러 번 생성하여 hill climbing search를 진행
  Conducts a series of hill-climbing searches from randomly
  generated initial states
• Very effective Powerful solution

Simulated Annealing Search

• 담금질 기법 탐색
• minmization 기준 기술. maximize도 가능.

Idea

• valley-descending의 효율성 + random walk의 완전성
• 'Bad Move'를 일부 허용함으로써 local minima에서 탈출한다.
  - 점차적으로 step size와 frequency를 줄여나가며, 허용 빈도를 줄여나간다.

  

Pseudo Code

• $schedule$ : $T$를 점차적으로 줄이는 함수 Inital T → 0

  
  
  $next.VALUE - current.VALUE < 0$
  $next.VALUE < current.VALUE$

  1. next값이 current 값보다 작다.
  2. minimization 과정 중이기 때문에 next가 current보다 정답에 가깝다.
  3. 따라서 current를 next로 갱신한다.

특징

• Random Move. best move가 아니라 random move
  • good move면 항상 그 쪽으로 진행
  • Otherwise! 즉, bad move라면 확률적으로 진행을 결정.(갈수도 있고, 안 갈수도 있고.)
  • 여기서 확률은 $e^{-ΔE/T}$
    → T 감소 : 확률 감소 - 진행할수록 확률 감소
    → ΔE 증가 : 확률 감소 - 더 bad move일수록 확률 감소
  • schedule이 T를 충분히 천천히 낮춘다면, 1에 가까운 확률로 global optimum을 찾을 수 있다.
  • $T → 0$ : first-chois hill climbing

Genetic Algorithms

• 유전법칙을 표방
• 고유의 표현을 사용
  • individual : state
  • fitness function : objective function

과정

• pair를 선택해 짝짓기 Crossover 한다.

1. Chromosome(염색체) design

• problem을 해결하기 위해 individual(state)을 적절한 방식으로 represent하는 과정

2. Initializing : individuals population(initial state)을 생성하여 초기상태를 구성
3. Fitness : Fitness Function을 이용해 각 individual을 평가
4. Selection : 규칙에 따라 확률적으로 조상을 선택
5. Crossover : 선택된 조상을 규칙에 따라 서로 Crossover
6. Mutation : 랜덤하게 돌연변이를 일으킴.
7. Update Generate : 만들어진 세대로 population을 업데이트 한다.
8. 3번으로 돌아가 과정을 반복한다.

Pseudo Code

Continuous State Space

Gradient method

• $x → x +/- \alpha ∇f(x)$ $∇f(x) = f'(x)$
• Too small $\alpha$ : 많은 스텝이 필요함 → time complexity가 커짐
• Too big $\alpha$ : global maxima / minima를 찾지 못할 수도 있음.
• $∇f(x) = 0$인 지점이 Critical Points

Line Search(for minmization)