[include(틀:분자생물학&생화학)]
[include(틀:이론 컴퓨터 과학)]
[include(틀:컴퓨터공학)]

[목차]

|| [youtube(Yr_nRnqeDp0)] ||
|| 유전 알고리즘 작동 예시 ||

== 개요 ==
>"결국 살아남는 종은 강인한 종도 아니고, 지적 능력이 뛰어난 종도 아니다. 종국에 살아남는 것은 변화에 가장 잘 적응하는 종이다."
>- [[찰스 다윈]]
'''Genetic Algorithm'''
'''Evolutionary Algorithm'''

유전 알고리즘은 존 홀랜드(John Holland)가 1975년에 저서 "Adaptation on Natural and Artificial Systems" 에서 처음 소개한 [[최적화]] 기법이며 실제 생물 진화를 모방해서 문제를 해결하는 진화 연산의 대표적인 방법이다.

유전 알고리즘은 자연계의 [[유전학]]에 바탕을 두며, 특히 다윈의 [[자연 선택]] 이론을 기본 개념으로 한다. 유전자 프로그래밍에서는 문제에 대한 가능한 해들을 나열한 뒤, 점점 유전자들을 변화시켜 정확도가 높고 좋은 해들을 만들어 낸다. 여기서 문제의 해들을 유전자 라고 부르고, 그리고 이런 유전자들을 변형시켜 좋은 해를 얻는 것을 진화라고 볼 수 있다. 즉, 더 좋은 답을 찾아 가기 위해 진화를 모방한 [[탐색 알고리즘]]이라고 할 수 있다.

유전'''자''' 알고리즘으로 잘못 알고 있는 경우도 있는데, '유전 알고리즘'이 맞다.

NN(Neural Network)이 나오기 전까지 가장 핫했던 알고리즘이며, [[인공신경망]]이 나오며 쇠퇴할 줄 알았으나 [[딥러닝]]에서의 초깃값을 설정할 때 쓰이는 등 아직도 중요한 역할을 하고있다.

Evolutionary Algorithm(진화 알고리즘)이라는 이름으로 불리기도 한다.
== 전체적인 과정 ==
일반인도 알 수 있게끔 간단하고 유명한 예시를 곁들여 설명한다.
예시 목표: '''이진수''' 0000''(2)''~1111''(2)''까지의 수 중에서 가장 큰 수를 찾고 싶다.[* 물론 1111''(2)''인 것을 바로 계산할 수 있지만 어디까지나 예시이다.]

