크게 두가지 방법이 있습니다.

Physics Controller 를 이용한 접근

혹은

Supervisor Controller 를 이용한 접근


이렇게 두가지 방법이 있는데
제가 테스트 해본 바로는 신뢰성이 Physics Controller 가 더 높아보입니다.

Aibo ERS-7 의 Trajectory 를 구성하고 로봇이 실제 움직이는 모양이
Trajectory 와 어느정도 비슷한지를 평가하기 위해 Supervisor Controller 의
supervisor_field_get 함수를 이용해서 값을 추출해 봤는데
좌표값이 제대로 매칭이 안되는 것으로 판단됩니다.

로봇의 루트 노드를 타겟으로 잡고 값을 추출 할 때는 매칭이 되지만
하나의 일부 노드를 타겟으로 잡고 값을 추출 할 때는 제대로 매칭이되지 않는 것 같습니다.

반면에

Physics Controller 에서 ODE 라이브러리의 dBodyGetPosition 함수를 통해 값을 추출했을때는 로봇의 위치와 추출된 좌표값이 제대로 매칭이 되는 것으로 판단됩니다.

그리고 상대적 좌표값으로 변환했을 때, 나타나는 점들의 자취또한 Physics Controller 를 이용해 추출해 낸 값들에서 더 올바른 형태가 나타났습니다.

정리해보면

로봇이 현재 위치한 포인트를 잡아내는 방법은 두가지가 있는데
Physics ControllerdBodyGetPosition 이 있고,
Supervisor Controllersupervisor_field_get 이 있는데,

로봇의 한 노드의 포인트를 잡아내기에는 Physics Controller 를 쓰는것이 더 좋고,
현재 로봇의 루트노드의 포인트를 잡아 위치한 곳을 판단하기에는
Supervisor Controller 를 이용하는 것이 더 편합니다.

P.S 아직 정확히 왜 차이를 보이는지는 알아내지 못했습니다. -ㅠ-

너무나 오랜만에 글을 포스팅 합니다.
요 근래 너무 바빠서 별다른 정리의 시간을 갖지를 못했네요.

어쨌든 Selection 연산자에 대해서 알아보겠습니다.

우선 Selection 연산자는 유전자 선택에 쓰이는 연산자 입니다.
밑에 설명한 Mutation 과 Crossover 를 해주기 위해서는 그 대상이 필요하겠죠?
그 대상을 골라주는 역할을 해주는 것이 바로 이 Selection 연산자입니다.

Selection 연산자도 꽤 많은 종류가 있는데 몇가지에 대해서만 알아 보겠습니다.

알아볼 Selection 연산자로는

  1. 룰렛휠(Roulette Wheel Selection)
  2. 균등선택(Stochastic Universal Sampling Method)
  3. 랭크선택(Rank-based Selection)
  4. 토너먼트선택(Tournament Selection)

이중에 일반적으로 룰렛휠 이나 토너먼트 선택이 가장 많이 쓰이는 경향이 있습니다.

저는 이것들에 대해 다른 여러 설명과는 다르게 수식은 최대한 배제 하고 설명하겠습니다.
제가 이것을 정리하고 있는 이유가 수식이야 언제든 다른곳을 참조하거나 만들 수 있지만
직관적으로 연산자가 쓰이는 것에 대해 알아보는게 힘들기 때문도 있습니다.


1. 룰렛휠(Roulette Wheel Selection)

  이것은 Fitness 와 그것이 차지하고 있는 비율을 이용하는 연산자 입니다.
  만약 총 Fitness 의 합이 100 이고 어떤 유전자의 Fitness 가 10 의 Fitness 수치를 갖는다면
  이 것이 선택될 확률은 10 / 100, 즉 1/10 이 되는 것입니다.
  약 10%의 확률로 선택되는 것입니다.
  이 연산자는 그래서 다른 이름으로 적합도 비례선택(proportional selection) 이라고 불립니다.
  간단히 정리하면 현재의 유전자가 차지하고 있는 비율에 따라 선택될 확률이 정해지는 것입니다.

2. 균등선택(Stochastic Universal Sampling Method)

  이것은 모든 유전자를 Fitness 에 관계없이 같은 확률로 선택될 수 있도록 해주는 것입니다.
  보통은 모든 Fitness 값들을 더한 것을 Popsize 로 나눠서 각각의 유전자가 같은 확률을 갖게 해 줍니다.

