- 상위 문서: 알고리즘
목차
GA, Genetic Algorithm
1 개요
"결국 살아남는 종은 강인한 종도 아니고, 지적 능력이 뛰어난 종도 아니다. 종국에 살아남는 것은 변화에 가장 잘 적응하는 종이다."- 찰스 다윈
유전 알고리즘은 존 홀랜드(Jonh Holland)가 1975년에 저서 "Adaptation on Natural and Artificial Systems" 에서 처음 소개된 최적화 기법이며 특히, 실제 생물 진화를 모방해서 문제를 해결하는 진화 연산의 대표적인 방법이다.
유전 알고리즘은 자연계의 유전학에 바탕을 두며, 특히 다윈의 적자생존 이론을 기본 개념으로 한다. 유전자 프로그래밍에서는 문제에 대한 가능한 해들을 나열한 뒤, 점점 유전자들을 변화시켜 정확도가 높고 좋은 해들을 만들어 낸다. 여기서 문제의 해들을 유전자 라고 부르고, 그리고 이런 유전자들을 변형시켜 좋은 해를 얻는 것을 진화라고 볼 수 있다. 즉, 더 좋은 답을 찾아 가기 위해 진화를 모방한 탐색 알고리즘이라고 할 수 있다.
유전자 알고리즘으로 잘못 알고 있는 경우도 있는데, '유전 알고리즘'이 맞다.
2 전체적인 과정
일반인도 알 수 있게끔 간단한 예시를 곁들여 설명한다.
예시 목표: 이진수 0000(2)~1111(2)까지의 수 중에서 가장 큰 수를 찾고 싶다.[1]
2.1 초기화 (Initialize)
- 유전 알고리즘으로 해결하고자 하는 해를 유전자로 표현한다.
- 예시에서는 간단하게 해 그 자체를 유전자로 표현해본다.
- 유전자 : [#, #, #, #] (#은 0 또는 1)
- [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 1]
2.2 선택 (Selection)
- 배치한 각 유전자에 대해 적합도(Fitness, 점수라고 봐도 좋다.)를 측정한다.
- 이때 점수를 계산하는 방법에 따라 해를 빨리 찾을 수도, 영원히 찾지 못할 수도 있으니 신중해야 한다.
- 여기선 1의 개수를 점수로 매긴다.
- [0, 0, 1, 0]: 1, [0, 1, 0, 0]: 1, [1, 0, 1, 0]: 2, [1, 1, 0, 1]: 3, [0, 0, 0, 0]: 0, [0, 0, 0, 0]: 0, [1, 0, 0, 0]: 1, [1, 0, 1, 1]: 3, [0, 0, 1, 1]: 2, [0, 0, 0, 1]: 1
- 점수가 큰 순서대로 정렬하면 다음과 같다.
- [1, 1, 0, 1], [1, 0, 1, 1] / [1, 0, 1, 0], [0, 0, 1, 1] / [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1] / [0, 0, 0, 0], [0, 0, 0, 0]
- 현재 세대에서 다음 세대로 전해질 후보를 선택한다.
- 여기서는 순위 기반 선택을 사용해서 상위 4개의 유전자만 골랐다.
- [1, 1, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [0, 0, 1, 1]
2.3 교차 (Crossover)
- 좌측의 유전자를 물려받은 자리는 -를, 우측의 유전자를 물려받은 자리는 +를, 좌우가 같은 경우는 *를 수 옆에 붙인다.
- [1, 0, 1, 1] + [1, 0, 1, 1] → [1*, 0*, 1*, 1*]
- [1, 0, 1, 0] + [1, 0, 1, 1] → [1*, 0*, 1*, 0-]
- [1, 0, 1, 0] + [1, 0, 1, 1] → [1*, 0*, 1*, 1+]
- [1, 0, 1, 1] + [1, 0, 1, 0] → [1*, 0*, 1*, 1-]
- [1, 1, 0, 1] + [1, 0, 1, 1] → [1*, 1-, 1+, 1*]
- [1, 0, 1, 1] + [1, 0, 1, 1] → [1*, 0*, 1*, 1*]
- [1, 0, 1, 0] + [1, 0, 1, 1] → [1*, 0*, 1*, 1+]
- [1, 0, 1, 0] + [1, 0, 1, 1] → [1*, 0*, 1*, 0-]
- [1, 0, 1, 1] + [1, 0, 1, 0] → [1*, 0*, 1*, 1-]
- [1, 0, 1, 1] + [1, 1, 0, 1] → [1*, 1-, 1+, 1*]
- 결과: [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]
2.4 변이 (Mutation)
- 만든 후대 유전자에서 낮은 확률로 변이를 일으킨다.
- [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1 → 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]
- 보다시피 정답이였던 유전자가 변이를 일으키는 바람에 정답의 수가 줄었다. 이렇듯 유전 알고리즘을 동작시킬 때 항상 답에 근접하는 것은 아니다.
2.5 대치 (Replace)
- 현재 유전자를 후대 유전자로 교체시킨다.
왕위를 계승 중입니다.- [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 1]
- ↓
- [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]
- 보다시피 전체적으로 정답에 좀 더 가까워졌다.
2.6 반복 (Loop)
- 거의 모든 유전자가 같아졌고 전체적으로 변화가 거의 없어질때까지 선택, 교차, 변이, 대치를 반복한다.
- 눈치챘겠지만 이런 방법으로는 운이 나쁘면 1111(2)에 도달하지 못하고 종료될 수도 있다. 이걸 방지하기 위해서 변이가 있는 것이지만 좀 더 복잡한 문제에서는 항상 최선의 결과가 나오지 않을 수 있다.
2.7 종료
- 얻은 유전자의 해가 원하던 것인지 확인하고 종료한다.
- 1111(2)라는 결과를 얻었고, 범위 내의 가장 큰 수인 듯하다!
3 학교 교과목의 일종으로서
학부과정에서는 인공지능 과목의 일부 단원에서 이를 다룬다. 동서대학교 강의자료
컴퓨터학과 대학원 과정에서 종종 '유전 알고리즘' 과목이 개설된다. 'Evolutionary Algorithms'(진화 알고리즘)이라고도 개설된다. 강의계획서(콜로라도 대학교)
주된 주제로는 다음이 있다. 각 수업은 교재나 관련 논문 1편을 주 텍스트로 잡고 이뤄진다.
- binary genetic algorithm
- Continuous Genetic Algorithm
- Hybrid Genetic Algorithm
- Evolutionary visual art and design
- Genetic Algorithm-based Clustering Technique
- micro-genetic algorithm
- effective heuristic algorithm
- parallel genetic algorithm
- evolutionary multi-objective optimization
- Differential Evolution (DE)
- particle swarm algorithm
- ant colony system