Previous Contents/Genetic Algorithm

2. GA(Genetic Algorithm)의 간단한 예제

shhyun 2006. 12. 14. 15:33

오늘은 GA 의 간단한 예제에 대해서 올려봅니다.

우선 하나의 가정을 하죠.

다음과 같은 수식이 있고 그것의 범위를 다음과 같이 할당해 줍니다.
우리는 이 수식의 최대값을 알아내려고 하는 것입니다.

y = x^2 - 2*x + 4

x = [ -10 , 10 ]

이렇다고 가정을 해보는 것입니다.
위 문제는 누구라도 간단하게 구할수 있는 문제이지만 그냥 하나의 예로서 들어본 것입니다.

그렇다면 GA 의 흐름에서 이 문제를 어떤 식으로 풀어나가는지 알아보도록 하죠.

우리는 GA 연산에서 쓰일 몇가지 구체적인 변수에 대해 설정을 해 줘야 합니다.
우선 GA 에서 초기화에 몇가지의 개체를 이용할 것인지 설정해 줘야 하고,
몇개의 비트로서 그 개체에 대해 표현을 할지도 결정을 해 줘야 합니다.
어느정도 확률로서 Crossover 와 Mutation 연산을 수행하게 할지도 설정을 해 줘야 합니다.
그리고 몇 세대 정도 계산을 해 나갈지에 대해서도 설정을 해야 하죠

우선 초기 개체의 수를 설정을 합니다. 5개로 가정을 하고,
그리고 하나의 개체는 5개의 비트를 이용한다고 가정해 봅시다.
Crossover 와 Mutation 확률 90% 와 10%로 각각 설정을 한다고 가정 하죠.
그리고 5세대만 진행한다고 가정을 해 봅시다.

------------------------------------------------------------------------------------
먼저 여기서 설명드릴게 하나 있는데
5개의 비트를 이용해서 하나의 개체를 만들었는데,
그 개체를 x 의 범위에 한정 시킨 10진수로 변환을 해야 한다는 문제가 있습니다.
이 문제는 일반적으로 다음과 같은 방법으로 해결합니다.
  (Max - Min ) * (x의 개체를 10진수로 변환한것 / (2^개체의 비트수) - 1 ) + Min
이런방식으로 해결을 합니다.
만약 지금과같이 5개의 비트로서 Max값이 10이고 Min 값이 -10 이고
x 가 11111 이 나왔다고 가정을 하죠. 그럼 이것을 10진수로 바꾸면 31이 됩니다.
  (10 - -10 ) * ( 31 / 2^5 -1 =31 ) - 10
이라고 한다면 20 * ( 1 ) - 10 으로 최대값 10이 나오게 됩니다.
------------------------------------------------------------------------------------

다음과 같이 초기 개체가 생성 되었다고 가정을 해 보죠
1. 10101 ==> 21 ==> 3.5484
2. 11000 ==> 24 ==> 5.4839
3. 00010 ==> 2  ==> -8.7097
4. 00101 ==> 5  ==> -6.7742
5. 10001 ==> 17 ==> 0.96774
  원래개체 ==> 10진수로 변환 ==> -10~10의 범위 한정

그리고 이것에 대해 위에서 설명드린 10진수로의 변환을 거친 후,
평가의 작업을 하게 됩니다.

위의 우리가 가정한 y의 방정식인 x^2 - 2*x + 4 에 대입을 하면
1. 9.4943
2. 23.1054
3. 97.2783
4. 63.4382
5. 3.0010
이 값을 각 개체의 Fitness(적합도) 값으로 갖게 되는 것입니다.

그리고 우리는 이 값을 토대로 선택의 작업을 하게 됩니다.
균등한 선택을 이용한다고 가정하면 각각의 개체들은 2번정도로 거의 동등한 선택을 받게됩니다. 거의 2번이라고 한다는 것은 3번이 선택될수도 있고 1번이 선택될수도 있기 때문입니다.
어디까지나 랜덤한 확률에 의한 선택이기 때문입니다.
우선 편하게 1,2 2,4 4,5 가 Crossover 에 이용되었다고하고 3번이 Mutation 되었다고 합시다.

그렇다면 Crossover 연산이 이루어지게 되는데 이연산은 각각의 개체들을 서로 교배시킨다고 말씀 드렸습니다. 이 연산에도 많은 방식이 있는데 우선 One Point Crossover 를 이용한다고 해보죠. 이것은 다음과 같은 방식의 연산입니다. 자세한 것은 추후 설명 하겠습니다.

현재 1,2 번 개체가 선택 되었고, 만약 Crossover Point 를 4번이라고 잡았다고 합시다.
Crossover Point 라는 것은 그 위치에서부터 뒤에있는 모든 비트에 대해 서로 교배를 하겠다는 것입니다.

그러므로 1,2 번 개체는 10101 과 11000 이었으므로 다음과 같이 계산이 되게 됩니다.
  1 0 1 0 1  
         | | <--- 두 개체의 교환.
  1 1 0 0 0

1번은 10100 2번은 11001  이런식으로 형태가 변하게 되는 것입니다.
그리고 뒤이어 2,4 4,5 번에 대해서도 연산을 수행하게 되면 각각 다음과 같이 됩니다.

2번 11001 4번 00101 --> 변환후 2번 11001 4번 00101
4번 00101 5번 10001 --> 변환후 4번 00101 5번 10001

그렇게 Crossover 연산이 끝난 후에는 각각의 유전자는 다음과 같은 형태를 지니게 됩니다.
1. 10100
2. 11001
3. 00010
4. 00101
5. 10001

이제 Mutation 연산을 수행하게 됩니다. 여기서는 3번에 대해 4번째 비트가 Mutation 되었다고 가정 합니다.

00010 --> 00000 이런식으로 선택된 비트를 반전시켜 버리는 것입니다.

결국 한세대의 연산이 모두 끝난후에 유전자는 다음과 같이 바뀌었습니다.

1. 10100 ==> 2.9032
2. 11001 ==> 6.1290
3. 00000 ==> -10
4. 00101 ==> -6.7742
5. 10001 ==> 0.96774

그리고 이 유전자에 대해 재 평가 작업이 이루어지게 됩니다.

결론적으로
1. 6.6222
2. 29.3066
3. 124
4. 63.4382
5. 3.0010

이런 Fitness 값을 갖게 되고 GA 는 결과적으로 x 값 -10 y 값 124 의 최대값에 도달했습니다.

GA 의 알고리즘은 이와 같은 방식으로 수행이 되는 것입니다.
각각의 연산자들은 매우 많은 종류가 있고
여기서는 가장 기본적인 연산자들에 대해서만 예제를 수행했습니다.
내일은 용어에 대해서 정리를 해보겠습니다.
각 알고리즘의 형태마다 쓰이는 용어가 조금씩 차이를 보이기때문에
조금은 정리해볼 필요가 있습니다.

P.S 제가 이런것을 하는데는 제 개인이 배운것에 대한 정리도 하는 것이고 
     다른 사람들로부터 제가 잘못 알고 있거나 틀린것에 대해서 알고자 하는 것도 있습니다.