제 15강 유전 알고리즘 ( 선택, 교차, 변이)

유전 알고리즘의 처리 과정

 [초기화]  난수를 사용해 n개의 염색체로 이루어진 개체군을 생성

 [적합도]  개체군의 각 염색체에 대해 적합도 점수를 계산

[새 개체군] 새로운 개체군이 완성될 때까지 다음 과정을 반복

     [선택] 적합도에 따라 개체군에서 두 부모 염색체를 선택

     [교차] 교차 확률에 따라 두 부모 염색체를 교차시켜 자손을 생성

     [변이] 변이 확률에 따라 새 자손 염색체의 선택된 위치의 값을 변경

     [저장] 새 자손을 새로운 개체군에 포함시킴

[대체] 새로운 개체군으로 이전의 개체군을 대체

[종료검사] 종료 조건이 만족되면 종료하고, 현 개체군의 가장 좋은 해를 반환

[반복] 위의 [적합도] 계산 부분부터 다시 수행

 

 

(2) 선택 

개체군으로부터 부모가 되어 교차를 수행할 염색체를 선택

- 가급적 좋은 부모가 선택되어 자손을 생성해야 됨

- 룰렛 힐 선택, 순위 선택, 토너먼트 선택, 엘리티즘

 

1) 룰렛 힐 roulette wheel 선택

염색체들의 적합도에 비례해서 개체군에서 다음 세대로 넘겨 줄 염색체를 선택하는 방법

- 적합도 점수가 높을수록 선택될 확률이 높은 방법

>>> 가장 적합한 염색체가 다음 세대로 전달되는 것을 보장하는 것이 아니라

그것들이 그렇게 될 가능성을 높여주는 방법

 

염색체의 적합도 점수에 비례하여 힐의 각 슬라이스의 할당 크기가 결정

[합 계산]

개체군의 모든 염색체의 적합도 점수의 합 S 계산

 

[선택]

구간 0 ~ S 사이의 난수 r을 생성

 

[반복]

for ( i=0; i<n; I++ ) {
     s = s + 염색체i 적합도;

     if (r < s) return i ; // 염색체i 반환

}

 

2) 순위 선택

염색체들의 적합도가 아닌 순위에 비례해서 선택하는 방법

- 개체군에 대해 각 염색체의 순위를 지정한 후,

순위가 높을 수록 선택될 확률을 높게 하는 방법

- 모든 염색체가 선택될 기회 제공, 늦은 수렴 속도

 

 

 

3) 토너먼트 선택

두개의 염색체를 임의로 선택한 후, 0과 1 사이의 난수를 발생시키고,

이 값이 기준 t보다 작으면 두 염색체중에서 적합도가 좋은 것을 선택하고, 그렇지 않으면 적합도가 낮은 것을 선택

 

4) 엘리티즘 elitism

가장 좋은 몇 개의 염색체를 아무런 변화 없이 새로운 개체군으로 그대로 복사한 후, 나머지는 전형적인 방법과 동일하게 동작

- 교차와 변이 과정에서 가장 좋은 염색체의 분실 가능성을 방지

- 급격한 성능 향상이 가능

 

 

 

(3) 교차 crossver

두 해의 특징을 부분 결합하여 하나의 새로운 특징을 생성

- 유전 알고리즘의 대표적인 연산

 : 다른 최적화 방법과 구별 짓는 주요 요소

- 교차의 유형과 구현은 인코딩과 주어진 문제에 따라 달라짐

- 단일점 교차, 두전 교차, 균등 교차, 산술 교차 등

 

1) 단일점 single point 교차

교차점 하나를 이용하는 방법으로 하나의 교차 점을 기준으로 첫 번째 분모 염색체로부터는 시작부터 교차점까지의 유전자가 새 염색체로 복사되고,

두 번째 부모 염색체로부터는 교차점 이후부터 마지막까지의 유전자가 복사되어 새로운 염색체를 구성한다.

 

2) 두점two point 교차

교차점 두 개를 이용하는 방법

부모 염색체 1 (1)부분 : 시작부분 부터 첫번째 교차점까지의 유전자가 복사 되고, 

(2)부분 : 다시 두번째 교차점에서 마지막 까지,

그리고 (3)부분 : 부모 염색체 2에서는 첫번째 교착점에서 두번째 교착점 까지 중간부분을 복사해서 

