[ML] GA(Genetic Algorithm)

이번 포스팅에서는 생물체가 환경에 적응하면서 진화해나가는 모습을 모방하여 최적의 해를 구하는 방법론인 GA라고 불리는 유전 알고리즘에 대해서 알아보려고 한다. GA의 이름에 알고리즘이라는 용어가 붙어 우리가 그동안 배웠던 머신러닝의 지도학습 또는 비지도학습의 종류 중 하나라고 오해할 수 있다. 하지만 GA는 모델의 종류가 아닌 파라미터의 최적화 문제를 풀기 위한 일종의 방법이다. 파라미터의 최적화 문제를 풀기 위한 다른 방법으로는 이전 포스팅에서 배웠던 EM(Expectation Maximization)알고리즘을 예로 들 수 있다.

 

 

유전자를 어떻게 알고리즘으로 변환시킬 수 있을까?

 

GA를 이해하기 위해서는 사전에 정의하고 넘어가야 할 몇 가지 개념들이 존재한다. 하나씩 정의해보자.

 

• 염색체(Chromosome) : 여러개의 유전자를 담고 있는 하나의 집합을 의미한다. GA에서는 하나의 해(파라미터)를 표현한다. 

• 유전자(Gene) : 염색체를 구성하고 있는 요소로서, 하나의 유전 정보를 나타낸다. 예를 들어, 하나의 특정한 염색체가 [A,B,C,D] 라고 정의된다면 해당 염색체의 유전자는 A,B,C,D로 4개의 유전자가 존재한다.

• 자손(Offspring) : 특정 시간(t)에 존재했던 염색체들(예를 들어, A,B 두 개의 염색체가 있다고 가정.)로부터 생성된 새로운 염색체들(C,D라고 가정.)이다. 즉 C,D 는 A,B 염색체들의 자손이라고 할 수 있다. 자손 염색체는 부모 염색체의 비슷한 유전 정보를 갖는다.

• 정확도(Fitness) : 특정한 염색체가 갖고 있는 고윳값으로서, 특정한 염색체가 표현하는 해(파라미터)가 해결하려는 문제에 대해 얼마나 적합한지를 나타낸다.

유전 알고리즘의 구성요소

 

이제 사전적으로 필요한 개념에 대해 정립했으니 GA가 어떤 방식으로 알고리즘이 구현되는지에 대해서 알아보자.

GA는 다음과 같은 순차적인 방식으로 iterative하게 작용하면서 최적의 해를 찾아나가게 된다.

 

1. 초기 염색체의 집합을 생성한다.

2. 초기 염색체들에 대한 적합도를 계산한다.

3. 현재 염색체들로부터 자손염색체들을 생성한다.

4. 생성된 자손들의 적합도를 계산한다.

5. 이제 종료 조건을 만족하는지 판별을 한다.

6. (만약 종료 조건이 거짓인 경우) 3번으로 이동하여 반복한다.

7. (만약 종료 조건이 참인 경우) 알고리즘을 종료한다.

https://medium.com/@appsby12/optimization-with-the-genetic-algorithm-acb50c5709fd

 

이렇게 보니 GA의 알고리즘의 실행 단계가 비교적 단순하다고 볼 수 있다. 하지만 3번 단계인 자손 염색체를 생성하는 과정에서 몇 가지 다양한 기법들이 존재하는데, 다음 항목에서는 이러한 기법들에 대해 알아보자.

 

유전 알고리즘을 문제 해결에 적용하기 위해서는 다음과 같은 5가지 연산에 대해서 알고 있어야 한다.

1. 초기 염색체를 생성하는 연산

최초의 염색체를 생성하기 위해서는 이전의 염색체가 존재하지 않기 때문에 최초의 염색체를 생성하는 연산을 따로 정의해주어야 한다. GA에서 가장 많이 이용되는 방법은 규칙 없이 임의의 값으로 초기 염색체를 생성하는 것이다.

2. 적합도를 계산하는 연산

염색체에 표현된 정보를 토대로 적합도를 계산하는 연산이다. 이 연산은 해결하려는 문제에 따라 달라진다.

