Genetic Algorithm (GA) 이란 생물학 진화 이론에서 비롯된 자연선택(natural selection) 메카니즘에서 영감을 받아 최적화 문제를 해결하는 metaheuristic 알고리즘입니다. 생물학 이론에서는 유전적 진화를 통해 유전자는 더 좋은 방법으로, 문제 해결을 위해 좋은 자식을 낳는 경향이 있습니다. 즉, 솔루션에 훨씬 더 빠르게 도달하기 위해 가장 적합한(Fittest) 생존자 유전자를 사용합니다.
이렇게, 생물학 진화 이론을 통해, 돌연변이(muation), 유전자교차(crossover), 그리고 후손 선택(selection) 등의 개념을 사용하여 솔루션을 생성합니다.
GA가 사용된 어플리케이션의 예로는 스도쿠 퍼즐 게임, hyperparameter 최적화 등이 있습니다.
GA는 크게 5단계로 구성되어 있습니다.
- 모집단 초기화
- Fitness function 정의
- 모집단에서 fittest 멤버 선택
- crossover, mutation
- 솔루션을 찾을때까지 3-4단계 반복
1. 모집단 및 파라미터 초기화
모집단 초기화 단계에서는 모집단(population) 크기를 선택합니다. 그리고, 각 population별로 유전자(chromosome)를 랜덤으로 선택하여 서로 다른 DNA를 각각 제공합니다.
2. Fitness Function 정의
Fitness function은 문제를 해결하기 위한 유전자의 "좋음" 의 척도를 구하는 함수입니다. Fitness function을 통해 얻는 값을 Fitness value(positive value)라고 합니다. Fitness function은 다양하게 정의될 수 있습니다.
3. 모집단에서 fittest 멤버 선택
부모가 될 인구 중 가장 적합한(fittest) 구성원을 선택하는 단계입니다. 위에서 정의된 Fitness function으로부터 계산된 값을 바탕으로, 값이 큰 멤버들을 선택합니다.
4. crossover, mutation
crossover과 mutation을 사용하여 개선된 다음세대를 생성합니다. 다음 세대는 희망적으로 개선이 될 수도 있고, 안될 수도 있습니다.
3단계에서 선택된 fittest 멤버들의 유전자를 가져와, crossover, mutation처리를 해줍니다.
4.1. crossover
crossover는 말그대로 교차입니다. 만약 선택된 fittest 멤버가 2명이라면, 2명의 유전자를 교차시켜줍니다. crossover methods는 여러 방식이 있습니다.
4.2. mutation
만약 mutation처리를 해주지 않는다면, 우리는 local minima 문제에 빠질 가능성이 큽니다. mutation처리는 우리가 새로운 것을 발견하게 도와줍니다.
하지만 mutation 비율이 너무 크다면, 우리는 너무나 방대하게 explore할 것이며, 미래 세대는 parent의 정보를 많이 담고 있지 않을 것입니다. 반대로 mutation 비율이 너무 작다면, 미래 세대는 parent의 정보를 너무 많이 담고 있어, local minima 근처에 있다면 그곳에서 벗어나기란 너무 힘들 것입니다.
때문에 mutation 비율은 trade-off 문제를 가지고 있으므로, 적절한 값을 선택해주는 것이 매우 중요합니다.
만약 mutation rate가 0.1이라면, 10퍼센트의 확률로 DNA가 랜덤으로 변형됩니다.
5. 솔루션을 찾을때까지 3-4단계를 반복해줍니다.