3. 랭크선택(Rank-based Selection)

  이 연산자는 최고의 값을 갖는 유전자를 선택해 줍니다.
  조기수렴의 염려가 매우 많은 관계로 보통은 잘 사용하지 않습니다.
  조기수렴이란것에 대해서는 나중에 설명 하겠지만
  값이 전역극대 또는 전역극소를 찾아내지 못하고,
  그에 준하거나 그렇지 못하는 지역극대 또는 지역극소를 찾아내게 되는 경우가 있는데,
  그것이 너무 빠르게 지역극대나 지역극소점에 수렴하게되면
  전역극대나 전역극소를 찾지못하고, 수렴하게 되는 현상을 말합니다.

  어쨌든 이 연산자는 최고의 Fitness 를 지닌 유전자부터 내림차순으로 선택하게 됩니다.

4. 토너먼트 선택(Tournament Selection)

  가장 많이 쓰이는 토너먼트 선택 연산자 입니다.
  위의 랭크 선택과 다른 점이라고 하면
  유저가 지정한 7 또는 10 과 같은 수치에 의해 해당갯수만큼 후보를 선택하게 되고
  이것들을 경쟁을 시켜 승리하는 값을 선택하는 것이 다른 점입니다.
  무조건 적으로 전체를 후보로 두고 최고의 값을 찾는것이 아닌
  랜덤한 후보를 이용해서 경쟁을 시켜 최고의 값을 찾는 것이 조금 다릅니다.
 

오늘은 Selection 연산자에 대해서 알아보았습니다.

제가 정리하고 있는 내용들은 수식이나 구체적인 내용이 빠져있는 개략적인 설명정도이기 때문에 자세히 알아보고 싶으신분은 저에게 따로 이메일을 주시거나 아니면 다른 여러사이트들을 참조하시는 것도 좋을 것 같습니다.

다음에는 벤치마크 Problem 들에 대해서 알아보도록 하겠습니다.
일반적으로 많이 쓰는 dejong function 말고, f3deceptive 와 같은 기만적인 문제들에 대해서 알아보겠습니다.
GA 알고리즘을 연구하시는 분께는 살짝 도움이 될 것 같습니다.
오랜만에 글을 포스팅 합니다.
이래저래 하고 있는건 많고 정리할 시간이 부족하다보니 이제야 포스팅합니다.

일반적으로 쓰이는 MUT 연산자는 다음과 같은 2가지가 있습니다.

1. Single MUT
2. Multi MUT

하나는 하나의 Bit 를 MUT 시키는 것이고 다른 하나는 여러개의 Bit 를 대상으로 MUT를 수행합니다.

1. Single MUT

  이것은 하나의 Bit 만을 MUT 시킵니다. 아주 간단하게 알아 볼 수 있습니다.

  (1) 선택연산자를 통하여 선택이 이루어진다.
 (2) 선택된 개체의 한 bit 를 선택하여 MUT 시킨다.

  예를 보면 간단하게 변화를 알아볼 수 있습니다.

 만약 다음과 같은 유전자가 있다면
 
  0 0 0 0 0 0 1 0

  이것이 선택되어 7번째 bit 를 Mutation 시킨다고 가정합니다.
  그렇다면 다음과 같이 변하는 것입니다.

  0 0 0 0 0 0 0 0

2. Multi MUT

  이것은 여러개의 Bit 를 MUT 시키는 것입니다. 이전것과 동일한 방식으로 이루어 집니다.

  만약  다음과 같은 유전자가 있다면

  0 0 0 1 1 0 1 0
 
  그리고 이것이 선택 되었다고 가정을 하고, 4~8 번째 bit 가 선택 되었다고 한다면
 
 0 0 0 0 0 1 0 1

 이런식으로 변화하게 됩니다.



오늘 살펴본 MUT 는 아주 간단한 연산자 입니다만 그 사용에 있어서 아주 조심해야 합니다.
이것은 파괴연산자라 불리는 것으로서 확률의 의외성을 바라고 이용하는 것입니다.
즉 이 연산이 너무 자주 수행되게 된다면, 실제 답을 잘 못찾는 현상이 나타나기도 합니다.
보통 GA 연산 수행시에 1 ~ 10% 정도의 확률로 수행하게 하는게 일반적입니다.
알고리즘의 테스트를 위해서라면 아예 수행을 하지 않는 경우도 있습니다.

다음 번에는 Selection 연산자에 대해서 알아보겠습니다.

Webots 시뮬레이터를 혹시라도 이용하시는 분이 있으시다면

참고해 볼만한 내용 입니다.

제작자인 Olivier 씨에게 문의를 해 보았는데

x,y,z 좌표계의 1 이라는 수치가 의미하는 길이가

실세계의 1 미터 라고 하는 군요

그리고 Webots 에서 구현되어 있는 모든 로봇들의 좌표계에 대한 것인데

좌표들은 다 부모 노드에 종속되어 있는 상대적 좌표계 라고 하네요