3. 적합도를 기준으로 자손 염색체를 선택하는 연산

자손 염색체를 생성할 때 흔히 적합도가 가장 높은 염색체들을 선택하는 것이 최고의 방법이라고 생각할 수 있다. 하지만 이러한 방법은 염색체의 다양성을 손상시키기 때문에 Global optimum을 찾기에는 부적합하다. 이러한 문제를 피하기 위해서 GA에서는 룰렛 휠 선택(Roulette Wheel Selection) 방법을 이용한다. 룰렛 휠 선택이란, 우리가 흔히 생각하는 원판을 돌리면서 확률에 기반해 결과가 도출되는 룰렛의 개념과 비슷하다고 생각하면 된다. 밑의 그림은 룰렛 휠 선택에 대한 확률적 수식이며 다음 그림은 수식을 룰렛 그림으로 나타낸 그림이다. 룰렛 그림에서 면적의 총 합은 1(100%)이다. 왜냐하면 각각이 확률값이며 확률의 합은 1이기 때문이다.

 

https://untitledtblog.tistory.com/110

 

룰렛 휠 선택을 그림으로 표현하면 이러한 그림일 것이다.

 

위와 같이 룰렛 휠 선택의 방법을 이용하게 되면 적합도가 높은 염색체가 룰렛에서 더 많은 비율의 면적을 차지할 것이고 이에 따라 높은 적합도의 염색체가 선택될 확률이 높아진다. 또 동시에 염색체의 다양성을 훼손시키지 않을 수 있다.

4. 선택된 염색체들로부터 자손 염색체들을 생성하는 연산 

방금 언급했던 룰렛 휠 선택 방법으로 선정된 두 개의 부모 염색체들로부터 하나의 자손 염색체를 생성한다. 이 때 GA에서는 자손 염색체를 생성하는 연산으로서 주로 Crossover이라는 연산을 사용한다. Crossover 연산에 대해 그림으로 설명하자면 다음과 같다.

 

먼저 두 개의 염색체들로부터 하나의 자손염색체를 생성하는 Crossover 연산이다.

 

https://untitledtblog.tistory.com/110

 

다음은 두 개의 염색체들로부터 두 개의 division point(crossover point)를 임의로 설정하고 두 개의 자손염색체를 생성하는 그림이다.

 

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.htm

 

5. 돌연변이 연산

지금까지 살펴보았던 룰렛 휠 선택을 통해 Crossover 연산만을 사용한다면 Local optimum에 빠지는 문제를 발생시킬 수 있다. 이러한 문제를 피하기 위해서 자손 염색체에 돌연변이 연산을 추가적으로 적용하는 방법이 있다.

보통은 0.1%나 0.05%등의 아주 낮은 확률로 돌연변이가 발생하도록 한다. 돌연변이를 발생시키는 연산은 매우 다양하지만 여기에서는 몇 가지 방법만 살펴보자.

 

https://untitledtblog.tistory.com/110

 

우선 binary값인 0과 1에서 0을 1로, 또는 1을 0으로 바꿔주는 reverse 방법이 있다. 그리고 임의의 두 개의 유전자를 선택해서 서로의 위치를 바꾸는 exchange 방식이 있다.

 

https://www.sciencedirect.com/topics/engineering/mutation-operator

 

다음은 각 유전자에 Gaussian(정규분포) 연산을 적용하는 것이다. 정확히 말해서 Gaussian error function을 사용한다. Gaussian 연산은 값이 작은 값들을 가장 likely하게 만들고 자주 generate하게 만들며 반면에 값이 큰 값들은 거의 generate되지 않도록 해주며 편차를 이용해 계산하게 된다. 이 방법은 다른 돌연변이 연산 방법들보다 알고리즘 종료 조건(기준=criteria)에 converge 하는 데에 더 효율적인 방법이다.

 

#참조 문헌

https://www.geeksforgeeks.org/mutation-algorithms-for-real-valued-parameters-ga/ 

Mutation Algorithms for Real-Valued Parameters (GA) - GeeksforGeeks

https://untitledtblog.tistory.com/110

[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm)