The 8-queens problem
- Complete state formulation (먼저 퀸을 다 배치한 후 이동한다) -> Local Search 에서 사용
- 8(어떤 퀸을 움직일지) x 7(그 퀸이 움직일 수 있는 칸) = 56 successors 가 존재할 수 있다.
- Heuristic cost function h : 퀸들 중에서 공격할 수 있는 쌍의 개수
h = 0 일때 goal state 이다. h = 8x7 / 2 는 h의 최댓값이 될 것이다.
칸에 적혀있는 숫자는 퀸을 그 칸으로 이동했을 때 h의 값이 된다.
The hill-climbing search algorithm
problem 을 input 으로 받고 state(local maximum) 를 return 하는 함수이다.
노드를 만들고, 그 노드를 current 노드로 지정한다.
current 노드의 successor 중 highest/lowest-valued (best) 인 노드를 골라서 neighbor 로 만든다.
- h값이 높은 것을 찾아가는 알고리즘 -> steepest ascent (가장 가파른) algorithm 이라고 한다.
- h값이 낮은 것을 찾아가는 알고리즘 -> steepest descent algorithm 이라고 한다.
만약 neighbor.VALUE 가 나보다 좋지 않다면 (highest의 경우) current.STATE 를 return 한다.
neighbor 가 더 좋다면 current 를 neighbor 로 지정한다.
-> 알고리즘은 "peak" 에 도달하면 멈춘다. (가장 좋은 곳 = 꼭대기)
예시)
가장 좋은 neighbor 인 12 중에서 무작위로 하나를 고른다.
이때 current 는 12가 된다.
5번의 step 를 거친 후 h = 1이 된다.
이때, 위 알고리즘에서는 h = 1을 solution 으로 찾고 알고리즘이 종료된다.
후계자 중 h = 0 인 neighbor 을 찾을 수 없기 때문이다.
state space 사이에 action 들은 복잡한 그래프 형식으로 이루어져 있다. 이때 복잡한 그래프를 3차원에 배열했다고 가정하면, state 사이의 h값에 따라서 높이가 결정될 수 있다. 처음 initial state 에서부터 더 높은 곳을 찾아서 올라가다가, 더 이상 높은 곳에 갈 수 없는 peak 에 도달했을 때 알고리즘은 종료하게 된다. 이를 3차원 배열이 아닌 더 간단한 형태로 표현한 것이 state-space landscape 이다.
x축은 1차원 직선 상에서 state 들이 움직인다고 가정한다. y축은 hueristic cost function 이다.
이 경우는 h가 클 수록 좋은 landscape 이다. 만약 h가 작을 수록 좋은 경우라면 그래프를 상하로 뒤집고, maximum 대신 minimum 을 사용할 것이다.
현재 current state 에서 취할 수 있는 action은 왼쪽 혹은 오른쪽으로 가는 것인데, 이때 오른쪽으로 가는 것이
h가 커지므로 위로가는 action을 취할 것이다. 이때 local maximum (내 주변에서 가장 좋은 곳) 에 도달하면 어떤 액션을 취하더라도 모두 h가 더 작아지므로, 알고리즘은 종료되고 solution을 리턴하게 된다. 그러나 실제론 더 좋은 solution이 존재한다. 이때 가장 좋은 solution 을 global maximum 이라고 한다.
-> initial state 에 따라 global maximum 에 도달할 수 있다. 그러나 어디에서 시작해야 할지를 알 수가 없다.
- local maxima : 주변에서는 가장 좋지만 global maximum 보다는 좋지 않다.
- plateaux : flat / shoulder
8-queen 문제의 경우,
86%의 확률로 global maximum 을 찾지 못한다.
이때 sideways moves 를 허용한다면, 평행이동이 가능하다. 즉, 나랑 똑같은 h의 경우에도 이동할 수 있다.
shoulder 의 경우 sideway moves 를 허용하면 더 높이 올라갈 수 있지만,
flat 의 경우 평평한 곳에서 무한 반복이 일어날 수 있기 때문에 움직임의 횟수에 제한을 둔다.
따라서 100번의 움직임의 제한 하에 sideway moves로 알고리즘을 진행한다면, 94%의 확률로 성공하게 된다.
Hill-Climbing Search 의 변형
- Stochastic hill climbing : 항상 가장 높은 쪽으로만 가는 것이 아니라 선택에 확률을 둔다. 이때 낮은 확률로 local maxima 를 피할 수 있게 된다.
- First-choice hill climbing : successor 가 매우 많을 때 사용하는 방법이다. 무작위로 successor 를 생성하다가 좋은 것이 나오면 그곳으로 움직인다.
Random-Restart Hill-Climbing Search
- 무작위로 initial state 를 생성하면서 hill-climbing search 를 goal 을 찾을 때까지 여러번 수행한다.
- 만약 성공 확률이 p라면, 평균 수행 횟수는 1/p 이 된다. 예로 성공확률이 0.1 이라면 평균 수행 횟수는 10번이 된다.
- 이때 성공횟수는 1번이기 때문에 실패횟수는 (1/p) - 1 이 된다.
- sideway moves 를 허용한 경우와 허용하지 않은 경우 평균 수행 횟수
-> 8-queen 의 경우 sideway 를 추가하지 않는 것이 더 효율적이다.
state-space landscape 에 local maxima 이나 plateaux 가 별로 없다면, random-restart 로 solution 을 빨리 찾을 수 있다. 즉, hill-climbing search 로 solution 을 찾는 것은 landscape 의 모양과 관련이 있다.
그러나 많은 AI 문제들은 local maxima 를 많이 가지고 있기 때문에 보통은 local maximum 을 찾는 것에 의의를 둔다.
댓글