4.1.3 Local beam search(시험 - 이어서)
Local Beam Search는 Best-First Search에서 기억 노드의 수를 제한하는 방법임
이 탐색 방법은 기억 공간을 축소시키기에 굉장히 유리하지만 가지치기가 지나치게 빠름.
실제로 사용하는 방법은 먼저 BFS Search로 다음 상태의 해 집합을 구한 뒤에, 해 집합을 Goal에 가까운 순서대로 정렬함. 그리고 사전 설정된 수 만큼의 해 집합을 유지하고 나머지는 잘라내는 방법임
좀 더 구체적으로 말하자면
시험
- 무작위로 생성된 State들인 K에서 시작함
- 각 단계에서 모든 K의 자손 노드를 생성함
- 자손 노드 중에서 어느 하나가 목표인 경우 알고리즘은 해를 찾음
- 그렇지 않으면 목록에서 K의 최선의 자손 노드를 선택하고 이를 반복
- Beam 탐색의 병렬 검색은 가치가 없는 자손 노드를 빠르게 제거하고 가장 그럴싸한 노드로 이동할 수 있게 해줌
- 확률적인 Beam 탐색에서는 유지된 자손 노드들이 그들의 효용성을 기반으로 선택
하지만 local beam search는 너무 지엽적인 구간만을 다루기 때문에 다양화하는 것에는 매우 약하다. 그래서 나온 것이 stochastic beam search 알고리즘이다. 이 알고리즘은 기존 지엽적인 local beam search에서 자손 노드를 랜덤하게 고르는 것으로 문제를 해결한다.
4.1.4 Genetic Algorithms
A Genetic Algorithms(GA) 유전자 알고리즘은 자연계의 원리와 같이 좋은 유전자는 남고 안좋은 유전자는 도태시켜 자손으로서 변영하지 못하게 되는 섭리가 있습니다. 또한 중간에 돌연변이 유전자가 개입할 여지도 있는 등등 최종적으로 가장 우수한 유전자는 살아남는다는 점을 이용한 알고리즘입니다.
이때 Genetic Algorithms은 STOCHASTIC BEAM SEARCH와 유사한점을 가지고 있는데 GA는 랜덤하게 상태를 생성한다는 점이다.
그래서 GA는 STOCHASTIC BEAM SEARCH과 같이 처음에는 K라는 랜덤 state로 시작합니다. 다음 자손으로 세대가 교체될 떄 모든 유전자들은 Fitness Function에 의해 평가됩니다. 이 Fitness가 높게 측정되는 유전자에 한해서 번식이 가능하게 됩니다. 그렇기 때문에 이 기준이 되는 Fitness를 결정하는 것이 GA에서 가장 어려운 문제가 됩니다.
가치가 높은 각각의 유전자끼리 만나게 되면 이제 랜덤하게 선을 긋고 그 선을 기준으로 Crossover를 합니다. 그렇게 Swap을 행하고 난 뒤에는 자손 문자열 중에서 임의적으로 Mutation(돌연변이)를 만들어주면 됩니다. 하지만 Mutation은 항상 만들어주는 것이 아니라 임의의 확률로 이행이 되어야한다.
현대에 와서는 이 방법은 아주 유명한 휴리스틱 탐색 방법이 되었지만 상당히 비효율적입니다.
위의 그림은 유전자 알고리즘의 자손과 Crossover 그리고 Mutation에 대한 대략적인 설명을 그림으로 표현하고 있습니다.
시험
이제 GA 알고리즘의 흐름에 대해서 생각하여 보자.
1. 주어진 개체군에 대해서 적합성을 평가하여(fittness function) 각 객체들이 선택될 확률을 계산한다.
2. 해당 확률에 맞게 개체들을 다수 선택한다.
3. 선택된 개체들의 유전자를 적절히 섞어 다음 세대로 계승한다.
4. 다음 세대의 객체들 사이에서 일부 객체의 유전자를 임의로 바꾸어 돌연변이를 만든다.
5. 원하는 수준의 솔루션을 찾을 때까지 이를 반복한다.
4.2 Local Search In Continuous Spaces(시험X)
유전자 알고리즘을 좀더 확장하여 소프트웨어 화한 것이 Evolutionary Programming 이라고 합니다.
4.3 Searching with Nondeterministic Actions
이 장에서는 제약 조건들이 있는 상황들이 나옵니다. Classical한 알고리즘에서 제약 조건들이 들어감에 따라서 기존의 알고리즘으로는 해결하기 벅찬 상화이 생기니까 이런 새로운 방법들이 고안되게 되었다.
Searching with Nondeterministic Actions (비결정적인 상황에서의 탐색)은 현실세계에서는 우리가 아무리 정상적인 선택을 했다고 하더라도 불투명한 환경에 따라서 제 3의 방해나 간섭이 들어올 수 있기 때문에 비결정적인 어떤 Action도 고려하여야 한다.
4.3.1 The Erratic Vacuum World(불규칙한 청소기 세상)
말 그대로 고장이 난 고장이 난 진공청소기 문제이다.
위의 그림은 불규칙한 청소기 세상의 제약조건을 보이기 위해 나타낸 그림들이다. 만약 위와 같은 상황이 된다면 다음 2가지의 제약조건이 생길 수 있다.
- 깨끗한 방에서 Suck을 했을 때 특정 확률로 오히려 방이 더러워진다.
- 가끔은 Suck을 하면 현재 방만 청소하는 것이 아니라 인접한 방도 같이 청소를 해버린다.
4.3.2 AND-OR search trees
그래서 이것을 묘사하기 위해서 AND-OR Search Tree를 활용. 이제 다음 질문으로 정확히 무작휘 해를 어떻게 찾아낼 수 있겠냐는 것입니다. 그래서 AND-OR 탐색 트리를 사용하게 됩니다.
여기에서 OR노드는 각각의 현재 State에서 어떻게 변화할 수 있는지를 보여줍니다.(Suck, Right, Left)
반면에 AND 노드는 각각의 행동의 결과에 환경적인 선택에서 추가적으로 발생하는 가지들을 의미합니다.
위 사진은 1번의 상태에서 시작했을 때를 가정하고 그린 AND-OR Search Tree입니다.
4.3.3 Try, try again
이번에는 Suck과 관련된 Nondeterministic이 아니라 이동에 관한 Nondeterministic입니다. 만약에 자신이 의도한 결과가 나오지 않으면 Percept를 이용해 인식하면서 원하는 결과가 나올 때까지 다시 행동을 반복하는 것입니다. 말 그대로 Try-Try Again입니다.
위 그림에서 5번의 상태에 처해있다고 생각했을 때 우리는 6번의 상태로 Right를 통해 건너가야겠죠. 하지만 바닥이 미끄러워서 이동에 실패했다면 이동할 때까지 게속해서 Right를 반복하면 되겠죠.
이상 위에까지가 시험
