유전자 알고리즘 진행 단계

■ 유전자 알고리즘 진행 단계

 유전자 알고리즘을 수행하기 위해서는 해당 문제를 유전형으로 표현할 수 있어야 합니다. 대표적인 예로 0,1로 나타내는 이진수가 있고 가장 많이 쓰이고 있습니다. 그 이유는 가장 간단하게 표현할 수 있고, 수식을 만들 때도 비교적 수월하기 때문입니다. 그리고 상황에 따라 실수형, 위치기반 표현 등을 씁니다. 

 해당 문제를 유전형으로 표현한 후 다음 단계로 초기 모집단을 결정해야 합니다. 모집단의 크기는 알고리즘을 구성하는 초기에 지정을 해야 합니다. 모집단의 크기가 너무 작을 경우 교차를 통한 진화 가능성이 줄어들어 알고리즘의 적합도가 떨어질 확률이 높아집니다. 그리고 모집단의 크기가 너무 큰 경우 알고리즘을 수행하는데 필요한 시간이 너무 많이 소요된다는 단점이 있습니다. 

 그리고 다음으로 개체 적합도를 계산해야 합니다. 초기 모집단부터 목표 값을  찾기 위해 각 개체의 적합도를  평가하기 위한 함수를 설정해야 합니다. 이 과정이 매우 중요합니다. 기준이 되는 적합도를 무엇으로 할건지 결정하고, 그에 맞는 수식을 설정해야 합니다. 여기서 적합도가 부적절하다면 전체 알고리즘의 적합도가 떨어질 가능성이 매우 큽니다. 적합도 함수를 설정하는 것이 유전 알고리즘에서 가장 중요한 부분이라고 생각합니다. 적합도 함수를 설정하는 과정에서 문제가 생기면 최적값을 찾는 것이 의미가 없어집니다. 유전 알고리즘 방법론을 선택하기 전에 적절한 적합도 함수를 설정할 수 있는지를 먼저 생각해보는 것이 필요합니다.

 선택 수행(Perform Selection) 단계입니다. 선택은 전체 유전자 중에 어떤 유전자를 선택할지를 결정하는 단계 입니다. 아래 사진은 룰렛 선택입니다. 적합도 비례 방법이라고 하는데 각 유전자의 적합도에 따라 선택될 확률을 K배로조정하는 방법입니다. 확률에 기반하였기 때문에 우수한 개체라도 선택되지 않을 가능성이 있고, 열등한 개체라도 선택될 확률이 있어서 한쪽으로 치우지지 않는 개체를 선정할 수 있다는 장점이 있습니다. 많은 연구들이 룰렛 휠 방식을 채택해서 진행되었습니다.

 순위 기반 선택입니다. 순위 기반 선택은 룰렛 선택 방법을 보완하는 방법으로 룰렛 방식이 우수한 개체가 선택 받을 확률이 높은데, 이때 특정 우수한 개체만 선택 받을 확률이 높아집니다. 이를 보안하기 위해서 적합도에 따라 순위를 매기고, 그 순위에 따라 각 개체가 선택받을 확률을 결정합니다.

 기대값 선택 방법은 적합도에 대한 각 개체의 기대값을 정하는 것입니다. 기대값에 따라 확률적인 재생 개수를 구해서 선택하여한번 선택된 개체 수는 기대값을 한번 더 곱해줘서 다시 뽑힐 확률을 최소화 합니다. 

 다음으로 토너먼트 선택 방식은 개체군 중 임의의 개체들을 선택해서 비교한 다음 적합도가 더 높은 개체를 다음 세대에 남기는 선택 방법으로 최근에는 토너먼트 선택방식을 많이 쓰이고 있습니다. 개체들의 확률 값을 직접 비교하기 때문에 아무래도 결과에 우월성이 더 높다고 볼 수 있습니다.

 엘리트 보존 방법은 확률에 따라 개체를 선택하게 될 때, 우수한 개체가 소실되는 것을 막기 위해서 가장 좋은 해를 보존하여 다음 세대로 넘기는 선택방법입니다.

 유전 알고리즘을 이해하는데 기본적인 용어를 제대로 숙지하는 것이 매우 중요합니다. 유전자는 0,1과 같은 유전자 하나하나를 말합니다. 그리고 개체는 유전자 0,1 모인 집단을 말합니다. 여기서 집단에 포함되는 유전자 개수는 처음에 알고리즘을 설정할 때 결정해야 합니다. 여러 연구에서 룰렛 휠 방법을 많이 사용했지만, 최근에는 토너먼트 방식이 가장 많이 쓰고 있다고 합니다. 그 이유는 선택단계에서 적합도가 높은 개체를 뽑아서 알고리즘을 수행하는데 효율적이라고  합니다.  그리고 유전자 알고리즘을 쓰는데 있어서 해당 도메인에 대한 이해가 매우매우 중요합니다. 해당 도메인이 유전자 알고리즘을 적용할 수 있는 것인지, 다른 방법들이 더 적합하지 않는지에 대한 고민이 필요합니다.