정의
유전 알고리즘(Genetic Algorithm)은 자연 선택과 생물의 진화 과정에서 영감을 얻은 최적화 알고리즘의 일종으로, 해를 표현하는 개체들이 유전적 연산을 통해 세대를 거쳐 진화함으로써 최적해에 수렴하도록 설계된 계산 기법이다. 주로 복잡한 최적화 문제나 탐색 공간이 넓은 문제에서 사용된다.
개요
유전 알고리즘은 존 홀런(John Holland)이 1975년대에 제안한 개념으로, 진화 전산학(Evolutionary Computation)의 대표적인 분야 중 하나이다. 이 알고리즘은 문제의 해를 염색체로 모델링하고, 개체군(Population) 내의 각 개체가 적합도(Fitness) 함수에 따라 평가된다. 이후 선택(Selection), 교차(Crossover), 돌연변이(Mutation) 등의 유전 연산을 통해 다음 세대를 생성함으로써 전반적으로 적합도가 높은 해를 도출하는 방식으로 작동한다. 유전 알고리즘은 정확한 해를 보장하지 않지만, 글로벌 최적해에 근접하는 해를 비교적 효율적으로 탐색할 수 있는 강점이 있다.
어원/유래
"유전 알고리즘"이라는 용어는 생물학에서 유전(Genetics)과 관련된 개념을 인공적인 알고리즘에 적용한 데에서 비롯되었다. 영어로는 "Genetic Algorithm"이며, "genetic"은 생물의 유전 정보를 전달하는 메커니즘에서 유래하였고, "algorithm"은 문제 해결을 위한 절차 또는 규칙을 의미한다. 이 용어는 존 홀런이 1975년 출판한 저서 『Adaptation in Natural and Artificial Systems』에서 본격적으로 정립되었다고 알려져 있다.
특징
유전 알고리즘의 주요 특징은 다음과 같다.
- 문제의 해를 문자열(보통 이진수)이나 구조적 형태로 인코딩하여 표현한다.
- 복수의 해(개체)를 동시에 처리하는 집단 기반 탐색 방식을 사용한다.
- 기울기 정보가 필요 없으므로, 미분 불가능하거나 비연속적인 함수에도 적용 가능하다.
- 확률적 탐색 기법으로, 지역 최적해에 빠질 가능성을 줄이면서 전역 탐색을 수행할 수 있다.
- 병렬 처리와 결합이 용이하여 복잡한 문제에 적용하기에 유리하다.
관련 항목
- 진화 알고리즘(Evolutionary Algorithm)
- 유전자 프로그래밍(Genetic Programming)
- 자연 선택(Natural Selection)
- 적합도 함수(Fitness Function)
- 최적화 이론(Optimization Theory)
- 메타휴리스틱(Metaheuristic)