쉽게 이해하는 유전자 알고리즘

1. 유전자 알고리즘이란?

이 글 보러 들어온 사람이라면 대충 이게 뭘 하는건지 쯤은 알고 있을거라 생각한다.
모르는 사람을 위해 개념 요약을 적어 놓았다.

2. 이걸 왜 쓸까?

최적화 문제를 푸는 전통적인 방식은 대부분 한 지점에서 시작하여 정해진 규칙에 따라 더 나은 방향으로 점진적으로 이동하는 구조를 가진다. 예를 들어 경사하강법(Gradient Descent)은 함수의 기울기를 따라 꾸준히 내려가 최솟값을 찾는 방식이다. 이런 알고리즘들은 많은 상황에서 효과적이지만, 시작점에 따라 이상한 ‘지역 최적해(Local Optimum)’에 빠져버릴 수 있다는 단점이 존재한다.

반면 유전자 알고리즘은 접근 방식부터 근본적으로 다르다. 하나의 해에서 출발하는 것이 아니라, 수많은 해의 ‘집단(Population)’을 동시에 다룬다. 특정 규칙에 얽매이기보다는, 집단 전체를 다음 세대로 ‘진화’시키는 확률적이고 병렬적인 탐색을 수행한다. 이는 **단순 계산이 아닌 ‘진화적 탐색’**의 개념으로, 알고리즘이 스스로 다양한 해를 탐색하며 전역 최적해(Global Optimum)에 도달할 가능성을 높인다.

이러한 특성 덕분에 유전자 알고리즘은 전통적인 방법으로는 풀기 어려운 복잡한 문제에 매우 효과적이다. 목적 함수가 미분 불가능하거나, 데이터가 불연속적인 경우에도 유연하게 적용할 수 있다. 예를 들어, 수많은 도시를 한 번씩만 방문하고 돌아오는 최단 경로를 찾는 ‘외판원 문제(TSP)’나, 로봇이 스스로 걷는 법을 터득하게 하는 학습 과정, 혹은 항공기 날개와 같은 복잡한 구조물의 최적 설계안을 도출하는 등 다양한 분야에서 쓸수있다.

결론만 쉽게 말하면 가능한 해의 공간 전체를 넓게 탐색하며 최선의 답을 찾아내는 강력한 방법이다.

3. 유전자 알고리즘의 기본 구조

유전자 알고리즘이 최적해를 찾아가는 과정은 생물의 진화 사이클과 매우 유사하다. 이 과정은 몇 가지 핵심적인 단계들로 구성되며, 이 단계들이 순환하면서 집단 전체가 점진적으로 더 나은 방향으로 진화하게 된다. 전체적인 흐름을 이해하면 각 연산(교차, 변이 등)이 어떤 역할을 하는지 명확히 파악할 수 있다.​

유전자 알고리즘은 아래와 같은 기본 구조를 따른다.​

1. 초기 해 집단(Initial Population) 생성:
   가장 먼저, 문제에 대한 가능한 해(Solution)들을 무작위로 여러 개 생성하여 초기 집단을 구성한다. 여기서 각각의 해를 ‘염색체(Chromosome)’라고 부르며, 해를 구성하는 개별 요소들을 ‘유전자(Gene)’라고 한다. 예를 들어, 비밀번호 1357을 찾는 문제라면 [11][12][13][2]이 하나의 염색체가 되고, 1, 3, 5, 7은 각각의 유전자가 될 수 있다.
   ​
2. 적합도 평가(Fitness Evaluation):
   생성된 각각의 염색체가 얼마나 문제의 정답에 가까운지를 평가하여 점수를 매긴다. 이 점수를 ‘적합도(Fitness)’라고 한다. 적합도가 높을수록 더 좋은 해(우수한 개체)임을 의미한다. 예를 들어, 위 비밀번호 찾기 문제에서 [11][12][14][1]이라는 염색체는 정답과 2개의 숫자가 일치하므로 적합도 2점을 부여할 수 있다.​
   
3. 선택(Selection):
   적합도가 높은, 즉 우수한 염색체들이 다음 세대에 유전자를 전달할 ‘부모’로 선택될 확률이 높아진다. 마치 자연에서 환경에 잘 적응한 개체가 살아남아 번식 기회를 더 많이 얻는 것과 같다. 대표적인 선택 방식으로는 룰렛 휠 선택(Roulette Wheel Selection)이 있다.
   ​
