Evaluation  Function

평가함수 (evaluation function) 은 heuristic evaluation function 또는 static evaluation function 이라고도 하며, 체스와 같은 게임 (Game) 프로그램에서 돌의 위치가 얼마나 좋은지를 측정하기 위해 최소최대 (Mini-max) 알고리즘에서 사용된다. 평가함수는 일반적으로 빠른 결정이 나도록 설계되며 정확성은 주요 관심사항이 아니다 (따라서 휴리스틱 (Heuristic) 하다) ; 평가함수는 현재의 돌의 위치에서만 평가하게 되며 가능한 돌의 움직임을 탐색하지는 않는다 (따라서 static 하다).

평가함수를 만드는 잘 알려진 전략은, 돌의 위치에 영향을 미친다고 생각되는 여러 가지 요인들의 가중치 합 (weighted sum of various factors) 이다. 예를들면 체스 (chess) 를 위한 평가함수는 다음과 같은 형태를 가질 수 있다 ......... (Wikipedia : Evaluation Function).

 c1 * material + c2 * mobility + c3 * king safety + c4 * center control + ...

휴리스틱 (Heuristic) 은 새로이 생성된 후계 노드들을 heuristic information 에 따라 정해지는 기준에 의해 순서를 정하거나 ,재조정 하는 것으로서 이렇게 함으로써 탐색 (Search) 은 가장 바람직한 부분을 확장시켜 나가게 될 것이다. 이렇듯 순서를 재조정하기 위해서는 노드의 바람직한 정도를 평가하기 위한 척도가 필요한데 이 척도를 evaluation function 이라 한다.

평가함수의 목적은 확장시킬 노드들에게 순위를 매김으로써 어떤 것이 목표노드 까지의 최상의 경로에 있음직한가를 결정하는 것이다. 평가함수은 여러 가지 착상에 근거를 두고 있다. 어떤 노드에 대하여 최상의 경로에 있을 확률을 이용하는 것도 있고, 임의의 노드와 목표 노드들간의 거리 (distance) 나 차이 (difference)를 이용하는 경우도 있다. 게임 (Game) 이나 퍼즐에서는 목표까지의 가능성과 관계된 특성들에 근거를 두는 경우도 있다. 노드를 확장시키기 위한 순서를 규정하는 평가함수은 다음과 같다.

은 노드 n에서의 이 함수의 값을 나타낸다. 즉 출발노드로부터 노드 n을 통하여 목표노드까지의 가는 최소비용경로의 비용에 대한 예측치 (estimate) 이다. 은 출발노드 로부터 노드 n까지의 최적경로 (최소비용경로) 의 실제비용에 대한 예측치이다. 은 노드 n부터 목표 노드까지의 최적경로의 비용에 대한 예측치이다 .............. (김재희 1988)

Site :

GNU chess heuristics : GNU Chess에서 만든 heuristic function

Paper :

평가 함수의 사용 (Using Evaluation Function) : Nils J.Nilsson

얼굴의 특성을 반영하는 휴리스틱 평가함수를 이용한 얼굴 특징 검출 (Facial Features Detection Using Heuristic Cost Function) : 장경식, 한국정보처리학회, 2001

점진적 개념학습의 클러스터 응집도 개선 (The Study on Improvement of Cohesion of Clustering in Incremental Concept Learning) : 박영택. 백혜정, 한국정보처리학회, 2003

적응적 얼굴검출 및 얼굴특징자 평가함수를 사용한 실시간 얼굴인식 알고리즘 (Adaptive Face Region Detection and Real-Time Face Identification Algorithm Based on Face Feature Evaluation Function) : 김지홍. 김정훈. 이응주, 한국멀티미디어학회, 2004