[Data Science] Feature Selection - 유전 알고리즘(Genetic Algorithm, GA)

모델 성능을 향상시키기 위해서는 특징 선택(Feature Selection)이라는 과정이 반드시 필요합니다.

굉장히 중요한 단계인데요, 특징 선택은 여러가지 방법론을 활용할 수 있습니다.

 

이번 포스팅에서는 그 중에서도 굉장히 효과가 좋다고 알려진, "유전 알고리즘"에 대해 알아보겠습니다!

---

유전 알고리즘의 이점

 

유전 알고리즘은 기존의 전진 선택, 후진 소거, 단계적 선택과 같은 휴리스틱 기법들 보다
조금 더 많은 시간을 들이지만, 최적 변수 집합을 찾을 가능성이 더 높습니다!

---

유전 알고리즘(Genetic Algorithm, GA)이란?

유전 알고리즘은 진화론적 개념(자연 선택 및 유전)에서 영감을 받아 최적화를 수행하는 메타 휴리스틱(Meta-Heuristic) 알고리즘 입니다.

메타 휴리스틱이란, 닫힌 해가 존재하지 않는 복잡한 문제에 대해서 시행착오를 줄이는 효율적인 해 탐색 기법을 말합니다.

 

쉽게 직관만 가져가자면, 유전 알고리즘의 목표는 "우수한 유전자(해)를 생식을 통해 다음 세대에서도 발현되도록 하는 것"입니다.

https://www.2e.co.kr/news/articleView.html?idxno=205409

---

유전 알고리즘의 핵심 단계

• 선택(Selection) : 현재 가능 해 집합에서 우수한 해들을 선택하여 다음 세대를 생성하기 위한 부모 세대로 지정
• 교배(Crossover) : 선택된 부모 세대들의 유전자를 교환하여 새로운 세대를 생성
• 돌연변이(Mutation) : 낮은 확률로 변이를 발생시켜 Local Optimum에서 탈출할 수 있는 기회 제공
• 적합도(Fitness) : 각 염색체의 품질을 평가하는 함수 

---

유전 알고리즘 절차

유전 알고리즘은 문제 해결을 위해 여러 세대를 거치며 해를 개선해 나가는 방식으로 작동합니다.

아래는 각각의 단계별 주요 내용입니다.

---

Step 1: 염색체(Population) 초기화 및 하이퍼파라미터 설정 (Initiation)

유전 알고리즘의 첫 단계는 초기 해집합(염색체 집합)을 생성하는 것입니다.

• 염색체(Population): 문제의 해를 표현하는 구조로, 초기에는 무작위로 생성됩니다. 예) 이진 문자열, 실수 배열, 또는 기타 구조.
• 하이퍼파라미터: 알고리즘의 작동에 영향을 미치는 변수
  • Population 크기: 한 세대에 존재할 염색체 수
  • 세대 수(Max Generation): 알고리즘의 반복 횟수
  • 교차 확률(Crossover rate): 부모 염색체 간 교차가 발생할 확률
  • 돌연변이 확률(Mutation rate): 유전자 변이가 발생할 확률

---

Step 2: 각 염색체 선택 변수 별 모델 학습

초기화된 염색체들을 바탕으로 문제와 관련된 모델 학습을 수행합니다.

• 각 염색체는 문제의 해를 나타내며, 선택된 변수에 따라 학습이 이루어질 수 있습니다.
• 예를 들어, 머신러닝 모델 학습에서 하이퍼파라미터 조합을 탐색하는 경우, 각 염색체가 다른 하이퍼파라미터 집합으로 학습됩니다.

---

Step 3: 각 염색체 적합도 평가 (Fitness Evaluation)

모든 염색체의 "적합도(Fitness)"를 평가합니다.

• 적합도는 해당 염색체가 문제를 얼마나 잘 해결했는지를 나타냅니다. 예) 회귀 모델의 경우 R² 값, 분류 모델의 경우 정확도(Accuracy) 등이 될 수 있습니다.
• 높은 적합도를 가진 염색체일수록 다음 세대에 선택될 가능성이 높아집니다.

---

Step 4: 우수 염색체 선택 (Selection)

적합도 평가를 바탕으로, 다음 세대에 유전자를 전달할 부모 염색체를 선택합니다.

• 선택 기법:
  • 룰렛휠 선택(Roulette Wheel Selection): 적합도가 높을수록 선택 확률 증가
  • 토너먼트 선택(Tournament Selection): 임의로 선택된 몇 개체 중 적합도가 높은 개체를 선택
  • 엘리트 선택(Elitism): 적합도가 가장 높은 염색체를 무조건 다음 세대에 전달