4. 교차(Crossover):
   선택된 두 부모 염색체의 유전자를 서로 조합하여 새로운 자손 염색체를 만들어내는 과정이다. 부모 세대의 좋은 형질이 자손에게 유전되는 효과를 모방한다. 이 연산은 유전자 알고리즘의 핵심적인 탐색 메커니즘으로 작용한다.
   
5. 변이(Mutation):
   생성된 자손 염색체의 유전자 중 일부를 아주 낮은 확률로 의도적으로 변경하는 과정이다. 이는 자연의 돌연변이와 같은 역할로, 현재 집단에 없는 새로운 특성을 도입하여 해의 다양성을 유지하고, 자칫 빠질 수 있는 지역 최적해에서 벗어날 기회를 제공한다.​

위의 2~5번 과정이 한 세대(Generation)를 구성하며, 알고리즘은 **세대 교체(Generation Replacement)**를 통해 이 사이클을 반복한다. 오래된 세대는 새로운 자손 세대로 대체되고, 이 진화 과정은 미리 정해둔 종료 조건(예: 특정 세대 수 도달, 만족할 만한 적합도의 해 발견 등)을 만족할 때까지 계속된다.

전체적인 흐름을 도식화하면 아래와 같다.

4. 교차(Crossover)

교차(Crossover)는 유전자 알고리즘의 핵심적인 탐색 연산으로, 부모 세대의 우수한 형질을 자손에게 물려주기 위해 두 부모 염색체의 유전 정보를 ‘교환’하고 ‘재조합’하는 과정이다. 이는 마치 생물학적 부모로부터 자녀가 유전자를 물려받아 새로운 조합의 특성을 갖게 되는 것과 같은 원리다.

교차의 기본 목적은 ‘탐색(Exploration)’이다. 이미 검증된 좋은 해(부모)들의 정보를 조합하여, 기존보다 더 나을 가능성이 있는 새로운 해의 영역을 효율적으로 탐색하는 것이다. 단순히 무작위로 해를 생성하는 것보다 훨씬 발전된 방식이다.

가장 대표적인 교차 방식인 ‘단일점 교차(Single-Point Crossover)’를 예로 들어보자. 아래 도식을 보면 그 원리를 이해할 수 있다.

위 도식처럼, 두 부모 염색체 ABCDEFG와 1234567이 있을 때, 3번째 유전자 뒤를 교차점(Crossover Point)으로 무작위 설정한다. 그리고 그 지점을 기준으로 서로의 뒷부분을 교환하여 새로운 자손인 ABC4567과 123DEFG를 생성한다.

하지만 교차점이 많다고 해서 항상 더 좋은 결과를 얻는 것은 아니다. 교차점이 너무 많으면 부모의 좋은 형질 덩어리(스키마)가 파괴되어 오히려 탐색 성능이 저하될 수 있다. 반대로 교차점이 너무 적으면 새로운 조합이 잘 만들어지지 않아 탐색이 정체될 수 있다. 따라서 교차율(Crossover Rate)과 교차 방식은 문제의 특성에 맞게 신중하게 선택해야 한다.

교차 방식에는 위에서 본 단일점 교차 외에도 다점 교차(Multi-point Crossover), 균등 교차(Uniform Crossover) 등 다양한 방법이 존재한다.

5. 변이(Mutation)

교차 연산이 부모 세대의 좋은 형질을 ‘조합’하여 해를 탐색하는 ‘탐색(Exploration)’에 가깝다면, 변이(Mutation)는 현재 집단에 존재하지 않는 완전히 새로운 유전 정보를 ‘도입’하는 역할을 한다. 이는 마치 생물의 DNA가 복제 오류 등으로 인해 ‘돌연변이’를 일으키는 현상을 모방한 것이다.

변이의 가장 중요한 기능은 해 집단의 다양성을 유지하고, 알고리즘이 지역 최적해(Local Optimum)에 빠지는 것을 방지하는 것이다. 선택과 교차만 계속 반복하면 모든 염색체가 서로 비슷해지면서 특정 지점에서 더 이상 발전하지 못하는 상태에 놓일 수 있다. 이때 변이가 새로운 가능성을 열어주는 것이다.

