[1-3] Dimension Reduction : GA

유전 알고리즘을 이용한 변수 선택 방법

Genetic Algorithm

유전 알고리즘은 변수 선택 기법 중 가장 우수한 방법입니다. 이전까지의 변수 선택 기법들은 탐색 소요 시간을 줄이기 위한 방법들을 제안해오면서, 효율적인 탐색은 가능하게 하였습니다. 하지만, 탐색 범위가 적기 때문에, 전역 최저점을 찾을 확률이 적다는 문제가 있습니다. 이번 장에서 소개해드릴 유전 알고리즘은 메타 휴리스틱 방법론 중 하나입니다. 메타 휴리스틱 방법론은 시행착오(Trials and Errors)를 통해 효율적으로 해서 문제를 푸는 방법입니다. 이러한 메타 휴리스틱 방법론은 자연현상을 모사한 방법이 많은데, 유전 알고리즘은 진화설 중 다윈의 "자연선택설" 에 기반한 방법론 입니다. 자연 선택설이란, 초기에 다양한 유전자를 가지고 있던 종이, 생존에 유리한 유전자를 택하면서, 현재 상태가 된 진화설로 기린의 목 길이, 시베리아 곰의 색, 북극 곰의 색 등의 예를 들 수 있습니다. AlphaStar (Kai et al,, 2019) 논문에 따르면, 다윈의 자연선택설이 라마르크의 용불용설보다 더 받아들여지고 있습니다.

자연 현상을 모사한 메타 휴리스틱 기법에는 인공 신경망, 개미 군집 알고리즘, Particle Swarm Optimization 등의 방법론이 존재합니다.

유전 알고리즘의 단계는 다음과 같습니다.

Step 1. Initiation

유전 알고리즘의 첫 단계는 $d$ 차원의 변수 속성 벡터를 이진수로 초기화 하는 것입니다. 즉, $x_0 =0$ 이면, 0번째 변수를 사용하지 않는 것이고, $x_0 =1$ 이면 0번째 변수를 사용하는 것입니다. 염색체(Chromosome)의 갯수는 하이퍼파라미터입니다. 설정한 염색체의 수만큼 랜덤하게 염색체 인코딩을 구성합니다. 랜덤하기 때문에 초기 성능은 낮을 수 있습습니다.

유전 알고리즘은 변수 선택 뿐만 아니라 최적화 문제에서도 다양하게 사용되기 때문에 Encoding Scheme 이 달라질 수 있습니다. 변수 선택에서는 Binary 로 인코딩합니다.

유전자 알고리즘의 하이퍼파라미터는 염색체의 수, Fitness Function (염색체의 성능 평가 방법), Crossover Mechanism (교배방식), The rate of mutation (돌연변이률), Stopping Criteria (종료조건) 이 있습니다.

Step 3. Fitness Evaluation

Step 2 에서 총 8개의 Chromosome 에 해당 모델들을 실행하고, Fitness Evaluation 에서는 총 8개의 모델을 평가합니다. 유전자 알고리즘의 Fitness Function 은 높은 값이 좋은 Chromosome 을 나타내므로 $RMSE$ 와 같은 오차의 경우 $1-RMSE$ 를 Fitness Function 으로 사용합니다. 만약 두 모델의 성능이 같은 경우, 더 적은 변수를 사용한 모델을 선택합니다.

Step 4. Selection

Step 3 에서 Fitness Function 을 통해 부모 염색체의 우수성을 평가했다면, Step 4 에서는 우수한 부모 염색체를 선택하여 자손에게 물려줍니다. 이는 부모 염색체가 우월하면, 자손들도 우월하다는 가정을 가지고 있습니다. 부모 염색체를 선택하는 방법은 두가지 입니다.

Deterministic Selection

Fitness Evaluation 에서 산출된 RANK 기준으로 상위 N% 의 염색체를 선택합니다. 상위 N% 에 포함되지 못한 염색체는 자손에게 물려줄 기회가 아예 사라지는 것입니다. 하지만, 4등과 5등의 차이가 얼마 나지 않을 경우, 이는 5등 입장에서 억울할 수 있습니다. 이를 보완한 방법이 Probabilistic Selection 입니다.

Probabilistic Selection

Probabilistic Selection 은 Step3에서 산출된 Weight 를 사용해서 모든 염색체에게 자손에게 전달해 줄 수 있는 기회를 줍니다. 하지만 당연히 적은 가중치를 가진 염색체는 더 적은 확률로 선택되게 됩니다.

Step 5. Crossover & Mutation

Crossover

Crossover 는 Step4 에서 선택된 부모 염색체로부터 자식을 재생산해는 과정입니다. Cross over point 를 만들어 부모의 염색체를 해당 구간 만큼 뒤집습니다.

Mutation

랜덤한 수를 할당한 다음 0.01 이하에 해당하는 변수를 뒤짚는 방법입니다. 0.01 은 돌연변이률로 하이퍼파라미터입니다. 최적화 알고리즘에서는 Exploitation 과 Exploration 의 균형을 갖는 것이 중요합니다. Crossover 는 Exploitation 에 해당하며, Mutation 은 Exploration 에 해당합니다. 즉 돌연변이률은 현재 탐색하고 있는 공간 밖의 전역 최저점을 재탐색할 수 있는 기회를 제공합니다. 하지만 너무 큰 값을 주면, 어느 곳에도 수렴되지 않을 수 있습니다. 반면에 작은 값으로 설정할 경우, 지역 최저점을 찾아 일찍 수렴되 알고리즘이 종료될 수 있습니다.