유전 알고리즘

왜 배우는가: 유전 알고리즘은 복잡한 최적화 문제를 탐색 공간 전체를 계산하지 않고 해결하는 대표적 메타휴리스틱이다. 정보관리기술사 시험에서 정의, 절차, 선택 연산(룰렛 휠)과 최적화 기법이 반복해서 출제되므로 개념 구조를 정확히 잡아야 한다.

출제 이력: 제137회 4교시 5번, 제113회 3교시 5번

1. 한 줄 정의와 핵심 키워드

유전 알고리즘은 자연선택과 유전 원리를 모방하여 해의 집단을 선택·교차·돌연변이로 진화시키며 최적해 또는 준최적해를 찾는 확률적 전역 탐색 알고리즘이다.

핵심 키워드는 다음과 같다.

• 유전 알고리즘(Genetic Algorithm, GA)
• 염색체(Chromosome)
• 적합도 함수(Fitness Function)
• 선택(Selection)
• 교차(Crossover)
• 돌연변이(Mutation)
• 세대(Generation)
• 메타휴리스틱(Metaheuristic)

2. 개념 풀이

쉽게 말하면 좋은 해를 남기고 나쁜 해를 버리는 과정을 컴퓨터에서 반복하는 방법이다. 해를 유전자 배열로 바꾸고, 우수한 해끼리 섞어 새로운 해를 만들며, 세대가 거듭될수록 집단이 목적에 가까워진다.

정식 정의는 다음과 같다. 유전 알고리즘은 문제의 가능한 해를 염색체(Chromosome)로 부호화한 해집단(Population)을 두고, 각 염색체의 우수성을 적합도 함수(Fitness Function)로 평가한 뒤, 선택·교차·돌연변이 연산을 반복하는 탐색 알고리즘이다. John Holland가 1970년대 중반에 체계화하였다.

핵심 용어를 풀이하면 다음과 같다. 염색체(Chromosome)는 해를 표현한 비트열이나 값의 배열이다. 하나의 유전자는 염색체의 한 위치에 해당하는 값이다. 적합도 함수(Fitness Function)는 해가 문제를 얼마나 잘 푸는지 수치로 나타내며, 진화 방향을 결정한다. 세대(Generation)는 특정 순간의 해집단을 뜻하고, 한 세대에서 다음 세대가 만들어진다.

특징은 도함수를 쓰지 않고 방향성 있는 탐색과 확률 탐색을 함께 수행하는 점이다. 그래서 연속과 불연속이 섞인 문제, 볼록하지 않은(non-convex) 영역의 문제에도 적용할 수 있다. 다만 최적해를 보장하지는 않는다.

3. 등장 배경과 필요성

전통적 최적화 방법은 도함수를 이용해 한 점씩 탐색하거나 임의의 점에서 출발한다. 이 방식은 국소 최적해에 갇히기 쉽고, 목적함수가 불연속이거나 탐색 공간이 매우 클 때 적용이 어렵다. 조합 최적화처럼 경우의 수가 지수적으로 커지는 문제는 전수 탐색이 현실적이지 않다.

유전 알고리즘은 생물 진화의 원리를 적용해 이 한계를 보완한다. 여러 해를 동시에 다루므로 병렬적 탐색이 가능하고, 확률적 연산으로 국소 최적해를 벗어날 수 있다. 1970년대 초 John Holland의 연구를 기점으로 발전하였으며, 1975년에 자연적응 시스템 연구로 정리되었다고 알려져 있다.

실무에서는 설계 변수가 많고 목적함수 계산이 복잡한 문제에 쓰인다. 예를 들어 일정 계획, 배낭 문제, 경로 탐색, 하이퍼파라미터 탐색 등이다. 시험에서는 정의와 필요성을 묻고 이후 절차와 선택 연산으로 이어지는 출발점이므로 이 세 가지를 먼저 정리해 둘 필요가 있다.

세대마다 해집단을 구성하고 갱신하는 것이 기본 설정이다.

4. 구성요소·원리·절차

유전 알고리즘은 해를 염색체로 표현하고, 초기 집단을 만든 뒤 적합도가 높은 개체를 골라 교차와 변이로 새 세대를 만드는 반복 구조다. 구성요소는 다음 표와 같다.

표의 구성요소는 서로 역할이 달라 혼동하지 않아야 한다. 염색체는 해 전체이고, 유전자는 그 안의 한 자리다. 적합도 함수는 문제마다 새로 설계해야 하는 유일한 부분이다.

원리는 우수한 개체가 우수한 자손을 낳는다는 자연 선택에 있다. 유전 알고리즘은 도함수를 쓰지 않고 방향성 있는 탐색과 확률 탐색을 함께 수행한다. 그래서 연속과 불연속이 섞인 문제나 non-convex 영역에서도 적용할 수 있다.

절차는 다음과 같다.

• 초기 집단을 무작위 또는 휴리스틱으로 생성하고 각 해를 염색체로 부호화한다.
• 적합도 함수로 각 개체를 평가한다.
• 선택(Selection)으로 적합도가 높은 부모를 확률적으로 뽑는다.
• 교차(Crossover)로 두 부모의 유전자 일부를 맞바꿔 자손을 만든다.
• 변이(Mutation)로 자손 유전자 일부를 낮은 확률로 무작위 변경한다.
• 대체(Replacement)로 자손을 집단에 반영한다.
• 종료 조건(최대 세대 수, 수렴, 목표 적합도 도달)을 만족할 때까지 2~6을 반복한다.

선택 단계에서 룰렛 휠은 적합도에 비례한 면적을 준다. 적합도가 1인 해와 5인 해가 있으면 뒤의 해가 룰렛에서 약 5배 넓은 면적을 차지한다. 교차 예로 부모 [10110]과 [01011]의 한 점 교차는 자손 [10011]을 만든다. 이 과정은 부모 선택을 원하는 자손 수에 도달할 때까지 반복한다.

유전 알고리즘은 선택·교차·변이·대체를 종료 조건까지 반복하는 확률적 탐색이다.

5. 관련 법령·기준·표준

유전 알고리즘은 법령이나 고시로 규정된 기법이 아니다. 따라서 본 절의 기준은 학술적으로 널리 쓰이는 설계 관례다. 수치는 문제와 실험에 따라 달라지므로 아래 값은 출발점으로 삼는다.

교차 확률은 높을수록 탐색이 활발하지만 우수 해가 깨질 수 있다. 변이 확률은 다양성을 유지하는 장치이므로 너무 높으면 탐색이 무작위화된다. 표의 값은 고정 값이 아니라 시작점이다.

개정 연혁으로 볼 근거는 없다. 다만 유전 알고리즘의 기본 틀은 John Holland가 1970년대에 제안한 것으로 알려져 있다.

6. 유형과 비교

유전 알고리즘은 부호화 방식, 선택 방식, 교차 방식에 따라 여러 변형으로 나뉜다. 시험에서는 선택 방식의 비교가 가장 자주 묻는다. 룰렛 휠 선택은 적합도 값에 비례해 면적을 배분하고, 순위 선택은 값의 크기 대신 순서를 쓴다. 토너먼트 선택은 무작위로 묶은 그룹에서 최고 개체만 고른다.