'crossover'에 해당되는 글 2건

  1. 2007.05.22 9. 실수최적화 문제에서 이용되는 CX 연산자 (1)
  2. 2006.12.21 4. CX(Crossover) 연산자

오랜만에 GA 관련 포스팅 입니다.
예전에 한번 설명 드렸지만, GA 는 원래 Bit 형태의 유전자를 이용해서 연산을 하게 됩니다.
이 Bit 형태의 유전자를 이용해서 연산을 하게 되면,

Bit -> Real Number -> Bit 의 변환과정을 거쳐서 적합도평가(Fitness Evaluation)가 이루어집니다.

결과적으로 변환 과정의 해상도(Bit 의 갯수를 얼마나 더 확장시키는지)가 성능에 어느정도 영향을 미치는 꼴이 됩니다. 이 문제에 대해 간단한 예제로 설명하자면 밑의 More 부분을 클릭하시면 됩니다.



그래서 학자들 사이에서는

Binary 로 이용해서 변환과정을 거치는 것만으로도 실수 최적화에 성공할 수 있다.

 VS

실수 최적화 문제는 실수자체를 이용해서 최적화 시키는 것이 더 좋은 결과가 나온다.

의 두가지 논점으로 갈라지게 되었습니다.

GA 에 대해 오래 연구하신 분들께서는 위의 의견에 동의를 하시는 편이시고, GA 외에도 ES(Evolutionary Strategies)나 다른 C.I.분야에 대해서 연구하신 분들께서는 아래쪽 의견에 동의를 하시는 편 입니다.

저 같은 경우에는 Rosenbrock 이나 Griewangk 과 같은 Benchmark 문제를 두가지 접근방식으로 해결해 본 결과 아랫쪽 의견에 더 동의하는 편 입니다.

만약 우리가 실수 연산을 이용하고자 한다면, 그에 맞는 CX 와 MUT 연산자를 이용 해야 할 필요가 있습니다. 기존의 Bit 방식의 접근으로는 실수 유전자를 이용하는 의미가 떨어지게 되기 때문입니다.

그래서 오늘은 실수 유전자를 이용하는 CX 연산자 중에서 가장 기본적 연산자인 Arithmetical Crossover[Michalewicz 1996] 에 대해서 살펴보도록 하겠습니다.

--------------------------------------------------------------------------------------------

Arithmetical Crossover[Michalewicz 1996]

역시 본론 부터 말씀드리자면 기본 적인 연산자 답게 크게 어려움은 없습니다.

여기서 기억하실 것은 λ(lamda) 값 입니다.

일반 적으로 0~1 사이의 실수값으로 표현되는 λ(lamda) 값에 의해 유전자가 미묘하게 수정되게 됩니다.

그림의 예를 통해 어떻게 수정되는지 표현해보겠습니다.

사용자 삽입 이미지

(*) 그림이 조금 깨지면 클릭 하셔서 보시면 됩니다.

위에 보시면 아시겠지만 아주 단순한 알고리즘 입니다.

λ 값에 의한 변화라고 볼 수 있습니다.
λ 값의 범위가 0 ~ 1 사이로 제한되면 Convex CX
λ 값의 범위가 -0.5 ~ 1.5 사이로 제한되면 Affine CX

라고 부릅니다.

여기서 Convex 범위를 갖게 되면 유전자의 값들이 항상 원래 의도하고자 하는 유전자의 범위를
벗어나지 않게 됩니다만, Affine 범위를 갖게되면 유전자가 자칫 값이 커져버려서 범위를 벗어나곤 합니다.
그렇기에 범위를 벗어나는 것을 막아주어야 하는데, 일반적으로 두가지 방법이 있습니다.

유전자 차원에서 매번 값의 검색을 통해 Error 값을 나타내는 것
적합도 차원에서 값이 벗어날 경우 Error 값을 나타내는 것


이 있습니다. 저의 경우에는 후자를 사용해서 값을 통제했습니다.

결론적으로, Arithmetical CX 방식은 λ값을 통해 유전자 값들을 미묘하게 흔들어 주는 방식입니다.
이 방식은 구현도 매우 쉬운편이고, 효과도 그럭저럭 나쁘지 않은 편이기에 기본적인 GA에서 많이 쓰입니다.


(*) 마치며...

  사실 제가 조금 변형한 GA 를 올릴까 했습니다. 하지만 부족한 것이 너무 많기에 아직은 올리기에 부끄러울 지경입니다. 적어도 기본적인 SGA 보다는 압도적인 성능을 보여야 한다고 생각하는게 제 생각이기에 아직은 올릴 시기가 아닌 듯 싶네요. 그래서 제가 프로그래밍 하고 있는 GA 에 이용되고 있는 몇가지 연산자들에 대해서 천천히 설명하고, 새로 구현되는 내용들에 대해서 언급을 다 한후에 완성된 것을 올려보겠습니다. 보고 공부하기 좋은 GA 를 구현하려고 노력하고 있습니다 ^^
Posted by SHHyun

댓글을 달아 주세요

이번에는 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가지에 대해서 알아보도록 하겠습니다.
Posted by SHHyun

댓글을 달아 주세요