즉 가장 외부로 나와 있는 것은 dWorld 객체에 종속되어 있는 좌표계를 이용하는 것이고

로봇의 각각의 부분은 그것이 부착되어 있는 부모 노드의 좌표를 원점으로 종속되어 있다고 하는군요.

혹시 웹봇을 이용하시는분이 계신다면 저한테 연락좀 주시겠습니까?

서로 자료에 대해 공유도 하고 토론도 하게요 ^^

이번에는 GA 의 핵심 연산자인 Crossover 연산자 입니다.

GA 의 연산자 중에서 가장 많은 연산을 수행하고
그만큼 중요도도 높은 Crossover 연산자 입니다.

수많은 방식의 연산자 들이 존재하지만 오늘은 밑에 있는 것에 대해서만 알아보겠습니다.

1. Onepoint crossover(Single)
2. Twopoint crossover(Multi)
3. Uniform crossover

위의 1,2 번 연산자는 대표적인 기본 연산자 이고, 거의 모든 bit 연산에서 쓰입니다.
3번은 거의 쓰이지 않지만 어떤 문제에는 쓰이기도 합니다. 그래서 소개하는 것입니다.

어쨌든 하나하나 알아보도록 하죠.

1. One-point Crossover(Single Crossover)

  Onepoint Crossover 는 Single Crossover 라고도 하고 GA 의 대표적 연산자 입니다.
  초기에 GA 가 만들어졌을때부터 사용된 연산자 입니다.
  가장 기본적이면서도 가장 많이 이용되고 있는 연산자 입니다.
  방식은 이전에 GA 소개 할때 보여 드렸던 것과 같은 방식입니다.

  (1) 랜덤한 수(point) 를 만들어내어 CX 할 위치 선정
  (2) Select 에 의해 선택된 두개의 개체에 대해 CX 수행

  이것이 끝입니다. 간단하죠.
  예를 들면 다음과 같습니다.

    1 0 0 0 1 1 1 0
    1 0 0 1 1 1 0 0  

위의 두 개체가 있다고 가정해봅시다. 그리고 point 가 4로 설정 되었다고 하면

    1 0 0 0 1 1 1 0
    1 0 0 1 1 1 0 0
            ^  <-- 바로 이 위치

결과는 다음과 같이 되는 것입니다.

    1 0 0 1 1 1 0 0
    1 0 0 0 1 1 1 0

  그리하여 개체는 발전해 나갈수도 있는 것이고, 더 성능이 안 좋아 질 수도 있는 것입니다.

2. Two-point Crossover (Multi Crossover)

Twopoint CX 는 Onepoint CX 가 발전된 방식 입니다. 문제의 특성에 따라 다르지만
대체적으로 Twopoint CX 가 Onepoint CX 보다 더 좋은 성능이 나오는 것으로 알려졌습니다.
  다음과 같은 방식으로 수행이 됩니다.

  (1) 랜덤한 수 (point) 를 두개를 만들어 낸다.
  (2) Select에 의해 선택된 두개의 개체에 대해 CX 를 수행

  Onepoint 와의 차이점이라면 단지 두개의 수를 만들어 낸다는 것입니다.
예를 보면 바로 이해할 수 있습니다.

  1 1 0 0 1 1 0 1
  1 0 1 1 1 0 1 1  

위와 같이 두 개체가 있다고 가정해 봅시다. 그리고 point 가 각각 2,4로 설정이 되면
 
  1 1 0 0 1 1 0 1
  1 0 1 1 1 0 1 1
      ^   ^ <-- 바로 이 두 위치
 
  결과는 다음과 같이 됩니다.

    1 0 1 1 1 1 0 1
    1 1 0 0 1 0 1 1

  최초의 point 에서부터 마지막 point 까지의 사이의 값들에 대한 CX가 이루어 지는 것입니다.
  어떤 특정 지점에 대해 좋은 형질만, 혹은 나쁜 형질만 CX 가 이루어 질 수 있는것이
  Twopoint CX 의 강점입니다.

