인공지능의 탐색방법 - Local Search (Hill Climbing Search, Simulated Annealing Search, Local Beam Search, Genetic Algorithm)

https://cs-ssupport.tistory.com/429

[AI] Local Search

"오늘 수업 내용은 위의 블로그에서 너무 잘 나와 있기에 위의 블로그에서 설명을 많이 참고하였습니다. 해당 포스팅보다 더 자세한 내용이 궁금하시다면 위의 블로그를 보면 더 좋을것 같습니다."

1. Local Search의 특성

Local search를 살펴보면 매 순간마다 이전 순간보다 더 최적화 된 방향을 찾아간다는 특징이 있다. Open list에서는 명령어를 우선순위 큐에 맞춰서 집어 넣게 되는데, 현재 위치만 살펴보고 다음 단계로 넘어가기 때문에 공간 복잡도에서는 엄청난 이익이지만 단점은 현재 위치에서 좋아보이는 것만 하기 때문에 계산적으로 보면 최선은 아닐 수 있다.

2. N-Queens 문제

N-Queens 문제는 퀸이 체스판에 여러개가 있을 때 충돌 횟수를 계산하는 것이다.

체스판에서 다음 수를 생각해 볼 때 체스를 한번 움직이는 행위를 할 때마다 퀸끼리의 충돌횟수가 달라지므로 충돌횟수를 줄이는 것을 찾는 것은 단계별로 최적값을 계산하는 케이스로 볼 수 있다.

3. Hill Climbing Search(언덕 오르기 탐색)

출처 : https://cs-ssupport.tistory.com/429

그래프 형태로 보면 최적점을 향해 가기 때문에 지속적으로 최적점을 향해 가게 되지만 (local max를 찾는다.)
하지만 local  max를 찾더라도 global 기준에서는 다양한 지점이 존재하기 때문에 손해보는것도 결국에는 허용이 될 수 밖에 없다. 부분적으로는 항상 최적을 추구하지만 전체적으로는 손해를 보는 구간도 존재한다는 것이다. 저 빨간 점을 최적으로 찾더라도 결국 전체적으로 는 빨간점과 노란점 사이의 손해보는 구간도 거쳐야 한다는 것이다.

여기서 타고 내려가면 점진적 하강, 타고 올라가면 점진적 상승 (gradient decrease, increase)라고 부른다. 근데 이건 이전에 배운 그리디 서치와 비슷하다는 생각이 들지 않는가? 그래서 이러한 언덕오르기 탐색은 로컬 그리디 서치라고도 부른다고 한다.

출처 : https://cs-ssupport.tistory.com/429

다시 돌아와서 maximum만 구한다고 친다고 해도 maximum에는 여러 종류가 존재한다. 이에 따라서 각 상황에 맞는 다양한 언덕오르기 서치가 존재한다.

1. Stochastic HC -> 경사도의 정도를 보고 가장 가파른 곳을 선택

2. First-choice HC -> 더 좋은게 나올 때까지 계속해서 연속적인 다음 지점을 탐색

3. Random-choice HC -> 아예 시작점 자체부터 매번 랜덤하게 선택

 

4. Simulated Annealing Search

Annealing은 담금질이라고 한다.

담금질처럼 좋은 서치와 나쁜 서치를 반복해 가면서 최적의 지점을 찾는 것이다.

언덕오르기는 계속해서 오르기만 하지만 Simulated Annealing에서는 손해가 크지 않다면 언덕을 내려가기도 한다고 할 수 있다.

출저 : https://cs-ssupport.tistory.com/429

수도 코드를 보면 VALUE가 0인 경우에도 next가 current보다 더 좋아지는 정도가 크지 않다면 확률적으로 음수의 VALUE를 선택하여 LOCAL MAXIMUM에만 최적화 되는 것을 방지한다.

절대로 음수의 가치를 고려하지 않는다면 언덕오르기 아니면 Simulated Annealing 탐색 이라고 한다.

5.  Local Beam Search

앞의 두 탐색은 "현재" 탐색 포인트가 한 점이지만 Local Beam Search는 현재 시점의 탐색 포인트를 여러 개를 두는 것이다.

초기 상태는 랜덤한 K개의 상태를 두며 어느 하나로도 골에 도달할 시에는 탐색을 종료하는 것이다.

출저 : https://cs-ssupport.tistory.com/429

그러나 각 state가 동일한 경로 안에 있을 확률도 있기때문에 Local Maximam 문제를 완전히 해결한 것은 아니라고 한다.

6. Genetic Algorithm - 유전적 알고리즘

k개의 랜덤한 상태에서 시작을 하며 재밌는 사실은 결국 생물학적 진화로부터 영감을 받았다는 것이다.

각 상태는 평가 함수를 통해서 평가가 되는데 각 단계에서 가장 적합한 상태가 선택되고 과정은 가장 적합한 상태가 발견될 때까지 반복된다.

각 State가 문자열로 인코딩 되어 있고. 이 상태 하나를 염색체로 문자열 안의 bit 하나를 유전자로 표현한다.

다음세대는 GenaticOperators를 통해서 생성이 되며 아래 방식들이 이런 Operation에 해당된다.

Replication (복제) - 이전세대에서 우수한 것을 다음 세대로 넘기기

Selection (선택) - 우수한 state를 선택하여 새로운 세대 생성

CrossOver(교배) - 선택한 쌍들을 교환하여 새로운 유전자 만들기

Mutation(돌연변이) - 모종의 이유로 부모와는 다르게 특성이 변경됨

https://cs-ssupport.tistory.com/429

 

위에서 숫자가 체스판에서의 퀸의 위치라고 봤을 때 충동하지 않는 쌍의 횟수를 각각 구할 수 있다.

위의 표를 보았을 때 초기 집단에 있는 충돌하지 않는 쌍의 횟수를 각각 화살표에 표시해두고 여기서 전체 비중 대비 해당 유전체가 차지하는 %를 수치로 담고 있다. 이에 따라서 선택을 하는데 이때 다양성을 보장하기 위해서 랜덤한 지점에서 커팅을 한다.

커팅을 한 후에는 교배를 통해서 부모끼리의 값을 섞어 준다.

하지만 이런 경우 돌연변이 단계에서 보여주는 것처럼 기존에 없었던 특성도 나타나게 된다.

이 과정을 통해서 볼 수 있듯이 "확률적"으로 상태변이를 해서 다양성을 보장하는 것이 GA라고 할 수 있다.

 

7. Online Search VS Offline search

이러한 탐색들을 분류하는 방식 중 하는 온라인, 오프라인 서치가 있다.

Offline search는 데이터가 들어오고 나서 다 모으고 나서 실행하는 것이고. 액션을 다 끝내고 결정하는 방식이다.

OnlineSearch는 데이터가 들어오자마자 중간중간 계속해서 실행하고 결정하는 방식이다.

온라인 서치는 환경이 잘 안보이고 전체를 보기 어려울 때 사용된다.