Genetic Algorithm

Genetic algorithm

여러 개의 변수가 사용되는 경우 'Gradient descent'알고리즘을 사용하면 local minimum을 찾을 수 있고, 운이 좋으면 global minimum을 찾게 된다. 운이 좋다는 것은 시작점을 잘 선택했다는 것이다. (그래서 neural network에서 weight initialization이 매우 중요하다.) 

하지만, Gradient descent는 많은 변수가 사용되면 계산 비용이 매우 커질 뿐만 아니라, gradient를 계산하기 위해서 편미분이 가능해야한다. 만약 편미분이 불가능한 상태에서는 optimization은 불가능한가? 답은 아니다. Genetic algorithm은 매우 직관적인 결과를 제공한다.

Genetic algorithm (GA)은 domain-independent인 조합 최적화이다. GA의 문제는 1. 문제를 표현하는 방법과 2. 적합도 함수만 있으면 구현이 가능하고 최적화 문제를 해결할 수 있는 실마리를 제공한다. (사실, 최적화라는 단어를 쓰기는 어렵다고 한다.)

GA는 특정 해를 가지고 있는 chromosome(염색체)를 구성하고, 각 해는 gene(유전자)가 된다. 이 염색체가 다수인 개체군을 population이라고 정의한다. 이를 mutation, selection, reproduction, crossover 등을 통해서 새로운 population을 만들어내고, 최적의 해의 조합을 찾아낸다. Fitness function은 각 염색체를 평가를 하여 앞으로 사용을 할 것인지 아니면 버릴 것인지를 결정해낸다. 따라서, 높은 fitness 염색체는 살아나고 낮은 fitness 염색체는 사라진다. (자연선택설)

Genetic operation

1. Selection, reproduction

- fitness function에서 적합한 값을 보여주면 살아남고, 그렇지 못한 것들은 제거되는 자연 선택설 현상이 모델링 된 것이다.

1) Roulette wheel - 염색체의 적합도에 비례하여 염색체를 선택하는 방법.

2) Rank selection - 1) 방법을 사용하는 경우, 낮은 적합도를 갖는 염색체가 선택되는 확률이 매우 적어진다. 이런 결과는 다양한 유전자를 갖는 '다양성'에 큰 손해를 만듦으로, 낮은 적합도를 갖더라도 이러한 객체를 선택함으로서 '다양성'을 유지해야한다. 우선순위를 매기고, 순위에 따라 확률을 정하는 방법.

3) Tournament - n개의 염색체 선택을 위해서 n개의 tournament를 구성한다. 2개로 이루어진 염색체 그룹중에서 가장 fitness가 큰 염색체를 선택하고 다른 것을 제거한다.

4) Elitism - fitness가 가장 큰 것들을 그대로 살려두는 방법.

2. Cross-over

- 두 개의 부모 염색체가 새로운 염색체를 생성해내는 것을 말한다.

1) Simple Cross-over = One-point Crossover - 1개의 교배점, 교배점은 랜덤하게 선택된다. 특징은 빠른 속도로 부모와 달라진다는 것이다.

2) Two-point Cross-over - 2개의 교배점을 사용해서 인접한 gene 정보를 살려주는 방법이다.

3) Uniform Cross-over

3. Inversion

- 염색체의 부분이 절단되어 반대 위치에 부착되는 방법. 적합도가 높은 개체들을 빠르게 결합하여 현재 집단 전역에 확산시키는 특징이 있다.

4. Mutation

- 임의로 선택된 유전자를 0->1 혹은 1->0으로 바꿔주는 방법이다. 이 과정은 local minimum을 피할 수 있는 역할을 한다. 

위의 알고리즘은 Simple Genetic Algorithm (SGA)를 설명하고 있다. 단계는 다음과 같다.

1. 염색체들을 random하게 만들어 낸다. (initial population)

2. 각 염색체의 적합도를 평가한다.

3. 적합도에 따라서 selection, reproduction 과정을 거친다.

4. 3의 과정의 결과인 염색체에 유전 연산자 (Cross-over, Mutation 등)을 적용한다.

5. 다시 적합도를 평가한다.

6. 3-5를 계속 반복하면서 user가 정한 fitness 정도 혹은 iteration 최대 수에 도달하면 반복을 멈춘다.

필자는 Genetic algorithm을 사용해서 3D printing의 path를 최적화 하는 알고리즘을 개발한 적이 있었다. 3D printing에서 생성되는 path를 최소화하는 것을 문제로 만들고 여기에 genetic algorithm을 적용했을 때, software가 만들어내는 path보다 더 짧은 path를 만들어내는 조합을 찾을 수 있었다. 문제를 정확하게 염색체, 유전자로 나타낼 수 있고 fitness function을 정의할 수 있으면 정말 쉽게 구현할 수 있는 알고리즘이고, 강력한 tool이라고 생각한다.