인공지능 강의 3화 :: 언덕오르기, 모의담금질, A* 알고리즘

인공지능 강의 3화를 보며 배운내용

 

 

Keywords

• 언덕오르기 탐색: 랜덤 상태에서 시작해서 가장 목표에 근접한 후계상태로 이동하는 탐색 알고리즘
• 지역최대치 문제: 시스템 최대치에 해당되는 계수를 찾는 문제에서 실제 최대치가 아닌 주변 극대치에 해당되는 계수를 찾게되는 문제
• 모의 담금질: 탐색공간에서 평가함수의 전역최대치(최소치) 해를 구하기 위한 확률적인 경험적 접근 방법, 현재 상태를 개선하지 않는 후계상태로도 시간에 따라 감소하는 확률로 이동할 수 있도록 함으로써 지역최대치(최소치)에서 빠져나올 수 있게 하는 방법
• A* 알고리즘: 다음 확장할 노드를 결정할 때 그 노드까지 도달하는 경로비용과, 그 노드로부터 목표노드에 도달하기 위한 결로비용 예측치의 합이 최소인 노드를 선택하여 탐색
• 후계노드: 자식노드, 하위노드, 차일드노드
• 평가함수: 비용

 

경험적 탐색

목표 상태를 보다 효과적으로 탐색하기 위해 경험적 지식을 평가함수에 반영

경험을 넣는거라 항상 효과적이지 않을 수 있다

 

언덕오르기 탐색

현재 상태를 확장해서 만든 자식 노드들 중에서 평가함수 계산한 비용이 가장 적은 노드를 다음 확장할 노드로 선택.

 

언덕오르기 평가함수

자식 노드로부터 목표노드에 도달하는 비용을 예측

자식 노드까지 도달하는데 사용된 비용을 고려하지 않음

 

가장 효율적인 해를 찾지는 않는다

=> 같은 평가함수가 나오면 임의로 선택하기 때문

 

등산을 한다고 예를들어

최급상승법(steepest acsent method) <==> 최급하강법(steepest decent method)

가장 높은 고도(비용)로 가능 방법

 

최급상승법의 난제

• 지역최대치 문제: 그 지역에서 높은 봉우리를 정상으로 착각
• 고원문제: 평원에 도달하면 끝인줄 안다.
• 능선문제

 

 

모의 담금질(simulated annealing)

평가함수의 값이 전역최대치(최소치) 해를 구하기 위한 확률적 접근 방법

확률에 의해서 상태가 개선되지 않는 방법으로도 이동한다.

 

시간에 따라 감소하는 확률에 따라 평가함수 값이 개선되지 않는 자식 노드로도 이동할 수 있게 하는 확률적 접근방법

거듭할수록 평가함수가 더 높은 상태로 이동할 확률이 낮아진다.

 

언덕오르기에 비해 시간이 더 많이 걸린다.

*annealing(풀림): 금속, 유리에 열을 가하고 식혀서 응력을 제거해서 변형시키기 좋은 상태로 만드는 것

 

 

A* 알고리즘

최소비용경로가 되기 위한 탐색

평가함수

출발노드에서 한 노드의 비용 + 그 노드에서 목표노드에 도달하는데 필요한 예측 비용

A* 알고리즘에서 평가함수가 최소인 노드를 선택해서 확장.

 

예측비용 <= 실제 비용

h'(n) <= h(n)

=> 이렇게 정의되면 탐색된 경로를 최소비용 경로 보장

 

목표노드까지 도달하는 경로비용을 예측한 값이 실제 비용이하라면(h'(n) <= h(n)이 성립),

최소비용 경로를 탐색하는 것을 보장

 

가정

출발노드부터 n까지 경로 비용: g(n)

g(n)의 예측 비용: g'(n)

n으로부터 목표노드까지 경로 비용: h(n)

h(n)의 예측 비용: h'(n)

OPEN 리스트에 존재하는 노드 n의 평가함수: g(n) +'(n)