Matlab을 이용한 유전 알고리즘(Genetic Algorithm) 예제

 

지난 포스트에서는 유전 알고리즘이 어떤 의미를 가지며, 어떤 연산으로 이루어지는지에 대해 알아보았다.

 

이번 포스트에서는 지난 번에 다루었던 내용을 바탕으로 간단한 형태의 유전 알고리즘을 구현하고, 그 연산 과정이 어떻게 이루어지는지 알아보도록 하겠다.

 

경험적으로 장황한 이론적인 설명 보다는 복잡하지 않은 예제에 대해 이야기 하는 것이 더 이해가 빠른 경우가 많았다. 따라서 지난번에 유전 알고리즘에 대한 개념에 대해 간단히 언급을 했다라면, 이번 경우에는 실제 문제를 통해 유전 알고리즘의 구성 요소와 연산이 실제 어떻게 이루어지는지에 대해 알아보는 것이 좋을 것 같다.

 

문제 정의 : 모든 개체가 특정 값의 20자리 바이너리 스트링을 가지도록 진화 수렴 시킴

 

바이너리 스트링 유전자의 예

 

 

초기화 : 100개의 개체가 랜덤한 값을 가지는 20자리 바이너리 스트링으로 초기화

 

적합도 함수 Fitness Function : 20자리의 값이 원하는 값과 얼마나 매칭되느냐에 따라 점수를 매긴다.

예를 들어, 20 자리 중 7자리가 원하는 값과 일치하면 7이라는 값을 매긴다. 따라서 적합도 함수 출력은 최소 0에서 최대 20까지의 값을 가진다.

 

하기의 적합도 함수 코드는 유전자 스트링의 앞 10자리는 0, 그리고 뒤의 10자리는 1인 경우에 가장 적합도가 높다고 판단한다.

 

function [ y ] = ga_fitness( X , size)

 

check = 0;

for i = 1:size
    if i >= 1 && i <= size/2
        if X(1,i) == 0
            check = check + 1;
        end
    elseif i >= (size/2+1) && i <= size
        if X(1,i) == 1
            check = check + 1;
        end
    end
end

y = check;

 

end

 

이제 연산의 종류를 선택할 차례이다. 선택, 교차, 변이, 대치 연산에 대해 어떻게 수행할지를 결정해야 한다.

 

 

선택 연산

 

먼저 선택 연산은 룰렛휠 선택 방식을 사용할 것이다. 룰렛휠 선택은 원형 회전판을 몇 개의 구역으로 나누고, 이 회전판이 돌아가고 있는 상태에서 다트를 던져 맟주는 방식을 생각하면 된다. 다트가 회전 판에 어느 구역에 꽂힐지는 랜덤하지만 확률로 보면 넓은 구역에 꽂히게 될 가능성이 높다. 룰렛휠 선택 연산은 모든 개체의 적합도 함수 값을 구해서 이를 더하고, 각각의 개체가 차지하는 영역의 비율을 산출하여 룰렛 판의 영역을 결정한다. 개체의 적합도가 높아 좋은 품질이라고 생각되는 개체는 많은 영역을 차지하게 되고, 적합도가 낮아 나쁜 품질이라고 생각되는 개체는 작은 영역을 차지하게 된다. 따라서 좋은 품질의 개체가 부모로 선택될 확률이 커지게 된다.

 

룰렛휠 선택 연산의 공식은 다음과 같다.

 

 

 

여기서 Cw는 해집단 내에서 가장 나쁜 품질의 개체가 가지는 비용, Cb는 해집단 내에서 가장 좋은 품질의 개체가 가지는 비용, Ci는 i번째 개체가 가지는 비용으로 좋은 품질의 개체일 수록 f 값은 커지게 된다. Cw, Cb, Ci는 각각 비용을 뜻하는 변수로 그 값이 작을수록 좋다. k는 튜닝 변수로 일반적으로 3 혹은 4의 값을 사용한다.

 

 

 

이 예제에서는 해집단이 100개의 개체로 이루어져 있으므로 f(1) ~ f(100)의 값을 모두 더하여 룰렛휠을 만든다. 0 ~ (모든 f의 합) 사이의 임의의 랜덤 값을 구해 그 값의 위치에 해당하는 개체를 선택하게 된다. 적합도가 높은 개체가 선택되는 것은 자연계에서 환경에 적응을 잘하는 개체가 더 잘 살아남는 현상을 모델링하는 것이다.

 

 

교차 연산

 

교차 연산은 2점 교차 방식을 사용하였다. 2점 교차 방식은 유전자 스트링의 임의의 2점을 선택하여 한 쪽 부모에게서는 바깥 쪽 유전자를, 다른 한 쪽 부모에게서는 안 쪽 유전자를 물려 받게 하는 방식이다. 선택되는 2점은 랜덤이므로 어느 부모에게서 더 많은 유전자를 물려받게 될지는 예측하기 어렵다.

 

 

 

 

변이 연산

 