=== 초기화 (Initialize) ===
 1. 유전 알고리즘으로 해결하고자 하는 해를 [[유전자]]로 표현한다.
  i. 예시에서는 간단하게 해 그 자체를 유전자로 표현해본다.
  유전자 : [#, #, #, #] (#은 0 또는 1)
 1. [[랜덤]]한 유전자를 적당한 개수만큼 준비한다.
  i. 여기서는 10개를 준비했다. '''실제로는 이거보단 많아야 한다!'''
  {{{[1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 0, 1]}}}

=== 선택 (Selection) ===
 1. 배치한 각 유전자에 대해 적합도(Fitness, [[점수]]라고 봐도 좋다.)를 측정한다.
 이때 점수를 계산하는 방법에 따라 [[해]]를 빨리 찾을 수도, 영원히 찾지 못할 수도 있으니 신중해야 한다.
  i. 여기선 1의 개수를 점수로 매긴다.
  {{{[1, 0, 0, 0]: 1, [0, 1, 0, 0]: 1, [0, 0, 1, 0]: 1, [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}}}
  i. 점수가 큰 순서대로 [[정렬]]하면 다음과 같다.
  {{{[1, 1, 0, 1], [1, 0, 1, 1] / [1, 0, 0, 1], [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]}}}
 1. 현재 세대에서 다음 세대로 전해질 후보를 선택한다.
 선택하는 방법에는 균등 비례 [[룰렛]] 휠 선택, [[토너먼트(스포츠)|토너먼트]] 선택, [[순위]] 기반 선택 등이 있다.
  i. 여기서는 순위 기반 선택을 사용해서 상위 4개의 유전자만 골랐다.
  {{{[1, 1, 0, 1], [1, 0, 1, 0], [1, 0, 0, 1], [0, 0, 1, 1]}}}

=== 교차 (Crossover) ===
 1. 선택한 유전자들을 가지고 여러 방법을 이용해서 [[자식|후대]] 유전자를 만든다.
  i. 여기서는 후보 중 두 유전자를 랜덤으로 골라서 각 자리에서 [[확률]]적으로 물려받아 후대를 생성한다.
  좌측의 유전자를 물려받은 자리는 -를, 우측의 유전자를 물려받은 자리는 +를, 좌우가 같은 경우는 *를 수 옆에 붙였다.
  {{{[1, 0, 1, 0] + [1, 0, 1, 0] → [1*, 0*, 1*, 0*]}}}
  {{{[1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 0-]}}}
  {{{[1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 1+]}}}
  {{{[1, 1, 0, 1] + [1, 0, 1, 0] → [1*, 0+, 1+, 1-]}}}
  {{{[1, 1, 0, 1] + [1, 0, 0, 1] → [1*, 1-, 0*, 1*]}}}
  {{{[1, 0, 0, 1] + [1, 1, 0, 1] → [1*, 0-, 0*, 1*]}}}
  {{{[1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 1+]}}}
  {{{[1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 0-]}}}
  {{{[1, 0, 0, 1] + [1, 0, 1, 0] → [1*, 0*, 1+, 1-]}}}
  {{{[0, 0, 1, 1] + [1, 0, 0, 1] → [1+, 0*, 1-, 1*]}}}
  결과: {{{[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]}}}

=== 변이 (Mutation) ===
 1. 만든 후대 유전자에서 낮은 확률로 [[변이]]를 일으킨다.
  i. {{{[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1 → 0, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]}}}
  보다시피 정답이었던 유전자가 변이를 일으키는 바람에 정답의 수가 줄었다. 이렇듯 유전 알고리즘을 동작시킬 때 항상 답에 근접하는 것은 아니다.

=== 대치 (Replace) ===
 1. 현재 유전자를 후대 유전자로 교체시킨다. 
  i. {{{[1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 0, 1]}}}
  ↓
  {{{[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]}}}
  보다시피 전체적으로 정답에 좀 더 가까워졌다.

=== 반복 (Loop) ===
 1. 거의 모든 유전자가 같아졌고 전체적으로 변화가 거의 없어질때까지 선택, 교차, 변이, 대치를 반복한다.
  i. 눈치챘겠지만 이런 방법으로는 [[운]]이 나쁘면 1111''(2)''에 도달하지 못하고 종료될 수도 있다. 이걸 방지하기 위해서 변이가 있는 것이지만 좀 더 복잡한 문제에서는 항상 최선의 결과가 나오지 않을 수 있다.

=== 종료 ===
 1. 얻은 유전자의 해가 원하던 것인지 확인하고 종료한다.
  i. 1111''(2)''라는 결과를 얻었고, 범위 내의 가장 큰 수인 듯하다!

이렇게 놓고 보면 그냥 간단히 계산기 돌려서 구할 수 있는 문제를 뭣 하러 이렇게 복잡하고 확률의존적인 방식을 써서 구하나 의문이 들 수도 있는데, 쉬운 설명을 위해 단순하고 답이 정해져 있는 문제로 예시를 들어서 그렇게 보이는 것. 실제로는 답이 정해져 있는 것도 아니고 최적해가 이미 알려져있지도 않은 복잡한 문제에 활용을 하게 된다. 이를테면 인공지능에게 이족보행 방법을 가르친다든지. [[https://m.youtube.com/watch?v=pgaEE27nsQw|참고영상]]

== 학교 교과목의 일종으로서 ==
학부과정에서는 [[인공지능]] 과목의 일부 단원에서 이를 다룬다. [[http://kowon.dongseo.ac.kr/~dkkang/AI2011Fall/W0910.pdf|동서대학교 강의자료]]

[[컴퓨터학과]] 대학원 과정에서 종종 '유전 알고리즘' 과목이 개설된다. 'Evolutionary Algorithm'(진화 알고리즘)이라고도 개설된다. [[http://www.cs.uccs.edu/~jkalita/work/cs571/2012/|강의계획서(콜로라도 대학교)]]

주된 주제로는 다음이 있다. 각 수업은 교재나 관련 논문 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: agent(개미)들이 목적지를 향해 나아가는 동안 각 경로에 페로몬을 분비하고, 이후에 지나가는 개미들은 그 경로에 쌓여 있는 페로몬 정보를 이용해 다음 경로를 선택하는 원리를 [[휴리스틱]] 탐색에 적용한 것. 1992년경 만들어졌다.

[[분류:인공지능]][[분류:알고리즘]][[분류:생물정보학]][[분류:컴퓨터 공학]]