유전 알고리즘(Genetic Algorithm, GA)은 자연계의 생물 진화 과정, 특히 다윈의 적자생존 이론과 유전학의 원리를 컴퓨터 모델로 구현한 전역 최적화 기법이다. 1975년 미국의 컴퓨터 과학자 존 홀랜드(John Holland)가 저서 《Adaptation in Natural and Artificial Systems》에서 처음 체계적으로 소개하였으며, 이후 데이비드 골드버그(David Goldberg) 등에 의해 발전되었다.
유전 알고리즘은 특정 문제에 국한된 알고리즘이라기보다는, 문제 해결을 위한 하나의 접근 방법론에 가깝다. 풀고자 하는 문제의 가능한 해들을 정해진 자료구조(염색체)로 표현한 뒤, 이들을 점진적으로 변형하여 더 나은 해를 생성해 나간다. 목적 함수가 불연속적이거나, 미분이 불가능하거나, 비선형성이 높아 표준 최적화 알고리즘으로 풀기 어려운 문제에 주로 적용된다.
구성 요소
유전 알고리즘을 적용하기 위해서는 두 가지 준비가 필요하다. 첫째, 문제의 가능한 해를 염색체(Chromosome) 형태로 표현하는 인코딩(encoding) 방식의 정의이다. 염색체는 유전자(Gene)들의 배열로 구성되며, 일반적으로 이진 문자열, 실수 벡터, 또는 문자열 등의 형태가 사용된다. 둘째, 각 염색체가 문제의 해로서 얼마나 적합한지를 평가하는 적합도 함수(Fitness Function)의 정의이다.
기본 연산
유전 알고리즘은 선택(Selection), 교차(Crossover), 변이(Mutation), 대치(Replacement)의 네 가지 주요 연산으로 구성된다.
선택 연산은 현재 세대의 해집단(Population)에서 다음 세대를 생성할 부모 해를 선별하는 과정이다. 적합도가 높은 해일수록 선택될 확률이 높아지도록 설계된다. 대표적인 방법으로는 적합도 비례 룰렛 휠 선택(Roulette Wheel Selection), 토너먼트 선택(Tournament Selection), 순위 기반 선택(Rank-based Selection) 등이 있다.
교차 연산은 선택된 두 부모 해의 유전자 일부를 서로 교환하여 새로운 자식 해를 생성하는 과정이다. 이는 생물의 유전자 재조합에 대응하며, 유전 알고리즘의 핵심적인 탐색 연산으로 간주된다. 1점 교차, 2점 교차, 균등 교차(Uniform Crossover) 등 다양한 방식이 존재한다.
변이 연산은 일정한 확률로 염색체의 일부 유전자 값을 임의로 변경하는 연산이다. 이는 해집단의 유전적 다양성을 유지하고, 지역 최적해(Local Optimum)에 빠지는 것을 방지하는 역할을 한다. 변이 확률은 일반적으로 0.001에서 0.01 사이의 낮은 값으로 설정된다.
대치 연산은 교차와 변이를 통해 생성된 새로운 해들을 기존 해집단에 반영하고, 기존의 열등한 해들을 제거하는 과정이다.
알고리즘의 흐름
유전 알고리즘의 전형적인 수행 과정은 다음과 같다. 먼저 무작위로 초기 해집단을 생성한다. 이후 각 해의 적합도를 평가하고, 적합도에 기반하여 부모 해를 선택한다. 선택된 부모 해들 간의 교차와 변이를 통해 자식 해를 생성하고, 이를 기존 해집단과 대치하여 다음 세대를 구성한다. 이 과정을 종료 조건(설정된 최대 세대 수 도달, 적합도가 일정 수준에 도달, 또는 해집단의 수렴 등)이 만족될 때까지 반복한다. 최종적으로 가장 적합도가 높은 해를 결과로 반환한다.
특성 및 한계
유전 알고리즘은 기울기(Gradient) 정보 없이도 탐색이 가능하며, 병렬적이고 전역적인 탐색이 가능하다는 장점이 있다. 그러나 계산 비용이 크고, 해집단 크기, 교차율, 변이율 등의 매개변수 설정에 따라 성능 차이가 크며, 전역 최적해로의 수렴을 이론적으로 보장하지는 않는다. 일반적으로 최적해에 가까운 근사해를 실용적인 시간 내에 얻는 것을 목표로 한다.
응용 분야
유전 알고리즘은 순회판매원 문제(TSP), 작업 공정 스케줄링(Job Shop Scheduling), VLSI 설계 레이아웃, 데이터베이스 질의 최적화, 신경망 가중치 학습, 로봇 경로 계획, 단백질 구조 예측, 금융 모델링 등 다양한 분야에서 활용되고 있다. 또한 PostgreSQL 데이터베이스의 유전 질의 최적화(GEQO) 모듈과 같이 실제 상용 소프트웨어에도 적용된 사례가 있다.
관련 기법
유전 알고리즘은 진화 연산(Evolutionary Computation)이라는 더 큰 범주의 한 분야이다. 같은 범주에 속하는 기법으로는 실수 벡터를 주로 다루는 진화 전략(Evolution Strategy, ES), 유한 오토마타나 그래프 구조를 다루는 진화 프로그래밍(Evolutionary Programming, EP), 프로그램 자체를 진화시키는 유전 프로그래밍(Genetic Programming, GP) 등이 있다. 이 외에도 개미 집단 최적화(Ant Colony Optimization, ACO), 담금질 기법(Simulated Annealing, SA), 지역 탐색과 유전 알고리즘을 결합한 미미틱 알고리즘(Memetic Algorithm) 등이 관련 기법으로 분류된다.
