진화적 방법에 의한 규칙 학습 1

<아래 글은 '만들면서 배우는 기계학습' 을 읽고 쓰는 글입니다.>

이번에 다룰 주제는 유전 학습입니다.

유전 학습에 대해 다루기 전에 '랜덤 탐색' 과 '계통적 탐색' 에 대해 집고 넘어갑니다.

앞에서 다루었던 '감독 학습' 에서 논리식을 랜덤으로 생성해 평가하고, 최적해를 구하는

방식이 '랜덤 탐색' 의 예라고 할 수 있겠습니다.

'랜덤 탐색' 은 획득해야 하는 지식의 탐색 범위가 방대하고, 최적의 지식의 존재하는

위치가 불분명할 때 효과적입니다.

이와 반대로 탐색 범위가 비교적 명확하고 탐색 방향을 어느정도 알고 있다면,

'랜덤 탐색' 보다는 '계통적 탐색' 을 하는 편이 유리합니다. 

여기서 '계통적 탐색' 은 탐색 공간을 특정한 순서에 따라 빠짐 없이 조사하는 것을 말합니다.

'계통적 탐색' 의 예로는 기본적으로 '횡형탐색', '종형탐색'이 있습니다.

좋아 보이는 부분을 우선 탐색하는 '최량 우선 탐색'

이미 조사한 결과 중 더 좋은 부분을 최우선으로 남겨 조사하는 '최적 경로 탐색'

양쪽을 융합한 A 알고리즘과 A* 알고리즘 등이 있습니다.

'랜덤 탐색' 과 '계통적 탐색' 은 각각 장,단점이 존재합니다.

'랜덤 탐색' 은 적용 범위가 넓지만 지식 획득 효율이 높지 않습니다.

'계통적 탐색' 은 적용 범위가 제한적이며, 자칫하면 '전수 조사' 의 가능성이 있습니다.

그리하여, 두 가지 방법을 적절히 섞은 방법들이 나옵니다. 

'랜덤 탐색' 에 일정한 방향성을 부여하는 '모의 담금질' 방법이 있습니다.

현재 지점에서 랜덤한 지점의 평가치를 계산하여 평가치가 높으면, 그 곳으로 이동합니다.

여기까진 '랜덤 탐색' 과 동일합니다.

여기에는 온도 T 가 등장합니다. T 값이 크면 평가치가 낮아도 이동할 확률이 높아지고, 

반대로 T 값이 낮으면 평가치가 높지 않을 시 이동하지 않게 됩니다.

(한마디로 점점 얄짤 없어진다는 말입니다.)

그 외에 여러 탐새점을 동시에 병행 조사하는 방법도 있습니다.

탐색 공간 안을 운동하는 복수 입자를 가정하고 입자끼리 통신을 하며 탐색하는 

'입자군 최적화(Particle Swarm Optimization)' 이 있습니다.

개미 떼가 하는 행동을 모의하여 탐색을 진행하는 '개미 군집 최적화' 같은 

무리 지능을 응용한 다양한 탐색 방법이 제안됩니다.