---

Step 5: 다음 세대 염색체 생성 (Crossover & Mutation)

선택된 부모 염색체를 기반으로 새로운 자식 염색체를 생성합니다.

 

1. 교차(Crossover):

• 부모 염색체 간 일부 유전 정보를 섞어 자식 염색체를 생성
• 교차 기법:
  • 단일점 교차(One-point Crossover): 하나의 교차점을 기준으로 자식 생성
  • 다중점 교차(Multi-point Crossover): 두 개 이상의 교차점을 사용
  • 균등 교차(Uniform Crossover): 각 유전자를 확률적으로 교환

2. 돌연변이(Mutation):

• 자식 염색체의 일부 유전자를 확률적으로 변경하여 탐색 공간의 다양성을 보장
  예) 이진 표현의 경우 특정 비트를 반전(0↔1)

---

Step 6: 최종 변수 집합 선택

최종 세대에 도달하면, 적합도가 가장 높은 염색체를 선택하여 최적 해로 간주합니다.

• 마지막 염색체 집합에서 적합도가 최고인 염색체를 찾습니다.
• 이 염색체가 문제의 최적 해를 나타냅니다.

---

치환(Substitution)

각 세대마다 기존의 염색체 집합을 새로운 자식 염색체 집합으로 치환(Substitution)합니다.
이를 통해 적합도가 점점 높아지며, 알고리즘은 최적 해에 수렴하게 됩니다.

---

유전 알고리즘 구현 (Python)

import random

# 파라미터 설정
POP_SIZE = 10           # 개체군 크기
GENE_LENGTH = 5         # 염색체 길이 (이진수 표현: 0~31)
MAX_GEN = 30            # 최대 세대 수
CROSSOVER_RATE = 0.9    # 교차 확률
MUTATION_RATE = 0.01    # 돌연변이 확률

# 적합도 함수: f(x) = x^2
def fitness(x):
    return x**2

# 이진 문자열로 변환
def to_binary_str(x):
    return format(x, f'0{GENE_LENGTH}b')

# 이진 문자열을 정수로 변환
def to_int(binary_str):
    return int(binary_str, 2)

# 초기 개체군 생성
def init_population(size):
    return [to_binary_str(random.randint(0, 31)) for _ in range(size)]

# 개체군 적합도 평가
def evaluate_population(pop):
    return [fitness(to_int(ind)) for ind in pop]

# 룰렛휠 선택
def selection(pop, fit_values):
    total_fit = sum(fit_values)
    pick = random.uniform(0, total_fit)
    current = 0
    for i, fit in enumerate(fit_values):
        current += fit
        if current >= pick:
            return pop[i]

# 교차(Crossover): 단일점 교차
def crossover(parent1, parent2):
    if random.random() < CROSSOVER_RATE:  # 교차 확률 적용
        point = random.randint(1, GENE_LENGTH - 1)
        child1 = parent1[:point] + parent2[point:]
        child2 = parent2[:point] + parent1[point:]
    else:
        # 교차하지 않고 부모를 그대로 전달
        child1, child2 = parent1, parent2
    return child1, child2

# 돌연변이(Mutation)
def mutate(gene):
    gene_list = list(gene)
    for i in range(len(gene_list)):
        if random.random() < MUTATION_RATE:
            gene_list[i] = '1' if gene_list[i] == '0' else '0'
    return "".join(gene_list)

# 유전 알고리즘 실행
def genetic_algorithm():
    # 초기화
    pop = init_population(POP_SIZE)

    for gen in range(MAX_GEN):
        # 적합도 평가
        fit_values = evaluate_population(pop)
        best_fit = max(fit_values)
        best_ind = pop[fit_values.index(best_fit)]
        avg_fit = sum(fit_values) / len(fit_values)

        # 세대 정보 출력
        print(f"세대 {gen}: 최고 적합도 = {best_fit} (x = {to_int(best_ind)}), 평균 적합도 = {avg_fit:.2f}")

        # 다음 세대 생성
        new_pop = []
        while len(new_pop) < POP_SIZE:
            parent1 = selection(pop, fit_values)
            parent2 = selection(pop, fit_values)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutate(child1)
            child2 = mutate(child2)
            new_pop.extend([child1, child2])

        # 치환
        pop = new_pop[:POP_SIZE]

    # 최종 결과
    fit_values = evaluate_population(pop)
    best_fit = max(fit_values)
    best_ind = pop[fit_values.index(best_fit)]
    print(f"\n최적 해: x = {to_int(best_ind)}, 적합도 = {best_fit}")

# 실행
genetic_algorithm()

코드 실행 결과