유전 알고리즘(Genetic Algorithm)이란? : 자연에서 배운 최적화 기법

유전 알고리즘(Genetic Algorithm, GA)은 자연의 진화 과정을 모방한 최적화 기법입니다. 이는 자연선택, 돌연변이, 교차(crossover) 등의 개념을 활용하여 최적의 해(solution)를 탐색하는 방법입니다. 복잡한 문제를 해결할 때 전통적인 수학적 접근법보다 효율적인 경우가 많아, AI, 로봇공학, 머신러닝, 게임 개발, 산업 공학 등 다양한 분야에서 사용됩니다.

이 글에서는 유전 알고리즘의 기본 개념, 동작 원리, 구현 방법, 그리고 Python 코드 예제까지 자세히 설명하겠습니다.

---

1. 유전 알고리즘의 개념

유전 알고리즘(GA)은 생물학적 진화 원리를 기반으로 한 탐색 및 최적화 기법입니다. 주어진 문제의 해를 유전자(DNA)처럼 표현한 후, 세대를 거치면서 최적의 해를 찾아갑니다.

💡 핵심 개념:

• 유전자(Gene): 문제의 해를 표현하는 기본 단위
• 염색체(Chromosome): 여러 개의 유전자로 이루어진 개체(개별 해)
• 집단(Population): 여러 개의 염색체(해)의 집합
• 적합도(Fitness Score): 각 염색체가 문제 해결에 얼마나 적합한지를 평가하는 점수
• 선택(Selection): 높은 적합도를 가진 개체를 다음 세대로 전달
• 교차(Crossover): 두 개의 부모 염색체를 섞어 새로운 개체를 생성
• 돌연변이(Mutation): 일부 유전자를 무작위로 변경하여 다양성을 확보

이 과정을 반복하면서 최적의 해를 찾아가는 것이 유전 알고리즘의 핵심입니다.

반응형

---

2. 유전 알고리즘의 동작 원리

유전 알고리즘은 아래와 같은 과정을 거쳐 최적의 해를 점진적으로 찾아갑니다.

1️⃣ 초기 집단 생성 (Initialization)

• 무작위로 여러 개의 해(염색체)를 생성하여 초기 집단을 만듭니다.
• 각 개체는 문제의 해를 나타내는 이진수(0과 1), 실수 값, 문자열 등의 형태로 표현될 수 있습니다.

2️⃣ 적합도 평가 (Fitness Evaluation)

• 각 개체의 적합도를 평가하여 문제 해결에 얼마나 좋은 해인지 측정합니다.
• 예를 들어, 최단 경로 문제라면 경로의 길이가 짧을수록 높은 적합도를 가집니다.

3️⃣ 선택 (Selection)

• 높은 적합도를 가진 개체를 우선적으로 선택하여 다음 세대에 전달합니다.
• 룰렛 휠 선택(Roulette Wheel Selection), 토너먼트 선택(Tournament Selection) 등의 방법이 사용됩니다.

4️⃣ 교차(Crossover)와 돌연변이(Mutation)

• 선택된 개체들을 교차하여 새로운 개체를 생성합니다.
• 일정 확률로 일부 유전자가 돌연변이를 일으켜 탐색 공간의 다양성을 유지합니다.

5️⃣ 반복 (Iteration)

• 이 과정을 반복하면서 최적의 해를 점진적으로 찾아갑니다.
• 일정한 세대 수가 지나거나 적합도가 특정 기준에 도달하면 알고리즘을 종료합니다.

---

3. 유전 알고리즘 구현 (Python 코드 예제)

아래는 간단한 유전 알고리즘을 Python으로 구현한 코드입니다. 이진 문자열을 이용해 최적의 해를 찾는 문제를 해결하는 예제입니다.

import random

# 유전자(염색체) 길이
GENE_LENGTH = 10
POPULATION_SIZE = 20
MUTATION_RATE = 0.01
GENERATIONS = 100

# 목표 유전자 (예: 모두 1인 유전자 찾기)
TARGET_GENE = "1111111111"

# 개체(염색체) 생성
def generate_chromosome():
    return ''.join(random.choice("01") for _ in range(GENE_LENGTH))

# 적합도 평가 함수
def fitness(chromosome):
    return sum(1 for a, b in zip(chromosome, TARGET_GENE) if a == b)

# 선택 (룰렛 휠 방식)
def selection(population):
    total_fitness = sum(fitness(chromo) for chromo in population)
    pick = random.uniform(0, total_fitness)
    current = 0
    for chromo in population:
        current += fitness(chromo)
        if current > pick:
            return chromo

# 교차 (단일 지점 교차)
def crossover(parent1, parent2):
    point = random.randint(1, GENE_LENGTH - 1)
    return parent1[:point] + parent2[point:], parent2[:point] + parent1[point:]

# 돌연변이
def mutate(chromosome):
    return ''.join(
        gene if random.random() > MUTATION_RATE else random.choice("01")
        for gene in chromosome
    )

# 유전 알고리즘 실행
def genetic_algorithm():
    population = [generate_chromosome() for _ in range(POPULATION_SIZE)]
    
    for generation in range(GENERATIONS):
        population = sorted(population, key=fitness, reverse=True)
        
        if fitness(population[0]) == GENE_LENGTH:
            print(f"Generation {generation}: Solution found -> {population[0]}")
            break

        new_population = []
        
        for _ in range(POPULATION_SIZE // 2):
            parent1, parent2 = selection(population), selection(population)
            child1, child2 = crossover(parent1, parent2)
            new_population.extend([mutate(child1), mutate(child2)])

        population = new_population

    print(f"Best solution: {population[0]}")

# 실행
genetic_algorithm()

---

4. 유전 알고리즘의 활용 사례

유전 알고리즘은 다양한 분야에서 사용됩니다.

✅ 머신러닝 및 AI: 신경망 최적화, 하이퍼파라미터 튜닝
✅ 게임 개발: NPC 행동 최적화, 자동 레벨 생성
✅ 로봇 공학: 로봇 경로 탐색, 자동 제어 시스템
✅ 금융 및 투자: 포트폴리오 최적화, 리스크 분석
✅ 공학 및 제조: 생산 공정 최적화, 스케줄링 문제 해결

---

5. 결론

유전 알고리즘은 자연의 진화 원리를 모방한 강력한 최적화 기법입니다.

• 랜덤 탐색과 최적화 기능을 결합하여 다양한 문제를 해결할 수 있음
• 전통적인 최적화 방법보다 복잡한 문제에서 더 나은 결과를 제공할 수 있음
• Python을 활용하여 쉽게 구현 가능하며 다양한 산업에서 활용됨