변이는 일반적으로 아주 낮은 확률(보통 0.1% ~ 1%)로 일어나게 한다. 특정 유전자를 무작위로 선택하여 그 값을 임의로 변경하는 방식으로 동작한다. 아래 도식은 이진수(0과 1)로 표현된 염색체에서 변이가 발생하는 과정을 보여준다

위 도식처럼, 1011010이라는 염색체에서 5번째 유전자(0)가 변이 대상으로 선택되면, 그 값이 1로 바뀌어 1011110이라는 새로운 염색체가 탄생한다. 이 새로운 염색체는 교차만으로는 절대 만들어질 수 없었던 개체다.

물론, 변이는 대부분의 경우 해의 품질을 떨어뜨린다. 정답에 가까워지고 있던 해가 갑자기 엉뚱한 방향으로 튈 수 있기 때문이다. 하지만 ‘가끔 발생하는 성공적인 변이’가 집단 전체의 품질을 획기적으로 향상시키는 역할을 한다. 알고리즘이 더 넓은 해 공간을 탐험하게 만드는 일종의 장치인 셈이다.

변이율(Mutation Rate)을 어떻게 설정하느냐는 매우 중요하다. 변이율이 너무 높으면 알고리즘이 최적해로 수렴하지 못하고 무작위 탐색에 가까워지며, 너무 낮으면 지역 최적해에 빠져 헤어나오지 못할 위험이 커진다. 따라서 문제의 특성과 알고리즘의 진행 상황에 따라 변이율을 조절하는 기법(예: 동적 변이)도 사용된다.

6. 적합도(Fitness)와 평가 함수 설계

지금까지 선택, 교차, 변이를 통해 더 나은 해를 만드는 과정을 설명했다. 그렇다면 어떤 해가 ‘좋은 해’이고 어떤 해가 ‘나쁜 해’인지 컴퓨터는 어떻게 판단할까? 그 역할을 하는 것이 적합도 평가(Fitness Evaluation)와 그 적합도 함수(Fitness Function)다.

적합도 함수는 특정 염색체(해)가 주어진 문제를 얼마나 잘 해결하는지를 정량적인 점수(적합도)로 환산해주는 척도다. 이 점수가 높을수록 더 우수한 해로 간주하며, 다음 세대에 선택될 확률이 높아진다. 이는 머신러닝에서 모델의 예측값과 실제값의 차이(오차)를 계산하는 비용 함수(Cost Function)와 매우 유사한 개념이다. 비용 함수는 그 값이 작을수록 좋은 모델인 반면, 적합도 함수는 일반적으로 그 값이 클수록 좋은 해를 의미한다는 점에서 방향만 반대일 뿐, 그 역할은 동일하다.

좋은 적합도 함수를 설계하는 것은 유전자 알고리즘의 성능을 좌우하는 가장 중요한 과정이다. 적합도 함수가 문제의 본질을 제대로 반영하지 못하면, 알고리즘은 엉뚱한 방향으로 수렴하거나 최적해를 찾지 못할 수 있다.

적합도 함수는 보통 다음 3단계를 거쳐 설계된다. ‘비밀번호 4자리를 맞추는 문제’를 예시로 들어보자. (정답: 8520)

1단계: 규칙(제약조건) 정리하기

먼저 문제에서 가장 중요한 규칙부터 덜 중요한 규칙 순으로 우선순위를 정한다.

기타 규칙: 정답에 포함되지 않은 숫자는 패널티를 부여한다.

2단계: 보상(Reward)과 벌점(Penalty) 결정

정리된 규칙에 따라 상점과 벌점을 구체적으로 정한다.

정답에 없는 숫자: -2점 (벌점)

3단계: 적합도 함수 설계 및 계산

이제 위 규칙을 바탕으로 최종 적합도를 계산하는 함수를 만든다.

적합도 = (위치/값 일치 개수 × 10) + (값만 일치 개수 × 1) + (불일치 개수 × -2)

예를 들어, 8123이라는 염색체의 적합도를 계산해 보자.

• 위치/값 일치: 8, 2 (2개) → 2 × 10 = +20점
• 값만 일치: 없음 → 0 × 1 = 0점
• 불일치: 1, 3 (2개) → 2 × -2 = -4점
• 최종 적합도: 20 + 0 – 4 = 16점