사람에게서도 부모가 가지고 있지 않는 어떤 재능이나 특징이 굉장히 드물게 나타나는 경우가 있다. 훌륭한 부모 밑에서 상당히 좋지 않은 자식이 태어날 수도 있고, 그 반대의 경우도 생각할 수 있다. 이것은 유전자의 품질 향상이 한 방량으로만 흐르는 것을 탈피하여 일정 변화를 주어 좀 더 환경에서 더 잘 살아남게 하는 기회로 작용하게 한다. 이러한 과정을 모델링하는 변이 연산은 부모에게서 교차 연산을 통해 물려 받은 유전자에 작은 확률로 변화를 주는 것을 말한다. 유전자 스트링을 하나하나 탐색하면서 랜덤하게 변이를 가한다. 여기서는 바이너리 유전자를 가지므로 물려 받은 n번째 유전자가 0이라면 1로 변이를 가하게 된다.

 

 

대치 연산

 

대치 연산은 해집단을 자식 개체로 교체하는 것으로 사람으로 말하자면 사회의 주요 구성원이 다음 세대로 바뀌는 것이라고 보면 된다. 이 때 해집단 내의 모든 개체를 자식 개체로 교체할 수도 있고, 실제 생명체의 조직과는 다르지만 적합도가 부모에 비해 우수하다고 판단된 자식의 경우로만 교체할 수도 있다. 여기서는 모든 개체를 교체하는 것으로 한다.

 

 

Matlab 시뮬레이션

 

앞에서 설명한 유전자 구조와 해집단, 적합도 함수를 바탕으로 각각의 연산이 수행될 수 있도록 Matlab 코드로 구현하였다. 시나리오는 다음과 같다.

 

1. 20개의 길이를 가지는 유전자 바이너리 스트링을 랜덤하게 초기화하며, 개체는 100개를 생성한다.

2. 선택 연산 : 룰렛휠 선택 연산을 사용하며 k값은 3으로 설정한다. 부모 개체 선택을 위해 2번 연산을 수행한다.

3. 교차 연산 : 2점 교차 방식을 사용하며, 첫 번째 점은 1~19 사이의 값을, 두 번째 점은 첫 번째 점과 20 사이의 값을 선택하여 유전자 교차를 수행한다.

4. 변이 연산 : 교차 연산으로 생성된 자식 개체의 유전자 스트링을 하나하나 체크하여 랜덤 변수가 변이율 0.001 보다 작을 경우 비트를 반전시킨다.

5. 대치 연산 : 모든 개체를 자식 개체로 교체한다.

6. 2~5의 과정을 1000 세대 동안 수행하며, 만약 모든 개체의 적합도가 최대치인 20을 만족할 경우 진화를 종료한다.

 

아래는 진화를 수행한 그래프이다.

 

 

코드를 실행시키면 세대가 진행되면서 각 세대에서 최대의 적합도를 가지는 개체가 얼마의 적합도 값을 가지는지와 그 세대의 해집단이 가지는 평균 적합도가 얼마인지를 표시하게 된다. 진화는 153 세대에서 완료되었다. 세대가 진행 될 수록 전반적으로 적합도가 상승하는 것으로 나타나며, 최대 적합도는 어느 순간 상승하다가도 다시 하락하는 양상을 볼 수가 있다.

 

초중반에는 비교적 빠른 진화를 나타내며, 후반부로 갈수록 수렵 속도가 줄어드는 것을 볼 수 있다. 이것은 해집단이 전체적으로 좋은 품질의 유전자를 가지고 있어서 선택에 있어서 거의 균등한 확률로 부모 세대의 개체를 선택하고, 부족한 개체를 찾아 보완시키는데 시간이 걸리기 때문이며 간혹 변이에 의해서 양질의 유전자가 오히려 낮은 품질로 바뀌는 경우가 발생하기도 하기 때문이다.

 

변이의 확률을 좀 더 높여주면 어떻게 될까? 아래는 변이 확률을 0.001에서 0.01로 올려 진화를 수행한 경우이다.

 

 

초기 수렴 속도는 0.001일 경우보다 다소 빠르지만 변이가 자주 일어나기 때문에 양질의 유전자도 다수 변이가 되기 때문에 결국에는 수렴이 되지 않는다. 이를 통해 적당한 변이율을 선택하는 것이 중요하다는 것을 알 수가 있다.

 

이 밖에도 주어진 문제에 따라 적당한 수의 해집단, 적당한 형태의 유전자 표현 형태 등을 고려해야 한다. 해집단의 수가 너무 작으면 다양성을 확보하기 어렵고, 너무 많도 수렴성에 문제가 되며 연산량 또한 많아진다. 우리가 풀고자 하는 문제의 유형에 따라 찾는 값이 실수형 값인지 단계의 구분을 원하는지에 따라서 유전자 구성이 달라져야 한다.

 

 

더 생각해봐야 할 것들

 

간단한 형태의 유전 알고리즘을 Matlab 코드로 구현해 보았다. 이 예제에서 구현된 코드는 하기에 첨부하도록 하겠다.

 

유전 알고리즘에서 각 단계의 연산에는 여러 방법들이 있으며 각각의 장단점이 있을 것이다. 유전 알고리즘을 자유자재로 사용할 수 있으려면 그런 다양한 방법을 알고 있어야 할 것이다. 또한 경험적으로 유전자 표현형을 어떻게 설정하여 염색체를 구성한 것인가도 중요하다. 다음 글에서는 이러한 것들을 알아보도록 하겠다.

 

또한 이해를 위한 예제를 넘어서 실제 문제에의 응용을 통해 유전 알고리즘의 가능성과 한계에 대해서도 알아보도록 한다.

 

 

ga.m

 

ga_fitness.m

 

 

 

 

(이 글이 마음에 드신다면 아래 버튼을 눌러 주세요~~^^)