[유전자 알고리즘]

우리 인류는 적자생존의 원칙을 기반하여 진화해왔습니다.

교차, 돌연변이, 도태 등의 과정을 거쳐 우성 유전자만이 살아남았죠.

 

 

 

 

 

 

 

 

 

이러한 생물학적 개념으로부터 영감을 얻은 알고리즘을 유전자 알고리즘(Genetic Algorithm)이라고 합니다.

 

 

 

 

 

 

 

 

 

 

 

유전자 알고리즘은 위와 같은 과정으로 흘러갑니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

선택 과정에서는 부모 염색체가 될 2개의 염색체를 선택해야합니다.

이때, 많이 사용되는 알고리즘은 룰렛 휠 선택입니다.

룰렛 휠 선택을 사용하는 이유는 적합도 높은 염색체를 뽑되, 그렇지 않는 염색체도 선별되도록 하기 위함입니다.

이 말은 즉슨, 적합도가 낮은 염색체도 최적 솔루션에 해당될 수 있다는 것을 의미하죠.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

교차 과정에서는 앞의 단계에서 선택된 염색체를 교차점 기준으로 crossover시켜 자식 염색체를 만들어냅니다.

 

 

 

 

 

 

 

 

 

유전자 알고리즘(GA)는 선택과 교차만으로 지역  최대점에서 더 이상 발전하기 어려운데 이를 극복하기 위해서

돌연변이 연산이 필요합니다.(전역 최적값을 찾는 것이 목표임)

 

 

 

 

 

 

 

 

 

 

의사코드로 표현하자면 위와 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

특히 GA는 외판원 순환문제(TSP)에서 활용됩니다. 최적의 솔루션은 필요하지는 않고 근사해도 충분하면서 최적해를 구하고자 하면 시간이 너무 오래 걸리는 문제에 종종 사용됩니다.