Previous Contents/Genetic Algorithm

1. GA의 간단한 순서

shhyun 2006. 12. 13. 13:39

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

1. 초기화(Initialize)

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

2. 평가(Evaluate)

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

  (1) 선택(Selection)

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

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

  (3) 돌연변이(Mutation)

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

  (4) 재조합(Recombination)

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

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

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


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

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