3. Uniform Crossover

  Uniform Crossover 는 일반적으로 잘 쓰이는 연산자는 아니지만 가끔 쓰일때가 있습니다.
  방식은 다음과 같습니다.

  (1) Mask 를 설정해 줍니다.
  (2) 그 Mask 에 맞추어 선택된 두개의 개체의 CX 를 수행합니다.
 
  이것 역시 예만 보면 간단히 이해할 수 있습니다.

    1 0 0 0 0 1 1 1
    1 0 1 1 1 0 0 0

  다음과 같은 두 개체가 있다고 생각해 봅시다. 그리고 이것에 대해 UCX 를 수행하는겁니다.
  여기서 UCX 는 다른것과 다르게 Mask 를 설정해 줘야 합니다.
  임의에 설정에 따라 Mask 를 설정해 줄 수도 있고, 직접 해 줄 수도 있습니다.
  우리는 0 0 0 1 1 0 0 1 로 Mask를 설정했다고 가정해보죠.
  그리고 이 Mask 를 토대로 다음과 같이 연산을 수행합니다.
 
    1 0 0 0 0 1 1 1
    1 0 1 1 1 0 0 0
    0 0 0 1 1 0 0 1 <-- Mask

  Mask 는 1로 설정된 위치에 대해서만 서로를 CX시켜주는 역할을 합니다.
  그러므로 결과는 다음과 같이 됩니다.

    1 0 0 1 1 0 0 0
    1 0 1 0 0 0 0 1
 
  결과적으로 특정 위치에 대해서만 CX 를 시켜주는 용도로 이용되는 연산자입니다.


CX 연산자들은 개체의 형태에 따라 조금씩 달라지기는 합니다.
하지만 기본적으로 컴퓨터는 2진수를 사용하고 개체가 어떻게 표현이 되더라도
그것은 2진수로 변환할 수 있기에 위의 연산자를 이용하면 광범위한 CX 연산이 가능합니다.

다음에는 대표적인 Mutation 방식 2가지에 대해서 알아보도록 하겠습니다.
으흠...

로봇 시뮬레이션 때문에 Webots 을 이용하고 있는데

모르는게 참 많아서 걱정이네요

3D 처리나 이런부분에 대해서는 공부를 안해봐서요 -_-;;

생소한 것도 많고 ㅠㅠ

어쨌든

다음 GA 연산자 Crossover 에 대한 글은

다 정리되어가고 있습니다.

몇가지 용어에 대해서 정리해 보도록 하겠습니다.

사실 GA 에서는 크게 2가지의 알고리즘으로 나뉘어 있고
흐름에 의한 알고리즘 자체의 차이가 있을뿐이지
용어에 대해서는 차이가 없습니다.

하지만 GA 를 구현한 프로그램들마다
용어자체에 약간의 차이를 두고 구현되어 있는 경우가 있습니다.
그에 대해서 한번 생각해 보기 위해 용어에 대해 정리해 보는 것입니다.

가장 하위계층의 개체부터 개체의 조합. 그리고 연산자까지 정리해보도록 하겠습니다.

먼저 하나의 개체는 일반적으로 다음과 같이 되어 있습니다.

Chromosome - 유전자표현
Fitness - 적합도
OBJ(x) - 유전자표현을 10진수로 변환한것, 다른형태로 표현하기도 합니다.
parent1 -
parent2 - parent1과 2는 현재의 개체가 Crossover로 부터 다시 생성되었을 때
             이 두 개체의 부모개체가 되는 유전자의 번호입니다.

일반적으로 하나의 개체를 표현하는데에 저 다섯가지의 요소로서 구성됩니다.

저 개체는 Individual 이라고 표현하고 개체라고 합니다.

Individual < Population < Multi-population

이런식으로 되어 있습니다.

각각의 Individual 이 모인 집합을 Population 이라고 하고
Population 이 모인 집합을 Multi-population 이라고 합니다.

Multi-population 에 대해서는 나중에 소개를 하겠지만
대부분의 실제 알고리즘에서는 다수의 Population 을 이용해서
서로간의 연산 알고리즘이 이루어 집니다.
복잡해지는 관계로 다음에 추후 이야기 하겠습니다.

그리고 연산자에 대해서 간단히 용어정리를 하겠습니다.
CX = Crossover 를 의미하는 것입니다.
      제가 지난번에 Crossover 연산에 대해 간략하게 소개 했습니다.
      그런 식으로 이루어지는 일련의 연산들을 Crossover 라고 합니다.
      더 자세하게는 다음에 소개하겠습니다.
MUT = Mutation 을 의미합니다.
         역시 마찬가지로 다음에 소개 하겠습니다.
         (소개할 내용이 무지하게 많습니다;;)
SELECT = 말그대로 선택 연산자입니다.
INV = Inversion , 역위 연산자 입니다. 거의 쓰지 않습니다만
       몇몇 알고리즘에서는 여전히 이용합니다. 역시 나중에 설명하겠습니다.

사실 이 외에도 엄청나게 다양한 용어의 정리가 필요합니다.
하지만 가장 기본이 되는 저 틀은 거의 변하지 않습니다.

다음번에는 CX 연산자들에 대해서 소개하겠습니다.
몇회에 걸쳐서 소개해 보겠습니다.

오늘은 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