오늘은 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 제가 이런것을 하는데는 제 개인이 배운것에 대한 정리도 하는 것이고 
     다른 사람들로부터 제가 잘못 알고 있거나 틀린것에 대해서 알고자 하는 것도 있습니다.

GA 는 하나의 알고리즘으로서 기본적으로 다음과 같은 순서로 동작합니다.
(여기서 설명하는 것은 일반적인 알고리즘이고 변형된 알고리즘으로서 Steady-State 알고리즘이 있습니다.)

1. 초기화(Initialize)

  유전자 개체를 초기화 합니다.
  임의로 지정한 수치 만큼의 유전자를 생성해 내는 것입니다.

2. 평가(Evaluate)

위에 생성된 유전자 개체에 대해 평가를 합니다.
  평가의 기준은 사용자가 만드는 것입니다.
  생성된 유전자가 문제에 어느정도 적합한 유전자 인지 평가하는 것입니다.
 
3. 반복(Loop)
 
  여기서 부터는 몇가지 반복작업이 계속 이루어 집니다.
  반복이 멈추는 조건은 사용자가 지정한 최대 세대수[1]에 도달하거나
사용자가 지정한 최대조건에 도달 했을 경우 입니다.
  멈추지 않을경우 밑에 작업을 순서대로 반복 수행 하게 됩니다.

  (1) 선택(Selection)

    선택도 하나의 연산입니다.
    여러가지 방식이 있으며 가장 평가가 좋은 유전자를 선택할 수도 있습니다.
    아니면 랜덤하게 선택할 수도 있는 것입니다.
    문제에 맞게 선택연산자를 선택해 주면 됩니다.
    여기서 선택된 유전자는 다음의 교배, 돌연변이 연산자에 이용 됩니다.

(2) 교배(Crossover)
 
    유전자 알고리즘의 가장 핵심이 되는 부분이라고 할 수 있습니다.
    각각의 선택된 유전자 개체에 대해 교배가 이루어 지는 부분입니다.
    유전자의 일부분을 다른 상대방 유전자의 일부분과 교체 하는 등의 연산입니다.
    이것을 통해 개선이 이루어질 수 있습니다. 물론 성능이 떨어질 수도 있죠.
    대부분의 연산은 이것을 통해 이루어 집니다.

  (3) 돌연변이(Mutation)

    돌연변이 연산은 유전자의 일부분을 임의대로 변경해버리는 것입니다.
    교배와 다른점이라면 교배는 한 쌍의 유전자를 서로 교체 하는 등 같이 연산되는 것이지만
    이것은 하나의 유전자의 일부분을 랜덤하게 교체시켜 버리는 것입니다.
    그것으로서 유전자가 파괴될수도 있지만 의외로 좋은 유전자가 될수도 있기때문에
    아주 적은 확률로서 이루어지게 합니다.

  (4) 재조합(Recombination)

    이것은 위의 교배와 돌연변이의 연산자로서 새로 변경된 유전자들을 모아서 새로운 세대를
    생성하는 것입니다. 이것이 이루어지면 한 세대가 지났다고 할 수 있습니다.

  (5) 평가(Evaluate)
 
    다시 평가 작업입니다. 새로 교배와 돌연변이를 통해 생성된 유전자를 평가하는 것입니다.
    유전자의 성능의 개선여부에 대해 확인할 수 있습니다.
   
  (6) 통계(Statistics)

    평가가 이루어진 유전자에 대한 통계를 냅니다.
    주로 개체의 최대,최소,평균 성능에 대해 통계를 냅니다.


위와 같은 반복적 작업을 통해 개체의 상태를 개선시켜 나가고 문제의 해답을 알아내는 알고리즘이 GA 입니다.

최대한 수학적인 요소는 제거하고 가장 간단한 상태의 GA 에 대해 설명했습니다. 내일은 간단한 예에 대해 올려보도록 하겠습니다.

rUNSWIft 팀( http://www.cse.unsw.edu.au/~robocup/2006site/index.phtml )

의 Inverse Kinematics 자료를

분석해 놓은 것입니다.

관심 있으신분은 보세요.

틀린부분이 있다면 지적해 주시면 감사하겠습니다.

출처는 꼭 밝혀주세요.

PDF#1 PDF#2

우선 크게 분류를 나눠보고 제가 어느 분야를 공부하고 있는지를 말씀드리자면
Artificial Intelligence 와 Computational Intelligence 로 구분할 수 있는데
A.I. 는 흔히 알고 있는 인공지능 이고
C.I. 는 계산지능이라고 표현하면 올바를것 같습니다.
저는 C.I. 쪽을 공부하고 있습니다.
이것은 Fuzzy System(FS), Neural Network(NN), Evolutionary Computation(EC) 등 으로 구분할 수 있는데
저는 이중에서도 Evolutionary Computation 쪽을 공부하고 있습니다.
그 중에서도 Genetic Algorithm 과 Genetic Programming 에 대해서 공부를 하고 있습니다.
유전적인 이론(예: 다윈의 진화론)들을 토대로 이것을 연산에 이용하는 것인데요

Genetic Algorithm 에 대해 간단히 말씀드리면
어떤 문제에 대한 해결책으로서의 유전자를 생성후에 이것을 진화시켜 나가는 것이죠
진화 시켜 나가는 방식이 바로 다윈의 진화론이나 교육시스템 과 같은 사회적, 자연적 현상들을
모티브로서 가져온 것들입니다.
(물론 인위적인 요소들이 많이 있습니다만 실제적으로 우리는 자연적 현상들을 더 많이 적용시킨것을 볼 수 있습니다.)
GA 에 대해서는 많은 자료들이 있기때문에 검색해보시면 잘 알수 있을거예요.

GA 에 대한 실질적 예제와 방식은 다음에 정리해 보렵니다.

이 블로그에 앞으로 제가 배우고 있는 것들과 연구하고 있는 것들에 대해서
정리해서 올려놓을 생각입니다.

+ Recent posts