고급 검색 기법

<검색을 통한 문제해결>에서 관찰 가능, 결정론적, 기지 환경을 가진, 그리고 해답이 하나의 동작열인 단일범주의 문제들

-> 이 가정들을 완화하면 어떻게 되는지에 대한 것이다.

 

상태공간 안에서 초기 상태로부터의 경로들을 체계적으로 탐색하는 대신 현재 상태 한두 개를 평가하고 수정하는데 주력하는 Local Search

 

국소 검색 알고리즘과 최적화 문제

• 목표로의 경로가 중요하지 않다면, 이전과는 달리 경로들을 전혀 신경 쓰지 않는 부류의 알고리즘들을 고려한다
• Local Search 알고리즘들은 현재 노드만 사용하여 일반적으로 오직 그 노드의 이웃 노드로만 이동하는 식으로 작동
• 장점
  • 메모리를 적게 소비한다.
  • 체계적 알고리즘에 적합하지 않은 커다란 또는 무한한 상태 공간에서도 적당한 해답을 찾아내는 경우가 많다.

언덕 오르기 검색

• 값이 증가하는 방향으로, 즉 오르막으로 계속해서 이동하는 루프로 이루어진다.
• 루프는 주변에 더 큰 값이 없는 정상(Peak)에 도달하면 종료
• 알고리즘은 검색 트리를 유지하지 않으므로, 현재 노드를 위한 자료구조는 상태와 목적 함수의값만 담으면 된다.
• 언덕 오르기는 현 상태의 바로 이웃한 값들만 고려한다. 그 밖은 미리 고려 X
• 최상의 후행자가 둘 이상일 때, 일반적으로 언덕 오르기 알고리즘은 그냥 그 후행자 중 하나를무작위로 선택한다.
• 다음에 어디로 갈지 고려하지 않고 눈앞의 상황에서 가장 좋은 이웃을 선택한다는 점에서 언덕오르기를 탐욕적 국소 검색
• 탐욕적 국소 검색:다음에 어디로 갈지 고려하지 않고 눈앞의 상황에서 가장 좋은 이웃을 선택한다는 점에서 언덕오르기

• 언덕 오르기는 해답을 향해 빠르게 나아가는 경우가 많은데, 이는 대체로 나쁜 상태를 개선하는것이 상당히 쉽기 때문이다.

• (a)는 하나의 퀸을 중심으로 왼 -> 오른쪽으로 공격할 수 있는 퀸을 세면 17이 된다.
• (a)의 숫자는 퀸 하나를 옮기면 한 방향으로 공격할 수 있는 퀸의 총 공격횟수 이다.

BUT, 곤경에 빠지는 경우가 많다.

• 극대값
• 능선
• 대지
• 어깨
• 횡이동

여러 변형이 고안되었다.

• 확률론적 언덕 오르기
• 최초 선택 언덕 오르기
• 무작위 재시작 언덕 오르기

모의 정련

효율성과 완결성을 모두 제공하도록 언덕 오르기와 무작위 보행을 결합한 시도이다.

-> 먼저 세게 흔드는 것으로 시작해서 흔들기의 강도를 점차 감소한다.

• 후행자들 중 하나를 균등 분포 난수로 선택하는 방식은 완결적이지만 극도로 비효율적이다.
• 내리막 이동이 없는 오르기 알고리즘은 극대값에 머무를 수 있으므로 완결성을 보장하지 못한다.

국소 다발 검색

• k개의 상태를 추적한다.
• 무작위로 생성한 상태 k개로 시작한다.
• 각 단계마다 k 개의 모든 상태의 모든 후행자를 생성한다.
• 그중 하나가 목표이면 알고리즘이 끝난다.
• 그렇지 않으면 전체 후행자 중 최상의 k 개를 선택해서 같은 과정을 반복한다.

유전 알고리즘

확률론적 다발 검색의 한 변형으로, 두 부모 상태의 결합에 의해 생성된다

• 유전 알고리즘은 무작위로 생성한 k개의 상태들로 시작한다.
• 검색 공정 초기
  • 교차에 의해 알고리즘이 상태 공간을 좀 더 큰 보폭으로 탐색한다.
  • 나중에 대부분의 개체가 상당히 비슷해지면 좀 더 작은 보폭으로 탐색

연속 공간의 국소 검색

• 대부분의 실세계 환경은 연속적이다.
• 지금 까지 설명한 알고리즘 중 연속적인 상태와 동작 공간을 처리할 수 있는 것은 최초 선택 언덕 오르기와 모의 정련이다.
• 연속 공간에서 분기 계수가 무한대이기 때문에 작동하지 않는다.

비결정론적 동작들을 수반한 검색

• 환경이 완전히 관찰 가능하고 결정론적이며 에이전트는 자신의 각 동작의 효과를 정확히 안다고 가정
• 에이전트는 임의의 동작열로부터 어떤 상태가 나오는지 계산할 수 있으며, 자신이 어떤 상태에 있는지도 항상 알 수 있다.
• 동작 이후 에이전트의 지각들은 새로운 정보를 전혀 제공하지 않는다.

예)

변덕스러운 진공청소기

동작: Left, Rigth, Suck

목표: 모든 먼지를 빨아들이는 것

해답: 하나의 동작열

문제: 변덕스러운 진공청소기에 Suck 동작에 다음과 같이 작동한다.

• 가끔은 인접한 칸의 먼지도 치운다.
• 깨끗한 칸에서 이 동작은 가끔 카펫에 먼지를 쏟아 붓는다.

-> 다음과 같은 상황이 일어나면, 우발적 계획이 필요하다.

AND-OR 검색 트리

OR 노드

결정론적 환경에서 분기는 오직 각 상태에서의 에이전트 자신의 선택에 의해서만 일어난다.

AND 노드

비결정론적 환경에서 분기는 각 동작의 결과에 대한 환경의 선택

예)

1의 Suck 동작은 집합 {5,7}의 한 상태로 이어지므로, 에이전트는 상태 5를 위한, 그리고(and) 상태 7을 위한 하나의 계획을 찾아야 한다.

부분 관찰 가능 환경의 검색

• 에이전트의 지각들만으로는 정확한 상태를 결정할 수 없다
• 에이전트가 여러 가능한 상태 중 하나에 있다면, 비록 환경이 결정론적이라고 해도 하나의동작은 여러 가능한 결과 중 하나로 이어진다
• 이 환경 문제를 푸는 핵심 개념은 믿음 상태이다.
  • 믿음 상태: 현재 심점까지 동작열들과 지각들이 주어졌을 때 에이전트가 현재 처한 가능한 물리적 상태들에 관한  에이전트 자신의 믿음을 나타낸다.