만약 다른 염색체 5082의 적합도를 계산하면 (값만 4개 일치) 4점이 된다. 따라서 유전자 알고리즘은 8123이 5082보다 훨씬 우수한 해라고 판단하고, 8123을 다음 세대의 부모로 선택할 확률을 높여준다.

7. 구체적인 절차 및 알고리즘 구조 코드 예시

지금까지 배운 유전자 알고리즘의 모든 구성 요소(초기화, 적합도 평가, 선택, 교차, 변이)를 하나로 합쳐 실제 동작하는 코드로 만들어 보자. 가장 이해하기 쉬운 문제인 ‘특정 문자열 맞추기’를 목표로 파이썬 코드를 작성했다.

이 코드의 목표는 무작위 문자열로 이루어진 초기 집단에서 시작하여, 세대를 거듭하며 “Hello, World!”라는 목표 문자열로 진화해 나가는 과정을 보여주는 것이다.

전체 파이썬 코드

import random
import string

# --- 하이퍼파라미터 설정 ---
TARGET = "Hello, World!"  # 목표 문자열
GENE_POOL = string.printable  # 유전자 풀 (출력 가능한 모든 ASCII 문자)
POPULATION_SIZE = 100  # 인구 집단의 크기
MUTATION_RATE = 0.01  # 변이 확률
ELITISM_SIZE = 1  # 다음 세대에 바로 전달할 엘리트 개체의 수

# --- 1. 염색체(개체) 생성 ---
def create_individual():
    """목표 문자열과 동일한 길이의 무작위 염색체를 생성한다."""
    return ''.join(random.choice(GENE_POOL) for _ in range(len(TARGET)))

# --- 2. 적합도 함수 ---
def calculate_fitness(individual):
    """
    적합도를 계산한다. 목표 문자열과 일치하는 문자의 개수를 점수로 한다.
    수식: f(I) = Σ [T[i] == I[i]]
    """
    score = 0
    for i in range(len(TARGET)):
        if individual[i] == TARGET[i]:
            score += 1
    return score

# --- 3. 선택 연산 ---
def selection(population_with_fitness):
    """
    적합도에 기반한 룰렛 휠 선택 방식으로 부모를 선택한다.
    적합도가 높을수록 선택될 확률이 높아진다.
    """
    # population_with_fitness는 (염색체, 적합도) 튜플의 리스트
    population, fitness_scores = zip(*population_with_fitness)
    
    # 적합도 합계가 0인 경우(초기 세대 등)를 대비해 모든 개체에 동일한 확률 부여
    if sum(fitness_scores) == 0:
        return random.choice(population)
        
    return random.choices(population, weights=fitness_scores, k=1)[0]

# --- 4. 교차 연산 ---
def crossover(parent1, parent2):
    """단일점 교차를 수행하여 자손을 생성한다."""
    crossover_point = random.randint(1, len(TARGET) - 1)
    child = parent1[:crossover_point] + parent2[crossover_point:]
    return child

# --- 5. 변이 연산 ---
def mutation(individual):
    """변이 확률에 따라 각 유전자를 무작위로 변경한다."""
    mutated_individual = ""
    for gene in individual:
        if random.random() < MUTATION_RATE:
            mutated_individual += random.choice(GENE_POOL)
        else:
            mutated_individual += gene
    return mutated_individual

# --- 메인 실행 로직 ---
if __name__ == "__main__":
    # 1. 초기 집단 생성
    population = [create_individual() for _ in range(POPULATION_SIZE)]
    
    generation = 0
    while True:
        generation += 1
        
        # 2. 적합도 평가
        population_with_fitness = [(ind, calculate_fitness(ind)) for ind in population]
        
        # 3. 현재 세대에서 가장 우수한 개체 출력
        population_with_fitness.sort(key=lambda x: x[1], reverse=True)
        best_individual, best_fitness = population_with_fitness[0]
        
        print(f"세대: {generation:4d} | 적합도: {best_fitness:2d}/{len(TARGET)} | 최적 개체: {best_individual}")
        
        # 4. 종료 조건 확인
        if best_fitness == len(TARGET):
            print("\n목표 달성!")
            break
            
        # 5. 다음 세대 생성
        next_generation = []
        
        # 5-1. 엘리티즘: 가장 우수한 개체를 그대로 다음 세대에 전달
        elites = [ind for ind, fit in population_with_fitness[:ELITISM_SIZE]]
        next_generation.extend(elites)
        
        # 5-2. 나머지 집단 생성 (선택, 교차, 변이)
        while len(next_generation) < POPULATION_SIZE:
            parent1 = selection(population_with_fitness)
            parent2 = selection(population_with_fitness)
            
            child = crossover(parent1, parent2)
            mutated_child = mutation(child)
            
            next_generation.append(mutated_child)
            
        # 6. 세대 교체
        population = next_generation

