PostgreSQL 9.6.2 문서
이전	위로	장 58. 유전 쿼리 최적화	다음

58.2. 유전자 알고리즘

유전자 알고리즘 (genetic algorithm GA)은 무작위 차출을 통해 만들어지는 경험적 최적화 방법이다. 최적화 문제를 풀기위한 해결책들(실행 계획 후보군들)을 개체들의 집단으로 간주한다. 한 개체가 그 환경에 적응하는 정도를 적합도라 한다.

검색 공간에서 한 개체의 위치는 염색체라고 간주하고, 이것은 하나의 문자열로 처리된다. 유전자는 염색체의 구성요소이며, 염색체는 단일 매개변수값으로 최적화된 자료로 인코딩된다. 유전자 인코딩은 이진자료형이나, 정수형으로 처리한다.

진화과정을 시뮬레이션한다 - 재조합, 변이, 선택 과정을 거치면서 해결책 가운데 가장 적합도가 높은 것을 선택한다.

comp.ai.genetic 뉴스그룹 FAQ에 따르면, 어떤 문제의 해결책을 찾는데 있어 GA 방법은 순수한 무작위 검색은 아니다라고 꼭 그렇게 말할 수는 없다고 한다. (순수한 무작위 선택의 결과와 같을 수도 있다 - 옮긴이) GA는 확률론적 과정을 거치기에 그 결과는 분명 임의적 결과는 아니다(순수 임의 선택보다는 낫다).

그림 58-1. 유전자 알고리즘의 구조화된 도식

P(t)	t 시간에 만든 조상 세대
P''(t)	t 시간에 만든 자손 세대

+=========================================+
|>>>>>>>>>>>   알고리즘 GA  <<<<<<<<<<<<<<|
+=========================================+
| t := 0 초기화                           |
+=========================================+
| P(t) 생성                               |
+=========================================+
| P(t) 적합도계산                         |
+=========================================+
| 중지 조건에 맞을 때까지 반복
|   +-------------------------------------+
|   | P'(t)  := P(t) 재조합               |
|   +-------------------------------------+
|   | P''(t) := P'(t) 변이                |
|   +-------------------------------------+
|   | P(t+1) := P''(t)와 P(t) 가운데 선택 |
|   +-------------------------------------+
|   | P''(t) 적합도 계산                  |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+

이전	처음으로	다음
복잡한 쿼리 최적화 문제 관점에서 본 쿼리 처리	위로	PostgreSQL 유전 쿼리 최적화 Genetic Query Optimization (GEQO)