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

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

이제 본격적은 '진화연산' 에 대해 알아보도록 하겠습니다.

앞에서도 언급했지만 '진화연산' 은 생물이 환경과 상호작용하면서, 필요한 형질을 획득하는 

진화과정의 모의하여 검색과 최적화 혹은 지식 획득 같은 처리하는 것을 말합니다.

여기서는 가장 대표적인 '유전 알고리즘' 에 대해서 설명하고 있습니다.

'유전 알고리즘' 의 개념을 이해하려면, 몇가지 키워드에 대해 짚고 넘어가야 합니다.

유전자, 유전자좌, 유전자 풀, 적응도 함수 등이 있겠습니다.

'유전자' 는 우리가 추구하는 최적해의 성질 또는 규격이라고 표현 하겠습니다.

'유전자' 는 어떤 값들의 나열된 형태로 표현됩니다. 

'유전자 좌'란 그 때 '유전자' 를 구성하는 각각의 값에 해당합니다. 

'유전자 풀'은 여러 종류의 '유전자' 들이 모인 집합을 의미합니다.

'적응도 함수' 란 유전자 정보를 처리하여 우리가 추구하는 해와 얼마나

근사한지, 최적화된 지식인지를 수치로 표현해주는 함수입니다.

이제 '유전 알고리즘' 의 진행 과정에 대해서 알아봅시다.

1. 유전자 풀의 규모만큼 최초 1세대의 유전자를 임의로 생성해냅니다.

2. 모든 유전자에 대해서 적응도 함수를 통해 적응도를 산출합니다.

3. 다음 세대의 유전자를 생산합니다.

3-1. 1세대의 유전자 풀에서 부,모 유전자 각각 1개씩 선출합니다.

이 때, 적응도가 높을 수록 선출될 확률이 높도록 구성합니다.

선출법에는 룰렛 선택, 랭크 선택, 토너먼트 선택 등이 있습니다.

3-2. 부, 모의 유전자를 유전자 조작 과정을 통해 부,모의 형질을 이어받은 

자식 유전자를 생성합니다. 이 과정을 '교차' 라고 합니다.

'교차' 에는 일점교차, 균등 교차 등이 있습니다.

3-3. '교차' 만으로는 전혀 다른 유전자의 출현을 기대하기 어렵습니다.

'돌연변이' 라는 특정 확률로 유전자 정보를 랜덤하게 바꾸는 조작을 취합니다.

4. 유전자 풀의 유전자 평균 적응도, 혹은 가장 우수한 적응도 값이 임계치에 도달하거나

미리 정해둔, 세대 수를 모두 지나올 때 까지 과정을 반복합니다.

'교차' 과정의 두가지 '일점 교차' 와 '균등 교차' 에 대해 자세히 알아봅시다.

'일점 교차' 란 선출된 두 유전자를 한 지점을 기준으로 한쪽은 앞에 값만, 

다른 한쪽은 뒤에 값만, 채택하여 둘을 이은 형태로 새로운 유전자를 만드는 방법입니다.

위의 방법과 동일하지만 지점을 두개 선출하면 '이점 교차' 가 됩니다.

'균등 교차' 는 각 유전자좌의 채택을 확률적으로 선택하는 방법이 됩니다.