각 함수는 생물의 진화 과정에 있는 특정 단계를 수학적, 논리적으로 모방한다. 주요 함수인 적합도 평가와 선택의 내부 로직을 자세히 살펴보자.

적합도 함수(Fitness Function)의 수학적 모델

적합도 함수는 문제의 목표를 수치적으로 정의하는 가장 중요한 요소다. 이번 예제에서 사용한 ‘문자열 일치’ 적합도 함수 f(I)는 다음과 같은 지시 함수(Indicator Function)의 합으로 모델링할 수 있다

$ f(I) = \sum_{i=0}^{L-1} \mathbb{I}(T_i = I_i) $

수식 해설:

• I: 평가 대상이 되는 하나의 개체(Individual), 즉 염색체를 의미한다. 예시 코드에서는 individual 변수에 해당한다.
• T: 우리가 목표로 하는 정답 문자열(Target)이다. 예시 코드에서는 “Hello, World!”다.
• L: 염색체의 길이(Length)를 나타낸다.
• i: 염색체 내 유전자의 위치를 나타내는 인덱스로, 0부터 시작한다.
• $ T_i $와 $ l_i $: 각각 목표 문자열과 개체 염색체의 i번째 문자를 의미한다.
• $ \mathbb{I}(condition) $: 지시 함수다. 괄호 안의 조건(T_i = I_i)이 참이면 1을 반환하고, 거짓이면 0을 반환한다.
• $ \sum_{i=0}^{L-1} $: i를 0부터 L-1까지 1씩 증가시키면서 모든 결과를 더하라는 기호다.

결론적으로 이 수식은 “염색체 I와 목표 문자열 T를 첫 번째 문자부터 끝까지 하나씩 비교하여, 같은 위치에 같은 문자가 나올 때마다 1점씩 부여하여 그 총합을 최종 적합도 점수로 한다”는 의미를 수학적으로 표현한 것이다. 코드에서는 for 루프와 if 조건문을 통해 이 계산을 수행한다.

선택(Selection)의 확률 모델: 룰렛 휠 선택

선택 과정은 우수한 개체가 다음 세대에 유전자를 전달할 기회를 더 많이 갖도록 설계된다. ‘룰렛 휠 선택(Roulette Wheel Selection)’ 방식은 각 개체의 적합도에 비례하여 선택 확률을 할당한다. 개체 $ I_j $가 부모로 선택될 확률 $ P(\text{select } I_j) $는 다음과 같다.

$ P(\text{select } I_j) = \frac{f(I_j)}{\sum_{k=1}^{N} f(I_k)} $

수식 해설:

• $ f(I_j) $: 개체 $ j $의 적합도 점수를 의미한다.
• $ N $: 전체 집단(Population)의 크기다. 예시 코드에서는 POPULATION_SIZE에 해당한다.
• $ \sum_{k=1}^{N} f(I_k) $: 집단에 속한 모든 개체($ k=1 $부터 $ N $까지)의 적합도를 전부 더한 총합을 의미한다.
• 이 수식은 전체 룰렛 판의 크기(적합도 총합)에서 특정 개체가 차지하는 영역의 크기(개별 적합도)가 바로 그 개체가 선택될 확률이라는 것을 의미한다. 예를 들어, 어떤 개체의 적합도가 집단 전체 적합도 합의 10%를 차지한다면, 그 개체는 10%의 확률로 부모로 선택된다.

파이썬 코드의 random.choices(population, weights=fitness_scores, k=1) 부분이 바로 이 수학적 모델을 구현한 것이다. weights 인자에 각 개체의 적합도 리스트를 전달함으로써, 라이브러리가 자동으로 적합도에 비례하는 확률에 따라 개체를 선택해준다. 이 과정을 통해 자연스럽게 우수한 개체는 더 많이 선택되고, 부적합한 개체는 도태되는 ‘자연 선택’의 원리가 구현된다.