부분 (1),(2),(3) 을 이어서 새로운 염색체를 구성한다.

 

3) 균등 uniform 교차 

염색체의 각 유전자 위치에 대하여 난수를 발생시키고, 이 값과 미리 설정된 임곗값과의 비교를 통해

큰 경우에는 첫번째 염색체의 해당 위치에 있는 유전자를 복사하고 

작은 경우에는 두 번째 부모 염색체의 유전자를 복사하는 방법

 

4) 산술 arithmetic 교차

두 부모 염색체에 득정 산술 연산을 적용하여 자손 염색체를 생성하는 방법, 실수로 인코딩된 염색체를 사용하는 경우에 유용

 

 

 

(4) 변이

낮은 확률로 새로운 개체의 일부분의 유전자를 변경하는 연산

- 자손 염색체가 부모 염색체에 없는 속성을 갖도록 유도

- 탐색 공간에서 임의적인 이동을 유발하여 개체군 내의 다양성을 유지하며 정상보다 이름 수렴이 일어나지 않도록 억제하는 역활

 

> 전형적인 연산 방법

if각 유전자에 대한 0~1사이의 난수 < Θ 

                                           then 해당 유전자를 임의로 변경

                                            else 아무런 변화도 없음

 

 

 

1) 이진 인코딩의 변이

비트를 변환, 선택된 유전자에 해당하는 비트를 0 에서 1  or  1에서 0 으로 바꾼다.

 

2) 순열 인코딩의 변이

두 개의 숫자를 선택한 후 위치를 바꾼다.

 

 

3) 실수값 인코딩

선택된 유전자의 값에 작은 값을 더하거나 빼준다.

 

4) 트리 인코딩의 변이

연산자 또는 숫자에 해당하는 노드를 변경. 

 

 

 

 

 

8.3.3 유전 알고리즘의 주요 매개변수

교차 확률, 변이 확률, 개체군의 크기가 있다.

- 이진 인코딩 방식의 유전 알고리즘의 경험적인 연구 결과에 기반

 

(1) 교차 확률

교차가 얼마나 자주 수행될 것인가?

 -교차 확률 = 100% → 모든 자손 염색체가 교차에 의해 생성 

 - 교차 확률 =  0%  → 교차 미적용 → 새로운 자손 염색체는 부모 염색체의 복사본

 엘리티즘이 필요하므로 일반적으로 80~95%가 되도록 높게 설정

 

(2) 변이 확률

> 얼마나 자주 염색체의 일부가 변경될 것인가?

   - 100% >> 염색체의 모든 것이 변경

   -   0%  >> 어떤 변경도 없이 그대로 사용

> 국부해에 빠지는 것을 방지하는 효과를 갖지만, 너무 자주 발생하지 않아야 함

   - 자주 발생하면 임의 탐색으로 변질될 가능성이 높음

> 변이 확률은 매우 낮아야 하며, 대략 0.5% ~ 1.0%

 

(3) 개체군의 크기

한 세대 (개체군) 내에 얼마나 많은 염색체를 포함하고 있는가?

  - 너무 작으면 >> 교차를 수행할 가능성이 낮고 탐색 공간의 매우 작은 부분만 사용

  - 너무 크면    >> 늦은 수렴

대략 20 ~ 30, 경우에 따라서 50 ~ 100 

  - 인코딩 방법과 인코딩된 스트링의 길이에 의존

 

 

8.3.4 외판원 문제

여러 도시가 주어지고 도시 사이를 이동할 때 필요한 비용이 주어진 경우, 최소한의 비용으로 모든 도시를 한 번씩만 방문하고 처음 도시로 돌아오는 방법을 찾는 문제 

 

 

(1) 염색체의 인코딩

순열 인코딩 >> n개의 정점을 1부터 n까지의 n개의 숫자로 취급

 

 

(2) 교차

단일점 교차 또는 두 점 교차

 

 

(3) 변이

 

 

(4)적합도 함수

가중치의 합이 작을수록 최적해에 가깝고

-> 최적해에 가까울수록 높은 적합도 부여

모든 간선의 가중치 중 가장 큰 값을 m 이라고 가정

 

f(염색체) = mn + 1 - ( 염색체 사이클의 가중치의 합)

 

(5) 종료 조건

개체군의 70 ~ 80 %가 동일한 수준의 적합도를 갖는 염색체로 구성될 때 종료 또는 최대 세대수를 설정