제 15강 해탐색 알고리즘 (유전알고리즘 원리, 연산자 )

8.3 유전 알고리즘 (GA : genetic algorithm) 

8.3.1 유전 알고리즘

 

최적화 문제를 해결하기 위해 탐색 공간에서 해를 찾을 때 진화 메커니즘을 모방하여 탐색하는 방법

  - 탐색 공간 search space -> 모든 가능한 해의 집합

 

보다 나은 성능의 영역으로 탐색을 이끌기 위해 적자생존 모방

 - 다윈의 진화에 대한 원칙을 수용해서 설계

    - 실제 자연에서는 제한된 자원에 대한 개체 간의 경쟁을 통해 환경에 가장 적합한 개체가 형성되고, 이들이 결국은 약자를 다스리게 된다.

 

 - "해가 진화한다. "

   - 주어진 문제 해결을 위해서 연속적인 세대를 거치면서 개체 사이의 적자 생존을 통해 점진적으로 해를 향상 시켜 나감 

 

- 다윈의 진화 -

1. 개체군의 각 개체는 자원과 짝을 형성하기 위해서 서로 경쟁한다.

2. 경쟁에서 가장 성공적인 개체들은 그렇지 못한 개체보다 더 많은 자손을 생성한다.

3. '좋은' 개체로 부터의 유전자는 개체군을 통해서 전파되어,

두 개의 좋은 부모는 종종 그들 부모보다 더 나은 자손을 만들 수 있다.

4. 이러한 각각의 세대는 그들의 환경에 보다 적합해진다.

 

유전 알고리즘의 처리 과정

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

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

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

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

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

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

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

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

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

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

 

 

8.3.2 유전 알고리즘의 연산자

 처리 과정에 영향을 미치는 요인

- 염색체를 어떻게 만들 것인가?  교차 및 변이 연산에도 영향을 미침

- 부모 염색체를 어떻게 선택할 것인가? 좋은 부모가 좋은 자손을 생산할 것이라는 희망에서 출발

- 교차위치, 교차확률, 변이 확률을 어떻게 할 것인가? 

- 적합도를 어떻게 계산할 것인가?

 

염색체

탐색 공간에서 각 점에 해당하는 개체(염색체)는 하나의 가능한 해를 타내고,

따라서 각 개체들의 집합인 개체군은 해법의 집합을 의미

 

(1) 염색체의 인코딩

 해에 대한 정보를 염색체의 형태로 표현

: 주어진 문제에 전적으로 의존 

ex) 이진 인코딩, 순열 인코딩, 값 인코딩, 트리 인코딩 등

 

 

1) 이진 인코딩

 가장 보편적인 방법

- 각 염색체를 0과 1의 비트열로 표현

  : 각 비트는 해의 한 특성을 표현

- 종종 교차/변이 연산 후에 별도의 작업이 필요한 경우 발생 

2) 순열 인코딩

순서를 결정하는 문제에 적용될 수 있는 방법

 - 외판원 문제, 작업 순서등

 

3) 값 인코딩

직접 값을 사용해서 인코딩하는 방법

- 각 염색체가 어떤 값(정수, 실수, 문자 등)들의 스트링으로 표현

- 이진 인코딩으로는 표현이 어렵거나 적절하지 못한 경우에 사용 가능

 

4) 트리 인코딩

각 염색체가 프로그래밍 언어에서 함수나 명령과 같은 어떤 객체의 트리로 표현

- 프로그램과 수식의 진화 과정을 나타내는 데 주로 사용

- LISP 에서 종종 사용

  : 트리 형태로 쉽게 파싱가능 ->상대적으로 용이한 교차 연산과 변이 연산