4. CX(Crossover) 연산자

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