인공지능의 기초 - 지역탐색

지역탐색(Local Search)

현재 상태에서 더 나은 인접 상태로 나아가는 방법. 

장점

• 메모리가 절약된다.
• systematic paths를 메모리 상에 저장하지 않는다.
• 오직 현재, 인접노드만 메모리상에 존재하게 된다.
• state space가 continuous하거나 무한히 큰 문제에 대해서 합리적인 해를 도출 가능하다.

어떤 경우에 쓸까?

• 가능한 Goal state들을 찾는것 자체가 Solution인 문제들. ex) 채스
• goal state가 곧 solution state가 된다.
• 최적화 문제(Optimization Problems) : 목적함수값이 가장 최적인 state를 찾는 문제
• Goal test, path cost가 없다.
• 목적함수(Object Function) : 최적화 대상을 수치로 표현한 함수.

대표적인 Local Search들

• Hill-Climbing Search
• Simulated Annealing Search

Hill-Climbing Search

이웃 state들 중 가장 좋은 목적함수를 가진 state로 진행하는 방법.

다른 별명들이 많다.
Greedy local search (Greedy는 이웃 state중 무조건 가장 목표에 근접해 보이는 state를 선택 하는 방법 )

Maximization문제 에서는 Steepest ascent, Gradient ascent라고도 하고

Minimization문제 에서는 Steepest descent, Gradient descent라고도 함.

단점 : Local maxima(minima)에 빠져서 Global maxima(minima)에 갈수 없다.

Simulated Annealing Search

Annealing이란 금속을 재결정화 온도 이상으로 가열시키고 천천히 냉각하여 부드럽게 만드는 작업을 말한다. 금속 원자는 가열을 통해 자신이 갇힌 내부 에너지의 local minima에서 빠져나와 천천히 냉각 시킴으로써 전보다 더 낮은 내부에너지로 안정화될 기회를 갖는다. 이러한 개념을 local search에 적용하여 local maxima(minima)문제를 해결한 알고리즘이다.

따라서, Annealing을 시뮬레이팅은 다음과 같이 매핑될 수 있다.

원자 : 노드.

내부에너지 : 목표함수 값.

열 : local minima(maxima)를 거슬러 올라갈 확률.

열은 처음에 고열상태에서 시작해서, iteration을 반복하면서 점점 낮아져간다.

local minima에 갇히지 않게끔, 시작부터 노드 진행의 무작위성을 높게 설정한다. 이후 서서히 방향성이 잡혀가면서 무작위성을 낮춰주어 최적화 노드를 찾을수 있게 한다.