검색
색인
유전 알고리즘, 遺傳-, Genetic Algorithm, GA
진화의 핵심 원리인 자연 선택과 유전자의 개념을 이용한 최적화 기법.
주어진 문제에 대한 해답(solution)을 무작위로 생성한 뒤 이 해답 집단을 진화시켜 좋은 해답을 찾는다.
유전 알고리즘은 집단 기반의 최적화 기법인 진화 알고리즘의 한 종류로, 집적 회로 설계, 리보핵산(RNA: Ribonucleic acid) 구조 예측, 인공 신경망 학습 등 매우 다양한 분야의 최적화 및 탐색(search) 문제에 적용되고 있다.


유전 알고리즘에서 문제의 해답(solution)은 고정된 길이의 문자열로 표현되며, 이는 다음 세대를 생성할 때 교차 및 돌연변이 과정의 적용을 용이하게 한다. 해답의 좋고 나쁨의 정도는 최적화 문제의 목적(objective) 함수에 의해 평가되는데, 이를 적합도(fitness) 함수라고 한다.
유전 알고리즘을 구성하는 주요 연산은 ‘선택(selection)’, ‘교차(crossover)’, ‘돌연변이(mutation)’이다. 선택은 현재 세대에서 다음 세대를 생성할 때 사용하는 해답들을 결정하는 연산으로, 적합도에 따라 확률적으로 결정된다. 교차는 두 해답을 결합해 새로운 해답을 만드는 과정으로, 생물의 염색체 교차를 모사한 것이다. 서로 다른 두 해답의 좋은 점을 모두 취하는 새로운 해답을 만들 수 있다. 돌연변이는 해답의 일부분을 무작위로 변형하는 것으로, 지역 최적 해답(local optimum solution)에 빠질 가능성을 줄여 준다.
유전 알고리즘은 1931년 시월 라이트(Sewall Wright)가 제안한 적합도 경관(fitness landscape)의 개념에 영향을 받았고, 1965년 잉고 레켄베르크(Ingo Rechenberg)가 비행기 익형(airfoil)의 최적화에 진화 전략을 적용하면서 유명해졌다.