Genetic Algorithm(GA) 유전 알고리즘의 이해

이 포스팅을 보는 사람들 중에 '유전 알고리즘'에 대해 처음 들어보는 사람들은 없을 것이라고 생각한다.

보통 나무위키라도 보고 시작할 듯싶다.

여러 글들을 살펴보면 유전 알고리즘은 최적의 해를 찾는 메타 휴리스틱 알고리즘이라고 나와있다.

그래서 외판원 문제 등 복잡한 문제를 해결하기에 적합하다고.

 

유전 알고리즘은 내 첫 학술 논문에서 사용한 알고리즘이다.

클래식한 최적화 알고리즘으로 아직까지 쓰이고 있다고 하지만 조금은 구닥다리다.

학술지에 게재를 하고 난 뒤에도 왜 유전 알고리즘을 선택했냐는 피드백도 받았다.

첫 논문이었으니 제일 기본적인 알고리즘으로 골랐지만

사실, 문제 자체를 해결하기엔 다른 알고리즘도 함께 적용하는 것이 적절할 듯싶다.

 

유전 알고리즘에 대한 포스팅은 시리즈로 구성해보려고 한다.

개념부터 활용 방법까지 다루어 볼 예정이다.

자, 시작해 보자.

---

1. 유전 알고리즘의 정의

유전 알고리즘은 생물의 적자생존 법칙을 모방한 최적화 기법이다.

매트랩에서는 유전 알고리즘을 이렇게 정의한다.

유전 알고리즘은 생물학적 진화를 유도하는 과정인 자연 선택에 기반한 것으로
제약 조건이 있는 최적화 문제와 제약 조건이 없는 최적화 문제를 모두 풀 수 있는 방법이다.

2. 유전 알고리즘의 순서도

유전 알고리즘의 순서도를 살펴보면 아래와 같다.

구글에서 '유전 알고리즘'을 검색하면 나오는 이미지 자료다.

위 그림에 따라 용어를 정리해 보자면,

Population을 해집단이라고 많이들 정의하지만 나는 일단 '인구'라고 표현하고 싶다.

그리고 Chromosome은 염색체 혹은 사람, Gene은 유전자라고 생각하면 된다.

 

염색체는 유전인자로 구성되어 있으며

여러 염색체, 즉 사람들이 모이면 인구가 된다.

3. 유전 알고리즘의 원리

유전 알고리즘을 구현하기 위해서는

문제 해결 목적에 따라 초기값 생성과 적합도 함수만 정해주면 된다.

 

그래도 원리는 알아야하니 다음 순서도를 살펴보자.

구글에서 '유전 알고리즘'을 검색하면 나오는 이미지 자료다.

먼저, 'Population Initialization' 단계에서 초기값을 생성한다.

초기값에서 염색체를 구성하는 유전자의 값을 만들어준다.

그렇게 생성된 염색체의 집합은 보라색 Population이 된다.

 

다음으로, 목적에 맞게 구현한 Fitness Fuction(적합도 함수)를 거치며

문제 목적에 맞는 유전자가 걸러지게 되고 세대교체(Crossover)가 이루어진다.

적합도 함수는 유전 알고리즘의 성능을 결정하기 때문에 가장 주의 깊게 살펴야 하는 부분이다.

적합도 함수 설정은 다음 포스팅을 보며 더 구체화해 보도록 하자.

 

아무튼 적합도 함수를 거치며 우수한 유전자를 고르게 되고

우수한 유전자를 대상으로 변이(Mutation)가 일어난다.

 

다만 이 변이 과정에서 항상 우수한 유전자를 선택하지는 않는다.

무작위성(Randomness)을 반영하여 성능 개선에 도움을 준다.

Randomness가 성능 개선에 효과가 있는 이유?
깜짝선물이다! 나도 몰랐던 내 취향의 발견을 도와준다고 생각하자.

유전 알고리즘은 위 과정을 조건에 맞춰 반복하며 실행된다.

내가 이해한 유전 알고리즘

다음 포스팅에서는 간단하게 유전 알고리즘을 구현해 보도록 하겠다.