Previous Contents/Genetic Algorithm

6. Selection 연산자

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

어쨌든 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 알고리즘을 연구하시는 분께는 살짝 도움이 될 것 같습니다.