[인공지능] Hill climbing search

Local Search

Path 에는 관심이 없고 Goal 자체를 찾는게 목적일 때 사용

h(n) : heuristic 함수

Hill-Climbing Search

Steepest descent(ascent) 알고리즘 : 가장 가파른 알고리즘

현재 노드의 후임자(successor) 중에서 가장 좋은 값이 현재 자신보다 좋으면 이동하는 알고리즘

더 이상 자신보다 좋은 successor 를 발견하지 못하는 순간 종료

8-queen example

queen 을 옮겼을 때 서로 공격할 수 있는 queen 의 수를 h(n) 으로 사용한 결과 정답을 찾지 못하는 문제를 발견

State-space landscape

클 수록 좋은 값을 찾는 문제에서 Hill-Climbing 알고리즘의 문제점을 보여주는 landscape

현재 위치에서 Greedy 하게 움직이다보니 global maximum 을 찾지 못함

 

Local maximum : 주변에서는 제일 좋지만 global maximum 보다는 나쁜곳

Plateaux, shoulder : 평평한 local maximum

Ridges

Sideway moves

8-queen 문제의 경우 86% 확률로 정답을 찾지 못함

goal 을 찾으면 평균 4번, 찾지 못하는 경우(Local maximum) 3번만에 알고리즘이 끝남

 

Plateaux 에서도 움직일 수 있는 Sideway moves 를 허용한 8-queen 은 6%확률로 정답을 찾지 못함

goal 을 찾으면 21번, 찾지 못하는 경우에는 64번만에 알고리즘이 끝남

 

단 sideway moves 를 할 때 plateaux 에서만 무한으로 왔다갔다 할 수 있으므로 이동 횟수를 제한해야함

Stochastic hill climbing

h(n) 이 좋을수록 해당 노드로 이동할 확률은 높지만 100%는 아님

 

100% 보장까진 아니지만 운이 좋다면 local maximum 문제를 회피할 수 있음

First choice hill climbing

hill-climbing 과 비슷하지만 기존의 것은 모든 successor를 만들어 두고 가장 최적의 것을 골랐음

하지만 successor 가 엄청나게 많은 경우 이는 부담이므로 successor 를 생성하다가 자기 자신보다 좋은 것을 발견하면 바로 이동함

Random restart hill climbing

init state 의 위치를 바꿔가면서 수행하는 알고리즘

 

global goal 을 찾을 확률 p, 평균 실행횟수 n

1번 성공했을 때 평균 실패 횟수 = 1/p - 1 = (1 - p) / p

 

8-queen sideway move 허용 안한 경우

성공 시 평균 4회, 실패 시 평균 3회 알고리즘 수행.   p = 0.14

falure = (1 - 0.14) / 0.14 = 약 6

평균 알고리즘 시도 횟수 : 1(success) * 4 + 6(failure) * 3 = 약 22회

 

8-queen sideway move 허용 한 경우

성공 시 21회, 실패 시 평균 64회 알고리즘 수행. p = 0.96

falure = (1 - 0.96) / 0.96 = 1/24 = 약 0.04

평균 알고리즘 시도 횟수 : 1(success) * 21 + 0.04(failure) * 64 = 약 25회

 

따라서 sideway move 허용 안한 경우가 더 효율적임

Hill climbing 정리

• Local max 와 plateaux가 적으면 좋은 알고리즘

• 대부분의 알고리즘은 local max, plateaux 가 많음

• 따라서 적당히 좋은 local-maximum 을 찾는것으로 타협

• incomplete : 반드시 goal 을 찾는다는 보장은 없음